Chapter 4

LINEAR PROGRAMMING

Sensitivity Analysis top

Having obtained the optimal solution for a linear programming problem, it would be desirable to know how much the cost coefficients could change, for example, before it is necessary to resolve the problem. In fact there are five areas that should be examined for their effect on the optimal solution. These are:

  1. changes in the right-hand side of the constraint equations, bi
  2. changes in the coefficients of the objective function, cj
  3. changes in the coefficients of the constraint equations, aij
  4. addition of new variables
  5. addition of more constraint equations

Changes in the right-hand side of the constraint equations correspond to changes in the maximum capacity of a process unit or the availability of a raw material, for example. Changes in the coefficients of the objective function correspond to changes of the cost or the sale price of the products, and changes in the coefficients of the constraint equations correspond to changes in volumetric yields of a process. Addition of new variables and constraint equations correspond to the addition of new process units in the plant. It is valuable to know how these various coefficients and parameters can vary without changing the optimal solution, and this may reduce the number of times the linear programming problem must be solved.

     Prior to doing this post-optimal analysis, some preliminary mathematical expressions must be developed for the analysis of the effect of the above five areas on the optimal solution. These are the inverse of the optimal basis and the Lagrange Multipliers. To obtain the matrix called the inverse of the optimal basis, A-1, consider that the optimal basis has been found by the previously described Simplex Method. There are m constraint equations and n variables as given by equations 4-1a, b, and c. For convenience, the nonzero variables in the optimal basis have been rearranged to go from 1 to m, (x1*, x2*,...,xm*, 0, 0,..., 0); and there are (n - m) variables not in the basis whose value is zero. The optimal solution to this linear programming problem is indicated below where x* contains only the m nonzero basis variables.

Equ4-16.jpg (3591 bytes)

and

A* x* = b                                                           (4-17)

To solve for x*, both sides of the above equation are multiplied by the inverse of the optimal basis, A*-1 whose elements are bij and obtain:

x* = A-1b                                                           (4-18)

It should be noted that A-1 may be obtained from the last step of the Simplex Method if all of the constraint equations required slack variables. If not, then it has to be obtained from the original formulation of the problem using the optimal basis found from the Simplex Method.

     The linear programming problem could be solved by the classical method of Lagrange Multipliers. However, the Simplex Method gives a systematic procedure for locating the optimal basis. Having located the optimal basis by the Simplex Method, the Lagrange Multiplier formulation and the inverse of the optimal basis will be used to determine the effect of change in the right-hand side on the optimal solution. Consequently, it is necessary to compute the values of the Lagrange Multipliers as follows. Multiplying each constraint equation, (4-1b), by the Lagrange multiplier li and adding to the objective function equation (4-1a), gives the following equation:

Equ4-19.jpg (16888 bytes)

where x1 to xm are positive numbers, i.e., values of the variables in the basis, and xm+1 to xn are zero, i.e., values of the variables that are not in the basis.

To solve this problem by classical methods, the partial derivatives of p with respect to the independent variables and the Lagrange Multipliers would be set equal to zero. Taking the partial derivatives of p with respect to the Lagrange Multipliers just gives the constraint equations, and taking the partial derivatives with respect to the independent variables, xj* (j = 1, 2, ...m) gives:

Equ4-20.jpg (6289 bytes)

and xj* for j = m + 1,...n is zero since x* is the optimal solution.

     The values of the Lagrange Multipliers are obtained from the solution of equation (4-20). Written in matrix notation, equation (4-20) is:

c + ATl = 0                            (4-21)

where AT is the transpose of the matrix A.

     Using the matrix identity [AT]-1 = [A-1]T and solving for the Lagrange Multipliers gives:

l = -[A-1]T c                            (4-22)

In terms of the elements of the inverse of the optimal basis bik, equation (4-22) can be written as:

Equ4-23.jpg (4999 bytes)

     With this as background, the effect of the five changes on the optimal solution can be determined. The inverse of the optimal basis A-1 and the Lagrange Multipliers will be used to evaluate these changes. The following example illustrates the computation of the inverse of the optimal basis and the Lagrange Multipliers.

