Di bagian berikut, Anda akan mendapatkan contoh masalah aliran maksimum (aliran maksimum).
Contoh aliran maksimum
Masalah ini ditentukan oleh grafik berikut, yang merepresentasikan jaringan transportasi:
Anda ingin memindahkan material dari node 0 (sumber) ke node 4 (sink). Angka di samping busur adalah kapasitasnya — kapasitas busur adalah jumlah maksimum yang dapat diangkut melintasinya dalam jangka waktu tetap. Kapasitas adalah batasan untuk suatu masalah.
Alur adalah penetapan angka non-negatif ke setiap busur (jumlah aliran) yang memenuhi aturan konservasi aliran berikut:
Masalah aliran maksimum adalah menemukan aliran yang jumlah alirannya untuk seluruh jaringan adalah sebesar mungkin.
Bagian berikut menampilkan program untuk menemukan flow maksimum dari sumber (0) ke sink (4).
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
Python
import numpy as np from ortools.graph.python import max_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/max_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MaxFlow;
C#
using System; using Google.OrTools.Graph;
Mendeklarasikan pemecah masalah
Untuk mengatasi masalah tersebut, Anda dapat menggunakan pemecah masalah SimpleMaxFlow.
Python
# Instantiate a SimpleMaxFlow solver. smf = max_flow.SimpleMaxFlow()
C++
// Instantiate a SimpleMaxFlow solver. SimpleMaxFlow max_flow;
Java
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
C#
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
Menentukan data
Anda menentukan grafik untuk soal dengan tiga array, untuk node awal, node akhir, dan kapasitas busur. Panjang setiap array sama dengan jumlah busur dalam grafik.
Untuk setiap i, lengkung i dimulai dari start_nodes[i]
ke end_nodes[i]
, dan kapasitasnya
diberikan oleh capacities[i]
. Bagian berikutnya menunjukkan cara membuat busur menggunakan
data ini.
Python
# Define three parallel arrays: start_nodes, end_nodes, and the capacities # between each pair. For instance, the arc from node 0 to node 1 has a # capacity of 20. start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3]) end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4]) capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])
C++
// Define three parallel arrays: start_nodes, end_nodes, and the capacities // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 20. std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3}; std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4}; std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};
Java
// Define three parallel arrays: start_nodes, end_nodes, and the capacities // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 20. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3}; int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4}; int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20};
C#
// Define three parallel arrays: start_nodes, end_nodes, and the capacities // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 20. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 }; int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 }; int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 };
Menambahkan busur
Untuk setiap node awal dan node akhir, Anda membuat lengkungan dari node awal ke node akhir dengan kapasitas yang ditentukan, menggunakan metode AddArcWithCapacity. Kapasitas adalah kendala untuk suatu masalah.
Python
# Add arcs in bulk. # note: we could have used add_arc_with_capacity(start, end, capacity) all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) { throw new Exception("Internal error"); } }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) throw new Exception("Internal error"); }
Memanggil pemecah masalah
Setelah semua alur ditentukan, yang tersisa hanyalah memanggil
pemecah masalah dan menampilkan hasilnya. Anda memanggil metode Solve()
, yang menyediakan
sumber (0) dan sink (4).
Python
# Find the maximum flow between node 0 and node 4. status = smf.solve(0, 4)
C++
// Find the maximum flow between node 0 and node 4. int status = max_flow.Solve(0, 4);
Java
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.solve(0, 4);
C#
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.Solve(0, 4);
Menampilkan hasil
Sekarang, Anda dapat menampilkan alur di setiap busur.
Python
if status != smf.OPTIMAL: print("There was an issue with the max flow input.") print(f"Status: {status}") exit(1) print("Max flow:", smf.optimal_flow()) print("") print(" Arc Flow / Capacity") solution_flows = smf.flows(all_arcs) for arc, flow, capacity in zip(all_arcs, solution_flows, capacities): print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}") print("Source side min-cut:", smf.get_source_side_min_cut()) print("Sink side min-cut:", smf.get_sink_side_min_cut())
C++
if (status == MaxFlow::OPTIMAL) { LOG(INFO) << "Max flow: " << max_flow.OptimalFlow(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity"; for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) { LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " " << max_flow.Flow(i) << " / " << max_flow.Capacity(i); } } else { LOG(INFO) << "Solving the max flow problem failed. Solver status: " << status; }
Java
if (status == MaxFlow.Status.OPTIMAL) { System.out.println("Max. flow: " + maxFlow.getOptimalFlow()); System.out.println(); System.out.println(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.getNumArcs(); ++i) { System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " " + maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i)); } } else { System.out.println("Solving the max flow problem failed. Solver status: " + status); }
C#
if (status == MaxFlow.Status.OPTIMAL) { Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow()); Console.WriteLine(""); Console.WriteLine(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.NumArcs(); ++i) { Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " + string.Format("{0,3}", maxFlow.Flow(i)) + " / " + string.Format("{0,3}", maxFlow.Capacity(i))); } } else { Console.WriteLine("Solving the max flow problem failed. Solver status: " + status); }
Berikut adalah output program:
Max flow: 60 Arc Flow / Capacity 0 -> 1 20 / 20 0 -> 2 30 / 30 0 -> 3 10 / 10 1 -> 2 0 / 40 1 -> 4 20 / 30 2 -> 3 10 / 10 2 -> 4 20 / 20 3 -> 2 0 / 5 3 -> 4 20 / 20 Source side min-cut: [0] Sink side min-cut: [4, 1]
Jumlah aliran di setiap busur ditampilkan di bagian Flow
.
Selesaikan program
Dengan menggabungkan semuanya, berikut adalah program lengkapnya.
Python
"""From Taha 'Introduction to Operations Research', example 6.4-2.""" import numpy as np from ortools.graph.python import max_flow def main(): """MaxFlow simple interface example.""" # Instantiate a SimpleMaxFlow solver. smf = max_flow.SimpleMaxFlow() # Define three parallel arrays: start_nodes, end_nodes, and the capacities # between each pair. For instance, the arc from node 0 to node 1 has a # capacity of 20. start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3]) end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4]) capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20]) # Add arcs in bulk. # note: we could have used add_arc_with_capacity(start, end, capacity) all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities) # Find the maximum flow between node 0 and node 4. status = smf.solve(0, 4) if status != smf.OPTIMAL: print("There was an issue with the max flow input.") print(f"Status: {status}") exit(1) print("Max flow:", smf.optimal_flow()) print("") print(" Arc Flow / Capacity") solution_flows = smf.flows(all_arcs) for arc, flow, capacity in zip(all_arcs, solution_flows, capacities): print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}") print("Source side min-cut:", smf.get_source_side_min_cut()) print("Sink side min-cut:", smf.get_sink_side_min_cut()) if __name__ == "__main__": main()
C++
// From Taha 'Introduction to Operations Research', example 6.4-2.""" #include <cstdint> #include <vector> #include "ortools/graph/max_flow.h" namespace operations_research { // MaxFlow simple interface example. void SimpleMaxFlowProgram() { // Instantiate a SimpleMaxFlow solver. SimpleMaxFlow max_flow; // Define three parallel arrays: start_nodes, end_nodes, and the capacities // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 20. std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3}; std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4}; std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]); } // Find the maximum flow between node 0 and node 4. int status = max_flow.Solve(0, 4); if (status == MaxFlow::OPTIMAL) { LOG(INFO) << "Max flow: " << max_flow.OptimalFlow(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity"; for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) { LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " " << max_flow.Flow(i) << " / " << max_flow.Capacity(i); } } else { LOG(INFO) << "Solving the max flow problem failed. Solver status: " << status; } } } // namespace operations_research int main() { operations_research::SimpleMaxFlowProgram(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MaxFlow; /** Minimal MaxFlow program. */ public final class SimpleMaxFlowProgram { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow(); // Define three parallel arrays: start_nodes, end_nodes, and the capacities // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 20. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3}; int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4}; int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) { throw new Exception("Internal error"); } } // Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.solve(0, 4); if (status == MaxFlow.Status.OPTIMAL) { System.out.println("Max. flow: " + maxFlow.getOptimalFlow()); System.out.println(); System.out.println(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.getNumArcs(); ++i) { System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " " + maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i)); } } else { System.out.println("Solving the max flow problem failed. Solver status: " + status); } } private SimpleMaxFlowProgram() {} }
C#
// From Taha 'Introduction to Operations Research', example 6.4-2. using System; using Google.OrTools.Graph; public class SimpleMaxFlowProgram { static void Main() { // Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow(); // Define three parallel arrays: start_nodes, end_nodes, and the capacities // between each pair. For instance, the arc from node 0 to node 1 has a // capacity of 20. // From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 }; int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 }; int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]); if (arc != i) throw new Exception("Internal error"); } // Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.Solve(0, 4); if (status == MaxFlow.Status.OPTIMAL) { Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow()); Console.WriteLine(""); Console.WriteLine(" Arc Flow / Capacity"); for (int i = 0; i < maxFlow.NumArcs(); ++i) { Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " + string.Format("{0,3}", maxFlow.Flow(i)) + " / " + string.Format("{0,3}", maxFlow.Capacity(i))); } } else { Console.WriteLine("Solving the max flow problem failed. Solver status: " + status); } } }