组合太多
Too many combinations
您好，我正在尝试生成工人与建筑物的所有可能组合。 （让我解释一下我的情况）：
我正在玩 MineColonies 我的世界。在这个 mod 中，您有殖民者可以在建筑物中分配工作。这些工人有技能和分配给他们的分数。 （比如敏捷：20，Strength:5 等）并且当分配给技能相称的殖民者时，建筑物的工作会更好地执行...
所以我创建了一个包含所有工人和建筑物的数据库，并希望优化哪些工人在哪些建筑物工作。
buildings_dict = {1: ['Strength', 'Focus'],
2: ['Adaptability', 'Athletics'],
3: ['Knowledge', 'Dexterity'],
4: ['Adaptability', 'Knowledge'],
6: ['Stamina', 'Athletics'],
5: ['Athletics', 'Stamina'],
7: ['Focus', 'Agility'],
8: ['Dexterity', 'Creativity'],
9: ['Strength', 'Focus'],
10: ['Adaptability', 'Stamina'],
11: ['Agility', 'Adaptability'],
12: ['Mana', 'Knowledge'],
13: ['Strength', 'Stamina'],
14: ['Athletics', 'Strength'],
15: ['Creativity', 'Dexterity'],
16: ['Knowledge', 'Mana'],
17: ['Agility', 'Adaptability']}
workers_dict = {3: {'Mana': 30,
'Focus': 1,
'Agility': 3,
'Stamina': 3,
'Knowlege': 30,
'Strenght': 8,
'Athletics': 13,
'Dexterity': 6,
'Creativity': 10,
'Adaptability': 10,
'Intelligence': 10},
4: {'Mana': 29,
'Focus': 32,
'Agility': 22,
'Stamina': 28,
'Knowlege': 21,
'Strenght': 30,
'Athletics': 20,
'Dexterity': 31,
'Creativity': 31,
'Adaptability': 8,
'Intelligence': 18},
5: {'Mana': 13,
'Focus': 1,
'Agility': 9,
'Stamina': 27,
'Knowlege': 9,
'Strenght': 13,
'Athletics': 15,
'Dexterity': 21,
'Creativity': 16,
'Adaptability': 13,
'Intelligence': 28},
6: {'Mana': 17,
'Focus': 14,
'Agility': 10,
'Stamina': 17,
'Knowlege': 13,
'Strenght': 5,
'Athletics': 10,
'Dexterity': 15,
'Creativity': 1,
'Adaptability': 11,
'Intelligence': 4},
7: {'Mana': 1,
'Focus': 8,
'Agility': 6,
'Stamina': 27,
'Knowlege': 11,
'Strenght': 17,
'Athletics': 30,
'Dexterity': 1,
'Creativity': 5,
'Adaptability': 11,
'Intelligence': 5},
8: {'Mana': 6,
'Focus': 1,
'Agility': 12,
'Stamina': 30,
'Knowlege': 20,
'Strenght': 15,
'Athletics': 30,
'Dexterity': 9,
'Creativity': 17,
'Adaptability': 30,
'Intelligence': 19},
9: {'Mana': 5,
'Focus': 7,
'Agility': 19,
'Stamina': 5,
'Knowlege': 22,
'Strenght': 18,
'Athletics': 26,
'Dexterity': 10,
'Creativity': 24,
'Adaptability': 20,
'Intelligence': 22},
10: {'Mana': 8,
'Focus': 12,
'Agility': 27,
'Stamina': 3,
'Knowlege': 17,
'Strenght': 1,
'Athletics': 5,
'Dexterity': 9,
'Creativity': 7,
'Adaptability': 29,
'Intelligence': 1},
11: {'Mana': 1,
'Focus': 4,
'Agility': 5,
'Stamina': 30,
'Knowlege': 16,
'Strenght': 11,
'Athletics': 28,
'Dexterity': 11,
'Creativity': 5,
'Adaptability': 12,
'Intelligence': 4},
12: {'Mana': 7,
'Focus': 1,
'Agility': 17,
'Stamina': 25,
'Knowlege': 23,
'Strenght': 4,
'Athletics': 8,
'Dexterity': 26,
'Creativity': 15,
'Adaptability': 29,
'Intelligence': 22},
13: {'Mana': 2,
'Focus': 1,
'Agility': 5,
'Stamina': 21,
'Knowlege': 24,
'Strenght': 18,
'Athletics': 20,
'Dexterity': 10,
'Creativity': 12,
'Adaptability': 30,
'Intelligence': 5},
14: {'Mana': 9,
'Focus': 16,
'Agility': 14,
'Stamina': 25,
'Knowlege': 14,
'Strenght': 24,
'Athletics': 30,
'Dexterity': 9,
'Creativity': 19,
'Adaptability': 23,
'Intelligence': 18},
15: {'Mana': 23,
'Focus': 15,
'Agility': 5,
'Stamina': 12,
'Knowlege': 24,
'Strenght': 12,
'Athletics': 20,
'Dexterity': 29,
'Creativity': 5,
'Adaptability': 19,
'Intelligence': 12},
17: {'Mana': 21,
'Focus': 23,
'Agility': 30,
'Stamina': 18,
'Knowlege': 27,
'Strenght': 7,
'Athletics': 30,
'Dexterity': 10,
'Creativity': 5,
'Adaptability': 22,
'Intelligence': 18},
18: {'Mana': 11,
'Focus': 11,
'Agility': 4,
'Stamina': 7,
'Knowlege': 28,
'Strenght': 11,
'Athletics': 20,
'Dexterity': 28,
'Creativity': 13,
'Adaptability': 12,
'Intelligence': 30},
19: {'Mana': 11,
'Focus': 11,
'Agility': 4,
'Stamina': 7,
'Knowlege': 28,
'Strenght': 11,
'Athletics': 20,
'Dexterity': 28,
'Creativity': 13,
'Adaptability': 12,
'Intelligence': 30},
20: {'Mana': 15,
'Focus': 20,
'Agility': 28,
'Stamina': 22,
'Knowlege': 18,
'Strenght': 15,
'Athletics': 23,
'Dexterity': 19,
'Creativity': 20,
'Adaptability': 27,
'Intelligence': 20},
21: {'Mana': 30,
'Focus': 7,
'Agility': 9,
'Stamina': 7,
'Knowlege': 30,
'Strenght': 3,
'Athletics': 6,
'Dexterity': 17,
'Creativity': 4,
'Adaptability': 11,
'Intelligence': 28},
22: {'Mana': 9,
'Focus': 10,
'Agility': 28,
'Stamina': 26,
'Knowlege': 1,
'Strenght': 8,
'Athletics': 5,
'Dexterity': 26,
'Creativity': 1,
'Adaptability': 14,
'Intelligence': 16},
23: {'Mana': 4,
'Focus': 14,
'Agility': 19,
'Stamina': 5,
'Knowledge': 21,
'Strength': 25,
'Athletics': 12,
'Dexterity': 23,
'Creativity': 26,
'Adaptability': 21,
'Intelligence': 22},
24: {'Mana': 1,
'Focus': 1,
'Agility': 18,
'Stamina': 24,
'Knowledge': 25,
'Strength': 20,
'Athletics': 9,
'Dexterity': 14,
'Creativity': 19,
'Adaptability': 30,
'Intelligence': 7},
25: {'Mana': 12,
'Focus': 13,
'Agility': 21,
'Stamina': 23,
'Knowledge': 11,
'Strength': 16,
'Athletics': 18,
'Dexterity': 24,
'Creativity': 1,
'Adaptability': 20,
'Intelligence': 1},
26: {'Mana': 10,
'Focus': 14,
'Agility': 12,
'Stamina': 27,
'Knowledge': 17,
'Strength': 24,
'Athletics': 23,
'Dexterity': 21,
'Creativity': 5,
'Adaptability': 5,
'Intelligence': 28},
27: {'Mana': 11,
'Focus': 23,
'Agility': 21,
'Stamina': 12,
'Knowledge': 15,
'Strength': 24,
'Athletics': 17,
'Dexterity': 12,
'Creativity': 1,
'Adaptability': 11,
'Intelligence': 9},
28: {'Mana': 7,
'Focus': 21,
'Agility': 22,
'Stamina': 21,
'Knowledge': 14,
'Strength': 15,
'Athletics': 9,
'Dexterity': 16,
'Creativity': 2,
'Adaptability': 11,
'Intelligence': 5},
29: {'Mana': 12,
'Focus': 25,
'Agility': 29,
'Stamina': 6,
'Knowledge': 7,
'Strength': 10,
'Athletics': 14,
'Dexterity': 15,
'Creativity': 6,
'Adaptability': 13,
'Intelligence': 29},
30: {'Mana': 21,
'Focus': 17,
'Agility': 8,
'Stamina': 21,
'Knowledge': 22,
'Strength': 22,
'Athletics': 26,
'Dexterity': 13,
'Creativity': 15,
'Adaptability': 24,
'Intelligence': 13}}
抱歉，代码块太长了，是的，我意识到 ID 不一定正确（希望使其可重现）。
所以我正在使用 itertools.permutations 将所有工人组合带到建筑物中：
import itertools
workers_ls = list(workers_dict.keys())
combinations = list(itertools.permutations(workers_ls, len(buildings_dict))
（我打算后面组合打分）
这显然从未完成 运行 因为它大约是 27！ = 1×10²⁸。
我想知道是否有另一种解决方案来解决我的问题，或者是否有一种方法可以在不经过所有组合的情况下确定最佳解决方案。 （我愿意使用其他编码语言工作）
谢谢！
我假设您想最大化总产量的总和。例如，当没有分配工人时，总产量为零（或某个不依赖于工人分配的常数）。如果将 Agility 2 和 Focus 3 的工人与属性为 [Agility, Focus] 的建筑物配对，则总产量将增加 2+3=5。
像这样的问题通常可以用线性规划来解决。我将使用 pulp 来帮助制定线性规划问题。我还建议检查 Julia 包 JuMP.
计算总产量的实际规则可能更复杂。如果 (1) 您可以定义一些生产矩阵的模拟，并且 (2) 总产量可以表示为（工人、建筑物）对的产量之和，您仍然可以使用线性规划。
这里有两种方法可以解决这个问题。第一个允许每个建筑物有多个工人，第二个不允许。
设置
import pandas as pd
import numpy as np
# !pip install pulp
import pulp
df_buildings = pd.DataFrame(buildings_dict).T
df_workers = pd.DataFrame(workers_dict).T
# there are a few typos, e.g. Strenght vs. Strength and Knowlege vs. Knowledge
# let's fix this first
df_workers.Knowledge.fillna(df_workers.Knowlege, inplace=True)
df_workers.Strength.fillna(df_workers.Strenght, inplace=True)
del df_workers["Strenght"], df_workers["Knowlege"]
# fixing some notation
workers = df_workers.index.tolist() # list of workers
buildings = df_buildings.index.tolist() # list of building
# next, we define production matrix
# production[i,j] will contain the productivity of
# worker i when assigned to building j
# you could vectorize this step, though it seems fast enough here
production = pd.DataFrame(index=workers, columns=buildings)
for i in df_workers.index:
for j in df_buildings.index:
production.loc[i, j] = df_workers.loc[i, df_buildings.loc[j]].sum()
print(production.head())
# 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 16 17
# 3 9 23 36 40 16 16 4 16 9 13 13 60 11 21 16 60 13
# 4 62 28 52 29 48 48 54 62 62 36 30 50 58 50 62 50 30
# 5 14 28 30 22 42 42 10 37 14 40 22 22 40 28 37 22 22
# 6 19 21 28 24 27 27 24 16 19 28 21 30 22 15 16 30 21
# 7 25 41 12 22 57 57 14 6 25 38 17 12 44 47 6 12 17
每栋建筑允许多名工人
prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)
# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")
# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
for i in workers for j in buildings)
# each worker can be assigned to at most one building:
for i in workers:
prob += sum(assignment[i][j] for j in buildings) <= 1
prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1
# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
if assignment[i][j].varValue == 1}
print(f"Total production is {prob.objective.value()}") # 1401
# here is the the solution
# assignment_dict_saved = {3: 12, 4: 1, 5: 5, 6: 16, 7: 5, 8: 6, 9: 2, 10: 17, 11: 6, 12: 10, 13: 4, 14: 6, 15: 3, 17: 7, 18: 3, 19: 3, 20: 11, 21: 12, 22: 17, 23: 15, 24: 4, 25: 10, 26: 13, 27: 9, 28: 7, 29: 7, 30: 2}
每栋楼最多一名工人
prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)
# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")
# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
for i in workers for j in buildings)
# each worker can be assigned to at most one building:
for i in workers:
prob += sum(assignment[i][j] for j in buildings) <= 1
# each building has at most one worker
for j in buildings:
prob += sum(assignment[i][j] for i in workers) <= 1
prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1
# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
if assignment[i][j].varValue == 1}
# assignment_dict_saved = {3: 16, 4: 9, 7: 5, 8: 2, 10: 11, 11: 6, 12: 10, 14: 14, 18: 3, 19: 8, 20: 17, 21: 12, 23: 15, 24: 4, 26: 13, 27: 1, 29: 7}
print(f"Total production is {prob.objective.value()}") # 929
我们可以看到，当我们允许每个建筑物配备多个工人时，总产量会更高。这是意料之中的，因为最大化问题的约束较少。
我们还可以将优化后的生产与随机分配工人时的生产进行比较。垂直线对应于最佳生产。看来我们做的还不错。
您好，我正在尝试生成工人与建筑物的所有可能组合。 （让我解释一下我的情况）：
我正在玩 MineColonies 我的世界。在这个 mod 中，您有殖民者可以在建筑物中分配工作。这些工人有技能和分配给他们的分数。 （比如敏捷：20，Strength:5 等）并且当分配给技能相称的殖民者时，建筑物的工作会更好地执行...
所以我创建了一个包含所有工人和建筑物的数据库，并希望优化哪些工人在哪些建筑物工作。
buildings_dict = {1: ['Strength', 'Focus'],
2: ['Adaptability', 'Athletics'],
3: ['Knowledge', 'Dexterity'],
4: ['Adaptability', 'Knowledge'],
6: ['Stamina', 'Athletics'],
5: ['Athletics', 'Stamina'],
7: ['Focus', 'Agility'],
8: ['Dexterity', 'Creativity'],
9: ['Strength', 'Focus'],
10: ['Adaptability', 'Stamina'],
11: ['Agility', 'Adaptability'],
12: ['Mana', 'Knowledge'],
13: ['Strength', 'Stamina'],
14: ['Athletics', 'Strength'],
15: ['Creativity', 'Dexterity'],
16: ['Knowledge', 'Mana'],
17: ['Agility', 'Adaptability']}
workers_dict = {3: {'Mana': 30,
'Focus': 1,
'Agility': 3,
'Stamina': 3,
'Knowlege': 30,
'Strenght': 8,
'Athletics': 13,
'Dexterity': 6,
'Creativity': 10,
'Adaptability': 10,
'Intelligence': 10},
4: {'Mana': 29,
'Focus': 32,
'Agility': 22,
'Stamina': 28,
'Knowlege': 21,
'Strenght': 30,
'Athletics': 20,
'Dexterity': 31,
'Creativity': 31,
'Adaptability': 8,
'Intelligence': 18},
5: {'Mana': 13,
'Focus': 1,
'Agility': 9,
'Stamina': 27,
'Knowlege': 9,
'Strenght': 13,
'Athletics': 15,
'Dexterity': 21,
'Creativity': 16,
'Adaptability': 13,
'Intelligence': 28},
6: {'Mana': 17,
'Focus': 14,
'Agility': 10,
'Stamina': 17,
'Knowlege': 13,
'Strenght': 5,
'Athletics': 10,
'Dexterity': 15,
'Creativity': 1,
'Adaptability': 11,
'Intelligence': 4},
7: {'Mana': 1,
'Focus': 8,
'Agility': 6,
'Stamina': 27,
'Knowlege': 11,
'Strenght': 17,
'Athletics': 30,
'Dexterity': 1,
'Creativity': 5,
'Adaptability': 11,
'Intelligence': 5},
8: {'Mana': 6,
'Focus': 1,
'Agility': 12,
'Stamina': 30,
'Knowlege': 20,
'Strenght': 15,
'Athletics': 30,
'Dexterity': 9,
'Creativity': 17,
'Adaptability': 30,
'Intelligence': 19},
9: {'Mana': 5,
'Focus': 7,
'Agility': 19,
'Stamina': 5,
'Knowlege': 22,
'Strenght': 18,
'Athletics': 26,
'Dexterity': 10,
'Creativity': 24,
'Adaptability': 20,
'Intelligence': 22},
10: {'Mana': 8,
'Focus': 12,
'Agility': 27,
'Stamina': 3,
'Knowlege': 17,
'Strenght': 1,
'Athletics': 5,
'Dexterity': 9,
'Creativity': 7,
'Adaptability': 29,
'Intelligence': 1},
11: {'Mana': 1,
'Focus': 4,
'Agility': 5,
'Stamina': 30,
'Knowlege': 16,
'Strenght': 11,
'Athletics': 28,
'Dexterity': 11,
'Creativity': 5,
'Adaptability': 12,
'Intelligence': 4},
12: {'Mana': 7,
'Focus': 1,
'Agility': 17,
'Stamina': 25,
'Knowlege': 23,
'Strenght': 4,
'Athletics': 8,
'Dexterity': 26,
'Creativity': 15,
'Adaptability': 29,
'Intelligence': 22},
13: {'Mana': 2,
'Focus': 1,
'Agility': 5,
'Stamina': 21,
'Knowlege': 24,
'Strenght': 18,
'Athletics': 20,
'Dexterity': 10,
'Creativity': 12,
'Adaptability': 30,
'Intelligence': 5},
14: {'Mana': 9,
'Focus': 16,
'Agility': 14,
'Stamina': 25,
'Knowlege': 14,
'Strenght': 24,
'Athletics': 30,
'Dexterity': 9,
'Creativity': 19,
'Adaptability': 23,
'Intelligence': 18},
15: {'Mana': 23,
'Focus': 15,
'Agility': 5,
'Stamina': 12,
'Knowlege': 24,
'Strenght': 12,
'Athletics': 20,
'Dexterity': 29,
'Creativity': 5,
'Adaptability': 19,
'Intelligence': 12},
17: {'Mana': 21,
'Focus': 23,
'Agility': 30,
'Stamina': 18,
'Knowlege': 27,
'Strenght': 7,
'Athletics': 30,
'Dexterity': 10,
'Creativity': 5,
'Adaptability': 22,
'Intelligence': 18},
18: {'Mana': 11,
'Focus': 11,
'Agility': 4,
'Stamina': 7,
'Knowlege': 28,
'Strenght': 11,
'Athletics': 20,
'Dexterity': 28,
'Creativity': 13,
'Adaptability': 12,
'Intelligence': 30},
19: {'Mana': 11,
'Focus': 11,
'Agility': 4,
'Stamina': 7,
'Knowlege': 28,
'Strenght': 11,
'Athletics': 20,
'Dexterity': 28,
'Creativity': 13,
'Adaptability': 12,
'Intelligence': 30},
20: {'Mana': 15,
'Focus': 20,
'Agility': 28,
'Stamina': 22,
'Knowlege': 18,
'Strenght': 15,
'Athletics': 23,
'Dexterity': 19,
'Creativity': 20,
'Adaptability': 27,
'Intelligence': 20},
21: {'Mana': 30,
'Focus': 7,
'Agility': 9,
'Stamina': 7,
'Knowlege': 30,
'Strenght': 3,
'Athletics': 6,
'Dexterity': 17,
'Creativity': 4,
'Adaptability': 11,
'Intelligence': 28},
22: {'Mana': 9,
'Focus': 10,
'Agility': 28,
'Stamina': 26,
'Knowlege': 1,
'Strenght': 8,
'Athletics': 5,
'Dexterity': 26,
'Creativity': 1,
'Adaptability': 14,
'Intelligence': 16},
23: {'Mana': 4,
'Focus': 14,
'Agility': 19,
'Stamina': 5,
'Knowledge': 21,
'Strength': 25,
'Athletics': 12,
'Dexterity': 23,
'Creativity': 26,
'Adaptability': 21,
'Intelligence': 22},
24: {'Mana': 1,
'Focus': 1,
'Agility': 18,
'Stamina': 24,
'Knowledge': 25,
'Strength': 20,
'Athletics': 9,
'Dexterity': 14,
'Creativity': 19,
'Adaptability': 30,
'Intelligence': 7},
25: {'Mana': 12,
'Focus': 13,
'Agility': 21,
'Stamina': 23,
'Knowledge': 11,
'Strength': 16,
'Athletics': 18,
'Dexterity': 24,
'Creativity': 1,
'Adaptability': 20,
'Intelligence': 1},
26: {'Mana': 10,
'Focus': 14,
'Agility': 12,
'Stamina': 27,
'Knowledge': 17,
'Strength': 24,
'Athletics': 23,
'Dexterity': 21,
'Creativity': 5,
'Adaptability': 5,
'Intelligence': 28},
27: {'Mana': 11,
'Focus': 23,
'Agility': 21,
'Stamina': 12,
'Knowledge': 15,
'Strength': 24,
'Athletics': 17,
'Dexterity': 12,
'Creativity': 1,
'Adaptability': 11,
'Intelligence': 9},
28: {'Mana': 7,
'Focus': 21,
'Agility': 22,
'Stamina': 21,
'Knowledge': 14,
'Strength': 15,
'Athletics': 9,
'Dexterity': 16,
'Creativity': 2,
'Adaptability': 11,
'Intelligence': 5},
29: {'Mana': 12,
'Focus': 25,
'Agility': 29,
'Stamina': 6,
'Knowledge': 7,
'Strength': 10,
'Athletics': 14,
'Dexterity': 15,
'Creativity': 6,
'Adaptability': 13,
'Intelligence': 29},
30: {'Mana': 21,
'Focus': 17,
'Agility': 8,
'Stamina': 21,
'Knowledge': 22,
'Strength': 22,
'Athletics': 26,
'Dexterity': 13,
'Creativity': 15,
'Adaptability': 24,
'Intelligence': 13}}
抱歉，代码块太长了，是的，我意识到 ID 不一定正确（希望使其可重现）。
所以我正在使用 itertools.permutations 将所有工人组合带到建筑物中：
import itertools
workers_ls = list(workers_dict.keys())
combinations = list(itertools.permutations(workers_ls, len(buildings_dict))
（我打算后面组合打分）
这显然从未完成 运行 因为它大约是 27！ = 1×10²⁸。 我想知道是否有另一种解决方案来解决我的问题，或者是否有一种方法可以在不经过所有组合的情况下确定最佳解决方案。 （我愿意使用其他编码语言工作）
谢谢！
我假设您想最大化总产量的总和。例如，当没有分配工人时，总产量为零（或某个不依赖于工人分配的常数）。如果将 Agility 2 和 Focus 3 的工人与属性为 [Agility, Focus] 的建筑物配对，则总产量将增加 2+3=5。
像这样的问题通常可以用线性规划来解决。我将使用 pulp 来帮助制定线性规划问题。我还建议检查 Julia 包 JuMP.
计算总产量的实际规则可能更复杂。如果 (1) 您可以定义一些生产矩阵的模拟，并且 (2) 总产量可以表示为（工人、建筑物）对的产量之和，您仍然可以使用线性规划。
这里有两种方法可以解决这个问题。第一个允许每个建筑物有多个工人，第二个不允许。
设置
import pandas as pd
import numpy as np
# !pip install pulp
import pulp
df_buildings = pd.DataFrame(buildings_dict).T
df_workers = pd.DataFrame(workers_dict).T
# there are a few typos, e.g. Strenght vs. Strength and Knowlege vs. Knowledge
# let's fix this first
df_workers.Knowledge.fillna(df_workers.Knowlege, inplace=True)
df_workers.Strength.fillna(df_workers.Strenght, inplace=True)
del df_workers["Strenght"], df_workers["Knowlege"]
# fixing some notation
workers = df_workers.index.tolist() # list of workers
buildings = df_buildings.index.tolist() # list of building
# next, we define production matrix
# production[i,j] will contain the productivity of
# worker i when assigned to building j
# you could vectorize this step, though it seems fast enough here
production = pd.DataFrame(index=workers, columns=buildings)
for i in df_workers.index:
for j in df_buildings.index:
production.loc[i, j] = df_workers.loc[i, df_buildings.loc[j]].sum()
print(production.head())
# 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 16 17
# 3 9 23 36 40 16 16 4 16 9 13 13 60 11 21 16 60 13
# 4 62 28 52 29 48 48 54 62 62 36 30 50 58 50 62 50 30
# 5 14 28 30 22 42 42 10 37 14 40 22 22 40 28 37 22 22
# 6 19 21 28 24 27 27 24 16 19 28 21 30 22 15 16 30 21
# 7 25 41 12 22 57 57 14 6 25 38 17 12 44 47 6 12 17
每栋建筑允许多名工人
prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)
# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")
# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
for i in workers for j in buildings)
# each worker can be assigned to at most one building:
for i in workers:
prob += sum(assignment[i][j] for j in buildings) <= 1
prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1
# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
if assignment[i][j].varValue == 1}
print(f"Total production is {prob.objective.value()}") # 1401
# here is the the solution
# assignment_dict_saved = {3: 12, 4: 1, 5: 5, 6: 16, 7: 5, 8: 6, 9: 2, 10: 17, 11: 6, 12: 10, 13: 4, 14: 6, 15: 3, 17: 7, 18: 3, 19: 3, 20: 11, 21: 12, 22: 17, 23: 15, 24: 4, 25: 10, 26: 13, 27: 9, 28: 7, 29: 7, 30: 2}
每栋楼最多一名工人
prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)
# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")
# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
for i in workers for j in buildings)
# each worker can be assigned to at most one building:
for i in workers:
prob += sum(assignment[i][j] for j in buildings) <= 1
# each building has at most one worker
for j in buildings:
prob += sum(assignment[i][j] for i in workers) <= 1
prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1
# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
if assignment[i][j].varValue == 1}
# assignment_dict_saved = {3: 16, 4: 9, 7: 5, 8: 2, 10: 11, 11: 6, 12: 10, 14: 14, 18: 3, 19: 8, 20: 17, 21: 12, 23: 15, 24: 4, 26: 13, 27: 1, 29: 7}
print(f"Total production is {prob.objective.value()}") # 929
我们可以看到，当我们允许每个建筑物配备多个工人时，总产量会更高。这是意料之中的，因为最大化问题的约束较少。
我们还可以将优化后的生产与随机分配工人时的生产进行比较。垂直线对应于最佳生产。看来我们做的还不错。