Example 4-6

Solve the following problem by the Simplex Method and compute the inverse of the optimal basis and the Lagrange Multipliers:

Maximize:   2x1 +  x2 + x3

Subject to:    x1 +   x2 + x3 < 10

x1 + 5x2 + x3 > 20

Adding slack variables gives:

Maximize:  2x1 + x2   +  x3              = p

Subject to:   x1 + x2   +  x3 + x4      = 10

x1 + 5x2 + x3     - x5   = 20

An initially feasible basis is not available, and either artificial variables or algebraic manipulations must be performed to obtain one. Algebraic manipulations are used to have x1 and x2 be the variables in the basis. The result is:

         -  x3  -  9/4x4 - 1/4x5  = p - 17½      p = 17½

x1      + x3 +  5/4x4 +1/4x5  = 7½              x1 = 7½

     x2          - 1/4x4 - 1/4x5  = 2½              x2 = 2½

     x3 = 0

     x4 = 0

     x5 = 0

This is the optimum, for all the coefficients of the nonbasic variables in the objective function are negative. With the optimal solution known, the original problem now takes the form:

Maximize:  2x1  +  x2    = 17½

Subject to:   x1  +   x2   = 10

x1 + 5x2  = 20

The inverse of the optimal basis is computed using the cofactor method

Ex4-6a.jpg (3224 bytes)

where || A ji || = || A ij || T, and || A ij || the co-factors of the matrix A.(8)

Ex4-6b.jpg (12641 bytes)

The Lagrange Multipliers are computed using equation (4-22)

l = -[A-1]T c

Ex4-6c.jpg (5832 bytes)

or       l1= -9/4      and       l2 = ¼

Changes in the Right Hand Side of the Constraint Equations top

Changes in the right hand side of the constraint equations, i.e., changes in the bi's, will cause changes in the values of the variables in the optimal solution, the xj's. For an optimal solution to remain optimal, the xj's cannot become negative. Equation (4-18) will be used to evaluate changes in the xj's caused by changes in the bi's. The jth component of equation 4-18 is used.

Equ4-24.jpg (4863 bytes)

For a change in bi of an amount Dbi, the new value of xj*, called x*j,new is:

Equ4-25.jpg (9414 bytes)

for the optimal solution x* to remain optimal, the values of x*j,new must not become negative. The problem must be resolved if any of the x*j,new's becomes negative.

     The change in the value of the objective function for changes in the bi's, is computed using equation (4-19). Because the left-hand side of equation (4-19) is zero at the optimum, it can be written as:

Equ4-26.jpg (3552 bytes)

Using the same procedure for the change Dbi, the change in the value of the objective function is:

Equ4-27.jpg (7373 bytes)

It is from this equation that the Lagrange Multipliers receive the name shadow prices, for they have dimensions of dollars per unit and are used to compute the new value of the objective function from changes in the bi's. This is called a marginal cost calculation.

     Generally, in large linear programming computer programs, part of the computations includes the calculation of x*j,new and p*new for upper and lower limits on the bi's. Also, values of the Dbi's can be computed that will give the largest possible change in the xj*'s, i.e., xj,new = 0. Simultaneous changes in the right-hand side of the constraint equations can be performed using the 100% rule, and this procedure is described by Bradley et. al.(19).

Example 4-7

For the problem given in example 4-6, find the new optimal solution for Db1 = -5 without resolving the problem. Using equation (4-25) to compute the changes in the xi's gives:

x1,new  =  x1 + b11 Db1  +  b12 Db2

x2,new  =  x2 + b21 Db1  +  b22 Db2

Substituting in the values for Db1 = -5 and Db2 = 0 gives

x1,new  =  7½ + (5/4)(-5)   =  5/4

x2,new  =  2½ + (-¼)(-5)   = 15/4

Using equation (4-27), the change in the objective function is computed as:

p*new = p* - [l1 Db1 + l2 Db2] = 17½ - (-9/4) (-5)

