Larry J. Goldstein David I. Schneider Martha J. Siegei i-' r A 1 son Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Linear... Linear programming is a method for solving problems in which a linear function (representing cost, prot, distance, weight, or the like) is to be maximized or mini: mized. Such problems are called optimization problems. As we shall see, these problems, when translated into mathematical language, involve systems of linear inequalities. systems of linear equations, and eventually (in Chapter 4) matrices. 3.1 A Linear Programming Problem Let us begin with a detailed discussion of a typical problem that can be solved by linear programming. Furniture Manufacturing Problem A furniture manufacturer makes two types of furniturechairs and sofas. For simplicity, divide the production process into three distinct operationscarpeutry, nishing, and upholstery. The amount of labor required for each operation varies. Manufacture of a chair requires 6 hours of carpentry, 1 hour of nishing, and 2 hours of upholstery. Manufacture of a sofa requires 3 hours of carpentry, 1 hour of nishing, and 6 hours of upholstery. Due to limited availability of skilled labor as well as of tools and equipment, the factory has available each day 96 labor-hours for carpentry, 18 labor-hours for nishing. 117 Larry J. Goldstein David i. Schneider Martha J. Siegei Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Linear... Chapter 3 Linear Programming, A Geometric Approach and 72 labor-hours for upholstery. The prot per chair is $80 and the prot per sofa $70. How many chairs and how many sofas should be produced each day to maximize the prot? It is often helpful to tabulate data given in verbal problems. Our filst step, then, is to construct a chart. Chair Sofa Available time Carpentry 6 hours 3 hours 96 labor~hours Finishing 1 hour 1 hour 181aborshours Upholstery 2 hours 6 hours 72 labor-hours Prot $80 570 The next step is to translate the problem into mathematical language. As you know, this is done by identifying what is unknown and denoting the unknown quantities by letters. Since the problem asks for the optimal number of chairs and sofas to be produced each day, there are two unknownsthe number of chairs produced each day and the number of sofas produced each day. Let .r denote the number of chairs and y the number of sofas. To achieve a large prot, one need only manufactlu'e a large number of chairs and sofas, But due to restricted availability of tools and labor. the factory cannot manufacture an unlimited quantity of furniture. Let us translate the restrictions into mathematical language. Each of the rst three rows of the chart gives one restriction. The rst row says that the amount of carpentry required is 6 hours for each chair and 3 hours for each sofa. Also. there are available only 96 laborshours i li' i I i 1 El 1 Him. dammit\" Larry J. Geldstein David I. Schneider Martha J. Siegei Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Linear... The next step is to translate the problem into mathematical language. As you know, this is done by identifying what is unknown and denoting the unknown quantities by letters. Since the problem asks for the optimal number of chairs and sofas to be produced each day, there are two unknowns" the number of chairs produced each day and the number of sofas produced each day. Let :1: denote the number of chairs and y the number of sofas. To achieve a large prot. one need only manufacture a large number of chairs and sofas. But due to restricted availability of tools and labor, the factory cannot manufacture an unlimited quantity of furniture. Let us translate the restrictions into mathematical language. Each of the rst three rows of the chart gives one restriction. The rst row says that the amount of carpentry required is 6 hours for each chair and 3 hours for each sofa. Also, there are available only 96 labor-hours of carpentry per day. We can compute the total number of labophours of carpentry required per day to produce a: chairs and y sofas as follows: [number of labor-hours per day of carpentry] : (number of hours carpentry per chair) - (number of chairs per day} + (number of hours carpentry per sofa) - (number of sofas per day) = 6 - cc + 3 . y. The requirement that at most 96 labor-hours of carpentry be used per day means that a; and y must. satisfy the inequality 6I+3y g 96. (1) The second row of the chart gives a restriction imposed by nishing. Since 1 hour of nishing is required for each chair and sofa. and since at most 18 laborlhours of nishing are available per day. the same reasoning as used to derive inequality (1) yields PEARSON Larry J. Goldstein David It Schneider Maitha J. Siegel i'l mum. Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Linear... Mme mathematical language. Each of the rst three rows of the chart gives one restriction. The rst row says that the amount of carpentry required is 6 hours for each chair and 3 hours for each sofa. Also, there are available only 96 labor-hours of carpentry per day. We can compute the total number of laborahours of carpentry required per day to produce 1: chairs and y sofas as follows: [number of laborrhours per day of carpentry] = (number of hours carpentry per chair) - [number of chairs per day) + (number of hours carpentry per sofa) - (number of sofas per day) = 6 . a: -i- 3 - y. The requirement that at most 96 labor-hours of carpentry be used per day means that a: and y must satisfy the inequality 6x + 33; E 96. (1) The second rovir of the chart gives a restriction imposed by nishing. Since 1 hour of nishing is required for each chair and sofa, and since at most 18 laborhours of nishing are available per day, the same reasoning as used to derive inequality (1] yields 1' - y g 18. (2) Similarly, the third row of the chart gives the restriction due to upholstery: 2x -- 6y 5 72. (3) Further restrictions are given by the fact that the numbers of chairs and sofas must he nonnegative: 3:20? yes. (4) Now that we have written down the restrictions constraining .1: and 5:: let us express the prot (which is to be maximized} in terms of a: and y. The pro t comes [VE p 1 t illi Larry J. Goldstein David I. Schneider Martha .J. Siegel Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Linear... We may describe this mathematical problem in the following general way. We are required to maximize an expression in a certain number of variables, where the variables are subject to restrictions in the form of one or more inequalities. Protr leins of this sort are called mathematical programming pr'obiems. Actually, general mathematical programming problems can be quite involved, and their solutions may require very sophisticated mathematical ideas. However, this is not the case with the furniture manufacturing problem. \"iliat makes it a rather simple math- ematical programming problem is that both the expression to be maximized and the inequalities are linear. For this reason the furniture manufacturing problem is called a linear programming problem, The theory of linear programming is a fairly recent advance in mathematics. It was developed over the last 70 years to deal with the increasingly more complicated problems of our technological society. The 1975 Nobel Prize in economics was awarded to Kantorovich and Koopmans for their pioneering work in the eld of linear programming. We will solve the furniture manufacturing problem in Section 3.2, where we develop a general technique for handling similar linear programming problems. At this point it is worthwhile to attempt to gain some insights into the problem and possible methods for attacking it. It seems clear that a factory will operate most efciently when its labor is fully utilized. Let us therefore take the operations one at a time and determine the conditions on :c and 3; that fully utilize the three kinds of labor. The restriction on carpentry asserts that 6r+3y 96. if .7; and g were chosen so that 61c + 33,: is actually less than 96, we would leave the carpenters idle some of the time, a waste of labor. Thus it would seem reasonable to choose at and y to satisfy Sm + 3y = 96. Similarly, to utilize all the finishers' time, :1: and 3; must satisfy i't Al-Ihlf'i'a Larry J. Goldstein David I. Schneider Maltha J. Siegel Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Llnear Programming, A Geometric Approach: 3.1 A Unear... ematieal programming problem is that both the expression to be maximized and the inequalities are linear. For this reason the furniture manufacturing problem is called a linear programming problem. The theoryr of linear programming is a fairly recent advance in mathematics. it was developed over the last 70 years to deal with the increasingly more complicated problems of our technological society. The 1975 Nobel Prize in economics was awarded to Kantomvich and Koopmans for their pioneering work in the field of linear programming. W' will solve the furniture manufacturing problem in Section 3.2, where we develop a general technique for handling similar linear programming problems. At this point it is Worthwhile to attempt to gain some insights into the problem and possible methods for attacking it. It seems clear that a factor),r will operate most efciently when its labor is fully utilized. Let us therefore take the operations one at a time and determine the conditions on re and 3; that fully utilize the three kinds of labor. The restriction on carpentry asserts that 6x+3y S 'in [f :c and 1:; were chosen so that. 65': -l- 33:; is actually less than 96, we would leave the carpenters idle seine of the time, a waste of labor. Thus it would seem reasonable to choose a; and y to satisfy 6w 3y : 96. Similarly, to utilize all the nishers" time, :15 and 1; must satisfy :1: y = 18, and to utilize all the upholsterers' time, we must have 2.1: 63; = 72. ill Al-IEC'YN Larryr J. Goldstein David I. Schneider Martha J. Siegel Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Linear... Sec. 3.1 A Linear Programming Problem 119 from two sourceschairs and sofas. Therefore, [profit] 2 [prot from chairs] + [profit from sofas] = [prot per chair] - [number of chairs] + [prot per sofa] - [number of sofas] : 8ch + my Since the objective of the problem is to optimize profit: the expression 803: + 70:; is called the objective function. Combining (1) to (5), we arrive at the following: Furniture Manufacturing ProblemMathematical Formulation Find numbers x and y for which the objective function 80:1: + 703; is as large as possible, and for which all the following inequalities hold simultaneously: 6.1:n3yg'96 m 3;ng 2 <6) m5y72 2:20. 120 We may describe this mathematical problem in the following general way. We are required to maximize an expression in a certain number of variables5 where the variables are Subject to restrictions in the form of one or more inequalities. Prob- lems of this sort are called mathematical programming problems. Actually, general mathematical programming problems can be quite involved, and their solutions may require very sophisticated mathematical ideas. However: this is not the case with the furniture manufacturing problem' What makes it a rather simple math ematical programming problem is that both the expression to be maximized and the inequalities are linear. For this reaSon the furniture manufacturing problem is l'l ALISON Larry J. Goldstein David I. Schneider Martha J. Siegel Finite Math ematics 8: Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Unear... I 2x + 69 = 72 (upholstery) . ' m + y = 18 {>35 + 5:1} 2 9f" (finishing) (carpentry) Figure 1 \"that does Fig. 1 say about the furniture manufacturing problem? Each par ticular pair of numbers (3:,y] is called a production schedule. Each of the lines in Fig. 1 gives the production schedules that fully utilize one of the types of labor. Notice that the three lines do not have a common intersection point. This means that. there is no production schedule that. simultaneously makes Full use of all three types of labor. In an),r production schedule at least some of the laborhours must be wasted. This is not a solution to the furniture manufacturing problem, but it is a valuable insight. It says that in the inequalities of (6) not all of the correspond- ing equations can hold. This suggests that we take a closer look at the system of inequalities. The standard forms of the inequalities (6) are y572m+32 yg m+18 yg%m+12 nun .xn l"! ALISON Larry J. Goldstein David I. Schneider Maitha J. Siegel Finite Math ematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Unear... feasible set Figure 2 )zl': -i- . J} = - (finishing) (carpentry) Figure 1 What does Fig. 1 say about the furniture manufacturing problem? Each par ticular pair of numbers (any) is called a production schedule. Each of the lines in Fig. 1 gives the production schedules that fully utilize one of the types of labor. Notice that the three lines do not have a common intersection point. This means that there is no production schedule that sinmitoneousiy makes full use of all three types of labor. In any production schedule at least some of the laborshours must be wasted. This is not a solution to the furniture manufacturing problem, but it is a valuable insight. It says that in the inequalities of (6) not all of the correspond- ing equations can hold. This suggests that we take a closer look at the system of inequalities. The standard forms of the inequalities (5] are yS2$+32 yg a':+18 yS*%m+12 3320, \"920 By using the techniques of Section 1.2I we arrive at a feasible set for the preceding system of inequalities7 as shown in Fig. 2. The feasible set for the furniture manufacturing problem is a bounded, ve sided region. The points on and inside the boundary of this feasible set give the production schedules that satisfy all the restrictions. In Section 3.2 we Show how to pick out a particular point of the feasible set that corresponds to a. maximum prot. l'l iii-HON Larryr J. Goldstein David I. Schneider Martha J. Siegel i'l an sow Finite Mathematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: 3.1 A Unear... 1 20 Chapter 3 Linear Programming, A Geometric Approach Time: if no iabor is to be wasted: then, :r: and y must satisfy the system of equations 6a: 3y 2 96 3:\" 11218 (7) 2m W 63; 2 7'2 Let us now graph the three equations of (7], which represent the conditions for full utilization of all forms of labor. (See the following chart and Fig. 1.) Equation Standard form w-Intercept y-Intercept 6:: 3y : 96 y : 2:1: -i 32 (1610) (EL 32) a: y = 18 y = a: -i 18 (1810) (0,18) 2x--6y:72 y:a.~+ 12 (36.0) (0,12) 1' 2;: + 59 : 72 (upholstery) . ' as + y = 13 ba'. + 3'5" 2 9" (finishing) in: rnmnrvi Larry J. Goldstein w" David I. Schneider Maitha J. Siegel Finite Ma ematics & Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: Chapter 3 Pr... y = %r + 12 (upholstery) y = _I + 19 (nishing) y = _2a: + 32 (carpentry) Determine the optimal solution for the revised linear programming problem. What is the new maximum prot? By how much was the prot increased due to the additional hour for nishing? What is the shadow price for the nishing constraint? Return to the original furniture manufacturing problem and assume that one addi tional hour is available for carpentry. Solve the altered problem and determine the shadow price for the carpentry constraint. Use your knowledge of the solution of the original furniture manufacturing problem and the denition of shadow price to explain why the shadow price for the upholstery constraint is 0. (Hint: No computation is necessary.) Fill in the blanks in the following sentence. The shadow price associated with a constraint can be interpreted as the change in value of the per unit change of the constraint's right-hand-side resource. l'tARSON Larry J. Goldstein ,i' David I. Schneider Martha J. Siegel Finite Mathematics 8: Its Applications, Tenth Edition Chapter 3: Linear Programming, A Geometric Approach: Chapter 3 Pr... CH \\ \\f--/ !\\ -.. Chapter Project 149 A'TER3 | PROJECT Shadow Prices When a mathematician is presented with a linear programming problem, he or she will not only determine the optimal solution but will also supply what are called shadow prices for each constraint. This chapter project develops the concept of a shadow price. Consider the furniture manufacturing problem. The constraint for nishing is a: + y g 18. The number 18 came from the fact that 18 hours are available for nishing each day. Suppose you could increase the number of hours available for nishing by one hour. The shadow price for the nishing constraint is the maximum price you would be willing to pay for that additional hour. 1. What is the new inequality for the nishing constraint? What is its corresponding linear equation? 2. The gure shows the graph of the original feasible set for the furniture manufacturing problem drawn with a red boundary. The blue line segments show the change in the feasible set when the new,r nishing constraint is used. Find the coordinates of the points A and B. y=%z+12 (upholstery) y = .r + 19 (nishing) l'I'ARSON Project 2 YOUR NAME____________________________________________ This project is given on page 149 in the textbook. Refer to the furniture manufacturing problem discussed in Ch3.1 pages 117-120 (Read the introduction to the problem page117-118) Maximize 80x +70y Subject to 6x + 3y <= 96 x + y <= 18 2x + 6y <= 72 x >=0, y >= 0 carpentry finishing upholstery constraints on labor hours in each manufacturing stage. (Now read the introduction in Shadow Prices page 149, stop reading before question1 ) Study the solution of this problem below .This is called base case. The graph of the feasible set is made here for the formulated linear programming problem above 6x + 3y <= 96 y <= 32 - 2x x 0 2 4 6 8 10 12 14 16 18 20 x + y <= 18 y <= 18 - x 32 28 24 20 16 12 8 4 0 -4 -8 2x + 6y <= 72 y <= 12 - 1/3x y >= 0 y >= 0 18 12 16 11.3333333333 14 10.6666666667 12 10 10 9.3333333333 8 8.6666666667 6 8 4 7.3333333333 2 6.6666666667 0 6 -2 5.3333333333 0 0 0 0 0 0 0 0 0 0 0 35 30 25 20 c y <= 32 - 2x 15 y <= 18 - x y <= 12 - 1/3x 10 y >= 0 b 5 d a 0 0 -5 5 10 15 20 25 20 c y <= 32 - 2x 15 y <= 18 - x y <= 12 - 1/3x 10 y >= 0 b 5 d a 0 0 5 10 15 20 25 -5 -10 Corner point a b c d point a point b point c point d x,y 80x + 70y 14,4 9,9 0,12 16,0 1400 optimal solution 1350 840 1280 32-2x=18-x 32-18=2x-x 14=x y=32-2*14 y=4 18-x=12-1/3x 18-12=x-1/3x 6=2/3x 9=x y=18-9 y=9 y=12-1/3*0 y=12 x=0 0=32-2x x=16 y=0 Now follow the direction answer the questions. If necessary insert more rows. Show your work here. Save when finished with your name in the name of the file and submit it. 1.Suppose that the finishing constraint now has 19 instead of 18 labor hours limit. Write he new finishing constrain. 2. Add the graph of the new finishing constraint on the graph for the base case below Label the two new corner points as A and B (see the picture in the project page 149) Find the coordinates of points A and B. 35 30 25 20 35 30 25 20 c y <= 32 - 2x 15 y <= 18 - x y <= 12 - 1/3x 10 y >= 0 b 5 d a 0 0 5 10 15 20 25 -5 -10 3. Determine the optimal solution for the problem with the new finishing constraint (ignore points a and b when objective functi 4. Calculate the shadow price as the difference between the optimal profit with the new constraint and the optimal profit of the 5. Return to 18 labor-hour limit in finishing constraint and increase the labor-hour limit by 1 in carpentry constraint. Solve the problem with the new carpentry constraint. Determine the shadow price for the carpentry constraint. 6.Return to base case value in carpentry constraint and increase the right-hand side value of the upholstery constraint by 1. Solve the problem with the new upholstery constraint. Determine the shadow price for the upholstery constraint. 7. Fill in the blanks in the following sentence. The shadow price associated with a constraint can be interpreted as the change in the value of the ______________________ _______________per unit change of the constraint's right-hand side limit. urs in each manufacturing stage. y <= 32 - 2x y <= 18 - x y <= 12 - 1/3x y >= 0 y <= 32 - 2x y <= 18 - x y <= 12 - 1/3x y >= 0 new finishing constrain. y <= 32 - 2x y <= 18 - x y <= 12 - 1/3x y >= 0 oints a and b when objective function is calculated). nstraint and the optimal profit of the base case. n carpentry constraint. rpentry constraint. of the upholstery constraint by 1. pholstery constraint. Project 2 YOUR NAME____________________________________________ This project is given on page 149 in the textbook. Refer to the furniture manufacturing problem discussed in Ch3.1 pages 117-120 (Read the introduction to the problem page117-118) Maximize 80x +70y Subject to 6x + 3y <= 96 x + y <= 18 2x + 6y <= 72 x >=0, y >= 0 carpentry finishing upholstery constraints on labor hours in each manufacturing stage. (Now read the introduction in Shadow Prices page 149, stop reading before question1 ) Study the solution of this problem below .This is called base case. The graph of the feasible set is made here for the formulated linear programming problem above 6x + 3y <= 96 y <= 32 - 2x x 0 2 4 6 8 10 12 14 16 18 20 x + y <= 18 y <= 18 - x 32 28 24 20 16 12 8 4 0 -4 -8 2x + 6y <= 72 y <= 12 - 1/3x y >= 0 y >= 0 18 12 16 11.3333333333 14 10.6666666667 12 10 10 9.3333333333 8 8.6666666667 6 8 4 7.3333333333 2 6.6666666667 0 6 -2 5.3333333333 0 0 0 0 0 0 0 0 0 0 0 y<=19-x 19 17 15 13 11 9 7 5 3 1 -1 35 30 25 20 c y <= 32 - 2x 15 y <= 12 - 1/3x y >= 0 10 y <= 18 - x b 5 d a 0 0 -5 5 10 15 20 25 20 c y <= 32 - 2x 15 y <= 12 - 1/3x y >= 0 10 y <= 18 - x b 5 d a 0 0 5 10 15 20 25 -5 -10 Corner point a b c d point a point b point c point d x,y 80x + 70y 14,4 9,9 0,12 16,0 1400 optimal solution 1350 840 1280 32-2x=18-x 32-18=2x-x 14=x y=32-2*14 y=4 18-x=12-1/3x 18-12=x-1/3x 6=2/3x 9=x y=18-9 y=9 y=12-1/3*0 y=12 x=0 0=32-2x x=16 y=0 Now follow the direction answer the questions. If necessary insert more rows. Show your work here. Save when finished with your name in the name of the file and submit it. NOTE IN ALL THE FOLLOWING THE FEASIBLE REGION IS BOUNDED BY CBAD or its new positions 1.Suppose that the finishing constraint now has 19 instead of 18 labor hours limit. Write he new finishing constrain. x+y <=19 y<=19-x 2. Add the graph of the new finishing constraint on the graph for the base case below Label the two new corner points as A and B (see the picture in the project page 149) Find the coordinates of points A and B. A=13,6 B=10.5,8.5 35 30 25 35 30 25 20 c y <= 32 - 2x 15 y <= 18 - x y <= 12 - 1/3x B 10 y >= 0 A y<=19-x b 5 d a 0 0 5 10 15 20 25 -5 -10 3. Determine the optimal solution for the problem with the new finishing constraint (ignore points a and b when objective functi price point c point d x=0, y=12 x=16, y=0 Point A point B y=32-2x, y=19-x y=19-x y=12-x/3 19-x=12-x/3 x=10.5 840 1280 x=13, y=6 1460 OPTIMAL y=12-10.5/3 y=8.5 1435 4. Calculate the shadow price as the difference between the optimal profit with the new constraint and the optimal profit of the Diference =1460-1400=60 5. Return to 18 labor-hour limit in finishing constraint and increase the labor-hour limit by 1 in carpentry constraint. Solve the problem with the new carpentry constraint. Determine the shadow price for the carpentry constraint. 6x+3y<=97 y=18-x New A= 14.33, 3.667 Cost =1403.3 other point is outside feasible region Difference 1403.3-1400 =3.3 shadow=3.3 6.Return to base case value in carpentry constraint and increase the right-hand side value of the upholstery constraint by 1. Solve the problem with the new upholstery constraint. Determine the shadow price for the upholstery constraint. 2x+6y<=73 New B y=18-x 12.167-x/3=18-x x=8.7495, y=9.2505 new B cost Old A still gives optimal as 1400 so no change in optimal price as t t the old level Shadow price 0 for upholstery constraint 1347.5 (by definition given above) 7. Fill in the blanks in the following sentence. The shadow price associated with a constraint can be interpreted as the change in the value of the _ optimal cost per unit change of the constraint's right-hand side limit. 35 30 25 Column B Column C Column D Column E 20 15 10 5 0 -5 0 5 10 15 20 25 Column B Column C Column D Column E 20 15 10 5 0 -5 -10 0 5 10 15 20 25 urs in each manufacturing stage. y <= 32 - 2x y <= 12 - 1/3x y >= 0 y <= 18 - x y <= 32 - 2x y <= 12 - 1/3x y >= 0 y <= 18 - x CBAD or its new positions new finishing constrain. y <= 32 - 2x y <= 18 - x y <= 12 - 1/3x y >= 0 y<=19-x 25 oints a and b when objective function is calculated). nstraint and the optimal profit of the base case. n carpentry constraint. rpentry constraint. of the upholstery constraint by 1. pholstery constraint. Column B Column C Column D Column E Column B Column C Column D Column E Project 2 YOUR NAME____________________________________________ This project is given on page 149 in the textbook. Refer to the furniture manufacturing problem discussed in Ch3.1 pages 117-120 (Read the introduction to the problem page117-118) Maximize 80x +70y Subject to 6x + 3y <= 96 x + y <= 18 2x + 6y <= 72 x >=0, y >= 0 carpentry finishing upholstery constraints on labor hours in each manufacturing stage. (Now read the introduction in Shadow Prices page 149, stop reading before question1 ) Study the solution of this problem below .This is called base case. The graph of the feasible set is made here for the formulated linear programming problem above 6x + 3y <= 96 y <= 32 - 2x x 0 2 4 6 8 10 12 14 16 18 20 x + y <= 18 y <= 18 - x 32 28 24 20 16 12 8 4 0 -4 -8 2x + 6y <= 72 y <= 12 - 1/3x y >= 0 y >= 0 18 12 16 11.3333333333 14 10.6666666667 12 10 10 9.3333333333 8 8.6666666667 6 8 4 7.3333333333 2 6.6666666667 0 6 -2 5.3333333333 0 0 0 0 0 0 0 0 0 0 0 y<=19-x 19 17 15 13 11 9 7 5 3 1 -1 35 30 25 20 c y <= 32 - 2x 15 y <= 12 - 1/3x y >= 0 10 y <= 18 - x b 5 d a 0 0 -5 5 10 15 20 25 20 c y <= 32 - 2x 15 y <= 12 - 1/3x y >= 0 10 y <= 18 - x b 5 d a 0 0 5 10 15 20 25 -5 -10 Corner point a b c d point a point b point c point d x,y 80x + 70y 14,4 9,9 0,12 16,0 1400 optimal solution 1350 840 1280 32-2x=18-x 32-18=2x-x 14=x y=32-2*14 y=4 18-x=12-1/3x 18-12=x-1/3x 6=2/3x 9=x y=18-9 y=9 y=12-1/3*0 y=12 x=0 0=32-2x x=16 y=0 Now follow the direction answer the questions. If necessary insert more rows. Show your work here. Save when finished with your name in the name of the file and submit it. NOTE IN ALL THE FOLLOWING THE FEASIBLE REGION IS BOUNDED BY CBAD or its new positions 1.Suppose that the finishing constraint now has 19 instead of 18 labor hours limit. Write he new finishing constrain. x+y <=19 y<=19-x 2. Add the graph of the new finishing constraint on the graph for the base case below Label the two new corner points as A and B (see the picture in the project page 149) Find the coordinates of points A and B. A=13,6 B=10.5,8.5 35 30 25 35 30 25 20 c y <= 32 - 2x 15 y <= 18 - x y <= 12 - 1/3x B 10 y >= 0 A y<=19-x b 5 d a 0 0 5 10 15 20 25 -5 -10 3. Determine the optimal solution for the problem with the new finishing constraint (ignore points a and b when objective functi price point c point d x=0, y=12 x=16, y=0 Point A point B y=32-2x, y=19-x y=19-x y=12-x/3 19-x=12-x/3 x=10.5 840 1280 x=13, y=6 1460 OPTIMAL y=12-10.5/3 y=8.5 1435 4. Calculate the shadow price as the difference between the optimal profit with the new constraint and the optimal profit of the Diference =1460-1400=60 5. Return to 18 labor-hour limit in finishing constraint and increase the labor-hour limit by 1 in carpentry constraint. Solve the problem with the new carpentry constraint. Determine the shadow price for the carpentry constraint. 6x+3y<=97 y=18-x New A= 14.33, 3.667 Cost =1403.3 other point is outside feasible region Difference 1403.3-1400 =3.3 shadow=3.3 6.Return to base case value in carpentry constraint and increase the right-hand side value of the upholstery constraint by 1. Solve the problem with the new upholstery constraint. Determine the shadow price for the upholstery constraint. 2x+6y<=73 New B y=18-x 12.167-x/3=18-x x=8.7495, y=9.2505 new B cost Old A still gives optimal as 1400 so no change in optimal price as t t the old level Shadow price 0 for upholstery constraint 1347.5 (by definition given above) 7. Fill in the blanks in the following sentence. The shadow price associated with a constraint can be interpreted as the change in the value of the _ optimal cost per unit change of the constraint's right-hand side limit. 35 30 25 Column B Column C Column D Column E 20 15 10 5 0 -5 0 5 10 15 20 25 Column B Column C Column D Column E 20 15 10 5 0 -5 -10 0 5 10 15 20 25 urs in each manufacturing stage. y <= 32 - 2x y <= 12 - 1/3x y >= 0 y <= 18 - x y <= 32 - 2x y <= 12 - 1/3x y >= 0 y <= 18 - x CBAD or its new positions new finishing constrain. y <= 32 - 2x y <= 18 - x y <= 12 - 1/3x y >= 0 y<=19-x 25 oints a and b when objective function is calculated). nstraint and the optimal profit of the base case. n carpentry constraint. rpentry constraint. of the upholstery constraint by 1. pholstery constraint. Column B Column C Column D Column E Column B Column C Column D Column E