Solution. With dual variables \(y_1 \geq 0\) for the \(\geq \) row (in a minimisation) and \(y_2\) free for the equation: maximise \(6y_1 + y_2\) subject to \(y_1 + 2y_2 \leq 3\) (from \(x_1 \geq 0\)), \(y_1 - y_2 = 2\) (from \(x_2\) free), \(y_1 \leq 1\) (from \(x_3 \geq 0\)), \(y_1 \geq 0\), \(y_2\) free.

Solution. The dual is: maximise \(-40w_1 + 30w_2 + 60w_3\) subject to \(-w_1 + 3w_2 + 4w_3 \leq 20\), \(-2w_1 + w_2 + 3w_3 \leq 10\), \(w \geq 0\) (the first primal constraint written as \(-x_1 - 2x_2 \geq -40\)). At \(x = (6, 12)\) the first constraint has slack \(40 - 30 = 10\), so \(w_1 = 0\); both \(x_j > 0\), so both dual constraints are tight: \(3w_2 + 4w_3 = 20\), \(w_2 + 3w_3 = 10\), giving \(w_3 = 2\), \(w_2 = 4\). These are non-negative, so \(w\) is dual feasible, and \(30\cdot 4 + 60\cdot 2 = 240\) equals the primal cost: both are optimal.

Solution. Adding the primal constraints gives \(0 \leq -2\), so the primal is infeasible. The dual is: minimise \(-y_1 - y_2\) subject to \(y_1 - y_2 \geq 1\), \(-y_1 + y_2 \geq 1\), \(y \geq 0\), and adding its constraints gives \(0 \geq 2\): infeasible too. With the objective \(x_1 - x_2\) the dual constraints become \(y_1 - y_2 \geq 1\) and \(-y_1 + y_2 \geq -1\), which force \(y_1 - y_2 = 1\) and are satisfied by \(y = (1 + t, t)\) for every \(t \geq 0\); the dual objective \(-1 - 2t \to -\infty \), so the dual is unbounded, as it must be when the primal is infeasible and the dual feasible.

Solution. \(y_2\) is the value of one more unit of the second resource. If the basis stays optimal, the profit rises by \(4 \times \frac {10}3 = 13.3\), to \(243.3\). Check: with \(2x_1 + x_2 = 26\) and \(2x_1 + 4x_2 = 60\), \(x_2 = \frac {34}3\), \(x_1 = \frac {22}3\), feasible for the third constraint (\(-\frac {22}3 + \frac {34}3 = 4 \leq 5\)), and \(10\cdot \frac {22}3 + 15\cdot \frac {34}3 = \frac {730}3 = 243.3\). How far the resource can change before the basis changes is the subject of the next section.

Solution. Take \(y = (1, 1, 2)\): \(A^{\mathsf T}y = (1 - 1 + 0, 2 + 0 - 2) = (0, 0)\), and \(b^{\mathsf T}y = 1 - 2 + 0 = -1 < 0\). Indeed adding the first constraint, the second and twice the third gives \(0 \leq -1\).

Solution. By weak duality, the primal objective is bounded above by \(b^{\mathsf T}y\) for the feasible \(y\), so (P) is feasible and bounded. A feasible bounded LP has an optimal solution: the simplex method with Bland’s rule terminates, and it cannot end with unboundedness, so it ends at an optimal BFS. By strong duality (D) then has an optimal solution too.