p*new = 25/4

     Changes in the right-hand side of the constraint equations are part of the sensitivity analysis of the MPSX program. In Table 4-12(a) the smallest and largest values of the right-hand side of the constraint equations are given for the optimal solution to remain optimal as LOWER LIMIT and UPPER LIMIT. Also the Lagrange Multipliers were computed, and these are called the DUAL ACTIVITY in the MPSX nomenclature of Table 4-12(a). In this table NONE indicates that there is no bound, and a dot indicates that the value was zero. Correspondingly, in Table 4-12(b) the upper and lower limits on the variables are given. In this case the dot indicates that the lower bound was zero, and NONE indicates that there was no upper bound on the variable because BOUNDS was not used.

Changes in the Coefficients of the Objective Function top

It is necessary to consider the effect on the optimal solution of changes in the cost coefficients of the variables in the basis and those not in the basis also. Referring to equation (4-19), the coefficients of the variables that are not in the basis, i.e., xm+1,...,xn must remain negative for maximization.

Equ4-28.jpg (5402 bytes)

If a coefficient becomes positive from a change in the cost coefficients, it would be profitable to have that variable enter the basis.

     The values of the Lagrange Multipliers are affected by changes in the cost coefficients of the variables in the basis, since they are related by equation (4-23). The term in the brackets in equation (4-28) is named the reduced cost(19), and it is convenient to define this term as c'j to obtain the equation that accounts for the effect of changes in cost coefficients on the optimal solution.

Equ4-29.jpg (5350 bytes)

where cj' must remain negative for the optimal solution to remain optimal for maximizing.

     The Lagrange Multipliers, li's, are eliminated from equation (4-29) by substituting equation (4-23) to give:

Equ4-30.jpg (11589 bytes)

For a change, Dcj, in the nonbasic variable cost coefficient, cj, and for a change, Dck, in the basic variables cost coefficient ck, it can be shown that the following equation holds:

Equ4-31.jpg (6845 bytes)

When maximizing, the new coefficients must remain negative for the variables not in the basis to have the optimal solution remain optimal, i.e.:

c'j, new < 0                           (4-32)

If (4-32) does not hold, then a new optimal solution must be obtained by solving the linear programming problem with the new values of the cost coefficients.

     If the optimal solution remains optimal, the new value of the objective function can be computed with the following equation:

Equ4-33.jpg (3987 bytes)

     If the problem must be resolved, it is usually convenient to introduce an artificial variable and proceed from this point to the new optimal solution. Large linear programming codes usually have this provision. Also, they can calculate a range of values of the cost coefficients where the optimal solution remains optimal and the corresponding effect on the objective function. The procedure used is called the 100% rule and is described by Bradley, et. al.(19).

Example 4-8

For the problem given in example 4-6, compute the effect of changing the cost coefficient c1 from 2 to 3 and c3 from 1 to 4, i.e., Dc1 = 1 and Dc3 = 3. Using equation (4-31) produces the following results for j = 3,4,5 (since Dc2 = 0).

c'3, new = c'3 + Dc3 - Dc1[a13b11+ a23b12]

substituting

c'3, new = -1 + 3 - (1)[(1)(5/4) + (1)(-¼)] = 1

c'4, new = c'4 + Dc4 - Dc1[a14b11+ a24b12]

substituting

c'4, new = -9/4 + 0 - (1)[(1)(5/4) + (0)(-¼)] = -13/4

c'5, new = c'5 + Dc5 - Dc1[a15b11+ a25b12]

substituting

c'5,new = -¼ + 0 - (1)[(0)(5/4) + (-1)(-¼)] = -½

