Zuweisung als Problem mit dem Mindestkostenfluss

Sonderfälle können Sie mit dem Minen Cost Flow Solver Aufgabenzuweisung.

Tatsächlich liefert der minimale Kostenfluss oft eine Lösung schneller als die MIP- oder CP-SAT-Löser. MIP und CP-SAT können jedoch eine größere Gruppe von Problemen lösen Min. Cost-Flow. Daher sind MIP oder CP-SAT in den meisten Fällen die beste Wahl.

In den folgenden Abschnitten werden Python-Programme vorgestellt, mit denen sich Folgendes lösen lässt: Aufgaben mit dem Minen Cost Flow Solver:

Beispiel für lineare Zuweisung

In diesem Abschnitt erfahren Sie, wie Sie das hier beschriebene Beispiel lösen. Linear Assignment Solver, als Mindestwert Kostenflussprobleme lösen.

Bibliotheken importieren

Mit dem folgenden Code wird die erforderliche Bibliothek importiert.

Python

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

Mit dem folgenden Code wird der Mindestbetrag für das Abrechnungsmodell erstellt.

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 erstellen

Das Flussdiagramm für das Problem besteht aus dem zweiteiligen Diagramm für die Kosten (siehe die Aufgabenübersicht finden Sie Beispiel) mit einer Quelle und einer Senke.

Diagramm für Netzwerkkostenfluss

Die Daten enthalten die folgenden vier Arrays, die den Startknoten entsprechen: Endknoten, Kapazitäten und Kosten für das Problem. Die Länge jedes Arrays beträgt Anzahl der Bögen im Diagramm.

Python

# Define the directed graph for the flow.
start_nodes = (
    [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8]
)
end_nodes = (
    [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9]
)
capacities = (
    [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1]
)
costs = (
    [0, 0, 0, 0]
    + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115]
    + [0, 0, 0, 0]
)

source = 0
sink = 9
tasks = 4
supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]

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.
const std::vector<int64_t> start_nodes = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
                                          3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8};
const std::vector<int64_t> end_nodes = {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8,
                                        5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9};
const std::vector<int64_t> capacities = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                                         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
const std::vector<int64_t> unit_costs = {0,  0,   0,  0,   90,  76, 75, 70,
                                         35, 85,  55, 65,  125, 95, 90, 105,
                                         45, 110, 95, 115, 0,   0,  0,  0};

const int64_t source = 0;
const int64_t sink = 9;
const int64_t tasks = 4;
// Define an array of supplies at each node.
const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};

Java

// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes =
    new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8};
int[] endNodes =
    new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9};
int[] capacities =
    new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int[] unitCosts = new int[] {
    0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0};

int source = 0;
int sink = 9;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};

C#

// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 };
int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 };
int[] capacities = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int[] unitCosts = { 0,   0,  0,  0,   90, 76,  75, 70,  35, 85, 55, 65,
                    125, 95, 90, 105, 45, 110, 95, 115, 0,  0,  0,  0 };

int source = 0;
int sink = 9;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };

Um zu verdeutlichen, wie die Daten aufgebaut sind, wird jedes Array in drei unterteilt. Subarrays:

  • Das erste Array entspricht den Bögen, die aus der Quelle herausführen.
  • Das zweite Array entspricht den Bögen zwischen Workern und Aufgaben. Für costs ist dies nur der Wert Kostenmatrix (wird vom linearen Zuweisungslöser verwendet), zu einem Vektor vereinfacht.
  • Das dritte Array entspricht den Bögen, die in die Senke führen.

Die Daten enthalten auch den Vektor supplies, der das Angebot an jedem Knoten.

Wie ein Problem mit den Mindestkosten ein Zuweisungsproblem darstellt

Inwiefern stellt das obige Problem des Ablaufs der Mindestkosten ein Zuweisungsproblem dar? Erstens: Da die Kapazität jedes Bogens 1 beträgt, bringt die Versorgung von 4 an der Quelle alle Kräfte der vier Bögen, die zu den Workern führen, einen Fluss von 1 haben.

