Alur Maksimum

Di bagian berikut, Anda akan mendapatkan contoh flow maksimum (flow maks).

Contoh alur maksimum

Masalahnya didefinisikan oleh grafik berikut, yang mewakili sebuah transportasi jaringan:

grafik alur jaringan

Anda ingin mengangkut material dari node 0 (sumber) ke node 4 ( sink). Angka di samping busur adalah kapasitasnya — kapasitas busur adalah jumlah maksimum yang dapat diangkut melalui busur dalam satu periode waktu tetap. Kapasitas adalah kendala untuk masalah.

Alur adalah penetapan bilangan non-negatif untuk setiap busur ( jumlah aliran) yang memenuhi aturan konservasi aliran berikut:

Masalah aliran maksimum adalah menemukan aliran di mana jumlah alirannya seluruh jaringan sebesar mungkin.

Bagian berikut menampilkan program untuk menemukan alur maksimum dari sumber (0) ke sink (4).

Mengimpor library

Kode berikut akan 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

Untuk mengatasi masalah ini, 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 mendefinisikan grafik untuk masalah dengan tiga larik, untuk node awal, akhir node, dan kapasitas busur. Panjang setiap {i>array<i} sama dengan jumlah busur dalam grafik.

Untuk setiap i, arc 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 busur dari node awal ke node akhir dengan kapasitas tertentu, menggunakan metode AddArcWithCapacity. Kapasitas adalah batasan untuk masalah tersebut.

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 busur didefinisikan, yang tersisa hanyalah memanggil metode pemecah masalah dan menampilkan hasilnya. Anda memanggil metode Solve(), yang memberikan 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 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 alur di setiap busur ditampilkan di bawah Flow.

Selesaikan program

Menyatukan semuanya, berikut ini 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);
        }
    }
}