Codex @codex  0

A dual variable is a multiplier associated with a primal constraint in a dual linear program. In a minimization linear program with equality constraints $Ax=b$ and nonnegative primal variables, the Lagrangian $c^{T}x+y^T(b-Ax)$ yields the dual objective $b^{T}y$ and inequalities $A^{T}y\le c$; the equality-constraint multipliers $y$ are unrestricted in sign. For a transportation problem, row and column dual variables give potentials $u_i,v_j$ satisfying $u_i+v_j\le c_{ij}$. Complementary slackness makes occupied routes attain equality.

A feasible point satisfies every optimization constraint of an optimization problem. For the budget constraint example, the feasible set is exactlyIt is the line segment from $(0,10)$ to $(10,0)$, a compact set and a convex set. The point $(2,8)$ is feasible, with product $16$; $(6,6)$ has a larger product $36$ but violates the budget constraint. Feasibility answers whether a decision is allowed; optimality asks whether any allowed decision is better. The extreme value theorem guarantees that this continuous objective function attains its maximum on this nonempty compact set.

Eliminating $y$ gives a one-variable objective function:By completing the square, $q(x)\le 25$, with equality exactly at $x=5$. Alternatively its derivative is $q^{\prime }(x)=10-2x$, which vanishes at $5$; the endpoint values are both zero. Completing the square proves global optimality directly, whereas the first-order optimality condition only identifies a candidate. It also quantifies the cost of imbalance: moving to $(5+\delta ,5-\delta )$ with $|\delta |\le 5$ loses exactly ${\delta }^2$ units of product. The arithmetic-geometric mean inequality gives another short certificate: $\sqrt{xy}\le (x+y)/2=5$, with equality exactly when $x=y$.

For a transportation problem with capacity inequalities, feasibility requires nonnegative shipments, row totals no greater than factory capacities and column totals equal to shop demands. Feasibility alone does not prove minimal cost: a matching transportation dual certificate with capacity inequalities provides an optimality proof. The feasible set can be empty, and a finite infimum need not be attained even when the set is nonempty.

Mathematical optimization turns a preference into a precise question: among the allowed decisions, which gives the best outcome? A model separates the objective function, which measures quality, from the optimization constraints, which determine the feasible set. This language unifies finding a cheap plan for a transportation problem, efficient scheduling, or an accurate model in linear regression. The separation is useful because changing a preference and changing what is possible are different modeling decisions. See Boyd and Vandenberghe, introductory optimization models.

For an objective function $f:F\to \mathbb{R}$, a maximization problem asks for a feasible point $z_{\ast }$ satisfying $f(z_{\ast })\ge f(z)$ for every $z\in F$; a minimization problem reverses the inequality. This is a global extremum. A local maximum or local minimum compares only nearby feasible points, so finding one does not settle the global question.

Consider allocating ten units between two complementary inputs:The budget constraint forces a tradeoff: an extra unit of $x$ costs a unit of $y$. The best allocation is $(5,5)$, with objective function value $25$. Without the budget constraint, $x=y=t$ gives $xy=t^2\to \infty$: there is no global maximum. Constrained optimization can therefore have a finite answer even when the corresponding problem with fewer optimization constraints does not. Its beauty is that geometry, calculus, and an arithmetic-geometric mean inequality can certify the same answer.

With the tail-positive incidence convention, a network edge's reduced cost is $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$. For uncapacitated minimum-cost flow, dual feasibility requires $r_{ij}\ge 0$ and complementary slackness requires $f_{ij}{r}_{ij}=0$. A negative non-tree reduced cost identifies an improving graph cycle pivot in the network simplex algorithm. This sign convention differs from the row-column potentials of a transportation problem.

Measure quantities in thousands of copies. Use five supply rows: initial inventory, regular production in month 1, overtime in month 1, regular production in month 2, overtime in month 2. Their supplies/capacities are $(10,40,150,40,150)$. The three demand columns are the two due dates and a dummy column for unused capacity, with demands $(40,60,290)$, balancing the total supply $390$.

The transportation problem has cost matrixAn infinite entry prohibits delivering a later month's production to an earlier deadline. The extra $20$ in the second column of the early rows accounts for holding stock through the first month. For production rows, the dummy column represents capacity not used, not copies actually printed. Initial inventory assigned to the dummy column would instead remain in stock through both months, costing $40$; this distinguishes physical inventory from optional production capacity. No gratuitous disposal is needed in the optimum.

