Optimization Methods in Management Science, Recitation 4 Solutions

Optimization Methods in Management Science MIT 15.053 Recitation 4 At the end of this recitation, students should be able to: 1. Interpret the solution and sensitivity report of a problem to take decisions related to modifications in the problem data. 2. Be able to determine the shadow prices, price an activity, determine allowed one-at-a-time changes in the tableau. Problem 1 (Problem 3 of Applied Mathematical Programming, Chapter 3) Jean-Pierre Leveque has recently been named the Minister of International Trade for the new nation of New France. In connection with this position, he has decided that the welfare of the country (and his performance) could best be served by maximizing the net dollar value of the country’s exports for the coming year. (The net dollar value of exports is defined as exports less the cost of all materials imported by the country.) The area that now constitutes New France has traditionally made three products for export: steel, heavy machinery, and trucks. For the coming year, Jean-Pierre feels that they could sell all that they could produce of these three items at existing world market prices of $900/unit for steel, $2,500/unit for machinery, and $3,000/unit for trucks. In order to produce one unit of steel with the country’s existing technology, it takes 0.05 units of machinery, 0.08 units of trucks, two units of ore purchased on the world market for $100/unit, and other imported materials costing $100. In addition, it takes .5 man-years of labor to produce each unit of steel. The steel mills of New France have a maximum usable capacity of 300,000 units/year. To produce one unit of machinery requires .75 units of steel, 0.12 units of trucks, and 5 man-years of labor. In addition, $150 of materials must be imported for each unit of machinery produced. The practical capacity of the country’s machinery plants is 50,000 units/year. In order to produce one unit of trucks, it takes one unit of steel, 0.10 units of machinery, three man-years of labor, and $500 worth of imported materials. Existing truck capacity is 550,000 units/year. The total manpower available for production of steel, machinery, and trucks is 1,200,000 men/year. To help Jean-Pierre in his planning, he had one of his staff formulate with Excel the model shown in Figure 1 and solved in Figure 2. A sensitivity report is given in Figure 3. The variables are labeled as follows: ExportSteel = Steel production for export, ExportMachinery = Machinery production for export, ExportTruck = Truck production for export, ProdSteel = Total steel production, ProdMachinery = Total machinery production, ProdTruck = Total truck production. ExportSteel ExportMachinery ExportTruck ProdSteel ProdMachinery ProdTruck Variables NetExports OutputSteel OutputMachinery OutputTruck CapacitySteel CapacityMachinery CapacityTruck CapacityManpower 0 0 0 0 0 0 900 2500 3000 -300 -150 -500 -1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1 0 0 0 0 1 -0.05 -0.08 1 0 0 0.5 -0.75 1 -0.12 0 1 0 5 -1 -0.1 1 0 0 1 3 Rel = = = <= <= <= <= Capacity 0 0 0 300000 50000 550000 1200000 Figure 1: Formulation sheet for Problem 1. The constraints have labels: OutputSteel, CapacitySteel, OutputMachinery, CapacityMachinery, OutputTruck, CapacityTruck, CapacityManpower. Referring to the three figures, he has asked you to help him with the following questions: (a) What is the optimal production and export mix for New France, based on Fig. 2? What would be the net dollar value of exports under this plan? In your answer, identify clearly how much is produced of each product, and how much is exported. You should also clearly state what units you are using for each item produced or exported. Solution. The optimal production mix is 300,000 unit of steel, 50,000 units of ma­ chinery, and 262,500 units of trucks. In terms of export, 8,750 units of machinery and 232,500 units of trucks should be exported. The net value of the exports is $490,625,000. (b) What do the first three constraint equations (OutputSteel, OutputMachinery, and OutputTruck) represent? Why are they equality constraints instead of ≤ constraints? Solution. The three equations are balance constraints that represent the relationship between total production and exports for each product. In particular, the number of exported units of product P is equal to the number of units of P produced, minus the units of P that are employed in the production of the remaining products. These are equality constraints instead of ≤ constraints because we assume that New France can sell all it produces, therefore to maximize profit we are interested in exporting everything that is produced and is not employed internally for manufacturing other products. In other words, there is no net change in inventory. (c) The optimal solution suggests that New France produce 50,000 units of machinery. How are those units to be utilized during the year? Solution. Of those 50,000 units, 15,000 are employed for steel production, 26,250 are employed for truck production, and 8750 should be exported. 2 Objective Cell (Max) Cell Name $C$16 NetExports Original Value 0 Final Value 490625000 Variable Cells Cell Name $C$3 ExportSteel $D$3 ExportMachinery $E$3 ExportTruck $F$3 ProdSteel $G$3 ProdMachinery $H$3 ProdTruck Original Value 0 0 0 0 0 0 Final Value Cell Value Formula $C$18=$E$18 $C$19=$E$19 $C$20=$E$20 $C$21<=$E$21 $C$22<=$E$22 $C$23<=$E$23 $C$24<=$E$24 Constraints Cell Name $C$18 OutputSteel $C$19 OutputMachinery $C$20 OutputTruck $C$21 CapacitySteel $C$22 CapacityMachinery $C$23 CapacityTruck $C$24 CapacityManpower 0 0 0 300000 50000 262500 1187500 0 8750 232500 300000 50000 262500 Integer Contin Contin Contin Contin Contin Contin Status Binding Binding Binding Binding Binding Not Binding Not Binding Slack 0 0 0 0 0 287500 12500 Figure 2: Solution sheet for Problem 1. (d) What would happen to the value of net exports if the world market price of steel increased to $1250/unit and the country chose to export one unit of steel? Solution. The original market price of steel is of $900/unit, and this yields a reduced cost of -$1,350/unit at the optimum. From Fig. 3, we see that the objective function coefficient for ExportSteel can be increased by 1350 units without changing the optimal production mix. Therefore, an increase of $(1250-900)=$350 falls within the allowed range. It follows that the reduced cost of ExportSteel will be $(-1350 + 350)=-$1,000/unit after the increase. Exporting one unit of steel would decrease the total profit (i.e. objective function value) by $1,000, to $490,624,000. (e) New France wants to identify other products it can profitably produce and export, i.e. include in the optimal production mix. Among the four possible resources (steel, machinery, trucks, manpower), there is one which is the least preferable to be used by new products, and should be used as sparingly as possible. Identify this resource and explain your choice. Solution. The shadow price for CapacitySteel is the largest among the capacity con­ straints for the four resources ($1585/unit versus $302.5/unit for Machinery and 0 for 3 Variable Cells Cell $C$3 $D$3 $E$3 $F$3 $G$3 $H$3 Final Value Name ExportSteel ExportMachinery ExportTruck ProdSteel ProdMachinery ProdTruck 0 8750 232500 300000 50000 262500 Reduced Objective Allowable Allowable Cost Coefficient Increase Decrease -1350 900 1350 1E+30 0 2500 10566.66667 281.3953488 0 3000 347.7011494 1350 0 -300 1E+30 1585 0 -150 1E+30 302.5 0 -500 403.3333333 1350 Constraints Cell $C$18 $C$19 $C$20 $C$21 $C$22 $C$23 $C$24 Name OutputSteel OutputMachinery OutputTruck CapacitySteel CapacityMachinery CapacityTruck CapacityManpower Final Value 0 1.45519E-11 1.16415E-10 300000 50000 262500 1187500 Shadow Constraint Allowable Allowable Price R.H. Side Increase Decrease -2250 0 232500 4166.666667 -2500 0 8750 1E+30 -3000 0 232500 1E+30 1585 300000 3571.428571 252717.3913 302.5 50000 4545.454545 8139.534884 0 550000 1E+30 287500 0 1200000 1E+30 12500 Figure 3: Sensitivity report for Problem 1. Truck and Manpower). Therefore, using up units of Steel is the most expensive possibil­ ity. For this reason, new products should try to use as few units of steel as possible. (f) There is a chance that Jean-Pierre may have $500,000 to spend on expanding capacity. If this investment will buy 500 units of truck capacity, 1,000 units of machine capacity, or 300 units of steel capacity, what would be the best investment? Solution. Fig. 3 shows that the three proposed increases in capacity all fall within the allowed increases. This means that the shadow price for the constraints will not change if one of the constraint rhs is modified as proposed. It follows that we can compute the profit increase by simply multiplying the rhs increase by the shadow price of the corresponding constraint. Namely: Steel = 1, 585 × 300 = 475, 500 Machinery = 302.5 × 1, 000 = 302, 500 Truck = 0 × 500 = 0. Increasing the Steel capacity is clearly the best option. (g) If the world market price of the imported materials needed to produce one unit of trucks were to increase by $400, what would be the optimal export mix for New France, and what would be the dollar value of their net exports? Solution. Fig. 3 shows that the market price of the imported materials needed to 4 produce one unit of trucks can be increased by $1350/unit and it would not change the optimal production/export mix. It follows that the new value of the net exports can be computed as the current net value, minus the extra costs sustained to produce trucks. Namely: 490, 625, 000 − (262, 500 × 400) = $385, 625, 000. (h) The Minister of Defense has recently come to Jean-Pierre and said that he would like to stockpile (inventory) an additional 10,000 units of steel during the coming year. How will this change the constraint equation OutputSteel, and what impact will it have on net dollar exports? Solution. Because the rhs of the OutputSteel constraint represents the inventory at the end of the year, it sufficies to change the rhs from 0 to 10,000. After the modification, the equation will read: (Total steel production) = (Exported steel) + (Steel used within the country) + (10,000), which is what we want. Fig. 3 shows that we can increase the rhs of OutputSteel by at most 232,500 without changing its shadow price. Therefore, we can compute the impact on the net dollar exports as: 10, 000 × −2250 = −$22, 500, 000. The net exports will decrease by $22,500,000. (i) Is it possible with this particular formulation to deal with existing inventories at the start of the year and desired inventories at the end of the year? Suppose we start the year with Ss units of steel in the inventory, Ms units of machinery, and Ts units of trucks. At the end of the year we want to have Se units of steel in the inventory, Me units of machinery, and Te units of trucks. How should we modify the constraints OutputSteel, OutputMachinery and OutputTruck to deal with this situation? Solution. We should set the rhs of OutputSteel to Se −Ss , the rhs of OutputMachinery to Me − Ms , and the rhs of OutputTrucks to Te − Ts . (j) A government R&D group has recently come to Jean-Pierre with a new product, Product X, that can be produced for export with 1.5 man-years of labor and 0.3 units of machinery for each unit produced. What must Product X sell for on the world market to make it attractive for production? Solution. We can use the shadow prices of the constraints to determine the value of the inputs going into production of one unit of Product X. This value is: (0 × 1.5) + (2500 × 0.3) = $750. Hence, it is attractive to produce Product X if it can be sold on the world market for at least $750. (k) There is the possibility of strikes during the year that will impair Machinery production. In particular, Jean-Pierre wants to know how a reduction of the machinery capacity from 50,000 to 40,000 will affect the total value of net exports. Compute an estimate of the net dollar exports in this particular scenario, using the information given in Figures 2 and 3. Is the value that you computed the exact value of the net dollar exports in the new scenario, or is it an estimate? If it is an estimate, is it from below or from above (in other words: will the real net dollar exports value be larger or smaller than what you computed)? Solution. Fig. 3 shows that the allowable decrease for the rhs of the CapacityMachinery constraint is 8,139.5349. If we decrease the rhs by more than this value, the corresponding shadow price will change. Therefore, if we decrease the rhs by 10,000 we will obtain just 5 an estimate of the effect on the net dollar exports in the new scenario. In particular, we can estimate that the net dollar exports will decrease by at least 8, 139.5349 × 302.5 ≈ $2, 462, 209. The estimate of the new net dollar exports is 490, 625, 000 − 2, 462, 209 = $488, 162, 791. This is an estimate from above of the real value should the scenario occur: if we decrease the rhs of CapacityMachinery by more than the allowed decrease, the profit may decrease by more than what we estimated. Problem 2 Consider the following Linear Program: max x1 + 4x2 subject to: Resource 1: x1 − x2 ≤ 2 Resource 2: x1 + 2x2 ≤ 4 Resource 3: x1 ≤ 3. ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ We introduce slack variables s1 , s2 , s3 in the three constraints in this order, and we solve the resulting LP. The optimal simplex tableau is given below: Basic (−z) s1 x2 s3 x1 -1 1.5 0.5 1 x2 s1 1 1 s2 -2 0.5 0.5 s3 1 Rhs -8 4 2 3 Using the final tableau and the initial formulation, answer the following questions: (a) What is the optimal solution? Solution. x2 = 2, s1 = 4, s3 = 3 and all the remaining variables are zero. (b) Determine the shadow price for each constraint? Solution. Remember that the shadow price is the increase in the objective function value per unit increase in the rhs of that constraint. Increasing the rhs of the first constraint by Δ, is the same as replacing s1 with s1 − Δ. If we do this in the final tableau, we see that it has no impact on the objective function value. Same for the third constraints. Therefore, the shadow price for the first and third constraint is zero. On the other hand, for the second constraint substituting s2 with s2 − Δ yields −z = −8 − 2Δ, hence the objective function increases by two units for every unit of Δ. The shadow price of the second constraint is 2. The derivation of the shadow prices shows that the shadow price of a constraint is equal to the negative of the final coefficient in the objective function row for the corresponding slack variable. (c) Determine the range on the objective function coefficient of variables x1 and x2 for which the current optimal solution stays optimal, assuming that the remaining data stays fixed. (Note: only one of the two coefficients should change at a time, while everything else is fixed. Hint: you will have to treat differently the cases where the corresponding variable is basic or nonbasic. When the variable is basic, substitute c + δ to the old coefficient c, and make sure the final tableau stays in canonical form.) 6 Solution. We start with the objective coefficient c1 of x1 , which is nonbasic with reduced cost −1 in the final tableau. If c1 changes to c1 + δ, the final reduced cost will be −1 + δ. It follows that for δ ∈ [−∞, 1], the reduced cost of x1 will be nonpositive and the final tableau with its associated solution stay optimal. Because c1 is currently 1, the condition on δ translates into c1 ∈ [−∞, 2]. We now analyze the objective coefficient c2 of x2 . If we change c2 to c2 + δ, we have to subtract δ times the second row from the objective function row (z-row) in order to make sure that the tableau is in canonical form (i.e. x2 has coefficient zero in the objective function row). We obtain: Basic (−z) s1 x2 s3 x1 −1 − 0.5δ 1.5 0.5 1 x2 s1 s2 −2 − 0.5δ 0.5 0.5 1 1 s3 1 Rhs −8 − 2δ 4 2 3 This tableau is optimal as long as −1 − 0.5δ ≤ 0 and −2 − 0.5δ ≤ 0, that is, δ ≥ −2. For δ ∈ [−2, ∞], the tableau will stay optimal. Because c2 = 4 currently, the condition on δ translates into c2 ∈ [2, ∞]. Problem 3 Assume that we have the following LP in canonical form: Basic (−z) s1 s2 s2 x1 3 1 2 3 x2 1 1 -2 x3 2 1 1 x4 -2 1 -6 -1 s1 s2 s3 1 1 1 Rhs 0 4 2 7 The optimal tableau is: Basic (−z) x3 x1 x2 x1 0 x2 0 1 1 x3 0 1 x4 -1 -4 1 4 s1 -2 3 -1 -1 s2 -0.5 1.5 -0.5 -1 s3 0 -2 1 1 Rhs -9 1 2 1 (a) What is the optimal solution? (b) Determine the shadow price for each constraint? Solution. The shadow price for the first, second, and third constraint are 0.5, 0, and 9, respectively (see Problem 2, part (b)). (c) Price a new activity corresponding to the column with coefficients (0.5, 2, 5), using the simplex multipliers (also called shadow prices). (Note: pricing an activity means finding out how much it costs to produce one unit of the activity at the current optimal solution, or equivalently, how much revenue for one unit of the activity is required to reach the break-even point.) 7 Solution. The shadow prices can be read from the final tableau as the negative of the reduced costs of the slack variables. The vector of shadow prices is (2, 0.5, 0), therefore pricing the new activity (i.e. performing the dot product between the vector of shadow prices and the coefficients in the column of the constraint matrix corresponding to the new activity) yields 2. The activity would be profitable if its contribution is at least 2. (d) By how much can we increase the objective function coefficient of x4 while leaving the current optimal solution unchanged? Solution. The current optimal solution will be unchanged if the reduced costs of the nonbasic variables stay nonpositive. The reduced cost of x4 is -1. This means that the objective function value will decrease by 1 per unit increase in x4 . Hence, if the contribution of x4 increase by more than 1, the reduced cost will be positive and x4 will enter the basis. 8