Linear Programming 7 23 Aplanthas five machines, each of which can manufacture the same two models of a certain product. The maximum number of hours available on the five machines during the next production period are, respectively, 60, 85, 65, 90, and 70. The demand for products created during this next production period is expected to be 850 units of model 1 and 960 units of model 2. The profits (in dollars per hour) and production rates (per hour) are given in tabular form: Profit Production Rate Machine 5 Model Machine Model Let x, be the number of hours machine i is scheduled to manufacture model j, for i= 1, ..., 5 andj =1, 2. Formulate a linear programming model to maximize profits. 24 Metallic alloys A, B, and C are to be made to customer specifications from four dif- ferent metals (W, X, Y, and Z) that are extracted from two different ores. The cost, maximum available quantity, and constituent parts of these ores are: Maximum Tons Peteentase of Constituents Ore Cost siton) Available WXYZ 1 150 72500 | o 0 6 3 i 9% 100 Ee ee Customer specifications and selling price for the three alloys are: Alloy Specifications Selling Price ton) A Atleast 30% of cy ‘Atleast 50% of W Atmost 10% of Y B Between 30% and 40% of Z 00 ‘Atleast 40% of X [At most 70% of W Atleast 40% of Y 450 [At most 60% of W Formulate a linear programming model that meets the specified constraints and maximizes the profits from the sale of the alloys. (Hint: Let xj, be the amount of the i-th metal extracted from the j-th ore and used in the kth alloy)78 25 26 28 Operations Research Show graphically the feasible region corresponding to the following set of constraints: 2x2 wt s8 mate 56 x20 Give the coordinates of each of the extreme points of the feasible region. What is the feasible region corresponding to the following set of constraints? x +3xq 524 x56 mas +2x2 510 x x2 20 Evaluate the objective function z= 2x, + 5x, at each of the extreme points of this, feasible region. Solve the following linear programming problem graphically. maximize subject to Give the optimal value of 2 and the optimal solution (Xx). Solve the following linear programming problem graphically: maximize 2=—2x, +x subjectto x $5 x57 x56 xox et X20 Outline the feasible region, and give the optimal values of 2, x;, and xyLinear Programming 29° Examine the following formulation, and comment on the nature of its solution: maximize 2=3x)—2xs subjectto 52 <3 3xi—200 28 x m20 2.10 Examine the next formulation, and comment on the nature of its solution: maximize = Bx 44x: subjectto 6x; +8x2 $10 xi eee 21 x1 220 2.11 Examine the following formulation, and comment on the nature of its solution: maximize 2= 5x 4x subjectto xy $10 xy-2xn 23 x 220 212 Place the following linear programming model in standard form: maximize 2=16xy 42x: ~3xs subjectto (I) x) 6x24 3x24 7x3 5-5 @)x tx += 10 (8) x22) 20 7980 Operations Research 2.13 Place the following linear programming model in standard form: maximize 2=5x; + 6 +3%) subjectto (1) bs -3|<10 (2) 10x; +72 +45 <50 8) 2x) -Txs 215 x1,x320 x2 unrestricted in sign 214 Give all of the basic solutions and basic feasible solutions of the problem in Exercise 29. 215 Give the coordinates of all of the basic solutions and basic feasible solutions of the problem in Exercise 2.10, 2.16 Use the Simplex algorithm to solve the linear programming formulation from Exercise 2.1. What is the percentage utilization of the disk and printer resources at optimality? Comment on how the university community is likely to react to the optimal solution to this problem. 27 Solve the following problem using the Simplex method: maximize 2x1 2k subjectto — Maytn 26 Qx<6 @xss wy x20 218 Solve the following problem using the Simplex method: maximize 2=dx, +x subjectto (3x1 += 3 2) 4x, +326 Ox 420s3 x1, %220Linear Programming 81 2.19 Apply the Simplex algorithm to each of the following problems. Observe the behavior of the Simplex method and indicate which problems display degeneracy, multiple optima, infeasibility, or an unbounded solution. a maximize 3 +x: subjectto (x18 2) 2x,-3x2 <5, (3)xi,x2.20 ‘B. maximize 3x1 + xa, subjectto (I) xy #x225 Q) 2x +x: <4 @)x.x220 © maximize x; +2x subjectto (1) xy 2x1 $10 2) x1, x220 maximize 3x) +9) subjectto (I) xy +4xn <8 x42 <4 @)x,x220 2.20 Create a linear programming problem formulation that has unbounded solu: tions but in which no evidence of unboundedness appears in the initial Simplex tableau, 2.21 Perform as many Simplex iterations as possible on the example problem in Section 2.72. Observe that the algorithm terminates when there are no ratios 8, from which to choose a variable to leave the basis.82 Operations Research 2.22 Solve the following linear programming problem using the Two Phase Simplex method. maximize 2=4x:+x2 subjectto 3x; #x2=3 xj 43x26 xit2x <3 xee0 2.23 Examine this linear programming formulation: maximize x; +2k2 subjectto xi #2x2 10 xy X20 Comment on the nature of its solution(s). How does this change if the first con- straint is removed from the problem? 2.24 Solve the following linear programming problem graphically. subjectto xy +x221 e229 2x ter <4 x15 x m220 2.25 What determines the number of basic variables in a linear programming problem solution? 2.26 What is the value of a non-basic variable in a feasible solution of a linear program- ming problem? 2.27 Inan optimal Simplex tableau, what is the economic interpretation of the objective function row entry corresponding to the i-th slack variable? 2.28 Ina Simplex table column? 2.29 What is the consequence of a tie for the entering basic variable? 2.30 What if there is a tie for the leaving basic variable? 2.31 What if, in the objective function row of a final tableau, there is a zero in a column, corresponding to a non-basic variable? 1u, What is the interpretation of the entries in the right-hand-sideLinear Programming 2322 234 235 236 237 What happens in the Simplex algorithm if you choose, as the entering variable, a variable with a negative objective row coefficient but not the most negative coefficient?” Solve the following problem using the Simplex method: maximize 2=x,+9x2+% subjectto x; 2k: + 3x $9 3xi + 2x2 +2x5 £15 XM X 20 Use the Two Phase Simplex method to solve the following problem: minimize = 16x; +2x2—3xs subjectto xi 6x24 3x2 +7X3 $B xi +X2+xs =10 Xie XaXa- 20. A business executive has the option of investing money in two plans. Plan A guar- antees that each dollar invested will earn 70 cents a year hence, and plan B guar- antees that each dollar invested will earn $2 two years hence. Plan A allows yearly investments, while in plan B, only investments for periods that are multiples of two years are allowed. How should the executive invest $100,000 to maximize the earn- ings at the end of three years? Formulate this problem as a linear programming problem An investment portfolio management firm wishes to develop a mathematical ‘model to help decide how to invest $1 million for one year. Municipal bonds are to bbe bought in combinations that balance risk and profit. Three types of bonds are being considered + AAA sated bonds yielding 6% annually and which must be purchased in units cf $5000 + Arrated bonds yielding 8% annually and which must be purchased in units of 1000, and + J rated (unk) bonds yielding 10% annually and which must be purchased in “units of $10,000 ‘The Board of Directors has specified that no more than 25% of the portfolio should be invested in (risky) junk bonds, and at least 40% should be invested in AAA rated bonds. Bonds are to be purchased with the objective of maximizing earnings at the end of the year. It may be assumed that the stated yield dividend is paid at the end of the year, and that no other distributions are made during the year. Formulate this problem as a linear programming problem. A philanthropist wishes to develop a mathematical model to help him decide how to donate his spare cash to several worthy causes. He has §10 million to distribute among the recipients, and he would like to donate in units of thousands of dollars. 8384 238 239 240 2a1 242 243 Operations Research Three organizations would like to receive funds: Our Great State University, the Friends of the Grand Opera, and the Save the Humuhumunukunukuapua’a Society. The philanthropist wants to give at most 50% of his cash to any one orga- nization, The desirability of the philanthropist’s giving to any particular recipient is to be measured in terms of the number of tax credits he will receive. The value of giving to an educational institution is rated at 10 credits for every $1000 donation, while the value of $1000 donation to the music lovers is rated at 8 credits, and each {$1000 donation to the wildlife conservation is rated at 6 credits. Write a linear pro- gramming model to help this philanthropist maximize the number of tax credits that can be achieved by contributing among these three groups. Solve the following problem graphically: maximize 2 = -24) 4X subjectto xx $5 s7 <6 wom Xi,¥220 Write the dual of the primal linear programming problem in Exercise 27 Write the dual of the primal problem in Exercise 2.8. Solve the dual problem, and identify the shadow prices. Solve the dual problem corresponding to the primal problem in Exercise 2.12. Determine whether optimal solutions exist. If so, describe the relation between the primal shadow prices and dual variables at optimality. Describe the nature of the solutions of the primal problem in Exercise 2.10 and its dual problem, Each of the following statements refers to the Simplex algorithm. Fill in the blanks with an appropriate letter from the following choices: 1. Ifall slack and surplus variables are zero in an optimal solution, then 2. Ifa basic variable has the value zero in an optimal solution, then 3. Ifan artificial variable is non-zero in an optimal solution, then. 4. If anon-basie variable has zero coefficient in the top row of an optimal tableau, then Completion alternatives: A. There are multiple optimal solutions. ‘The current solution is degenerate. All constraints are equalities at optimality. B c D. The shadow prices are inverses of the dual variables. E, No feasible solution exists. E ‘The solution is unbounded.