หน้านี้ได้รับการแปลโดย Cloud Translation API

โฟลว์ต้นทุนขั้นต่ํา

มีความเกี่ยวข้องอย่างใกล้ชิดกับปัญหาการไหลสูงสุดคือต้นทุนขั้นต่ำ (ต้นทุนขั้นต่ำ) โจทย์การไหล ซึ่งแต่ละส่วนในกราฟมีต้นทุนต่อหน่วย ในการเรียนรู้ทั้งหมด ปัญหาก็คือการหาขั้นตอนที่มีค่าใช้จ่ายรวมน้อยที่สุด

ปัญหาการไหลของค่าใช้จ่ายขั้นต่ำยังมีโหนดพิเศษที่เรียกว่าโหนดอุปทานหรืออุปสงค์ ซึ่งคล้ายกับต้นทางและจมใน ปัญหาโฟลว์สูงสุด วัสดุมีการลำเลียงจากโหนดอุปทานไปยังโหนดอุปสงค์

ที่โหนดซัพพลาย จำนวนบวก — ซัพพลาย — จะถูกเพิ่มลงใน โฟลว์ได้ เช่น ซัพพลายอาจแสดงถึงการผลิตที่โหนดนั้น
ที่โหนดดีมานด์ จำนวนค่าลบ ซึ่งก็คือดีมานด์ ได้ไม่สะดุด ความต้องการอาจหมายถึงการใช้งานที่โหนดนั้น

เพื่อความสะดวก เราจะสมมติว่าโหนดทั้งหมด ยกเว้นโหนดอุปทานหรืออุปสงค์ ไม่มีซัพพลาย (และอุปสงค์)

สำหรับปัญหาโฟลว์ค่าใช้จ่ายขั้นต่ำ เรามีกฎการอนุรักษ์โฟลว์ต่อไปนี้ ซึ่งพิจารณาการจัดหาสินค้าและความต้องการ ได้แก่

กราฟด้านล่างแสดงปัญหาโฟลว์ของต้นทุนขั้นต่ำ เส้นโค้งมีป้ายกำกับเป็นคู่ ตัวเลขจำนวน 1 ตัว: จำนวนตัวแรกคือความจุ ส่วนจำนวนที่ 2 คือต้นทุน ตัวเลขในวงเล็บถัดจากโหนดแสดงถึงสินค้าหรืออุปสงค์ โหนด 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();

กำหนดข้อมูล

โค้ดต่อไปนี้จะระบุข้อมูลของปัญหา ในกรณีนี้ มี อาร์เรย์ 4 อาร์เรย์สำหรับโหนดเริ่มต้น โหนดปลายทาง ความจุ และต้นทุนต่อหน่วย ขอย้ำอีกครั้งว่า ความยาวของอาร์เรย์คือจำนวนโค้งในกราฟ

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