ন্যূনতম খরচ প্রবাহ

সর্বাধিক প্রবাহের সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত হল ন্যূনতম খরচ ( ন্যূনতম খরচ ) প্রবাহের সমস্যা, যেখানে গ্রাফের প্রতিটি আর্কের এটি জুড়ে উপাদান পরিবহনের জন্য একটি ইউনিট খরচ রয়েছে। সমস্যা হল সর্বনিম্ন মোট খরচ সহ একটি প্রবাহ খুঁজে পাওয়া।

ন্যূনতম খরচ প্রবাহের সমস্যাটিতেও বিশেষ নোড রয়েছে, যাকে সরবরাহ নোড বা চাহিদা নোড বলা হয়, যা সর্বাধিক প্রবাহের সমস্যায় উত্স এবং ডুবে যায়। উপাদান সরবরাহ নোড থেকে চাহিদা নোড পরিবহন করা হয়.

• একটি সরবরাহ নোডে , একটি ধনাত্মক পরিমাণ — সরবরাহ — প্রবাহে যোগ করা হয়। একটি সরবরাহ সেই নোডে উত্পাদন প্রতিনিধিত্ব করতে পারে, উদাহরণস্বরূপ।
• একটি চাহিদা নোডে , একটি ঋণাত্মক পরিমাণ — চাহিদা — প্রবাহ থেকে সরিয়ে নেওয়া হয়। একটি চাহিদা সেই নোডে খরচ প্রতিনিধিত্ব করতে পারে, উদাহরণস্বরূপ।

সুবিধার জন্য, আমরা ধরে নেব যে সরবরাহ বা চাহিদা নোড ছাড়া অন্য সব নোডের সরবরাহ (এবং চাহিদা) নেই।

ন্যূনতম খরচ প্রবাহের সমস্যার জন্য, আমাদের কাছে নিম্নলিখিত প্রবাহ সংরক্ষণের নিয়ম রয়েছে, যা সরবরাহ এবং চাহিদাগুলিকে বিবেচনা করে:

দ্রষ্টব্য: প্রতিটি নোডে, নোড থেকে বেরিয়ে আসা মোট প্রবাহ বিয়োগ করে নোডে যাওয়ার মোট প্রবাহ সেই নোডে সরবরাহের (বা চাহিদা) সমান।

নীচের গ্রাফটি একটি ন্যূনতম খরচ প্রবাহ সমস্যা দেখায়। আর্কগুলি সংখ্যার জোড়া দিয়ে লেবেলযুক্ত: প্রথম সংখ্যাটি ক্ষমতা এবং দ্বিতীয় সংখ্যাটি ব্যয়। নোডের পাশের বন্ধনীতে থাকা সংখ্যাগুলি সরবরাহ বা চাহিদার প্রতিনিধিত্ব করে। নোড 0 হল সাপ্লাই 20 সহ একটি সাপ্লাই নোড, যখন নোড 3 এবং 4 হল ডিমান্ড নোড, চাহিদা -5 এবং -15 সহ।

লাইব্রেরি আমদানি করুন

নিম্নলিখিত কোড প্রয়োজনীয় লাইব্রেরি আমদানি করে।

পাইথন

import numpy as np

from ortools.graph.python import min_cost_flow

সি++

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

সমাধানকারী ঘোষণা করুন

সমস্যা সমাধানের জন্য, আমরা SimpleMinCostFlow সমাধানকারী ব্যবহার করি।

পাইথন

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

সি++

// 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 four parallel arrays: sources, destinations, capacities,
# and unit costs between each pair. For instance, the arc from node 0
# to node 1 has a capacity of 15.
start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4])
end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2])
capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5])
unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3])

# Define an array of supplies at each node.
supplies = [20, 0, 0, -5, -15]

সি++

// Define four parallel arrays: sources, destinations, capacities,
// and unit costs between each pair. For instance, the arc from node 0
// to node 1 has a capacity of 15.
std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3};

// Define an array of supplies at each node.
std::vector<int64_t> supplies = {20, 0, 0, -5, -15};

জাভা

// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 15.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4};
int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2};
int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5};
int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3};

// Define an array of supplies at each node.
int[] supplies = new int[] {20, 0, 0, -5, -15};

সি#

// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 15.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 };
int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };

// Define an array of supplies at each node.
int[] supplies = { 20, 0, 0, -5, -15 };

আর্কস যোগ করুন

প্রতিটি স্টার্ট নোড এবং শেষ নোডের জন্য, আমরা AddArcWithCapacityAndUnitCost পদ্ধতিটি ব্যবহার করে প্রদত্ত ক্ষমতা এবং ইউনিট খরচ সহ স্টার্ট নোড থেকে শেষ নোড পর্যন্ত একটি চাপ তৈরি করি।

