Masalah alur biaya minimum (biaya min) yang terkait erat dengan masalah alur maksimum adalah biaya per unit untuk pengangkutan material yang melewatinya. Masalahnya adalah menemukan alur dengan biaya total terkecil.
Masalah aliran biaya minimum juga memiliki node khusus, yang disebut node suplai atau node permintaan, yang mirip dengan sumber dan sink dalam masalah aliran maksimum. Material diangkut dari node pasokan ke node permintaan.
- Pada node suplai, jumlah positif — pasokan — ditambahkan ke aliran. Misalnya, pasokan dapat mewakili produksi pada node tersebut.
- Pada node permintaan, jumlah negatif — permintaan — akan dipindahkan dari aliran. Misalnya, permintaan dapat mewakili konsumsi pada node tersebut.
Untuk memudahkan, kita akan mengasumsikan bahwa semua node, selain node penawaran atau permintaan, memiliki pasokan (dan permintaan) nol.
Untuk masalah aliran biaya min, kita memiliki aturan konservasi aliran berikut, yang mempertimbangkan persediaan dan permintaan:
Grafik di bawah menunjukkan masalah aliran biaya min. Busur diberi label dengan pasangan angka: angka pertama adalah kapasitas dan angka kedua adalah biaya. Angka-angka dalam tanda kurung di sebelah {i>node<i} mewakili persediaan atau permintaan. Node 0 adalah node pasokan dengan pasokan 20, sedangkan node 3 dan 4 adalah node permintaan, dengan permintaan -5 dan -15.
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
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;
Mendeklarasikan pemecah masalah
Untuk mengatasi masalah tersebut, kita menggunakan pemecah masalah 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();
Menentukan data
Kode berikut mendefinisikan data untuk masalah tersebut. Dalam hal ini, ada empat array untuk node awal, node akhir, kapasitas, dan biaya satuan. Sekali lagi, panjang array adalah jumlah busur dalam grafik.
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 };
Menambahkan busur
Untuk setiap node awal dan node akhir, kita membuat lengkung dari node awal ke node akhir dengan kapasitas dan biaya satuan yang ditentukan, menggunakan metode AddArcWithCapacityAndUnitCost.
Metode SetNodeSupply pemecah masalah membuat vektor pasokan untuk node tersebut.
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]);
}
Memanggil pemecah masalah
Setelah semua alur ditentukan, yang tersisa hanyalah memanggil
pemecah masalah dan menampilkan hasilnya. Kita memanggil metode 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();
Menampilkan hasil
Sekarang, kita dapat menampilkan alur dan biaya di setiap busur.
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);
}
Berikut adalah output program 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
Selesaikan program
Dengan menggabungkan semuanya, berikut adalah program lengkapnya.
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);
}
}
}