慕码人8056858
数学模型我会引入一个二元变量：x[i,j] = 1 if item i is assigned to slot j
0 otherwise这是我们的第一个问题：有许多 (i,j) 组合是不允许的。智能模型会尽量不生成禁止的组合。因此我们需要实现一个稀疏变量而不是完全分配的变量。x[i,j]我们只想在为allowed(i,j)真时分配和使用。此外，引入一个连续变量xstat[s]来计算每个统计数据的总值。一旦我们有了这个，我们就可以写下约束：sum( i | allowed(i,j), x[i,j] ) = 1 for all slots j (exactly one item in each slot) xstat[s] = sum( (i,j) | allowed(i,j), x[i,j] * stat[i,s]) (calculate total stats) xstat['StatDark'] >= 9 该目标是两个目标的加权和： minimize xstat['StatDark'] - 9 maximize xstat['StatLight']所以我们这样做： maximize -w1*(xstat['StatDark'] - 9) + w2*xstat['StatLight']对于用户提供的权重 w1 和 w2。这两个问题让问题变得更加复杂。此外，我们还需要对数据做一些工作，使其适合在优化模型中使用。Python代码import pandas as pdimport pulp as lpfrom io import StringIO#----------------------------------------# raw data#----------------------------------------itemData = pd.read_table(StringIO("""Item Group StatDark StatLightItem1 Group1 3 5Item2 Group1 7 1Item3 Group1 2 5Item4 Group2 1 6Item5 Group2 2 5"""),sep="\s+")slotData = pd.read_table(StringIO("""Slot GroupSlotA Group1SlotB Group1SlotC Group2"""),sep='\s+')# minimum total of DarkminDark = 9# statsstat = ['StatDark','StatLight']# objective weights# we have two objectives and there are trde offs between them.# here we use a simple weighted sum approach. These are the weights.w = {'StatDark':0.3, 'StatLight':0.7}#----------------------------------------# data prep#----------------------------------------# join on Group# we need to know which (Item,Slot) combinations are allowed.merged = pd.merge(itemData[['Item','Group']],slotData,on='Group').set_index(['Item','Slot']) items = itemData['Item']slots = slotData['Slot']# we will use the convention:# i : items# j : slots# s : stats# stat values# easy lookup of statv[(i,s)]itemData = itemData.set_index('Item')statv = {(i,s):itemData.loc[i,s] for i in items for s in stat}#----------------------------------------# MIP model#----------------------------------------# x[(i,j)] = 1 if item i is assigned to slot j# 0 otherwise# only use combinations (i,j) that are allowedx = lp.LpVariable.dicts('x', [(i,j) for i,j in merged.index], cat='Binary') # xstat[stat] = total accumulated valuesxstat = lp.LpVariable.dicts('xstat', [s for s in stat], cat='Continuous', lowBound = 0)prob = lp.LpProblem("assignItemsToSlots", lp.LpMaximize)# objective: weighted sum#----------# 1. minimize statDark exceeding minDark# 2. maximize statLightprob += -w['StatDark']*(xstat['StatDark'] - minDark) + w['StatLight']*xstat['StatLight']# constraints# -----------# each slot much have exactly one item# (but the same item can go to different slots)for j in slots: prob += lp.lpSum([x[(i,j)] for i,jj in merged.index if jj==j]) == 1# minimum total value for dark prob += xstat['StatDark'] >= minDark # calculate stat totalsfor s in stat: prob += xstat[s] == lp.lpSum([x[(i,j)]*statv[i,s] for i,j in merged.index])#----------------------------------------# solve problem#----------------------------------------prob.solve()# to show the log use # solve(pulp.PULP_CBC_CMD(msg=1))print("Status:", lp.LpStatus[prob.status])print("Objective:",lp.value(prob.objective))#----------------------------------------# solution#----------------------------------------assigned = []for i,j in merged.index: if lp.value(x[(i,j)]) > 0.5: assigned += [[i, j]]assigned = pd.DataFrame(assigned, columns=['item','slot'])print(assigned)讨论该表merged看起来像：Item Slot Group-----------------------Item1 SlotA Group1 SlotB Group1Item2 SlotA Group1 SlotB Group1Item3 SlotA Group1 SlotB Group1Item4 SlotC Group2Item5 SlotC Group2 Item,Slot 列为我们提供了允许的组合。该字典statv提供了一个方便的数据结构来访问统计贡献：{('Item1', 'StatDark'): 3, ('Item1', 'StatLight'): 5, ('Item2', 'StatDark'): 7, ('Item2', 'StatLight'): 1, ('Item3', 'StatDark'): 2, ('Item3', 'StatLight'): 5, ('Item4', 'StatDark'): 1, ('Item4', 'StatLight'): 6, ('Item5', 'StatDark'): 2, ('Item5', 'StatLight'): 5}生成的 MIP 模型如下所示：assignItemsToSlots:MAXIMIZE-0.3*xstat_StatDark + 0.7*xstat_StatLight + 2.6999999999999997SUBJECT TO_C1: x_('Item1',_'SlotA') + x_('Item2',_'SlotA') + x_('Item3',_'SlotA') = 1_C2: x_('Item1',_'SlotB') + x_('Item2',_'SlotB') + x_('Item3',_'SlotB') = 1_C3: x_('Item4',_'SlotC') + x_('Item5',_'SlotC') = 1_C4: xstat_StatDark >= 9_C5: - 3 x_('Item1',_'SlotA') - 3 x_('Item1',_'SlotB') - 7 x_('Item2',_'SlotA') - 7 x_('Item2',_'SlotB') - 2 x_('Item3',_'SlotA') - 2 x_('Item3',_'SlotB') - x_('Item4',_'SlotC') - 2 x_('Item5',_'SlotC') + xstat_StatDark = 0_C6: - 5 x_('Item1',_'SlotA') - 5 x_('Item1',_'SlotB') - x_('Item2',_'SlotA') - x_('Item2',_'SlotB') - 5 x_('Item3',_'SlotA') - 5 x_('Item3',_'SlotB') - 6 x_('Item4',_'SlotC') - 5 x_('Item5',_'SlotC') + xstat_StatLight = 0VARIABLES0 <= x_('Item1',_'SlotA') <= 1 Integer0 <= x_('Item1',_'SlotB') <= 1 Integer0 <= x_('Item2',_'SlotA') <= 1 Integer0 <= x_('Item2',_'SlotB') <= 1 Integer0 <= x_('Item3',_'SlotA') <= 1 Integer0 <= x_('Item3',_'SlotB') <= 1 Integer0 <= x_('Item4',_'SlotC') <= 1 Integer0 <= x_('Item5',_'SlotC') <= 1 Integerxstat_StatDark Continuousxstat_StatLight Continuous解决方案解决方案如下所示：Status: OptimalObjective: 8.099999999999998 item slot0 Item2 SlotB1 Item3 SlotA2 Item4 SlotC
