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