Narzędzie do rozwiązywania problemów z minimalnym kosztem może służyć do rozwiązywania specjalnych problemów zadań związanych z przypisaniem.
W rzeczywistości przepływ minimalnego kosztu często może zwrócić rozwiązanie szybciej niż rozwiązanie MIP lub CP-SAT. MIP i CP-SAT mogą jednak rozwiązać większą klasę problemów niż minimalny przepływ kosztów, więc w większości przypadków najlepszym rozwiązaniem są MIP lub CP-SAT.
W kolejnych sekcjach znajdziesz programy w Pythonie, które rozwiązują wymienione poniżej problemy z przypisywaniem przy użyciu narzędzia do rozwiązywania problemów z przepływem kosztów minimalnych:
- Minimalny przykład przypisania linearnego.
- Problem z przypisaniem do zespołów pracowników.
Przykład przypisania liniowego
W tej sekcji pokazujemy, jak rozwiązać problem z przepływem minimalnego kosztu opisany w sekcji Rozwiązanie do rozwiązywania problemów liniowych.
Zaimportuj biblioteki
Poniższy kod importuje wymaganą bibliotekę.
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;
Deklarowanie rozwiązania
Poniższy kod tworzy rozwiązanie do rozwiązywania problemów z minimalnymi kosztami.
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();
Tworzenie danych
Diagram przepływu tego zadania składa się z wykresu dwustronnego dla macierzy kosztów (nieco inny przykład znajdziesz w omówieniu przypisań) oraz dodanych źródeł i ujścia.
Dane te zawierają 4 tablice odpowiadające węzłom początkowym, węzłom końcowym, pojemnościom i kosztom związanym z problemem. Długość każdej tablicy to liczba łuków na wykresie.
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 };
Aby ułatwić skonfigurowanie danych, każda tablica jest podzielona na 3 tablice podrzędne:
- Pierwsza tablica odpowiada łukom wychodzącym ze źródła.
- Druga tablica odpowiada łukom między instancjami roboczymi i zadaniami.
W przypadku właściwości
costs
jest to po prostu tablica kosztów (używana przez narzędzie do rozwiązywania problemów liniowych) podzielona na wektor. - Trzecia tablica odpowiada łukom prowadzącym do ujścia.
Dane obejmują też wektor supplies
, który dostarcza informacje w każdym węźle.
Jak problem z przepływem kosztów minimalnych reprezentuje problem z przypisaniem
W jaki sposób opisany powyżej problem związany z minimalnym kosztem przedstawia problem z przypisaniem? Po pierwsze, ze względu na to, że pojemność każdego łuku wynosi 1, źródło 4 sztuk wymusza na każdym z 4 łuków prowadzących do pracowników przepływ o wartości 1.
Następnie warunek napływu równa się wypływu wymusza wartość 1 na przepływie z każdej instancji roboczej. Jeśli to możliwe, rozwiązanie skieruje ten przepływ przez minimalny próg kosztów na początku każdej instancji roboczej. Rozwiązanie nie może jednak kierować przepływów z 2 różnych instancji roboczych do 1 zadania. Gdyby tak się stało, w ramach tego zadania byłby połączony przepływ 2 razy, którego nie można przesłać przez pojedynczy łuk z pojemnością 1 z zadania do ujścia. Oznacza to, że rozwiązanie może przypisać zadanie tylko 1 podmiotowi roboczemu, zgodnie z wymaganiami zadania.
Na koniec warunek napływu równa się wypływu wymusza na każdym zadaniu wypływ równy 1, więc każde zadanie jest wykonywane przez jakąś instancję roboczą.
Tworzenie wykresu i ograniczeń
Poniższy kod pozwala utworzyć wykres i ograniczenia.
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]); }
Wywoływanie rozwiązania
Poniższy kod wywołuje funkcję i wyświetla rozwiązanie.
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();
Rozwiązanie składa się z łuków między instancjami roboczymi a zadaniami, do których rozwiązanie ma przypisany przepływ o wartości 1. (Łuki połączone ze źródłem lub ujściem nie są częścią rozwiązania).
Program sprawdza każdy łuk, aby sprawdzić, czy ma przepływ 1. Jeśli tak, drukuje Tail
(węzeł początkowy) i Head
(węzeł końcowy) łuku, który odpowiada instancji roboczej i zadaniu w przypisaniu.
Wyniki programu
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); }
Oto dane wyjściowe programu.
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
Wynik jest taki sam jak w przypadku liniowego rozwiązania do zadań (z wyjątkiem różnic w numeracji pracowników i kosztów). Liniowe narzędzie do rozwiązywania problemów działa trochę szybciej niż minimalny przepływ kosztów – 0,000147 sekundy w porównaniu z 0,000458 sekundy.
Cały program
Cały program jest widoczny poniżej.
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); } } }
Zadania z zespołami pracowników
W tej sekcji omawiamy bardziej ogólny problem z przypisywaniem. W tym przypadku 6 pracowników jest podzielonych na 2 zespoły. Problem polega na przypisaniu do pracowników 4 zadań, tak aby ich zadania były równoważne między zespołami, czyli tak, aby każdy zespół wykonał 2 zdania.
Rozwiązanie tego zadania dotyczącego MIP znajdziesz w artykule Projekt przy użyciu zespołów pracowników.
W kolejnych sekcjach opisano program, który rozwiązuje problem za pomocą rozwiązania do zarządzania przepływem minimalnych kosztów.
Zaimportuj biblioteki
Poniższy kod importuje wymaganą bibliotekę.
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;
Deklarowanie rozwiązania
Poniższy kod tworzy rozwiązanie do rozwiązywania problemów z minimalnymi kosztami.
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();
Tworzenie danych
Poniższy kod tworzy dane programu.
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 };
Instancje robocze odpowiadają węzłom 1–6. Zespół A składa się z instancji roboczych 1, 3 i 5, a zespół B – pracowników 2, 4 i 6. Zadania są ponumerowane od 7 do 10.
Między źródłem a instancjami roboczymi są 2 nowe węzły: 11 i 12. Węzeł 11 jest połączony z węzłami zespołu A, a węzeł 12 z węzłami zespołu B o łukach pojemności 1. Poniższy wykres przedstawia tylko węzły i łuki od źródła do instancji roboczych.
Kluczem do równoważenia obciążenia jest to, aby źródło 0 było połączone z węzłami 11 i 12 za pomocą łuków pojemności 2. Oznacza to, że w węzłach 11 i 12 (a tym samym w zespołach A i B) przepływ może wynosić maksymalnie 2. W związku z tym każdy zespół może wykonać maksymalnie 2 z nich.
Tworzenie ograniczeń
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]); }
Wywoływanie rozwiązania
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();
Wyniki programu
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); }
Poniżej znajdziesz dane wyjściowe programu.
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
Zespołowi A otrzymują zadania 9 i 10, a zespołu B – zadania 7 i 8.
Pamiętaj, że narzędzie do rozwiązywania problemów związanych z minimalnym kosztem jest szybsze niż narzędzie MIP, które zajmuje około 0,006 sekundy.
Cały program
Cały program jest widoczny poniżej.
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); } } }