System Optimization: LP (Linear Programming) Example

Leaders for Manufacturing Mid Term Solution FORMULATION Decision variables (5 points): there are decision variables for vegetables planted, for tomatoes sold, for tomatoes frozen, for soup made and sold. All variables are non negative. Define X1, X2, X3, X4, X5, X6 – number of plants to grow, for beefsteak tomato, better boy tomato, … green pepper, respectively. (units are number of plants) T7, T8, … T20 – pounds of tomatoes to sell in weeks 7, 8, … 20. F7, F8, … F20 - pounds of tomatoes to freeze in weeks 7, 8, … 20. S9, S8, … S16 – pounds of soup to make in week 9, 10, … 16. Y – pounds of soup to sell. Constraints (20 points): there are resource constraints, balance constraints for tomatoes, and supply constraints for soup. Resource constraints There are only 2000 square feet for planting: 9 X1 + 8 X2 + … + 3 X6 £ 2000. There are only 25 hours of labor each week: 0.1 X1 + 0.1 X2 + … + 0.05 X6 £ 25. Tomato balance constraints In each week, tomatoes produced equals tomatoes consumed by Mr. Smith, or frozen, or sold. 1.5 X3 – Ti – Fi = 10 2 X2 + 1.5 X3 – Ti – Fi = 10 2 X1 + 2 X2 + 1.5 X3 – Ti – Fi = 10 2 X1 + 2 X2 – Ti – Fi = 10 1 for i = 7, 8, 9 for i = 10 for i = 11, 12 … 16 for i = 17 2 X1 – Ti – Fi = 10 for i = 18, 19, 20 There is also a demand constraint as Mr. Smith needs 250 pounds of frozen tomatoes. F7 + F8 + … +F20 ≥ 250. Soup supply constraints Each week the amount of soup made is limited by the ingredients, that need be supplied according to the recipe. One can deduce that soup can only be made in weeks 9, 10, … 16, due to the requirement to use fresh ingredients. The amount made cannot exceed the available supply of ingredients. Since one eggplant bush yields one pound of vegetable each week and one pound of eggplant is needed to produce four pounds of soup, then one eggplant bush is needed for every four pounds of soup that we make. Similarly we need one zucchini plant to make twelve pounds of soup, and one green pepper plant for every two pounds of soup we make. 4 X4 – Si ≥ 0 12 X5 – Si ≥ 0 2 X6 – Si ≥ 0 for i = 9, 10, … 16. We need 200 pounds of soup for winter and can sell up to 2000 pounds of soup: S9 + S10 + … + S16 – Y ≥ 200, and Y £ 2000. Objective function (10 points): The objective is to maximize revenue net of operating costs. Mr. Smith gets revenue from selling tomatoes according to the declining price schedule, and from selling soup a $5 per pound: Revenue($) = 4 T7 + … + 3.2 T11 + … + 2.2 T16 + … 1.4 T20 + 5 Y Mr. Smith has a labor cost for each plant. For instance, for each Beefsteak plant, he requires 0.1 hours of labor each week for 20 weeks, at a cost of $8 per hour. Thus the labor cost is $16 per Beefsteak plant for the season. Cost($) = 16 X1 + 16 X2 + 24 X3 + 8 X4 + 8 X5 + 8 X6 The objective is to maximize Revenue – Cost. 2 SOLUTION (15 points) The optimal solution is given by Beefsteak tomato Better Boy tomato Rutgers tomato Eggplant Zucchini Green Pepper Number of plants 67.5 19.3 6.7 68.8 22.9 137.5 Tomatoes sold Week 7 Week 8 Week 9 Week 10 Week 11 Week 12 Week13 Week 14 Week 15 Week 16 Week 17 Week 18 Week 19 Week 20 Tomatoes frozen Soup Made 275 275 275 275 275 275 275 275 38.5 173.5 173.5 173.5 173.5 173.5 173.5 163.5 125 125 125 At the end of the season 2000 pounds of soup are sold. The net revenue to Mr. Smith from this plan is $10112.83. 3 Extra Labor (10 points): Mr. Smith should not seek extra labor as the optimal plan only requires 21 hours now, and there is five hours of slack. The shadow price of additional labor is zero. More Space (15 points): As shown below, the shadow price for more space is $3.40 per square foot. This shadow price is valid for an increase of 309 square feet. Thus, you can’t answer the question without re-running the solver. Cell $C$9 Name garden area Final Value Shadow Price Constraint R.H. Side Allowable Increase Allowable Decrease 2000 3.40 2000 309.17 154.17 When one re-runs the problem with 310 more square feet of space (total equals 2310), the shadow price for space drops to $3.20 per square foot, and this is valid between 309 and 367 additional square feet. Cell $C$9 Name garden area Final Value Shadow Price Constraint R.H. Side Allowable Increase Allowable Decrease 2310 3.2 2310 57.08 0.83 When one re-runs the problem with 368 more square feet of space, the shadow price drops to zero, as the space constraint is no longer binding; the solution remains unchanged for any amount of additional space beyond 368 square feet. With 367 more square feet of space, the profit is $11349.33, an increase of $1236.67. This is the most that Mr. Smith would pay for 500 square feet of space. Indeed, he would be willing to pay as much as $3.40 per square foot for the first 309 square feet, and then $3.20 per square feet for the next 58 square feet. But he would not pay anything for incremental space beyond 367 square feet. He will use the additional land to modify the mix of Beefsteak tomatoes and Better Boy tomatoes. The number of Rutgers tomatoes, eggplant, zucchini and green peppers remain the same. The table below shows how the plant mix changes as the size of the garden expands. Beef Steak Better Boy 2000 square feet 67.5 19.3 2309 square feet 67.5 57.9 2367 square feet 125.4 0 As one initially adds space, the extra space is used to plant more Better Boy tomatoes, and ultimately to sell more tomatoes. This is because the revenue per square foot for Better Boy is higher than for Beef steak (once we have satisfied the requirement for frozen tomatoes). However, after we add 309 square feet, then the labor constraint is binding. As we add additional space, we actually reduce the number of Better Boy plants and increase the number of Beef Steak plants. For each additional square foot we substitute one Beef 4 Steak for one Better Boy, since each require the same amount of labor but Beef steak requires one more square foot than Better Boy. Profit goes up since a single Beef Steak plant generates more revenue than a single Better Boy plant. This substitution stops after we add 58 more square feet since the number of Better Boy plants is now zero. Tomato Purchases (15 points): The following table shows the non-zero reduced costs for the decision variable for selling tomatoes for the optimal solution. In all of the other weeks the reduced cost is zero. Cell Name $N$17 week 9 sell tom $N$27 week 19 sell tom $N$28 week 20 sell tom Final Value Reduced Cost Objective Coefficient Allowable Increase Allowable Decrease 0.00 0.00 0.00 -0.87 -0.05 -0.25 3.60 1.60 1.40 0.87 0.05 0.25 1E+30 1E+30 1E+30 These reduced costs suggest that Mr. Smith might want to buy tomatoes in weeks 9, 19, and 20. We can also look at the shadow prices for the tomato balance constraints, which indicate the impact on profit from having to supply one more pound of tomatoes. These shadow prices exceed the market price for tomatoes in weeks 9, 19 and 20, which suggests that Mr. Smith would want to buy tomatoes in these weeks. To confirm this intuition, we can re-solve the LP – where we add a set of variables to denote buying tomatoes in each week. The tomato balance constraints are now modified, e.g., for weeks 11, 12…16: 2 X1 + 2 X2 + 1.5 X3 – Ti – Fi + Bi = 10 for i = 11, 12 … 16 where Bi is the amount bought in week i. The garden plan is now beefsteak betterboy rutgers 0 101.04 eggplant zucchini 0 68.75 green pepper 22.92 137.5 With a profit of 10187. Furthermore, Mr Smith buys 10 pounds of tomatoes in weeks 7, 8, 9, 18, and 19, and then buys 260 pounds in week 20. It is cheaper for Mr. Smith to buy tomatoes in these weeks, rather than plant Rutgers plants for the early weeks or plant Beef Steaks for the last weeks of the season. Soup Sale (10 points) From the sensitivity report, we get the reduced cost for the upper bound on the amount of soup sold: Cell 5 Name Final Value Reduced Cost Objective Coefficient Allowable Increase Allowable Decrease $L$6 soup sold 2000.00 2.33 5.00 1E+30 This tells us that if we could sell an incremental pound of soup for $5, then our total profit increases by $2.33. So if we were to sell the incremental pound of soup for $3, then our profit increases by $0.33. So the proposed contract has potential to be of interest. The above sensitivity information does not tell us the range over which the reduced cost is valid. So we need to re-solve the LP. When we do, we get a new garden plan: beefsteak betterboy rutgers 67.5 5.73 6.67 eggplant zucchini 75 25 green pepper 150 With a profit of $10177.83. We take the contract for 200 additional pounds of soup. Consequently we increase the amount of the garden used for eggplant, zucchini, and green peppers so as to make 200 more pounds of soup. We make 300 pounds of soup in each week from week 9 to week 16. We still plant 67.5 Beef Steak and 6.67 Rutgers – so as to satisfy Mr. Smith’s requirements. We reduce the number of Better Boy plants, and thus reduce the amount of tomatoes that we sell. 6 2.33