Keywords

JEL Classifications

A list of applications of linear programming, since it was first proposed in 1947 by G. Dantzig, could fill a small volume. Both J. von Neumann and L. Kantorovich made important contributions prior to 1947. Its first use by G. Dantzig and M. Wood was for logistical planning and deployment of military forces. A. Charnes and W. Cooper in the early 1950s pioneered its use in the petroleum industry. S. Vajda and E.M.L. Beale were early pioneers in the field in Great Britain. In socialist countries, it is used to determine the plan for optimal growth of the economy. Thousands of linear programs are efficiently solved each day all over the world using the simplex method, an algorithm, also first proposed in 1947. Many problems which once could only be solved on high-speed mainframe computers can now be solved on personal computers.

The problem of minimizing or maximizing a function f0 of several variables X = (X1, X2, … , Xn) subject to constraints fi(X) ≤ 0, i = 1 , … , n is called a mathematical program. When all the functions f are linear, it is called a linear program; otherwise a non-linear program. If all f are convex functions, it is called a convex program. At first glance, linear inequality systems appear to be a very restricted class. However, as pointed out by T. C. Koopmans as early as 1948, linear programs can be used to approximate the broad class of convex functions commonly encountered in economic planning.

Linear programs may be viewed as a generalization of the Leontief Input–Output Model, one important difference being that alternative production processes (activities) are allowed to compete; another being the representation of capacity as an input that becomes available at a later point in time as an output (possibly depreciated). Solving a model with alternative activities requires not only software for efficiently solving on computers large systems of equations as in the Leontief case, but also software for selecting the best combination from an astronomical number of possible combinations of activities. (See the entry simplex method for solving linear programs.)

Formulating a Linear Program

Finding an optimal product mix (for example blend of gasoline, or metals, or mix of nuts, or animal feeds) is a typical application. For example, a manufacturer wishes to purchase at minimum total cost a number of solder alloys A, B, C, D which are available in the market-place in order to melt them down to make a blend of 30% lead, 30% zinc, and 40% tin. Their respective costs per pound are shown in Table 1.

Table 1 Linear Programming, Table 1
Full size table

Suppose 100 pounds of blend is desired and XA, XB, XC, XD are the unknown number of pounds of A, B, C, D to be purchased. The problem to be solved is clearly: find Z and (XA, XB, XC, XD) ≥ 0, such that:

$$ {\displaystyle \begin{array}{c}\hfill 0.1{X}_A+0.1{X}_B+0.4{X}_C+0.6{X}_D=30\hfill \\ {}\hfill 0.1{X}_A+0.3{X}_B+0.5{X}_C+0.3{X}_D=30\hfill \\ {}\hfill 0.8{X}_A+0.6{X}_B+0.1{X}_C+0.1{X}_D=40\hfill \\ {}\hfill \overline{4.1{X}_A+4.3{X}_B+5.8{X}_C+6.0{X}_D=Z\left(\min \right)}\hfill \end{array}} $$

This example can be solved in a few seconds on a personal computer.

The standard form of a linear program is: find min z, x = (x1,. ..,xn) ≥ 0:

$$ Ax=b,\, cx=z\left(\min \right) $$

where A is a m by n matrix, b a column vector of m components and c a row vector of n components. The matrix A of coefficients is referred to as the technology matrix.

One way to formulate a linear program is to begin by (a) listing various constraints such as resources availability, demand for various goods by consumers, known bounds on productive capacity; (b) listing variables to be determined representing the levels of activities whose net inputs and outputs must satisfy the constraints, and finally (c) tabulating the coefficients of the various inequalities and equations.

Since linear programming models can be very large systems with thousands of inequalities and variables, it is necessary to use a special software, called matrix generators, to facilitate the model building process. Such systems have millions of coefficients, fortunately most of them are zero. Matrices with very few nonzero elements are called sparse. The World Bank uses software called GAMS to generate moderate-size sparse matrices A by rows. Another type of software called OMNI has been developed by Haverly Systems and has been used to generate very large sparse matrices by columns. When a model is formulated by columns, it is called Activity Analysis: the column of coefficients of a variable is the same as a recipe in a cook book – these are the input and output flows required to carry out one unit of an activity (or process). The variables, usually non-negative, are the unknown levels of activity to be determined. For example the activity of ‘putting one unit (pound) of solder alloy A in the blend’ has an input of $4.10 and outputs to the blend of 0.10 lb of lead, 0.10 lb of zinc, 0.80 lb of tin.

In economic applications, output coefficients are typically stated with + signs and input coefficients with – signs. Under this convention, the signs of the coefficients of the Z equation in the blending example should be reversed and, net revenues, (−Z) maximized. In practice, instead of equations in non-negative variables, there can be a mix of equations and inequalities. Simple algebraic steps allow one to pass from one form of the system to another.

