หน้านี้ได้รับการแปลโดย 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}.");
        }
    }
}

วิธีแก้ไขเมื่อผู้ปฏิบัติงานทำงานทั้งหมดไม่ได้

ในตัวอย่างก่อนหน้านี้ เราสันนิษฐานว่าพนักงานทุกคนสามารถทำงานทุกอย่างได้ แต่ ซึ่งไม่ได้เป็นเช่นนี้เสมอไป ผู้ปฏิบัติงานอาจทำงานไม่ได้อย่างน้อย 1 อย่าง ด้วยเหตุผลหลายประการ อย่างไรก็ตาม สามารถแก้ไขโปรแกรมด้านบนเพื่อจัดการกับ นี้

ตัวอย่างเช่น สมมติว่าผู้ปฏิบัติงาน 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' ในเมทริกซ์ต้นทุน)

กราฟโฟลว์โซลูชันการกำหนดผลรวมเชิงเส้น

เนื่องจากโหนดสำหรับผู้ปฏิบัติงาน 3 ตัว 0, 1 และ 2 จะเชื่อมต่อกับผู้ปฏิบัติงาน 2 ตัวเท่านั้น โหนดสำหรับงาน 0 และ 1 จะไม่สามารถมอบหมายงานที่แตกต่างกันให้กับโหนดเหล่านี้ ผู้ปฏิบัติงาน

ทฤษฎีบทการแต่งงาน

มีผลที่รู้จักกันดีในทฤษฎีกราฟที่เรียกว่า ทฤษฎีบทการแต่งงาน ซึ่งบอกให้เราทราบถึงเวลาที่คุณสามารถกำหนดแต่ละโหนดทางด้านซ้ายให้กับ ทางด้านขวาในกราฟแบบ 2 ภาคเช่นเดียวกับข้างต้น เป็นงานที่มอบหมาย เรียกว่าการจับคู่ที่สมบูรณ์แบบ สรุปคือ ทฤษฎีบทว่าเป็นไปได้ หากไม่มีชุดย่อยของโหนดที่ด้านซ้าย (เช่นในตัวอย่างก่อนหน้านี้ ) ซึ่งมีขอบนำไปยังโหนดชุดที่เล็กลงทางด้านขวา

ยิ่งไปกว่านั้น ทฤษฎีบทยังกล่าวไว้ว่ากราฟสองภาคมีการจับคู่ที่ตรงกันอย่างลงตัว ต่อเมื่อมีการแสดงชุดย่อยของ S ในโหนดทางด้านซ้ายของกราฟ ชุดของโหนดทางด้านขวาของกราฟซึ่งเชื่อมด้วยขอบ อย่างน้อยโหนดใน S ใหญ่พอๆ กับ S