EMIS 3360 Fall 2001 Homework 1 Suggested Solutions 1) Let milk = gallons of milk purchased Let cheese = pounds of cheese purchased Let apples = pounds of apples purchased A correct LP formulation is: Minimize obj: milk + 2.5 cheese + 0.75 apples Subject To Protein_RDA: 40 milk + 20 cheese + 10 apples >= 80 Vitamin_A_RDA: 5 milk + 40 cheese + 30 apples >= 60 Vitamin_B_RDA: 20 milk + 30 cheese + 40 apples >= 50 Vitamin_C_RDA: 30 milk + 50 cheese + 60 apples >= 30 Bounds All variables are >= 0. An optimal solution is Variable Name Solution Value milk 1.565217 apples 1.739130 All other variables in the range 1-3 are zero. The optimal objective function value is given below: Primal - Optimal: Objective = 2.8695652174e+00 2) a) Let powerbar = the number of powerbars purchased LP formulation: Minimize obj: milk + 2.5 cheese + 0.75 apples + 1.5 powerbar Subject To Protein_RDA: 40 milk + 20 cheese + 10 apples + 10 powerbar >= 80 Vitamin_A_RDA: 5 milk + 40 cheese + 30 apples >= 60 Vitamin_B_RDA: 20 milk + 30 cheese + 40 apples >= 50 Vitamin_C_RDA: 30 milk + 50 cheese + 60 apples + 30 powerbar >= 30 Bounds All variables are >= 0. The optimal solution is the same: Variable Name Solution Value milk 1.565217 apples 1.739130 All other variables in the range 1-4 are zero. b) Even by reducing the price of the powerbar to $1, it is still too expensive to be included in an optimal diet. Minimize obj: milk + 2.5 cheese + 0.75 apples + powerbar Subject To Protein_RDA: 40 milk + 20 cheese + 10 apples + 10 powerbar >= 80 Vitamin_A_RDA: 5 milk + 40 cheese + 30 apples >= 60 Vitamin_B_RDA: 20 milk + 30 cheese + 40 apples >= 50 Vitamin_C_RDA: 30 milk + 50 cheese + 60 apples + 30 powerbar >= 30 Bounds All variables are >= 0. Solution: Primal - Optimal: Objective = 2.8695652174e+00 Variable Name Solution Value milk 1.565217 apples 1.739130 All other variables in the range 1-4 are zero. 3) Let x1 = tons of waste processed from factory 1 Let x2 = tons of waste processed from factory 2 Let x3 = tons of waste processed from factory 3 Minimize obj: 15 x1 + 10 x2 + 20 x3 Subject To reduction in pollutant 1: 0.1 x1 + 0.2 x2 + 0.4 x3 >= 30 reduction in pollutant 2: 0.45 x1 + 0.25 x2 + 0.3 x3 >= 40 Bounds All variables are >= 0. Primal - Optimal: Objective = 1.5769230769e+03 Variable Name Solution Value x1 7.692308 x2 146.153846 All other variables in the range 1-3 are zero. The proportionality assumption may not be realistic here. Processing 10 tons of waste probably costs less than 10 times the cost of processing one ton. Also, the pollution-reduction may not scale up. Thus, processing two tons of waste may only reduce the amount of pollutant 1 by 0.15 tons instead of 0.2. 4) a) Let x1 be the number of pounds of food 1 purchased Let x2 be the number of pounds of food 2 purchased LP Formulation: Minimize obj: 7 x1 + x2 Subject To Vitamin_A: 3 x1 + x2 >= 12 Vitamin_C: x1 + x2 >= 6 Bounds All variables are >= 0. Optimal Solution: Primal - Optimal: Objective = 1.2000000000e+01 Solution time = 0.00 sec. Iterations = 0 (0) Variable Name Solution Value x2 12.000000 All other variables in the range 1-2 are zero. b) New LP formulation: Minimize obj: 7 x1 + x2 Subject To Vitamin_A: 3 x1 + x2 = 12 Vitamin_C: x1 + x2 = 6 Bounds All variables are >= 0. Tried aggregator 1 time. Optimal Solution: Primal - Optimal: Objective = 2.4000000000e+01 Solution time = 0.00 sec. Iterations = 0 (0) Variable Name Solution Value x1 3.000000 x2 3.000000 By changing the constraints from >= to =, we make the feasible region smaller and reducing the size of the feasible region can never improve the objective function value. So, the new solution will either cost the same or more than the first solution. Since it is impossible to meet the constraints exactly with food 2, the Fundy's are now forced to buy some of the first food which is more expensive per unit of vitamin A than the second item. Thus, it is more expensive to meet the constraints exactly. 5) Let xij = number of workers who work shift i and j where shift 1 is from 12 a.m. to 6 a.m. shift 2 is from 6 a.m. to 12 p.m. shift 3 is from 12 p.m. to 6 p.m. shift 4 is from 6 p.m. to 12 a.m. Assume that all shift pairings are allowed. The possible shift pairings are 12, 13, 14, 23, 24 and 34 consecutive shifts: 12, 23, 34 and 14 pay = $12 per hour for 12 hours = $144. non consecutive shifts: 13, 14 and 24 pay = $18 hour for 12 hours = $216 objective function: minimize daily cost =144 (x12 + x14 + x23 + x34) +216 (x13 + x24) subject to x12 + x13 + x14 >= 15 (workers covering shift 1) x12 + x23 + x24 >= 5 (workers covering shift 2) x13 + x23 + x34 >= 12 (workers covering shift 3) x14 + x24 + x34 >= 6 (workers covering shift 4) xij >= 0 CPLEX Solution: Log started (V6.5.3) Fri Sep 8 19:18:32 2000 Problem 'temp.lp' read. Read time = 0.00 sec. Minimize obj: 144 x12 + 216 x13 + 144 x14 + 144 x23 + 216 x24 + 144 x34 Subject To shift1: x12 + x13 + x14 >= 15 shift2: x12 + x23 + x24 >= 5 shift3: x13 + x23 + x34 >= 12 shift4: x14 + x24 + x34 >= 6 Bounds All variables are >= 0. Solution Primal - Optimal: Objective = 3.3120000000e+03 Solution time = 0.00 sec. Iterations = 4 (2) Variable Name Solution Value x12 5.000000 x13 8.000000 x14 2.000000 x34 4.000000 All other variables in the range 1-6 are zero. Interpretation: 5 workers should work from 12 a.m. to 12 p.m. (shifts 1 and 2) 2 workers should work from 6 p.m. to 6 a.m. (shifts 1 and 4) 4 workers should work from 12 p.m. to 12 a.m. (shifts 3 and 4) 8 workers should work from 12 a.m. to 6 a.m. and then from 12 p.m. to 6 p.m. (shifts 1 and 3).