Primal and Dual Statements of the Linear Program

John von Neumann in 1947 was the first to point out that associated with a linear program is another called its Dual, formed by transposing the matrix A and interchanging the role of the RHS b and the ‘cost’ vector c. The original problem is called the Primal. Von Neumann expressed both of these LP in inequality form:

Primal: \( \min \, \overline{z}= cX: AX\ge b,X\ge 0,\, (P) \) Dual: min z = Y′b : Y′A ≤ c,  Y ≥ 0, (D).where Y′ is the transpose of column vector Y.

If we denote the jth column of A by A (*, j), the n inequalities Y′A ≤ c may be rewritten as Y′A(∗, j) ≤ cj for j = 1,…, n.

(P) expresses the physical constraints of the system under study. The variables Y of the dual (D) can be interpreted as prices. Mathematicians call them Lagrange multipliers. The dual conditions, Y′A(∗, j) − cj ≤ 0 for j =1,..., n, may appear strange and just the opposite from what one would expect. They state that levels Xj of all activities j that show profit in the economy will rise to the point that all ‘price out’ nonprofitable. It turns out that when the value z = Y′b in (D) is maximized, all activities j that are operated at positive levels will just break even, i.e., just ‘clear their books’ and that all activities j operating at a strict loss will be operating at zero levels.

The famous duality theorem of von Neumann states that, when there exist ‘feasible’ solutions AX ≥ b, X ≥ 0 to (P) and Y′A ≤ c, Y ≥0 to (D),

$$ \operatorname{Max}\, \overline{z}=\operatorname{Min}\, \overline{z} $$

It is easy to prove that any feasible solutions to (P) and (D) not necessarily optimum satisfy.

$$ \overline{z}={Y}^{\prime }b\le cX=\overline{z}, $$

so that if it happens that Y*b = cX*, for some feasible X = X*, Y = Y* then by the duality theorem we know that such a pair (X*, Y*) are optimal solutions to (P) and (D).

This makes it possible to combine the primal and dual problems into the single problem of finding a feasible solution to the following: find \( \left(X,\overline{X},Y,\overline{Y},\theta \right)\ge 0: \)

$$ \left[\begin{array}{ccc}\hfill 0\hfill & \hfill A\hfill & \hfill -b\hfill \\ {}\hfill -{A}^{\prime}\hfill & \hfill 0\hfill & \hfill {c}^{\prime}\hfill \\ {}\hfill {b}^{\prime}\hfill & \hfill -c\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill Y\hfill \\ {}\hfill X\hfill \\ {}\hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill \overline{Y}\hfill \\ {}\hfill \overline{X}\hfill \\ {}\hfill \theta \hfill \end{array}\right]\quad \left(\mathrm{P},\, \mathrm{D}\right) $$

where we have introduced two slack vectors \( \overline{Y}\ge 0 \) and \( \overline{X}\ge 0 \) which turn the inequality relations (P) and (D) into equality relations \( AX{-} \overline{Y}=b \) and \( {Y}^{\prime }A+{\overline{X}}^{\prime }=c \). The last relation is the single equation Y′b – cX = θ where θ ≥ 0 is a scalar.

It we multiply (P, D) by the vector (Y′, X′, 1) on the left and perform all the matrix multiplications, everything on the left side cancels out because of the skew symmetry of the matrix and we are left with

$$ 0=\left[{Y}^{\hbox{'}}{X}^{\hbox{'}}1\right]{\left[\overline{YX}\theta \right]}^{\prime }=\sum\limits_i{Y}_i\overline{Y}+\sum\limits_j{X}_j{\overline{X}}_j+\theta . $$

Because all terms are non-negative, it follows that

$$ {X}_j{\overline{X}}_j=0,\quad {Y}_i{\overline{Y}}_i=0,\quad \theta =0\quad \mathrm{for}\ \mathrm{all}\, i\, \mathrm{and}\, j. $$

These are called complementary slackness or Kuhn–Tucker conditions for optimality.

Zero-Sum Matrix Games

These games can be formulated as a special class of linear programs. The ‘row’ player chooses row i of a matrix while his opponent, the ‘column’ player, simultaneously chooses column j. Column player wins an amount aij if aij ≥ 0 otherwise he pays the other player −aij. The payoff matrix is A = [aij]. It is called a zero-sum game because the sum of the payments each player receives adds up to zero. Von Neumann analysed this game in 1928 and introduced the notion of a mixed strategy (Y1,Y2, … ,Ym), (X1, X2, … ,Xn) which are the probabilities of the players choosing any particular row and column. He showed that there exist optimal mixed strategies, Y = Y* for the row player and X = X* for the column player, such that if a player’s mixed strategy is discovered by his opponent, it will have no effect on his expected payoff and hence no effect on the expected payoff of his opponent which is the negative of his.

