Dual linear program

The duality theorem has an economic interpretation.[2][3] If we interpret the primal LP as a classical "resource allocation" problem, its dual LP can be interpreted as a "resource valuation" problem.

Consider a factory that is planning its production of goods. Let ${\displaystyle x}$ be its production schedule (make ${\displaystyle x_{i}}$ amount of good ${\displaystyle i}$), let ${\displaystyle c\geq 0}$ be the list of market prices (a unit of good ${\displaystyle i}$ can sell for ${\displaystyle c_{i}}$). The constraints it has are ${\displaystyle x\geq 0}$ (it cannot produce negative goods) and raw-material constraints. Let ${\displaystyle b}$ be the raw material it has available, and let ${\displaystyle A\geq 0}$ be the matrix of material costs (producing one unit of good ${\displaystyle i}$ requires ${\displaystyle A_{ji}}$ units of raw material ${\displaystyle j}$).

Then, the constrained revenue maximization is the primal LP:

Maximize c^Tx subject to Ax ≤ b, x ≥ 0.

Now consider another factory that has no raw material, and wishes to purchase the entire stock of raw material from the previous factory. It offers a price vector of ${\displaystyle y}$ (a unit of raw material ${\displaystyle i}$ for ${\displaystyle y_{i}}$). For the offer to be accepted, it should be the case that ${\displaystyle A^{T}y\geq c}$, since otherwise the factory could earn more cash by producing a certain product than selling off the raw material used to produce the good. It also should be ${\displaystyle y\geq 0}$, since the factory would not sell any raw material with negative price. Then, the second factory's optimization problem is the dual LP:

Minimize b^Ty subject to A^Ty ≥ c, y ≥ 0

The duality theorem states that the duality gap between the two LP problems is at least zero. Economically, it means that if the first factory is given an offer to buy its entire stock of raw material, at a per-item price of y, such that A^Ty ≥ c, y ≥ 0, then it should take the offer. It will make at least as much revenue as it could producing finished goods.

The strong duality theorem further states that the duality gap is zero. With strong duality, the dual solution ${\displaystyle y^{*}}$ is, economically speaking, the "equilibrium price" (see shadow price) for the raw material that a factory with production matrix ${\displaystyle A}$ and raw material stock ${\displaystyle b}$ would accept for raw material, given the market price for finished goods ${\displaystyle c}$. (Note that ${\displaystyle y^{*}}$ may not be unique, so the equilibrium price may not be fully determined by ${\displaystyle A}$, ${\displaystyle b}$, and ${\displaystyle c}$.)

To see why, consider if the raw material prices ${\displaystyle y\geq 0}$ are such that ${\displaystyle (A^{T}y)_{i}<c_{i}}$ for some ${\displaystyle i}$, then the factory would purchase more raw material to produce more of good ${\displaystyle i}$, since the prices are "too low". Conversely, if the raw material prices satisfy ${\displaystyle A^{T}y\geq c,y\geq 0}$, but does not minimize ${\displaystyle b^{T}y}$, then the factory would make more money by selling its raw material than producing goods, since the prices are "too high". At equilibrium price ${\displaystyle y^{*}}$, the factory cannot increase its profit by purchasing or selling off raw material.

The duality theorem has a physical interpretation too.[1]^: 86–87

The weak duality theorem says that, for each feasible solution x of the primal and each feasible solution y of the dual: c^Tx ≤ b^Ty. In other words, the objective value in each feasible solution of the dual is an upper-bound on the objective value of the primal, and objective value in each feasible solution of the primal is a lower-bound on the objective value of the dual. Here is a proof for the primal LP "Maximize c^Tx subject to Ax ≤ b, x ≥ 0":

• c^Tx
• = x^Tc [since this just a scalar product of the two vectors]
• ≤ x^T(A^Ty) [since A^Ty ≥ c by the dual constraints, and x ≥ 0]
• = (x^TA^T)y [by associativity]
• = (Ax)^Ty [by properties of transpose]
• ≤ b^Ty [since Ax ≤ b by the primal constraints]

Weak duality implies:

max_x c^Tx ≤ min_y b^Ty

In particular, if the primal is unbounded (from above) then the dual has no feasible solution, and if the dual is unbounded (from below) then the primal has no feasible solution.

The strong duality theorem says that if one of the two problems has an optimal solution, so does the other one and that the bounds given by the weak duality theorem are tight, i.e.:

max_x c^Tx = min_y b^Ty

The strong duality theorem is harder to prove; the proofs usually use the weak duality theorem as a sub-routine.

One proof uses the simplex algorithm and relies on the proof that, with the suitable pivot rule, it provides a correct solution. The proof establishes that, once the simplex algorithm finishes with a solution to the primal LP, it is possible to read from the final tableau, a solution to the dual LP. So, by running the simplex algorithm, we obtain solutions to both the primal and the dual simultaneously.[1]^: 87–89