An improvement in the objective function can be obtained, for c'3,new is greater than zero. Increasing x3 from zero to a positive number will increase the value of the objective function. However, the problem will have to be resolved.

     In the MPSX program the RANGE command and the parametrics are used to find the range over which the variables, right-hand-sides, and the coefficients of the objective function and constraints may be varied without changing the basis for the optimal solution. Output from the RANGE command consists of four sections: sections 1 and 2 for rows and columns at their limit levels, and sections 3 and 4 for rows and columns at an intermediate level (in the basis), which will be described here. Further information is given in References (12, 15, and 16).

     In Table 4-13 the RANGE output is shown for constraint rows at upper and lower limit levels. The first four columns have the same meaning as in the output from SOLUTION. The next four have two entries for each row. LOWER ACTIVITY and UPPER ACTIVITY are the lower and upper bounds on the range of values that the row activity (right-hand side) may have. Because the slack variable for the row is zero at a limit level, the upper and lower activities are numerically equal to the bounds of the range that the right-hand sides may have. The two UNIT COST entries are the changes in the objective function per unit change of activity when moving from the solution activity to either the upper or lower bound. The column labeled LIMITING PROCESS contains the name of the row or column that will leave the basis if the activity bounds are violated. The status column, AT, indicates the status of the leaving row or column. For example, in line 15 of Table 4-13, the row FOMIN is at its lower limit, its activity value is 10,000, and the right-hand side may take on values between 5,652.8 and 12,252.2 without changing the basis. If FOMIN goes below 5,652.8, then CCFODF would leave the basis. If FOMIN exceeds 12,252.2, then SRFODF would leave the basis. The cost associated with a change in FOMIN is $27.18/bbl with profit decreasing for an increase in FOMIN.

     Similar information is provided in Table 4-14 about the range over which the nonbasis activities (variables) at upper or lower limits may be varied without forcing the row or column in LIMITING PROCESS out of the basis. An additional column is included in the table, LOWER COST/UPPER COST to show the highest and lowest cost coefficients at which the variable will remain in the basis. If the objective function cost coefficient goes to the LOWER COST, the activity will increase to UPPER ACTIVITY. Similarly, if its cost goes below UPPER COST, the activity will be decreased to LOWER ACTIVITY.

     The third section of output from the range study is given in Table 4-15. It contains information about constraints that are not at their limits and, therefore, are in the basis of the optimal solution. The column headings have the same meaning as the headings for section 1 except that here the variables listed under LIMITING PROCESS will enter the basis if the bounds are exceeded.

     The fourth section, shown in Table 4-16, gives the RANGE analysis of the columns in the basis. As in Table 4-15, the variable listed under LIMITING PROCESS will enter the basis when activity is forced beyond the upper or lower activity bounds. The information of greatest interest here are the entries for columns with coefficients in the objective function. These are CRUDE(39), FGAD(40), SRNRF(45), FGRF(46), SRFOCC(49), FCCC(50), PG(57), RG(62), DF(67), and FO(71). Examining the first row in Table 4-16, one finds that if the cost coefficient becomes - 41.15 the activity (crude flow rate) would be reduced from 100,000 to 94,572.98. Consequently, if the cost of crude oil is increased to $40.09/barrel (operating cost is $1.00/barrel) the refinery should reduce its throughput by only 5.2%. Also notice that the lower cost for premium gasoline (PG) is 44.082, while the input cost is 45.35. If the bulk sale price of premium gasoline were to drop to $44.08/barrel, it would be profitable for the refinery to produce 23,655 barrels/day, a drop of almost 50% from the optimum value of 47,111barrels/day currently produced. A similar analysis for fuel oil (FO) indicates that it will probably never be profitable to produce fuel oil, for the sale price would have to increase from $13.14/bbl to $40.32/barrel before production should be increased above the minimum.

Changes in Coefficients of the Constraint Equations top

Referring to equation (4-29), it is seen that changes in the aij's for the nonbasic variables will cause changes in c'j. For the optimal solution to remain optimal, c'j < 0 when maximizing, and if not, the problem must be resolved. To evaluate the changes in the coefficients of the constraint equations, aij, several pages of algebraic manipulations are required. This development is similar to the ones given here for the bi's and cj's and is discussed in detail by Garvin (3) and Gass (4), along with the subject of parametric programming, i.e., evaluating a set of ranges on the aij's, bi's, and cj's where the optimal solution remains optimal. Due to space limitations, these results will not be given here. Also the MPSX code has the capability of making these evaluations, as previously mentioned.

