펄프 LP 최소화 "하나의 유형 선택"제약 조건

Question

아래의 코드는 특정 식품, 영양가 및 비용이있는 경우 LP 최소화 문제를 실행하는 데 사용됩니다. 코드는 현재 제시된 상태에서 작동합니다. 한 가지 유형의 제약 조건을 추가하려고합니다. 나는 모든 음식을 그들의 범주 (아침, 점심, 저녁, 스낵)로 나누었다. 제약을 만들고 싶습니다. 아침, 점심, 저녁 식사 중 하나만 선택할 수 있습니다. (간식에 대한 제한 없음). "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 제약"으로이를 수행 할 수 있습니다.

각 유형의 음식에 대한 결정의 합계를 나타내는 파이썬 변수를 만듭니다. breakfast_sum, lunch_sum 등

그런 다음 펄프 이진 변수를 만들 breakfast_binary, lunch_binary 등

우리는 breakfast_sum은 0 그런 다음 우리는 또 다른를 사용하는 것보다보다 때 breakfast_binary "플립"을 가지고 큰 M 제약 조건을 사용합니다

제약 조건은 이진 변수의 합이 < = 1이되도록하십시오.

M은 기본적으로 큰 숫자입니다. 얼마나 커야합니까? 각 아침 식사 품목을 2 인분 이상 할당하지 않으므로 M = 2 * {아침 식사 품목 수}를 사용해보십시오. 이제이 제약 조건을 살펴보십시오.

M * breakfast_binary >= breakfast_sum.

breakfast_sum 다음, 0 당신이 아침 식사 항목의 게재를 할당으로 breakfast_binary이 가 즉시 0으로을 허용하는 경우는, breakfast_binary 1.

점심이 작업을 수행, 저녁 식사 등을 플립 강제로 이진 변수의 합이 < = 1

이 대답은 존 포먼에 의해 4 장 데이터의 "최적화 모델링"스마트에서 자유롭게 의역 것으로, 다음 추가 제약 조건을 가지고있다. 나는 그것을 매우 추천한다.