С проблемой максимального потока тесно связана задача о потоке с минимальной стоимостью ( min cost ), в которой каждая дуга на графике имеет стоимость единицы транспортировки материала через нее. Задача состоит в том, чтобы найти поток с наименьшей общей стоимостью.
Задача о минимальном потоке затрат также имеет специальные узлы, называемые узлами предложения или узлами спроса, которые аналогичны источнику и стоку в задаче о максимальном потоке . Материал транспортируется от узлов снабжения к узлам спроса.
- В узле предложения к потоку добавляется положительная сумма — предложение. Например, предложение может представлять собой производство в этом узле.
- В узле спроса из потока забирается отрицательная сумма — спрос. Например, спрос может представлять потребление в этом узле.
Для удобства мы предположим, что все узлы, кроме узлов спроса и предложения, имеют нулевое предложение (и спрос).
Для задачи потока минимальных затрат у нас есть следующее правило сохранения потока, которое учитывает спрос и предложение:
На графике ниже показана задача о минимальном потоке затрат. Дуги помечены парами чисел: первое число — это мощность, второе — стоимость. Числа в скобках рядом с узлами обозначают предложение или спрос. Узел 0 — это узел предложения с предложением 20, а узлы 3 и 4 — это узлы спроса со спросом -5 и -15 соответственно.
Импортируйте библиотеки
Следующий код импортирует необходимую библиотеку.
Питон
import numpy as np from ortools.graph.python import min_cost_flow
С++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Ява
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
С#
using System; using Google.OrTools.Graph;
Объявить решатель
Для решения задачи воспользуемся решателем SimpleMinCostFlow .
Питон
# Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow()
С++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Ява
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
С#
// 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. 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]
С++
// 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};Ява
// 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};С#
// 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 решателя создает вектор поставок для узлов.
Питон
# 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)С++
// 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]);
}Ява
// 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]);
}С#
// 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() .
Питон
# Find the min cost flow. status = smcf.solve()
С++
// Find the min cost flow. int status = min_cost_flow.Solve();
Ява
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
С#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.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 (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;
}Ява
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);
}С#
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
Полные программы
Собрав все это вместе, вот полные программы.
Питон
"""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()С++
// 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;
}Ява
// 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() {}
}С#
// 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);
}
}
}