Duality and Sensitivity Analysis Questions and Answers

Q: If the coefficient of x1 in the objective function is changed from 3 to 1, then which of the following statements is/are true ?(I) x2 enters as a new basic variable in place of x4.(II) The optimal value decreases by 33.33.

Only (I) is true.With \(c_{1} = 1\), the basic variables are \(x_{1}\) (cost 1) and \(x_{4}\) (cost 0). The new \(z_{2} - c_{2}\) is\[ 1(0.75) + 0(2.25) - 2 = -1.25 \lt 0 \]so \(x_{2}\) enters. The ratios are \(30/0.75 = 40\) and \(60/2.25 = 26.67\), so \(x_{4}\) leaves: (I) is true.(Since \(x_{4}\) is basic, its column is really the unit vector (0, 1); the tableau prints 0 in both rows.) After the pivot, \(x_{2} = 26.67\) and \(x_{1} = 30 - 0.75 \times 26.67 = 10\), and the new \(z_{j} - c_{j}\) for \(x_{3}\) and \(x_{4}\) are \(\frac{1}{9}\) and \(\frac{5}{9}\), both non-negative, so this is optimal:\[ Z = 1(10) + 2(26.67) = 63.33 \]The optimal value falls from 90 to 63.33, a decrease of 26.67, not 33.33, so (II) is false.

Q: In a linear programming problem, if a resource is not fully utilized, the shadow price of that resource is

The shadow price is zero.A shadow price is the increase in the optimal objective value from one more unit of a resource. If some of the resource is already left over at the optimum, an extra unit would only add to the slack and could not improve the objective. This is complementary slackness: a constraint with positive slack has a zero dual value.A positive (or, for minimisation, negative) shadow price is possible only for a binding resource, one that is fully used. An infinite shadow price has no meaning for a resource that is not even fully used.

Q: An objective function \(Z\) of primal variables (\(x_{1}\) and \(x_{2}\)) is described below:Minimize \(Z = 0.07x_{1} + 0.05x_{2}\)subject to \(0.1x_{1} \ge 0.4\)\(0.1x_{2} \ge 0.6\)\(0.1x_{1} + 0.2x_{2} \ge 2.0\)\(0.2x_{1} + 0.1x_{2} \ge 1.8\)\(x_{1}, x_{2} \ge 0\)\(W\) is the objective function of the dual of \(Z\). \(k_{1}, k_{2}, k_{3}\), and \(k_{4}\) represent the corresponding dual variables. Which one of the following options represents the correct form of \(W\)?

The correct dual is the one with constraints \(0.1k_{1} + 0.1k_{3} + 0.2k_{4} \le 0.07\) and \(0.1k_{2} + 0.2k_{3} + 0.1k_{4} \le 0.05\).For a minimisation primal with \(\ge\) constraints and non-negative variables, the dual maximises \(b^{T}k\) subject to \(A^{T}k \le c\), \(k \ge 0\). The objective uses the right-hand sides 0.4, 0.6, 2.0, 1.8, which all options share.Each dual constraint comes from one primal variable's column. Column \(x_{1}\) has coefficients 0.1, 0, 0.1, 0.2 and cost 0.07; column \(x_{2}\) has 0, 0.1, 0.2, 0.1 and cost 0.05. That gives exactly the keyed pair.The second option puts \(k_{2}\) in the \(x_{1}\) constraint in place of \(k_{3}\). The third and fourth swap the right-hand sides 0.07 and 0.05 between the columns.

Q: For any primal problem and its dual :

The keyed statement is the primal will have an optimal solution iff the dual does.This is the fundamental duality theorem of linear programming: if either problem has a finite optimal solution, so does the other, and their optimal objective values are equal.The other options are not true 'for any' primal problem. Equal optimal values presuppose that optima exist, which fails when the primal is unbounded or infeasible. 'Both primal and dual can not be infeasible' is false: there are pairs in which both are infeasible, for example maximise \(x_{1}\) subject to \(x_{1} - x_{2} \le -1\), \(-x_{1} + x_{2} \le -1\), \(x \ge 0\), whose dual is also infeasible. 'Optimal solution does not exist' is false in general, since most LPs do have optima.

