בעיית הזרימה המקסימלית שקשורה באופן הדוק לבעיית הזרימה המקסימלית היא העלות המינימלית (min cost), שבה לכל קשת בתרשים יש עלות יחידה להובלת החומר. הבעיה היא למצוא זרימה עם העלות הכוללת הנמוכה ביותר.
לבעיה של זרימת העלות המינימלית יש גם צמתים מיוחדים, שנקראים צומתי אספקה או צומתי ביקוש, שדומים למקור ולשוקע בבעיה של זרימה מקסימלית. החומר מועבר מצומתי אספקה לצומתי ביקוש.
- בצומת האספקה, סכום חיובי מתווסף לזרימה. לדוגמה, האספקה יכולה לייצג ייצור בצומת הזה.
- בצומת הביקוש, סכום שלילי – הביקוש – נעלם מהזרימה. לדוגמה, ביקוש יכול לייצג צריכה בצומת הזה.
לשם נוחות, נניח שלכל הצמתים יש, מלבד צומתי היצע או ביקוש, היצע אפס (וביקוש).
בנוגע לבעיה של תזרים העלות המינימלית, יצרנו את הכלל הבא לשימור זרימה, שמביא בחשבון את האספקה והביקוש:
התרשים הבא מציג בעיה של זרימת עלות מינימלית. לקשתות יש צמדים של מספרים: המספר הראשון הוא הקיבולת והמספר השני הוא העלות. המספרים בסוגריים מרובעים מייצגים את ההיצע או הביקוש. צומת 0 הוא צומת אספקה עם היצע 20, ואילו הצמתים 3 ו-4 הם צומתי ביקוש עם הדרישות -5 ו-15-, בהתאמה.
ייבוא הספריות
הקוד הבא מייבא את הספרייה הנדרשת.
Python
import numpy as np 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;
מצהירים על הפותר
כדי לפתור את הבעיה, אנחנו משתמשים בפתרון SimpleMinCostFlow.
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();
הגדרת הנתונים
הקוד הבא מגדיר את הנתונים עבור הבעיה. במקרה הזה יש ארבעה מערכים של צומתי ההתחלה, צומתי הסיום, הקיבולת ועלויות היחידות. שוב, אורך המערכים הוא מספר הקשתות בתרשים.
Python
# 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. start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4]) end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2]) capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5]) unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3]) # Define an array of supplies at each node. supplies = [20, 0, 0, -5, -15]
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.
std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3};
// Define an array of supplies at each node.
std::vector<int64_t> supplies = {20, 0, 0, -5, -15};
Java
// 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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4};
int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2};
int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5};
int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3};
// Define an array of supplies at each node.
int[] supplies = new int[] {20, 0, 0, -5, -15};
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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 };
int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };
// Define an array of supplies at each node.
int[] supplies = { 20, 0, 0, -5, -15 };
הוספת הקשתות
לכל צומת התחלה וצומת קצה, אנחנו יוצרים קשת מצומת התחלה לצומת קצה עם הקיבולת ועלות היחידה הנתונים באמצעות השיטה AddArcWithCapacityAndUnitCost.
שיטת SetNodeSupply של הפותר יוצרת וקטור של ציוד לצמתים.
Python
# Add arcs, capacities and costs in bulk using numpy.
all_arcs = smcf.add_arcs_with_capacity_and_unit_cost(
start_nodes, end_nodes, capacities, unit_costs
)
# Add supply for each nodes.
smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)
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]);
}
מזמינים את הפותר
אחרי שהגדרתם את כל הקשתות, כל מה שנשאר זה להפעיל את המפענח ולהציג את התוצאות. אנחנו מפעילים את השיטה Solve().
Python
# Find the min cost flow. 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("There was an issue with the min cost flow input.")
print(f"Status: {status}")
exit(1)
print(f"Minimum cost: {smcf.optimal_cost()}")
print("")
print(" Arc Flow / Capacity Cost")
solution_flows = smcf.flows(all_arcs)
costs = solution_flows * unit_costs
for arc, flow, cost in zip(all_arcs, solution_flows, costs):
print(
f"{smcf.tail(arc):1} -> {smcf.head(arc)} {flow:3} / {smcf.capacity(arc):3} {cost}"
)
C++
if (status == MinCostFlow::OPTIMAL) {
LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
LOG(INFO) << " Arc Flow / Capacity Cost";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i);
LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i)
<< " " << min_cost_flow.Flow(i) << " / "
<< min_cost_flow.Capacity(i) << " " << cost;
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed. Solver status: "
<< status;
}
Java
if (status == MinCostFlow.Status.OPTIMAL) {
System.out.println("Minimum cost: " + minCostFlow.getOptimalCost());
System.out.println();
System.out.println(" Edge Flow / Capacity Cost");
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i);
System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + " "
+ minCostFlow.getFlow(i) + " / " + minCostFlow.getCapacity(i) + " " + cost);
}
} 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("Minimum cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
Console.WriteLine(" Edge Flow / Capacity Cost");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + " " +
string.Format("{0,3}", minCostFlow.Flow(i)) + " / " +
string.Format("{0,3}", minCostFlow.Capacity(i)) + " " +
string.Format("{0,3}", cost));
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status);
}
זהו הפלט של תוכנת Python:
Minimum cost: 150 Arc Flow / Capacity Cost 0 -> 1 12 / 15 48 0 -> 2 8 / 8 32 1 -> 2 8 / 20 16 1 -> 3 4 / 4 8 1 -> 4 0 / 10 0 2 -> 3 12 / 15 12 2 -> 4 4 / 4 12 3 -> 4 11 / 20 22 4 -> 2 0 / 5 0
השלמה של תוכניות
הנה כל התוכניות האפשריות.
Python
"""From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1."""
import numpy as np
from ortools.graph.python import min_cost_flow
def main():
"""MinCostFlow simple interface example."""
# Instantiate a SimpleMinCostFlow solver.
smcf = min_cost_flow.SimpleMinCostFlow()
# 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.
start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4])
end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2])
capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5])
unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3])
# Define an array of supplies at each node.
supplies = [20, 0, 0, -5, -15]
# Add arcs, capacities and costs in bulk using numpy.
all_arcs = smcf.add_arcs_with_capacity_and_unit_cost(
start_nodes, end_nodes, capacities, unit_costs
)
# Add supply for each nodes.
smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)
# Find the min cost flow.
status = smcf.solve()
if status != smcf.OPTIMAL:
print("There was an issue with the min cost flow input.")
print(f"Status: {status}")
exit(1)
print(f"Minimum cost: {smcf.optimal_cost()}")
print("")
print(" Arc Flow / Capacity Cost")
solution_flows = smcf.flows(all_arcs)
costs = solution_flows * unit_costs
for arc, flow, cost in zip(all_arcs, solution_flows, costs):
print(
f"{smcf.tail(arc):1} -> {smcf.head(arc)} {flow:3} / {smcf.capacity(arc):3} {cost}"
)
if __name__ == "__main__":
main()
C++
// From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1
#include <cstdint>
#include <vector>
#include "ortools/graph/min_cost_flow.h"
namespace operations_research {
// MinCostFlow simple interface example.
void SimpleMinCostFlowProgram() {
// 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.
std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3};
// Define an array of supplies at each node.
std::vector<int64_t> supplies = {20, 0, 0, -5, -15};
// 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) << "Minimum cost flow: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
LOG(INFO) << " Arc Flow / Capacity Cost";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i);
LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i)
<< " " << min_cost_flow.Flow(i) << " / "
<< min_cost_flow.Capacity(i) << " " << cost;
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed. Solver status: "
<< status;
}
}
} // namespace operations_research
int main() {
operations_research::SimpleMinCostFlowProgram();
return EXIT_SUCCESS;
}
Java
// From Bradley, Hax, and Maganti, 'Applied Mathematical Programming', figure 8.1.
package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MinCostFlow;
import com.google.ortools.graph.MinCostFlowBase;
/** Minimal MinCostFlow program. */
public class SimpleMinCostFlowProgram {
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. For instance, the arc from node 0 to node 1 has a
// capacity of 15.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4};
int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2};
int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5};
int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3};
// Define an array of supplies at each node.
int[] supplies = new int[] {20, 0, 0, -5, -15};
// 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("Minimum cost: " + minCostFlow.getOptimalCost());
System.out.println();
System.out.println(" Edge Flow / Capacity Cost");
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i);
System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + " "
+ minCostFlow.getFlow(i) + " / " + minCostFlow.getCapacity(i) + " " + cost);
}
} else {
System.out.println("Solving the min cost flow problem failed.");
System.out.println("Solver status: " + status);
}
}
private SimpleMinCostFlowProgram() {}
}
C#
// From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1.
using System;
using Google.OrTools.Graph;
public class SimpleMinCostFlowProgram
{
static void Main()
{
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();
// 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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 };
int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };
// Define an array of supplies at each node.
int[] supplies = { 20, 0, 0, -5, -15 };
// 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("Minimum cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
Console.WriteLine(" Edge Flow / Capacity Cost");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + " " +
string.Format("{0,3}", minCostFlow.Flow(i)) + " / " +
string.Format("{0,3}", minCostFlow.Capacity(i)) + " " +
string.Format("{0,3}", cost));
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status);
}
}
}