Duality and Sensitivity Analysis Questions and Answers

Q: Consider the LP problem :Max \(Z = 4x_{1} + 2x_{2}\)Subject to the constraints :\(-x_{1} - x_{2} \le -3\)\(-x_{1} + x_{2} \ge -2\) and\(x_{1}, x_{2} \ge 0.\)Then the dual of the LP problem is :Min. \(W = ay_{1} + by_{2}\)\(-py_{1} + qy_{2} \ge 4\)\(-y_{1} - y_{2} \ge 2\) and \(y_{1}, y_{2} \ge 0\)where the values of \(a, b, p, q\) are :

The values are \(a = -3, b = 2, p = 1, q = 1\).For a maximisation problem, write every constraint as \(\le\). The second constraint \(-x_{1} + x_{2} \ge -2\) becomes \(x_{1} - x_{2} \le 2\). The primal is then\[ \begin{aligned} -x_{1} - x_{2} &\le -3 \\ x_{1} - x_{2} &\le 2 \end{aligned} \]The dual minimises \(W = -3y_{1} + 2y_{2}\) (the right-hand sides), with one constraint for each primal variable using the columns of coefficients: for \(x_{1}\), \(-y_{1} + y_{2} \ge 4\), and for \(x_{2}\), \(-y_{1} - y_{2} \ge 2\). Matching \(-py_{1} + qy_{2} \ge 4\) gives \(p = 1, q = 1\), and \(a = -3, b = 2\). The other options get a sign wrong in the objective or in the first constraint.

Q: Consider the non-linear programming problemMax. \(Z = 10x_{1} - x_{2}^{2}\)Subject to the constraints :\(x_{1} + x_{2} \le 14\)\(-x_{1} + x_{2} \le 6\) and \(x_{1}, x_{2} \ge 0\)Then the Lagrangian function is :

The Lagrangian is \((10x_{1} - x_{2}^{2}) - \lambda_{1}g_{1} - \lambda_{2}g_{2}\), where \(g_{1} = x_{1} + x_{2} + r_{1}^{2} - 14\) and \(g_{2} = -x_{1} + x_{2} + r_{2}^{2} - 6\).Each inequality \(g_{i}(x) \le b_{i}\) is turned into an equation by adding a squared slack variable, \(g_{i} + r_{i}^{2} = b_{i}\), which keeps the slack non-negative automatically. The Lagrangian for maximising \(f\) subtracts \(\lambda_{i}\) times each constraint written as \(g_{i} + r_{i}^{2} - b_{i} = 0\).Option B uses slacks \(r_{i}\) without squares, which would need a separate sign restriction; option C rewrites the constraints wrongly; and option D changes the objective to \(10x_{1} + x_{2}^{2}\).

Q: Consider the LP problem :Max \(Z = x_{1} - x_{2} + 3x_{3}\)Subject to the constraints :\(x_{1} + x_{2} + x_{3} \le 10\)\(2x_{1} - x_{2} - x_{3} \le 2\)\(2x_{1} - 2x_{2} - 3x_{3} \le 6\) and \(x_{1}, x_{2}, x_{3} \ge 0\).Then the dual of the above LP problem is :Min \(W : py_{1} + qy_{2} + ry_{3}\)Subject to the constraints :\(ay_{1} + by_{2} + cy_{3} \ge 1\)\(y_{1} - y_{2} - 2y_{3} \ge -1\)\(y_{1} - y_{2} - 3y_{3} \ge 3\) and \(y_{1}, y_{2}, y_{3} \ge 0\)where the values of \(p, q, r, a, b, c\) are :

The values are \(p = 10, q = 2, r = 6, a = 1, b = 2, c = 2\).For a maximisation problem with \(\le\) constraints and non-negative variables, the dual minimises the right-hand sides times the dual variables, and each primal column gives a \(\ge\) constraint:Objective: \(10y_{1} + 2y_{2} + 6y_{3}\), so \(p = 10, q = 2, r = 6\).Column of \(x_{1}\): coefficients 1, 2, 2, so \(y_{1} + 2y_{2} + 2y_{3} \ge 1\), giving \(a = 1, b = 2, c = 2\).Columns of \(x_{2}\) and \(x_{3}\): \(y_{1} - y_{2} - 2y_{3} \ge -1\) and \(y_{1} - y_{2} - 3y_{3} \ge 3\), as printed.The other options change signs of the right-hand sides or of the first column, which the primal does not have.

