Mindestkostenflüsse

Die Mindestkosten (minimale Kosten) stehen in engem Zusammenhang mit dem Problem mit dem maximalen Datenfluss. Strömungsproblem, bei dem jeder Bogen im Diagramm über Einheitskosten für den Transport und Material darauf. Das Problem besteht darin, einen Ablauf mit den geringsten Gesamtkosten zu finden.

Das Problem mit den Mindestkosten hat auch spezielle Knoten, die als Angebotsknoten oder Nachfrage bezeichnet werden. Knoten, die der Quelle und der Senke im Max Flow-Problem. Material wird von Versorgungsknoten zu Nachfrageknoten transportiert.

• An einem Lieferknoten wird ein positiver Betrag – das Angebot – den Ablauf. Ein Angebot könnte beispielsweise die Produktion an diesem Knoten darstellen.
• An einem Nachfrageknoten wird ein negativer Betrag, der Nachfrage, genommen vom Fluss weg. Eine Nachfrage könnte den Verbrauch an diesem Knoten darstellen, Beispiel.

Der Einfachheit halber nehmen wir an, dass alle Knoten, mit Ausnahme von Angebots- oder Nachfrageknoten, Angebot und Nachfrage nicht haben.

Für das Problem mit den minimalen Kosten haben wir die folgende Regel zur Flusserhaltung: bei dem Material und Nachfrage berücksichtigt werden:

Hinweis: An jedem Knoten der gesamte aus dem Knoten ausgehende Datenfluss abzüglich des gesamten Flusses. zum Knoten führt, gleich dem Angebot (oder der Nachfrage) an diesem Knoten.

Das folgende Diagramm zeigt ein Problem mit dem Mindestkostenfluss. Die Bögen sind paarweise beschriftet. von Zahlen: Die erste Zahl steht für die Kapazität und die zweite Zahl für die Kosten. Die Zahlen in Klammern neben den Knoten stellen Material oder Bedarf dar. Knoten 0 ist ein Versorgungsknoten mit Angebot 20, die Knoten 3 und 4 sind Nachfrageknoten, mit -5 bzw. -15.

Bibliotheken importieren

Mit dem folgenden Code wird die erforderliche Bibliothek importiert.

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;

Löser deklarieren

Um das Problem zu lösen, verwenden wir SimpleMinCostFlow Solver.

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

Daten definieren

Der folgende Code definiert die Daten für das Problem. In diesem Fall gibt es vier Arrays für die Startknoten, Endknoten, Kapazitäten und Stückkosten. Auch hier gilt: ist die Länge der Arrays die Anzahl der Bögen im Graphen.

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

Bögen hinzufügen

Für jeden Start- und Endknoten erstellen wir einen Bogen vom Startknoten zum Endknoten. mit den gegebenen Kapazitäts- und Stückkosten unter Verwendung der Methode AddArcWithCapacityAndUnitCost festlegen.

Der Löser SetNodeSupply erstellt einen Vektor von Materialien für die Knoten.

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

Solver aufrufen

Nachdem nun alle Bögen definiert wurden, muss nur noch die Funktion und die Ergebnisse anzeigen. Die Methode Solve() wird aufgerufen.

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

Ergebnisse anzeigen

Jetzt können wir den Fluss und die Kosten für jeden Bogen darstellen.

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

Hier ist die Ausgabe des Python-Programms:

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

Programme abschließen

Hier sind die kompletten Programme.

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