Faaliyetler İş Araştırma ve İktisat Quantitative Part 3 MAN203 PART 3 CEMiLKUZEY ___ --- --MlYlPLEX METHOD UESTION ~~~~~~~~a~cc~oiradIFn·n~g~to~the final simplex table given below. @ Optimum solution and the total profit eli) Which constraints are binding? I(S2 Values of slack/surplus @Dual (shadow) prices of constraints @Unitprofit of XI tJ) Unit profit ofX2z '/, (uJ· ~ Unit profit ofX3 RHS range of constraint I . I RHS range of constraint 2 II!w . ell RHS range of constraint 3 ~ write the reduced costs of each variable • ~ compare your result of simplex table with the computer result (l]LWhat would happen if the coefficient of Xl increased by 3? @YWha! would happen if the right-hand side of constraint I increased by 10? LINEAR PROGRAMMING PROBLEM MAX 31XI+35X2+32X3 S.T. I) 3X1+5X2+2X3>90 2) 6XI+7X2+8X3<150 3) 5X1+3X2+3X3<120 FINAL SIMPLEX TABLE 31 35 32 -M 0 0 Cj MV X1 X2 X3 A S1 surp S2 slack 35 '( Jl.L ) 0 1 -1 .33 0.67 -0.67 -0.33 31 ( } J 1 0 2.89 · 0.78 0.78 0.56 0 ~ h 0 0 -7.44 1.89 -1.89 -1 .78 zj 31 35 42.89 -0.78 0.78 5.56 cj-zj 0 0 -10.89 -M-??? -0.78 -5.56 0 S3 slack RHS 0 (""10) 0 10':3·33 2 1 =3 . . :# " XI+2X2 <=3 V''!'" .~ " ------------------------------------------------------------- A , 2_ Solve the given LP model by Simplex method (ANS: xl=18, x2=4 And Zmax=$190) ~ " Zmax= $9XI+$7X2 Constraint 2XI+IX2<= 40 XI+3X2 <= 30 • 3_ solve the following LP model by simplex algorithm Zmin= $4XI +$5X2 Constraint Xl+2X2 >= 80 3XI+X2 >= 75 What are the basic(main vario ables) in each iteration and what are the non-basic(non-main variables) in each iteration? Establish the first AND the second simplex table of the given LP model Zmin=$80XI + $40X2 +$20X3- $10X4 Subject To Xl+2X2+X3+5X4 <=150 X2-4X3+8X4 = 70 6XI+7X2+2X3-X4 >=150 answer the questions for the following maximum profit LP problem. The simplex table is given below Zmax= $9XI+$7X2 Constraint 2Xi+lX2<=40 Xl+3X2 <= 30 3 a) b) c) d) • ~ Fill the gap Is the table optimum? What is the total profit What is the optimum solution How much of the constraint I and constraint 2 are unsed what are the shadow (dual) prices for the two constraint perform RHS ranges for cC\nstraint I h) perform RHS ranges for constraint 2 ~hwm i) if the RHS of constraint I were increased by 10, what would be the maximum possible profit? Give values for all the variables ~) 9 7 Find the ranges of optimality for the profit on X I Find the ranges of optimality for the profit on X2 9 7 a a M.v/BASIC X1 X2 S1 S2 X1 1 a 3/5 -115 X2 a 1 -1/5 215 Z 9 ~ '1 1. c-z 0 to - -.. -.:l bmw RHS/QTN 18 4 ISO 6_ GUL Construction Company is building two apartment complexes. It must decide how many units to construct in each complex subject to labour and material constraints. The profit generated for each apartment in the fust complex is estimated at $900, for each apartment in the second complex is $1500. a partial initial simplex table for GUL construction is given in the following table 900 1500 a a M.v X1 X2 S1 S2 RHSlQTN <, 14 4 1 a 3360 ~z. 10 12 a 1 9600 Z 0 0 to 0 0 C-z '>,00 1:>00 0 0 a) complete the initial table b) reconstruct the LP model (object functIOn and the constraint) c) what is the basis(main variable) for the initial solution? d) Which variable should enter the solution at the next iteration? e) Which variable will leave the solution at the next iteration? f) How many units of the variable entering the solution next will be in the basis in the second table? g) How much will profit increase in the next solution? 4 o 7_ a linear program has been formulated and solved. The optimal simplex table for this is glven 80 120 90 0 0 0 MV X1 X2 X3 S1 S2 83 RHS/QTN 120 X2 -1 .5 1 0 0.125 ' 0.75 0 37 .5 90 0 X3 3.5 0 1 -0.125 1.25 0 12.5 S3 -1 0 0 0 -0.5 1 10 Z 135 120 90 3.75 22.5 0 5625 C-Z -55 0 0 -3.75 -22 .5 0 a) what are the shadow prices for the three constraints? What does zero shadow price mean? How can this occur? b) How much coudl the right hand side ofthe first constraint be changed without changing the optimum solution? c) How much could the right hand side of the third constraint be changed without changing the optimum solution? d) Find the unit profit range for second variable (c2 _range) 8_ consider the following optimal table $10 $30 $0 $0 MV X1 X2 S1 S2 RHS/QTN $10 X1 1 4 2 0 160 $0 S2 0 6 -7 1 200 Z 10 40 20 0 1600 C-Z 0 -10 -20 0 a) what is the range of optimality for the contribution rate of the variable XI? b) What is the range of optimality for the variable X2? c) How much would you be willing to pay for 3 more unit of the fust resource (represented by the slack variable S I)? d) What is the value of one more . unit of the second resource? Why? e) What would the optimal solution be if the profit on X2 where changed to $35 insread of$30? f) What would the optimal solution be if the profit on Xl were changed to $ 12 instead of $.10? How much the maximum profit change? . , . • 5 9_ Two simplex tables are given below for a minimization cost LP pro bl em. Are they optimum tables? Explain in detail s. Write the optimum solution as well as the to tal cost. (hin_ SOLUTION MIX= main variabl eslbasics QUANTITY_ RH S) .;"'\ C j - Solution ' 0 10 " 0 M M i Mix X, X, X, 5, A , A, Qu antlty 50 X, 1 -1 0 0 1 Q 1,000 75 X, 0 1 1 0 0 'f, 1,00 0 ( 0 5, 0 1 0 1 1 G ) 500 Z, 50 25 75 0 50 37~ S 125.000 C ; - z.. 0 15/ 0 0 M - 5D M - 37~"; C ;-+ Solution 50 10 75 0 M M 1 Mix X, X, X, 5, ... A, Qua ntity SO X, 0 0 0 0 1,500 75 X. 0 0 - 1 :.I 500 10 X, 0 0 - 1 0 500 Zj 50 10 75 - 15 65 3 71. S l1i,SOO C i - Z: 0 0 0 15 "" - 65 M - 371. _ Two simplex tables are given below for a Maximization Profit problem. Explain whether they are optimum or now. If they are optimum, write down the optimum solution. Also write the total profit of the given table. L U>\. ... ".~ ol~" ",\0. n \ 1('(' a) 7 '\" ,.i- / ... C r .. Solution 58 56 514/ 0 -M l Mix X, X, ~X;. 5, A, Quantity So (5, '" 0 It, 1 - I; '80 ) $6 X, 'A I % 0 X 40 . ~ 2: 6 4 0 1 $.240 C j - Zj 6 0 10 0 -M - 1 ........... 6 • b) ~-. Solution S8 4 Mix X, $14 X, 0/'1' $6 X, - ';S Z; '1, C j - Z; -1. 1 'l< 'l. ::. I 2.0 /1 )C ~ .:> 'Z ~ 0 /":1 56 X, 0 6· 0 514 0 -M X, S, A, Quantity !/, - ;., "I', () -V~ y, "17':- 14 K/_ , . + y, SS82 Y., 0 _ie,t, - M - Y, '1", +-(ll prD ~J 4- = S 8'Z. -+ ~ 'to\- )~ op+I~""~. 'It :=0 1o,(8U~" stv S IIV_ The final simplex table for an LP maximization problem is shown in the table. Describe the specical case. 3 5 0 0 -M M.V Xl X2 S1 S2 A1 5 X2 1 1 2 0 0 -M A1 -1 0 -2 -1 1 Z 5+M 5 10+2M M -M C-Z -2-M 0 -10-2M -M 0 12 a)formulate the dual of the given primal LP problem b) fmd the dual of the problem's dual Maximization profit= 80X I +7 5X2 XI+3X2<=4 2X1+5X2<=8 RHS/QTN 6 2 30-2M Oil ,..vI}.! 7 13_ the final simplex table for the LP problem is given below Zmax=200X I + 200X2 2Xl+X2<=8 '~ Xl+3X2<=9 What are the solutions to the dual variables, U I and U2? What is the optimal dual cost? 200 200 $0 $0 MV X1 X2 S1 S2 RHS/Q TN 200 X1 1 0 0.6 -0.2 3 200 X2 0 1 -0.2 0.4 2 Z 200 200 80 40 1000 C-Z 0 0 -80 -40 14_ The accompanying table provides the optimal solution to this dual: ZMIN=120Ul +240U2 SUBJECT TO 2UI+2U2>=0.5 U I+3U2>=0.4 What does the corresponding primal problem look like, and what is its optimal solution? 120 240 0 0 M M MV U1 U2 S1 S2 A1 A2 RHS/QTN 120 U1 1 0 -0.75 0.5 0.75 -0.5 0.175 240 U2 0 1 0.25 -0.5 -0.25 0.5 0.075 Z $ 120 $ 240 -$ 30 -$ 60 $ 30 $60 $ 39 C-Z 0 0 30 60 M-30 M-60 15_ Given the following dual formulation, reconstruct the original primal problem • ZMIN=28UI+53U2+70U3+18U4 S.T. UI+U4>=10 UI + 2U2+U3>=5 -2U2+5U4>=31 5U3>=28 12UI+2U3-U4>= 17 8