Linear programming examples

Consider a typical linear programming example in which N grades of paper are produced on a paper machine. Due to raw materials restrictions not more than a, tons of grade i can be produced in a week. Let... 

For the linear-programming example problem presented in this chapter where the simultaneous-equation solution is presented in Table 5, solve the problem using the simplex algorithm as was done in the text for Ihe example solved in Fig. 11-10. Use as the initial feasible starting solution the case of solution 2 in Table 5 where x2= S4 = 0. Note that this starting point should send the solution directly to the optimum point (solution 6) for the second trial. 

Table 4.9 Input Parameters for Least Cost Scheduling Linear Program Example [Lund, 1990a]...

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. 

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. 

The example used here does not represent any particular process and is simpler than most real life plant cases. It does, how ever, have the elements needed to talk our way through the development of a process design linear program model. All models should have the following ... 

Using linear programming, resolve the dephenolization example presented in this chapter for the case when the two waste streams are allowed to mix. 

Employ linear programming to find the MOC solution for the toluene-removal example described in Section 3.10 (Example 3.3). 

The above equations coupled with Eqs. (9.10)-<9.18) represent the constraints of the CHARMEN-synthesis formulation. The objective is to minimize the cost of MSAs and heating/cooling utilities. This is a linear-programming formulation whose solution determines the optimal flowrate and temperature of each substream and heating/cooling utilities. In order to demonstrate this formulation, let us consider the following example. 

Programming Problems.25—Let be a vector whose components are n variables xlt , xn. The general programming problem is concerned with finding the extremum values of a function/(a ) subject to the constraints xy > 0 (j = 1, -, n) and gt(z) < 0 ( = 1, -,m). A simple but important example of this type of problem is the linear programming problem, which we shall treat in some detail later. 

Example 1.—A classical problem of linear programming is the diet problem. Given minimal needs for vitamins, iron, calcium, phosphorous etc., which are present in known proportions in a variety of possible foods with given prices, it is desired to determine a diet from these foods that meets the minimal needs for the vitamins and other ingredients at the lowest cost. To illustrate with a simple example and hypothetical figures, denote three types of food by Flt F2, F3, and two types of dietary requirements, e.g., vitamins by A and B. The table... 

Example 2.—A well-known special case of the linear programming problem is the transportation problem requiring an assignment of shipments of materials from sources to destinations according to total availability and total demand, that minimizes the tot l shipping cost. If we denote the sources by St (i = 1, , m) and the destinations by... 

This problem can be cast in linear programming form in which the coefficients are functions of time. In fact, many linear programming problems occurring in applications may be cast in this parametric form. For example, in the petroleum industry it has been found useful to parameterize the outputs as functions of time. In Leontieff models, this dependence of the coefficients on time is an essential part of the problem. Of special interest is the general case where the inputs, the outputs, and the costs all vary with time. When the variation of the coefficients with time is known, it is then desirable to obtain the solution as a function of time, avoiding repetitions for specific values. Here, we give by means of an example, a method of evaluating the extreme value of the parameterized problem based on the simplex process. We show how to set up a correspondence between intervals of parameter values and solutions. In that case the solution, which is a function of time, would apply to the values of the parameter in an interval. For each value in an interval, the solution vector and the extreme value may be evaluated as functions of the parameter. 

The basic polymer appears to be a hydroxylated polyether to which octadecyl chains have been bonded and so it behaves as a reverse phase exhibiting dispersive interactions with the solutes. An example of the separation of a series of peptides is shown in figure 15. The column was 3.5 cm long, 4.6 mm i.d. The solutes shown were (1) oc-endorphin, (2) bombesin, (3) y-endorphin, (4) angiotensin, (5) somatostatin and (6) calcitonon. The separation was carried out with a 10 min linear program from water containing 0.2% trifluoroacetic acid to 80% acetonitrile. 

Our ability to make these distinctions rests on the fact that we know the direction that the branching generation imposes on the updating of the variables. If we were not solving the problem in such a way that all the variables are explicitly determined by the branching, then these distinctions would not be so clear. For example, if some variable values were the result of solving an auxiliary linear program that involved these constraints, we could not classify the variables this way. 

Problems resembling the first example, but much more complex, are often studied in industry. For instance in the agro-food industry linear programming is a current tool to optimize the blending of raw materials (e.g. oils) in order to obtain the wanted composition (amount of saturated, monounsaturated and polyunsaturated fatty acids) or property of the final product at the best possible price. Here linear programming is repeatedly applied each time when the price of raw materials is adapted by changing markets. 

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). 

This chapter focuses on a new approach that allows for the comprehensive planning and optimization of multi-stage production processes - the quant-based combinatorial optimization. First, a distinction is drawn between classical approaches such as Linear Programming (LP) and the quant-based combinatorial approach. Before going into the special characteristics and requirements of the process industry the one model approach with quant-based combinatorial optimization is introduced. Then we will give two examples of how this new approach is applied to real life problems. 

The SNP optimizer is based on (mixed-integer) linear programming (MILP) techniques. For a general introduction into MILP we refer to [11], An SAP APO user has no access to the mathematical MILP model. Instead, the modeling is done in notions of master data of example products, recipes, resources and transportation lanes. Each master data object corresponds to a set of constraints in the mathematical model used in the optimizer. For example, the definition of a location-product in combination with the bucket definition is translated into inventory balance constraints for describing the development of the stock level over time. Additional location-product properties have further influence on the mathematical model, e.g., whether there is a maximum stock-level for a product or whether it has a finite shelf-life. For further information on the master data expressiveness of SAP SCM we refer to [9],... 

The optimization problem in this example comprises a linear objective function and linear constraints, hence linear programming is the best technique for solving it (refer to Chapter 7). 

In addition to providing optimal x values, both simplex and barrier solvers provide values of dual variables or Lagrange multipliers for each constraint. We discuss Lagrange multipliers at some length in Chapter 8, and the conclusions reached there, valid for nonlinear problems, must hold for linear programs as well. In Chapter 8 we show that the dual variable for a constraint is equal to the derivative of the optimal objective value with respect to the constraint limit or right-hand side. We illustrate this with examples in Section 7.8. 

In addition to their use as stand-alone systems, LPs are often included within larger systems intended for decision support. In this role, the LP solver is usually hidden from the user, who sees only a set of critical problem input parameters and a set of suitably formatted solution reports. Many such systems are available for supply chain management—for example, planning raw material acquisitions and deliveries, production and inventories, and product distribution. In fact, the process industries—oil, chemicals, pharmaceuticals—have been among the earliest users. Almost every refinery in the developed world plans production using linear programming. 

EXAMPLE 9.1 BRANCH-AND-BOUND ANALYSIS OF AN INTEGER LINEAR PROGRAM... 

---