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.

Let $C\in {\mathbb{R}}^{m\times n}$ and $d\in {\mathbb{R}}^m$. For unrestricted $x\in {\mathbb{R}}^n$, the system of linear inequalities $Cx\le d$ has no feasible point if and only if there is a vector $y\in {\mathbb{R}}^m$ withThe entries $y_i$ are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition $C^{T}y=0$ cancels every variable, leaving the contradictionThis is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.

Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates $x_1,x_2$, drawn as $x,y$ in the diagram, must satisfyWrite every row in the same $\le$ direction:Then $C^{T}y=(0,0{)}^T$ and $d^{T}y=-1$. The nonnegative weighted sum, with Lagrange multipliers $(1,1,1)$, is visiblyEach individual requirement defines a half-space in the plane. Even every pair has a feasible point: $(1,1)$ satisfies the first two, $(1,0)$ the first and third, and $(0,1)$ the second and third. Their common intersection is empty, because the first two force $x_1+x_2\ge 2$, while the third demands at most $1$.

Why cancellation is necessary for unrestricted variables. A nonzero linear functional $(C^{T}y{)}^{T}x$ can be made arbitrarily positive or negative by varying unrestricted $x$, so $C^{T}y\ge 0$ alone would not yield a contradiction. Equality is essential here. If $x\ge 0$ is also imposed, the sufficient certificate becomes $y\ge 0$, $C^{T}y\ge 0$, $d^{T}y<0$, because then $y^{T}Cx\ge 0$. This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows $-x_j\le 0$ and use the equality certificate on the enlarged system. Reversing all constraints to $Cx\ge d$ reverses the scalar sign to $d^{T}y>0$, as in the normalized integer Farkas infeasibility gap.

Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute $C^{T}y$ and $d^{T}y$, and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by $-d^{T}y$ normalizes $d^{T}y$ to $-1$. With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual $C^{T}y$ is a diagnostic rather than an exact cancellation: unrestricted $x$ can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.

The same weighted sums give dual bounds. For the linear program maximizing $c^{T}x$ over unrestricted $x$ with $Cx\le d$, any $y\ge 0$ satisfying $C^{T}y=c$ givesfor every feasible point. Minimizing $d^{T}y$ over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize $x_1+x_2$ subject to $-x_1\le 0$, $-x_2\le 0$, $x_1+x_2\le 1$. The multipliers $(0,0,1)$ give the upper bound $1$, attained at $(1,0)$. The infeasibility example above uses the same row directions, but lower bounds of $1$ on both coordinates. Its multipliers cancel the objective function as well as the variables: $c=0$ with $d^{T}y=-1$ would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.

Why every inconsistent system has such a certificate. Introduce a slack variable vector $s\ge 0$ and write $Cx+s=d$. Split the unrestricted vector as $x=u-v$ with $u,v\ge 0$. Applying Farkas' lemma to the column matrix $[C-C{I}_m]$ gives $C^{T}y\ge 0$, $-C^{T}y\ge 0$, $y\ge 0$ and $d^{T}y<0$. The first two conditions together are exactly $C^{T}y=0$. This reduction explains both the equality and the nonnegative row multipliers.

For a linear program $\min \{c^{T}x:Ax=b,x\ge 0\}$ and its dual linear program, write $e=1$, $\bar{b}=b-Ae$, $\bar{c}=c-e$, and $\bar{z}=c^{T}e+1$. Introduce $x,s\ge 0$, $\tau ,\kappa ,\theta ,\rho \ge 0$, and a free multiplier $\lambda$ satisfyingThe point $x=s=e$, $\tau =\kappa =\theta =\rho =1$, $\lambda =0$ is strictly positive in all constrained coordinates. Multiplying the first three equations by ${\lambda }^T,x^T,\tau$ respectively and adding gives the displayed identity. Minimizing $\theta$ has value zero: primal-dual optimal solutions or certificates from Farkas' lemma give zero-$\theta$ solutions after selecting positive $\rho$ and scaling. At $\theta =0$, $\tau >0$ gives an optimal primal-dual pair by division by $\tau$, while $\kappa >0$ gives a primal infeasibility or dual infeasibility certificate. A point with $\tau =\kappa =0$ is not decisive; choosing a relative interior point of the optimal face of a linear program avoids that degeneracy because the face contains a point with $\tau +\kappa >0$.

Remove the integer requirements from the previous formulation to obtain its linear programming relaxation. Give each edge constraint a nonnegative dual variable $y_e$, and each bound for $v\in Z$ a nonnegative dual variable $z_v$. Since all right-hand sides are one, the dual linear program isAn integer feasible point selects a multiset of edges touching every nonisolated vertex, together with at least one singleton for each isolated vertex. Repeated edges or singleton choices can be discarded without losing coverage, so an optimum has a genuine edge cover of the nonisolated part and one singleton per isolated vertex. If $G$ has no isolated vertices, this is exactly an edge cover, with the objective counting selected edges including any unnecessary multiplicities. The isolated-singleton extension is necessary because a graph with an isolated vertex admits no ordinary edge cover.

