คุณจะใช้เครื่องมือแก้ขั้นตอนต้นทุนขั้นต่ำเพื่อแก้ปัญหาปัญหาการมอบหมายในกรณีพิเศษได้
อันที่จริง ขั้นตอนต้นทุนขั้นต่ำมักให้ผลลัพธ์ที่ดีกว่าเครื่องมือแก้โจทย์ MIP หรือ CP-SAT อย่างไรก็ตาม MIP และ CP-SAT สามารถแก้ปัญหาในระดับที่กว้างกว่าโฟลว์ต้นทุนขั้นต่ำได้ ดังนั้นในกรณีส่วนใหญ่ MIP หรือ CP-SAT จึงเป็นตัวเลือกที่ดีที่สุด
ส่วนต่อไปนี้จะแสดงโปรแกรม Python ที่แก้ปัญหาการมอบหมายต่อไปนี้โดยใช้โปรแกรมแก้โฟลว์ต้นทุนขั้นต่ำ
- ตัวอย่างการกำหนดเชิงเส้นเพียงเล็กน้อย
- ปัญหาในการมอบหมายงานให้กับทีมผู้ปฏิบัติงาน
ตัวอย่างการมอบหมายเชิงเส้น
ส่วนนี้จะแสดงวิธีแก้ตัวอย่างตามที่อธิบายไว้ในส่วนเครื่องมือแก้ปัญหางานเชิงเส้นว่าเป็นปัญหาการไหลเวียนของต้นทุนขั้นต่ำ
นำเข้าไลบรารี
โค้ดต่อไปนี้จะนำเข้าไลบรารีที่จำเป็น
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;
ประกาศเครื่องมือแก้โจทย์
โค้ดต่อไปนี้จะสร้างเครื่องมือแก้โฟลว์ต้นทุนขั้นต่ำ
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();
สร้างข้อมูล
แผนภาพโฟลว์ของโจทย์ประกอบด้วยกราฟ 2 ส่วนของเมทริกซ์ต้นทุน (ดูภาพรวมการกำหนดสำหรับตัวอย่างที่แตกต่างกันเล็กน้อย) โดยเพิ่มแหล่งที่มาและซิงก์
ข้อมูลจะมีอาร์เรย์ 4 รายการต่อไปนี้ ซึ่งสอดคล้องกับโหนดเริ่มต้น โหนดสิ้นสุด ความจุ และค่าใช้จ่ายของปัญหา ความยาวของแต่ละอาร์เรย์ คือจำนวนส่วนโค้งในกราฟ
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 };
เพื่อสร้างความชัดเจนในการตั้งค่าข้อมูล แต่ละอาร์เรย์จะแบ่งออกเป็นอาร์เรย์ย่อย 3 แบบดังนี้
- อาร์เรย์แรกจะสอดคล้องกับแนวโค้งที่ออกจากต้นทาง
- อาร์เรย์ที่สองจะสอดคล้องกับแนวโค้งระหว่างผู้ปฏิบัติงานและงาน
สำหรับ
costsนี่เป็นเพียงเมทริกซ์ต้นทุน (ซึ่งเครื่องมือแก้โจทย์กำหนดเชิงเส้นใช้) ซึ่งถูกตีให้เป็นเวกเตอร์ - อาร์เรย์ที่สามจะสอดคล้องกับแนวโค้งที่นำเข้าสู่อ่างล้างจาน
ข้อมูลนี้ยังมีเวกเตอร์ supplies ซึ่งระบุอุปทานในแต่ละโหนด
ปัญหาขั้นตอนต้นทุนขั้นต่ำแสดงถึงปัญหาการกำหนดอย่างไร
ปัญหาขั้นตอนต้นทุนขั้นต่ำด้านบนแสดงถึงปัญหาการมอบหมายอย่างไร ข้อแรก เนื่องจากความจุของทุกเส้นโค้งเท่ากับ 1 การให้พลังงานของเส้นโค้ง 4 แกนจะผลักดันให้แต่ละเส้นโค้งจากทั้ง 4 ส่วนที่นำไปยังผู้ปฏิบัติงานมีแนวไหลเท่ากับ 1
ถัดมา เงื่อนไข "การไหลในเท่ากับ" จะบังคับให้ผู้ปฏิบัติงานแต่ละรายไหลออก ซึ่งก็คือ 1 หากเป็นไปได้ ตัวแก้โจทย์จะนำทางขั้นตอนดังกล่าวผ่านเส้นโค้งต้นทุนขั้นต่ำที่นำออกสำหรับผู้ปฏิบัติงานแต่ละคน อย่างไรก็ตาม เครื่องมือแก้โจทย์คณิตไม่สามารถกำหนดเส้นทางจากผู้ปฏิบัติงาน 2 รายที่แตกต่างกันไปยังงานเดียวได้ ซึ่งหากเป็นเช่นนั้น งานนั้นจะมีกระบวนการรวม 2 อย่างซึ่งจะส่งผ่านเส้นโค้งเดี่ยวที่มีความจุ 1 จากงานไปยังซิงก์ไม่ได้ ซึ่งหมายความว่าโปรแกรมแก้โจทย์จะมอบหมายงานให้ผู้ปฏิบัติงานได้เพียงรายเดียวเท่านั้น ตามที่โจทย์การงานกำหนด
สุดท้าย เงื่อนไข "โฟลว์-เท่ากับ" จะบังคับให้แต่ละงานมีโฟลว์ออกเท่ากับ 1 เพื่อให้ผู้ปฏิบัติงานบางรายต้องทำแต่ละงาน
สร้างกราฟและข้อจำกัด
โค้ดต่อไปนี้จะสร้างกราฟและข้อจำกัด
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]);
}
เรียกใช้เครื่องมือแก้โจทย์
โค้ดต่อไปนี้จะเรียกเครื่องมือแก้โจทย์และแสดงคำตอบ
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();
คำตอบจะประกอบด้วยเส้นโค้งระหว่างผู้ปฏิบัติงานกับงานที่เครื่องมือแก้โจทย์กำหนดลำดับขั้นตอนเป็น 1 (ส่วนโค้งที่เชื่อมต่อกับแหล่งที่มาหรือซิงก์ไม่ได้เป็นส่วนหนึ่งของโซลูชัน)
โปรแกรมจะตรวจสอบแต่ละเส้นโค้งเพื่อดูว่ามีโฟลว์ 1 หรือไม่ หากมี ก็จะพิมพ์ Tail (โหนดเริ่มต้น) และ Head (โหนดสุดท้าย) ของเส้นโค้ง ซึ่งสอดคล้องกับผู้ปฏิบัติงานและงานในงาน
เอาต์พุตของโปรแกรม
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);
}
นี่คือเอาต์พุตของโปรแกรม
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
ผลลัพธ์จะเหมือนกับเครื่องมือแก้โจทย์การมอบหมายเชิงเส้น (ยกเว้นจำนวนผู้ปฏิบัติงานและต้นทุนที่ต่างกัน) ตัวแก้โจทย์การกำหนดเชิงเส้นจะเร็วกว่าโฟลว์ต้นทุนขั้นต่ำเล็กน้อย นั่นคือ 0.000147 วินาทีเทียบกับ 0.000458 วินาที
ทั้งโปรแกรม
ทั้งโปรแกรมแสดงอยู่ด้านล่างนี้
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);
}
}
}
งานกับทีมผู้ปฏิบัติงาน
ส่วนนี้จะพูดถึงโจทย์งานทั่วไป ในปัญหานี้ คนทำงาน 6 คนจะแบ่งออกเป็น 2 ทีม ปัญหาคือการมอบหมายงาน 4 รายการให้กับพนักงานเพื่อให้ภาระงานของทีมมีความสมดุลเท่าๆ กัน แต่ละทีมจึงทำงาน 2 อย่าง
โปรดดูโซลูชันเครื่องมือแก้ MIP สำหรับโจทย์นี้ที่หัวข้อการให้สิทธิกับทีมผู้ปฏิบัติงาน
ส่วนต่อไปนี้จะอธิบายโปรแกรมที่แก้ไขปัญหาโดยใช้โปรแกรมแก้โฟลว์ต้นทุนขั้นต่ำ
นำเข้าไลบรารี
โค้ดต่อไปนี้จะนำเข้าไลบรารีที่จำเป็น
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;
ประกาศเครื่องมือแก้โจทย์
โค้ดต่อไปนี้จะสร้างเครื่องมือแก้โฟลว์ต้นทุนขั้นต่ำ
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();
สร้างข้อมูล
โค้ดต่อไปนี้จะสร้างข้อมูลสำหรับโปรแกรม
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 };
ผู้ปฏิบัติงานจะสอดคล้องกับโหนด 1-6 ทีม ก ประกอบด้วยผู้ปฏิบัติงาน 1, 3 และ 5 และทีม ข ประกอบด้วยผู้ปฏิบัติงาน 2, 4 และ 6 งานต่างๆ มีลำดับเลข 7-10
มีโหนดใหม่ 2 โหนดคือ 11 และ 12 ระหว่างต้นทางและผู้ปฏิบัติงาน โหนด 11 เชื่อมต่อกับโหนดของทีม A และโหนด 12 เชื่อมต่อกับโหนดของทีม B โดยมีส่วนโค้งความจุ 1 กราฟด้านล่างแสดงเฉพาะโหนดและเส้นโค้งจากแหล่งที่มาไปยังผู้ปฏิบัติงาน
กุญแจสำคัญในการจัดสมดุลภาระงานคือแหล่งที่มา 0 เชื่อมต่อกับโหนด 11 และ 12 คูณส่วนโค้งของความจุ 2 ซึ่งหมายความว่าโหนด 11 และ 12 (ดังนั้นทีม A และ B) จะมีโฟลว์ได้สูงสุด 2 ดังนั้น แต่ละทีมจึงสามารถทํางานได้ไม่เกิน 2 งาน
สร้างข้อจำกัด
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]);
}
เรียกใช้เครื่องมือแก้โจทย์
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();
เอาต์พุตของโปรแกรม
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);
}
ข้อมูลต่อไปนี้แสดงเอาต์พุตของโปรแกรม
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
ทีม ก ได้รับมอบหมายงานที่ 9 และ 10 ส่วนทีม ข ได้รับมอบหมายงานที่ 7 และ 8
โปรดทราบว่าโปรแกรมแก้โฟลว์ต้นทุนขั้นต่ำสำหรับปัญหานี้จะเร็วกว่าเครื่องมือแก้โจทย์ MIP ซึ่งใช้เวลาประมาณ 0.006 วินาที
ทั้งโปรแกรม
ทั้งโปรแกรมแสดงอยู่ด้านล่างนี้
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);
}
}
}