Solution. \((1, 1) = 5\), exhausting \(D_1\); \((1, 2) = 2\), exhausting \(S_1\); \((2, 2) = 6\), exhausting \(D_2\); \((2, 3) = 3\), exhausting \(S_2\); \((3, 3) = 4\), exhausting \(D_3\); \((3, 4) = 14\). The cost is \[ 5\cdot 19 + 2\cdot 30 + 6\cdot 30 + 3\cdot 40 + 4\cdot 70 + 14\cdot 20 = 95 + 60 + 180 + 120 + 280 + 280 = 1015 . \]

Solution. With \(u_1 = 10\) (any normalisation works): \(v_1 = 9\), \(v_4 = 0\), then \(u_2 = 60\), \(u_3 = 20\), \(v_3 = -20\), \(v_2 = -12\). So \(d_{22} = 30 - 60 + 12 = -18 < 0\). The cycle is \((2, 2)^+ \to (3, 2)^- \to (3, 4)^+ \to (2, 4)^-\); the decreasing cells hold \(8\) and \(2\), so \(\theta = 2\). The new plan has \((2, 2) = 2\), \((3, 2) = 6\), \((3, 4) = 12\), \((2, 4) = 0\), and cost \(779 - 2 \times 18 = 743\), the optimum.

Solution. Supply is \(70\) and demand \(60\), so add a dummy destination \(D_4\) with demand \(10\) and zero cost. Shipments to \(D_4\) are supply left unused at its source; if storage or disposal has a cost, that cost goes in the dummy column.

Solution. Use costs \(c_{ij} = P - p_{ij}\) with \(P = \max p_{ij}\). Every assignment has exactly one entry in each row, so its cost is \(5P\) minus its payoff, and minimising cost is the same as maximising payoff. The costs are non-negative, as the method requires.

Solution. \(\det \begin {pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end {pmatrix} = 1(1 - 0) - 1(0 - 1) + 0 = 2\). The LP “maximise \(x_{12} + x_{23} + x_{13}\) with each vertex covered at most once” has the fractional vertex \(x = (\frac 12, \frac 12, \frac 12)\) with value \(\frac 32\), while the best matching has value \(1\): for non-bipartite graphs the LP needs extra constraints (Edmonds’ odd-set constraints) to be integral.

Solution. A basis has \(2n - 1\) cells, by Proposition 7.1.1. A BFS is a vertex, hence by total unimodularity a permutation matrix, with exactly \(n\) positive entries. So \(n - 1 \geq 1\) basic variables are zero.