Mit der Lösung für den min. Kostenprozess können Sie Sonderfälle des Zuweisungsproblems lösen.
Tatsächlich kann der min. Kostenfluss eine Lösung häufig schneller zurückgeben als der MIP- oder CP-SAT-Resolver. MIP und CP-SAT können jedoch eine größere Klasse von Problemen lösen als der minimale Kostenfluss. Daher sind MIP oder CP-SAT in den meisten Fällen die beste Wahl.
In den folgenden Abschnitten werden Python-Programme vorgestellt, die die folgenden Zuweisungsprobleme mit dem Min-Cost-Flow-Beheber lösen:
- Beispiel für eine minimale lineare Zuweisung
- Ein Problem bei der Zuweisung von Mitarbeiterteams.
Beispiel für eine lineare Zuweisung
In diesem Abschnitt wird gezeigt, wie Sie das im Abschnitt Linear Assignment Solver beschriebene Beispiel als Problem mit dem Ablauf der minimalen Kosten lösen können.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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;
Löser deklarieren
Mit dem folgenden Code wird der Ablauf-Beheber für die Mindestkosten erstellt.
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();
Daten erstellen
Das Flussdiagramm für das Problem besteht aus dem zweiteiligen Diagramm für die Kostenmatrix (siehe Zuweisungsübersicht für ein etwas anderes Beispiel), in dem eine Quelle und eine Senke hinzugefügt wurden.
Die Daten enthalten die folgenden vier Arrays, die den Startknoten, Endknoten, Kapazitäten und Kosten für das Problem entsprechen. Die Länge jedes Arrays ist die Anzahl der Bögen in der 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 };
Um zu verdeutlichen, wie die Daten eingerichtet sind, wird jedes Array in drei Teilarrays unterteilt:
- Das erste Array entspricht Bögen, die aus der Quelle führen.
- Das zweite Array entspricht den Bögen zwischen Workern und Tasks.
Für
costsist dies nur die Kostenmatrix, die vom linearen Zuweisungsrechner verwendet wird und zu einem Vektor vereinfacht wird. - Das dritte Array entspricht den Bögen, die in die Senke führen.
Die Daten enthalten auch den Vektor supplies, der die Versorgung an jedem Knoten liefert.
Wie stellt ein Problem mit dem min. Kostenfluss ein Zuweisungsproblem dar?
Inwiefern stellt das oben genannte Problem mit dem min. Kostenfluss ein Zuweisungsproblem dar? Da die Kapazität jedes Bogens 1 ist, zwingt die Bereitstellung von 4 an der Quelle jeden der vier Bögen, die in die Worker führen, zu einem Fluss von 1.
Als Nächstes erzwingt die Bedingung "Flow-in-equals-flow-out" für den Datenfluss aus jedem Worker den Wert 1. Wenn möglich, leitet der Solver diesen Fluss über den minimalen Kostenbogen, der aus jedem Worker herausführt. Der Solver kann jedoch die Abläufe von zwei verschiedenen Workern nicht zu einer einzigen Aufgabe leiten. Wenn dies der Fall wäre, gäbe es bei dieser Aufgabe einen kombinierten Fluss von 2, der nicht über den einzelnen Bogen mit Kapazität 1 von der Aufgabe zur Senke gesendet werden könnte. Das bedeutet, dass der Matherechner eine Aufgabe nur einem einzelnen Worker zuweisen kann, wie es für die Zuweisungsaufgabe erforderlich ist.
Schließlich erzwingt die Bedingung "Flow-in-equals-flow-out" für jede Aufgabe einen Outflow von 1, sodass jede Aufgabe von einem bestimmten Worker ausgeführt wird.
Diagramm und Einschränkungen erstellen
Mit dem folgenden Code werden die Grafik und die Einschränkungen erstellt.
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]);
}
Den Solver aufrufen
Der folgende Code ruft den Solver auf und zeigt die Lösung an.
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();
Die Lösung besteht aus den Bögen zwischen Workern und Aufgaben, denen vom Solver ein Fluss von 1 zugewiesen wird. Mit der Quelle oder Senke verbundene Bögen sind nicht Teil der Lösung.
Das Programm prüft jeden Bogen darauf, ob er Fluss 1 hat. Wenn ja, gibt es die Tail (Startknoten) und Head (Endknoten) des Bogens aus, die einem Worker und einer Aufgabe in der Zuweisung entsprechen.
Ausgabe des Programms
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);
}
Hier ist die Ausgabe des Programms.
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
Das Ergebnis ist dasselbe wie das für den linearen Zuweisungsrechner (mit Ausnahme der unterschiedlichen Anzahl der Worker und Kosten). Der lineare Zuweisungsrechner ist etwas schneller als der minimale Kostenfluss (0,000147 Sekunden gegenüber 0,000458 Sekunden).
Das gesamte Programm
Das gesamte Programm ist unten zu sehen.
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);
}
}
}
Zuweisung an Mitarbeiterteams
In diesem Abschnitt wird ein allgemeineres Zuweisungsproblem behandelt. Bei diesem Problem sind sechs Mitarbeitende in zwei Teams eingeteilt. Das Problem besteht darin, den Workern vier Aufgaben zuzuweisen, damit die Arbeitslast gleichmäßig auf die Teams verteilt wird – d. h., jedes Team führt zwei Aufgaben aus.
Eine MIP-Lösung für dieses Problem finden Sie unter Zuweisung an Mitarbeiterteams.
In den folgenden Abschnitten wird ein Programm beschrieben, das das Problem mit dem Minimum Cost Flow Solver löst.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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;
Löser deklarieren
Mit dem folgenden Code wird der Ablauf-Beheber für die Mindestkosten erstellt.
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();
Daten erstellen
Mit dem folgenden Code werden die Daten für das Programm erstellt.
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 };
Die Worker entsprechen den Knoten 1 bis 6. Team A besteht aus den Workern 1, 3 und 5, Team B aus den Workern 2, 4 und 6. Die Aufgaben sind von 7 bis 10 nummeriert.
Zwischen der Quelle und den Workern befinden sich die beiden neuen Knoten 11 und 12. Knoten 11 ist mit den Knoten für Team A verbunden und Knoten 12 mit den Knoten für Team B mit Kapazitätsbögen 1. Das folgende Diagramm zeigt nur die Knoten und Bögen von der Quelle zu den Workern.
Der Schlüssel zum Ausgleich der Arbeitslast besteht darin, dass Quelle 0 über Kapazität 2 mit den Knoten 11 und 12 verbunden ist. Das bedeutet, dass die Knoten 11 und 12 (und daher Teams A und B) einen maximalen Fluss von 2 haben können. Somit kann jedes Team maximal zwei der Aufgaben erledigen.
Einschränkungen erstellen
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]);
}
Den Solver aufrufen
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();
Ausgabe des Programms
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);
}
Im Folgenden wird die Ausgabe des Programms dargestellt.
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
Team A werden die Aufgaben 9 und 10 zugewiesen, während Team B die Aufgaben 7 und 8 zugewiesen wird.
Der min.Kosten-Flow-Beheber ist für dieses Problem schneller als der MIP-Rechner, der etwa 0,006 Sekunden dauert.
Das gesamte Programm
Das gesamte Programm ist unten zu sehen.
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);
}
}
}