2 marks, −0.667MathematicsConstrained optimisation and linear programmingLinear programming dualityHardabout 2 min

IIT JAM 2021 Question 22: Constrained optimisation and linear programming

$(x_1^* = 1, x_2^* = 0, x_3^* = 2)$ is optimal for: minimize $x_1 + 5x_2 + 2x_3$ subject to $x_1 - x_2 \le 1$ , $x_1 + x_2 + x_3 \ge 3$ , $x_1, x_2, x_3 \ge 0$ . If $(\lambda_1^*, \lambda_2^*)$ is an optimal dual solution, then

Tap an option to check your answer.

Answer and worked solution

Answer: (B)

Both constraints are binding at $(1,0,2)$ . Since $x_3 > 0$ , the dual constraint for $x_3$ holds with equality, giving $\lambda_2^* = 2$ ; since $x_1 > 0$ , the dual constraint for $x_1$ gives $-\lambda_1^* + \lambda_2^* = 1$ , so $\lambda_1^* = 1$ .

Thus $\lambda_1^* = 1$ and $\lambda_2^* = 2$ , which satisfies $2\lambda_1^* = \lambda_2^*$ , option (B).

The trap: (D)

\lambda_1^* = \lambda_2^*

The two shadow prices are not equal; complementary slackness pins them at 1 and 2, so the correct relation is $2\lambda_1^* = \lambda_2^*$ .

Plain-text version

(x₁* = 1, x₂* = 0, x₃* = 2) is optimal for: minimize x₁ + 5x₂ + 2x₃ subject to x₁ - x₂ ≤ 1, x₁ + x₂ + x₃ ≥ 3, x₁, x₂, x₃ ≥ 0. If (λ₁*, λ₂*) is an optimal dual solution, then (A) 2λ₁* = 3λ₂* (B) 2λ₁* = λ₂* (C) λ₁* = 2λ₂* (D) λ₁* = λ₂*

Also written as: (x_1* = 1, x_2* = 0, x_3* = 2) is optimal for: minimize x_1 + 5x_2 + 2x_3 subject to x_1 - x_2 <= 1, x_1 + x_2 + x_3 >= 3, x_1, x_2, x_3 >= 0. If (lambda_1*, lambda_2*) is an optimal dual solution, then

Constrained optimisation and linear programming has come up 44 times in 7 exams since 2007.

What this question tests

This question is on Linear programming duality, part of Constrained optimisation and linear programming in Mathematics.

Pairing a linear program with its dual and what their solutions say about each other.

TestStop has 7 past-paper questions on this subtopic; the nearest in year are below.

IIT JAM 2022 · Q22An initial simplex tableau has Cⱼ row 15, 25, 0, -M, -M, 0 over columns x, y, S₁, A₁, A₂, S₃, with basis A₁…

Take this paper as a timed mock More on Linear programming duality

Question from the IIT JAM 2021 paper. Solutions are TestStop's own. Not affiliated with or endorsed by any examination authority.