Q: Consider the LPP :Minimize \(Z = 4x_{1} + 6x_{2} + 18x_{3}\)Subject to : \(x_{1} + 3x_{2} \ge 3\),\(x_{2} + 2x_{3} \ge 5\)and \(x_{1}, x_{2}, x_{3} \ge 0\).Then, which of the following is not a constraint in the corresponding dual problem ? (Assume that \(w_{1}\) and \(w_{2}\) are the dual variables.)

The statement that is not a dual constraint is \(3w_{1} + w_{2} \ge 6\).For a minimisation primal with \(\ge\) constraints and non-negative variables, the dual is to maximise \(3w_{1} + 5w_{2}\) subject to one \(\le\) constraint per primal variable:\(x_{1}\): \(w_{1} \le 4\)\(x_{2}\): \(3w_{1} + w_{2} \le 6\)\(x_{3}\): \(2w_{2} \le 18\), i.e. \(w_{2} \le 9\)\(w_{1}, w_{2} \ge 0\)The constraint for \(x_{2}\) is \(3w_{1} + w_{2} \le 6\); option C has the inequality reversed, so it is not a constraint of the dual. The others are.

Q: Let us consider the following primal problem :Maximize \(z = 2x_{1} + x_{2}\)Subject to \(x_{1} - x_{2} \le 4\),\(x_{1} - x_{2} \le 2\),\(x_{1}, x_{2} \ge 0\)What will be its dual problem ?

The dual is infeasible.The primal is unbounded. Take \(x_{1} = x_{2} + 2\): both constraints hold (\(x_{1} - x_{2} = 2\)), and\[ z = 2(x_{2} + 2) + x_{2} = 3x_{2} + 4 \]which grows without limit as \(x_{2}\) increases. By duality, if the primal is unbounded the dual has no feasible solution. Directly, the dual is to minimise \(4y_{1} + 2y_{2}\) subject to \(y_{1} + y_{2} \ge 2\) and \(-y_{1} - y_{2} \ge 1\) with \(y \ge 0\); the second constraint needs \(y_{1} + y_{2} \le -1\), which is impossible.So the dual cannot be feasible, and it cannot be unbounded, since an unbounded problem must first be feasible.

Q: For the LPPMin : 4x + 6y + 18zs.t. x + 3y ≥ 3;y + 2z ≥ 5;x, y, z ≥ 0,which of the following is not a constraint in the corresponding dual ?

The inequality that is not a dual constraint is \(3u + v \ge 6\).The primal is a minimisation with \(\ge\) constraints and non-negative variables, so the dual is: maximise \(3u + 5v\) subject to\[ \begin{aligned} u &\le 4 \quad (\text{column of } x) \\ 3u + v &\le 6 \quad (\text{column of } y) \\ 2v &\le 18,\ \text{i.e. } v \le 9 \quad (\text{column of } z) \\ u, v &\ge 0 \end{aligned} \]The y-column constraint is \(3u + v \le 6\); option C reverses the inequality, so it is not a dual constraint. Options A, B and D appear in the dual exactly as written.

11.

Consider the LP problem :

Max \(Z = 4x_{1} + 2x_{2}\)

Subject to the constraints :
\(-x_{1} - x_{2} \le -3\)
\(-x_{1} + x_{2} \ge -2\) and
\(x_{1}, x_{2} \ge 0.\)

Then the dual of the LP problem is :

Min. \(W = ay_{1} + by_{2}\)
\(-py_{1} + qy_{2} \ge 4\)
\(-y_{1} - y_{2} \ge 2\) and \(y_{1}, y_{2} \ge 0\)

where the values of \(a, b, p, q\) are :

A.\(a = -3, b = -2, p = -1, q = -1\)
B.\(a = 3, b = 2, p = -1, q = -1\)
C.\(a = -3, b = 2, p = 1, q = 1\)
D.\(a = 3, b = 2, p = -1, q = 1\)

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The values are \(a = -3, b = 2, p = 1, q = 1\).

For a maximisation problem, write every constraint as \(\le\). The second constraint \(-x_{1} + x_{2} \ge -2\) becomes \(x_{1} - x_{2} \le 2\). The primal is then

\[ \begin{aligned} -x_{1} - x_{2} &\le -3 \\ x_{1} - x_{2} &\le 2 \end{aligned} \]