Als Nächstes erzwingt die Bedingung „flow-in-equals-out“ den Ablauf aus jedem Worker 1 sein. Wenn möglich würde der Matherechner diesen Fluss über die Mindestkosten hinweg leiten. einen Bogen, der aus jedem Worker herausführt. Der Matherechner kann jedoch die Abläufe von zwei verschiedenen Mitarbeitenden zu einer einzigen Aufgabe. In diesem Fall gäbe es eine kombinierte ein zweifacher Fluss bei dieser Aufgabe, der nicht über einen Bogen hinweg Kapazität 1 von der Aufgabe zur Senke. Der Solver kann eine Aufgabe also nur einem einzelnen Worker zuweisen, die für das Aufgabenproblem erforderlich sind.

Schließlich erzwingt die "flow-in-equals-out"-Bedingung jeder Aufgabe, Outflow von 1, sodass jede Aufgabe von einem Worker ausgeführt wird.

Diagramm und Einschränkungen erstellen

Mit dem folgenden Code werden das Diagramm und die Einschränkungen erstellt.

Python

# Add each arc.
for i in range(len(start_nodes)):
    smcf.add_arc_with_capacity_and_unit_cost(
        start_nodes[i], end_nodes[i], capacities[i], costs[i]
    )
# Add node supplies.
for i in range(len(supplies)):
    smcf.set_node_supply(i, supplies[i])

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

Mit dem folgenden Code wird der Löser aufgerufen und die Lösung angezeigt.

Python

# Find the minimum cost flow between node 0 and node 10.
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();

Die Lösung besteht aus den Bögen zwischen Workern und Aufgaben, denen ein 1 durch den Löser. (Bögen, die mit der Quelle oder Senke verbunden sind, Lösung finden.)

Das Programm prüft jeden Bogen, um festzustellen, ob er Ablauf 1 enthält. Wenn ja, gibt Tail (Startknoten) und Head (Endknoten) des Bogens, die einem Arbeitnehmer und Aufgabe in der Aufgabe hinzufügen.

Ausgabe des Programms

Python

if status == smcf.OPTIMAL:
    print("Total cost = ", smcf.optimal_cost())
    print()
    for arc in range(smcf.num_arcs()):
        # Can ignore arcs leading out of source or into sink.
        if smcf.tail(arc) != source and smcf.head(arc) != sink:

            # Arcs in the solution have a flow value of 1. Their start and end nodes
            # give an assignment of worker to task.
            if smcf.flow(arc) > 0:
                print(
                    "Worker %d assigned to task %d.  Cost = %d"
                    % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
                )
else:
    print("There was an issue with the min cost flow input.")
    print(f"Status: {status}")

C++

if (status == MinCostFlow::OPTIMAL) {
  LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost();
  LOG(INFO) << "";
  for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
    // Can ignore arcs leading out of source or into sink.
    if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != sink) {
      // Arcs in the solution have a flow value of 1. Their start and end
      // nodes give an assignment of worker to task.
      if (min_cost_flow.Flow(i) > 0) {
        LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
                  << " assigned to task " << min_cost_flow.Head(i)
                  << " Cost: " << min_cost_flow.UnitCost(i);
      }
    }
  }
} else {
  LOG(INFO) << "Solving the min cost flow problem failed.";
  LOG(INFO) << "Solver status: " << status;
}

Java

if (status == MinCostFlow.Status.OPTIMAL) {
  System.out.println("Total cost: " + minCostFlow.getOptimalCost());
  System.out.println();
  for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
    // Can ignore arcs leading out of source or into sink.
    if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) {
      // Arcs in the solution have a flow value of 1. Their start and end nodes
      // give an assignment of worker to task.
      if (minCostFlow.getFlow(i) > 0) {
        System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
            + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
      }
    }
  }
} 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("Total cost: " + minCostFlow.OptimalCost());
    Console.WriteLine("");
    for (int i = 0; i < minCostFlow.NumArcs(); ++i)
    {
        // Can ignore arcs leading out of source or into sink.
        if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink)
        {
            // Arcs in the solution have a flow value of 1. Their start and end nodes
            // give an assignment of worker to task.
            if (minCostFlow.Flow(i) > 0)
            {
                Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
                                  " Cost: " + minCostFlow.UnitCost(i));
            }
        }
    }
}
else
{
    Console.WriteLine("Solving the min cost flow problem failed.");
    Console.WriteLine("Solver status: " + status);
}

