紙漿LP最小化制定「選擇一種類型」約束

Question

下面的代碼用於運行LP最小化問題，其中我們有某些食物，它們的營養價值和成本。代碼目前在所呈現的狀態下工作。我正在嘗試添加更多類型的約束。我把所有的食物分成他們的類別（早餐，午餐，晚餐，小吃）。我想創建一個約束，其中只有1早餐，午餐和晚餐項目可以選擇。 （零食無限制）。如果物品是（早餐，午餐，晚餐或小吃），取決於它在陣列中的位置，「1」和「0」對應。

from pulp import * 

Food = ["Bacon", "Eggs", "Pancakes", "Waffles", "Yogurt", "Bagels", "Sausage", "Cheerios", 
    "Strawberries", "Milk", "OJ", "Oranges", "Apples", "Carrots", "Broccoli","Ham", "Turkey", 
    "Steak", "Salmon", "Pasta","Chicken", "Pizza", "Rice", "Salad", "Potatoes"] 

nutrition = ["Calories", "Protein", "Sugars", "Cholesterol", "Vitamin_A", "Vitamin_B", "Vitamin_C", 
     "Vitamin_K", "Vitamin_E", "Zinc", "Iron", "Fat", "Sodium", "Carbs", "Fiber", 
     "Calcium", "Potassium", "Folic_acid", "Thiamin"] 

Category = ["Breakfast", "Lunch", "Dinner", "Snack"] 

VarCategory = [[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1], 
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] 
VarCategory = makeDict([Category, Food], VarCategory) 


VarNutrition = [[45, 367, 84.3, 212, 250, 72.3, 150, 103, 49, 100, 134, 85.1, 52.8, 5.3, 30.9, 290, 280, 412, 159, 288, 231, 324, 428, 370, 403], 
      [3, 24, 2.3, 5.3, 10.7, 2.8, 6, 3.2, 1, 8, 1, 1.3, 0.3, 1.1, 2.6, 18, 18, 21, 24.9, 12, 43.4, 13.9, 19.2, 20, 13.7], 
      [0, 4, 0, 5.2, 46.7, 0, 1, 1.1, 7, 13, 23.3, 16.9, 11.1, 0.7, 1.5, 6, 5, 0, 0, 11, 0, 4.1, 13.8, 1, 0], 
      [3, 86, 7, 0, 3, 2, 10, 0, 0, 3, 0, 0, 0, 0, 0, 8, 7, 61, 10, 10, 40, 9, 18, 13, 7], 
      [0, 23, 2, 20, 2, 1, 4, 16, 0, 10, 2, 8, 1, 41, 11, 6, 6, 0, 2, 10, 1, 6, 41, 10, 34], 
      [0, 20, 1, 19, 12, 1, 0, 27, 2, 0, 31, 2.5, 1, 1, 4, 0, 0, 50, 50, 12, 25, 10, 23, 0, 22], 
      [0, 1, 1, 2, 3, 0, 0, 11, 149, 0, 62, 139, 7, 1, 135, 35, 35, 0, 0, 10, 0, 0, 17, 30, 81], 
      [0, 11, 0, 0, 0, 0, 0, 1, 4, 0, 0, 0, 1, 2, 116, 0, 0, 4, 0, 10, 1, 8, 16, 0, 0], 
      [0, 12, 0, 0, 0, 0, 0, 1, 2, 0, 0, 2, 0, 0, 4, 0, 0, 4, 9, 10, 2, 6, 4, 0, 0], 
      [0, 15, 1, 3, 12, 1, 0, 30, 1, 0, 0, 1, 0, 0, 2, 0, 0, 69, 3, 10, 9, 10, 9, 0, 14], 
      [0, 15, 4, 20, 1, 6, 4, 49, 3, 0, 2, 1, 0, 1, 4, 20, 20, 28, 6, 10, 8, 16, 7, 8, 18], 
      [6, 41, 5, 11, 4, 1, 22, 3, 1, 4, 0, 1, 0, 0, 1, 8, 7, 25, 9, 20, 8, 19, 8, 29, 33], 
      [6, 26, 7, 12, 6, 5, 15, 8, 0, 5, 0, 0, 0, 0, 1, 53, 42, 3, 44, 50, 4, 25, 47, 59, 20], 
      [0, 2, 4, 11, 16, 5, 0, 7, 4, 4, 11, 7, 5, 0, 2, 15, 15, 0, 0, 10, 0, 13, 25, 10, 16], 
      [0, 0, 0, 8, 0, 2, 0, 11, 12, 0, 2, 18, 6, 2, 9, 16, 16, 0, 0, 30, 0, 7, 10, 0, 0], 
      [0, 16, 8, 4, 37, 0, 2, 11, 2, 30, 0, 8, 1, 0, 4, 6, 6, 1, 1, 0, 2, 15, 4, 4, 34], 
      [0, 9, 1, 4, 14, 1, 0, 5, 7, 0, 3, 9, 3, 1, 8, 0, 0, 14, 7, 10, 10, 6, 12, 0, 41], 
      [0, 17, 3, 10, 6, 6, 0, 68, 9, 0, 2, 8, 0, 1, 14, 0, 0, 5, 1, 20, 1, 0, 15, 0, 15], 
      [0, 8, 5, 21, 6, 9, 0, 36, 2, 0, 63, 12, 1, 0, 4, 0, 0, 9, 2, 10, 7, 14, 17, 0, 18]] 
