Programming, linear

Linear programming is an optimisation technique that can be used when the objective function and constraints can be expressed as a linear function of the variables see Driebeek (1969), Williams (1967) and Dano (1965). 

The technique is useful where the problem is to decide the optimum utilisation of resources. Many oil companies use linear programming to determine the optimum schedule of products to be produced from the crude oils available. Algorithms have been developed for the efficient solution of linear programming problems and the SIMPLEX algorithm, Dantzig (1963), is the most commonly used. 

Examples of the application of linear programming in chemical process plant design and operation are given by Allen (1971), Rudd and Watson (1968), Stoecker (1991), and Urbaniec (1986). 

Linear programming problems involve linear objective function and linear constraints. The LP optimum lies at a vertex of the feasible region, which is the basis of the simplex method. LP can have 0 (infeasible), 1, or infinite (multiple) solutions. The set of all feasible solutions to a linear programming problem is a convex set. Therefore, a linear programming optimum is a global optimum. 

Example 5.1 A batch product manufacturer sells products A and B. The profit from A is 12/kg and from B 7/kg. The available raw materials for the products are 100kg of C and 80 kg of D. To produce one kilogram of A, the manufacturer needs 0.5kg of C and 0.5kg of D. To produce one kilogram of B, the manufacturer needs 0.4kg of C and 0.6kg of D. The market for product A is 60kg and for B 120kg. How much raw material should be used to maximize the manufacturer s profit  

The sensitivity of the linear programming solution is expressed in terms of shadow prices (dual price/simplex multipliers) and opportunity (reduced) cost. A shadow 

Simplex methods ([72, 71, 73]) move from boundary to boundary within the feasible region. The simplex methods requires initial basic solution to be feasible. There are various variants of simplex methods like dual simplex method, the Big M method, and the two-phase simplex method. Interior point methods on the other hand visit points within the interior of the feasible region more inline with the nonlinear programming methods. In general, good interior point methods perform as well or better than simplex codes on larger problems when no prior information about the solution is available. When such warm start information is available, simplex methods are able to make much better use of it than the interior point methods. 

An important class of the constrained optimization problems is one in which the objective function, equality constraints and inequality constraints are all linear. A linear function is one in which the dependent variables appear only to the first power. For example, a linear function of two variables x and x2 would be of the general form  

1 and Product 2) in a batch plant involving two steps (Step I and Step II). The value of Product 1 is 3 -kg 1 and that of Product 

2 is 2 -kg 1. Each batch has the same capacity of 1000 kg per batch but batch cycle times differ between products. These are given in Table 3.1. 

Step I has a maximum operating time of 5000 h y 1 and Step II 6000 h y 1. Determine the operation of the plant to obtain the maximum annual revenue. 

Solution For Step I, the maximum operating time dictates that 25 i + 10//2 5000 

During the postwar period, several tools were developed to assist in decision making to address various types of recurring industrial problems in the area of operations. The most applicable tools to today s world are linear programming and the CPM method. One of the first textbooks on OR appeared in 1957, Introduction to Operations Research, by Churchman, Ackoff, and Amoff. 

OR uses the scientific method, through experimentation or simulation, utilizing a general sequential procedure or methodology (which may be iterative) to determine the structure of a situation and find the cause and effect relationships between variables. The typical stages of a real OR application are as follows  

At this stage in your career, we will show you, in some detail, two of the ten stages (marked with ) of OR application the formulation of a mathematical model and an application algorithm. In earlier chapters, you were continuously tested to formulate mathematical expressions to solve a wide variety of problems, so you are fully prepared to learn the right procedure to formulate and, with the help of an appropriate tool, solve these interesting and engaging problems. 

In the early 1950s, many US companies experienced strong growth in operational levels, and LP was used to determine activity levels and optimal resource allocation. 

LP (understood as being synonymous with linear planning) is currently one of the most widely used tools in OR. Furthermore, LP has expanded its scope of application to optimize a variety of 

Several, but not all, of these mathematical methods (e.g. multicriteria decision making. Chapter 26) or problems (the non-hierarchical clustering methods of Chapter 30, which can be treated as allocation models) have been treated earlier. In this chapter, we will briefly discuss the methods that are relevant to chemo-metricians and have not been treated in earlier chapters yet. 

Suppose that a manufacturer prepares a food product by adding two oils (A and B) of different sources to other ingredients. His purpose is to optimize the quality 

The line y, = 65 = 30x, + 15x2 shown in Fig. 42.1. All points on that line or above satisfy the constraint 30x, + 15x2 Similarly, all points lying above line y2 = lOx, + 25x2 = 40 satisfy the second constraint of eq. (42.2), while the last constraints limit the acceptable solutions to positive or zero values for x, and X2. The acceptable region is the shaded area of Fig. 42.1. 

We can now determine which pairs of (x, Xj) values yield a particular z. In Fig. 42.1 line Zi shows all values for which z = 50. These (x, X2) do not belong to the acceptable area. However, we can now draw parallel lines until we meet the acceptable area. This happens in point B with line Z2- The coordinates of this point are obtained by solving the set of simultaneous equations 

Let us look at another example (Fig. 42.2) [2]. A laboratory must carry out routine determinations of a certain substance and uses two methods, A and B, to do this. With method A, one technician can carry out 10 determinations per day, with method B 20 determinations per day. There are only 3 instruments available for method B and there are 5 technicians in the laboratory. The first method needs no sophisticated instruments and is cheaper. It costs 100 units per determination while method B costs 300 units per determination. The available daily budget is 14000 units. How should the technicians be divided over the two available methods, so that as many determinations as possible are carried out Let the number of technicians working with method A be and with method B X2, and the total number of determinations z then, the objective function to be maximized is given by  