Addition of New Variables top

The effect of adding new variables can be determined by modifying equation (4-19). If k new variables are added to the problem, then k additional terms will be added to equation (4-19), and the coefficient of the kth term is:

Equ4-34.jpg (4195 bytes)

     Each of these k terms can be computed with the available information. If all of these are less than zero, the original optimal solution remains at the maximum. If equation (4-34) is greater than zero, the solution can be improved, and the problem has to be resolved. Artificial variables are normally used to evaluate additional variables to obtain new optimal solution.

Addition of More Constraint Equations top

For the addition of more constraint equations, the procedure is to add artificial variables and proceed with the solution to the optimum. The artificial variables supply the canonical form for the solution. The following example shows the effect of adding an additional independent variable and an additional constraint equation to a linear programming problem to illustrate the application of the methods described above.

Example 4-9

Solve the linear programming problem using the Simplex Method

Minimize:          x1  - 3x2

Subject to:     3x1   -   x2  < 7

-2x1 + 4x2  < 12

     Introduce slack variables for an initially feasible basis, and ignore the terms in parentheses for now. This gives:

   x1  - 3x2              (+ 2x5)  = c             c = 0

3x1  -   x2   + x3      (+ 2x5)  = 7            x3 = 7

-2x1 + 4x2        + x4             = 12         x4 = 12

x1 = 0

x2 = 0

When the Simplex Method is applied, x2 enters and x4 leaves the basis.

     Performing the algebraic manipulations gives:

- 0.5x1              + 0.75x4 (+ 2x5)   = c + 9      c = -9

  2.5x1       + x3 + 0.25x4 (+ 2x5)   = 10         x3 = 10

- 0.5x1 + x2       + 0.25x4               = 3           x2 = 3

x1 = 0

x4 = 0

When the Simplex Method is applied, x1 enters and x3 leaves the basis, giving the following results:

           0.2x3 + 0.8x4 (+ 2.4x5)  = c + 11        c  = -11

x1     + 0.4x3 + 0.1x4 (- 0.8x5)  = 4                x1 = 4

    x2 + 0.2x3 + 0.3x4 (+ 0.4x5)  = 5               x2 = 5

x3 = 0

x4 = 0

The optimal solution has been obtained, for all of the coefficients of the variables in the objective function (not in the basis) are positive.

     We compute the inverse of the optimal basis A-1 and the Lagrange Multipliers, having obtained the optimal solution as follows:

Ex4-9a.jpg (8431 bytes)

For Lagrange Multipliers, equation (4-22) is used:

l = - [A-1]T · c

and substituting gives

Ex4-9b.jpg (5988 bytes)

If the first constraint equation is changed as follows by adding another variable x5:

3x1 - x2 + 2x5 < 7

and the objective function is changed by including x5 as shown below:

x1 - 3x2 + 2x5

determine how this addition of a new variable affects the optimal solution found previously. The linear programming problem now has the following form:

   x1  - 3x2    + 2x5                 = c

3x1  -   x2     + 2x5 + x3          = 7

-2x1 + 4x2                    + x4   = 12

To determine if the optimal solution remains optimal, equation (4-34) is used. For this problem n = 4, k = 1, and m = 2, and equation (4-34) has the form:

[c5 + a1,5 l1+ a2,5 l2]

substituting gives:

[2 + 2(1/5) + 0(4/5)] = 2.4 > 0

The optimal solution remains optimal, for equation (4-34) is positive, and it is not necessary to resolve the problem. x5 is not in the basis and has a value of zero.

     The terms in parentheses show the solution with the additional variable included. As can be seen, the coefficient at the final step is the same as computed using equation (4-34).

     Find the new optimal solution if the following constraint equation is added to the problem

-4x1 + 3x2 + 8x5 + x6 = 10