সমাধানকারীর SetNodeSupply পদ্ধতি নোডগুলির জন্য সরবরাহের ভেক্টর তৈরি করে।

পাইথন

# Add arcs, capacities and costs in bulk using numpy.
all_arcs = smcf.add_arcs_with_capacity_and_unit_cost(
    start_nodes, end_nodes, capacities, unit_costs
)

# Add supply for each nodes.
smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)

সি++

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

সমাধানকারীকে আহ্বান করুন

এখন সমস্ত আর্ক সংজ্ঞায়িত করা হয়েছে, যা বাকি আছে তা হল সমাধানকারীকে আহ্বান করা এবং ফলাফলগুলি প্রদর্শন করা। আমরা Solve() পদ্ধতি ব্যবহার করি।

পাইথন

# Find the min cost flow.
status = smcf.solve()

সি++

// 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("There was an issue with the min cost flow input.")
    print(f"Status: {status}")
    exit(1)
print(f"Minimum cost: {smcf.optimal_cost()}")
print("")
print(" Arc    Flow / Capacity Cost")
solution_flows = smcf.flows(all_arcs)
costs = solution_flows * unit_costs
for arc, flow, cost in zip(all_arcs, solution_flows, costs):
    print(
        f"{smcf.tail(arc):1} -> {smcf.head(arc)}  {flow:3}  / {smcf.capacity(arc):3}       {cost}"
    )

সি++

if (status == MinCostFlow::OPTIMAL) {
  LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost();
  LOG(INFO) << "";
  LOG(INFO) << " Arc   Flow / Capacity  Cost";
  for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
    int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i);
    LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i)
              << "  " << min_cost_flow.Flow(i) << "  / "
              << min_cost_flow.Capacity(i) << "       " << cost;
  }
} else {
  LOG(INFO) << "Solving the min cost flow problem failed. Solver status: "
            << status;
}

জাভা

if (status == MinCostFlow.Status.OPTIMAL) {
  System.out.println("Minimum cost: " + minCostFlow.getOptimalCost());
  System.out.println();
  System.out.println(" Edge   Flow / Capacity  Cost");
  for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
    long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i);
    System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + "  "
        + minCostFlow.getFlow(i) + "  / " + minCostFlow.getCapacity(i) + "       " + cost);
  }
} else {
  System.out.println("Solving the min cost flow problem failed.");
  System.out.println("Solver status: " + status);
}

সি#

if (status == MinCostFlow.Status.OPTIMAL)
{
    Console.WriteLine("Minimum cost: " + minCostFlow.OptimalCost());
    Console.WriteLine("");
    Console.WriteLine(" Edge   Flow / Capacity  Cost");
    for (int i = 0; i < minCostFlow.NumArcs(); ++i)
    {
        long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
        Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + "  " +
                          string.Format("{0,3}", minCostFlow.Flow(i)) + "  / " +
                          string.Format("{0,3}", minCostFlow.Capacity(i)) + "       " +
                          string.Format("{0,3}", cost));
    }
}
else
{
    Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status);
}

এখানে পাইথন প্রোগ্রামের আউটপুট:

Minimum cost: 150

  Arc    Flow / Capacity  Cost
0 -> 1    12  /  15        48
0 -> 2     8  /   8        32
1 -> 2     8  /  20        16
1 -> 3     4  /   4         8
1 -> 4     0  /  10         0
2 -> 3    12  /  15        12
2 -> 4     4  /   4        12
3 -> 4    11  /  20        22
4 -> 2     0  /   5         0

সম্পূর্ণ প্রোগ্রাম

এটি সব একসাথে করা, এখানে সম্পূর্ণ প্রোগ্রাম আছে.

পাইথন

"""From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1."""
import numpy as np

from ortools.graph.python import min_cost_flow


def main():
    """MinCostFlow simple interface example."""
    # Instantiate a SimpleMinCostFlow solver.
    smcf = min_cost_flow.SimpleMinCostFlow()

    # Define four parallel arrays: sources, destinations, capacities,
    # and unit costs between each pair. For instance, the arc from node 0
    # to node 1 has a capacity of 15.
    start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4])
    end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2])
    capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5])
    unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3])

    # Define an array of supplies at each node.
    supplies = [20, 0, 0, -5, -15]

    # Add arcs, capacities and costs in bulk using numpy.
    all_arcs = smcf.add_arcs_with_capacity_and_unit_cost(
        start_nodes, end_nodes, capacities, unit_costs
    )

    # Add supply for each nodes.
    smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)

    # Find the min cost flow.
    status = smcf.solve()

    if status != smcf.OPTIMAL:
        print("There was an issue with the min cost flow input.")
        print(f"Status: {status}")
        exit(1)
    print(f"Minimum cost: {smcf.optimal_cost()}")
    print("")
    print(" Arc    Flow / Capacity Cost")
    solution_flows = smcf.flows(all_arcs)
    costs = solution_flows * unit_costs
    for arc, flow, cost in zip(all_arcs, solution_flows, costs):
        print(
            f"{smcf.tail(arc):1} -> {smcf.head(arc)}  {flow:3}  / {smcf.capacity(arc):3}       {cost}"
        )


