Dual linear program

In fact, this bounding property holds for the optimal values of the dual and primal LPs.

Suppose we have the linear program: Maximize cTx subject to Ax ≤ b, x ≥ 0.We would like to construct an upper bound on the solution.

The dual LP tries to find such coefficients that minimize the resulting upper bound.

Then, the constrained revenue maximization is the primal LP:Maximize cTx 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.

Then, the second factory's optimization problem is the dual LP:Minimize bTy subject to ATy ≥ c, y ≥ 0The duality theorem states that the duality gap between the two LP problems is at least zero.

would accept for raw material, given the market price for finished goods

, then the factory would make more money by selling its raw material than producing goods, since the prices are "too high".

, the factory cannot increase its profit by purchasing or selling off raw material.

If all constraints have the same sign, it is possible to present the above recipe in a shorter way using matrices and vectors.

Here is a proof for the primal LP "Maximize cTx subject to Ax ≤ b, x ≥ 0":

Weak duality implies:maxx cTx ≤ miny bTyIn 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.

So, by running the simplex algorithm, we obtain solutions to both the primal and the dual simultaneously.

Suppose we have an oracle that, given an LP, finds an arbitrary feasible solution (if one exists).

The combined LP has both x and y as variables:Maximize 1 subject to Ax ≤ b, ATy ≥ c, cTx ≥ bTy, x ≥ 0, y ≥ 0If the combined LP has a feasible solution (x,y), then by weak duality, cTx = bTy.

The proof proceeds in two steps:[4]: 260–261 Consider the primal LP, with two variables and one constraint: Applying the recipe above gives the following dual LP, with one variable and two constraints: It is easy to see that the maximum of the primal LP is attained when x1 is minimized to its lower bound (0) and x2 is maximized to its upper bound under the constraint (7/6).

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

Consider a farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P pesticide.

In matrix form this becomes: 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), S1 for wheat and S2 for barley.

This corresponds to the following LP: In matrix form this becomes: The primal problem deals with physical quantities.

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?

In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.

Here is an example: There is a close connection between linear programming problems, eigenequations, and von Neumann's general equilibrium model.

The solution to a linear programming problem can be regarded as a generalized eigenvector.

The above eigenequations for the square matrix can be extended to von Neumann's general equilibrium model:[5] [6]

Let us illustrate the structural equilibrium model with the previously discussed tiny example.

We substitute the above calculation results into the structural equilibrium model, obtaining

We get: Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal.

As a result, we get: Note that we assume in our calculations steps that the program is in standard form.

However, any linear program may be transformed to standard form and it is therefore not a limiting factor.