Hier ist die Ausgabe des Programms.

Total cost = 265

Worker 1 assigned to task 8.  Cost = 70
Worker 2 assigned to task 7.  Cost = 55
Worker 3 assigned to task 6.  Cost = 95
Worker 4 assigned to task 5.  Cost = 45

Time = 0.000245 seconds

Das Ergebnis ist dasselbe wie bei der linearen Aufgabenlöser (mit Ausnahme der Anzahl der Worker und Kosten). Der Lineare Aufgabenlöser ist etwas schneller. als der Mindestkostenfluss: 0,000147 Sekunden im Vergleich zu 0,000458 Sekunden.

Das gesamte Programm

Das gesamte Programm ist unten zu sehen.

Python

"""Linear assignment example."""
from ortools.graph.python import min_cost_flow


def main():
    """Solving an Assignment Problem with MinCostFlow."""
    # Instantiate a SimpleMinCostFlow solver.
    smcf = min_cost_flow.SimpleMinCostFlow()

    # Define the directed graph for the flow.
    start_nodes = (
        [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8]
    )
    end_nodes = (
        [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9]
    )
    capacities = (
        [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1]
    )
    costs = (
        [0, 0, 0, 0]
        + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115]
        + [0, 0, 0, 0]
    )

    source = 0
    sink = 9
    tasks = 4
    supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]

    # Add each arc.
    for i in range(len(start_nodes)):
        smcf.add_arc_with_capacity_and_unit_cost(
            start_nodes[i], end_nodes[i], capacities[i], costs[i]
        )
    # Add node supplies.
    for i in range(len(supplies)):
        smcf.set_node_supply(i, supplies[i])

    # Find the minimum cost flow between node 0 and node 10.
    status = smcf.solve()

    if status == smcf.OPTIMAL:
        print("Total cost = ", smcf.optimal_cost())
        print()
        for arc in range(smcf.num_arcs()):
            # Can ignore arcs leading out of source or into sink.
            if smcf.tail(arc) != source and smcf.head(arc) != sink:

                # Arcs in the solution have a flow value of 1. Their start and end nodes
                # give an assignment of worker to task.
                if smcf.flow(arc) > 0:
                    print(
                        "Worker %d assigned to task %d.  Cost = %d"
                        % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
                    )
    else:
        print("There was an issue with the min cost flow input.")
        print(f"Status: {status}")


if __name__ == "__main__":
    main()

C++

#include <cstdint>
#include <vector>

#include "ortools/graph/min_cost_flow.h"

namespace operations_research {
// MinCostFlow simple interface example.
void AssignmentMinFlow() {
  // 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.
  const std::vector<int64_t> start_nodes = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
                                            3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8};
  const std::vector<int64_t> end_nodes = {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8,
                                          5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9};
  const std::vector<int64_t> capacities = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                                           1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  const std::vector<int64_t> unit_costs = {0,  0,   0,  0,   90,  76, 75, 70,
                                           35, 85,  55, 65,  125, 95, 90, 105,
                                           45, 110, 95, 115, 0,   0,  0,  0};

