Koleksiyonlar ile düzeninizi koruyun
İçeriği tercihlerinize göre kaydedin ve kategorilere ayırın.
Kombinasyonel optimizasyon problemlerinden en çok bilinenlerden biri atama problemidir. Bir örnek verelim: Bir çalışanın bir dizi görevi gerçekleştirmesi gerektiğini ve her çalışan ve görev için, söz konusu çalışanı
göreve atamanın bir maliyeti olduğunu varsayalım.
Problem, toplam maliyeti en aza indirirken, her çalışana en fazla bir göreve aynı görevi gerçekleştiren iki çalışan olmadan atamaktır.
Bu sorunu dört çalışan ve dört görevden oluşan aşağıdaki grafikle görselleştirebilirsiniz. Kenarlar, çalışanları görevlere atamanın mümkün olan tüm yollarını temsil eder. Kenarlardaki etiketler, çalışanları görevlere atama maliyetleridir.
Atama, kenarların bir alt kümesine karşılık gelir. Bu alt kümede her çalışanın en fazla bir kenarı dışarı çıkarken, iki çalışanın da aynı göreve giden kenarları yoktur. Olası bir atama aşağıda gösterilmektedir.
Ödevin toplam maliyeti: 70 + 55 + 95 + 45 = 265.
Sonraki bölümde, hem MIP çözücü hem de CP-SAT çözücüyü kullanarak bir ödev probleminin nasıl çözüleceği açıklanmaktadır.
Ödev sorunlarını çözmek için diğer araçlar
VEYA araçları, atama problemlerini çözmek için MIP ya da CP çözücülerden daha hızlı olabilecek birkaç araç daha sunar:
Ancak bu araçlar yalnızca basit ödev problemi türlerini çözebilir.
Bu nedenle, çok çeşitli problemleri çözebilen (ve çoğu uygulama için yeterince hızlı olan) genel çözücüler için MIP ve CP-SAT çözücülerini öneririz.
[[["Anlaması kolay","easyToUnderstand","thumb-up"],["Sorunumu çözdü","solvedMyProblem","thumb-up"],["Diğer","otherUp","thumb-up"]],[["İhtiyacım olan bilgiler yok","missingTheInformationINeed","thumb-down"],["Çok karmaşık / çok fazla adım var","tooComplicatedTooManySteps","thumb-down"],["Güncel değil","outOfDate","thumb-down"],["Çeviri sorunu","translationIssue","thumb-down"],["Örnek veya kod sorunu","samplesCodeIssue","thumb-down"],["Diğer","otherDown","thumb-down"]],["Son güncelleme tarihi: 2024-08-09 UTC."],[],["The content describes the assignment problem, a combinatorial optimization challenge where workers are assigned to tasks to minimize total cost. Each worker is assigned to at most one task, and each task is done by at most one worker. The example shows how the problem can be represented graphically, with edges representing possible assignments and their costs. The total cost is calculated by adding up the costs of the assigned edges. OR-Tools offer multiple tools to solve such problems, among which the MIP and CP-SAT are the most general.\n"]]
