我是一個(gè)完全的業(yè)余愛好者，沒有接受過正式培訓(xùn)，只是自學(xué)了一些 C# 和 Python有47個(gè)槽位。每一項(xiàng)必須填寫一項(xiàng)。這些插槽分為 8 組。項(xiàng)目被分為相同的 8 組。每個(gè)槽只能由同一組的一個(gè)項(xiàng)目填充。同一物品可用于填充多個(gè)插槽。每個(gè)項(xiàng)目由一個(gè)名稱、一個(gè)組和 9 個(gè)統(tǒng)計(jì)數(shù)據(jù)組成。item ("name", "group", "stat1", "stat2", "stat3", ..., "stat9")
exampleItem (exampleName, groupA, 3, 8, 19, ..., 431)每個(gè)槽由一個(gè) ID 和一個(gè)組組成。slot1 (1, groupC)讓每個(gè)槽填滿一個(gè)物品（遵循上述規(guī)則）。然后將每個(gè)不同的統(tǒng)計(jì)數(shù)據(jù)相加。stat1Total=item1(stat1)+item2(stat1)+item3(stat1)+...+item47(stat1)目標(biāo)是： -讓每個(gè)槽填滿相應(yīng)組的項(xiàng)目。（沒有空槽）- 讓 stat1Total、stat2Total 和 stat3Total 達(dá)到一定數(shù)量（stat1Goal、stat2Goal、stat3Goal）- 讓 stat1Total、stat2Total 和 stat3Total 盡可能少地超過該數(shù)量 -最大化所有其他 statTotal，并分別賦予權(quán)重輸出滿足上述目標(biāo)的最佳項(xiàng)目組合。（如果 2 個(gè)或更多組合同樣是最佳組合，則輸出所有組合。我嘗試搜索所有可能的組合以獲得最佳輸出，但總共有 2.16x10^16 種可能的組合，所以我認(rèn)為這是不可行的。現(xiàn)在我不知道如何解決這個(gè)問題，而且我對(duì)整數(shù)規(guī)劃的了解越多，我就越困惑。為了說明這個(gè)問題，我將給出一個(gè)包含 3 個(gè)槽、2 個(gè)組和 5 個(gè)項(xiàng)目的簡(jiǎn)化示例：SlotA、SlotB 和 SlotC 必須分別填充 5 個(gè)項(xiàng)目中的一個(gè)。Slot A 和SlotB 屬于組Group1，SlotC 屬于Group2。這些項(xiàng)目被分類到相同的組中。因此，我們有屬于 Group1 的 Item1、Item2 和 Item3，以及屬于 Group2 的 Item4 和 Item5。這意味著SlotA和SlotB只能由Item1、Item2和Item3填充。您可以將插槽想象為不同形狀的孔，并且具有適合這些孔的形狀的物品。您無法將星形釘放入方孔中，也無法將 Item5 放入 SlotB 中，因?yàn)樗贿m合。這些物品本身有不同的統(tǒng)計(jì)數(shù)據(jù)。對(duì)于此示例，我們假設(shè)每個(gè)項(xiàng)目?jī)H具有其所屬的組和 2 個(gè)統(tǒng)計(jì)數(shù)據(jù)：StatDark、StatLight。這些可以采用 0 到 10 之間的整數(shù)值。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)此示例的目標(biāo)是：- 用一個(gè)項(xiàng)目填充每個(gè)槽，同時(shí)遵守分組規(guī)則- 使所有選定項(xiàng)目的所有 StatDark 之和等于或大于 9- 將 StatDark 最小化為高于 9（每個(gè)高于 9 的 StatDark 都是無用和浪費(fèi)）-最大化所有選定項(xiàng)目的所有 StatLight 的總和在這種情況下，最佳解決方案是：SlotA & SlotB: Item2 & Item3SlotC: Item4以下是此示例的完整表格的鏈接：https://i.stack.imgur.com/TluHG.jpg我希望這個(gè)例子能讓問題更容易理解。
1 回答
慕碼人8056858
TA貢獻(xiàn)1803條經(jīng)驗(yàn) 獲得超6個(gè)贊
數(shù)學(xué)模型
我會(huì)引入一個(gè)二元變量：
x[i,j] = 1 if item i is assigned to slot j 0 otherwise
這是我們的第一個(gè)問題：有許多 (i,j) 組合是不允許的。智能模型會(huì)盡量不生成禁止的組合。因此我們需要實(shí)現(xiàn)一個(gè)稀疏變量而不是完全分配的變量。x[i,j]我們只想在為allowed(i,j)真時(shí)分配和使用。
此外，引入一個(gè)連續(xù)變量xstat[s]來計(jì)算每個(gè)統(tǒng)計(jì)數(shù)據(jù)的總值。
一旦我們有了這個(gè)，我們就可以寫下約束：
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
該目標(biāo)是兩個(gè)目標(biāo)的加權(quán)和：
minimize xstat['StatDark'] - 9
maximize xstat['StatLight']
所以我們這樣做：
maximize -w1*(xstat['StatDark'] - 9) + w2*xstat['StatLight']
對(duì)于用戶提供的權(quán)重 w1 和 w2。
這兩個(gè)問題讓問題變得更加復(fù)雜。此外，我們還需要對(duì)數(shù)據(jù)做一些工作，使其適合在優(yōu)化模型中使用。
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提供了一個(gè)方便的數(shù)據(jù)結(jié)構(gòu)來訪問統(tǒng)計(jì)貢獻(xiàn)：
{('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
添加回答
舉報(bào)
0/150
提交
取消