Lingo计算工时最小解

Question

题目
有4个工人，要指派他们分别完成4种工作，每人做各种工作做消耗的时间如表5-11所示，问指派哪个人去完成哪种工作，可使总的消耗时间为最小？

Answer 1

引自免费微信小程序：皆我百晓生

为了找到指派工人完成工作的最小总消耗时间，我们可以创建一个线性规划问题。在这个问题中，我们有两个变量：x_ij表示工人i被分配到工作j的决策（0或1），其中1表示工人i做工作j，0表示不做。我们需要优化的目标函数是总工时，即求和所有工人完成工作的工时。同时，每个工人只能做一种工作，所以我们需要添加约束条件。

首先，让我们定义变量和目标函数：

设x_ij = 1 如果工人i做工作j，否则x_ij = 0

目标函数：Minimize Z = Σ(x_1B + x_1D + x_1E + x_1F) + Σ(x_2B + x_2D + x_2E + x_2F) + Σ(x_3B + x_3D + x_3E + x_3F) + Σ(x_4B + x_4D + x_4E + x_4F)

接下来，添加约束条件：

1. 每个工人只能做一项工作：对于工人i，Σ(x_ij) = 1, i = 1, 2, 3, 4; j = B, D, E, F
2. 工作量不能超过可用时间：对于工作j，Σ(x_ij * t_ij) <= T_j, j = B, D, E, F, 其中t_ij 是工人i完成工作j的工时

现在，我们可以用线性规划软件或编程语言（如Python的 pulp 或 scipy）来解决这个问题。以下是使用pulp库的完整代码：

from pulp import *

# 定义变量
workers = ['A', 'B', 'C', 'D']
jobs = ['B', 'D', 'E', 'F']
time_matrix = {
    ('A', 'B'): 2,
    ('A', 'D'): 19,
    # ... 其他工人和工作的对应关系
}

# 创建模型
model = LpProblem("Minimum Working Time", LpMinimize)

# 定义决策变量
x = LpVariable.dicts("x", [(i, j) for i in workers for j in jobs], cat='Binary')

# 目标函数
objective = lpSum([time_matrix[i, j] * x[i, j] for i in workers for j in jobs])
model += objective

# 约束：每个工人只能做一项工作
for i in workers:
    model += lpSum([x[i, j] for j in jobs]) == 1, f"Constraint_{i}"

# 约束：工作量不超过可用时间
available_times = {
    'B': 15,
    'D': 18,
    # ... 其他工作对应的可用时间
}
for j in jobs:
    model += lpSum([time_matrix[i, j] * x[i, j] for i in workers]) <= available_times[j], f"Constraint_Time_{j}"

# 解决模型
model.solve()

# 输出结果
for v in model.variables():
    if v.varValue > 0.5:
        print(f"工人 {v.name[0]} 被指派做工作 {v.name[1]}，耗时为 {v.value:.2f} 小时")

# 总工时
total_time = value(objective)
print(f"最小总工时为 {total_time:.2f} 小时")

运行这段代码后，你会得到每个工人的工作分配以及最小的总工时。请注意，你需要将time_matrix和available_times字典中的数据替换为实际的数值。