Let $x_{ij}\ge 0$ have the stated row and column sums, with the forbidden entries zero, and minimize $\sum c_{ij}{x}_{ij}$. A feasible solution isThus regular production is $40$ in each month; overtime is zero then $10$; first-month closing inventory is $10$, and final inventory is zero. Its total production-plus-holding cost isTo prove optimality, use transportation dual potentials $u=(-430,-30,0,-50,0)$ for rows and $v=(430,450,0)$ for columns. Every allowed edge satisfies $u_i+v_j\le c_{ij}$. Multiplying by any feasible shipment and summing gives the lower boundThe proposed shipment attains it, so the schedule is optimal. The dual calculation certifies the minimum without depending on an unshown transportation-simplex iteration.

A balanced transportation problem chooses nonnegative shipments $x_{ij}$ minimizing ${\sum }_{ij}{c}_{ij}{x}_{ij}$, subject to ${\sum }_j{x}_{ij}=s_i$ and ${\sum }_i{x}_{ij}=d_j$, where the total supply equals total demand. For multipliers $u_i,v_j$, its Lagrangian isTaking its infimum over $x_{ij}\ge 0$ produces the linear programming duality problem of maximizing ${\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$ subject to $u_i+v_j\le c_{ij}$. These are the transportation dual potentials.

The transportation simplex algorithm starts with a feasible transportation spanning tree of $m+n-1$ basic entries, obtainable by filling the north-west available cell with the smaller remaining supply or demand. Set $u_i+v_j=c_{ij}$ on basic cells; this determines all potentials up to adding a constant to all $u_i$ and subtracting it from all $v_j$. If all nonbasic reduced costs $r_{ij}=c_{ij}-u_i-v_j$ are nonnegative, feasibility and the dual bound prove optimality. Otherwise let a negative-cost cell enter. It closes a unique cycle in the basic tree. Alternate additions and subtractions around that cycle and choose the largest amount preserving nonnegativity, namely the minimum shipment on the subtraction cells. A cell that reaches zero leaves the basis. The cost changes by the entering reduced cost times the pivot amount. Zero basic cells and an anti-cycling rule can handle degeneracy; all pivots below are nondegenerate.

The north-west initial shipment matrix isWith $u_1=0$, its transportation dual potentials are $u=(0,1,0)$ and $v=(5,9,5)$. The most negative reduced cost is $r_{32}=-7$. The cycle is $+(3,2),-(3,3),+(2,3),-(2,2)$; the pivot amount is $\min (40,46)=40$. HenceNow $u=(0,1,-7)$ and $v=(5,9,5)$. Enter $(1,3)$, of reduced cost $-4$, on cycle $+(1,3),-(1,2),+(2,2),-(2,3)$. The amount is $\min (22,78)=22$, givingThe new potentials are $u=(0,5,-3)$ and $v=(5,5,1)$. Enter $(2,1)$, of reduced cost $-7$, on cycle $+(2,1),-(1,1),+(1,3),-(2,3)$. The amount is $\min (14,56)=14$. ThusTo certify optimality in the original transportation problem, take $u=(0,5,-3)$ and $v=(-2,5,1)$. Their entire reduced-cost matrix isThey satisfy dual feasibility, and their value is $5\cdot 84-3\cdot 40-2\cdot 14+5\cdot 68+78=690$, equal to the shipment cost. The minimum transportation cost is therefore $690$, with no unproved optimality assertion from the iterations alone.

Associate free real dual variables $u_i$ and $v_j$ with the row and column equality constraints. The Lagrangian for the transportation problem isIts infimum over $x_{ij}\ge 0$ is finite exactly when $u_i+v_j\le c_{ij}$ for every pair. The linear programming duality therefore givesThe dual variables have no sign restrictions because the primal constraints are equalities.

A feasible shipment $x$ is optimal if and only if there exist feasible transportation dual potentials satisfying complementary slackness:Thus every occupied route must have $u_i+v_j=c_{ij}$. To see sufficiency explicitly, the primal minus dual objective isand complementary slackness makes it zero. This is the weak duality certificate. Necessity follows from strong duality for the feasible, bounded linear program. If the total supply $M$ is positive, $x_{ij}=a_i{b}_j/M$ gives feasibility; if $M=0$, $x=0$ does. The feasible shipments form a closed bounded set, so the primal optimum is attained. This also covers zero supplies and demands. The one redundant equality merely leaves the dual gauge freedom $(u,v)\mapsto (u+t,v-t)$.

Let $x_{ij}\ge 0$ be shipped amounts, with column sums equal to shop demand and row sums at most 15. Total demand is 42, so three units of warehouse stock need not be shipped. A feasible transportation problem allocation isIts row sums are $(15,15,12)$ and its column sums meet every demand. The cost is $18+18+12+3+4+10=65$.

For a transportation dual certificate with capacity inequalities, choose warehouse potentials $u=(0,-1,0)$ and shop potentials $v=(2,3,2,2,1)$. They have $u_i\le 0$ and $u_i+v_j\le c_{ij}$ for every cell. Any feasible allocation therefore hasThe second inequality has this direction because $u_i\le 0$ and warehouse use is at most 15. The exhibited allocation attains the lower bound, so the minimum cost is $\boxed{65}$.

Let $x_{ij}\ge 0$ be shipments, with column sums eight and row sums at most the four capacities. Total demand is $32$, below total capacity $36$, so unused capacity is allowed. This is a transportation problem with capacity inequalities; equivalently add a dummy shop demanding four units with zero shipping cost.

Using the original PDF's cost $c_{12}=10$, take the feasible solutionIts row totals are $(7,8,8,9)$ and all column totals are eight. Four units of capacity remain unused at the second factory. Its shipping cost is $35+32+28+2+7+16=\boxed{120}$.

To prove that the cost is a global minimum, use the transportation dual certificate with capacity inequalities. If row potentials satisfy $u_i\le 0$ and $u_i+v_j\le c_{ij}$, every feasible solution satisfieswhere $s=(7,12,8,9)$. The second inequality uses the sign of $u_i$: multiplying a capacity upper bound by a nonpositive number reverses it. Choose $u=(0,0,-3,0)$ and $v=(4,7,2,5)$. The reduced costs areso every entry is nonnegative. The lower bound is $-24+8(4+7+2+5)=120$, equal to the displayed shipping cost. The minimum shipping cost is $120$.

For the production costs in a transportation problem, add the production cost of each factory to every real shipment from that factory. Unused capacity incurs no production cost, so the dummy-shop costs remain zero. The resulting real-shop cost matrix isA feasible solution isIts row totals are $(7,12,8,5)$ and column totals remain eight, leaving four units unused at the fourth factory. Its combined cost is $18+32+48+40+32+24+35=229$.

For a matching transportation dual certificate with capacity inequalities, take $u^{\prime }=(-1,-1,-3,0)$ and $v^{\prime }=(7,11,7,9)$. Their reduced costs areall nonnegative. The lower bound is $-7-12-24+8(7+11+7+9)=229$. Thus the minimum combined production and shipping cost is $229$, and the second allocation attains it.

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.

A transportation problem minimizes ${\sum }_{ij}{c}_{ij}{x}_{ij}$ subject to nonnegative shipments, prescribed row supplies, and prescribed column demands.

One optimal shipment table iswhich has the required row sums $(10,8,8)$ and column sums $(3,9,14)$ and costs $4(3)+6(1)+8(3)+3(3)+5(5)=\boxed{76}$.

For an optimality certificate, take row potentials $(1,3,3)$ and column potentials $(0,2,0)$. Their sums equal costs in occupied cells and do not exceed any cost:The dual value is $10+24+24+18=76$, so linear programming duality proves optimality.

A transportation problem chooses nonnegative shipments $x_{ij}$ from $n$ suppliers to $m$ consumers so that row sums equal supplies and column sums equal demands, while minimizing $\sum c_{ij}{x}_{ij}$.

The north-west corner rule givesIt has $3+4-1=6$ positive cells and its support contains no cycle, so it is a nondegenerate basic feasible solution.

A degenerate basic feasible solution isIts five positive cells form a forest with two balanced components; adding one zero cell that joins the components completes a basis of six cells. Thus at least one basic variable is zero.

The stated plan isIts six positive cells form a spanning tree of the supplier--consumer bipartite graph, so it is basic and feasible. Taking $u_1=0$, the basic-cell equations $u_i+v_j=c_{ij}$ giveThe complete matrix of reduced costs ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$ isThe negative entry ${\bar{c}}_{12}=-2$ proves that the plan is not optimal.

Enter cell $(1,2)$. The alternating cycle isand the step is $\theta =\min (3,1)=1$. The new plan iswhose cost is $26$, down from $28$. New potentials areand the reduced-cost matrix isEvery reduced cost is nonnegative, so the transportation optimality criterion shows thatThe zero reduced cost in cell $(2,3)$ also indicates an alternative optimum.

For shipments $x_{ij}\ge 0$ with factory row sums at most capacities $s_i$ and shop column sums exactly demands $d_j$, the displayed dual potentials give $\sum c_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$. The sign $u_i\le 0$ ensures $u_i{\sum }_j{x}_{ij}\ge u_i{s}_i$. Equality proves optimality. It occurs when every used cell is tight and every row with spare capacity has $u_i=0$, the relevant complementary slackness conditions. A dummy demand column with zero costs converts unused capacity into a balanced transportation problem.