This interpretation concerns integer feasible dual solutions. The linear programming relaxation can have fractional optima, so its value need not equal the integer independent set optimum. For example, the triangle has relaxed independent-set value $3/2$, whereas its maximum independent set has size $1$ and its minimum edge cover has size $2$.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

Use the standard maximum form of a linear program convention $\max c^{T}u$ subject to $Mu\le b$ and $u\ge 0$. Split the unrestricted variables as $x=x^{+}-x^{-}$ and $y=y^{+}-y^{-}$, with all four new variables nonnegative. The resulting linear program isIf equality-constraint standard form is preferred, add a nonnegative slack variable to each inequality.

Give the two inequalities nonnegative dual variables $\alpha ,\beta$. The dual linear program isThe paired inequalities encode equalities for the two original unrestricted variables. Equivalently, the dual linear program has $2\alpha =2$, $-\alpha +\beta =3$, $\beta \ge 4$, $5\alpha +\beta \ge 7$ and $\alpha ,\beta \ge 0$. Thus its only feasible point is $(\alpha ,\beta )=(1,4)$, of objective function value $13$.

For the linear program in maximization form, a nonnegative multiplier $y$ of the resource inequalities giveswhenever $A^{T}y\ge c$. Equivalently, the Lagrangian is $b^{T}y+(c-A^{T}y{)}^{T}x$; its supremum over $x\ge 0$ is finite exactly when $A^{T}y\ge c$. Minimizing this bound gives the dual linear programThe displayed inequality proves weak duality directly.

For the final simplex tableau, the basic-variable order is $(x_2,x_1)$. With $z_1,z_2$ interpreted as the ordinary unpriced slack variables, its constraint equations giveThe bottom row is read in the reduced-cost convention $r_j=c_j-c_B^T{B}^{-1}{A}_j$, with right side minus the basic objective value. It says the reduced costs of $z_1,z_2$ are $0,-1/2$. Thus optimality requires $z_2=0$, while $z_1$ can increase without changing the objective until $x_2$ reaches zero. The complete primal optimum set is

Reconstructing a linear program from a final simplex tableau exposes a source inconsistency. The slack columns areBecause the first basic column is that of $x_2$, the original constraint data areThe slack reduced costs give $y^T=(0,1/2)$ andConsequently the recovered homogeneous linear program isEvery point in the optimum segment has value $15/2$. Since the segment contains a point with both variables positive, complementary slackness forces both dual column inequalities to be equalities. They give the unique dual optimum

The printed bottom-right entry is $-3$, but it must be $-15/2$ for this linear objective and these constraint rows. Thus no original problem in the stated homogeneous standard form has exactly the entire printed tableau. Changing that one entry to $-15/2$ gives the reconstructed problem above. Alternatively, if an affine objective is permitted, $5x_1-\frac{5}{2}{x}_2-\frac{9}{2}$ has the displayed optimum value $3$ and unchanged reduced costs; the corresponding affine dual objective is $b^{T}y-\frac{9}{2}$. Both interpretations have exactly the same primal and dual optimizer sets. The discrepancy is in the objective constant, not in the optimal segment.

The dual linear program isThe negatives of the final slack payoff coefficients give $\boxed{y^{\ast }=(1,2/3,2/3)}$. Its three dual constraints are equalities, and its objective is $11+32/3+58/3=41$. Equality with the primal objective proves optimality by weak duality, independently of tableau sign conventions. It is also the complementary slackness certificate, with all primal variables and all dual variables strictly positive.

The dual linear program is the minimization problemIndeed, for $y\ge 0$ the optimization Lagrangian $c^{T}x+y^T(b-Ax)$ bounds the primal objective above on its feasible points. Its supremum over $x\ge 0$ is finite precisely when $A^{T}y\ge c$, and then equals $b^{T}y$. The two labelled parts below establish the relevant weak duality and strong duality conclusions.

For the subsequent infeasibility argument, introduce nonnegative slack variables $s$ and the convex coneThis is generated by the columns of $A$ and the coordinate vectors. Here is why this finitely generated cone is closed. Any representation with a minimal number of positive coefficients uses linearly independent generators: otherwise subtract a suitable multiple of a dependence until one positive coefficient vanishes, preserving nonnegativity. For each fixed independent selection of generators, its nonnegative combinations form a closed set, because the inverse coordinate map on its span is continuous. There are finitely many selections, so their union $C$ is closed. This is the closedness of finitely generated cones used in Farkas' lemma.