  const int64_t source = 0;
  const int64_t sink = 9;
  const int64_t tasks = 4;
  // Define an array of supplies at each node.
  const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};

  // 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) << "Total cost: " << min_cost_flow.OptimalCost();
    LOG(INFO) << "";
    for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
      // Can ignore arcs leading out of source or into sink.
      if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != sink) {
        // Arcs in the solution have a flow value of 1. Their start and end
        // nodes give an assignment of worker to task.
        if (min_cost_flow.Flow(i) > 0) {
          LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
                    << " assigned to task " << min_cost_flow.Head(i)
                    << " Cost: " << min_cost_flow.UnitCost(i);
        }
      }
    }
  } else {
    LOG(INFO) << "Solving the min cost flow problem failed.";
    LOG(INFO) << "Solver status: " << status;
  }
}

}  // namespace operations_research

int main() {
  operations_research::AssignmentMinFlow();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MinCostFlow;
import com.google.ortools.graph.MinCostFlowBase;

/** Minimal Assignment Min Flow. */
public class AssignmentMinFlow {
  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.
    int[] startNodes =
        new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8};
    int[] endNodes =
        new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9};
    int[] capacities =
        new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    int[] unitCosts = new int[] {
        0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0};

    int source = 0;
    int sink = 9;
    int tasks = 4;
    // Define an array of supplies at each node.
    int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};

    // 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("Total cost: " + minCostFlow.getOptimalCost());
      System.out.println();
      for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
        // Can ignore arcs leading out of source or into sink.
        if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) {
          // Arcs in the solution have a flow value of 1. Their start and end nodes
          // give an assignment of worker to task.
          if (minCostFlow.getFlow(i) > 0) {
            System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
                + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
          }
        }
      }
    } else {
      System.out.println("Solving the min cost flow problem failed.");
      System.out.println("Solver status: " + status);
    }
  }

  private AssignmentMinFlow() {}
}

C#

using System;
using Google.OrTools.Graph;

public class AssignmentMinFlow
{
    static void Main()
    {
        // Instantiate a SimpleMinCostFlow solver.
        MinCostFlow minCostFlow = new MinCostFlow();

        // Define four parallel arrays: sources, destinations, capacities, and unit costs
        // between each pair.
        int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 };
        int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 };
        int[] capacities = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        int[] unitCosts = { 0,   0,  0,  0,   90, 76,  75, 70,  35, 85, 55, 65,
                            125, 95, 90, 105, 45, 110, 95, 115, 0,  0,  0,  0 };

        int source = 0;
        int sink = 9;
        int tasks = 4;
        // Define an array of supplies at each node.
        int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };

        // 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("Total cost: " + minCostFlow.OptimalCost());
            Console.WriteLine("");
            for (int i = 0; i < minCostFlow.NumArcs(); ++i)
            {
                // Can ignore arcs leading out of source or into sink.
                if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink)
                {
                    // Arcs in the solution have a flow value of 1. Their start and end nodes
                    // give an assignment of worker to task.
                    if (minCostFlow.Flow(i) > 0)
                    {
                        Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
                                          " Cost: " + minCostFlow.UnitCost(i));
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("Solving the min cost flow problem failed.");
            Console.WriteLine("Solver status: " + status);
        }
    }
}

Zuweisung mit Teams von Mitarbeitern

In diesem Abschnitt wird ein allgemeineres Problem bei der Zuweisung dargestellt. Bei dieser Aufgabe haben sechs werden die Mitarbeitenden in zwei Teams aufgeteilt. Die Aufgabe besteht darin, damit die Arbeitslast gleichmäßig auf die Teams verteilt ist, damit jedes Team zwei der Aufgaben ausführt.

Eine MIP-Lösen-Lösung für dieses Problem findest du unter Zuweisung durch Mitarbeiterteams.

In den folgenden Abschnitten wird ein Programm beschrieben, das das Problem mithilfe der min. Cost-Flow-Sortiment.

Bibliotheken importieren

Mit dem folgenden Code wird die erforderliche Bibliothek importiert.

Python

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

Mit dem folgenden Code wird der Mindestbetrag für das Abrechnungsmodell erstellt.

Python

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 erstellen

Mit dem folgenden Code werden die Daten für das Programm erstellt.

Python

# Define the directed graph for the flow.
team_a = [1, 3, 5]
team_b = [2, 4, 6]

