- Introduction
- Concepts and Methods
- Concepts and Geometric Interpretation
- General Statement of the Linear Programming Problem
- Slack and Surplus Variables
- Feasible and Basic Feasible Solutions of the Constraint Equations
- Optimization with the Simplex Method
- Simplex Tableau
- Mathematics of Linear Programming
- Degeneracy
- Artificial Variables
- Formulating and Solving Problems
- Sensitivity Analysis
- Changes in the Right Hand Side of the Constraint Equation
- Changes in the Coefficients of the Objective Function
- Changes in the Coefficients of the Constraint Equations
- Addition of New Variables
- Addition of More Constraint Equations
- Closure
- Selected List of Texts on Linear Programming and Extensions
- References
- Problems
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
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 .top |