الحد الأدنى لتدفقات التكلفة

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

تتضمن مشكلة تدفق الحد الأدنى من التكلفة أيضًا عقدًا خاصة تسمى عقد التوريد أو الطلب تشبه المصدر والوعاء في مشكلة في الحدّ الأقصى للتدفق. يتم نقل المواد من عُقد التوريد إلى عُقد الطلب.

• في عقدة التوريد، تتم إضافة مقدار موجب، وهو مقدار الإمداد، إلى التدفق. على سبيل المثال، يمكن أن يمثل التوريد الإنتاج في تلك العقدة.
• في عقدة الطلب، يتم رصد مبلغ سالب، أي الطلب. بعيدًا عن التدفق. ويمكن أن يمثل الطلب استهلاكًا في هذا الجزء، مثال.

ولتسهيل الأمر، سنفترض أن جميع النقاط، بخلاف عقد العرض أو الطلب، ليس لديها العرض (والطلب).

بالنسبة لمشكلة تدفق الحد الأدنى من التكلفة، لدينا قاعدة حفظ التدفق التالية، الذي يأخذ المستلزمات والطلبات في الاعتبار:

ملاحظة: في كل عقدة، يكون التدفق الإجمالي الناتج من العُقدة مطروحًا منه إجمالي التدفق التي تؤدي إلى العقدة تساوي العرض (أو الطلب) في تلك العقدة.

يوضح الرسم البياني التالي مشكلة تدفق الحد الأدنى من التكلفة. يتم تصنيف الأقواس بالأزواج. من الأرقام: الرقم الأول هو السعة والرقم الثاني هو التكلفة. تمثل الأرقام الموجودة بين قوسين بجوار العقد الإمدادات أو الطلبات. العقدة يمثل 0 عقدة توريد مع العرض 20، في حين أن العقد 3 و4 هما عقدتا طلب، مع على -5 و-15 على التوالي.

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

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

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;

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

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

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

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

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

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

ننشئ قوسًا من عقدة بداية ونهاية لكل عقدة بداية ونهاية. بالسعة وتكلفة الوحدة المحددة باستخدام الطريقة AddArcWithCapacityAndUnitCost.

أداة الحلّ SetNodeSupply لإنشاء متجه الإمدادات للعقد.

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

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

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

عرض النتائج

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

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

وفيما يلي مُخرجات برنامج 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

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

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

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