start_nodes = (
    # fmt: off
  [0, 0]
  + [11, 11, 11]
  + [12, 12, 12]
  + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6]
  + [7, 8, 9, 10]
    # fmt: on
)
end_nodes = (
    # fmt: off
  [11, 12]
  + team_a
  + team_b
  + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10]
  + [13, 13, 13, 13]
    # fmt: on
)
capacities = (
    # fmt: off
  [2, 2]
  + [1, 1, 1]
  + [1, 1, 1]
  + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  + [1, 1, 1, 1]
    # fmt: on
)
costs = (
    # fmt: off
  [0, 0]
  + [0, 0, 0]
  + [0, 0, 0]
  + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95]
  + [0, 0, 0, 0]
    # fmt: on
)

source = 0
sink = 13
tasks = 4
# Define an array of supplies at each node.
supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]

C++

// Define the directed graph for the flow.
const std::vector<int64_t> team_A = {1, 3, 5};
const std::vector<int64_t> team_B = {2, 4, 6};

const std::vector<int64_t> start_nodes = {
    0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3,
    3, 3, 4,  4,  4,  4,  5,  5,  5, 5, 6, 6, 6, 6, 7, 8, 9, 10};
const std::vector<int64_t> end_nodes = {
    11, 12, 1, 3, 5, 2,  4, 6, 7, 8,  9, 10, 7, 8,  9,  10, 7,  8,
    9,  10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8,  9, 10, 13, 13, 13, 13};
const std::vector<int64_t> capacities = {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                                         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                                         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
const std::vector<int64_t> unit_costs = {
    0,  0,   0,  0,  0,   0,  0,   0,   90, 76,  75, 70,
    35, 85,  55, 65, 125, 95, 90,  105, 45, 110, 95, 115,
    60, 105, 80, 75, 45,  65, 110, 95,  0,  0,   0,  0};

const int64_t source = 0;
const int64_t sink = 13;
const int64_t tasks = 4;
// Define an array of supplies at each node.
const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0,
                                       0,     0, 0, 0, 0, 0, -tasks};

Java

// Define the directed graph for the flow.
// int[] teamA = new int[] {1, 3, 5};
// int[] teamB = new int[] {2, 4, 6};

int[] startNodes = new int[] {0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
    4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10};
int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7,
    8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13};
int[] capacities = new int[] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int[] unitCosts = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95,
    90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0};

int source = 0;
int sink = 13;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};

C#

// Define the directed graph for the flow.
int[] teamA = { 1, 3, 5 };
int[] teamB = { 2, 4, 6 };

// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3,
                     3, 3, 4,  4,  4,  4,  5,  5,  5, 5, 6, 6, 6, 6, 7, 8, 9, 10 };
int[] endNodes = { 11, 12, 1, 3, 5, 2,  4, 6, 7, 8,  9, 10, 7, 8,  9,  10, 7,  8,
                   9,  10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8,  9, 10, 13, 13, 13, 13 };
int[] capacities = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int[] unitCosts = { 0,  0,   0,  0,   0,  0,   0,  0,   90, 76, 75, 70, 35,  85, 55, 65, 125, 95,
                    90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0,  0,  0,   0 };

int source = 0;
int sink = 13;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };

Die Worker entsprechen den Knoten 1 bis 6. Team A besteht aus den Workern 1, 3 und 5, und Team B besteht aus den Workern 2, 4 und 6. Die Aufgaben sind von 7 bis 10 nummeriert.

Es gibt zwei neue Knoten, 11 und 12, zwischen der Quelle und den Workern. Node 11 ist und Knoten 12 ist mit den Knoten für Team A verbunden. Team B mit einer Kapazitätsbögen von 1. Das folgende Diagramm zeigt nur die Knoten und Bögen von der Quelle zu den Workern.

Diagramm für Netzwerkkostenfluss

Der Schlüssel zum Ausgleichen der Arbeitslast ist, dass die Quelle 0 mit den Knoten 11 verbunden ist. und 12 in Bögen der Kapazität 2. Das bedeutet, dass die Knoten 11 und 12 (und somit Teams A und B) können einen maximalen Fluss von 2 haben. Daher kann jedes Team höchstens zwei der Aufgaben ausführen.