VarNutrition = makeDict([nutrition, Food], VarNutrition) 

ConstraintsLow = [2000, 72, 0, 85, 100, 100, 100, 100, 100, 0, 0, 0, 0, 90, 100, 100, 100, 100, 100] 
ConstraintsLow = makeDict([nutrition],ConstraintsLow) 



Cost = [1.22, 1.56, 6.79, 6.79, 1.00, 2.50, 2.00, 0.14, 1.37, 1.69, 1.99, 0.50, 0.50, 0.50, 0.50, 4.25, 4.25, 4.00, 5.00, 7.00, 3.18, 1.25, 5.00, 6.00, 3.00] 
Cost = makeDict([Food], Cost) 

prob = LpProblem("Nutrition Calculator", LpMinimize) 

vars = LpVariable.dicts("Servings of", (Food), 0, None, LpContinuous) 
Svars = LpVariable.dicts("Food Chosen", (Category, Food), 0, None, LpBinary) 

prob += lpSum(vars[i]*Cost[i] for i in Food) 

for j in nutrition: 
    prob += lpSum([vars[i]*VarNutrition[j][i] for i in Food]) >= ConstraintsLow[j] 


for i in Food: 
    prob += vars[i] >= 0 
    prob += vars[i] <= 2 




print (prob) 
prob.writeLP("Nutrition.lp") 
prob.solve() 
print ("Status:", LpStatus[prob.status]) 
for v in prob.variables(): 
    print (v.name, "=", v.varValue) 
print ("Total Cost = ", value(prob.objective)) 

我遇到的問題是創建這樣一個約束。我以爲使用二進制變量，但我不知道如何實現。任何幫助，將不勝感激

Answer 1

你應該做的是有二元變量爲每種類型的食物被選中，然後約束他們的總和爲1 - 意味着剛好一個二進制變量是1和其他是0.

問題是，例如，使早餐二元變量打開意味着在你的線性程序中存在一個if-then條件。如果至少有一個早餐項目被選中，則早餐爲1，否則爲0. if-then語句不是線性的，所以我們需要一種巧妙的方式來使這種線性。我們可以用「大M約束」來做到這一點。

使python變量代表每種食物的決定總和，例如， breakfast_sum，lunch_sum等

然後使紙漿二元變量breakfast_binary，lunch_binary等

我們將使用大M約束有breakfast_binary「翻轉」的時候breakfast_sum大於0。然後，我們會使用其他約束來確保二進制變量< = 1的總和。

M基本上是一個很大的數字。它需要多大？請注意，您永遠不會分配每份早餐項目超過2份，因此請嘗試製作M = 2 * {早餐項目數量}。現在看看這個約束：

M * breakfast_binary >= breakfast_sum。

如果breakfast_sum爲0，則breakfast_binary是允許爲0。只要你分配一個早餐項目的服務，breakfast_binary被迫翻轉到1

午餐做到這一點，晚餐等，然後有一個額外的約束二元變量的總和< = 1

此答案由約翰·福爾曼從優從4章數據的「優化模型」智能複述。我強烈推薦它。