Duality and Sensitivity Analysis Questions and Answers

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}\).

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.

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.

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.

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.

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.

Answer: C

If the primal linear programming problem has an unbounded solution, its dual has no feasible solution at all. By weak duality, the objective value of every feasible primal solution is bounded by the objective value of any feasible dual solution. If a feasible dual solution existed it would therefore put a finite bound on the primal objective, which contradicts unboundedness.

A feasible or alternative dual solution would give that bound, so those options are wrong. "No bounded solution" is not the standard duality outcome: the dual is not merely unbounded, it is infeasible.