Einschränkungen erstellen

Python

# Add each arc.
for i in range(0, len(start_nodes)):
    smcf.add_arc_with_capacity_and_unit_cost(
        start_nodes[i], end_nodes[i], capacities[i], costs[i]
    )

# Add node supplies.
for i in range(0, len(supplies)):
    smcf.set_node_supply(i, supplies[i])

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

Python

# Find the minimum cost flow between node 0 and node 10.
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();

Ausgabe des Programms

Python

if status == smcf.OPTIMAL:
    print("Total cost = ", smcf.optimal_cost())
    print()
    for arc in range(smcf.num_arcs()):
        # Can ignore arcs leading out of source or intermediate, or into sink.
        if (
            smcf.tail(arc) != source
            and smcf.tail(arc) != 11
            and smcf.tail(arc) != 12
            and smcf.head(arc) != sink
        ):

            # Arcs in the solution will have a flow value of 1.
            # There start and end nodes give an assignment of worker to task.
            if smcf.flow(arc) > 0:
                print(
                    "Worker %d assigned to task %d.  Cost = %d"
                    % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
                )
else:
    print("There was an issue with the min cost flow input.")
    print(f"Status: {status}")

C++

if (status == MinCostFlow::OPTIMAL) {
  LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost();
  LOG(INFO) << "";
  for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
    // Can ignore arcs leading out of source or intermediate nodes, or into
    // sink.
    if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 &&
        min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != sink) {
      // Arcs in the solution have a flow value of 1. Their start and end
      // nodes give an assignment of worker to task.
      if (min_cost_flow.Flow(i) > 0) {
        LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
                  << " assigned to task " << min_cost_flow.Head(i)
                  << " Cost: " << min_cost_flow.UnitCost(i);
      }
    }
  }
} else {
  LOG(INFO) << "Solving the min cost flow problem failed.";
  LOG(INFO) << "Solver status: " << status;
}

Java

if (status == MinCostFlow.Status.OPTIMAL) {
  System.out.println("Total cost: " + minCostFlow.getOptimalCost());
  System.out.println();
  for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
    // Can ignore arcs leading out of source or intermediate nodes, or into sink.
    if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11
        && minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) {
      // Arcs in the solution have a flow value of 1. Their start and end nodes
      // give an assignment of worker to task.
      if (minCostFlow.getFlow(i) > 0) {
        System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
            + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
      }
    }
  }
} 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("Total cost: " + minCostFlow.OptimalCost());
    Console.WriteLine("");
    for (int i = 0; i < minCostFlow.NumArcs(); ++i)
    {
        // Can ignore arcs leading out of source or into sink.
        if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 &&
            minCostFlow.Head(i) != sink)
        {
            // Arcs in the solution have a flow value of 1. Their start and end nodes
            // give an assignment of worker to task.
            if (minCostFlow.Flow(i) > 0)
            {
                Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
                                  " Cost: " + minCostFlow.UnitCost(i));
            }
        }
    }
}
else
{
    Console.WriteLine("Solving the min cost flow problem failed.");
    Console.WriteLine("Solver status: " + status);
}

Im Folgenden sehen Sie die Ausgabe des Programms.

Total cost = 250

Worker 1 assigned to task 9.  Cost =  75
Worker 2 assigned to task 7.  Cost =  35
Worker 5 assigned to task 10.  Cost =  75
Worker 6 assigned to task 8.  Cost =  65

Time = 0.00031 seconds

Team A werden die Aufgaben 9 und 10 zugewiesen, während Team B die Aufgaben 7 und 8 zugewiesen wird.

Beachten Sie, dass der Min. Cost Flow Solver für dieses Problem schneller ist als der MIP-Resolver, dauert etwa 0,006 Sekunden.

Das gesamte Programm

Das gesamte Programm ist unten zu sehen.