Q: Consider the following statements :1. Sensitivity analysis provides a single value within which a parameter may change without affecting optimality.2. While performing sensitivity analysis, the upper bound infinity on the right hand side of a constraint means that the constraint is redundant.3. When an additional constraint is added in the LP models, the existing optimal solution can further be improved if \(z_{i} - c_{j} \ge 0\).Which of the above are correct ?

The answer is All are wrong.1 is wrong: sensitivity analysis gives a range (lower and upper limits) within which a cost coefficient or right-hand side can vary without changing the optimal basis, not a single value.2 is wrong: an infinite upper limit on a right-hand side means the constraint has slack at the optimum (it is non-binding), so increasing its right-hand side changes nothing. That does not make it redundant: lowering the right-hand side can make it binding, and removing it can change the feasible region.3 is wrong: adding a constraint can only shrink the feasible region, so the optimal value can stay the same or get worse, never improve. With nothing correct, D is the answer.

Q: Consider the following statements :(1) Changing basic objective function coefficient \(c_{j}\) will affect the entire 0-raw to change.(2) Changing right-hand side of a constraint will retain the current basis to be optimal even if the constraint is negative.(3) Changing the column of a non-basic variable \(x_{j}\) will affect, the coefficient of \(x_{j}\) in row-0 is still non-negative and the current basis is optimal.Which of the above are correct ?

Statements 1 and 3 are correct.1: the reduced costs in row 0 are \(z_{j} - c_{j} = c_{B}B^{-1}a_{j} - c_{j}\). Changing the cost of a basic variable changes \(c_{B}\), and so every entry of row 0 can change, as the statement says.3: changing the column of a non-basic variable \(x_{j}\) affects only its own column of the tableau, so only its row-0 coefficient changes. If that coefficient stays non-negative (for a maximisation), the current basis remains optimal.2 is false: changing a right-hand side changes the values of the basic variables, \(B^{-1}b\). If any of them becomes negative, the current basis is no longer feasible and so no longer optimal; the dual simplex method is then needed.

Q: Let the primal maximization LP problem has \(m\) constraints and \(n\) non-negative variables. Then consider the following two statements about it :(I) The dual have \(n\) constraints and \(m\) non-negative variables.(II) The dual is a minimization problem.Which of the following is true ?

Both statements are true.For a primal 'maximize \(c^{T}x\) subject to \(Ax \le b\), \(x \ge 0\)' with \(m\) constraints and \(n\) variables, the dual is 'minimize \(b^{T}y\) subject to \(A^{T}y \ge c\), \(y \ge 0\)'.Each primal constraint gives one dual variable (\(m\) of them, non-negative for \(\le\) constraints) and each primal variable gives one dual constraint (\(n\) of them), so (I) holds. A maximization primal has a minimization dual, so (II) holds. That rules out every option leaving one of them out.

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 above LP problem is :Min. : \(W = py_{1} + qy_{2}\)Subject to the constraints :\(ry_{1} + sy_{2} \ge 4\)\(-y_{1} - y_{2} \ge 2\)\(y_{1}, y_{2} \ge 0,\)where the values of \(p, q, r, s\) are :

The values are \(p = -3, q = 2, r = -1, s = 1\).For a maximization primal, first write every constraint as \(\le\). The second constraint \(-x_{1} + x_{2} \ge -2\) becomes \(x_{1} - x_{2} \le 2\), so the primal is\[ \begin{aligned} -x_{1} - x_{2} &\le -3 \\ x_{1} - x_{2} &\le 2 \end{aligned} \]The dual minimizes \(-3y_{1} + 2y_{2}\) (right-hand sides), so \(p = -3\), \(q = 2\). Its constraints come from the columns: the \(x_{1}\) column \((-1, 1)\) gives \(-y_{1} + y_{2} \ge 4\), so \(r = -1\), \(s = 1\); the \(x_{2}\) column \((-1, -1)\) gives \(-y_{1} - y_{2} \ge 2\), exactly as printed.The other options get the signs wrong, typically by converting the second constraint incorrectly or by flipping the first row's signs.

Q: If the dual problem has an unbounded solution, then primal has :

The primal has no feasible solution.By weak duality, every feasible primal value bounds every feasible dual value: for a max primal, \(c^{T}x \le b^{T}y\). If the primal had even one feasible point, the dual objective would be bounded by its value and could not be unbounded. So an unbounded dual forces an infeasible primal.The primal cannot then be unbounded or have a feasible solution, which rules out (B) and (C), and 'none of the above' fails because (A) is correct.

