Penetapan sebagai Masalah Alur Biaya Minimum

Anda dapat menggunakan pemecah aliran biaya min untuk menyelesaikan kasus khusus masalah tugas.

Faktanya, aliran biaya minimum sering kali dapat memberikan solusi lebih cepat daripada MIP atau Pemecah masalah CP-SAT. Namun, MIP dan CP-SAT dapat memecahkan kelas masalah yang lebih besar daripada aliran biaya min, jadi dalam kebanyakan kasus MIP atau CP-SAT adalah pilihan terbaik.

Bagian berikut ini menyajikan program Python yang memecahkan masalah berikut soal tugas menggunakan pemecah masalah aliran biaya min:

Contoh penetapan linear

Bagian ini menunjukkan cara menyelesaikan contoh, yang dijelaskan di bagian Pemecah Tugas Linear, sebagai min masalah aliran biaya.

Mengimpor library

Kode berikut akan mengimpor library yang diperlukan.

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;

Mendeklarasikan pemecah

Kode berikut membuat pemecah aliran biaya minimum.

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

Membuat data

Diagram alir untuk masalah tersebut terdiri dari grafik bipartit untuk biaya matriks (lihat ringkasan tugas selama contoh yang berbeda), dengan menambahkan sumber dan sink.

grafik alir biaya jaringan

Data berisi empat {i>array<i} berikut, sesuai dengan {i>node<i} awal, {i>node<i} akhir, kapasitas, dan biaya untuk masalah. Panjang setiap {i>array<i} adalah jumlah busur dalam grafik.

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

Untuk memperjelas cara data disiapkan, setiap array dibagi menjadi tiga sub-array:

  • Array pertama berhubungan dengan busur yang mengarah keluar dari sumber.
  • Array kedua sesuai dengan busur antara pekerja dan tugas. Untuk costs, ini hanyalah matriks biaya (digunakan oleh pemecah tugas linear), diratakan menjadi vektor.
  • Array ketiga sesuai dengan busur yang mengarah ke sink.

Data ini juga menyertakan vektor supplies, yang memberikan pasokan di setiap {i>node<i}.

Bagaimana masalah alur biaya min mewakili masalah tugas

Bagaimana masalah alur biaya min di atas mewakili masalah penugasan? Pertama, karena kapasitas setiap busur adalah 1, pasokan 4 pada gaya sumber masing-masing dari empat busur yang mengarah ke pekerja memiliki aliran 1.

Selanjutnya, kondisi flow-in-sama-flow-out memaksa aliran keluar dari setiap pekerja menjadi 1. Jika memungkinkan, pemecah masalah akan mengarahkan alur tersebut pada biaya minimum busur yang mengarah dari setiap pekerja. Namun, pemecah masalah tidak dapat mengarahkan alur dari dua pekerja yang berbeda pada satu tugas. Jika ya, akan ada model alur 2 pada tugas itu, yang tidak bisa dikirim melalui busur tunggal dengan kapasitas 1 dari tugas ke sink. Ini berarti pemecah masalah hanya dapat memberikan tugas ke satu pekerja, seperti yang diperlukan oleh soal tugas.

Terakhir, kondisi {i>flow-in-equals-flow-out<i} memaksa setiap tugas untuk memiliki aliran keluar 1, jadi setiap tugas dilakukan oleh beberapa pekerja.

Membuat grafik dan batasan

Kode berikut membuat grafik dan batasan.

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

Memanggil pemecah masalah

Kode berikut memanggil pemecah dan menampilkan solusinya.

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

Solusi ini terdiri dari alur antara pekerja dan tugas yang diberikan aliran 1 oleh pemecah masalah. (Arc yang terhubung ke sumber atau sink bukan bagian dari solusinya.)

Program ini memeriksa setiap busur untuk melihat apakah ia memiliki flow 1, dan jika demikian, mencetak Tail (node awal) dan Head (node akhir) busur, yang sesuai dengan pekerja dan tugas dalam penugasan.

Output program

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

Berikut ini adalah output program.

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

Hasilnya sama dengan untuk pemecah masalah linear (kecuali untuk penomoran pekerja dan biaya). Pemecah soal tugas linear sedikit lebih cepat dari aliran biaya min - 0,000147 detik versus 0,000458 detik.

Seluruh program

Seluruh program ditampilkan di bawah ini.

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

Penugasan dengan tim pekerja

Bagian ini menyajikan masalah penugasan yang lebih umum. Dalam soal ini, enam pekerja dibagi menjadi dua tim. Masalahnya adalah menetapkan empat tugas ke karyawan sehingga beban kerja di antara tim harus sama rata — yang sehingga setiap tim melakukan dua tugas.

Untuk solusi pemecah MIP masalah ini, lihat Penugasan dengan Tim Pekerja.

Bagian berikut ini menjelaskan program yang memecahkan masalah dengan menggunakan pemecah aliran biaya.

Mengimpor library

Kode berikut akan mengimpor library yang diperlukan.

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;

Mendeklarasikan pemecah

Kode berikut membuat pemecah aliran biaya minimum.

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

Membuat data

Kode berikut membuat data untuk program.

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

Pekerja sesuai dengan node 1 - 6. Tim A terdiri dari pekerja 1, 3, dan 5. Sedangkan tim B terdiri dari pekerja 2, 4, dan 6. Tugas diberi nomor 7 - 10.

Ada dua node baru, 11 dan 12, antara sumber dan worker. Node 11 adalah terhubung ke {i>node<i} untuk tim A, dan {i>Node<i} 12 terhubung ke {i>node<i} untuk tim A, tim B, dengan busur kapasitas 1. Grafik di bawah hanya menunjukkan node dan busur dari sumber ke pekerja.

grafik alir biaya jaringan

Kunci untuk menyeimbangkan beban kerja adalah sumber 0 terhubung ke node 11 dan 12 dengan busur kapasitas 2. Ini berarti bahwa {i>node<i} 11 dan 12 (dan karenanya tim A dan B) dapat memiliki aliran maksimum 2. Hasilnya, setiap tim dapat melakukan maksimal dua tugas.

Membuat batasan

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

Memanggil pemecah masalah

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

Output program

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

Berikut ini adalah output program.

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

Tim A diberi tugas 9 dan 10, sementara tim B diberi tugas 7 dan 8.

Perhatikan bahwa pemecah aliran biaya minimum lebih cepat untuk masalah ini daripada pemecah masalah MIP, yang membutuhkan waktu sekitar 0,006 detik.

Seluruh program

Seluruh program ditampilkan di bawah ini.

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