تخصیص به عنوان یک مشکل جریان حداقل هزینه

شما می توانید از حل کننده جریان حداقل هزینه برای حل موارد خاص مشکل انتساب استفاده کنید.

در واقع، حداقل جریان هزینه اغلب می تواند یک راه حل را سریعتر از حل کننده MIP یا CP-SAT برگرداند. با این حال، MIP و CP-SAT می توانند کلاس بزرگتری از مشکلات را نسبت به جریان حداقل هزینه حل کنند، بنابراین در بیشتر موارد MIP یا CP-SAT بهترین انتخاب هستند.

بخش‌های زیر برنامه‌های پایتون را ارائه می‌کنند که با استفاده از حل‌کننده جریان هزینه حداقل، مسائل تخصیص زیر را حل می‌کنند:

• یک نمونه تخصیص خطی حداقلی
• مشکل تکلیف با تیم های کارگری .

مثال تخصیص خطی

این بخش نحوه حل مثالی را که در بخش حل تکلیف خطی توضیح داده شده است، به عنوان یک مسئله جریان هزینه حداقل نشان می دهد.

کتابخانه ها را وارد کنید

کد زیر کتابخانه مورد نیاز را وارد می کند.

پایتون

from ortools.graph.python import min_cost_flow

C++

#include <cstdint>
#include <vector>

#include "ortools/graph/min_cost_flow.h"

جاوا

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

سی شارپ

using System;
using Google.OrTools.Graph;

حل کننده را اعلام کنید

کد زیر حل کننده جریان حداقل هزینه را ایجاد می کند.

پایتون

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

C++

// Instantiate a SimpleMinCostFlow solver.
SimpleMinCostFlow min_cost_flow;

جاوا

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

سی شارپ

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

داده ها را ایجاد کنید

نمودار جریان برای مسئله شامل نمودار دو بخشی برای ماتریس هزینه است (برای مثال کمی متفاوت به نمای کلی تخصیص مراجعه کنید)، با یک منبع و سینک اضافه شده است.

توجه: شماره‌گذاری کارگران و وظایف کمی متفاوت از بخش Linear Assignment Solver است، زیرا حل‌کننده جریان هزینه حداقل نیاز دارد که تمام گره‌ها در نمودار به طور مشخص شماره‌گذاری شوند.

داده ها شامل چهار آرایه زیر است که مربوط به گره های شروع، گره های پایانی، ظرفیت ها و هزینه های مشکل است. طول هر آرایه تعداد کمان های نمودار است.

پایتون

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

جاوا

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

سی شارپ

// 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 داشته باشند.

در مرحله بعد، شرایط flow-in-squals-flow-out جریان خروجی هر کارگر را مجبور می‌کند تا 1 باشد. در صورت امکان، حل‌کننده آن جریان را در طول کمان حداقل هزینه که از هر کارگر خارج می‌شود هدایت می‌کند. با این حال، حل‌کننده نمی‌تواند جریان‌ها را از دو کارگر مختلف به یک کار واحد هدایت کند. اگر چنین بود، یک جریان ترکیبی 2 در آن وظیفه وجود خواهد داشت که نمی‌توان آن را در سراسر قوس منفرد با ظرفیت 1 از وظیفه به سینک فرستاد. این به این معنی است که حل کننده فقط می تواند یک کار را به یک کارگر اختصاص دهد، همانطور که در مسئله انتساب لازم است.

در نهایت، شرایط flow-in-equals-flow-out هر وظیفه را مجبور می کند که خروجی 1 داشته باشد، بنابراین هر کار توسط تعدادی کارگر انجام می شود.

نمودار و محدودیت ها را ایجاد کنید

کد زیر گراف و محدودیت ها را ایجاد می کند.

پایتون

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

جاوا

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

سی شارپ

// 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 minimum cost flow between node 0 and node 10.
status = smcf.solve()

C++

// Find the min cost flow.
int status = min_cost_flow.Solve();

جاوا

