利用pulp解決線性規劃問題

Stardew Valley(星露谷物語) 在 nintendo switch 上架的消息刺激 Y.Cheung 又回鍋啦~這次想做出完美開局,於是在研究過wiki檔案後決定計算出在一個季度月內使用初始資金種植什麼農作物種多少最轉錢。不考慮跨季度農作物與季度月內收成後售出後增加的資金部分,並且默認每天晚上都會澆水讓其生長。

因此可以簡化為一個線性規劃問題。

首先,基本數據的錄入並存儲在mysql數據庫中。基本資料包含:農作物名稱,成長天數,持續生長天數,每季度月最大收穫次數,種子價格,售賣單價,生長季節,每季度月最大生長周期。

每季度月最大生長周期由以下公式計算值,其他可在wiki中找到值。

每季度月最大生長周期 = 成長天數 + ((每季度月最大收穫次數 - 1) * 持續生長天數)

然後,安裝pulp,開始設計模型。

PULP使用起來也很簡單,具體可以參看文檔給出的CASE STUDIES

用戶輸入三個參數:所持金額,農作天數(此處可做更多限制),季度月

在本問題中,先定義這是一個線性規劃求最大值的問題。

model = pulp.LpProblem("Profit maximising problem", pulp.LpMaximize)  

找出指定季度月中能種植的農作物作為元素集合(Ingredients)在pulp中處理為pulp.LpVariable.dicts。

ingredient_vars = pulp.LpVariable.dicts("Ingr", Ingredients, lowBound=0, cat='Integer')  

指定模型計算公式,pulp.lpSum 就是求和。profit是各農作物元素利潤的集合。單個農作物利潤的計算在模型建立之前已經計算出並暫存在變量profit中。利潤的計算方法區分一種多收的農作物與一種一收的農作物。

model += pulp.lpSum(profit[i] * ingredient_vars[i] for i in Ingredients), "profit"  

指定模型的限制條件,所持資金是固定的,即能夠購買的種子是有限制的。

model += pulp.lpSum(cost[i] * ingredient_vars[i] for i in Ingredients) <= money  

問題解決!

model.solve()  

最後,打印出最優解中各農作物元素名稱與數量值。

這個問題涉及到的因素很多,以後有時間可以再考慮更多的因素,讓結果更準確。