When the primal linear program is infeasible, $b\notin C$. Let $p$ be the nearest point of $C$ to $b$, and set $h=p-b$. The minimizing property gives $h^T(z-p)\ge 0$ for every $z\in C$. Taking $z=0,2p$ gives $h^{T}p=0$. ConsequentlyIn particular $h\ge 0$ and $A^{T}h\ge 0$. Rescaling $h$ by the positive number $-h^{T}b$ produces the requested Farkas' lemma certificate:Now a feasible point of the relaxed inequalities would satisfySince ${\lambda }^{T}b=-1$, the sum of the nonnegative ${\lambda }_i$ is positive. Thus robust infeasibility under uniform constraint relaxation givesThe ellipsoid method makes progress by reducing the volume of a containing ellipsoid. A nonempty linear polyhedron may have empty interior, so small volume alone cannot certify that the original system is infeasible. Relaxing the inequalities remedies this difficulty, but must not make an infeasible system appear feasible. The displayed positive gap proves exactly that sufficiently small relaxations preserve infeasibility. For rational input, determinant bounds give a Farkas' lemma certificate of polynomial encoding length, so a sufficiently small rational relaxation can be chosen from the input encoding length. Together with a bounding box and bounds on the volume of a relaxed feasible system, this lets the ellipsoid method distinguish infeasibility from a feasible system of very small or zero original volume in polynomial time. The certificate argument alone does not assert a polynomial precision bound for arbitrary unencoded real coefficients.

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.

Introduce nonnegative slack variables $s_1,s_2,s_3$ and start the simplex algorithm at $x=y=z=0$, with slacks $9,8,2$. The objective's largest positive entering coefficient belongs to $y$. Its ratio test is $9/3=3$, $8/2=4$, $2/1=2$, so $s_3$ leaves and $y$ enters.

Solve that pivot row for $y$ and substitute into the other rows and the objective $v$:This is a feasible simplex dictionary at nonbasic variables $x=z=s_3=0$. All their objective coefficients are negative, so no feasible increase can improve the objective. ThusThe negative reduced coefficients also prove uniqueness of this optimum.

The dual linear program, with nonnegative variables $u_1,u_2,u_3$, isThe feasible choice $\boxed{(u_1,u_2,u_3)=(0,0,5)}$ has objective $10$. Weak duality proves that it and the primal point are optimal. Complementary slackness also forces $u_1=u_2=0$ because the first two primal slacks are positive, and then the positive $y$ forces $u_3=5$.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.

Substitute the dual linear program from the previous part and optimize jointly over $x,t,s$. The result isThe objective is linear, and the constraints are equalities or inequalities between affine functions, so this is a linear program. For each fixed feasible $x$, minimizing over $t,s$ gives exactly $f_k(x)$ by the threshold formula for the sum of the largest components; hence the reformulation preserves the optimal value and optimal $x$ whenever an optimum exists.

Introduce slack variables $s_1,s_2,s_3$. In the initial simplex algorithm dictionary, $x_2$ has the largest positive objective coefficient. The ratio test givesso $x_2$ enters and $s_3$ leaves. Solving the third constraint for $x_2$ givesThe objective becomesEvery reduced cost is now nonpositive, so the simplex optimality criterion givesThe other two slacks both equal one.

The dual linear program isThe vectoris dual feasible and has objective value $12$. By weak duality, it and the displayed primal point are optimal; they also satisfy complementary slackness.

If $A$ has $m$ rows and $n$ columns, attach a nonnegative dual variable $y_i$ to each of the $m$ upper-bound constraints. The dual linear program isHere $A^T$ is the transpose of $A$, and all vector inequalities hold componentwise. Nonnegative dual variables preserve the direction of the original inequalities when taking weighted sums.

There are two primal inequalities, so there are two nonnegative dual variables. The five primal variables yield five dual inequalities:Each coefficient column of the primal linear program becomes one row of this dual linear program.

The dual linear program isFor feasible $x,y$, nonnegativity and the two constraint inequalities imply weak duality:If a feasible pair has equal objectives, every primal feasible objective is at most that common value and every dual feasible objective at least it. Thus both feasible solutions are optimal. Strong duality is not needed for this certificate.

For the primal equality-form linear program, the dual linear program isIf $x\ge 0$ is primal feasible and $y$ dual feasible, thenThis proves weak duality. Their objective gap is ${\sum }_j{x}_j((A^{T}y{)}_j-c_j)$, a sum of nonnegative terms. The complementary slackness theorem states that a feasible pair is optimal for the two programmes exactly whenThese conditions make the gap zero, which by weak duality certifies optimality; necessity follows from strong duality.

This convention for standard maximum form of a linear program requires a maximizing linear function, upper-bound linear inequalities, and nonnegative variables. An unrestricted variable becomes the difference of two nonnegative variables; a lower-bound inequality changes sign. The corresponding dual linear program is $\min \{b^{T}y:A^{T}y\ge c,y\ge 0\}$. Adding nonnegative slack variables instead gives the equivalent equality-constraint standard form. Since standard-form terminology varies, state the chosen convention.

For the primal linear program maximising $c^{T}x$ with $Ax\le b$, $x\ge 0$, and its dual linear program minimising $b^{T}y$ with $A^{T}y\ge c$, $y\ge 0$, let $x,y$ be optimal. The complementary slackness identity gives $x_j((A^{T}y{)}_j-c_j)=0$. Thus a strict inequality in the $j$th dual constraint forces $x_j=0$. One optimal dual feasible solution can therefore force zero components in every primal optimum. The same argument with roles reversed says that $y_i>0$ forces the $i$th primal constraint to be an equality.