// Find the min cost flow.
MinCostFlowBase.Status status = minCostFlow.solve();

سی شارپ

// Find the min cost flow.
MinCostFlow.Status status = minCostFlow.Solve();

راه‌حل شامل کمان‌هایی بین کارگران و وظایفی است که توسط حل‌کننده جریان 1 به آنها اختصاص داده می‌شود. (قوس های متصل به منبع یا سینک بخشی از راه حل نیستند.)

برنامه هر کمان را بررسی می کند تا ببیند آیا جریان 1 دارد یا خیر، و اگر چنین است، Tail (گره شروع) و Head (گره انتهایی) کمان را چاپ می کند که مربوط به یک کارگر و وظیفه در تکلیف است.

خروجی برنامه

پایتون

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

جاوا

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

سی شارپ

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 ثانیه.

کل برنامه

کل برنامه در زیر نشان داده شده است.

پایتون

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

جاوا

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() {}
}

سی شارپ

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 برای این مشکل ، به تکالیف با تیم‌های کارگران مراجعه کنید.

بخش‌های زیر برنامه‌ای را توضیح می‌دهند که با استفاده از حل‌کننده جریان هزینه حداقل مشکل را حل می‌کند.

کتابخانه ها را وارد کنید

کد زیر کتابخانه مورد نیاز را وارد می کند.

پایتون

from ortools.graph.python import min_cost_flow

C++

#include <cstdint>
#include <vector>

#include "ortools/graph/min_cost_flow.h"

جاوا

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

سی شارپ

using System;
using Google.OrTools.Graph;

حل کننده را اعلام کنید

کد زیر حل کننده جریان حداقل هزینه را ایجاد می کند.

پایتون

smcf = min_cost_flow.SimpleMinCostFlow()

C++

// Instantiate a SimpleMinCostFlow solver.
SimpleMinCostFlow min_cost_flow;

جاوا

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

سی شارپ

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

داده ها را ایجاد کنید

کد زیر داده های برنامه را ایجاد می کند.

پایتون

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

جاوا

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

سی شارپ

// 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 مطابقت دارند. تیم A متشکل از کارگران 1، 3، و 5، و تیم B شامل کارگران 2، 4، و 6 است. وظایف 7 - 10 شماره گذاری شده اند.

دو گره جدید 11 و 12 بین منبع و کارگران وجود دارد. گره 11 به گره های تیم A و گره 12 به گره های تیم B با کمان هایی با ظرفیت 1 متصل است. نمودار زیر فقط گره ها و کمان ها را از منبع به کارگران نشان می دهد.

نکته کلیدی برای متعادل کردن حجم کار این است که منبع 0 با کمان هایی با ظرفیت 2 به گره های 11 و 12 متصل می شود. این بدان معنی است که گره های 11 و 12 (و ​​بنابراین تیم های A و B) می توانند حداکثر جریان 2 داشته باشند. در نتیجه ، هر تیم می تواند حداکثر دو کار را انجام دهد.

محدودیت ها را ایجاد کنید

پایتون

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

جاوا

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

سی شارپ

// 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 minimum cost flow between node 0 and node 10.
status = smcf.solve()

C++

// Find the min cost flow.
int status = min_cost_flow.Solve();

جاوا

// Find the min cost flow.
MinCostFlowBase.Status status = minCostFlow.solve();

سی شارپ

// Find the min cost flow.
MinCostFlow.Status status = minCostFlow.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}")

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

جاوا

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

سی شارپ

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

به تیم A وظایف 9 و 10 اختصاص داده شده است، در حالی که به تیم B وظایف 7 و 8 اختصاص داده شده است.

توجه داشته باشید که حل کننده جریان حداقل هزینه برای این مشکل سریعتر از حل کننده MIP است که حدود 0.006 ثانیه طول می کشد.

کل برنامه

کل برنامه در زیر نشان داده شده است.

پایتون

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

جاوا

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() {}
}

سی شارپ

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