Min cost flow python

Потоки с минимальными затратами

Оптимизируйте свои подборки Сохраняйте и классифицируйте контент в соответствии со своими настройками.

С задачей максимального потока тесно связана задача минимальной стоимости ( минимальной стоимости ) потока, в которой каждая дуга графа имеет удельную стоимость транспортировки материала по ней. Задача состоит в том, чтобы найти поток с наименьшими суммарными затратами.

В задаче потока минимальной стоимости также есть специальные узлы, называемые узлами предложения или узлами спроса, которые аналогичны источнику и приемнику в задаче максимального потока . Материал транспортируется от узлов снабжения к узлам спроса.

• В узле подачи к потоку добавляется положительное количество — поставка. Например, предложение может представлять производство в этом узле.
• В узле спроса из потока отнимается отрицательное количество — спрос. Например, спрос может представлять потребление в этом узле.

Для удобства предположим, что все узлы, кроме узлов спроса и предложения, имеют нулевое предложение (и спрос).

Для задачи потока с минимальными затратами у нас есть следующее правило сохранения потока, учитывающее спрос и предложение:

Примечание. В каждом узле общий поток, выходящий из узла, за вычетом общего потока, входящего в узел, равен предложению (или спросу) в этом узле.

На приведенном ниже графике показана задача потока минимальных затрат. Дуги помечены парами чисел: первое число — это пропускная способность, а второе — стоимость. Цифры в круглых скобках рядом с узлами представляют запасы или потребности. Узел 0 является узлом снабжения с предложением 20, а узлы 3 и 4 являются узлами спроса со спросом -5 и -15 соответственно.

Импортируйте библиотеки

Следующий код импортирует необходимую библиотеку.

питон

import numpy as np from ortools.graph.python import min_cost_flow

С++

#include #include #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 start_nodes = ; std::vector end_nodes = ; std::vector capacities = ; std::vector unit_costs = ; // Define an array of supplies at each node. std::vector supplies = ;

Джава

// 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[] ; int[] endNodes = new int[] ; int[] capacities = new int[] ; int[] unitCosts = new int[] ; // Define an array of supplies at each node. int[] supplies = new int[] ;

С#

// 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) // Add node supplies. for (int i = 0; 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

С#

// 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

Вызвать решатель

Теперь, когда все дуги определены, остается только вызвать решатель и отобразить результаты. Мы вызываем метод 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: ') exit(1) print(f'Minimum 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' ->  / ' )

С++

if (status == MinCostFlow::OPTIMAL) < LOG(INFO) " > else

Джава

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

С#

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(«», minCostFlow.Flow(i)) + » / » + string.Format(«», minCostFlow.Capacity(i)) + » » + string.Format(«», cost)); > > else

Вот вывод программы 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: ') exit(1) print(f'Minimum 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' ->  / ' ) if __name__ == '__main__': main()

С++

// From Bradley, Hax and Maganti, ‘Applied Mathematical Programming’, figure 8.1 #include #include #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::vectorstart_nodes = ; std::vector end_nodes = ; std::vector capacities = ; std::vector unit_costs = ; // Define an array of supplies at each node. std::vector 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) // 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) " > else < LOG(INFO) > > // namespace operations_research int main()

Джава

// 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[] ; int[] endNodes = new int[] ; int[] capacities = new int[] ; int[] unitCosts = new int[] ; // Define an array of supplies at each node. int[] supplies = new int[] ; // 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("", minCostFlow.Flow(i)) + " / " + string.Format("", minCostFlow.Capacity(i)) + " " + string.Format("", cost)); > > else < Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status); >> >

Если не указано иное, контент на этой странице предоставляется по лицензии Creative Commons «С указанием авторства 4.0», а примеры кода – по лицензии Apache 2.0. Подробнее об этом написано в правилах сайта. Java – это зарегистрированный товарный знак корпорации Oracle и ее аффилированных лиц.

Последнее обновление: 2023-03-30 UTC.

Источник

min_cost_flow#

Returns a minimum cost flow satisfying all demands in digraph G.

G is a digraph with edge costs and capacities and in which nodes have demand, i.e., they want to send or receive some amount of flow. A negative demand means that the node wants to send flow, a positive demand means that the node want to receive flow. A flow on the digraph G satisfies all demand if the net flow into each node is equal to the demand of that node.

Parameters : G NetworkX graph

DiGraph on which a minimum cost flow satisfying all demands is to be found.

demand string

Nodes of the graph G are expected to have an attribute demand that indicates how much flow a node wants to send (negative demand) or receive (positive demand). Note that the sum of the demands should be 0 otherwise the problem in not feasible. If this attribute is not present, a node is considered to have 0 demand. Default value: ‘demand’.

capacity string

Edges of the graph G are expected to have an attribute capacity that indicates how much flow the edge can support. If this attribute is not present, the edge is considered to have infinite capacity. Default value: ‘capacity’.

weight string

Edges of the graph G are expected to have an attribute weight that indicates the cost incurred by sending one unit of flow on that edge. If not present, the weight is considered to be 0. Default value: ‘weight’.

Returns : flowDict dictionary

Dictionary of dictionaries keyed by nodes such that flowDict[u][v] is the flow edge (u, v).

This exception is raised if the input graph is not directed or not connected.

This exception is raised in the following situations:

• The sum of the demands is not zero. Then, there is no flow satisfying all demands.
• There is no flow satisfying all demand.

This exception is raised if the digraph G has a cycle of negative cost and infinite capacity. Then, the cost of a flow satisfying all demands is unbounded below.

This algorithm is not guaranteed to work if edge weights or demands are floating point numbers (overflows and roundoff errors can cause problems). As a workaround you can use integer numbers by multiplying the relevant edge attributes by a convenient constant factor (eg 100).

A simple example of a min cost flow problem.

>>> G = nx.DiGraph() >>> G.add_node("a", demand=-5) >>> G.add_node("d", demand=5) >>> G.add_edge("a", "b", weight=3, capacity=4) >>> G.add_edge("a", "c", weight=6, capacity=10) >>> G.add_edge("b", "d", weight=1, capacity=9) >>> G.add_edge("c", "d", weight=2, capacity=5) >>> flowDict = nx.min_cost_flow(G) 

Источник