The column player, if he plays conservatively and assumes his mixed strategy will become known to his opponent, will choose his probabilities Xj ≥ 0 so as to maximize L where Max L and X ≥ 0 are chosen so that

$$ \sum\limits_j{a}_{ij}{X}_j\ge L,\quad {X}_j\ge 0,\quad i=1,\dots, m\sum\limits_j{X}_j=1.\quad \left(\mathrm{C}\right) $$

Likewise the row player’s-optimal mixed strategy, if he plays conservatively, will choose his probabilities Yi ≥ 0 so as to minimize K where Min K and Y ≥ 0 are chosen so that

$$ \sum\limits_i{Y}_i{a}_{ij}\le K,\quad {Y}_i\ge 0,\quad j=1,..\dots, n\sum\limits_i{Y}_i=1.\quad \left(\mathrm{R}\right) $$

It is not difficult to prove that (C) and (R) are feasible linear programs and each is the dual of the other. Let \( \left({Y}_1^{\ast },\dots, {Y}_m^{\ast}\right) \)and \( \left({X}_1^{\ast },\dots, {X}_m^{\ast}\right) \)be optimal solutions to (R) and (C). Applying the duality theorem, we obtain von Neumann’s famous mini-max theorem for zero-sum bimatrix games:

$$ \max \, L=\min \, K=\sum\limits_i\sum\limits_j{Y}_i^{\ast }{a}_{ij}{X}_j^{\ast }, $$

the expected payoff to the column player.

Decomposition Principle

Linear programming can be used in an iterative mode to aid a Central Authority to allocate scarce resources to factories in an optimal way without having to have detailed knowledge about each factory. Specifically the Central Authority proposes prices on the scarce commodities that induce the factories to submit a summary plan for approval of their requirement for scarce resources. The Central Authority blends these proposed plans with earlier ones submitted and uses them to generate new proposed prices. The entire cycle is then iterated. This method, first proposed by Dantzig and Wolfe in 1960, is known as the D–W or Primal Decomposition Principle.

The dual form of the Decomposition Principle is known as Benders Decomposition and was proposed by Benders in 1962. We illustrate it here in the context of a two-period planning problem.

$$ {\displaystyle \begin{array}{c}\hfill \mathrm{find}\, \min \, Z={c}_1{X}_1+{c}_2{X}_2\quad \mathrm{subject}\, \mathrm{to}:\hfill \\ {}\hfill {b}_1={A}_1{X}_1\quad \left({X}_1,{X}_2\right)\ge 0,\hfill \\ {}\hfill {b}_2=-{B}_1{X}_1+{A}_2{X}_2\hfill \end{array}} $$

where A1, B1, A2 are matrices, b1, b2, c1, c2 vectors and Xt≥ 0 are the vectors of activity levels to be determined in periods t = 1 and 2.

The first period planners determine a feasible plan (p) that satisfies \( b={AX}_l^p,{X}_l^p\ge 0 \)(augmented by certain necessary conditions, called ‘cuts’), which they submit to the second period planners in the form of a vector \( {B}_1{X}_l^p \) which is used by them to solve the second period sub problem:

$$ {A}_2{X}_2={b}_2+{B}_1{X}_1^P,{X}_2\ge 0{c}_2{X}_2={Z}_2\left(\min \right). $$

The second period planners respond with a vector of optimality prices\( {\pi}_2^k \)corresponding to the second period if the sub-problem is feasible, or with infeasibility prices\( {\sigma}_2^l \)(obtained at the end of phase 1 of the simplex method) if it is infeasible.

The first period planners then iteratively resolve, their problem augmented by k′ + l′ additional necessary conditions (cuts) shown below:

$$ \mathrm{Find}\, {c}_1{X}_1+\theta =Z\left(\min \right)\ {A}_1{X}_1={b}_1,\quad X\ge 0,\mathrm{optimality}\, \mathrm{cuts}:-\left({\pi}_2^k{B}_1\right){X}_1+\theta \ge {\pi}_2^k{b}_2,k=1,\dots, {k}^{\prime}\mathrm{infeasibility}\, \mathrm{cuts}:-\left({\sigma}_2^l{B}_1\right){X}_1\ge {\sigma}_2^lb\, l=1,\dots, {l}^{\prime } $$

where θ = (c2X2) is treated as an unknown variable. The interative process stops if θ = Z2, or Z2 – θ = Δ > 0 is small enough.

Note that the additional conditions imposed on Period 1 are expressed in terms of Period-1 variables and θ only. These serve as surrogates for future periods (in this example for only one future period). The decomposition principle allows one to solve a multi-time-period problem one period at time and pass the ending conditions of one period on to initiate the next and to pass back price vectors to earlier periods that are translated into policy constraints called cuts. Applying this same approach to a multi-stage production line, one obtains an iterative process that can be viewed as an intelligent control system with learning.

See Also