The dual minimises \(W = -3y_{1} + 2y_{2}\) (the right-hand sides), with one constraint for each primal variable using the columns of coefficients: for \(x_{1}\), \(-y_{1} + y_{2} \ge 4\), and for \(x_{2}\), \(-y_{1} - y_{2} \ge 2\). Matching \(-py_{1} + qy_{2} \ge 4\) gives \(p = 1, q = 1\), and \(a = -3, b = 2\). The other options get a sign wrong in the objective or in the first constraint.

Discuss in Forum

12.

Consider the non-linear programming problem

Max. \(Z = 10x_{1} - x_{2}^{2}\)

Subject to the constraints :
\(x_{1} + x_{2} \le 14\)
\(-x_{1} + x_{2} \le 6\) and \(x_{1}, x_{2} \ge 0\)

Then the Lagrangian function is :

A.\((10x_{1} - x_{2}^{2}) - \lambda_{1}(x_{1} + x_{2} + r_{1}^{2} - 14)\) \(- \lambda_{2}(-x_{1} + x_{2} + r_{2}^{2} - 6)\)
B.\((10x_{1} - x_{2}^{2}) + \lambda_{1}(x_{1} + x_{2} + r_{1} - 14)\) \(+ \lambda_{2}(-x_{1} + x_{2} + r_{2} - 6)\)
C.\((10x_{1} - x_{2}^{2}) + \lambda_{1}(-x_{1} + x_{2} - r_{1} - 14)\) \(+ \lambda_{2}(x_{1} - x_{2} - r_{2} + 6)\)
D.\((10x_{1} + x_{2}^{2}) + \lambda_{1}(x_{1} + x_{2} - r_{1}^{2} + 14)\) \(+ \lambda_{2}(x_{1} - x_{2} - r_{2}^{2} + 6)\)

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: A

The Lagrangian is \((10x_{1} - x_{2}^{2}) - \lambda_{1}g_{1} - \lambda_{2}g_{2}\), where \(g_{1} = x_{1} + x_{2} + r_{1}^{2} - 14\) and \(g_{2} = -x_{1} + x_{2} + r_{2}^{2} - 6\).

Each inequality \(g_{i}(x) \le b_{i}\) is turned into an equation by adding a squared slack variable, \(g_{i} + r_{i}^{2} = b_{i}\), which keeps the slack non-negative automatically. The Lagrangian for maximising \(f\) subtracts \(\lambda_{i}\) times each constraint written as \(g_{i} + r_{i}^{2} - b_{i} = 0\).

Option B uses slacks \(r_{i}\) without squares, which would need a separate sign restriction; option C rewrites the constraints wrongly; and option D changes the objective to \(10x_{1} + x_{2}^{2}\).

Discuss in Forum

13.

Consider the LP problem :

Max \(Z = x_{1} - x_{2} + 3x_{3}\)

Subject to the constraints :
\(x_{1} + x_{2} + x_{3} \le 10\)
\(2x_{1} - x_{2} - x_{3} \le 2\)
\(2x_{1} - 2x_{2} - 3x_{3} \le 6\) and \(x_{1}, x_{2}, x_{3} \ge 0\).

Then the dual of the above LP problem is :

Min \(W : py_{1} + qy_{2} + ry_{3}\)

Subject to the constraints :
\(ay_{1} + by_{2} + cy_{3} \ge 1\)
\(y_{1} - y_{2} - 2y_{3} \ge -1\)
\(y_{1} - y_{2} - 3y_{3} \ge 3\) and \(y_{1}, y_{2}, y_{3} \ge 0\)

where the values of \(p, q, r, a, b, c\) are :

A.\(p = 10,\ q = 2,\ r = -6,\ a = -1,\ b = 2,\ c = -2\)
B.\(p = 10,\ q = 2,\ r = 6,\ a = 1,\ b = 2,\ c = 2\)
C.\(p = 10,\ q = -2,\ r = -6,\ a = -1,\ b = -2,\ c = 2\)
D.\(p = -10,\ q = 2,\ r = 6,\ a = -1,\ b = -2,\ c = 2\)

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

The values are \(p = 10, q = 2, r = 6, a = 1, b = 2, c = 2\).

For a maximisation problem with \(\le\) constraints and non-negative variables, the dual minimises the right-hand sides times the dual variables, and each primal column gives a \(\ge\) constraint:

Objective: \(10y_{1} + 2y_{2} + 6y_{3}\), so \(p = 10, q = 2, r = 6\).
Column of \(x_{1}\): coefficients 1, 2, 2, so \(y_{1} + 2y_{2} + 2y_{3} \ge 1\), giving \(a = 1, b = 2, c = 2\).
Columns of \(x_{2}\) and \(x_{3}\): \(y_{1} - y_{2} - 2y_{3} \ge -1\) and \(y_{1} - y_{2} - 3y_{3} \ge 3\), as printed.