Python

"""Assignment with teams of workers."""
from ortools.graph.python import min_cost_flow


def main():
    """Solving an Assignment with teams of worker."""
    smcf = min_cost_flow.SimpleMinCostFlow()

    # Define the directed graph for the flow.
    team_a = [1, 3, 5]
    team_b = [2, 4, 6]

    start_nodes = (
        # fmt: off
      [0, 0]
      + [11, 11, 11]
      + [12, 12, 12]
      + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6]
      + [7, 8, 9, 10]
        # fmt: on
    )
    end_nodes = (
        # fmt: off
      [11, 12]
      + team_a
      + team_b
      + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10]
      + [13, 13, 13, 13]
        # fmt: on
    )
    capacities = (
        # fmt: off
      [2, 2]
      + [1, 1, 1]
      + [1, 1, 1]
      + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
      + [1, 1, 1, 1]
        # fmt: on
    )
    costs = (
        # fmt: off
      [0, 0]
      + [0, 0, 0]
      + [0, 0, 0]
      + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95]
      + [0, 0, 0, 0]
        # fmt: on
    )

    source = 0
    sink = 13
    tasks = 4
    # Define an array of supplies at each node.
    supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]

    # Add each arc.
    for i in range(0, len(start_nodes)):
        smcf.add_arc_with_capacity_and_unit_cost(
            start_nodes[i], end_nodes[i], capacities[i], costs[i]
        )

    # Add node supplies.
    for i in range(0, len(supplies)):
        smcf.set_node_supply(i, supplies[i])

    # Find the minimum cost flow between node 0 and node 10.
    status = smcf.solve()

    if status == smcf.OPTIMAL:
        print("Total cost = ", smcf.optimal_cost())
        print()
        for arc in range(smcf.num_arcs()):
            # Can ignore arcs leading out of source or intermediate, or into sink.
            if (
                smcf.tail(arc) != source
                and smcf.tail(arc) != 11
                and smcf.tail(arc) != 12
                and smcf.head(arc) != sink
            ):

                # Arcs in the solution will have a flow value of 1.
                # There start and end nodes give an assignment of worker to task.
                if smcf.flow(arc) > 0:
                    print(
                        "Worker %d assigned to task %d.  Cost = %d"
                        % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
                    )
    else:
        print("There was an issue with the min cost flow input.")
        print(f"Status: {status}")


if __name__ == "__main__":
    main()

C++

#include <cstdint>
#include <vector>

#include "ortools/graph/min_cost_flow.h"

namespace operations_research {
// MinCostFlow simple interface example.
void BalanceMinFlow() {
  // Instantiate a SimpleMinCostFlow solver.
  SimpleMinCostFlow min_cost_flow;

  // Define the directed graph for the flow.
  const std::vector<int64_t> team_A = {1, 3, 5};
  const std::vector<int64_t> team_B = {2, 4, 6};

  const std::vector<int64_t> start_nodes = {
      0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3,
      3, 3, 4,  4,  4,  4,  5,  5,  5, 5, 6, 6, 6, 6, 7, 8, 9, 10};
  const std::vector<int64_t> end_nodes = {
      11, 12, 1, 3, 5, 2,  4, 6, 7, 8,  9, 10, 7, 8,  9,  10, 7,  8,
      9,  10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8,  9, 10, 13, 13, 13, 13};
  const std::vector<int64_t> capacities = {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                                           1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                                           1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  const std::vector<int64_t> unit_costs = {
      0,  0,   0,  0,  0,   0,  0,   0,   90, 76,  75, 70,
      35, 85,  55, 65, 125, 95, 90,  105, 45, 110, 95, 115,
      60, 105, 80, 75, 45,  65, 110, 95,  0,  0,   0,  0};

  const int64_t source = 0;
  const int64_t sink = 13;
  const int64_t tasks = 4;
  // Define an array of supplies at each node.
  const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0,
                                         0,     0, 0, 0, 0, 0, -tasks};

  // 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) << "Total cost: " << min_cost_flow.OptimalCost();
    LOG(INFO) << "";
    for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
      // Can ignore arcs leading out of source or intermediate nodes, or into
      // sink.
      if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 &&
          min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != sink) {
        // Arcs in the solution have a flow value of 1. Their start and end
        // nodes give an assignment of worker to task.
        if (min_cost_flow.Flow(i) > 0) {
          LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
                    << " assigned to task " << min_cost_flow.Head(i)
                    << " Cost: " << min_cost_flow.UnitCost(i);
        }
      }
    }
  } else {
    LOG(INFO) << "Solving the min cost flow problem failed.";
    LOG(INFO) << "Solver status: " << status;
  }
}

}  // namespace operations_research

