Question

Use the Big M method to find the optimal solution to the following LP:

min z = -3x₁ + x₂

s.t. X₁ - 2x2 $\geq$    2

-x₁ + x_{2 $\geq$} 3

x_1, x₂ $\geq$ 0

Answer 1

Min Z = - 3x1 + x2 subject to X1 - 2x222 - X1 + X223 and x1,x220; The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate 1. As the constraint-1 is of type'>' we should subtract surplus variable S, and add artificial variable 4, 2. As the constraint-2 is of type ''we should subtract surplus variable S, and add artificial variable A2 After introducing surplus,artificial variables Min Z = - 3x1 + x2 + 0 S1 + 0 S2 + M41 + M42 subject to X1 - 2x2 - Si + A1 = 2 - X1 + 12 - S2 42 = 3 and x1,x2, 51. 52.41,4220 Iteration-1 -3 1 0 0 M M MinRatio XB B CB XB X X2 Si S2 41 42 X1 41 M 2 (1) -2 -1 0 1 0 * =2- 42 M 3 -1 1 0 - 1 0 1 Z = 5M 0 -M -M -M M M Z; 2;-9 31 -M-1 -M -M 0 0

Positive maximum Z;- C; is 3 and its column index is 1. So, the entering variable is x1. Minimum ratio is 2 and its row index is 1. So, the leaving basis variable is 41- · The pivot element is 1. Entering = x1, Departing = A4, Key Element = 1 + R, (new) = RZ (old) + R (new) = Rz(old) + R, (new) Iteration 2 C -3 1 0 0 M B CB XB xi X2 Si S, A2 MinRatio * 1 -3 2 1 -2 - 1 0 0 42 M 5 0 -1 -1 -1 1 Z = 5M-6 -3 -M+6 -M +3 -M M Z; Z; - C; 0 -M+5 -M-3 -M 0 Since all Z; -C;s0 Hence, optimal solution is arrived with value of variables as: *1 = 2.x2 = 0 Min Z= -6