Atama probleminin özel durumlarını çözmek için minimum maliyet akışı çözücüyü kullanabilirsiniz.
Aslında minimum maliyet akışı, MIP veya CP-SAT çözücüden daha hızlı bir çözüm döndürebilir. Ancak MIP ve CP-SAT, min. maliyet akışından daha büyük bir problem sınıfını çözebilir. Bu nedenle çoğu durumda MIP veya CP-SAT en iyi seçenektir.
Aşağıdaki bölümlerde, minimum maliyet akışı çözücüyü kullanarak aşağıdaki atama problemlerini çözen Python programları sunulmaktadır:
- Minimal doğrusal atama örneği.
- Çalışan ekiplerinde yaşanan bir atama sorunu.
Doğrusal atama örneği
Bu bölümde, Doğrusal Atama Çözücü bölümünde açıklanan örneğin minimum maliyet akışı problemi olarak nasıl çözüleceği gösterilmektedir.
Kitaplıkları içe aktarın
Aşağıdaki kod gerekli kitaplığı içe aktarır.
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;
Çözücüyü bildirme
Aşağıdaki kod minimum maliyet akışı çözücüyü oluşturur.
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();
Verileri oluşturun
Problemin akış diyagramı, kaynak ve havuzun eklendiği, maliyet matrisine ait iki parçalı grafikten oluşur (biraz farklı bir örnek için atama genel bakışı bölümüne bakın).
Verilerde başlangıç düğümlerine, bitiş düğümlerine, kapasitelere ve problemin maliyetlerine karşılık gelen aşağıdaki dört dizi bulunur. Her dizinin uzunluğu, grafikteki yayların sayısıdır.
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 };
Verilerin nasıl ayarlandığını net bir şekilde açıklamak için her bir dizi üç alt diziye bölünür:
- İlk dizi, kaynağın dışına çıkan yaylara karşılık gelir.
- İkinci dizi, çalışanlar ve görevler arasındaki yaylara karşılık gelir.
costsiçin bu, doğrusal atama çözücü tarafından kullanılan ve vektöre dönüştürülmüş maliyet matrisidir. - Üçüncü dizi, havuza giden yaylara karşılık gelir.
Veriler, her düğümde kaynağı veren supplies vektörünü de içerir.
Min. maliyet akışı problemi, atama problemini nasıl temsil eder?
Yukarıdaki minimum maliyet akışı problemi, atamadaki bir sorunu nasıl temsil eder? İlk olarak, her yayın kapasitesi 1 olduğundan, kaynaktaki 4 yay, çalışanlara giden dört yayın her birini 1 akışında zorlar.
Daha sonra, akış-in-eşittir-çıkış koşulu, her çalışanın dışarı akışını 1 olmaya zorlar. Mümkünse çözücü, bu akışı her çalışandan çıkan minimum maliyet aralığına yönlendirir. Ancak çözücü, iki farklı çalışandan gelen akışları tek bir göreve yönlendiremez. Eğer gerçekleşirse bu görevde toplam 2 akış olacaktır ve bu akış, görevden lavaboya 1 kapasite ile tek yay boyunca gönderilemez. Bu, çözücünün atama probleminin gerektirdiği şekilde yalnızca tek bir çalışana görev atayabileceği anlamına gelir.
Son olarak, akış-in-eşittir-çıkış koşulu her görevi 1 çıkışlı olmaya zorlar. Bu nedenle her görev bir çalışan tarafından gerçekleştirilir.
Grafiği ve kısıtlamaları oluşturma
Aşağıdaki kod, grafiği ve kısıtlamaları oluşturur.
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]);
}
Çözücüyü çağır
Aşağıdaki kod çözücüyü çağırır ve çözümü görüntüler.
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();
Çözüm, çalışanlar ve problem çözme aracı tarafından 1 akış atanırken görevler arasındaki yaylardan oluşur. (Kaynağa veya havuza bağlı yaylar çözümün bir parçası değildir.)
Program, her bir yayda 1. akışın olup olmadığını kontrol eder. Akış varsa yayındaki bir çalışana ve göreve karşılık gelen Tail (başlangıç düğümü) ve Head (bitiş düğümü) de yazdırılır.
Program çıktısı
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);
}
Programın sonucunu burada bulabilirsiniz.
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
Sonuç, doğrusal atama çözücü ile aynıdır (çalışan sayısı ve maliyetlerin farklı olması hariç). Doğrusal atama çözücü, minimum maliyet akışından biraz daha hızlıdır. 0,000147 saniyeye karşılık 0,000458 saniye.
Programın tamamı
Programın tamamı aşağıda gösterilmektedir.
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);
}
}
}
Çalışan ekipleriyle atama
Bu bölümde daha genel bir atama sorunu ele alınmaktadır. Bu problemde altı çalışan iki ekibe bölünmüştür. Sorun, iş yükünün ekipler arasında eşit olarak dengelenmesi, yani her ekibin görevlerin ikisini yerine getirmesi için çalışanlara dört görev atamaktır.
Bu soruna MIP çözücü çözümü için Çalışan Ekipleriyle Atama bölümüne bakın.
Aşağıdaki bölümlerde minimum maliyet akışı çözücüyü kullanarak problemi çözen bir program açıklanmaktadır.
Kitaplıkları içe aktarın
Aşağıdaki kod gerekli kitaplığı içe aktarır.
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;
Çözücüyü bildirme
Aşağıdaki kod minimum maliyet akışı çözücüyü oluşturur.
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();
Verileri oluşturun
Aşağıdaki kod, program verilerini oluşturur.
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 };
Çalışanlar 1 - 6 arasındaki düğümlere karşılık gelir. A Ekibi 1, 3 ve 5, B ekibi ise 2, 4 ve 6 numaralı çalışanlardan oluşur. Görevler 7'den 10'a kadar numaralandırılmıştır.
Kaynak ile çalışanlar arasında 11 ve 12 numaralı iki yeni düğüm var. Düğüm 11, A ekibinin düğümlere bağlıdır. Düğüm 12, kapasite 1 yaylarıyla B ekibinin düğümlerine bağlıdır. Aşağıdaki grafikte yalnızca, kaynaktan çalışanlara uzanan düğümler ve yaylar gösterilmektedir.
İş yükünü dengelemenin anahtarı, kaynak 0'ın kapasite 2 yaylarıyla 11 ve 12. düğümlere bağlanmasıdır. Bu, 11 ve 12 numaralı düğümlerin (ve dolayısıyla A ve B ekiplerinin) maksimum 2 akışa sahip olabileceği anlamına gelir. Sonuç olarak her ekip, görevlerin en fazla ikisini gerçekleştirebilir.
Kısıtlamaları oluşturma
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]);
}
Çözücüyü çağır
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();
Program çıktısı
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);
}
Aşağıda programın sonucu gösterilmektedir.
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
A Ekibi’ne 9 ve 10. görevler, B ekibine ise 7. ve 8. görevler atanır.
Min.maliyet akışı çözücünün bu sorun için yaklaşık 0, 006 saniye süren MIP çözücüden daha hızlı olduğunu unutmayın.
Programın tamamı
Programın tamamı aşağıda gösterilmektedir.
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);
}
}
}