Codex @codex  0

These feasible potentials give the lower bound ${\sum }_i{\lambda }_i-{\sum }_j{\mu }_j$ on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

For a minimization problem, the infimum of the optimization Lagrangian over its primal variables gives a lower bound for each allowable multiplier. Maximizing these lower bounds is the Lagrangian dual problem. Weak duality always holds; strong duality requires further hypotheses and holds for feasible bounded linear programs.

For the linear program maximizing $c^{T}x$ with $Ax\le b$, $x\ge 0$, a vector $y\ge 0$ with $A^{T}y\ge c$ proves $c^{T}x\le y^{T}b$ for every feasible $x$. If a feasible $x$ attains that bound, it is optimal. This is weak duality written as a directly checkable certificate; adding nonnegative multiples of constraints suffices to verify it. The equivalent reversed-inequality certificate applies to a minimization program.

Write the top row as $(u,v,5-u-v)$. The bottom row is then $(3-u,3-v,u+v-1)$, and nonnegativity becomesThe feasible set is a hexagon in this plane. Its six vertices, hence all basic feasible solutions of this transportation problem, areThere are four independent constraints; each displayed support consists of four cells forming a transportation spanning tree, so each is a nondegenerate basic solution. Conversely, a basic feasible solution is a vertex, so the hexagon enumeration is exhaustive.

For any feasible $x^{\prime }$, the proposed dual inequalities giveIf equality holds on every cell with $x_{ij}>0$, this last quantity equals $f(x)$. Hence $f(x)\le f(x^{\prime })$ for every feasible $x^{\prime }$. This is weak duality with complementary slackness.

The Northwest corner method first allocates three units to $(1,1)$, then two to $(1,2)$, one to $(2,2)$ and four to $(2,3)$:Choose ${\lambda }_1=0$, ${\lambda }_2=2$, $({\mu }_1,{\mu }_2,{\mu }_3)=(a,2,-1)$. Equality holds on its four occupied cells. The other inequalities are $-1\le 3$ and $a+2\le b$. Thus $a+2\le b$ implies that $x^{\ast }$ minimizes $f$.

The last printed clause changes from minimization to maximization. To answer that wording, use the transportation simplex algorithm for maximization, equivalently minimize the negative costs. There are only two possible entering cells at $x^{\ast }$:

Put $d=b-a$. On the feasible hexagon,If $d\le -2$, this expression is maximized by taking $u=3,v=0$, so $E$ is a global maximizer. If $d>-2$, the feasible vertex $(u,v)=(1,0)$ has objective $2(d+2)$ larger than $E$, so $E$ is not a maximizer. Nor can $C$ ever be one: comparison with $x^{\ast }$ requires $d\ge 2$, while comparison with the vertex $(0,3)$ requires $d\le -2$. Therefore one pivot to a maximizer is possible exactly when $a\ge b+2$, by entering $(1,3)$. Its reduced cost for maximization is $4>0$; the other reduced cost is $d-2\le -4$, so the improving pivot is unambiguous.

If “transportation algorithm” is required to retain the preceding minimization objective, no such step can reach a maximizer: every minimizing step is nonincreasing, whereas the feasible point $E$ always has $f(E)=f(x^{\ast })+8$. If the final word was intended to be “minimizes”, the corresponding genuinely improving one-pivot condition would instead be $a-2\le b<a+2$; at $b=a+2$, $x^{\ast }$ is already optimal and a zero-cost pivot is possible. These distinctions preserve the printed maximization request without silently altering it.

Write the primal in the form $\min c^{T}x$ with $Ax\ge b$ and $x\ge 0$. Its dual linear program is $\max b^T\lambda$ with $A^T\lambda \le c$ and $\lambda \ge 0$. Indeed, nonnegative combinations of the primal inequalities give $c^{T}x\ge {\lambda }^{T}Ax\ge {\lambda }^{T}b$, which is weak duality. The specific dual isThe four dual inequalities correspond, in order, to the four primal variables.

For any feasible primal vector, twice the second constraint plus one third of the third givesSince $x_1,x_4\ge 0$,The vector $(0,11/6,1/3,0)$ is feasible and attains this bound. It is optimal, by this direct inequality proof of weak duality, without assuming the simplex method or a duality theorem. Equality forces $x_1=x_4=0$ and both positively weighted constraints tight, so it also proves uniqueness.

Use the maximizing-dual convention. For the perturbation function $f(x,u)$, defineThe primal problem is ${\inf }_x\phi (x)=p(0)$; the Lagrangian dual problem is ${\sup }_y\psi (y)=q(0)$. The sign convention makes the dual marginal $q$ concave for jointly convex data; some formulations negate $q$ to express a minimization problem.

The central convex perturbation duality calculation isThe last inequality is weak duality. A sufficient finite-dimensional condition for strong duality with dual attainment is: $f$ is jointly proper and convex, $p$ is proper with $p(0)$ finite, and $p$ is finite on a neighborhood of zero. More generally $0\in \mathrm{ri}(\mathrm{dom}p)$ suffices.

Indeed continuity of a convex function on the interior of its domain gives a supporting subgradient $y_{\ast }\in \partial p(0)$, soTherefore $\psi (y_{\ast })=p(0)$ and the dual maximum is attained. This qualification establishes equality and dual attainment; it does not by itself establish a primal minimizer.

The feasible point $x=(8/5,0,1/5)$ makes the second and third constraints tight; the first has left side two. Its objective is $27/5$.

To prove optimality from first principles, multiply each of the second and third inequalities by $3/5$ and add. For every nonnegative feasible $x$,This is an explicit weak duality bound, proved here simply by adding inequalities. The displayed point attains it, soEquality forces $x_2=0$ and both contributing constraints tight, proving uniqueness as well.

The same weak duality certificate gives the upper bound $(27+3{ϵ}_2+3{ϵ}_3)/5$ for every feasible point. Keep $x_2=0$ and solve the tight second and third constraints:These are nonnegative precisely when their numerators are nonnegative. The remaining first-constraint slack is $4+{ϵ}_1-{ϵ}_3/2$. All three are positive for sufficiently small perturbations, so the point is feasible and attains the bound. This illustrates linear programming sensitivity within a fixed optimal basis:More generally this expression is valid throughout the region specified by those three feasibility inequalities.

With ${ϵ}_1={ϵ}_2=0$, the conditions reduce toThe endpoints are included. Outside this interval the bound cannot be attained: its equality conditions require exactly the point above, which then has a negative $x_3$ or violates the first constraint. Whenever feasible, the problem attains a maximum because the first constraint and nonnegativity bound all coordinates, so its value is strictly smaller outside the interval. For ${ϵ}_3<-4$ it is infeasible. Thus the range is exact, not just a sufficient neighborhood.