इस पेज का अनुवाद Cloud Translation API से किया गया है.

लीनियर सम असाइनमेंट सॉल्वर

इस सेक्शन में, लीनियर सम असाइनमेंट सॉल्वर के बारे में बताया गया है. यह एक खास यह हल करने में आपकी मदद करने के लिए, MIP या CP-SAT सॉल्वर. हालांकि, MIP और CP-SAT सॉल्वर और इसलिए हैं, क्योंकि ज़्यादातर मामलों में ये एक बेहतरीन विकल्प होते हैं.

कॉस्ट मैट्रिक्स

कर्मचारियों और टास्क पर होने वाला खर्च, नीचे दी गई टेबल में दिया गया है.

वर्कर	टास्क 0	कार्य 1	कार्य 2	कार्य 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

नीचे दिए गए सेक्शन में एक Python प्रोग्राम के बारे में बताया गया है, जो किसी असाइनमेंट को हल करता है लीनियर सम असाइनमेंट सॉल्वर का इस्तेमाल करके सवाल हल करें.

लाइब्रेरी इंपोर्ट करें

ज़रूरी लाइब्रेरी इंपोर्ट करने वाला कोड नीचे दिखाया गया है.

Python

import numpy as np

from ortools.graph.python import linear_sum_assignment

C++

#include "ortools/graph/assignment.h"

#include <cstdint>
#include <numeric>
#include <string>
#include <vector>

Java

import com.google.ortools.Loader;
import com.google.ortools.graph.LinearSumAssignment;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Graph;

डेटा तय करना

यहां दिया गया कोड, प्रोग्राम के लिए डेटा बनाता है.

Python

costs = np.array(
    [
        [90, 76, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 105],
        [45, 110, 95, 115],
    ]
)

# Let's transform this into 3 parallel vectors (start_nodes, end_nodes,
# arc_costs)
end_nodes_unraveled, start_nodes_unraveled = np.meshgrid(
    np.arange(costs.shape[1]), np.arange(costs.shape[0])
)
start_nodes = start_nodes_unraveled.ravel()
end_nodes = end_nodes_unraveled.ravel()
arc_costs = costs.ravel()

C++

const int num_workers = 4;
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = 4;
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);

const std::vector<std::vector<int>> costs = {{
    {{90, 76, 75, 70}},    // Worker 0
    {{35, 85, 55, 65}},    // Worker 1
    {{125, 95, 90, 105}},  // Worker 2
    {{45, 110, 95, 115}},  // Worker 3
}};

Java

final int[][] costs = {
    {90, 76, 75, 70},
    {35, 85, 55, 65},
    {125, 95, 90, 105},
    {45, 110, 95, 115},
};
final int numWorkers = 4;
final int numTasks = 4;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
final int[] allTasks = IntStream.range(0, numTasks).toArray();

C#

int[,] costs = {
    { 90, 76, 75, 70 },
    { 35, 85, 55, 65 },
    { 125, 95, 90, 105 },
    { 45, 110, 95, 115 },
};
int numWorkers = 4;
int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int numTasks = 4;
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

कलेक्शन, लागत मैट्रिक्स है, जिसका i, j, वर्कर i की लागत है टास्क j. पंक्तियों में, चार वर्कर कर सकते हैं. साथ ही, कॉलम से जुड़े चार टास्क पूरे कर सकते हैं.

सॉल्वर बनाएं

यह प्रोग्राम लीनियर असाइनमेंट सॉल्वर, खास सॉल्वर की मदद से, असाइनमेंट के सवाल हल कर सकते हैं.

यह कोड, सॉल्वर बनाता है.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

कंस्ट्रेंट जोड़ें

यहां दिया गया कोड, सॉल्वर में लागत को जोड़ता है. इसके लिए, कर्मचारियों को लूप में चलाया जाता है और टास्क.

Python

assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)

C++

for (int w : all_workers) {
  for (int t : all_tasks) {
    if (costs[w][t]) {
      assignment.AddArcWithCost(w, t, costs[w][t]);
    }
  }
}

Java

// Add each arc.
for (int w : allWorkers) {
  for (int t : allTasks) {
    if (costs[w][t] != 0) {
      assignment.addArcWithCost(w, t, costs[w][t]);
    }
  }
}

C#

// Add each arc.
foreach (int w in allWorkers)
{
    foreach (int t in allTasks)
    {
        if (costs[w, t] != 0)
        {
            assignment.AddArcWithCost(w, t, costs[w, t]);
        }
    }
}

सॉल्वर आज़माएं

यह कोड, सॉल्वर को शुरू करता है.

Python

status = assignment.solve()

C++

SimpleLinearSumAssignment::Status status = assignment.Solve();

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

