Question

for last thing, these are 2 methods that we learned in class

Theorem 1 (Sufficient Optimality Criterion): If x0 and y0 are feasible solutions to the primal and dual problems such that z = cx0 = y0b = w, then x0 and y0 are optimal solutions to their respective problems.

Theorem 2 (Strong Duality): In a primal-dual pair of LPs, if either the primal or the dual problem has an optimal feasible solution, then the other problem does also have an optimal solution and the two optimal objective values are equal.

The objective function can be maximization or minimization. The LP must have at least three decision variables. The LP must have at least three constraints. Solve the LP you create by using the Simplex Method. You can use Big-M or Two-Phase Method if needed. Show each iteration in detail. You should have at least 2 iterations and at most five iterations. If your model is not obeying this rule, please change your model and randomly generate a new model. Make sure that you obtain a single optimal solution. (10 pts) Indicate clearly the optimal basic and nonbasic variables and their values and write the reduced cost of each optimal nonbasic variable. (5 pts) Find the dual of the primal problem you have on hand. (5 pts) Find the optimal dual solution by using the two methods you have learned in class. (10 pts)

Answer 1

I have done all parts for you. KIndly go through.

1. Minimise ; 2x, – 3x2 + 6x2 Subject to : 34,- 4x2 - 6x3 = 2 bort 285, '+ x2 + 2x3,711 x + 3x2 – 2x2 = 5 de po #1, #2, X2 70 | A: Minimize . f(x) = 2x, – 3x2 +683 bo subject to : 3x - 4x₂ - 6x₂ + x4=2 2%, + x2 + 2x, -5 U 8, + 3%, -2%, +46-5 21,22,K3, 44, 45, 4620 : If we put x = x₂ = X₂=0, we get 44=2 , K5=-11 and 28= 5. This is not a basic feasible solations .. so we introduce artificial variables & Now constraints are: 3*, -482-683 + x4=2 24, +82 +243 -345 + X7 = 1). X, + 322 - 233 + x6 = 5 X1, 42, 43, 24, 25, 26, 2770. . 3 equations. So A Variables 7 variables and must be given O. los CamScanne

ie., X,= x, = x3 = Kg = 0. So x4=2, x==11 and x = 5 is the .. basic feasible solution in Now we formulate the ancillary problems Minimize g(x) = *7 subject to : 3%, -4% -6X3 +34 = 2 23, + x2 + 2x3.-257 67 = 11 X1 + 3x2–2xy + Peg = 5 21,42,23,24,25, X6, X7 >0. Now g(x) = 11 2%, –X2 -2X2 +Xg Here we use two-phase method. Iterations : ln ist phase, I iteration, R₂ R₂ Blog Ri - R. + ŚR R g Rot In ist phase, I iteration, R₂ R₃ CALDER, - Ri Re In and phase, I iteration, so we got required " II es values so we stop here. CamScanner

A Basis et Pat B/Pi f - % %-> - M -5/ F M -35 ² sal . N t - - -33 -4. T W + 01 00 - 0 -3 2 Thus mis f(x)= a at 6 1 2 Optimal basic variables : (22,23,24) Optimal non-basic variables : (311, K5, ze] The reduced cost of each optimal nonbasic scovariablen T, = 1% az = ½ [c= / E l CamScanner

Dual of the primal : Primal : Minimize 2x,-34₂ +6*3 subject to : -34, +4% +6X, > - 2 2x, + -H, +223 >11 - %, + 3H2 + 2 H2 > -5 26,62,H3 20. Dual: Maximize -ay, +lly2-593 subject to : -34, +2y-Y3=2 AY, +4₂-Y3€-3 by , +242 +243 € 6. Y, Yz, Y₃ 20. we found that the primal problem has a solution and the solution is a. So by Theorem a (strong Duality), the dual problem also has a solution and the optimal solution - 9. Scanned with CamScanner