Anda dapat menggunakan pemecah alur biaya min untuk menyelesaikan kasus khusus masalah penetapan.
Faktanya, aliran biaya min sering kali dapat memberikan solusi lebih cepat daripada pemecah MIP atau CP-SAT. Namun, MIP dan CP-SAT dapat menyelesaikan kelas masalah yang lebih besar daripada aliran biaya minimum, sehingga dalam banyak kasus MIP atau CP-SAT adalah pilihan terbaik.
Bagian berikut menampilkan program Python yang menyelesaikan masalah penetapan berikut menggunakan pemecah alur biaya min:
- Contoh penetapan linear minimal.
- Masalah penugasan dengan tim pekerja.
Contoh penetapan linear
Bagian ini menunjukkan cara menyelesaikan contoh, yang dijelaskan di bagian Pemecah Soal Tugas Linear, sebagai masalah alur biaya min.
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
Python
from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
Mendeklarasikan pemecah masalah
Kode berikut membuat pemecah alur biaya minimum.
Python
# Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
Membuat data
Diagram alur untuk soal ini terdiri dari grafik bipartit untuk matriks biaya (lihat ringkasan penetapan untuk contoh yang sedikit berbeda), dengan tambahan sumber dan sink.
Data berisi empat array berikut, yang sesuai dengan node awal, node akhir, kapasitas, dan biaya untuk soal tersebut. Panjang setiap {i>array<i} adalah jumlah busur dalam grafik.
Python
# Define the directed graph for the flow. start_nodes = ( [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8] ) end_nodes = ( [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9] ) capacities = ( [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] ) costs = ( [0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0] ) source = 0 sink = 9 tasks = 4 supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
C++
// Define four parallel arrays: sources, destinations, capacities, // and unit costs between each pair. For instance, the arc from node 0 // to node 1 has a capacity of 15. const std::vector<int64_t> start_nodes = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; const std::vector<int64_t> end_nodes = {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; const std::vector<int64_t> capacities = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = {0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 9; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
Java
// Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; int[] endNodes = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; int[] capacities = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
C#
// Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 }; int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 }; int[] capacities = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0 }; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
Untuk memperjelas cara data disiapkan, setiap array dibagi menjadi tiga sub-array:
- Array pertama berkaitan dengan busur yang mengarah keluar dari sumber.
- Array kedua sesuai dengan busur antara pekerja dan tugas.
Untuk
costs
, ini hanyalah matriks biaya (digunakan oleh pemecah penetapan linear), yang disatukan menjadi vektor. - Array ketiga sesuai dengan busur yang mengarah ke sink.
Data tersebut juga menyertakan vektor supplies
, yang memberikan pasokan di setiap
node.
Cara masalah aliran biaya min merepresentasikan masalah penetapan
Bagaimana masalah aliran biaya min. di atas mewakili masalah penugasan? Pertama, karena kapasitas setiap busur adalah 1, persediaan 4 pada sumber memaksa masing-masing dari keempat busur yang mengarah ke pekerja memiliki aliran 1.
Selanjutnya, kondisi flow-in-equal-flow-out memaksa aliran keluar dari setiap pekerja menjadi 1. Jika memungkinkan, pemecah masalah akan mengarahkan aliran tersebut ke alur biaya minimum yang mengarah ke setiap pekerja. Namun, pemecah masalah tidak dapat mengarahkan alur dari dua pekerja yang berbeda ke satu tugas. Jika ya, akan ada alur gabungan 2 pada tugas tersebut, yang tidak dapat dikirim melalui busur tunggal dengan kapasitas 1 dari tugas ke sink. Artinya, pemecah masalah hanya dapat menetapkan tugas kepada satu pekerja, seperti yang diwajibkan oleh masalah penetapan.
Terakhir, kondisi flow-in-equals-flow-out memaksa setiap tugas untuk memiliki aliran keluar 1, sehingga setiap tugas dilakukan oleh beberapa pekerja.
Membuat grafik dan batasan
Kode berikut membuat grafik dan batasan.
Python
# Add each arc. for i in range(len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(len(supplies)): smcf.set_node_supply(i, supplies[i])
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); }
Memanggil pemecah masalah
Kode berikut memanggil pemecah dan menampilkan solusi.
Python
# Find the minimum cost flow between node 0 and node 10. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
Solusi ini terdiri dari alur antara pekerja dan tugas yang diberi alur 1 oleh pemecah. (Busur yang terhubung ke sumber atau sink bukan bagian dari solusi.)
Program akan memeriksa setiap busur untuk melihat apakah memiliki flow 1. Jika demikian, program akan mencetak
Tail
(node awal) dan Head
(node akhir) busur, yang sesuai dengan
pekerja dan tugas dalam penetapan.
Output program
Python
if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or into sink. if smcf.tail(arc) != source and smcf.head(arc) != sink: # Arcs in the solution have a flow value of 1. Their start and end nodes # give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}")
C++
if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; }
Java
if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); }
Berikut adalah output program.
Total cost = 265 Worker 1 assigned to task 8. Cost = 70 Worker 2 assigned to task 7. Cost = 55 Worker 3 assigned to task 6. Cost = 95 Worker 4 assigned to task 5. Cost = 45 Time = 0.000245 seconds
Hasilnya sama dengan hasil untuk pemecah tugas linear (kecuali untuk penomoran pekerja dan biaya yang berbeda). Pemecah tugas linear sedikit lebih cepat daripada aliran biaya minimum — 0,000147 detik versus 0,000458 detik.
Seluruh program
Seluruh program ditampilkan di bawah ini.
Python
"""Linear assignment example.""" from ortools.graph.python import min_cost_flow def main(): """Solving an Assignment Problem with MinCostFlow.""" # Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow() # Define the directed graph for the flow. start_nodes = ( [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8] ) end_nodes = ( [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9] ) capacities = ( [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] ) costs = ( [0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0] ) source = 0 sink = 9 tasks = 4 supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks] # Add each arc. for i in range(len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(len(supplies)): smcf.set_node_supply(i, supplies[i]) # Find the minimum cost flow between node 0 and node 10. status = smcf.solve() if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or into sink. if smcf.tail(arc) != source and smcf.head(arc) != sink: # Arcs in the solution have a flow value of 1. Their start and end nodes # give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}") if __name__ == "__main__": main()
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h" namespace operations_research { // MinCostFlow simple interface example. void AssignmentMinFlow() { // Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow; // Define four parallel arrays: sources, destinations, capacities, // and unit costs between each pair. For instance, the arc from node 0 // to node 1 has a capacity of 15. const std::vector<int64_t> start_nodes = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; const std::vector<int64_t> end_nodes = {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; const std::vector<int64_t> capacities = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = {0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 9; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. int status = min_cost_flow.Solve(); if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; } } } // namespace operations_research int main() { operations_research::AssignmentMinFlow(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase; /** Minimal Assignment Min Flow. */ public class AssignmentMinFlow { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; int[] endNodes = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; int[] capacities = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve(); if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private AssignmentMinFlow() {} }
C#
using System; using Google.OrTools.Graph; public class AssignmentMinFlow { static void Main() { // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 }; int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 }; int[] capacities = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0 }; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve(); if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); } } }
Penugasan ke tim pekerja
Bagian ini menampilkan masalah tugas yang lebih umum. Dalam masalah ini, enam pekerja dibagi menjadi dua tim. Masalahnya adalah menetapkan empat tugas kepada pekerja sehingga beban kerja memiliki keseimbangan yang sama di antara tim — yaitu, sehingga setiap tim melakukan dua tugas.
Untuk solusi pemecah MIP atas masalah ini, lihat Penetapan ke Tim Pekerja.
Bagian berikut menjelaskan program yang memecahkan masalah menggunakan pemecah alur biaya min.
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
Python
from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
Mendeklarasikan pemecah masalah
Kode berikut membuat pemecah alur biaya minimum.
Python
smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
Membuat data
Kode berikut akan membuat data untuk program.
Python
# Define the directed graph for the flow. team_a = [1, 3, 5] team_b = [2, 4, 6] start_nodes = ( # fmt: off [0, 0] + [11, 11, 11] + [12, 12, 12] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] + [7, 8, 9, 10] # fmt: on ) end_nodes = ( # fmt: off [11, 12] + team_a + team_b + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] + [13, 13, 13, 13] # fmt: on ) capacities = ( # fmt: off [2, 2] + [1, 1, 1] + [1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] # fmt: on ) costs = ( # fmt: off [0, 0] + [0, 0, 0] + [0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95] + [0, 0, 0, 0] # fmt: on ) source = 0 sink = 13 tasks = 4 # Define an array of supplies at each node. supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
C++
// Define the directed graph for the flow. const std::vector<int64_t> team_A = {1, 3, 5}; const std::vector<int64_t> team_B = {2, 4, 6}; const std::vector<int64_t> start_nodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; const std::vector<int64_t> end_nodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; const std::vector<int64_t> capacities = {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 13; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
Java
// Define the directed graph for the flow. // int[] teamA = new int[] {1, 3, 5}; // int[] teamB = new int[] {2, 4, 6}; int[] startNodes = new int[] {0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; int[] capacities = new int[] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
C#
// Define the directed graph for the flow. int[] teamA = { 1, 3, 5 }; int[] teamB = { 2, 4, 6 }; // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10 }; int[] endNodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13 }; int[] capacities = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0 }; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
Pekerja sesuai dengan node 1 - 6. Tim A terdiri dari pekerja 1, 3, dan 5, dan tim B terdiri dari pekerja 2, 4, dan 6. Tugas diberi nomor 7 - 10.
Ada dua node baru, 11 dan 12, antara sumber dan pekerja. Node 11 terhubung ke node untuk tim A, dan Node 12 terhubung ke node untuk tim B, dengan busur kapasitas 1. Grafik di bawah hanya menampilkan node dan busur dari sumber ke pekerja.
Kunci untuk menyeimbangkan beban kerja adalah sumber 0 terhubung ke node 11 dan 12 melalui busur kapasitas 2. Artinya node 11 dan 12 (sehingga tim A dan B) dapat memiliki aliran maksimum 2. Hasilnya, setiap tim dapat melakukan paling banyak dua tugas.
Membuat batasan
Python
# Add each arc. for i in range(0, len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(0, len(supplies)): smcf.set_node_supply(i, supplies[i])
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); }
Memanggil pemecah masalah
Python
# Find the minimum cost flow between node 0 and node 10. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
Output program
Python
if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or intermediate, or into sink. if ( smcf.tail(arc) != source and smcf.tail(arc) != 11 and smcf.tail(arc) != 12 and smcf.head(arc) != sink ): # Arcs in the solution will have a flow value of 1. # There start and end nodes give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}")
C++
if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into // sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 && min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; }
Java
if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11 && minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); }
Berikut adalah output program.
Total cost = 250 Worker 1 assigned to task 9. Cost = 75 Worker 2 assigned to task 7. Cost = 35 Worker 5 assigned to task 10. Cost = 75 Worker 6 assigned to task 8. Cost = 65 Time = 0.00031 seconds
Tim A diberi tugas 9 dan 10, sedangkan tim B diberi tugas 7 dan 8.
Perhatikan bahwa pemecah aliran biaya min lebih cepat untuk masalah ini daripada pemecah masalah MIP, yang memakan waktu sekitar 0,006 detik.
Seluruh program
Seluruh program ditampilkan di bawah ini.
Python
"""Assignment with teams of workers.""" from ortools.graph.python import min_cost_flow def main(): """Solving an Assignment with teams of worker.""" smcf = min_cost_flow.SimpleMinCostFlow() # Define the directed graph for the flow. team_a = [1, 3, 5] team_b = [2, 4, 6] start_nodes = ( # fmt: off [0, 0] + [11, 11, 11] + [12, 12, 12] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] + [7, 8, 9, 10] # fmt: on ) end_nodes = ( # fmt: off [11, 12] + team_a + team_b + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] + [13, 13, 13, 13] # fmt: on ) capacities = ( # fmt: off [2, 2] + [1, 1, 1] + [1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] # fmt: on ) costs = ( # fmt: off [0, 0] + [0, 0, 0] + [0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95] + [0, 0, 0, 0] # fmt: on ) source = 0 sink = 13 tasks = 4 # Define an array of supplies at each node. supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks] # Add each arc. for i in range(0, len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(0, len(supplies)): smcf.set_node_supply(i, supplies[i]) # Find the minimum cost flow between node 0 and node 10. status = smcf.solve() if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or intermediate, or into sink. if ( smcf.tail(arc) != source and smcf.tail(arc) != 11 and smcf.tail(arc) != 12 and smcf.head(arc) != sink ): # Arcs in the solution will have a flow value of 1. # There start and end nodes give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}") if __name__ == "__main__": main()
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h" namespace operations_research { // MinCostFlow simple interface example. void BalanceMinFlow() { // Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow; // Define the directed graph for the flow. const std::vector<int64_t> team_A = {1, 3, 5}; const std::vector<int64_t> team_B = {2, 4, 6}; const std::vector<int64_t> start_nodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; const std::vector<int64_t> end_nodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; const std::vector<int64_t> capacities = {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 13; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. int status = min_cost_flow.Solve(); if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into // sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 && min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; } } } // namespace operations_research int main() { operations_research::BalanceMinFlow(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase; /** Minimal Assignment Min Flow. */ public class BalanceMinFlow { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define the directed graph for the flow. // int[] teamA = new int[] {1, 3, 5}; // int[] teamB = new int[] {2, 4, 6}; int[] startNodes = new int[] {0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; int[] capacities = new int[] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve(); if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11 && minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private BalanceMinFlow() {} }
C#
using System; using Google.OrTools.Graph; public class BalanceMinFlow { static void Main() { // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define the directed graph for the flow. int[] teamA = { 1, 3, 5 }; int[] teamB = { 2, 4, 6 }; // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10 }; int[] endNodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13 }; int[] capacities = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0 }; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve(); if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); } } }