דף זה תורגם על ידי 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

שימו לב שהעלות הכוללת גבוהה עכשיו בהשוואה לבעיה המקורית. אין זה מפתיע, מאחר שבבעיה המקורית הפתרון האופטימלי הקצה את העובד 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, לא ניתן להקצות משימות נפרדות לעובדים.

משפט הנישואין

יש תוצאה ידועה מאוד של תורת הגרפים, שנקראת The Marriage Theorem (חוק הנישואים), והיא מראה לנו מתי בדיוק אפשר להקצות כל צומת בצד ימין לצומת נפרד בצד ימין, בתרשים דו-צדדי כמו זה שלמעלה. מטלה כזאת נקראת התאמה מושלמת. על קצה המזלג, המשפט אומר שזה אפשרי אם אין קבוצת משנה של צמתים בצד שמאל (כמו זו שבדוגמה הקודמת) שהקצוות שלהם מובילים לקבוצה קטנה יותר של צמתים מימין.

ליתר דיוק, המשפט אומר שלתרשים דו-חלקי יש התאמה מושלמת אם ורק אם לקבוצת משנה S כלשהי של הצמתים בצד שמאל של התרשים, קבוצת הצמתים בצד ימין של התרשים שמחוברים בקצה לצומת ב-S גדולה לפחות כמו S.