if __name__ == "__main__":
    main()

সি++

// From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1
#include <cstdint>
#include <vector>

#include "ortools/graph/min_cost_flow.h"

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

  // Define four parallel arrays: sources, destinations, capacities,
  // and unit costs between each pair. For instance, the arc from node 0
  // to node 1 has a capacity of 15.
  std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
  std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
  std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
  std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3};

  // Define an array of supplies at each node.
  std::vector<int64_t> supplies = {20, 0, 0, -5, -15};

  // Add each arc.
  for (int i = 0; i < start_nodes.size(); ++i) {
    int arc = min_cost_flow.AddArcWithCapacityAndUnitCost(
        start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
    if (arc != i) LOG(FATAL) << "Internal error";
  }

  // Add node supplies.
  for (int i = 0; i < supplies.size(); ++i) {
    min_cost_flow.SetNodeSupply(i, supplies[i]);
  }

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

  if (status == MinCostFlow::OPTIMAL) {
    LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost();
    LOG(INFO) << "";
    LOG(INFO) << " Arc   Flow / Capacity  Cost";
    for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
      int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i);
      LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i)
                << "  " << min_cost_flow.Flow(i) << "  / "
                << min_cost_flow.Capacity(i) << "       " << cost;
    }
  } else {
    LOG(INFO) << "Solving the min cost flow problem failed. Solver status: "
              << status;
  }
}

}  // namespace operations_research

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

জাভা

// From Bradley, Hax, and Maganti, 'Applied Mathematical Programming', figure 8.1.
package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MinCostFlow;
import com.google.ortools.graph.MinCostFlowBase;

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

    // Define four parallel arrays: sources, destinations, capacities, and unit costs
    // between each pair. For instance, the arc from node 0 to node 1 has a
    // capacity of 15.
    // Problem taken From Taha's 'Introduction to Operations Research',
    // example 6.4-2.
    int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4};
    int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2};
    int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5};
    int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3};

    // Define an array of supplies at each node.
    int[] supplies = new int[] {20, 0, 0, -5, -15};

    // Add each arc.
    for (int i = 0; i < startNodes.length; ++i) {
      int arc = minCostFlow.addArcWithCapacityAndUnitCost(
          startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
      if (arc != i) {
        throw new Exception("Internal error");
      }
    }

    // Add node supplies.
    for (int i = 0; i < supplies.length; ++i) {
      minCostFlow.setNodeSupply(i, supplies[i]);
    }

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

    if (status == MinCostFlow.Status.OPTIMAL) {
      System.out.println("Minimum cost: " + minCostFlow.getOptimalCost());
      System.out.println();
      System.out.println(" Edge   Flow / Capacity  Cost");
      for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
        long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i);
        System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + "  "
            + minCostFlow.getFlow(i) + "  / " + minCostFlow.getCapacity(i) + "       " + cost);
      }
    } else {
      System.out.println("Solving the min cost flow problem failed.");
      System.out.println("Solver status: " + status);
    }
  }

  private SimpleMinCostFlowProgram() {}
}

সি#

// From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1.
using System;
using Google.OrTools.Graph;

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

        // Define four parallel arrays: sources, destinations, capacities, and unit costs
        // between each pair. For instance, the arc from node 0 to node 1 has a
        // capacity of 15.
        // Problem taken From Taha's 'Introduction to Operations Research',
        // example 6.4-2.
        int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
        int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
        int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 };
        int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };

        // Define an array of supplies at each node.
        int[] supplies = { 20, 0, 0, -5, -15 };

        // Add each arc.
        for (int i = 0; i < startNodes.Length; ++i)
        {
            int arc =
                minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
            if (arc != i)
                throw new Exception("Internal error");
        }

        // Add node supplies.
        for (int i = 0; i < supplies.Length; ++i)
        {
            minCostFlow.SetNodeSupply(i, supplies[i]);
        }

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

        if (status == MinCostFlow.Status.OPTIMAL)
        {
            Console.WriteLine("Minimum cost: " + minCostFlow.OptimalCost());
            Console.WriteLine("");
            Console.WriteLine(" Edge   Flow / Capacity  Cost");
            for (int i = 0; i < minCostFlow.NumArcs(); ++i)
            {
                long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
                Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + "  " +
                                  string.Format("{0,3}", minCostFlow.Flow(i)) + "  / " +
                                  string.Format("{0,3}", minCostFlow.Capacity(i)) + "       " +
                                  string.Format("{0,3}", cost));
            }
        }
        else
        {
            Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status);
        }
    }
}