Tetap teratur dengan koleksi
Simpan dan kategorikan konten berdasarkan preferensi Anda.
Salah satu masalah pengoptimalan kombinatorial yang paling terkenal adalah
masalah penetapan. Berikut ini contohnya: anggaplah sekelompok pekerja perlu melakukan serangkaian tugas, dan untuk
setiap pekerja dan tugas, ada biaya untuk menetapkan pekerja ke tugas tersebut.
Masalahnya adalah menetapkan setiap pekerja paling banyak pada satu tugas, tanpa dua pekerja
yang melakukan tugas yang sama, sekaligus meminimalkan total biaya.
Anda dapat memvisualisasikan masalah ini melalui grafik di bawah ini, yang berisi empat
pekerja dan empat tugas. Bagian tepi mewakili semua cara yang memungkinkan untuk menetapkan pekerja
ke tugas. Label di tepian adalah biaya penugasan pekerja.
Penetapan sesuai dengan subset tepi, tempat setiap pekerja memiliki
satu tepi yang mengarah ke luar, dan tidak ada dua pekerja yang memiliki tepi yang mengarah ke tugas
yang sama. Satu kemungkinan tugas ditampilkan di bawah ini.
Total biaya tugas adalah 70 + 55 + 95 + 45 = 265.
Bagian berikutnya menunjukkan cara menyelesaikan
masalah tugas, menggunakan pemecah MIP dan pemecah CP-SAT.
Alat lain untuk menyelesaikan soal tugas
OR-Tools juga menyediakan beberapa alat lain untuk memecahkan masalah tugas,
yang dapat lebih cepat daripada pemecah MIP atau CP:
Namun, alat-alat ini hanya dapat memecahkan jenis masalah penugasan yang sederhana.
Jadi, untuk pemecah masalah umum yang dapat menangani berbagai masalah (dan cukup
cepat untuk sebagian besar aplikasi), kami merekomendasikan pemecah masalah MIP dan CP-SAT.
[[["Mudah dipahami","easyToUnderstand","thumb-up"],["Memecahkan masalah saya","solvedMyProblem","thumb-up"],["Lainnya","otherUp","thumb-up"]],[["Informasi yang saya butuhkan tidak ada","missingTheInformationINeed","thumb-down"],["Terlalu rumit/langkahnya terlalu banyak","tooComplicatedTooManySteps","thumb-down"],["Sudah usang","outOfDate","thumb-down"],["Masalah terjemahan","translationIssue","thumb-down"],["Masalah kode / contoh","samplesCodeIssue","thumb-down"],["Lainnya","otherDown","thumb-down"]],["Terakhir diperbarui pada 2024-08-09 UTC."],[[["The assignment problem focuses on optimally assigning workers to tasks to minimize the total cost, where each worker is assigned at most one task and no task is assigned to multiple workers."],["This problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment."],["OR-Tools offers various solvers like MIP, CP-SAT, Linear Sum Assignment, and Minimum Cost Flow, but MIP and CP-SAT are recommended for their versatility and efficiency in handling a broader range of assignment problems."]]],["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"]]
