Consider an LPP given as \(\text{Max } Z=2x_1-x_2+2x_3\) subject to the…
2019
Consider an LPP given as
\(\text{Max } Z=2x_1-x_2+2x_3\)
subject to the constraints
\(2x_1+x_2 \leq 10 \\ x_1+2x_2-2x_3 \leq 20 \\ x_1 + 2x_3 \leq 5 \\ x_1, \: x_2 \: x_3 \geq 0\)
What shall be the solution of the LLP after applying first iteration of the Simplex Method?
- A.
\(x_1 = \frac{5}{2},\: x_2=0, \: x_3=0, \: Z=5\) - B.
\(x_1 = 0, x_2=0, \: x_3=\frac{5}{2}, \: Z=5\) - C.
\(x_1 = 0, x_2=\frac{5}{2}, \: x_3=0, \: Z=-\frac{5}{2}\) - D.
\(x_1 = 0, x_2=0, \: x_3=10, \: Z=20\)
Attempted by 2 students.
Show answer & explanation
Correct answer: B
Result after the first Simplex iteration:
Start from the initial basic feasible solution with slack variables:
Initial basic feasible solution: x1 = 0, x2 = 0, x3 = 0; slacks s1 = 10, s2 = 20, s3 = 5; Z = 0.
Objective coefficients for nonbasic variables are 2 (x1), -1 (x2), and 2 (x3). Positive coefficients indicate candidates to enter the basis for maximization; x1 and x3 both have +2.
Choose x3 to enter (a valid tie-break when x1 and x3 tie). Perform the ratio test using rows with positive coefficient of x3:
Constraint 1: coefficient of x3 = 0 → ignored.
Constraint 2: coefficient of x3 = -2 → not eligible (negative).
Constraint 3: coefficient of x3 = 2 → ratio = right-hand side / coefficient = 5 / 2 = 5/2.
Minimum eligible ratio is 5/2 from constraint 3, so pivot on that row: x3 enters with value 5/2, and the slack for constraint 3 leaves (becomes 0).
Compute the new basic solution:
x1 = 0, x2 = 0, x3 = 5/2.
s1 = 10 (unchanged), s2 = 25 (because -2·(5/2) + s2 = 20 ⇒ s2 = 25), s3 = 0.
Objective value: Z = 2·0 - 0 + 2·(5/2) = 5.
Final answer after the first iteration: x1 = 0, x2 = 0, x3 = 5/2, Z = 5.