หน้านี้ได้รับการแปลโดย 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 คนตามแถวของเมทริกซ์ และงาน 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

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

ในทฤษฎีกราฟ ชุดของขอบในกราฟ 2 ส่วนที่ตรงกับทุกโหนดทางด้านซ้ายโดยมีโหนดทางด้านขวาเพียง 1 โหนดเรียกว่าการจับคู่ที่สมบูรณ์แบบ

ทั้งโปรแกรม

ข้อมูลโปรแกรมทั้งหมดมีดังนี้

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