Chapter 4


Introduction top

   Linear programming is the most widely applied of all of the optimization methods.  The technique has been used for optimizing many diverse applications, including refineries and chemical plants, livestock feed blending, routing of aircraft and scheduling their crews. Many industrial allocation and transportation problems can be optimized with this method.  The application of linear programming has been successful, particularly in cases of selecting the best set of values of the variables when a large number of interrelated choices exists.  Often such problems involve a small improvement per unit of material flow times large production rates to have as the net result be a significant increase in the profit of the plant.   A typical example is a large oil refinery where the stream flow rates are very large, and a small improvement per unit of product is multiplied by a very large number to obtain a significant increase in profit for the refinery.

     The term programming of linear programming does not refer to computer programming but to scheduling.  Linear programming was developed about 1947, before the advent of the computer, when George B. Dantzig (1) recognized a generalization in the mathematics of scheduling and planning problems.  Developments in linear programming have followed advances in digital computing, and now problems involving several thousand independent variables and constraints equations can be solved.

     In this chapter a geometric representation and solution of a simple linear programming problem will be given initially to introduce the subject and illustrate the way to capitalize on the mathematical structure of the problem.  This will be followed by a presentation of the simplex algorithm for the solution of linear programming problems.  Having established the computational algorithm, we will give the procedure to convert a process flow diagram into a linear programming problem, using a simple petroleum refinery as an illustration.  The method of solution, using large linear programming computer codes, then will be described, and the solution of the refinery problem, using the IBM Mathematical Programming System Extended (MPSX), will illustrate the procedure and give typical results obtained from these large codes.  Once the optimal solution has been obtained, sensitivity analysis procedures will be detailed that use the optimal solution to determine ranges on the important parameters where the optimal solution remains optimal.  Thus, another linear programming solution is not required.  This will be illustrated also using results of the refinery problem obtained from the MPSX solution. Finally, a summary will be given of extensions to linear programming and other related topics