The other options change signs of the right-hand sides or of the first column, which the primal does not have.

Discuss in Forum

14.

Consider the LPP :

Minimize \(Z = 4x_{1} + 6x_{2} + 18x_{3}\)

Subject to : \(x_{1} + 3x_{2} \ge 3\),
\(x_{2} + 2x_{3} \ge 5\)
and \(x_{1}, x_{2}, x_{3} \ge 0\).

Then, which of the following is not a constraint in the corresponding dual problem ? (Assume that \(w_{1}\) and \(w_{2}\) are the dual variables.)

A.\(w_{1} \le 4\)
B.\(w_{2} \le 9\)
C.\(3w_{1} + w_{2} \ge 6\)
D.\(w_{1} \ge 0,\ w_{2} \ge 0\)

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

The statement that is not a dual constraint is \(3w_{1} + w_{2} \ge 6\).

For a minimisation primal with \(\ge\) constraints and non-negative variables, the dual is to maximise \(3w_{1} + 5w_{2}\) subject to one \(\le\) constraint per primal variable:

\(x_{1}\): \(w_{1} \le 4\)
\(x_{2}\): \(3w_{1} + w_{2} \le 6\)
\(x_{3}\): \(2w_{2} \le 18\), i.e. \(w_{2} \le 9\)
\(w_{1}, w_{2} \ge 0\)

The constraint for \(x_{2}\) is \(3w_{1} + w_{2} \le 6\); option C has the inequality reversed, so it is not a constraint of the dual. The others are.

Discuss in Forum

15.

Let us consider the following primal problem :

Maximize \(z = 2x_{1} + x_{2}\)
Subject to \(x_{1} - x_{2} \le 4\),
\(x_{1} - x_{2} \le 2\),
\(x_{1}, x_{2} \ge 0\)

What will be its dual problem ?

A.Dual feasible
B.Dual infeasible
C.Dual feasible and unbounded
D.Dual unbounded

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: B

The dual is infeasible.

The primal is unbounded. Take \(x_{1} = x_{2} + 2\): both constraints hold (\(x_{1} - x_{2} = 2\)), and

\[ z = 2(x_{2} + 2) + x_{2} = 3x_{2} + 4 \]

which grows without limit as \(x_{2}\) increases. By duality, if the primal is unbounded the dual has no feasible solution. Directly, the dual is to minimise \(4y_{1} + 2y_{2}\) subject to \(y_{1} + y_{2} \ge 2\) and \(-y_{1} - y_{2} \ge 1\) with \(y \ge 0\); the second constraint needs \(y_{1} + y_{2} \le -1\), which is impossible.

So the dual cannot be feasible, and it cannot be unbounded, since an unbounded problem must first be feasible.

Discuss in Forum

16.

For the LPP

Min : 4x + 6y + 18z
s.t. x + 3y ≥ 3;
y + 2z ≥ 5;
x, y, z ≥ 0,

which of the following is not a constraint in the corresponding dual ?

A.\(u \le 4\)
B.\(v \le 9\)
C.\(3u + v \ge 6\)
D.\(u, v \ge 0\)

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: C

The inequality that is not a dual constraint is \(3u + v \ge 6\).

The primal is a minimisation with \(\ge\) constraints and non-negative variables, so the dual is: maximise \(3u + 5v\) subject to

\[ \begin{aligned} u &\le 4 \quad (\text{column of } x) \\ 3u + v &\le 6 \quad (\text{column of } y) \\ 2v &\le 18,\ \text{i.e. } v \le 9 \quad (\text{column of } z) \\ u, v &\ge 0 \end{aligned} \]

The y-column constraint is \(3u + v \le 6\); option C reverses the inequality, so it is not a dual constraint. Options A, B and D appear in the dual exactly as written.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Duality and Sensitivity Analysis Questions and Answers || Duality and Sensitivity Analysis MCQ Questions and Answers || Duality and Sensitivity Analysis GK Questions and Answers || Duality and Sensitivity Analysis GK MCQ Questions || Duality and Sensitivity Analysis Multiple Choice Questions and Answers || Duality and Sensitivity Analysis GK || GK on Duality and Sensitivity Analysis || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research

Duality and Sensitivity Analysis Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications