我是一個完全的業余愛好者，沒有接受過正式培訓，只是自學了一些 C# 和 Python有47個槽位。每一項必須填寫一項。這些插槽分為 8 組。項目被分為相同的 8 組。每個槽只能由同一組的一個項目填充。同一物品可用于填充多個插槽。每個項目由一個名稱、一個組和 9 個統計數據組成。item ("name", "group", "stat1", "stat2", "stat3", ..., "stat9")
exampleItem (exampleName, groupA, 3, 8, 19, ..., 431)每個槽由一個 ID 和一個組組成。slot1 (1, groupC)讓每個槽填滿一個物品（遵循上述規則）。然后將每個不同的統計數據相加。stat1Total=item1(stat1)+item2(stat1)+item3(stat1)+...+item47(stat1)目標是： -讓每個槽填滿相應組的項目。（沒有空槽）- 讓 stat1Total、stat2Total 和 stat3Total 達到一定數量（stat1Goal、stat2Goal、stat3Goal）- 讓 stat1Total、stat2Total 和 stat3Total 盡可能少地超過該數量 -最大化所有其他 statTotal，并分別賦予權重輸出滿足上述目標的最佳項目組合。（如果 2 個或更多組合同樣是最佳組合，則輸出所有組合。我嘗試搜索所有可能的組合以獲得最佳輸出，但總共有 2.16x10^16 種可能的組合，所以我認為這是不可行的?，F在我不知道如何解決這個問題，而且我對整數規劃的了解越多，我就越困惑。為了說明這個問題，我將給出一個包含 3 個槽、2 個組和 5 個項目的簡化示例：SlotA、SlotB 和 SlotC 必須分別填充 5 個項目中的一個。Slot A 和SlotB 屬于組Group1，SlotC 屬于Group2。這些項目被分類到相同的組中。因此，我們有屬于 Group1 的 Item1、Item2 和 Item3，以及屬于 Group2 的 Item4 和 Item5。這意味著SlotA和SlotB只能由Item1、Item2和Item3填充。您可以將插槽想象為不同形狀的孔，并且具有適合這些孔的形狀的物品。您無法將星形釘放入方孔中，也無法將 Item5 放入 SlotB 中，因為它不適合。這些物品本身有不同的統計數據。對于此示例，我們假設每個項目僅具有其所屬的組和 2 個統計數據：StatDark、StatLight。這些可以采用 0 到 10 之間的整數值。Item1(Group1, StatDark=3, StatLight=5)Item2(Group1, StatDark=7, StatLight=1)Item3(Group1, StatDark=2, StatLight=5)Item4(Group2, StatDark=1, StatLight=6)Item5(Group2, StatDark=2, StatLight=5)此示例的目標是：- 用一個項目填充每個槽，同時遵守分組規則- 使所有選定項目的所有 StatDark 之和等于或大于 9- 將 StatDark 最小化為高于 9（每個高于 9 的 StatDark 都是無用和浪費）-最大化所有選定項目的所有 StatLight 的總和在這種情況下，最佳解決方案是：SlotA & SlotB: Item2 & Item3SlotC: Item4以下是此示例的完整表格的鏈接：https://i.stack.imgur.com/TluHG.jpg我希望這個例子能讓問題更容易理解。
1 回答
慕碼人8056858
TA貢獻1803條經驗 獲得超6個贊
數學模型
我會引入一個二元變量：
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 pd
import pulp as lp
from io import StringIO
#----------------------------------------
# raw data
#----------------------------------------
itemData = pd.read_table(StringIO("""
Item Group StatDark StatLight
Item1 Group1 3 5
Item2 Group1 7 1
Item3 Group1 2 5
Item4 Group2 1 6
Item5 Group2 2 5
"""),sep="\s+")
slotData = pd.read_table(StringIO("""
Slot Group
SlotA Group1
SlotB Group1
SlotC Group2
"""),sep='\s+')
# minimum total of Dark
minDark = 9
# stats
stat = ['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 allowed
x = lp.LpVariable.dicts('x', [(i,j) for i,j in merged.index], cat='Binary')
# xstat[stat] = total accumulated values
xstat = 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 statLight
prob += -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 totals
for 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 Group1
Item2 SlotA Group1
SlotB Group1
Item3 SlotA Group1
SlotB Group1
Item4 SlotC Group2
Item5 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.6999999999999997
SUBJECT 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 = 0
VARIABLES
0 <= x_('Item1',_'SlotA') <= 1 Integer
0 <= x_('Item1',_'SlotB') <= 1 Integer
0 <= x_('Item2',_'SlotA') <= 1 Integer
0 <= x_('Item2',_'SlotB') <= 1 Integer
0 <= x_('Item3',_'SlotA') <= 1 Integer
0 <= x_('Item3',_'SlotB') <= 1 Integer
0 <= x_('Item4',_'SlotC') <= 1 Integer
0 <= x_('Item5',_'SlotC') <= 1 Integer
xstat_StatDark Continuous
xstat_StatLight Continuous
解決方案
解決方案如下所示：
Status: Optimal
Objective: 8.099999999999998
item slot
0 Item2 SlotB
1 Item3 SlotA
2 Item4 SlotC
添加回答
舉報
0/150
提交
取消