Solver is a powerful tool that is a standard Excel Add-In. It can produce solutions to many different kinds of problems, among which are the following  

It is typical to also impose so-called nonnegativity constraints. These are not essential but traditional. This can always be made the case by change of variables, but some lower limit is most often imposed. The nonnegativity constraints 

FIGURE 9.1 Graphical interpretation of a linear programming problem. 

Solver can handle LPs very robnstly. Before invoking Solver, a spreadsheet must be set up to represent the objective function and constraints. A typical spreadsheet setup for the example problan appears below  

The actual formulas for the cells in column B are shown in bold in column C. The initial values for x, and X2 have been set to zero other values could be used, but selecting the origin as initial values is the usual procedure. 

---

Thus, if film transfer coefficients vary significantly, then Eq. (7.6) does not predict the true minimum network area. The true minimum area must be predicted using linear programming. However, Eq. (7.6) is still a useful basis to calculate the network area for the purposes of capital cost estimation for the following reasons ... 

Calculate the weighted network area Anetwork from Eq. (7.22). When the weighted h values i4>h) vary appreciably, say, by more than one order of magnitude, an improved estimate of Anetwork can be evaluated by linear programming. ... 

Grossmann, I. E., Mixed-Integer Non-Linear Programming Techniques for the Synthesis of Engineering Systems, Res. Eng. Design, 1 205, 1990. 

Linear paraffins Linear programming Linear rollback model Linear sensor arrays Linear superelasticity Linear topology Linear units Linen... 

A. M. Morshedi, C. R. Cutier, and T. A. Skrovanek, "Optimal Solution of Dynamic Matrix Control with Linear Programming Techniques,"... 

If the source fingerprints, for each of n sources are known and the number of sources is less than or equal to the number of measured species (n < m), an estimate for the solution to the system of equations (3) can be obtained. If m > n, then the set of equations is overdetermined, and least-squares or linear programming techniques are used to solve for L. This is the basis of the chemical mass balance (CMB) method (20,21). If each source emits a particular species unique to it, then a very simple tracer technique can be used (5). Examples of commonly used tracers are lead and bromine from mobile sources, nickel from fuel oil, and sodium from sea salt. The condition that each source have a unique tracer species is not often met in practice. 

In real-life problems ia the process iadustry, aeady always there is a nonlinear objective fuactioa. The gradieats deteroiiaed at any particular poiat ia the space of the variables to be optimized can be used to approximate the objective function at that poiat as a linear fuactioa similar techniques can be used to represent nonlinear constraints as linear approximations. The linear programming code can then be used to find an optimum for the linearized problem. At this optimum poiat, the objective can be reevaluated, the gradients can be recomputed, and a new linearized problem can be generated. The new problem can be solved and the optimum found. If the new optimum is the same as the previous one then the computations are terminated. 

Otherwise, the iterations consisting of formulation of linear approximations and the solution of the linear programming problem are continually repeated (48). 

Linear programming. Most current commercial codes for hn-... 

Selection of feedstock for thermal cracking to ethylene by linear programming... 

Miirty, Linear Programming, Wiley, New York, 1983. Reklaitis, Ravin-dran, and Ragsdell, Engineeiing Optimization, Wiley—Interscience, New York,... 

One important class of nonlinear programming techniques is called quadratic programming (QP), where the objective function is quadratic and the constraints are hnear. While the solution is iterative, it can be obtained qmckly as in linear programming. This is the basis for the newest type of constrained multivariable control algorithms called model predic tive control. The dominant method used in the refining industiy utilizes the solution of a QP and is called dynamic matrix con-... 

Production Controls The nature of the produc tion control logic differs greatly between continuous and batch plants. A good example of produc tion control in a continuous process is refineiy optimization. From the assay of the incoming crude oil, the values of the various possible refined products, the contractual commitments to dehver certain products, the performance measures of the various units within a refinery, and the hke, it is possible to determine the mix of produc ts that optimizes the economic return from processing this crude. The solution of this problem involves many relationships and constraints and is solved with techniques such as linear programming. 

Mathematical modeling, using digital computers, aids in performing a systems-type analysis for either the entire system or parts of it. By means of integer or linear-programming techniques, optimum systems can be identified. The dynamic performance of these can then be determined by simulation techniques. 

Once the highest steam level is set, then intermediate levels must be established. This involves having certain turbines exhaust at intermediate pressures required of lower pressure steam users. These decisions and balances should be done by in-house or contractor personnel having extensive utility experience. People experienced in this work can perform the balances more expeditiously than people with primarily process experience. Utility specialists are experienced in working with boiler manufacturers on the one hand and turbine manufacturers on the other. They have the contacts as well as knowledge of standard procedures and equipment size plateaus to provide commercially workable and optimum systems. At least one company uses a linear program as an aid in steam system optimization. 

Many process engineers think of linear programming (L.P.) as a sophisticated mathematical tool, which is best applied by a few specialists extremely well grounded in theory. This is certainly true for your company s central linear program. The layman does not write a linear program, he only provides input that will model the process in which he is interested. 

The linear program can be designed to deliver a wealth of base case information, such as ... 

If plant expansion is being studied with the idea of determining the best practical upper limit, the linear program can be a great help. Each incremental expansion step can be evaluated and payouts determined off line. Also, each piece of proposed new equipment can be evaluated as to its effect on the entire plant. 

Having a linear program available allows the designer to generate better designs, but does not necessarily make his job easier. In fact, it may put additional pressure on him to be sure his results are optimal rather than just a satisfactory design. 

Process Design vs. Accounting Linear Program Models... 

---