التعيين كمشكلة الحد الأدنى من التكلفة

يمكنك استخدام أداة حل تدفق الحد الأدنى للتكلفة لحل الحالات الخاصة مشكلة في التعيين.

في الواقع، يمكن أن يعرض تدفق الحد الأدنى من التكلفة غالبًا حلاً أسرع من MIP أو أداة حلّ CP-SAT ومع ذلك، يمكن أن يحل MIP وCP-SAT فئة أكبر من المشكلات وتدفق الحد الأدنى من التكلفة، لذلك في معظم الحالات، يعد MIP أو CP-SAT أفضل الخيارات.

توضح الفقرات التالية برامج بايثون التي تحل ما يلي: مسائل التعيين باستخدام أداة حل تدفق التكلفة الدنيا:

• تمثّل هذه السمة مثالاً بسيطًا على التعيين الخطي.
• مشكلة في المهمة مع فِرق من العمال.

مثال على التعيين الخطي

يعرض هذا القسم كيفية حلّ المثال الموضَّح في القسم. أداة حلّ المهام الخطية، كدقيقة مشكلة تدفق التكلفة.

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

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

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;

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

تُنشئ التعليمة البرمجية التالية أداة حل الحد الأدنى لتدفق التكلفة.

Python

# Instantiate a SimpleMinCostFlow solver.
smcf = min_cost_flow.SimpleMinCostFlow()

C++‎

// Instantiate a SimpleMinCostFlow solver.
SimpleMinCostFlow min_cost_flow;

Java

// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();

#C

// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();

إنشاء البيانات

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

ملاحظة: يختلف ترقيم العمال والمهام قليلاً عنه في قسم أداة حلّ المهام الخطية وذلك لأن أداة حل الحد الأدنى للتكلفة تتطلب ترقيم جميع النقاط في الرسم البياني بوضوح.

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

Python

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

لتوضيح كيفية إعداد البيانات، يتم تقسيم كل صفيف إلى ثلاثة المصفوفات الفرعية:

• تتجاوب الصفيفة الأولى مع الأقواس التي تخرج من المصدر.
• تتجاوب الصفيفة الثانية مع الأقواس بين العاملين والمهام. بالنسبة إلى costs، هذه السمة هي مصفوفة التكلفة (تستخدمه أداة حل التعيين الخطي)، مسطّحة في متجه.
• وتتجاوب الصفيفة الثالثة مع الأقواس التي تؤدي إلى الحوض.

تشمل البيانات أيضًا الخط المتجه supplies، الذي يعطي للعرض في كل العقدة.

كيف تمثل مشكلة تدفق الحد الأدنى للتكلفة مشكلة في المهمة

كيف تمثل مشكلة تدفق الحد الأدنى للتكلفة أعلاه مشكلة التعيين؟ أَوَّلًا، بما أن سعة كل قوس تساوي 1، فإن توفير 4 عند المصدر يفرض على كل قوس من الأقواس الأربعة التي تؤدي إلى العمال للحصول على تدفق 1.

بعد ذلك، تفرض شرط التدفق من حيث يساوي مساوية التدفق تدفقًا من كل عامل على 1. وإذا أمكن، ستعمل أداة الحلّ على توجيه هذا التدفق إلى الحد الأدنى للتكلفة قوس يخرج من كل عامل. ومع ذلك، لا يمكن للحل توجيه التدفقات من عاملين مختلفين في مهمة واحدة. إذا حدث ذلك، فسيكون هناك مجتمع تدفق 2 في تلك المهمة، والذي لا يمكن إرساله عبر القوس الفردي مع السعة 1 من المهمة إلى الحوض. وهذا يعني أن أداة الحلّ لا يمكنها إسناد مهمة إلا إلى عامل واحد، المطلوبة بسبب مشكلة المهمة.

أخيرًا، يجبر شرط التدفق من خلال مساواة "التدفق" كل مهمة على أن يكون لها تدفق 1، لذلك يتم تنفيذ كل مهمة من قبل عامل ما.

إنشاء الرسم البياني والقيود

تُنشئ التعليمة البرمجية التالية الرسم البياني والقيود.

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

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

يستدعي الرمز التالي أداة الحلّ ويعرض الحل.

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

يتكون الحل من الأقواس بين العمال والمهام التي يتم إسنادها التدفّق 1 بواسطة أداة الحلّ. (الأقواس المتصلة بالمصدر أو الحوض ليست جزءًا من الحل).

يفحص البرنامج كل قوس لمعرفة ما إذا كان يحتوي على التدفق 1، وفي هذه الحالة، يطبع Tail (عقدة البداية) وHead (عقدة النهاية) من القوس، والتي تتوافق مع عامل ومهمة في المهمة.

ناتج البرنامج

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

في ما يلي مخرجات البرنامج.

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

والنتيجة هي نفسها الخاصة أداة حل المهام الخطية (باستثناء الأدوات ترقيم العمال والتكاليف). أداة حلّ المهام الخطية أسرع قليلاً من الحد الأدنى لتدفق التكلفة - 0.000147 ثانية مقابل 0.000458 ثانية.

البرنامج بأكمله

يمكنك الاطّلاع أدناه على البرنامج بالكامل.

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

المهمة الدراسية مع فِرق العمل

يقدم هذا القسم مشكلة مهمة أكثر عمومية. في هذه المسألة، ستة يتم تقسيم العمال إلى فريقين. تكمن المشكلة في تعيين أربع مهام العاملين بحيث يتم موازنة عبء العمل بالتساوي بين الفرق - بحيث بحيث يقوم كل فريق بتنفيذ مهمتين.

للحصول على حل MIP لهذه المشكلة، راجع المهام الدراسية مع فِرق العمال:

تصف الأقسام التالية برنامجًا يحل المشكلة باستخدام أداة حل تدفق التكلفة.

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

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

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;

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

تُنشئ التعليمة البرمجية التالية أداة حل الحد الأدنى لتدفق التكلفة.

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

إنشاء البيانات

ينشئ الرمز التالي البيانات للبرنامج.

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

ويتجاوب العاملون مع العقد 1 - 6. يتكون الفريق "أ" من العاملين 1 و3 و5، ويتكون الفريق ب من العاملين 2 و4 و6. ترقيم المهام من 7 إلى 10.

هناك عُقدتان جديدتان، 11 و12، بين المصدر والعاملين. العقدة 11 هي متصلة بالعُقد الخاصة بالفريق A، وتتصل العقدة 12 بالعُقد الخاصة الفريق ب، مع أقواس ذات القدرة 1. يعرض الرسم البياني أدناه العُقد والأقواس من المصدر إلى العاملين.

مفتاح موازنة عبء العمل هو أن المصدر 0 متصل بالعُقد 11 و12 على أقواس السعة 2. وهذا يعني أن العقد 11 و12 (وبالتالي الفريقين A وB) يمكن أن يكون لها أقصى تدفق 2. نتيجة لذلك، يمكن لكل فريق أداء اثنتين على الأكثر من المهام.

وضع القيود

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

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

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

ناتج البرنامج

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

يظهر في ما يلي نتائج البرنامج.

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

تم تعيين المهمتين 9 و10 للفريق "أ"، بينما تم تعيين المهمتين 7 و8 للفريق "ب".

تجدر الإشارة إلى أن أداة حل الحدّ الأدنى للتكلفة أسرع لهذه المسألة من أداة حلّ MIP، التي يستغرق حوالي 0.006 ثانية.

البرنامج بأكمله

يمكنك الاطّلاع أدناه على البرنامج بالكامل.

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