int main() {
  operations_research::BalanceMinFlow();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MinCostFlow;
import com.google.ortools.graph.MinCostFlowBase;

/** Minimal Assignment Min Flow. */
public class BalanceMinFlow {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    // Instantiate a SimpleMinCostFlow solver.
    MinCostFlow minCostFlow = new MinCostFlow();

    // Define the directed graph for the flow.
    // int[] teamA = new int[] {1, 3, 5};
    // int[] teamB = new int[] {2, 4, 6};

    int[] startNodes = new int[] {0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
        4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10};
    int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7,
        8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13};
    int[] capacities = new int[] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    int[] unitCosts = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95,
        90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0};

    int source = 0;
    int sink = 13;
    int tasks = 4;
    // Define an array of supplies at each node.
    int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};

    // 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("Total cost: " + minCostFlow.getOptimalCost());
      System.out.println();
      for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
        // Can ignore arcs leading out of source or intermediate nodes, or into sink.
        if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11
            && minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) {
          // Arcs in the solution have a flow value of 1. Their start and end nodes
          // give an assignment of worker to task.
          if (minCostFlow.getFlow(i) > 0) {
            System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
                + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
          }
        }
      }
    } else {
      System.out.println("Solving the min cost flow problem failed.");
      System.out.println("Solver status: " + status);
    }
  }

  private BalanceMinFlow() {}
}

C#

using System;
using Google.OrTools.Graph;

public class BalanceMinFlow
{
    static void Main()
    {
        // Instantiate a SimpleMinCostFlow solver.
        MinCostFlow minCostFlow = new MinCostFlow();

        // Define the directed graph for the flow.
        int[] teamA = { 1, 3, 5 };
        int[] teamB = { 2, 4, 6 };

        // Define four parallel arrays: sources, destinations, capacities, and unit costs
        // between each pair.
        int[] startNodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3,
                             3, 3, 4,  4,  4,  4,  5,  5,  5, 5, 6, 6, 6, 6, 7, 8, 9, 10 };
        int[] endNodes = { 11, 12, 1, 3, 5, 2,  4, 6, 7, 8,  9, 10, 7, 8,  9,  10, 7,  8,
                           9,  10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8,  9, 10, 13, 13, 13, 13 };
        int[] capacities = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                             1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        int[] unitCosts = { 0,  0,   0,  0,   0,  0,   0,  0,   90, 76, 75, 70, 35,  85, 55, 65, 125, 95,
                            90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0,  0,  0,   0 };

        int source = 0;
        int sink = 13;
        int tasks = 4;
        // Define an array of supplies at each node.
        int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };

        // 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("Total cost: " + minCostFlow.OptimalCost());
            Console.WriteLine("");
            for (int i = 0; i < minCostFlow.NumArcs(); ++i)
            {
                // Can ignore arcs leading out of source or into sink.
                if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 &&
                    minCostFlow.Head(i) != sink)
                {
                    // Arcs in the solution have a flow value of 1. Their start and end nodes
                    // give an assignment of worker to task.
                    if (minCostFlow.Flow(i) > 0)
                    {
                        Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
                                          " Cost: " + minCostFlow.UnitCost(i));
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("Solving the min cost flow problem failed.");
            Console.WriteLine("Solver status: " + status);
        }
    }
}