Q: Consider the following statements :(I) Dual of the dual is primal.(II) Every solution of an LP problem is a basic feasible solution.Then which of the following is true ?

The answer is only (I) is true.(I) is a basic duality fact: forming the dual of the dual problem returns the original primal problem.(II) is false. Basic feasible solutions are the vertices of the feasible region; most feasible solutions, such as interior points or points along an edge, are not basic. What is true is weaker: if the problem has a feasible (or optimal) solution, then it has a basic feasible (or optimal basic feasible) solution.

Direction for [ Question No: 1 To 1 ] :

The final tableau of the simplex method of the LPP

Max : Z = 3x₁ + 2x₂

is given below :

		x₁	x₂	x₃
		3	2	0
x₁	3	1	0.75	0.25	30
x₄	0	0	2.25	-0.25	60
z_j - c_j :		0	0.25	0.75	90

If the coefficient of x₁ in the objective function is changed from 3 to 1, then which of the following statements is/are true ?

(I) x₂ enters as a new basic variable in place of x₄.
(II) The optimal value decreases by 33.33.

A.Only (I) is true
B.Only (II) is true
C.Both (I) and (II) are true
D.Neither (I) nor (II) is true

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: A

Only (I) is true.

With \(c_{1} = 1\), the basic variables are \(x_{1}\) (cost 1) and \(x_{4}\) (cost 0). The new \(z_{2} - c_{2}\) is

\[ 1(0.75) + 0(2.25) - 2 = -1.25 \lt 0 \]

so \(x_{2}\) enters. The ratios are \(30/0.75 = 40\) and \(60/2.25 = 26.67\), so \(x_{4}\) leaves: (I) is true.

(Since \(x_{4}\) is basic, its column is really the unit vector (0, 1); the tableau prints 0 in both rows.) After the pivot, \(x_{2} = 26.67\) and \(x_{1} = 30 - 0.75 \times 26.67 = 10\), and the new \(z_{j} - c_{j}\) for \(x_{3}\) and \(x_{4}\) are \(\frac{1}{9}\) and \(\frac{5}{9}\), both non-negative, so this is optimal:

\[ Z = 1(10) + 2(26.67) = 63.33 \]

The optimal value falls from 90 to 63.33, a decrease of 26.67, not 33.33, so (II) is false.

Discuss in Forum

In a linear programming problem, if a resource is not fully utilized, the shadow price of that resource is

A.positive
B.negative
C.zero
D.infinity

Exam Year(s)

GATE ME - 2022,

Answer: C

The shadow price is zero.

A shadow price is the increase in the optimal objective value from one more unit of a resource. If some of the resource is already left over at the optimum, an extra unit would only add to the slack and could not improve the objective. This is complementary slackness: a constraint with positive slack has a zero dual value.

A positive (or, for minimisation, negative) shadow price is possible only for a binding resource, one that is fully used. An infinite shadow price has no meaning for a resource that is not even fully used.

Discuss in Forum

An objective function \(Z\) of primal variables (\(x_{1}\) and \(x_{2}\)) is described below:

Minimize \(Z = 0.07x_{1} + 0.05x_{2}\)

subject to \(0.1x_{1} \ge 0.4\)
\(0.1x_{2} \ge 0.6\)
\(0.1x_{1} + 0.2x_{2} \ge 2.0\)
\(0.2x_{1} + 0.1x_{2} \ge 1.8\)
\(x_{1}, x_{2} \ge 0\)

\(W\) is the objective function of the dual of \(Z\). \(k_{1}, k_{2}, k_{3}\), and \(k_{4}\) represent the corresponding dual variables. Which one of the following options represents the correct form of \(W\)?