नतीजे दिखाएं

यह कोड, समाधान दिखाता है.

Python

if status == assignment.OPTIMAL:
    print(f"Total cost = {assignment.optimal_cost()}\n")
    for i in range(0, assignment.num_nodes()):
        print(
            f"Worker {i} assigned to task {assignment.right_mate(i)}."
            + f"  Cost = {assignment.assignment_cost(i)}"
        )
elif status == assignment.INFEASIBLE:
    print("No assignment is possible.")
elif status == assignment.POSSIBLE_OVERFLOW:
    print("Some input costs are too large and may cause an integer overflow.")

C++

if (status == SimpleLinearSumAssignment::OPTIMAL) {
  LOG(INFO) << "Total cost: " << assignment.OptimalCost();
  for (int worker : all_workers) {
    LOG(INFO) << "Worker " << std::to_string(worker) << " assigned to task "
              << std::to_string(assignment.RightMate(worker)) << ". Cost: "
              << std::to_string(assignment.AssignmentCost(worker)) << ".";
  }
} else {
  LOG(INFO) << "Solving the linear assignment problem failed.";
}

Java

if (status == LinearSumAssignment.Status.OPTIMAL) {
  System.out.println("Total cost: " + assignment.getOptimalCost());
  for (int worker : allWorkers) {
    System.out.println("Worker " + worker + " assigned to task "
        + assignment.getRightMate(worker) + ". Cost: " + assignment.getAssignmentCost(worker));
  }
} else {
  System.out.println("Solving the min cost flow problem failed.");
  System.out.println("Solver status: " + status);
}

C#

if (status == LinearSumAssignment.Status.OPTIMAL)
{
    Console.WriteLine($"Total cost: {assignment.OptimalCost()}.");
    foreach (int worker in allWorkers)
    {
        Console.WriteLine($"Worker {worker} assigned to task {assignment.RightMate(worker)}. " +
                          $"Cost: {assignment.AssignmentCost(worker)}.");
    }
}
else
{
    Console.WriteLine("Solving the linear assignment problem failed.");
    Console.WriteLine($"Solver status: {status}.");
}

नीचे दिया गया आउटपुट, टास्क के लिए वर्कर के सबसे बेहतर असाइनमेंट दिखाता है.

Total cost = 265
Worker 0 assigned to task 3.  Cost = 70
Worker 1 assigned to task 2.  Cost = 55
Worker 2 assigned to task 1.  Cost = 95
Worker 3 assigned to task 0.  Cost = 45
Time = 0.000147 seconds

यह ग्राफ़, ग्राफ़ में डैश वाले किनारों के रूप में हल दिखाता है. कॉन्टेंट बनाने डैश वाले किनारों के बगल में दिख रही संख्या उनकी लागत होती है. इस असाइनमेंट के लिए इंतज़ार का कुल समय, डैश वाले किनारे, जो कि 265 है.

लीनियर योग असाइनमेंट फ़्लो ग्राफ़

ग्राफ़ थ्योरी में, द्विपक्षीय ग्राफ़ में किनारों का एक सेट, जो बाईं ओर सिर्फ़ एक नोड होता है जिसे पूरी तरह मैचिंग कहा जाता है.

पूरा प्रोग्राम

यह रहा पूरा प्रोग्राम.

Python

"""Solve assignment problem using linear assignment solver."""
import numpy as np

from ortools.graph.python import linear_sum_assignment


def main():
    """Linear Sum Assignment example."""
    assignment = linear_sum_assignment.SimpleLinearSumAssignment()

    costs = np.array(
        [
            [90, 76, 75, 70],
            [35, 85, 55, 65],
            [125, 95, 90, 105],
            [45, 110, 95, 115],
        ]
    )

    # Let's transform this into 3 parallel vectors (start_nodes, end_nodes,
    # arc_costs)
    end_nodes_unraveled, start_nodes_unraveled = np.meshgrid(
        np.arange(costs.shape[1]), np.arange(costs.shape[0])
    )
    start_nodes = start_nodes_unraveled.ravel()
    end_nodes = end_nodes_unraveled.ravel()
    arc_costs = costs.ravel()

    assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)

    status = assignment.solve()

    if status == assignment.OPTIMAL:
        print(f"Total cost = {assignment.optimal_cost()}\n")
        for i in range(0, assignment.num_nodes()):
            print(
                f"Worker {i} assigned to task {assignment.right_mate(i)}."
                + f"  Cost = {assignment.assignment_cost(i)}"
            )
    elif status == assignment.INFEASIBLE:
        print("No assignment is possible.")
    elif status == assignment.POSSIBLE_OVERFLOW:
        print("Some input costs are too large and may cause an integer overflow.")


if __name__ == "__main__":
    main()

C++

#include "ortools/graph/assignment.h"

#include <cstdint>
#include <numeric>
#include <string>
#include <vector>

namespace operations_research {
// Simple Linear Sum Assignment Problem (LSAP).
void AssignmentLinearSumAssignment() {
  SimpleLinearSumAssignment assignment;

  const int num_workers = 4;
  std::vector<int> all_workers(num_workers);
  std::iota(all_workers.begin(), all_workers.end(), 0);

  const int num_tasks = 4;
  std::vector<int> all_tasks(num_tasks);
  std::iota(all_tasks.begin(), all_tasks.end(), 0);

  const std::vector<std::vector<int>> costs = {{
      {{90, 76, 75, 70}},    // Worker 0
      {{35, 85, 55, 65}},    // Worker 1
      {{125, 95, 90, 105}},  // Worker 2
      {{45, 110, 95, 115}},  // Worker 3
  }};

  for (int w : all_workers) {
    for (int t : all_tasks) {
      if (costs[w][t]) {
        assignment.AddArcWithCost(w, t, costs[w][t]);
      }
    }
  }

  SimpleLinearSumAssignment::Status status = assignment.Solve();

  if (status == SimpleLinearSumAssignment::OPTIMAL) {
    LOG(INFO) << "Total cost: " << assignment.OptimalCost();
    for (int worker : all_workers) {
      LOG(INFO) << "Worker " << std::to_string(worker) << " assigned to task "
                << std::to_string(assignment.RightMate(worker)) << ". Cost: "
                << std::to_string(assignment.AssignmentCost(worker)) << ".";
    }
  } else {
    LOG(INFO) << "Solving the linear assignment problem failed.";
  }
}

}  // namespace operations_research

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

Java

package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.LinearSumAssignment;
import java.util.stream.IntStream;

/** Minimal Linear Sum Assignment problem. */
public class AssignmentLinearSumAssignment {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    LinearSumAssignment assignment = new LinearSumAssignment();

    final int[][] costs = {
        {90, 76, 75, 70},
        {35, 85, 55, 65},
        {125, 95, 90, 105},
        {45, 110, 95, 115},
    };
    final int numWorkers = 4;
    final int numTasks = 4;

    final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
    final int[] allTasks = IntStream.range(0, numTasks).toArray();

    // Add each arc.
    for (int w : allWorkers) {
      for (int t : allTasks) {
        if (costs[w][t] != 0) {
          assignment.addArcWithCost(w, t, costs[w][t]);
        }
      }
    }

    LinearSumAssignment.Status status = assignment.solve();

    if (status == LinearSumAssignment.Status.OPTIMAL) {
      System.out.println("Total cost: " + assignment.getOptimalCost());
      for (int worker : allWorkers) {
        System.out.println("Worker " + worker + " assigned to task "
            + assignment.getRightMate(worker) + ". Cost: " + assignment.getAssignmentCost(worker));
      }
    } else {
      System.out.println("Solving the min cost flow problem failed.");
      System.out.println("Solver status: " + status);
    }
  }

  private AssignmentLinearSumAssignment() {}
}

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Graph;

public class AssignmentLinearSumAssignment
{
    static void Main()
    {
        LinearSumAssignment assignment = new LinearSumAssignment();

        int[,] costs = {
            { 90, 76, 75, 70 },
            { 35, 85, 55, 65 },
            { 125, 95, 90, 105 },
            { 45, 110, 95, 115 },
        };
        int numWorkers = 4;
        int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
        int numTasks = 4;
        int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

        // Add each arc.
        foreach (int w in allWorkers)
        {
            foreach (int t in allTasks)
            {
                if (costs[w, t] != 0)
                {
                    assignment.AddArcWithCost(w, t, costs[w, t]);
                }
            }
        }

        LinearSumAssignment.Status status = assignment.Solve();

        if (status == LinearSumAssignment.Status.OPTIMAL)
        {
            Console.WriteLine($"Total cost: {assignment.OptimalCost()}.");
            foreach (int worker in allWorkers)
            {
                Console.WriteLine($"Worker {worker} assigned to task {assignment.RightMate(worker)}. " +
                                  $"Cost: {assignment.AssignmentCost(worker)}.");
            }
        }
        else
        {
            Console.WriteLine("Solving the linear assignment problem failed.");
            Console.WriteLine($"Solver status: {status}.");
        }
    }
}

कर्मचारी के सभी टास्क न कर पाने पर मिलने वाला समाधान

पिछले उदाहरण में, हमने मान लिया था कि सभी कर्मचारी सभी काम कर सकते हैं. लेकिन हमेशा ऐसा नहीं होता - ऐसा हो सकता है कि कोई वर्कर एक या उससे ज़्यादा काम न कर पाए कई वजहों से ऐसा किया जा सकता है. हालांकि, ऊपर दिए गए प्रोग्राम को आसानी से बदला जा सकता है और यह.

उदाहरण के लिए, मान लें कि वर्कर 0, टास्क 3 को पूरा नहीं कर पा रहा है. इसलिए, ये बदलाव करें:

लागत मैट्रिक्स की 0, 3 एंट्री को स्ट्रिंग 'NA' में बदलें. (कोई भी स्ट्रिंग काम करेगी.)
```
cost = [[90, 76, 75, 'NA'],
    [35, 85, 55, 65],
    [125, 95, 90, 105],
    [45, 110, 95, 115]]
```
सॉल्वर के लिए लागत असाइन करने वाले कोड के सेक्शन में, लाइन जोड़ें if cost[worker][task] != 'NA':, जैसा कि नीचे दिखाया गया है.
```
for worker in range(0, rows):
for task in range(0, cols):
  if cost[worker][task] != 'NA':
    assignment.AddArcWithCost(worker, task, cost[worker][task])
```
जोड़ी गई लाइन ऐसे किसी किनारे को रोकती है जिसकी लागत मैट्रिक्स में 'NA' है उन्हें सॉल्वर में शामिल होने से रोका जा सकता है.

ये बदलाव करने और बदले गए कोड को चलाने के बाद, आपको ये बदलाव दिखते हैं आउटपुट:

Total cost = 276
Worker 0 assigned to task 1.  Cost = 76
Worker 1 assigned to task 3.  Cost = 65
Worker 2 assigned to task 2.  Cost = 90
Worker 3 assigned to task 0.  Cost = 45

ध्यान दें कि कुल लागत अब मूल सवाल की तुलना में अब ज़्यादा हो गई है. यह हैरानी की बात नहीं है, क्योंकि मूल समस्या में सबसे बेहतर समाधान टास्क 3 को वर्कर 0 को असाइन किया गया, जबकि संशोधित समस्या में यह है कि असाइनमेंट अनुमति नहीं है.

अगर ज़्यादा कर्मचारी काम नहीं कर पाते हैं, तो क्या होगा, यह देखने के लिए 'NA' के साथ लागत मैट्रिक्स की और एंट्री. इससे उन अतिरिक्त कर्मचारियों को दिखाया जा सकता है जो ये कुछ काम नहीं कर सकते:

cost = [[90, 76, 'NA', 'NA'],
        [35, 85, 'NA', 'NA'],
        [125, 95, 'NA','NA'],
        [45, 110, 95, 115]]

इस बार प्रोग्राम चलाने पर, आपको नेगेटिव नतीजा मिलता है:

No assignment is possible.

इसका मतलब है कि टास्क में वर्कर असाइन करने का कोई तरीका नहीं है. इससे हर वर्कर कोई दूसरा टास्क करता है. ऐसा क्यों है, इस ग्राफ़ को देखकर समस्या के लिए (जिसमें 'NA' की वैल्यू के कोई किनारे न हों लागत मैट्रिक्स में).

रैखिक योग असाइनमेंट समाधान फ़्लो ग्राफ़

तीन वर्कर 0, 1, और 2 के नोड सिर्फ़ दो से जुड़े होते हैं अगर आपको टास्क 0 और 1 के लिए अलग-अलग टास्क असाइन नहीं किए गए हैं, तो कर्मचारी.

द मैरिज थ्योरम

ग्राफ़ थ्योरी में एक जाना-पहचाना नतीजा है, जिसे द मैरिज थ्योरम, इससे हमें सटीक जानकारी मिलती है कि बाईं ओर के हर नोड को कब असाइन किया जा सकता है नोड पर क्लिक करें. ऐसा असाइनमेंट इसे परफ़ेक्ट मैचिंग कहते हैं. कम शब्दों में, थ्योरम में कहा गया है कि ऐसा करना संभव है अगर बाईं ओर नोड का कोई सबसेट नहीं है (जैसा कि पिछले उदाहरण में दिया गया है ) जिसके किनारे दाईं ओर नोड के छोटे सेट पर ले जाते हैं.

ज़्यादा सटीक रूप से, प्रमेय के हिसाब से यह बताया गया है कि दो हिस्सों वाला ग्राफ़ सही तरह से मेल खाता है अगर ग्राफ़ की बाईं ओर नोड के किसी भी सबसेट S के लिए, ग्राफ़ के दाईं ओर नोड का सेट जो एक किनारे से जुड़े हुए हैं S में नोड कम से कम S जितना बड़ा है.