問題描述
上圖所示的Whiskas貓糧由Ben生産。Ben希望盡可能便宜地生産其貓糧,同時確定它們滿足罐頭上所示的規定的營養分析要求。是以,他們希望改變每種成分的使用量(主要成分是雞肉,牛肉,羊肉,大米,小麥和凝膠),同時仍要滿足其營養标準。
雞肉,牛肉和羊肉的成本分别為0.013美元,0.008美元和0.010美元,而大米,小麥和凝膠的成本分别為0.002美元,0.005美元和0.001美元。(所有成本均為每克。)在此練習中,我們将忽略維生素和礦物質成分。(無論如何,這些的任何費用都可能很小。)
每種成分都有助于最終産品中蛋白質,脂肪,纖維和鹽的總重量。下表列出了每克成分的貢獻(以克計)。
東西 | 蛋白 | 脂肪 | 纖維 | 鹽 |
---|---|---|---|---|
雞 | 0.100 | 0.080 | 0.001 | 0.002 |
牛肉 | 0.200 | 0.100 | 0.005 | 0.005 |
羊肉 | 0.150 | 0.110 | 0.003 | 0.007 |
白飯 | 0.000 | 0.010 | 0.100 | 0.002 |
麥麸 | 0.040 | 0.010 | 0.150 | 0.008 |
凝膠 | 0.000 | 0.000 | 0.000 | 0.000 |
簡化模型的建立
首先,我們将考慮一個簡化的問題,以建構一個簡單的Python模型。
定義決策變量
假設Whiskas希望僅使用兩種成分制作貓食:雞肉和牛肉。我們将首先定義決策變量:
- x1 = 一罐貓糧中雞肉的百分比
- x2 = 一罐貓糧中牛肉的比例
制定目标函數
- min 0.013x1+0.008x2
限制條件
這些變量的限制條件是它們必須總計為100,并且滿足營養要求:
1.000x1 + 1.000x2 = 100.0
0.100x1 + 0.200x2 >= 8.0
0.080x1 + 0.100x2 >= 6.0
0.001x1 + 0.005x2 <= 2.0
0.002x1 + 0.005x2 <= 0.4
解決方案
要獲得此線性程式的解決方案,我們可以使用Python編寫一個簡短的程式來調用PuLP的模組化函數,然後将其調用求解器。這将逐漸解釋如何編寫此Python程式。
pulp.LpProblem(name='NoName', sense=LpMinimize)
,用來建立優化問題,其函數的參數為name:
在lp檔案中寫入的問題名稱;sense:最大或者最小,可為LpMinimize\LpMaximize二者之一。
pulp.LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)
,其函數參數為name:
變量名;lowBound變量下界;upBound變量上界;cat變量類型,可以為LpInteger\LpBinary\LpContinuous三者之一;
e指明變量是否在目标函數和限制中存在,主要用來實作列生成算法。
例如:
LpVariable(“example”, None, 100)
或LpVariable(“example”, upBound = 100)
- 針對此問題的Code
# 1. 建立問題
prob = LpProblem("Bleding Problem", LpMinimize)
# 2. 建立變量
x1 = LpVariable("ChickenPercent", 0, None, LpInteger)
x2 = LpVariable("BeefPercent", 0)
# 3. 設定目标函數
prob += 0.013*x1 + 0.008*x2, "Total Cost of Ingredients per can"
# 4. 施加限制
prob += x1 + x2 == 100, "PercentagesSum"
prob += 0.100*x1 + 0.200*x2 >= 8.0, "ProteinRequirement"
prob += 0.080*x1 + 0.100*x2 >= 6.0, "FatRequirement"
prob += 0.001*x1 + 0.005*x2 <= 2.0, "FibreRequirement"
prob += 0.002*x2 + 0.005*x2 <= 0.4, "SaltRequirement"
# 5.求解
prob.solve()
# 6.列印求解狀态
print("Status:",LpStatus[prob.status])
# 7. 列印出每個變量的最優值
for v in prob.variables():
print(v.name, "=", v.varValue)
# 列印最優解的目标函數值
print("Total Cost of Ingredient per can = ", value(prob.objective))
全模型建立
現在,我們将使用所有變量完全解決問題。盡管可以在上面的方法中添加很少的内容來将其實作到Python中,但我們将尋找一種更好的方法,該方法不将問題資料和公式混為一談。這将使更改其他測試的任何問題資料變得更加容易。我們将通過代數定義問題開始相同的方法:
定義決策變量
确定Whiskas貓食問題的決策變量決策變量是我們罐頭中所含不同成分的百分比。
由于罐頭為100克,是以這些百分比還代表所含每種成分的克含量。
我們必須正式定義決策變量,并確定陳述我們使用的機關。
- x1 = 一罐貓糧中雞肉的比例
- x2 = 一罐貓糧中牛肉的比例
- x3 = 一罐貓糧中羊肉的比例
- x4 = 一罐貓糧中白飯的比例
- x5 = 一罐貓糧中麥麸的比例
- x6 = 一罐貓糧中凝膠 的比例
制定目标函數
制定Whiskas貓食問題的目标函數,目的是使每罐貓食的成分總成本最小化。我們知道每種成分每克的成本。我們确定每種成分在罐中的百分比,是以我們必須除以100,再乘以以g為機關的罐的重量。這将使我們獲得每種成分的重量(克)
- min 0.013x1+0.008x2 + 0.010x3 + 0.002x4 + 0.005x5 + 0.001x6
限制條件
制定限制Whiskas貓糧問題的限制是:
百分比之和必須組成整個罐(= 100%)。
滿足規定的營養分析要求。
“整個罐頭”的限制是:
- x1 + x2 + x3 + x4 + x5 + x6 = 100
為了滿足營養分析的要求,每100克中至少要有8克蛋白質,6克脂肪,但不超過2克纖維和0.4克鹽。
為了制定這些限制條件,我們利用了每種成分的上一個貢獻表。這使我們能夠對成分中蛋白質,
脂肪,纖維和鹽的總貢獻制定以下限制條件:
- 0.100x1 + 0.200x2 + 0.150x3 + 0.000x4 + 0.040x5 + 0.0x6 >= 8.0
- 0.080x1 + 0.100x2 + 0.110x3 + 0.010x4 + 0.010x5 + 0.0x6 >= 6.0
- 0.001x1 + 0.005x2 + 0.003x3 + 0.100x4 + 0.150x5 + 0.0x6 <= 2.0
- 0.002x1 + 0.005x2 + 0.007x3 + 0.002x4 + 0.008x5 + 0.0x6 <= 0.4
解決方案
在prob定義問題的變量或類型之前,将關鍵問題資料輸入字典。其中包括成分清單,其次是每種成分的成本,
以及四種營養素中每種成分的百分比。這些值是明确列出的,對程式設計知識很少的人很容易更改。成分是參考鍵
,數字作為資料。
Ingredients = ['CHICKEN', 'BEEF', 'MUTTON', 'RICE', 'WHEAT', 'GEL']
# A dictionary of the costs of each of the Ingredients is created
costs = {'CHICKEN': 0.013,
'BEEF': 0.008,
'MUTTON': 0.010,
'RICE': 0.002,
'WHEAT': 0.005,
'GEL': 0.001}
# A dictionary of the protein percent in each of the Ingredients is created
proteinPercent = {'CHICKEN': 0.100,
'BEEF': 0.200,
'MUTTON': 0.150,
'RICE': 0.000,
'WHEAT': 0.040,
'GEL': 0.000}
# A dictionary of the fat percent in each of the Ingredients is created
fatPercent = {'CHICKEN': 0.080,
'BEEF': 0.100,
'MUTTON': 0.110,
'RICE': 0.010,
'WHEAT': 0.010,
'GEL': 0.000}
# A dictionary of the fibre percent in each of the Ingredients is created
fibrePercent = {'CHICKEN': 0.001,
'BEEF': 0.005,
'MUTTON': 0.003,
'RICE': 0.100,
'WHEAT': 0.150,
'GEL': 0.000}
# A dictionary of the salt percent in each of the Ingredients is created
saltPercent = {'CHICKEN': 0.002,
'BEEF': 0.005,
'MUTTON': 0.007,
'RICE': 0.002,
'WHEAT': 0.008,
'GEL': 0.000}
prob = LpProblem("The Whiskas Problem", LpMinimize)
# Create the 'prob' variable to contain the problem data
prob = LpProblem("The Whiskas Problem", LpMinimize)
# A dictionary called 'ingredient_vars' is created to contain the referenced Variables
ingredient_vars = LpVariable.dicts("Ingr",Ingredients,0)
prob += lpSum([costs[i]*ingredient_vars[i] for i in Ingredients]), "Total Cost of Ingredients per can"
# The five constraints are added to 'prob'
prob += lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "PercentagesSum"
prob += lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0, "ProteinRequirement"
prob += lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0, "FatRequirement"
prob += lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0, "FibreRequirement"
prob += lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4, "SaltRequirement"
# 此後代碼和前面相同,這裡略寫