求解任务分配问题(分枝限界法)代码

以下是分枝限界法求解任务分配问题的 Python 代码：

import numpy as np

# 定义任务分配问题的类
class Task:
    def __init__(self, cost_matrix):
        self.n = len(cost_matrix)
        self.cost_matrix = cost_matrix
        self.assigned = [None] * self.n
        self.marked_rows = set()
        self.marked_cols = set()
        self.row_min = np.min(self.cost_matrix, axis=1)
        self.col_min = np.min(self.cost_matrix, axis=0)

    # 获取当前分配的总成本
    def get_total_cost(self):
        total_cost = 0
        for i in range(self.n):
            j = self.assigned[i]
            if j is not None:
                total_cost += self.cost_matrix[i][j]
        return total_cost

    # 找到一个未分配的任务并返回其行和列号
    def find_unassigned_task(self):
        for i in range(self.n):
            if i not in self.marked_rows:
                for j in range(self.n):
                    if j not in self.marked_cols and self.cost_matrix[i][j] == self.row_min[i] + self.col_min[j]:
                        return i, j
        return None

    # 分配任务并更新行和列的最小值
    def assign_task(self, i, j):
        self.assigned[i] = j
        self.marked_rows.add(i)
        self.marked_cols.add(j)
        self.row_min[i] = np.min(self.cost_matrix[i])
        self.col_min[j] = np.min(self.cost_matrix[:, j])

    # 取消任务分配并恢复行和列的最小值
    def unassign_task(self, i, j):
        self.assigned[i] = None
        self.marked_rows.remove(i)
        self.marked_cols.remove(j)
        self.row_min[i] = np.min(self.cost_matrix[i])
        self.col_min[j] = np.min(self.cost_matrix[:, j])

# 分枝限界法求解任务分配问题
def solve_task_assignment(cost_matrix):
    task = Task(cost_matrix)
    stack = [task]
    best_cost = np.inf
    best_assignment = None

    while stack:
        task = stack.pop()
        if len(task.marked_rows) == task.n:
            # 所有任务都已分配，更新最优解
            total_cost = task.get_total_cost()
            if total_cost < best_cost:
                best_cost = total_cost
                best_assignment = task.assigned
        else:
            # 找到一个未分配的任务并分枝
            i, j = task.find_unassigned_task()
            if i is not None:
                # 分枝：将任务 i 分配给工人 j，继续求解子问题
                new_task = Task(task.cost_matrix.copy())
                new_task.assign_task(i, j)
                stack.append(new_task)
            # 分枝：不将任务 i 分配给任何工人，继续求解子问题
            new_task = Task(task.cost_matrix.copy())
            new_task.marked_rows.add(i)
            stack.append(new_task)

    return best_cost, best_assignment

# 示例
cost_matrix = np.array([
    [9, 11, 14, 5],
    [6, 15, 13, 7],
    [12, 13, 6, 8],
    [7, 10, 8, 9]
])
total_cost, assignment = solve_task_assignment(cost_matrix)
print("Total cost:", total_cost)
print("Assignment:", assignment)

其中，`Task` 类表示任务分配问题，包含以下属性和方法：

- `n`：任务数/工人数。
- `cost_matrix`：任务分配成本矩阵。
- `assigned`：长度为 `n` 的列表，表示每个任务分配给了哪个工人。如果任务未分配，则对应元素为 `None`。
- `marked_rows`：已标记的行号集合。
- `marked_cols`：已标记的列号集合。
- `row_min`：长度为 `n` 的列表，表示每行的最小值。
- `col_min`：长度为 `n` 的列表，表示每列的最小值。
- `get_total_cost()`：获取当前分配的总成本。
- `find_unassigned_task()`：找到一个未分配的任务并返回其行和列号。
- `assign_task(i, j)`：将任务 `i` 分配给工人 `j` 并更新行和列的最小值。
- `unassign_task(i, j)`：取消任务 `i` 的分配并恢复行和列的最小值。

`solve_task_assignment()` 函数使用分枝限界法求解任务分配问题，包含以下步骤：

- 初始化任务对象和栈，将任务对象压入栈中。
- 循环取出栈顶任务对象，如果所有任务都已分配，则更新最优解；否则找到一个未分配的任务并分枝，将分枝后的任务对象压入栈中。
- 返回最优解的总成本和分配方案。