The constraint equation is added to the optimal solution set so the problem will not have to be completely solved and is:

                   0.2x3 + 0.8x4 + 2.4x5           = c + 11

   x1          + 0.4x3 + 0.1x4 - 0.8x5          = 4

            x2 + 0.2x3 + 0.3x4 + 0.4x5          = 5

-4x1+ 3x2                          +    8x5 + x6  = 10

x6 is used as the variable in the basis from the additional constraint equation. x1 and x2 are eliminated from the added constraint equation by algebraic manipulation, and gives:

    0.2x3 + 0.8x4 + 2.4x5         = c + 11     c = -11

x1       + 0.4x3 + 0.1x4 -  0.8x5         = 4            x1 = 4

     x2  + 0.2x3 + 0.3x4 + 0.4x5         = 5            x2 = 5

                  x3  - 0.5x4 +   10x5 + x6  = 11          x6 = 11

   x4 = 0

   x5 = 0

The new optimal solution has been found, for all of the coefficients in the objective function are positive. Artificial variables would normally have been used, especially in a computer program, to give a feasible basis and proceed to the optimum.

Closure top

In this chapter the study of linear programming was taken through the use of large computer codes to solve industrial problems. Sufficient background was provided to be able to formulate and solve linear programming problems for an industrial plant using one of the large linear programming codes and to interpret the optimal solution and associated sensitivity analysis. In addition, this background should provide the ability for independent reading on extensions of the subject.

     The mathematical structure of the linear programming problem was introduced by solving a simple problem graphically. The solution was found to be at the intersection of constraint equations. The Simplex Algorithm was then presented, which showed the procedure of moving from one intersection of constraint equations (basic feasible solution) to another and having the objective function improve at each step until the optimum was reached. Having seen the Simplex Method in operation, we discussed the important theorems of linear programming, which guaranteed that the global optimum would be found for the linear objective function and linear constraints. Then methods were presented which illustrated how a process flow diagram and associated information could be converted to a linear programming problem to optimize an industrial process. This was illustrated with a simple petroleum refinery example, and the solution was obtained using a large standard linear programming code, Mathematical Programming System Extended (MPSX), on an IBM 4341 computer. The chapter was included with a discussion of post-optimal analysis procedures which evaluated the sensitivity of the solution to changes in important parameters of linear programming problem. This sensitivity analysis was illustrated using simple examples and results from the solution of the simple refinery using the MPSX code.

     A list of selected references is given at the end of the chapter for information beyond that presented here. These texts include the following topics. The Revised Simplex Method is a modification of the Simplex Method that permits a more accurate and rapid solution using digital computers. The dual linear programming problem converts the original or primal problem into a corresponding dual problem which may be solved more readily than the original problem. Parametric programming is an extension of sensitivity analysis where ranges on the parameters, aij's, bi's, and cj's, are computed directly considering more than one parameter at a time. Also, there are decomposition methods that take an extremely large problem and separate or decompose it into a series of smaller problems that can be solved with reasonable computer time and space. In addition, special techniques have been developed for a class of transportation and network problems which facilitate their solution. Linear programming has been extended to consider multiple conflicting criteria, i.e., more than one objective function, and this has been named goal programming. An important extension of linear programming is the case where the variables can take on only integer values, and this has been named integer programming. Moreover, linear programming and the theory of games have been interfaced to develop optimal strategies. Finally, almost all large computers have one or more advanced linear programming codes capable of solving problems with thousands of constraints and thousands of variables. It is very time consuming and tedious task to assemble and enter reliable data correctly in using these programs. These codes, e.g., MPSX, are very efficient and use sparse matrix inversion techniques, methods for dealing with ill-conditioned matrices, structural data formats, and simplified input and output transformations. Also, they usually incorporate post optimal ranging, generalized upper bounding, and parametric programming (9,12). Again, the topics mentioned above are discussed in the articles and books in the References and the Selected List of Texts at the end of the chapter.

Selected List of Texts on Linear Programming and Extensions top

Bazaraa, M. S., and J. J. Jarris, Linear Programming and Network Flows, John Wiley and Sons, Inc., New York (1977).

