Duality and Sensitivity Analysis Questions and Answers

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.

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.

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.

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.

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.