Another proof uses the Farkas lemma.[1]^: 94

1. The weak duality theorem implies that finding a single feasible solution is as hard as finding an optimal feasible solution. Suppose we have an oracle that, given an LP, finds an arbitrary feasible solution (if one exists). Given the LP "Maximize c^Tx subject to Ax ≤ b, x ≥ 0", we can construct another LP by combining this LP with its dual. The combined LP has both x and y as variables:

Maximize 1

subject to Ax ≤ b, A^Ty ≥ c, c^Tx ≥ b^Ty, x ≥ 0, y ≥ 0

If the combined LP has a feasible solution (x,y), then by weak duality, c^Tx = b^Ty. So x must be a maximal solution of the primal LP and y must be a minimal solution of the dual LP. If the combined LP has no feasible solution, then the primal LP has no feasible solution either.

2. The strong duality theorem provides a "good characterization" of the optimal value of an LP in that it allows us to easily prove that some value t is the optimum of some LP. The proof proceeds in two steps:[4]^{: 260–261}

• Show a feasible solution to the primal LP with value t; this proves that the optimum is at least t.
• Show a feasible solution to the dual LP with value t; this proves that the optimum is at most t.

Consider the primal LP, with two variables and one constraint:

${\displaystyle {\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}$

Applying the recipe above gives the following dual LP, with one variable and two constraints:

${\displaystyle {\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}$

It is easy to see that the maximum of the primal LP is attained when x₁ is minimized to its lower bound (0) and x₂ is maximized to its upper bound under the constraint (7/6). The maximum is 4 · 7/6 = 14/3.

Similarly, the minimum of the dual LP is attained when y₁ is minimized to its lower bound under the constraints: the first constraint gives a lower bound of 3/5 while the second constraint gives a stricter lower bound of 4/6, so the actual lower bound is 4/6 and the minimum is 7 · 4/6 = 14/3.

In accordance with the strong duality theorem, the maximum of the primal equals the minimum of the dual.

We use this example to illustrate the proof of the weak duality theorem. Suppose that, in the primal LP, we want to get an upper bound on the objective ${\displaystyle 3x_{1}+4x_{2}}$. We can use the constraint multiplied by some coefficient, say ${\displaystyle y_{1}}$. For any ${\displaystyle y_{1}}$ we get: ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}$. Now, if ${\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}$and ${\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}$, then ${\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}$, so ${\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}$. Hence, the objective of the dual LP is an upper bound on the objective of the primal LP.

Graphical solution to the farmer example – after shading regions violating the conditions, the vertex of the remaining feasible region with the dashed line farthest from the origin gives the optimal combination (its lying on the pesticide and land lines implies that pesticide and land limit revenue)

Consider a farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P pesticide. To grow one unit of wheat, one unit of land, ${\displaystyle F_{1}}$ units of fertilizer and ${\displaystyle P_{1}}$ units of pesticide must be used. Similarly, to grow one unit of barley, one unit of land, ${\displaystyle F_{2}}$ units of fertilizer and ${\displaystyle P_{2}}$ units of pesticide must be used.

The primal problem would be the farmer deciding how much wheat (${\displaystyle x_{1}}$) and barley (${\displaystyle x_{2}}$) to grow if their sell prices are ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$ per unit.

Maximize: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(maximize the revenue from producing wheat and barley)
subject to:	${\displaystyle x_{1}+x_{2}\leq L}$	(cannot use more land than available)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(cannot use more fertilizer than available)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(cannot use more pesticide than available)
	${\displaystyle x_{1},x_{2}\geq 0}$	(cannot produce negative quantities of wheat or barley).

In matrix form this becomes:

Maximize: ${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

subject to: ${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}$

For the dual problem assume that y unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S₁ for wheat and S₂ for barley. This corresponds to the following LP:

Minimize: ${\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}}$		(minimize the total cost of the means of production as the "objective function")
subject to:	${\displaystyle y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}}$	(the farmer must receive no less than S1 for his wheat)
	${\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}}$	(the farmer must receive no less than S2 for his barley)
	${\displaystyle y_{L},y_{F},y_{P}\geq 0}$	(prices cannot be negative).

In matrix form this becomes:

Minimize: ${\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}$

subject to: ${\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}$

The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?

To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.

The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.

Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.

Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to speak about complementary slackness.

A LP can also be unbounded or infeasible. Duality theory tells us that:

• If the primal is unbounded, then the dual is infeasible;
• If the dual is unbounded, then the primal is infeasible.

However, it is possible for both the dual and the primal to be infeasible. Here is an example:

Maximize: ${\displaystyle 2x_{1}-x_{2}}$
Subject to:	${\displaystyle x_{1}-x_{2}\leq 1}$
	${\displaystyle -x_{1}+x_{2}\leq -2}$
	${\displaystyle x_{1},x_{2}\geq 0.}$