Skip to content
We use only essential cookies to keep you signed in and remember your preferences. See our Cookie Policy.
TestStop
MocksPracticeResourcesIndiaBlogPricing
Sign in
Questions › IIT JAM › IIT JAM 2022 › Q22
2 marks, −0.667Mathematics › Constrained optimisation and linear programming › Linear programming dualityHardabout 2 min

IIT JAM 2022 Question 22: Constrained optimisation and linear programming

An initial simplex tableau has CjC_jCj​ row 15,25,0,−M,−M,015, 25, 0, -M, -M, 015,25,0,−M,−M,0 over columns x,y,S1,A1,A2,S3x, y, S_1, A_1, A_2, S_3x,y,S1​,A1​,A2​,S3​, with basis A1A_1A1​ (b=20, row 7,6,−1,1,0,07, 6, -1, 1, 0, 07,6,−1,1,0,0), A2A_2A2​ (b=18, row 3,−2,0,0,1,03, -2, 0, 0, 1, 03,−2,0,0,1,0) and S3S_3S3​ (b=30, row 8,5,0,0,0,18, 5, 0, 0, 0, 18,5,0,0,0,1), and Cj−Zj=15+10M, 25+4M, −M, 0, 0, 0C_j - Z_j = 15+10M,\ 25+4M,\ -M,\ 0,\ 0,\ 0Cj​−Zj​=15+10M, 25+4M, −M, 0, 0, 0. Choose the original linear programming problem, where SiS_iSi​ are slack/surplus and AiA_iAi​ are artificial variables.

Tap an option to check your answer.

Answer and worked solution

Answer: (B)

The objective coefficients 151515 and 252525 are positive and the artificial variables carry the penalty −M-M−M, which is the Big-M setup for a maximization problem, so minimization options are ruled out.

Constraint 1 has a surplus S1S_1S1​ with coefficient −1-1−1 plus an artificial, so it is a ≥\ge≥ constraint: 7x+6y≥207x+6y \ge 207x+6y≥20. Constraint 2 has an artificial but no surplus/slack, so it is an equality: 3x−2y=183x-2y = 183x−2y=18. Constraint 3 has a slack S3S_3S3​, so it is ≤\le≤: 8x+5y≤308x+5y \le 308x+5y≤30. This matches option (B).

The trap: (D) Maximize Z=15x+25yZ = 15x + 25yZ=15x+25y s.t. 7x+6y=207x+6y = 207x+6y=20, 3x−2y=183x-2y = 183x−2y=18, 8x+5y≤308x+5y \le 308x+5y≤30; x,y≥0x,y \ge 0x,y≥0.

Option (D) turns the first constraint into an equality; the presence of a surplus variable S1S_1S1​ with coefficient −1-1−1 marks it as a ≥\ge≥ inequality, not an equation.

Plain-text version

An initial simplex tableau has Cⱼ row 15, 25, 0, -M, -M, 0 over columns x, y, S₁, A₁, A₂, S₃, with basis A₁ (b=20, row 7, 6, -1, 1, 0, 0), A₂ (b=18, row 3, -2, 0, 0, 1, 0) and S₃ (b=30, row 8, 5, 0, 0, 0, 1), and Cⱼ - Zⱼ = 15+10M, 25+4M, -M, 0, 0, 0. Choose the original linear programming problem, where Sᵢ are slack/surplus and Aᵢ are artificial variables. (A) Minimize Z = 15x + 25y s.t. 7x+6y ≥ 20, 3x-2y ≤ 18, 8x+5y ≤ 30; x,y ≥ 0. (B) Maximize Z = 15x + 25y s.t. 7x+6y ≥ 20, 3x-2y = 18, 8x+5y ≤ 30; x,y ≥ 0. (C) Minimize Z = 15x + 25y s.t. 7x+6y ≥ 20, 3x-2y = 18, 8x+5y ≥ 30; x,y ≥ 0. (D) Maximize Z = 15x + 25y s.t. 7x+6y = 20, 3x-2y = 18, 8x+5y ≤ 30; x,y ≥ 0.

Also written as: An initial simplex tableau has C_j row 15, 25, 0, -M, -M, 0 over columns x, y, S_1, A_1, A_2, S_3, with basis A_1 (b=20, row 7, 6, -1, 1, 0, 0), A_2 (b=18, row 3, -2, 0, 0, 1, 0) and S_3 (b=30, row 8, 5, 0, 0, 0, 1), and C_j - Z_j = 15+10M, 25+4M, -M, 0, 0, 0. Choose the original linear programming problem, where S_i are slack/surplus and A_i are artificial variables.

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 2021 · Q22(x₁* = 1, x₂* = 0, x₃* = 2) is optimal for: minimize x₁ + 5x₂ + 2x₃ subject to x₁ - x₂ ≤ 1, x₁ + x₂ + x₃ ≥…
Take this paper as a timed mockMore on Linear programming duality

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