Trang này được dịch bởi Cloud Translation API.

Trình giải tổng hợp tuyến tính

Phần này mô tả trình giải bài tập tổng tuyến tính, một công cụ chuyên biệt giúp giải quyết bài tập đơn giản, có thể nhanh hơn so với Trình giải quyết MIP hoặc CP-SAT. Tuy nhiên, trình giải quyết MIP và CP-SAT có thể xử lý nhiều vấn đề hơn, nên trong hầu hết trường hợp, đây là lựa chọn tốt nhất.

Ma trận chi phí

Chi phí cho nhân viên và công việc được cho trong bảng dưới đây.

Worker	Nhiệm vụ 0	Nhiệm vụ 1	Nhiệm vụ 2	Nhiệm vụ 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

Các phần sau đây trình bày một chương trình Python có khả năng giải một bài tập bằng cách sử dụng trình giải bài tập tổng tuyến tính.

Nhập thư viện

Mã nhập thư viện bắt buộc được trình bày dưới đây.

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;

Xác định dữ liệu

Đoạn mã sau đây sẽ tạo dữ liệu cho chương trình.

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();

Mảng này là ma trận chi phí, trong đó mục nhập i, j là chi phí cho worker i để thực hiện tác vụ j. Có 4 worker, tương ứng với các hàng của ma trận và bốn công việc, tương ứng với các cột.

Tạo trình giải

Chương trình này sử dụng công cụ giải bài tập tuyến tính, để giải quyết bài tập trong bài tập.

Mã sau đây sẽ tạo trình giải toán.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

Thêm các điều kiện ràng buộc

Đoạn mã sau đây thêm chi phí cho trình giải bằng cách lặp lại giữa các nhân viên và công việc.

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]);
        }
    }
}

Gọi trình giải

Mã sau đây gọi trình giải.

Python

status = assignment.solve()

C++

SimpleLinearSumAssignment::Status status = assignment.Solve();

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

Hiển thị kết quả

Đoạn mã sau đây sẽ cho thấy giải pháp.

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}.");
}

Kết quả dưới đây cho thấy cách chỉ định tối ưu của worker cho các tác vụ.

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

Biểu đồ sau đây biểu diễn giải pháp dưới dạng các cạnh nét đứt trong biểu đồ. Chiến lược phát hành đĩa đơn bên cạnh các đường nét đứt là chi phí của chúng. Tổng thời gian chờ của nhiệm vụ này là tổng chi phí cho việc cạnh nét đứt là 265.

đồ thị luồng gán tổng tuyến tính

Trong lý thuyết đồ thị, một tập hợp các cạnh trong đồ thị hai phần khớp với mọi nút trên bên trái có đúng một nút bên phải được gọi là kết hợp hoàn hảo.

Toàn bộ chương trình

Sau đây là toàn bộ chương trình.

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}.");
        }
    }
}

Giải pháp khi worker không thể thực hiện tất cả các tác vụ

Trong ví dụ trước, chúng tôi giả định rằng tất cả worker đều có thể thực hiện tất cả các tác vụ. Nhưng điều này không phải lúc nào cũng đúng - một worker có thể không thực hiện được một hoặc nhiều tác vụ vì nhiều lý do. Tuy nhiên, bạn có thể dễ dàng sửa đổi chương trình trên để xử lý này.

Ví dụ: giả sử worker 0 không thể thực hiện tác vụ 3. Để sửa đổi để xem xét điều này, hãy thực hiện các thay đổi sau:

Thay đổi mục nhập 0, 3 của ma trận chi phí thành chuỗi 'NA'. (Bất kỳ chuỗi nào cũng được.)
```
cost = [[90, 76, 75, 'NA'],
    [35, 85, 55, 65],
    [125, 95, 90, 105],
    [45, 110, 95, 115]]
```
Trong phần mã chỉ định chi phí cho trình giải quyết, hãy thêm dòng if cost[worker][task] != 'NA':, như minh hoạ dưới đây.
```
for worker in range(0, rows):
for task in range(0, cols):
  if cost[worker][task] != 'NA':
    assignment.AddArcWithCost(worker, task, cost[worker][task])
```
Dòng đã thêm ngăn chặn mọi cạnh có mục nhập trong ma trận chi phí là 'NA' được thêm vào trình giải.

Sau khi thực hiện những thay đổi này và chạy mã đã sửa đổi, bạn sẽ thấy như sau đầu ra:

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

Lưu ý rằng tổng chi phí hiện cao hơn so với bài toán ban đầu. Điều này không có gì đáng ngạc nhiên, vì trong bài toán ban đầu, phương án tối ưu là đã giao worker 0 cho tác vụ 3, trong khi ở vấn đề đã sửa đổi, bài tập đó không được phép.

Để xem điều gì sẽ xảy ra nếu nhiều worker khác không thể thực hiện tác vụ, bạn có thể thay thế các mục nhập khác của ma trận chi phí bằng 'NA', để biểu thị các nhân viên bổ sung không thể thực hiện một số thao tác:

cost = [[90, 76, 'NA', 'NA'],
        [35, 85, 'NA', 'NA'],
        [125, 95, 'NA','NA'],
        [45, 110, 95, 115]]

Khi chạy chương trình lần này, bạn sẽ nhận được một kết quả âm:

No assignment is possible.

Điều này có nghĩa là không có cách nào để chỉ định nhân viên cho nhiệm vụ để mỗi nhân viên thực hiện một tác vụ khác. Bạn có thể biết lý do khiến điều này xảy ra thông qua biểu đồ cho bài toán (trong đó không có cạnh nào tương ứng với các giá trị của 'NA' trong ma trận chi phí).

đồ thị luồng nghiệm của phép tổng tuyến tính

Vì các nút của 3 worker 0, 1 và 2 chỉ được kết nối với cho các nút 0 và 1, nên không thể gán các nhiệm vụ riêng biệt cho nhân viên.

Định lý hôn nhân

Có một kết quả nổi tiếng trong lý thuyết đồ thị, được gọi là Định lý hôn nhân, Thông tin này cho chúng tôi biết chính xác thời điểm bạn có thể gán mỗi nút ở bên trái cho một nút ở bên phải, trong biểu đồ hai phần như biểu đồ trên. Bài tập như vậy được gọi là kết hợp hoàn hảo. Tóm lại, theo định lý này, điều này có thể xảy ra nếu không có tập hợp con các nút ở bên trái (như tập hợp con trong ví dụ trước ) có các cạnh dẫn đến một tập hợp các nút nhỏ hơn ở bên phải.

Chính xác hơn, định lý nói rằng đồ thị hai phần có kết quả phù hợp hoàn hảo nếu và chỉ khi với bất kỳ tập con S nào của các nút ở bên trái của đồ thị, tập hợp các nút ở bên phải của đồ thị được nối bởi một cạnh với nút trong S ít nhất lớn bằng S.