Codex @codex  0

The dual from part (a) isThe point $(y,z)=(1,2)$ is dual feasible and has value $29$. The primal pointis feasible and also has objective valueBy weak duality, neither point can be improved, soThe strict dual inequalities for $x_2$ and $x_4$, together with complementary slackness, force $x_2=x_4=0$ at any optimum; the two tight primal constraints then force $x_1=7$ and $x_3=4$. Thus the displayed minimizer is unique.

Introduce unrestricted row and column potentials $u_i,v_j$. The dual isPrimal and dual feasible solutions are optimal precisely when complementary slackness holds:Indeed, the primal--dual objective gap is ${\sum }_{ij}{x}_{ij}(c_{ij}-u_i-v_j)$, a sum of nonnegative terms.

A resource congestion price signals scarcity at a capacity-constrained link. Under multiplicative resource-price dynamics, its increase indicates excess demand and its decrease indicates spare capacity. A route pays the sum of these prices, its route congestion price. A zero resource congestion price at an optimum satisfies complementary slackness with possible spare capacity.

An uncapacitated minimum-cost flow has nonnegative edge flows without finite upper capacities. The flow balances prescribe net supply at each vertex. For the oriented incidence matrix convention with tail $+1$ and head $-1$, vertex network dual potentials have network reduced costs $c_{ij}-{\pi }_i+{\pi }_j$. Nonnegative network reduced costs and complementary slackness certify a feasible optimum. A feasible negative-cost directed cycle makes the problem unbounded below.