练习8
分配甲、乙、丙、丁4个人去完成A、B、C、D、E 5项任务，每个人完成各项任务的时间见下表。由于任务数多于人数，故考虑：
(1) 任务E必须完成，其他4项中可任选3项完成；
(2) 其中有一人完成两项，其他每人完成一项。
试分别确定最优分配方案，使完成任务的总时间为最少。
| 人员\任务 | A | B | C | D | E |
|---|---|---|---|---|---|
| 甲 | 25 | 29 | 31 | 42 | 37 |
| 乙 | 39 | 38 | 26 | 20 | 33 |
| 丙 | 34 | 27 | 28 | 40 | 32 |
| 丁 | 24 | 42 | 36 | 23 | 45 |
8.1 （1）问题指派分析
为了确定最优分配方案，使完成任务的总时间最少，我们可以按照以下步骤进行求解：
- 确定任务选择：
- 任务E必须完成，所以必须包含在选择的任务中。
- 在A、B、C、D四项任务中任选三项，共有\(\binom{4}{3} = 4\)种选择。
- 即选择组合为：{A, B, C, E}、{A, B, D, E}、{A, C, D, E}、{B, C, D, E}。
- 任务分配方案：
- 每个任务选择组合确定后，分配4个人完成这4项任务，计算所有可能的分配情况，选择总时间最少的方案。
- 计算最优方案：
- 对于每一种任务组合，使用计算机算法（如动态规划或组合搜索）来计算所有可能的分配方案，求出总时间最少的方案。
8.2 （1）问题的Python程序
import itertools
import numpy as np
from scipy.optimize import linear_sum_assignment
# 定义任务时间表
time_table = {
'A': [25, 39, 34, 24],
'B': [29, 38, 27, 42],
'C': [31, 26, 28, 36],
'D': [42, 20, 40, 23],
'E': [37, 33, 32, 45]
}
tasks = ['A', 'B', 'C', 'D', 'E']
persons = [0, 1, 2, 3] # 0: 甲, 1: 乙, 2: 丙, 3: 丁
# 任务组合
task_combinations = [
['A', 'B', 'C', 'E'],
['A', 'B', 'D', 'E'],
['A', 'C', 'D', 'E'],
['B', 'C', 'D', 'E']
]
def calculate_assignment_cost(cost_matrix):
row_ind, col_ind = linear_sum_assignment(cost_matrix)
return cost_matrix[row_ind, col_ind].sum(), list(zip(row_ind, col_ind))
best_time = float('inf')
best_combination = None
best_assignment = None
# 存储每个组合的最小总时间
combination_times = {}
for comb in task_combinations:
# 构建成本矩阵
cost_matrix = []
for person in persons:
cost_row = []
for task in comb:
cost_row.append(time_table[task][person])
cost_matrix.append(cost_row)
cost_matrix = np.array(cost_matrix)
# 计算最优分配
time, assignment = calculate_assignment_cost(cost_matrix)
combination_times[tuple(comb)] = time
if time < best_time:
best_time = time
best_combination = comb
best_assignment = assignment
# 输出每个任务组合的最小总时间
print("各任务组合的最小总时间:")
for comb, time in combination_times.items():
print(f"任务组合 {comb}: 最小总时间 {time}分钟")
# 输出最优方案
person_names = ['甲', '乙', '丙', '丁']
assignment_str = {best_combination[task]: person_names[person] for person, task in best_assignment}
print("\n最优方案:")
print(f"最优任务组合: {best_combination}")
print(f"最优分配方案: {assignment_str}")
print(f"最少总时间: {best_time}分钟")
各任务组合的最小总时间:
任务组合 ('A', 'B', 'C', 'E'): 最小总时间 111分钟
任务组合 ('A', 'B', 'D', 'E'): 最小总时间 105分钟
任务组合 ('A', 'C', 'D', 'E'): 最小总时间 106分钟
任务组合 ('B', 'C', 'D', 'E'): 最小总时间 110分钟
最优方案:
最优任务组合: ['A', 'B', 'D', 'E']
最优分配方案: {'B': '甲', 'D': '乙', 'E': '丙', 'A': '丁'}
最少总时间: 105分钟
8.3 （2）问题的指派分析
要解决这个问题，我们可以使用组合与排列的方法生成所有可能的任务分配方案，然后计算每个方案的总时间，选择最小的一个。具体步骤如下：
对4个人中的每一个考虑分配两个任务，其余三个人各分配一个任务，共有\(\binom{5}{2} = 10\)。
生成新的成本矩阵，对于每一个人承担两个任务的情况，计算出所有可能的任务分配组合。
对每个生成的成本矩阵，使用匈牙利算法（Hungarian Algorithm）来求解最优任务分配问题。
比较所有情况的最小总时间，找到最优分配方案。
8.4（2）问题的Python程序
import numpy as np
from scipy.optimize import linear_sum_assignment
# 给定的时间表
time_table = {
'A': [25, 39, 34, 24],
'B': [29, 38, 27, 42],
'C': [31, 26, 28, 36],
'D': [42, 20, 40, 23],
'E': [37, 33, 32, 45]
}
tasks = ['A', 'B', 'C', 'D', 'E']
persons = ['甲', '乙', '丙', '丁'] # 0: 甲, 1: 乙, 2: 丙, 3: 丁
# 将time_table转换为二维数组
time_matrix = np.array([time_table[task] for task in tasks]).T
# 创建新矩阵并输出
new_matrices = []
for i in range(time_matrix.shape[0]):
new_row = time_matrix[i, :]
new_matrix = np.vstack([time_matrix, new_row])
new_matrices.append((new_matrix, i))
# 对new_matrices进行指派问题求解并打印每个最优值
best_total_time = float('inf')
best_assignment = None
best_matrix = None
best_row_index = None
for idx, (matrix, row_index) in enumerate(new_matrices):
row_ind, col_ind = linear_sum_assignment(matrix)
total_time = matrix[row_ind, col_ind].sum()
print(f"新矩阵 {idx + 1} 的最优值: {total_time} 分钟")
if total_time < best_total_time:
best_total_time = total_time
best_assignment = list(zip(row_ind, col_ind))
best_matrix = matrix
best_row_index = row_index
# 输出最优指派方案和最小值
print("\n最优指派方案:")
for person, task in best_assignment:
person_name = persons[person] if person < len(persons) else '完成两个任务的人员'
task_name = tasks[task] if task < len(tasks) else '额外的任务'
time_spent = best_matrix[person, task]
print(f"{person_name} 负责任务 {task_name}, 所需时间: {time_spent} 分钟")
print(f"最小总时间: {best_total_time} 分钟")
print(f"添加的行: {best_row_index+1}，即完成两个任务的人员: {persons[best_row_index]}")
新矩阵 1 的最优值: 135 分钟
新矩阵 2 的最优值: 131 分钟
新矩阵 3 的最优值: 133 分钟
新矩阵 4 的最优值: 134 分钟
最优指派方案:
甲 负责任务 B, 所需时间: 29 分钟
乙 负责任务 C, 所需时间: 26 分钟
丙 负责任务 E, 所需时间: 32 分钟
丁 负责任务 A, 所需时间: 24 分钟
完成两个任务的人员 负责任务 D, 所需时间: 20 分钟
最小总时间: 131 分钟
添加的行: 2，即完成两个任务的人员: 乙