דף זה תורגם על ידי 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. יש ארבעה עובדים, שתואמים לשורות של ו-4 משימות, בהתאם לעמודות.

יצירת הפתרון

התוכנה משתמשת ב פותר הקצאה לינארית, שהוא פותר ייעודי לבעיית המטלה.

הקוד הבא יוצר את הפותר.

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, לא ניתן להקצות משימות נפרדות ב-Google Workspace for Education.

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

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

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