Fig. 9.1 Refinery flow.
9
Formulating and Solving Linear Programs
GEORGE B. DANTZIG
RESEARCH MATHEMATICIAN
THE RAND CORPORATION
9.1 Introduction
One of the reasons why the programming tool has assumed importance, both in industry and in the military establishment, is that it is a method for studying the behavior of systems.† In philosophy, it is close to what some describe as the distinguishing feature of management science or operations research,5 to wit: “Operations are considered as an entity. The subject matter studied is not the equipment used, nor the morale of the participants, nor the physical properties of the output, it is the combination of these in total as an economic process.”4
To many, the term “linear programming” refers to mathematical methods for solving linear inequality systems. While the solution of such systems may be the central mathematical problem, it is not the definition of linear programming. Linear programming is a technique for building a model describing the interrelations of the components of a system. As such, it is probably the simplest mathematical model that can be constructed that is of any value for broad programming problems of industry and government. Thus the importance of the linear-programming model is that it has wide applicability.
9.2 Formulating a Linear-programming Model
Suppose that the system under study, which may be one actually in existence or one that we wish to design, is a complex of machines, people, facilities, and supplies. There are certain over-all reasons for its existence. For the military, the purpose may be to provide a striking force; for industry, it may be to make certain types of products.
The linear-programming approach is first to consider the entire system as decomposable into a number of elementary functions called activities; each type of activity is abstracted to be a kind of “black box” into which flow tangible things called items, such as supply and money, and out of which may flow other items such as the products of manufacture or trained crews for the military. What goes on inside the “box” is the concern of the engineer or the educator; but to the programmer, only the rates of flow in and out are of interest.
The next step in building a model is to select some unit for measuring the quantity of each activity. For a production-type activity, it is natural to measure the quantity of the activity by the amount of some product produced by it. This quantity is called the activity level. To increase the activity level, it will be necessary, of course, to increase the flows into and out of the activity.
In the linear-programming model, the quantities of flow of various items into and out of the activity are always proportional to the activity level.
While any positive multiple of an activity is possible, negative quantities of activities are not possible.
On the basis of these two assumptions, we see that it is sufficient to know the flows for the unit activity level. If we wish to double the activity level, we simply double all the corresponding flows for the unit activity level.
One of the items in our system is regarded as precious, in the sense that the total quantity of it that is produced by the system measures the costs. The contribution of each activity to the total cost is the amount of the precious item that flows into or out of each activity. Thus if the objective is to minimize total cost, activities that require money contribute positively and those that produce money contribute negatively to the total cost.
Finally, it is required that the system of activities be complete, in the sense that a complete accounting of each item can be made by the system of activities. To be precise, for each item it is required that the total amount on hand is equal to the amount flowing into the various activities minus the amount flowing out. Thus, in our abstract system, each item is characterized by a material balance equation, the various terms of which represent the flows into or out of the various activities.
To review, the basic assumptions underlying the linear-programming model are:
a. Input-output flows are proportional to the activity level.
b. Activity levels are nonnegative.
d. The net flow of one selected item, the linear objective function, is to be minimized.
9.3 Building the Model
We consider now the following steps in model building.
a. Decompose the entire system under study into its elementary functions, the activities, and choose a unit for each activity in terms of which its quantity, or level, can be measured.
b. Determine the classes of objects, the items, that are consumed or produced by the activities and choose a unit for measuring each item. Select one item such that the net quantity of it that is required by the system as a whole measures the cost (or such that its negative measures the profit) of the entire system.
c. Determine the quantity of each item consumed or produced by the operation of each activity at its unit level. These numbers, the input-output coefficients, are the factors of proportionality between activity levels and item flows.
d. Determine the exogenous flows—the net inputs or outputs of the items between the system, taken as a whole, and the outside.
e. Assign unknown nonnegative activity levels x1, x2, … to all the activities; then, for each item, write the material balance equation, which asserts that the algebraic sum of the flows of that item into each activity, given as the product of the activity level by the appropriate input-output coefficient, is equal to the exogenous flow of the item.
The result of the model building is thus the collection of mathematical relationships characterizing all the feasible programs of the system. This collection is the linear-programming model.
Once the model has been built, the programming problem has been formulated in mathematical terms. The solution of the mathematical problem is then the ultimate aim of the particular application of linear programming:
The Linear-programming Problem
For all the activities of the system, determine levels that
a. Are nonnegative
b. Satisfy the material balance equations
c. Collectively minimize the total cost
9.4 The Linear-programming Model Illustrated
To illustrate the foregoing principles of the linear-programming approach to model building, let us turn to an application in the petroleum industry, where linear-programming methods have been very successful.
The complicated piece of plumbing of Fig. 9.1 is a simplified flow diagram of an oil refinery.† The problem facing management is this: By turning valves, setting temperatures and pressures, and starting pumps, crude oil is drawn from one or several oil fields under the control of the refinery, as shown on the left in the figure. As in the song about the music, the crude oil “goes ’round and ’round” and comes out as several streams of pure oils, shown on the right. The latter can be marketed at varying prices. By changes in the controls, the quantities in the various streams of pure oils can be altered. This will change both the costs of operating the equipment and the revenues from the sales of the final products. The various components are interrelated, however, in such a complicated manner that it is not obvious what is the best way to operate the equipment to maximize profits. In spite of these complex interrelationships, when this system is decomposed into elementary functions as the first step in building a model, it turns out that there are essentially only three main kinds of activities taking place: distilling, cracking, and blending.
Fig. 9.1 Refinery flow.
a. Distilling. The net effect of the flash tower, heater, fractionating towers, strippers, etc., is to separate the crude into the varying amounts of pure oils of which it is composed. Crudes drawn from different oil fields will have different decompositions. Hence, there must be a separate distillation activity developed for each type of crude. The maximum amount of crude that can be distilled depends on which one of the pieces of equipment it passes through is the bottleneck. In our case, let us suppose that it is the heater and that it has a fixed capacity of 14,000 bbl/day independent of the type of crude processed.
Fig. 9.2 Activities of (a) distilling, (b) cracking, and (c) blending.
From this description it is evident that, if the level of distillation activity is measured in number of barrels of crude input, then a unit level of activity can be pictured as in Fig. 9.2a. It is seen that 1 bbl of crude 1 will use 1 bbl of distillation capacity and will cost $1.80 to purchase and to distill; the outputs will be streams of pure oils in the amounts shown. These outputs are principally the heavier oils—fuel, diesel, and stove—and smaller amounts of the lighter types used in making gasoline. If instead of 1 bbl, it is desired to distill 10 or x bbl of crude, all input and output quantities of Fig. 9.2a would have to be multiplied by 10 or x.
b. Cracking. The net effect of the cracking equipment is to take one of the heavier types of oil and to cause it to be broken down into lighter types of oil. In the case of fuel oil, it will produce a small amount of the lighter types and a larger amount of stove oil; the latter, if desired, can in turn be recycled back into the cracker and made into lighter oils. It is seen from Fig. 9.2b that 1 unit of fuel oil requires 1 unit of cracking capacity, will cost $0.16, and will produce pure oils in the amounts shown on the right. A separate type of activity must be set up for cracking of fuel, diesel, and stove oils.
c. Blending. Gasoline is not a pure oil but is a blend of several of the lighter types of pure oil; see Fig. 9.2c. It will be noted that the only output shown is the net revenue from marketing 1 bbl of gasoline. The latter is assumed to be the sales price at the refinery less the cost of the blending operation.
Once the flows for these major activities have been determined on a per-barrel basis, it is a simple matter to set up the linear-programming model by means of which the managers can determine the best manner of operating the refinery in order to maximize profits. In Table 9.1, each row represents an activity. The input and output quantities per unit level of activity are shown in the row; to distinguish outputs from inputs, outputs are shown with a minus sign. For example, in Table 9.1 the data of Fig. 9.2a are shown in the row captioned “Distilling—Crude 1”; the data of Fig. 9.2b are denoted “Cracking—Fuel Oil”; the data of Fig. 9.2c are labeled “Marketing—Gasoline.” The other activity rows are self-explanatory. The amounts of various items available to the system are shown at the bottom of the table.
The unknown activity levels to be determined are denoted by x1, x2, …, x20. When these unknowns are multiplied by the corresponding numbers found in any column and the terms are summed, the total obtained should be equal to the availability shown at the bottom.
For example, the first material-balance equation reads
1x1 + 1x4 = 9,500
which means the amount of crude 1 available, 9,500 bbl, is completely accounted for by the amount left in the ground, x1, plus the amount distilled, x4.
The fourth material-balance equation, referring to distillation capacity, reads simply
1x4 + 1x5 + 1x6 + 1x7 = 14,000
which means that the distillation capacity of 14,000 bbl is completely accounted for by the amount used in distilling the various types of crude plus any excess capacity not used.
Finally, the profit equation states that the revenue obtained from marketing various products,
less the cost of distilling and crude purchases,
1.8x4 + 1.9x5 + 2.0x6
less the cost of cracking,
0.16x8 + 0.21x9 + 0.21x10
is the amount of profit. The problem, of course, is to choose the program of activity levels in such a way that the material balance equations are satisfied and the profits are maximized.
9.5 Algebraic Statement of the Linear-programming Problem
The minimization of a linear form subject to linear inequality constraints has been called the central mathematical problem of linear programming.† The standard form for such problems, because it arises naturally in many applications, is taken to be the following: Find a solution of a system of linear equations, in nonnegative variables, that minimizes a linear form. We shall see in a moment why this particular form is chosen as standard. At the same time, we shall formalize in mathematical terms our remarks regarding linear-programming models.
If the subscript k denotes the kth type of activity, k = 1, 2, …, n, and xk its quantity, or activity level, then usually xk ≥ 0. If, for example, xk represents the quantity of a stockpile allocated for the kth use, it does not, as a rule, make sense to allocate a negative quantity. In certain cases, however, one may wish to interpret a negative quantity as meaning taking stock from the kth use. Here some care must be exercised; for example, there may be costs, such as transportation charges, that are positive regardless of the direction of flow of the stock. One must also be careful not to overdraw the stock of the activity. For these reasons, it is better in formulating models to distinguish two activities, each with a nonnegative range, for their respective xk, rather than to try incorporating them into a single range.
The interdependencies between various activities arise because all practical programming problems are circumscribed by commodity limitations of one kind or another. The limiting commodities may be raw materials, manpower, facilities, or funds; these are referred to by the general term item. In chemical equilibrium problems, where molecules of different types play the role of activities, the different kinds of atoms in the mixture are the items. The different types of items are denoted by a subscript i, where i = 1, 2, …, m.
In linear-programming work, the quantity of an item required as input or produced as output by an activity is assumed to be proportional to the quantity of activity level; the coefficient of proportionality is denoted by aik. The sign of aik depends on whether the item is required or produced by the activity. The sign convention used will be + if required and − if produced, as shown in the diagram. Finally, let bi, if positive, denote the quantity of the ith item made available as input to the system of activities from outside (or exogenous) sources, and let bi, if negative, denote the quantity required as output by the system. Then the interdependencies between the xk can be expressed as a set of m linear equations; the ith such equation gives a complete accounting of the ith item. Thus,
where
Any set of values xk satisfying Eqs. (9.1) and (9.2) is called a feasible solution because the corresponding schedule is possible or feasible.
The objective of a program, in practice, often is most difficult to express in mathematical terms. There are many historical reasons for this; they go beyond the scope of the present discussion. In many problems, however, the objective is simply one of carrying out the requirements, expressed by those bi that are negative, in such a manner that total costs are minimized. Costs may be measured in dollars, or in number of people involved, or in the quantity of a scarce commodity used. In linear programming, the total cost, denoted by z, is assumed to be a linear function of the activity levels:
The linear form z is called the objective function.
In some problems, the linear objective form, as originally presented, is to be maximized rather than minimized. For example, the problem may be to produce the maximum dollar value of products under a fixed budget, fixed machine capacity, and fixed labor supply. Suppose the linear form expressing total profits to be maximized is
Maximizing this form obviously is mathematically equivalent to minimizing
For these reasons, the standard form of the linear-programming problem is taken to be the problem of determining a solution of a given system of linear equations in nonnegative variables in such a way as to minimize a given linear function of those variables.
9.6 Outline of the Simplex Method
The standard procedure for solving the central mathematical problem of linear programming is the simplex method. It makes use of two important characteristics of solutions:
a. If a feasible solution exists, so that Eqs. (9.1) and (9.2) are satisfied, then one exists with at least n − m variables equal to zero.
b. If feasible solutions exist and the objective form z has a finite lower bound, then a minimal feasible solution exists with at least n − m variables equal to zero.
Suppose that there is at hand a feasible solution with the property that n − m variables are equal to zero, say 
. We wish to test whether or not the solution is optimal. The procedure is first to eliminate each of the remaining variables, x1, x2, …, xm, from all but one of the equations. This will be possible if the determinant of the coefficients of the selected set of m variables does not vanish; in this case, the selected set is referred to as a basic set of variables. We shall refer to this process as reduction to canonical form. If x1, x2, …, xm are the variables selected for elimination, then the canonical form for the simplex method relative to these basic nonnegative variables is as follows:
where 
, and 
are constants.
It is important to note that this system is equivalent to the original system of Eqs. (9.1) and may be used in its place for any further discussions. In this form, it is easy to obtain a particular solution to the equations and to test whether or not it is feasible and optimal.
9.7 Test for Optimal Feasible Solution
THEOREM 9.1. If, in the canonical form, the values of the constant terms 
and the coefficients 
in the cost equation are nonnegative, then the basic solution obtained by setting nonbasic variables to zero and solving for values of basic variables, namely,
is optimal.
Proof. Since xk must be nonnegative and 
whatever the feasible solution, it follows from the last equation of the canonical form that the values of z for the class of feasible solutions must always exceed by the sum of the nonnegative terms on the left. Hence any particular feasible solution with 
, such as (9.3), would be a minimizing solution.
For example, consider the problem of finding min z and nonnegative x1, x2, x3, x4 satisfying
Suppose we would like to check if the particular solution obtained by setting x3 = x4 = 0 and solving for x1, x2, z is feasible and optimal. If we pivot on x1 in the first equation by dividing through by its coefficient, if necessary, so that this coefficient becomes unity, and then eliminating x1 from the other equations, we obtain
If next we pivot on the x2 term in the second equation, eliminating x2 from all the other equations including the first, we obtain the equivalent canonical form with respect to x1 and x2:
Note that Eqs. (9.4) fulfill the conditions of Theorem 9.1; hence, an optimal solution is obtained by setting the nonbasic variables x3 and x4 equal to 0 and solving for x1, x2, z:
x1 = 7 x2 = 3 x3 = x4 = 0 z = 13
This solution is also the unique optimal solution, as will become clear by applying the following result:
THEOREM 9.2. If in the canonical system the basic solution is feasible and the coefficients in the cost form are all positive for nonbasic variables, then the solution is the unique feasible optimal solution.
COROLLARY. If in the canonical system the basic solution is feasible and the coefficients satisfy ck ≥ 0 for all k, then no other feasible solution can also be optimal unless the values xk satisfy xk = 0 whenever 
.
Proof. Consider another feasible solution and suppose that the value of some xk is positive for a positive . Then the value of z must be greater than , since the term 
in the last equation of the canonical form satisfies 
. Hence, any feasible solution that is also minimal must have xk = 0 for all variables with corresponding , establishing the corollary.
Under the hypothesis of Theorem 9.2 that all corresponding to nonbasic xk satisfy , all nonbasic xk must satisfy xk = 0, but upon substitution this leaves only the values 
for basic variables, and accordingly z = z0.
9.8 Improving a Nonoptimal Basic Feasible Solution
The standard simplex method is applicable only to basic solutions that are feasible; i.e., the satisfy 
. To understand the underlying principle, let us suppose that one or more coefficients are negative in the canonical form for nonbasic variables. In this case, the test for optimality fails.
If all satisfy 
(note that zero is excluded), we can immediately improve the basic feasible solution by increasing the value of one of the corresponding nonbasic variables xk for which 
, keeping the other nonbasic variables at value zero. As a good empirical rule, we might choose to increase that variable xs for which
For example, suppose the canonical form is
which is the same as our earlier example except that the sign of the coefficient 
has been reversed. The basic solution formed by setting non-basic variables x3 and x4 equal to 0 and solving for x1, x2, and z yields x1 = 7, x2 = 3, z = 13, which is feasible.
Since 
, we now choose to increase x4, maintaining all other nonbasic variables (in this case x3) at zero value. The values of the basic variables and z will now depend on the value chosen for x4. For example, the value of z is given by
z = 13 − 4x4
so that the larger we take the value x4, the lower will be the value z. On the other hand, the values of the basic variables become
so that the largest value that x4 can take, without destroying the feasibility of the solution, is x4 = 3. Above this value, x2 would be negative. By setting x4 = 3, we see that the value of z is lowered by 4x4, or 12 units, and the new solution becomes
x1 = 13x4 = 3x2 = 0x3 = 0z = 1
Notice that, at the critical value x4 = 3, x2 has vanished. Accordingly, in the next iteration we interchange the roles of x2 and x4 as basic and nonbasic variables by pivoting on the circled term x4 in Eqs. (9.6) to eliminate x4 from the other equations. The pivot term is always in the column of the variable to be introduced into the basic set and the row of the basic variable to be dropped (in this case x2). This yields
Notice that this is now in canonical form relative to x1 and x4, except that we have not bothered to rearrange terms.
The new basic solution is obtained by setting the new nonbasic variables x2 and x3 equal to 0 and solving for the remaining variables: x1 = 13, x4 = 3, z = −23. Upon applying our test for optimality, we see that the solution is optimal because all and satisfy and . Moreover, it is unique, since all satisfy (not zero) for nonbasic variables.
9.9 General Iterative Procedure
As we have seen in the numerical example, the canonical form provides in general an immediate criterion for testing optimality of a basic feasible solution. Furthermore, if the solution is not optimal, and if all satisfy , then it leads to another solution that reduces the value of the cost or objective function.
The new basic feasible solution can again be tested for optimality by seeing if all satisfy (Theorem 9.1). If it is not optimal, then by criterion (9.5) one may choose a new variable xs to increase and proceed to construct either (1) a class of solutions in which there is no finite lower bound for z (if all 
satisfy 
) or (2) a new basic feasible solution in which the cost z is lower than the previous one (provided that the values of the basic variables for the latter are strictly positive; otherwise the new value of z may be equal to the previous value).
The simplex algorithm consists in repeating this cycle again and again, terminating only when there has been constructed one of the following:
a. A class of feasible solutions in which z → − ∞
b. An optimal basic feasible solution
If all satisfy at each cycle, the entire process will terminate in a finite number of cycles. The reason for this is that there are only a finite number of ways of choosing a set of m basic variables out of n variables. If the algorithm were to continue indefinitely, it could do so only by repeating the same basic set of variables—hence the same cost z. The latter is prevented from happening because on each cycle the value of z decreases a positive amount.
9.10 Finding an Initial Basic Feasible Solution
Up to the present, we have been assuming that it is possible to specify a basic set of variables that could be used to perform the necessary initial eliminations and reduce the problem to canonical form. It has also been assumed that the associated basic solution is feasible.
We shall now give a simple device that uses the simplex algorithm itself to provide (if it exists) a starting basic feasible solution. This part of the process is referred to as Phase I. The second part of the process, obtaining an optimal basic feasible solution, is then referred to as Phase II. The device has several important features that should be noted:
a. No assumptions are made regarding the original system; it may be redundant, inconsistent, or not solvable in nonnegative numbers.
b. No eliminations are required in order to obtain an initial solution in canonical form for Phase I.
c. The end product of Phase I is a basic feasible solution, if it exists, in canonical form ready to initiate Phase II. The procedure for Phase I is this:
a. Arrange the original system of equations so that all constant terms bi are positive or zero by changing, where necessary, the signs on both sides of any of the equations.
b. Augment the system to include a basic set of “artificial” variables xn+1 ≥ 0, xn+2 ≥ 0, …, xn+m ≥ 0 so that it becomes
where all bi satisfy bi ≥ 0 and for k = 1, …, n, n + 1, …, n + m, all xk satisfy
c. By using the simplex algorithm, find a solution to Eqs. (9.7) and (9.8) that minimizes the sum of the artificial variables, denoted by w:
We call this the infeasibility form. Its coefficients, after elimination of basic variables, are referred to as 
; these are the analogue of for the cost form.
d. If min w > 0, then no feasible solution exists and the procedure is terminated. On the other hand, if min w = 0, initiate Phase II of the simplex algorithm as follows:
i. Drop from further consideration all nonbasic variables xk for which the corresponding coefficients dk are positive (not zero) in the final modified w equation.
ii. Replace the linear form w, as modified through various eliminations, by the linear form z, after first eliminating from z all basic variables.
In practical computational work, the elimination of the basic variables from the z form is usually done on each cycle of Phase I.
REFERENCES
1. Dantzig, George B., “Thoughts on Linear Programming and Automation,” Paper P-824, The RAND Corporation, Santa Monica, Calif., 1956.
2. ——, “The Central Mathematical Problem,” Paper P-892, The RAND Corporation, Santa Monica, Calif., 1956.
3. ——, “Formulating a Linear Programming Model,” Paper P-893, The RAND Corporation, Santa Monica, Calif., 1956.
4. Hermann, C. C., and J. F. Magee, Operations Research for Management, Harvard Bus. Rev., July, 1953.
5. King, Gilbert W., Applied Mathematics in Operations Research, chap. 10 in “Modern Mathematics for the Engineer,” First Series, edited by E. F. Beckenbach, McGraw-Hill Book Company, Inc., New York, 1956.
† Material of the first four sections of this chapter is drawn from Refs. 1 and 3.
† This refinery example was taken from a term paper of R. J. Ullman.
† Material in this section is taken from Ref. 2.
