Question

Chapter 4 Duality and Post-Optimal Analysis 2. Generate the dual simplex iterations for the following problems (using TORA for convenience), and trace the path of the algorithm on the graphical solution space. (a) Minimize z = 2x1 + 3x2 subject to 2xı + 2x2 = 30 x1 + 2x2 2 10 (b) Minimize z = 5x1 + 6x2 subject to x1 + x2 2 2 4x1 + x2 2 4 X1, X2 20 (c) Minimize z = 4x1 + 2x2 subject to *+ x2 = 1 3.x1 - x2 2 2 X, X, 20

2a and 2c , both by hand but consider using Desmos for the required graphs.

thank you!!

Answer 1

# dual simplex iterations - » Min z = 2%,+342' St. 23, + 22 - 30 x + 22, 210 x,,t2 210 To apply dual simplex iteration method, first convert Minz to Max. z. and all inequalities (2) to (6) by multiply t.. . So, Max z = - 230, -3762 22, + 2x2 < 30 - x - 2242 -10 and x, zo ; Change inequalities into equations by adding slack variable. Max Z = -2, -32% + OS, +0S2 Audio St. 24, + 2x2 + Stos= 30 10 -2, + 2x2 +0S, 7 S and 4,32 , S, Sz 20. ". . # Simplex table ! 5 -2 | B C 1 XB I s, Is, ol 30 2 se 01-10-1 z =0 Zj0 Zj-G 1 2 -3 0 0 xz s S2 2 Tol F2 oito 0 0 0 3 0 0 Z; = {fposti] 2,- (o)(2) + )-1)=0 22 = )(2)+(0)(-2)=0 mase (-ne) Ratio 1-2 =15 - - - Z;-41 S2 S2 minimum XB 3-10 so ; .max C-ve) ratio : entering vector = maxve) ratio - 1.5 departing vector 2 minimum (-ve) XB -10) .

Here key element = F2 entering variable = xz , depaseting varicelde - Sz . # !13;= { [pixy R₂ = R₂ + (-2) Ri= R, -2Rz(new) Simplex table :-? 1-2 -3 0 0 BC8XBxi 22 8Sz] 7. : s, o 2010 ! x - s 0.5 l o. -0.51 | 23-15 | 2; -1.5 -3 0 1:57 12;-cj 0.5 0.0 1.57. rout jo - - 1 2 = ( 0 1 ).+ (-3).5) -1.5 2,- (0) (0)+(-3)(1) TC since all z; -cj zo and all XB Zo this the current sol@ is the optimal sole. , so, x, =0 ;32= 5 noin max z = -2(0)+(3)(5) = -15 i min za 15/ # Graphically - 22, + 23, 330 rxol 157 22 1510 x, + 222 210 e lolio H21 51 o. 7-21 I points ACO,157 B (15,0) (c (10,0) Toco,si | 2= 20,+ 3x2 2 = 45 2= 30 MN NNN 1 =2.0 2 =15 no min z =15 , n = o ; 2=5

-20 (0, 15) (0, 5) 20 (15, 0) (20, -5)

c) .. Min Z: 404, + 232 Sit. 2, + x2 21 3x,-* N₂ 32 and x, ,42 20 To apply dual simplex iteration method , first convert Minz to Man 2 and convert all (2) inequalities into (s) by multiply So, Max ze .4*, -272 Sit. 54, + x2 = 11:: -32, +2₂5-2 and se, ,H2zo. Change inequalities into aqun by adding artificial variable and slack varicelle Max Z = -4*, - 2262 + OS, - MA sit. x, + H2 + os, + A, 31 .. , -32, + x2 + S + OA'= -2 and a 22,S, ,A, zo S, = slack variable 4, 5 Grtificial variable , add because sine. constraints type: I simplex table in -4 XB 2, -2.1.0". 22 S -M*** Al B CB A iz; -M -M ; -MS 21-6; -M+4 -M+2 0 0 Ration -.12 Here all . 2; -C; co so optimal besic feasible solution not possible from this, method.

change in dual

(c) Min z = 4x + 2x2 .. Sit. 24, + X 1 3x, -2₂ 32 21,42 20 first change given problem into cual problem max 2,5 , +2712 Sat. 21, +372 =4 w; -712. 12 Change inequalities into eq" by adding artificial variable (A) and Slack varialde (5) artificial variable when constraints "=" types slack variable when constraints "s" types so, - Man z = x + 2x2 tos, MAI Sit. 7, + 371, +os + A, 24 z, - X; + S, P0A, -2 # simplene and 2,772 ,S, A 20 table !-1 . TG o xe lx, xz S, 4 1 3 0 . M A, I Min Ratio B XB/x2 co -M 415= 133 -> Tz; T-M 2;-4 M-1 -3M +3M-2 -M 0 0 1 entering rector minimimum (2; -C;) = -3M-2

departing vector positive Min lectio 1:33 so, key element - 3. . entering variable = H2, departing variable = A, # Simplex table :-2 . R = R2= R + 3 R2 + R, (new) Min patio X8/x, 1-336 0.33 s, 0 Gli 20 XB x X₂ S, 1:33 0.33 il 3.33 [133] 0 ' Z; 0.667 .2 3; -0; -0.33 0 0 3.33-46- 3.33. 1.33 no entering vector minimum (-ve) z;-(; = -0.33 .. departing vector positive Min Ratio = 2.5 So, key element = /1,33) i entering variable = x, depasting variable - S, #simplex table :-3 R2 = R2 + 1.33 R, ER, - 0.33(R2) (new) T T 2 .0 T MinRatiol ng B TCB | XB | a, . *2. s, 20. 50 -0.25 Il 2.5 i 0 0.75 | 2; II 2 0.25 [zj-C; o o 0.25

9,= 2.5,42=0.5 L since all 2; -; 20 so optimal solution is max z = 3.5. So minimum z = 3.5] #Graphically :- Min z: 4, + 272 Sit. 20, +=1 3%, -2222 2, +=1 31,-4272 17, olīv a To 0:671... 14, 1-2) 0.1. 320-%2= x Ist ei 7,+12-1 . points a A(0.75,0.25) 2= ux,+2212 ?= 3:5. 2-u i B (1,0) Min z = 3.5

(0,1) -0.5 (0.75, 0.25) (0.667, 0) (1,0) -0.5