تمت ترجمة هذه الصفحة بواسطة 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

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

لاحظ أن التكلفة الإجمالية الآن أعلى مما كانت عليه للمشكلة الأصلية. وهذا ليس بمستغرب، لأنه في المشكلة الأصلية يكون الحل الأمثل العامل 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 على الأقل.