Trong các phần sau, bạn sẽ nhận ví dụ về vấn đề lưu lượng tối đa (lưu lượng tối đa).
Ví dụ về lưu lượng tối đa
Vấn đề này được xác định bằng biểu đồ sau đây, biểu thị một mạng lưới giao thông:
Bạn muốn truyền tải tài liệu từ nút 0 (nguồn) đến nút 4 (bể chứa). Những con số bên cạnh các cung tròn là dung lượng của chúng. Dung tích của cung là dung lượng tối đa có thể được truyền qua vòng cung đó trong một khoảng thời gian cố định. Dung lượng là giới hạn của bài toán.
Luồng là phép gán một số không âm cho mỗi cung (lượng dữ liệu) đáp ứng quy tắc bảo toàn luồng sau:
Vấn đề về lưu lượng tối đa là tìm một luồng mà tổng số tiền của luồng cho toàn bộ mạng càng lớn càng tốt.
Các phần sau đây trình bày một chương trình để tìm luồng tối đa từ nguồn (0) đến bồn lưu trữ dữ liệu (4).
Nhập thư viện
Mã sau đây nhập thư viện bắt buộc.
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;
Khai báo trình giải
Để giải bài toán này, bạn có thể sử dụng trình giải 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();
Xác định dữ liệu
Bạn sẽ xác định biểu đồ cho bài toán về 3 mảng, cho nút bắt đầu, nút kết thúc và dung lượng của các vòng cung. Độ dài của mỗi mảng bằng số lượng ARC trong biểu đồ.
Đối với mỗi i, cung i đi từ start_nodes[i] đến end_nodes[i] và dung lượng được cung cấp bởi capacities[i]. Phần tiếp theo cho biết cách tạo vòng cung bằng dữ liệu này.
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 };
Thêm các cung tròn
Đối với mỗi nút bắt đầu và nút kết thúc, bạn sẽ tạo một vòng cung từ nút bắt đầu đến nút kết thúc với dung lượng đã cho, sử dụng phương thức AddArcWithCapacity. Dung lượng là những giới hạn của bài toán.
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");
}
Gọi trình giải
Giờ đây, tất cả các cung đã được xác định, tất cả những gì còn lại là gọi trình giải và hiển thị kết quả. Bạn gọi phương thức Solve(), cung cấp nguồn (0) và bồn lưu trữ dữ liệu (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);
Hiện kết quả
Bây giờ, bạn có thể hiển thị luồng trên mỗi cung.
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);
}
Sau đây là kết quả của chương trình:
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]
Số lượng luồng trên mỗi cung được hiển thị trong Flow.
Hoàn thành chương trình
Sau đây là toàn bộ các chương trình nếu bạn kết hợp kiến thức đã học.
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);
}
}
}