최대 흐름 문제와 밀접한 관련이 있는 문제는 최소 비용 (최소 비용) 흐름 문제입니다. 이 흐름 문제에는 그래프의 각 원호가 위로 자재를 운반하기 위한 단위 비용이 있습니다. 문제는 총비용이 가장 적은 흐름을 찾는 것입니다.
최소 비용 흐름 문제에는 공급 노드 또는 수요 노드라는 특수 노드도 있으며, 이는 최대 흐름 문제의 소스 및 싱크와 유사합니다. 머티리얼은 공급 노드에서 수요 노드로 전송됩니다.
- 공급 노드에서는 양의 양(공급량)이 흐름에 추가됩니다. 예를 들어 공급은 해당 노드의 프로덕션을 나타낼 수 있습니다.
- 수요 노드에서는 음수의 양(수요)이 흐름에서 멀어집니다. 예를 들어 수요는 해당 노드에서의 소비를 나타낼 수 있습니다.
편의를 위해 공급 노드 또는 수요 노드를 제외한 모든 노드에 공급 (및 수요)이 없다고 가정합니다.
최소 비용 흐름 문제의 경우 공급과 수요를 고려하는 다음과 같은 흐름 보존 규칙이 있습니다.
아래 그래프는 최소 비용 흐름 문제를 보여줍니다. 호는 숫자 쌍으로 레이블이 지정됩니다. 첫 번째 숫자는 용량이고 두 번째 숫자는 비용입니다. 노드 옆 괄호 안의 숫자는 공급 또는 수요를 나타냅니다. 노드 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();
데이터 정의
다음 코드는 문제에 관한 데이터를 정의합니다. 이 경우 시작 노드, 종료 노드, 용량, 단위 비용에 해당하는 4개의 배열이 있습니다. 마찬가지로 배열의 길이는 그래프의 호의 수입니다.
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); } } }