Charnes, A., and W. W. Cooper, Management Models and Industrial Applications of Linear Programming, Vols. 1 and 2, John Wiley and Sons, Inc., New York (1967).

Garfinkel, R. S., and G. L. Nemhauser, Integer Programming, John Wiley and Sons, Inc., New York (1972).

Glicksman, A. M., An Introduction to Linear Programming and the Theory of Games, John Wiley and Sons, Inc., New York (1963).

Greenberg, H., Integer Programming, Academic Press, New York (1971).

Hadley, G. H., Linear Programming, Addison-Wesley, Inc., Reading, Mass. (1962).

Land, A. H., and S. Powell, Fortran Codes for Mathematical Programming: Linear, Quadratic and Discrete, John Wiley and Sons, Inc., New York (1973).

Lasdon, L., Optimization Theory for Large Systems, Macmillan and Co., New York (1970).

Naylor, T. H., and E. T. Byrne, Linear Programming Methods and Cases, Wadsworth Publishing. Co., Balmont, Calif. (1963).

Orchard-Hays, W., Advanced Linear Programming Computing Techniques, McGraw-Hill Book Co., New York (1968).

Papadimitriou, C. H., and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1982).

Schrage, L., Linear Programming Models with LINDO, Scientific Press, Palo Alto, Calif.(1981).

Taha, H. A., Integer Programming: Theory, Applications and Computations, Academic Press, New York (1975).

References top

1.Dantzig, G. B., Linear Programming and Extensions, Princeton University Press, Princeton, N.J. (1963).

2.An Introduction to Linear Programming, I.B.M. Data Processing Application Manual E20 - 8171, I.B.M. Corp., White Plains, N.Y. (1964).

3.Garvin, W. W., Introduction to Linear Programming, McGraw-Hill Book Co., N.Y. (1966).

4.Ibid., p. 10

5.Ibid., p. 12

6.Ibid., p. 21

7.Gass, S. I., Linear Programming: Methods and Applications, 5th Ed., McGraw-Hill Book Co., New York (1985).

8.Smith, C. L., R. W. Pike, P. W. Murrill, Formulation and Optimization of Mathematical Models, International Textbook Co., Scranton, Pa. (1970).

9.Holtzman, A. G., Mathematical Programming for Operations Researchers and Computer Scientists, Ed. A.G. Holtzman, Marcel Dekker, Inc., New York (1981).

10.Aronofsky, J. S., J. M. Dutton, and M. T. Tayyabkhan, Managerial Planning with Linear Programming in Process Industry Operations, John Wiley and Sons, Inc., New York (1978).

11.Anonymous, Oil and Gas Journal, 394 (May 3, 1982).

12.Murtagh, B. A., Advanced Linear Programming: Computation and Practice, McGraw-Hill Book Co., New York (1981).

13.Smith, M. G., and J. S. Bonner, Computer-Aided Process Plant Design, Ed. M.E. Leesley, Gulf Publishing Co., Houston, p. 1335 (1982).

14.Stoecker, W. F., Design of Thermal Systems, 2nd Ed., McGraw-Hill Book Co., p.271 New York (1980).

15.IBM Mathematical Programming System Extended/370 (MPSX/370) Program Reference Manual, SH19-1095-3, 4th Ed., IBM Corp., White Plains, N.Y. (1979).

16.IBM Mathematical Programming System Extended/370 Primer, GH19-1091-1, 2nd Ed., IBM Corp., White Plains, N.Y. (1979).

17.Ignizio, J. P., Linear Programming in Single and Multiple Objective Systems, Prentice-Hall, Inc., Englewood Cliffs, N. J. (1982).

18.Quandt, R. E., and H. W. Kuhn, "On Upper Bounds for the Number of Iterations in Solving Linear Programs," Operations Research, 12:161-5 (1964).

19.Bradley, S. P., A. C. Hax, and T. L. Magnanti, Applied Mathematical Programming, Addison-Wesley Publishing Co., Reading, Mass. p. 97 (1977).

top