A.Maximize \(W = 0.4k_{1} + 0.6k_{2} + 2.0k_{3} + 1.8k_{4}\) subject to \(0.1k_{1} + 0.1k_{3} + 0.2k_{4} \le 0.07\); \(0.1k_{2} + 0.2k_{3} + 0.1k_{4} \le 0.05\); \(k_{1}, k_{2}, k_{3}, k_{4} \ge 0\)
B.Maximize \(W = 0.4k_{1} + 0.6k_{2} + 2.0k_{3} + 1.8k_{4}\) subject to \(0.1k_{1} + 0.1k_{2} + 0.2k_{4} \le 0.07\); \(0.1k_{2} + 0.2k_{3} + 0.1k_{4} \le 0.05\); \(k_{1}, k_{2}, k_{3}, k_{4} \ge 0\)
C.Maximize \(W = 0.4k_{1} + 0.6k_{2} + 2.0k_{3} + 1.8k_{4}\) subject to \(0.1k_{1} + 0.1k_{2} + 0.2k_{4} \le 0.05\); \(0.1k_{1} + 0.2k_{3} + 0.1k_{4} \le 0.07\); \(k_{1}, k_{2}, k_{3}, k_{4} \ge 0\)
D.Maximize \(W = 0.4k_{1} + 0.6k_{2} + 2.0k_{3} + 1.8k_{4}\) subject to \(0.1k_{1} + 0.1k_{3} + 0.2k_{4} \le 0.05\); \(0.1k_{2} + 0.2k_{3} + 0.1k_{4} \le 0.07\); \(k_{1}, k_{2}, k_{3}, k_{4} \ge 0\)

Exam Year(s)

GATE ME - 2026,

Answer: A

The correct dual is the one with constraints \(0.1k_{1} + 0.1k_{3} + 0.2k_{4} \le 0.07\) and \(0.1k_{2} + 0.2k_{3} + 0.1k_{4} \le 0.05\).

For a minimisation primal with \(\ge\) constraints and non-negative variables, the dual maximises \(b^{T}k\) subject to \(A^{T}k \le c\), \(k \ge 0\). The objective uses the right-hand sides 0.4, 0.6, 2.0, 1.8, which all options share.

Each dual constraint comes from one primal variable's column. Column \(x_{1}\) has coefficients 0.1, 0, 0.1, 0.2 and cost 0.07; column \(x_{2}\) has 0, 0.1, 0.2, 0.1 and cost 0.05. That gives exactly the keyed pair.

The second option puts \(k_{2}\) in the \(x_{1}\) constraint in place of \(k_{3}\). The third and fourth swap the right-hand sides 0.07 and 0.05 between the columns.

Discuss in Forum

For any primal problem and its dual :

A.optimal value of objective function is same
B.primal will have an optimal solution iff dual does
C.both primal and dual can not be infeasible
D.optimal solution does not exist

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: B

The keyed statement is the primal will have an optimal solution iff the dual does.

This is the fundamental duality theorem of linear programming: if either problem has a finite optimal solution, so does the other, and their optimal objective values are equal.

The other options are not true 'for any' primal problem. Equal optimal values presuppose that optima exist, which fails when the primal is unbounded or infeasible. 'Both primal and dual can not be infeasible' is false: there are pairs in which both are infeasible, for example maximise \(x_{1}\) subject to \(x_{1} - x_{2} \le -1\), \(-x_{1} + x_{2} \le -1\), \(x \ge 0\), whose dual is also infeasible. 'Optimal solution does not exist' is false in general, since most LPs do have optima.

Discuss in Forum

Consider the following statements :

1. Sensitivity analysis provides a single value within which a parameter may change without affecting optimality.
2. While performing sensitivity analysis, the upper bound infinity on the right hand side of a constraint means that the constraint is redundant.
3. When an additional constraint is added in the LP models, the existing optimal solution can further be improved if \(z_{i} - c_{j} \ge 0\).

Which of the above are correct ?

A.Only 1 is correct
B.Only 2 is correct
C.Only 3 is correct
D.All are wrong

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: D

The answer is All are wrong.

1 is wrong: sensitivity analysis gives a range (lower and upper limits) within which a cost coefficient or right-hand side can vary without changing the optimal basis, not a single value.

2 is wrong: an infinite upper limit on a right-hand side means the constraint has slack at the optimum (it is non-binding), so increasing its right-hand side changes nothing. That does not make it redundant: lowering the right-hand side can make it binding, and removing it can change the feasible region.

3 is wrong: adding a constraint can only shrink the feasible region, so the optimal value can stay the same or get worse, never improve. With nothing correct, D is the answer.

Discuss in Forum

Consider the following statements :

(1) Changing basic objective function coefficient \(c_{j}\) will affect the entire 0-raw to change.
(2) Changing right-hand side of a constraint will retain the current basis to be optimal even if the constraint is negative.
(3) Changing the column of a non-basic variable \(x_{j}\) will affect, the coefficient of \(x_{j}\) in row-0 is still non-negative and the current basis is optimal.

