این صفحه به‌وسیله ‏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

بخش‌های زیر یک برنامه پایتون را ارائه می‌کند که یک مسئله انتساب را با استفاده از حل‌کننده مجموع خطی حل می‌کند.

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

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

پایتون

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>

جاوا

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

سی شارپ

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

داده ها را تعریف کنید

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

پایتون

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

جاوا

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

سی شارپ

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 است. چهار کارگر مربوط به ردیف‌های ماتریس و چهار وظیفه مربوط به ستون‌ها وجود دارد.

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

این برنامه از حل کننده تخصیص خطی استفاده می کند، یک حل کننده تخصصی برای مسئله انتساب.

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

پایتون

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

جاوا

LinearSumAssignment assignment = new LinearSumAssignment();

سی شارپ

LinearSumAssignment assignment = new LinearSumAssignment();

محدودیت ها را اضافه کنید

کد زیر هزینه ها را با حلقه زدن کارگران و وظایف به حل کننده اضافه می کند.

پایتون

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

جاوا

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

سی شارپ

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

حل کننده را فراخوانی کنید

کد زیر حل کننده را فراخوانی می کند.

پایتون

status = assignment.solve()

C++

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

جاوا

LinearSumAssignment.Status status = assignment.solve();

سی شارپ

LinearSumAssignment.Status 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.")

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

جاوا

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

سی شارپ

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 می باشد.

نمودار جریان تخصیص جمع خطی

در تئوری گراف، مجموعه ای از یال ها در یک گراف دو بخشی که هر گره سمت چپ را دقیقاً با یک گره در سمت راست مطابقت می دهد، تطبیق کامل نامیده می شود.

کل برنامه

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

پایتون

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

جاوا

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

سی شارپ

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

توجه داشته باشید که هزینه کل اکنون بیشتر از مشکل اصلی است. این تعجب آور نیست، زیرا در مسئله اصلی، راه حل بهینه، کارگر 0 را به وظیفه 3 اختصاص می دهد، در حالی که در مسئله اصلاح شده این انتساب مجاز نیست.

برای اینکه ببینید اگر کارگران بیشتری قادر به انجام وظایف نباشند چه اتفاقی می‌افتد، می‌توانید ورودی‌های بیشتری از ماتریس هزینه را با '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 است.