الحد الأقصى للتدفقات

وفي الأقسام التالية، ستحصل على مثال على الحد الأقصى للتدفق. (الحد الأقصى للتدفق).

مثال للتدفق الأقصى

يتم تحديد المشكلة من خلال الرسم البياني التالي، الذي يمثل إحدى وسائل النقل الشبكة:

وتريد نقل المواد من العقدة 0 (المصدر) إلى العقدة 4 ( الحوض). الأرقام بجانب الأقواس هي سعاتها، أي سعة القوس هي أقصى كمية يمكن نقلها عبره في فترة زمنية ثابتة. القدرات هي القيود المفروضة على المشكلة.

التدفق هو عملية تعيين رقم غير سالب لكل قوس ( مقدار التدفق) تستوفي قاعدة الحفاظ على التدفق التالية:

ملاحظة: في كل عقدة، بخلاف المصدر أو الحوض، يمثل التدفق الإجمالي لجميع الأقواس التي تؤدي إلى العقدة تساوي التدفق الإجمالي لجميع الأقواس التي تؤدي إليها.

تتمثل مشكلة الحد الأقصى للتدفق في العثور على تدفق يكون مجموع التدفق له الشبكة بأكملها بأكبر حجم ممكن.

تقدم الأقسام التالية برامج للعثور على أقصى تدفق من المصدر (0) إلى الحوض (4).

استيراد المكتبات

يستورد الرمز التالي المكتبة المطلوبة.

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;

تضمين أداة الحلّ

ولحل المشكلة، يمكنك استخدام 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();

تعريف البيانات

يمكنك تحديد الرسم البياني للمشكلة التي تتعلق بثلاث صفائف، بالنسبة لعُقد البداية، ونهاية وقدرات الأقواس. طول كل صفيفة يساوي عدد الأقواس في الرسم البياني.

لكل i، ينتقل القوس i من start_nodes[i] إلى end_nodes[i]، ويسعه يتم تقديمها من خلال capacities[i]. يعرض القسم التالي كيفية إنشاء الأقواس باستخدام هذه البيانات.

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 };

إضافة الأقواس

لكل عقدة بداية ونهاية، عليك إنشاء قوس من عقدة البداية إلى النهاية بالسعة المحددة، باستخدام طريقة AddArcWithCapacity. الإمكانات هي القيود للمشكلة.

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");
}

استدعاء أداة الحلّ

الآن وقد تم تحديد جميع الأقواس، كل ما تبقى هو استدعاء أداة الحلّ وعرض النتائج. وقد استدعيت الطريقة Solve() مع تقديم قيمة المصدر (0) والحوض (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);

عرض النتائج

يمكنك الآن عرض التدفق على مستوى كل قوس.

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);
}

في ما يلي مخرجات البرنامج:

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]

يتم عرض كميات التدفق في كل قوس ضمن Flow.

إكمال البرامج

بوضع كل شيء معًا، ها هي البرامج الكاملة.

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);
        }
    }
}