Which of the above are correct ?

A.1 and 2 are correct
B.1 and 3 are correct
C.2 and 3 are correct
D.All are correct

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: B

Statements 1 and 3 are correct.

1: the reduced costs in row 0 are \(z_{j} - c_{j} = c_{B}B^{-1}a_{j} - c_{j}\). Changing the cost of a basic variable changes \(c_{B}\), and so every entry of row 0 can change, as the statement says.

3: changing the column of a non-basic variable \(x_{j}\) affects only its own column of the tableau, so only its row-0 coefficient changes. If that coefficient stays non-negative (for a maximisation), the current basis remains optimal.

2 is false: changing a right-hand side changes the values of the basic variables, \(B^{-1}b\). If any of them becomes negative, the current basis is no longer feasible and so no longer optimal; the dual simplex method is then needed.

Discuss in Forum

Let the primal maximization LP problem has \(m\) constraints and \(n\) non-negative variables. Then consider the following two statements about it :

(I) The dual have \(n\) constraints and \(m\) non-negative variables.
(II) The dual is a minimization problem.

Which of the following is true ?

A.Only (I) is true
B.Only (II) is true
C.Both are true
D.Neither (I) nor (II) is true

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

Both statements are true.

For a primal 'maximize \(c^{T}x\) subject to \(Ax \le b\), \(x \ge 0\)' with \(m\) constraints and \(n\) variables, the dual is 'minimize \(b^{T}y\) subject to \(A^{T}y \ge c\), \(y \ge 0\)'.

Each primal constraint gives one dual variable (\(m\) of them, non-negative for \(\le\) constraints) and each primal variable gives one dual constraint (\(n\) of them), so (I) holds. A maximization primal has a minimization dual, so (II) holds. That rules out every option leaving one of them out.

Discuss in Forum

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 above LP problem is :

Min. : \(W = py_{1} + qy_{2}\)

Subject to the constraints :
\(ry_{1} + sy_{2} \ge 4\)
\(-y_{1} - y_{2} \ge 2\)
\(y_{1}, y_{2} \ge 0,\)

where the values of \(p, q, r, s\) are :

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

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: D

The values are \(p = -3, q = 2, r = -1, s = 1\).

For a maximization primal, first write every constraint as \(\le\). The second constraint \(-x_{1} + x_{2} \ge -2\) becomes \(x_{1} - x_{2} \le 2\), so the primal is

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

The dual minimizes \(-3y_{1} + 2y_{2}\) (right-hand sides), so \(p = -3\), \(q = 2\). Its constraints come from the columns: the \(x_{1}\) column \((-1, 1)\) gives \(-y_{1} + y_{2} \ge 4\), so \(r = -1\), \(s = 1\); the \(x_{2}\) column \((-1, -1)\) gives \(-y_{1} - y_{2} \ge 2\), exactly as printed.

The other options get the signs wrong, typically by converting the second constraint incorrectly or by flipping the first row's signs.

Discuss in Forum

If the dual problem has an unbounded solution, then primal has :

A.No feasible solution
B.Unbounded solution
C.Feasible solution
D.None of the above

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: A

The primal has no feasible solution.

By weak duality, every feasible primal value bounds every feasible dual value: for a max primal, \(c^{T}x \le b^{T}y\). If the primal had even one feasible point, the dual objective would be bounded by its value and could not be unbounded. So an unbounded dual forces an infeasible primal.

The primal cannot then be unbounded or have a feasible solution, which rules out (B) and (C), and 'none of the above' fails because (A) is correct.

Discuss in Forum

10.

Consider the following statements :

(I) Dual of the dual is primal.
(II) Every solution of an LP problem is a basic feasible solution.

Then which of the following is true ?

A.Only (II) is true
B.Only (I) is true
C.Both are true
D.Neither (I) nor (II) is true

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The answer is only (I) is true.

(I) is a basic duality fact: forming the dual of the dual problem returns the original primal problem.

(II) is false. Basic feasible solutions are the vertices of the feasible region; most feasible solutions, such as interior points or points along an edge, are not basic. What is true is weaker: if the problem has a feasible (or optimal) solution, then it has a basic feasible (or optimal basic feasible) solution.

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

Direction for [ Question No: 1 To 1 ] :

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications