• Non ci sono risultati.

CHAPTER LINEAR PROGRAMMING AND APPLICATIONS

N/A
N/A
Protected

Academic year: 2021

Condividi "CHAPTER LINEAR PROGRAMMING AND APPLICATIONS"

Copied!
49
0
0

Testo completo

(1)

CHAPTER

LINEAR

PROGRAMMING

AND APPLICATIONS

7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.to

7.tr

Basic Concepts in Linear Programming Degenerate LP's-Graphical Solution Natural Occurrence of Linear Constraints

The Simplex Method of Solving Linear Programming Problems.

Standard LP Form.

Obtaining a First Feasible Solution The Revised Simplex Method Sensitivity Analysis.

Duality in Linear Programming.

The Karmarkar Algorithm LP Applications References Problems

254 259 261 263 270 273 279 282 284 287 290 290 291

250

(2)

LICATIONS 25I

Linear programming (LP) is one of the most widely used optimization techniques and one of the most effective. The term linear programming was coined by George Dantzig in 1947 to refer to the procedure of optimization in problems in which both the objective function and the constraints are linear (Dantzig, 1963). "Programming" does not specifically require computer coding, but you will find that the solution of almost all practical linear programming problems does involve the use of a computer code. Examples of LP problems which occur in plant management are:

1. Assign employees to schedules so that the work force is adequate each day of the week and worker satisfaction and productivity are as high as possible.

2. Select products to manufacture in the upcoming period, taking best advan- tage of existing resources and current prices to yield maximum profit.

3. Find a pattern of distribution from plants to warehouses that will minimize costs within the capacity limitations.

4. Submit bids on procurement contracts to take into account profit, competi- tors' bids, and operating constraints.

When stated mathematically, each of these problems potentially involves many variables, many equations, and inequalities. A solution must not only satisfy all of the equations, but also must achieve an extremum of the objective function, such as maximizing profit or minimizing cost. With the aid of computer codes you can solve LP problems with hundreds and even thousands of variables and constraints.

Linear programming (LP) prcb,ems are a type of convex programming problem, where the objective function is convex and the linear constraints form a convex set (see Chap. 4). This means that a local optimum will be a global optimum. Linear programming problems also exhibit the special characteristic that the optimal solution of the problem must lie on some constraint or at the intersection of several constraints, and not in the interior of the convex region where the inequality constraints can be satisfied. Examine Fig. 7.la in which an unconstrained linear objective function ,f(x) : xr + x2 is plotted. The first de- rivatives (Af lAxr,Af l1x) for /(x) can never be zero, so that for a linear objec- tive function, no finite maximum can exist. However, suppose you add linear inequality constraints to the maximization problem, namely xt 12 and xt < 1.

Now by inspection we see that a finite maximum occurs &t x, : 2 and xr: l;

note that this maximum lies at the intersection of the two constraints. If we remove either constraint, then ./ does not have a finite optimum. We conclude that to have a meaningful (well-posed) optimization problem, constraints must be introduced.

Suppose that an equality constraint is added to the problem stated above, namelv.

2 x , + x r : 2

(3)

,7

LINEAR PROGRAMMING AND APPLICATIONS

v : 3

\ r : , \

{ = 1

{ : 0

\

Figure 7.1a Contours for the linear objective function, f : xr + xz.

Figure 7.10 Addition of linear inequality constraints x132, x2< 1 (arrows point to the feasible rogion which is shaded).

x* : (2, 1)

(4)

LINEAR PROGRAMMING AND APPLICATIONS 253

Figure 7.1c Addition of an inequality constraint 2x, + xr: 2 (bold line indicates which points satisfy all constraints).

Figure 7.1c illustrates that the optimum value of / occurs at the intersection of the line xz: 1, and the equality constraint. At this point xf : 0.5 and f * : 1.5;

note that the constraint xl < 2 is no longer binding as in the previous case.

However, the optimum again appears at the intersection of two constraints.

The fact that the extremum in the solution of an LP problem lies on the intersection of constraints was recognized many years ago, and serves as the basis for a whole class of linear programming algorithms. A general linear pro- gramming problem can be stated as follows fmultiply "f(x) by - 1 for maximiza- tionl:

Minimize f (x):

Subject to x, ) 0 and

c 1 x ; : g r ; (7.r)

i : l, 2, ..., r (all r of the variables are nonnegative) (7.2)

f

I a i ; x i : b i

f

TZ-/

2 x t + x r : 2

x* : (0.5, 1.0)

j : 1 , 2 , . . . , m (7.3)

(5)

and

254 LINEAR PRoGRAMMING AND APPLIcATIoNs

or

A t x : b ,

a i i x i l b i i : m + 1 , . . . , p (7.4) or

Arx : b,

Hence there are r variables with r nonnegativity restrictions, (p - m) inequality constraints, and m equality constraints.

We will use the observation that the optimum lies at the intersection of constraints; therefore we could move along constraints which improve the value of the objective function. This strategy is essentially the basis for the LP algor- ithm presented later in this chapter.

7.I BASIC CONCEPTS IN LINEAR PROGRAMMING

Let us initiate the discussion of how to solve a linear programming problem by analyzing a detailed example. We will consider a simple version of a refinery blending and production problem, the solution for which can be illustrated via graphical techniques. Figure 7.2 is a schematic of feedstocks and products for the refinery (costs and selling prices are given in parentheses). Table 7.1 lists the information pertaining to the expected yields of the two types of crudes when processed by the refinery. Note that the product distribution from the refinery is quite different for the two crudes. Table 7.1 also lists the limitations on the established markets for the various products in terms of the allowed maximum daily production. In addition, processing costs are given.

To set up the complete linear programming problem, you must (1) formu- late an objective function, and (2) formulate the constraints for the refinery operation. You can see from Fig. 7.2 that six variables are involved, namely the flow rates of each of the two raw materials and the four products.

r

t/-/

Crude oil #l Crude oil #2

Sales price Gasoline ($36AbD Kerosene ($24lbbl) Fuel oil ($21lbbD Residual ($10/bbl) Figure 7.2 Refinery input and output schematic.

(6)

7.I BASIC CONCEPTS IN LINEAR PROGRAMMING 255

Table 7.1 Data for the refinery inputs and products

Volume percent yield

Maximum allowable production Crude # I Crude #2 bbl/day

Gasoline 80 M 24,ON

Kerosene 5 10 2,000

Fuel oil 10 36 6.000

Residual 5 10

Processing cost ($/bbl) 0.50 1.0O

Objective Function Let the variables be:

x r : b b U d a y o f c r u d e #1 xz : bbUdaY of ctude #2 xt : bbUday of gasoline x+: bbUdaY ofkerosene xs : bbUday of fuel oil xa : bbUday of residual

A typical linear objective function (to be maximized) is the difference between income and costs, namely profit:

Maximize f (x) : profit : income - raw material cost - processing cost (7.5) Income : 36xs * 24xn * 2lx, + l0xul

Raw material cost : 24x, * l5x2 I ,"U in dollars per day) (7,6t

I

Processing cost : 0.5x, * x2 )

Constraints

Using the yield data, we can write four linear equality constraints (material bal- ances) relating x, through xu:

Gasoline: 0.80x, -f O.44xr: y, Kerosene: 0.50x, I O.loxr: yn Fuel oil: 0.10x, t 36xt : xs Residual; 0.05xt * 0.10xt : vu

(7.7) (7.8)

(7.e)

( 7 . 1 0 )

(7)

256 LINEAR pRocRAMMINc AND AppLrcATroNS

The dimensionality of the problem can be reduced by eliminating the variables x3; x41 X5, ord x6 via the equality constraints, leaving just two independent variables, x, and xr. Introduction of (7.7) to (7.10) into the income function gives

Total income : (36)(0.80x, 1- 0.44xr) + (24)(0.50x1 * 0.10xr) + ( 2 1 ) ( 0 . 1 0 x 1 * 0 . 3 6 x r ) + (10X0.05x1 * 0.10xr)

$(32.6x, * 26.8xr)lday

and the objective function (profit) to be maximized after subtracting raw mater- ial and processing costs js

f ( x ) : 8 . l x t * 1 0 . 8 x , (7.tr)

Alternatively, you could express the objective function as minimize (-8.1x, - 10.8xr), but this step is not necessary in this illustration.

What other constraints exist or are implied in this problem? Table 7.1 lists certain restrictions on the x's in terms of production limits. You can formulate these as inequality constraintsi

.4. Gasolinei x: { 24,000; 0.80x, l'0.44xr<24,000 B. Kerosenei x+1 2,000; 0.05x1 * 0.10x, < 2,000 C. Fuel oil: xs S 6,0@; 0.10x1 i 0.36x, < 6,000

One other set of constraints, although not explicitly stated in the formula- tion of the problem, is composed of the nonnegativity restrictions on x1 and xr.

the independent variables:

(7.12) ( 7 . 1 3 ) ( 7 . r 4 )

x , > 0

x r ) 0 ( 7 . 1 s )

The independent variables must be zero or positive because it is meaningless to have negative production rates. Many chemical and physical variables are br' definition positive quantities, e.g., absolute pressure, concentration, absolute temperature. If for some reasons negative values variables must be allowed, then new nonnegative variables which are linear transformations of the old variables must be used in the LP problem.

The formal statement of the linear programming problem is now complete- consisting of Eqs. (7.11) to (7.15). We now proceed to solve the LP problem. A graphical illustration of the solution procedure will be used, consisting of three steps:

1. Plot the constraints on the xr-x, plane.

2. Determine the feasible region for x, and x, (those values of x, and x, that satisfy all of the constraints).

(8)

7.1 BASIC CONCEPTS IN LINEAR PROGRAMMING 257

3. Find the point along the boundary of the feasible region that maximizes the objective function f (x) by examining the constraint intersections; the slope of the objective function f (x): e, where e is a parameter indicating different values of f, can indicate which intersections are most favorable.

Figure 7.3 delineates the feasible region for the example problem by the bounds of constrainls A. B, and C. The shaded area, the feasible region that satisfies all five constraints, is convex. Figure 7.4 is an enlargement of the feasible region on which contours of the profit function are superimposed. As xt

and x2 become large, the profit function of course increases; however, unlimited production levels are not feasible given the constraints of the problem. Therefore you must find the maximum profit level which also satisfies the constraints.

Suppose you start at xr: xz:O, moving along the constraint xz:O (along the x, axis). We can improve the objective function up to the intersection of constraint A wilh xz:O. Next we move along constraint A, noting that the profit increases along this path also.

0.80x, * 0.44xt<24,000 0 . 0 5 x r * 0 . 1 0 x r < 2 , 0 0 0 0 . 1 0 x r * 0 . 3 6 x r < 6 , 0 0 0

Crude # 1 (in 1000 bbl)

Figure 7.3 Delineation of feasible region for the refinery blending problem.

(A) (B)

(c)

8 u l

o

N+

o

(J

20

: ::::: :: :i a r:; ,l

* l : l r : . .

feaSIDJO

redon';

(9)

258 LINEAR PROGRAMMING AND APPLICATIONS

!

)(x

6lrh

EO t

o

Crude #l (in 1000bbl)

FigureT.4Enlargementoffeasibleregionwithparameterizationofobjectivefunction.

It is helpful to examine the profit function to see which directions yield an improved vulrre of /. Figure 7.4 identifies three lines corresponding to three different profit levels; in iach case the equation for the profit contour is '/ : S.tx, + tb.8x, and each line identifies possible values of x, and xt which give this profit. NJte that it is easy to visualize from the contours which movements alon! the constraints yield improved values of /. In Fig. 7,! the optimum occurs at a corner of the feasible rlgion, with profit: /3. With some experience in graphical LP solution, you

"ui usually fnd tfre optimum corner by inspection ifter constructing the ielsible region and drawing only one profit contour'

R e g a r d l e s s o f h o w t h e f e a s i b l e r e g i o n i s c o n s t r u c t e d a n d w h a t s l o p e t h e profit line has, the unique maximizing lor minimizing) state for x will always be at a corner of the fe;sible region ior a well-posed problem. For a problem with two variables, the optimum *ill ul*uyt occur at the intersection of two or more constraint bounds. thar" intersecting constraint bounds are said to be ,.active,, if their value is 0. As discussed later, this idea can be generalized to n variables; in the n-dimensional case the optimum will lie at the intersection of the bounds of n or more difrerent inequality constraints'

(10)

,GENERATE LP's-GRAPHICALsoLUTIoN 259

In the refinery blending problem, using Fig. 7.4, note the optimum x(x*) occurs roughly at

xf x 26,N0 xt x 7,000

Because x* is at the intersection of two constraints ,4 and B, exact values of xl andxz can be found by solving inequalities (7.12) and (7,13) as equalities simul- taneously

0.80xt -t 0.44x, : 24,000 0 . 0 5 x t * 0 . 1 0 x r : 2 , 0 0 0 to get

(1) xl :26,200 xI : 6,900 "f(x*) : 8.1xf + 10.8xf : $286,700

Let us investigate the profit at other corners of the feasible region:

(2) (0,16,667) f (x) : $180,000 Intersection C and xt : g (3) (15,000, 12,500) f(x): $256,500 Intersection B and C (4) (30,000,0) f(x) : $243,000 Intersection A and x": Q

Therefore corner 1 is indeed the maximizing point. Note that the intersection of A and B corresponds to maximum production of gasoline and kerosene, but below the maximum production of fuel oil.

7.2 DEGENERATE LP's- GRAPHICAL SOLUTION

If the linear programming problem is not properly posed, it may not have a unique or even finite solution. Such LP problems are termed degenerate.

(1) A nonunique solution

Figure 7.5 shows a feasible region with respect to four inequality constraints and contours of /(x) for the following problem:

Maximize f (x) :2x, * 0.5x', Subject to 6x, + 5xt < 30 (A)

4 x 1 - t x , < 1 2 ( B ) x y x 2 > . 0

The objective function contours and constraint bound B are parullel, indicating that the objective function and the constraint B are not linearly independent (refer to Appendix B). Hence a unique solution cannot be found.

(11)

W LINBAR PRoGRAMMING AND APPLIcATIoNS

Figure 75 Occurrence of a lenunique optimrrm (shown by heavy line). A and B are inequa- lity constraints.

- r : . rlu

Other degenerate cases include Q) An unbomded optimwn (see Fig. 7.6)

Minimize f(x): -xt - xz Subject to 3x, - xr> O (A)

x 2 3 3 ( B )

X t r X r ) 0

x 1

l'rcure 7.6 occurrenoe of an unbounded optimum (the feasible region is partially bounded).

(12)

7.3 NATURAL OCCURRENCE OF LINEAR CONSTRAINTS 26I

Note that x, is unbounded for positive without bound.

(3) No feasible region exists (see Fig. 7.7)

Figure 7.7 No feasible region ex- ists. The arrows on the constraint show the direction of feasibility.

valu€s, hence /(x) can decrease

M i n i m i z e f (*): -Xr - xz Subject to xt + xz < -2 (A)

x , * 2x, <O ( B ) x " x ' ) 0

There is no solution to problem (3) because no feasible region exists for the constraints given.

7.3 NATURAL OCCURRENCE OF LINEAR CONSTRAINTS

Before taking up the strategy to solve linear programming problems numeri- cally, several general comments need to be made about the occurrence of linear inequality constraints in industrial processes. For chemical plants seveial differ- ent kinds of restrictions may be present.

l. Production limitations arise because of equipment throughput restrictions, storage limitations, or market constraints (no additional product can be sold beyond some specific level); see Eqs. (7.12) to (1.14).

2. Raw material limitations occur because of limitations in feedstock supplies;

these supplies often are determined by production levels of other plants with- in the same company. In the refinery example, you could have introduced a constraint on the feedstocks available.

(13)

l.

2.

262 LINEAR PRoGRAMMING AND APPLICATIONS

3. Safety or operability restrictions exist because of limitations on allowable operating temperatures, pressures, and flowrates.

Linear equality constraints exist as well:

Material and energy balances exist because of the basic conservation laws. In many cases the material balance can be expressed as a yield matrix (see Table 7.1) which is linear in form.

Physical property specifications on products must be considered. In refineries we require that the vapor pressure or octane level of fuel products must sat- isfy some specification. For blends of various products, you usually assume that a composite property can be calculated through the averaging of pure component physical properties. For N components with physical property values V,and volume fraction yr,the average property 7 is

, : L,4,,N

Note that the above expression is linear.

EXAMPLE 7.T FORMULATION OF A LINEAR INEQUALITY CONSTRAINT FOR BLENDING

Suppose three intermediates (light naphtha, heavy naphtha, and "catalytic" oil) made in a refinery are to be blended to produce an aviation fuel. The octane number of the fuel must be at least 95. The octane numbers for the three interme- diates are as follows:

Amount blended,

bbl/day Octane no.

Light naphtha Heavy naphtha Catalytic oil

x l 9 2

x2 86

x 3 9 7

Write an inequality constraint for the octane mumber of the aviation fuel assuming a linear mixing rule.

Soltttion. Assume the material balance can be based on conservation of volume (as well as mass). The production rate of aviation gas is xo: xr * x, * x.. The volume-average octane number of the gasoline can be computed as

x t

c 2 1 I x z

( g 6 ; 1 x r

( 9 7 ) > 9 5

x l + x 2 + x 3 x r * x 2 + x 3 x l + x 2 + x 3 (a)

(14)

7.4 THE SIMPLEX METHOD OF SOLVING LINEAR PROGRAMMING PROBLEMS 263

Multiplying Eq. (a) by (x, * x2 + x3) and rearranging we get - 3 " r - 9 x r + 2 x r > 0

This constraint ensures that the octane number specification is satisfied.

Because most LP problems will involve more than two variables, a method more versatile than graphical analysis must be employed to obtain the optimum.

However, the understanding and analysis of an LP problem on a two-dimen- sional plot is very helpful in understanding how you ought to treat a higher dimensional problem. In formulating a numerical approach, we shall use the fact that the optimum for a linear programming problem always lies at a corner of the feasible region. An efficient search technique must be used to progress from one corner to the next; in so doing the objective function is continually im- proved.

7.4 THE SIMPLEX METHOD OF SOLVING LINEAR PROGRAMMING PROBLEMS

In 1947 George Dantzig first advanced a general analytical procedure for han- dling large-dimensional linear programming problems. The iterative procedure employed, called the Simplex algorithm (not to be confused with the simplex method explained in Sec. 6.1.4) seeks to improve the objective function by consi- dering the value of /(x) at one constraint intersection after another (Dantzig, 1963). The iterations are designed so that the value of the objective function is always being improved. We shall describe the steps for solving the general linear programming problem and then examine how the procedure works for a func- tion of two variables, illustrating the operations via a graph.

The general procedure presented requires some understanding of matrix operations. If you are not familiar with these operations, refer to Appendix B for a general summary of the concepts involved. Keep in mind that a properly posed linear programming problem has a convex objective function and concave constraints (that form a convex region), hence it will have a unique solution.

The simplex algorithm entails the definition of additional variables that are introduced into the inequality constraints in the problem. These variables, called surplus or slack uariables depending on the direction of the inequality, convert the inequalities to equality constraints. Given a general inequality constraint

a ; i x i 2 b i (b; > o) (7.16)

it can be converted to an equality constraint by using a surplus variable s, > 0 such that

f

I a l i x i - s i : b :

i = 1

(b)

f

t/-/

(7.17)

(15)

264 LINEAR PROGRAMMING AND APPLTCATIoNs

If the surplus variable is zero, the jth constraint is at its bound (binding). If sj ) 0, the constraint is not binding (is inactive). Sometimes constraints are ex- pressed as

f

I alixi < b1 (b, > 0) In this case a nonnegative ,rt)O r^rr Ole is added, i.e.,

r

I aiixi + sj : bj

t : l

(7.te)

The sample problem to be used for illustration of the Simplex algorithm is M i n i m i z e f :-xr+ x 2

Subject to 2 x , - x " >

- x 1 * 3xr>.

- x l - x z >

X r ) 0 , x r ) 0

The LP problem is shown in Fig. 7.8. The optimum lies at the intersection of constraints B and C (corner 2 of the feasible region). In the steps below we show how the corners of the feasible region are identified and evaluated relative to minimization of the obiective function.

Step 0 Convert all inequality constraints to the form in which the right-hand sides are positive. All three inequality constraints have negative values on the right-hand side so that each constraint must be multiplied by (-l):

1

a

- 4

(7.20a)

(A) (1.20b)

(B) (7.20c)

(c) (7.2od)

( 7 . 1 8 )

(7.2ra) (7.2rb) (7.2rc)

(7.22a) (7.22b) (7.22c) Step 1 Introduce slack/surplus variables and convert the inequality constraints to equality constraints. Let the slack variables be x3, x4, and x5, the inequality constaints, (7.21) become respectively

- 2 x 1 I xr12 x r - 3 x r 1 2 x r * x r 1 4

- 2 x t * x 2 + x 3 : 2 ( A ) x , - 3 x , I x o : 2 ( B ) x r * x 2 + x 5 : 4 ( C )

Note that all variables (including slack variables) must be nonnegative. The op- timization problem (augmented) now requires that you find the values of xt (i: 1,5) that minimize f (x): -xr * xr. This minimization must be performed

(16)

7.4 THE SIMPLEX METHOD OF SOLVING LINEAR PROGRAMMING PROBLEMS 265

f : - 2 ' / - r : - 1

/ r

,/ ,..[ :

Figure 7.8 Representation of LP used to illustrate the Simplex method of solution (arrows point to the direction in which the inequality constraint is satisfied).

subject to five nonnegativity constraints and three equality constraints hence only two degrees of freedom exist.

Step 2 Define a basic solution corresponding to a vertex or corner of the feasible region. Let us define some new variables for the purposes of discussion, using Eqs. (7.3) ar'd (7.4). Let n : total number of variables, including slack variables.

Therefore

n : 2 + 3 : 5 for this example Let m: total number of equations. Then

m : 3 ,

The set of equations (7.22a) to (7.22c) involves three equations with five unknowns, hence it has no unique solution. If the values of two of the x, vari- ables are fixed (for example, set equal to zero), then you have a set of three equations which can be solved to obtain the values of the other three variables.

The process of identifying and specifying the values of a subset of the five vari- ables is called the formulation of the basic solution. A basic solution (also called the basic feasible solution when the m variables are nonnegative) corresponds

- 4

. . /

regron /'

(17)

266 LTNEAR pRocRAMMTNG AND AppLrcATIoNs

to a solution for x obtained by solvingfor m variables in terms of the remaini:-:

(n-m) variables and setting the (n-m) variables equal to zero. The m nonze:. - variables are called the basis or basic uariables. The (n-m) variables are the:

called nonb asic u ariable s.

Since there are two independent variables in this problem, it will be cor- venient to express the basic variables in terms of xt and xr. Figure 7.8 shou:

the feasible region. The vertices or corners of the feasible region correspond te.

basic feasible solutions in which two of the three slack variables are zero (and the rest of the variables are nonzero). For example, the intersection of constraint bounds B and C corresponds to xo: xs:0; however, the intersection of A and B (xr: x+:0) does not correspond to a feasible point (see Fig. 7.8). At the intersection of a constraint with either the xL or xz axes, one slack variable is zero and either x, or x, is zero. For this example problem we have assumed as a starting point that both xt and x, (the nonbasic variables) arezero; the vector of basic variables is (xr, x4,xs). For x, : X2:0, x3, X+, x, and /(x) can be easily calculated by writing the constraints and objective function in the follow- ing form:

x r - 2 x 1 * x z : 2 x + l X 1 - 3 x r : ) x s * x r * x z : 4

f + x L - x 2 : 0

B y i n s p e c t i o l x 3 : 2 , x + : 2 , x s : 2 , a n d f :0. Note that in all the constraints the right-hand sides are positive. This arrangement makes it easy to calculate the values of the basic variables and the objective function when x, and xr (the nonbasic variables) are assumed to be zero. In addition, the objective function is written only in terms of the nonbasic variables which are assumed to be zero initially.

Step 3 Selection of new basic and nonbasic variables. Normally the initial selec- tion of the basic solution does not correspond to the optimum. Therefore it is necessary to change the basic solution in such a way that / is improved.

Examine the coefficients of the terms in / to determine which variable (xt or xr) decreases the value of the objective function more when that variable is increased from zero. This variable will become a new basic variable and an old basic variable will be changed to the nonbasic category. In Eq. (7.23d) if xt is increased from zero, / decreases. If x, increases, / will increase, which is not desirable. As a general rule, it is most advantageous to select as a new basic variable that variable which has the largest positive coefficient in the objective function equation.

Once x, beomes nonzero, it is no longer a nonbasic variable and becomes a basic variable. Simultaneously, one of the existing basic variables needs to be

(7.23a) (7.23b) (7.23c) (7.23d)

(18)

IE SIMPLEX METHOD OF SOLVING LINEAR PROGRAMMING PROBLEMS 267

converted into a nonbasic variable, that is, set equal to zero. which basic vari- able would you select from (x., x+,xs) to be exchanged for xr?

Figure 7.8, in which the feasible region is denoted by the heavy solid lines, shows the limitations placed on x, in changing its value. Note that the con- straint bounds A, B, and C cross the x, axis at different points. Hence each constraint represents a different limit on the potential increase of xr. Because the objective function equation (7.23d) is linear you would like to increase x, as much as possible (in fact you would like to make x, infinite if this were allow- able). However, since there are three inequality constraints in the problem all of which must hold simultaneously, you must identify that constraint which is the limiting one, i.e., the most restrictive. You can see from the graph that the limit- ing constraint corresponds to B(-x, + 3x2> 2).

Keep the nonbasic variable x, at 0 in Eqs. (7.23a) to (7.23c) and exdmine the effect of variations in x, relative to each constraint being satisfied:

(a) As x, is increased, x. must always be positive in order to satisfy F,q.(7.23a), which means the nonnegativity constraint is automatically satisfied. In Fig.

7.8, note that constraint bound ,4 does not affect movement of x, along its axis.

(b) x, can be increased to 2.0 without causing xn to become negative in(7.23b).

This increase corresponds to the intersection of B with the x, axis at x, : 2.0.

(c) x, can be increased to 4.0 without forcing x, to become negative in (7.23c) (up to the intersection of C with the x, axis), but this would violate con- straint B.

The limiting constraint is thus B; therefore we would choose xn, the slack vari- able for constraint B, to be zero, corresponding to the intersection of that con- straint with the x, axis (x, :0). Constraint B is now active (binding).

The limiting value for x1 can be calculated analytically for each equation in the set (7.23) by using the respective coefficient on the right-hand side divided by the corresponding coefficient of xr. The limiting constraint is the one for which the ratio is positive and has the smallest value. In the example, from the set 2l -2,211, and 4lI, you can see that the second constraint B is thus the limiting constraint. The ratio test will henceforth be used to determined which variable to remove from the set of basic variables and make into a nonbasic variable.

Step 4 Transformation of the equations. Next we develop a set of equations in a format analogous to (7.23) with the nonbasic variables now x2 : x+ : 0 and the basic variable vector being (xr, xg, xs). This transformation can be accom- plished by substituting for x, as functions of x, and xn in all the equations (using the limiting constraint identified in step 3)

x r : 2 - x a * 3 x , (7.24a)

(19)

Note that the value of the objective function has decreased from f : O to f : -2, which is desirable for a minimization problem. In the format used pre- viously equations (7.24) are

268 LINEAR PRoGRAMMING AND APPLICATIoNS

By substitution of x,

x t : 2 * 2 x t - x r : 6 - 2 x o * 5 x , x s : 4 - X 1 - x 2 : 2 + x n - 4 x ,

f : x r + x 2 : - 2 + x 4 - 2 x 2

x 3 + 2 x 4 - 5 x r : 6 x r * x 4 - 3 x r : ) x 5 - x a i 4 x t : )

f - x a * 2 x r : - )

N

[1

l1

- 3- 1II 0001 0001

(7.24b ' (7.24c t (7.2M1

(7.25a) (7.2sb) (7.25c) (7.2sd)

(1.26)

(7.27) Rather than use algebraic substitution, Gauss-Jordan (or Gaussian) eli- mination can be used to systematically transform the equations from one basic solution to the next (refer to Appendix B). Let us write the original set of equa- tions and objective function (7.23) in matrix notation Ax : b (B designates basic variables and N nonbasic variables):

N B B B l l 0 0 0 l

- 3 0 I 0 0 l

I o o I o l

- r 0 0 0 t l

t 1

^ 2

x 3

x 5

{ [il

fl- o'""' ,"'"

To use Gauss-Jordan elimination, the matrix A is augmented with the constant vector on the right-hand side of (7.26):

0 0 0 0 1 0 0 1

pivot column

In matrix (7.27) we have identified a piuot column and a piuot row. The pivot column is the column of coefficients corresponding to the new basic variable selected by analysis of the coefficients in the terms of /. The pivot row is the row of coefficients corresponding to the coefficients in the limiting constraint.

The piuot element is the element at the intersection of the pivot row and the pivot column (circled in the matrix).

To exchange the basic variable xn for xr, the first column is transformed by elementary row operations (refer to Appendix B) to [0 I 0 0] r, and as a result of the operations the fourth column contains some additional nonzero

(20)

7.4 THE SIMPLEX METHOD OF SOLVING LINEAR PROCRAMMING PROBLEMS 269

elements. Elementary row operations are used to obtain zeros in elements crr, a31, &frd aa1, &r:rd azt : I of the transformed matrix with the result

l-o

n r : l;

L0

Multiplication of Arx yields algebraic substitution.

To help interpret the employed;

0 I 0 0

- 5 - 3

@ 2

1

1 0 0 0

0 0

I 0

0 6

o 2 O 2 * -

1 - 2

(7.2e)

The variables listed on the left side identify the basic variables. We shall use this format in subsequent calculations; more elaborate tableaus can be constructed (Kim, 1971; Cooper and Steinberg,1974; Reklaitis et al., 1983).

Step 5 Iterative improvement in the objective function. To continue with the Simplex procedure, we examine the objective function equation again. Note that the term 2x, in (7.25d) indicates that an increase in x, will yield an improve- ment (a decrease) in the objective function. The largest coefficient in the bottom row of the tableau is + 2 (the pivot column is indicated by an arrow). However, as before, you must determine the limiting constraint. The ratios of the b column to the x, column (-615, -213, 214) indicate that the third constraint gives the smallest positive ratio. xr, the slack variable for the third constraint, will now be set equal to zero. Eliminate x, from the nonbasic variables and replace it with xs, to obtain the largest allowable increase in ;f.

Next, in tableau (7.29) the x2 column (pivot column) must become a unit vector (x, is a new basic variable), and the column corresponding to xs will not be a unit vector. The pivot row is the one corresponding to xs in the basic variable column (marked with an arrow). The pivot element is circled in (7.29).

Using Gauss-Jordan elimination, the new tableau is

0 I 0 0

0 0 I 0

1 I

0 0 0

0.7s r.2s 0.25 0.7s -0.2s 0.2s

- 0.5 - 0.5 - 5 1 2 0 0 6 . l

- 3 0 I 0 0 2 l

4 o - 1 1 o ' l

Q ' 2 8 )

2 O - l 0 l - 2 1

the same set of equations (7.24) derived earlier by

matrix after it is transformed. a "tableau" can be

x 5 x4 x 3 x2

x l

x 3

x l

x s

x 5 x 3 X4

x 1 X 2

x 3 x 1

0 8 . 5 0 3 . 5

0 0.s t - 3

x 2

(7.30)

(21)

270 LTNEAR pRocRAMMING AND AppLIcATIoNs

The resulting set of equations is therefore

The objective function has decreased to -3 from the value of -2 on the previ- ous iteration.

At this stage we examine the equation for /. Note that increases in xn or x, do not have a beneficial effect on the objective function. Therefore the objec- tive function cannot be increased any further, and the optimum has been found.

R e a d i n g fr o m ( 7 . 3 1 ) , w e h a v e x g : 8 . 5 , X r : 3 . 5 , x z : 0 . 5 ( t h e f i r s t t h r e e e l e - ments of the b columr), x+:0, xs :0 (nonbasics), and f : -3 (the last ele- ment of the b column). In the tableau the optimum solution has been reached if all coefficients in the objective function row (except for / and b) are negative;

then the procedure is terminated.

Other LP Formulations

A number of textbooks (e.9., Kim (1971) and Cooper and Steinberg (1974))

formulate the LP as a maximization problem (rather than minimization). You should be careful in using transformation rules formulated for a different objec- tive function or constraint convention, since a number of variations exist in the literature.

7.5 STANDARD LP FORM

In the five steps above we have by way of motivation illustrated the procedure for a simple two-dimensional problem which could also be solved graphically.

We now focus on the general LP format and procedure in which many variables and constraints occur in the problem statement, namely

xt + O.75xn -f I.25xt : 8.5 x , + . O . 2 5 x n * 0 . 7 5 x r : 3 . 5 x r - 0 . 2 5 x n 1 0 . 2 5 x t : 0 . 5 f - 0 . 5 x n - 0 . 5 x t : - 3 . 0

M i n i m i z e : f(x): crx, I crx2* "'* cnxn S u b j e c t t o : a r r x , I a r r x 2 * . . . * & r n x o : f i ,

a r r x , * a 2 2 x 2 I . . , * x r n x r : S , :

a - r x 1 * c l ^ 2 x 2 I . . , * a ^ r x o : [ ^ x , ) 0 i : l , n b i > 0 i : l , m

(7.3ra) (7.3rb) (7.3rc) (7.3rd)

(7.32) (7.33)

(22)

7.5 STANDARD LP FORM 27I

In more compact notation:

min f : c'x

s.t. Ax : b (7.34)

x > 0 , b > 0

Tableau (7.30) illustrated the standord form which is used for the con- straints in the Simplex solution procedure for a linear programming problem with m:2 and n : 5. In general, the canonical form for a system of n variables and m constraints is shown in Table 7.2: note that there arc m basic variables and (n-m) nonbasic variables. Because the independent (nonbasic) variables are zero, the dependent (basic) variables can be calculated directly as x,: b.

(i : l, . . . , m). If any b, is zero, this result indicates that some of the constraints are dependent.

You should recognize that in order to write an LP in the form of Table 7.2, you must express the objective function in terms of the nonbasic variables (x^*r,xm+2t...,xn).This functional dependence rarely occurs in the original problem statement, thus procedures must be developed to obtain the first basic feasible solution and to obtain the tableau in standard (or canonical) form. Sec- tion 7.6 discusses several methods for obtaining a basic solution.

With n variables and m constraints, there are a finite number of possible basic solutions that can be obtained for the LP problem, a number ry' which is given by

, ( r \ n t '

:

\ ^ ) : m \ n - m ) t

As long as n and m arc rclatively small, only a few possible solutions need be evaluated. The Simplex procedure attempts to make the search for the optimum an efficient one, but it does not necessarily take the shortest route to the opti- mum. Based on practical experience, the number of iterations to reach an opti- mal solution ranges generally between m and 3rn, depending more heavily on the number of constraints than on the number of variables (Reklaitis, et al., 1983).

Table 7.2 Canonical representation with basic variables

x L t x 2 r . . . , x ^

Dependent (basic)

variables Independent (nonbasic) variables Constants

x 1 + a r , n + r x m + 1 + a 1 , m + 2 x m + 2 * ' . . I a r r x n : b , x 2 + a 2 , i l + t x m + r + a 2 , m + 2 x n + 2 - 1 " ' I a " n x n : $ ,

X ^ I o r , ^ 1 1 x ^ + | + a^.^+zxn t z * "' + o^,rr, : 6^

(23)

272 LINEAR PROGRAMMING AND APPLICATIONs

EXAMPLE 7.2 FORMULATION OF AN LP PROBLEM IN STANDARD FORM

Solve the refinery blending problem given in Eqs. (7.11) to (7.15) using the Simplex method. First formulate the problem as a minimization problem.

Solution, The blending problem stated in a minimization format is Minimize f : -8.lxt -10.8x,

Subjectto -0.80x, -D.Mx, > -24,000 - 0 . 0 5 x r - 0 . 1 0 x r > - 2 0 0 0 - 0 . 1 0 x , - 0 . 3 6 x r > - 6 0 0 0 Step 0. Multiply Eqs. (7.35b, c, d) bv (-1).

Step 1. Introduce slack variables x31 x4t and x, into (7.35b) to (7.35d), respec- tively, and multiply each constraint equation bV (-1) so that the constants on the right-hand side are positive:

(7.35a) (7.3sb) (7.35c) (7.3sd)

(7.36a) (7.36b) (7.36c) (7.36d) 0.80xt * 0.44xt * xz :24,000

0.05x, * 0.10x, * x+:20O0 0.10xt * 0.36x't * xs : 6000 f + 8 . l x r * 1 0 . 8 x , : 0

Step 2. If x, and x, are selected as the nonbasic variables and (x., xo, xr) are the basic variables, then the LP is already in standard form and you can proceed with the tableau calculations. The initial tableau is

0.44 0 . 1 0

1

0 0 0

0 1 0 0

0 0 I 0

0 0 0 1

24,W0 2,000 6,000

0 -

(7.37) 10.80

I

Step 3. Note that increases in both xr and x, will improve the objective func- tion. You should select the largest positive coefficient for the pivot column and use the ratio test to find the pivot row. Can you show that the arrows correctly mark the pivot row and pivot column in (7.37)?

Step 4/Step 5. Successive transformations are listed below:

x3 x "

xs 0.80 0.05 0 . 1 0 8 . 1 0

x3 x4 x2

0.68

@0.28 5 . 1

t

0 0 1 0

I

0 0 0

o -t.22 1 -0.28

o 2.78

0 - 30.00

0 16,667

0 333.3

o 16,667 - (7'38) 1 - 180,000

(24)

x 5 x4

x2 x 3 x 1

x3 x l x2

0 0 I 0

I

0 0 0

0 0 0 I - 30.5

45.0 - 1 2 . 5 - r ? q 5

x,

6.2s 33.75

1

x 5

6,500 15,0(X) 12,500 -2s6,500

b

(7.3e)

(7.40)

x 3 x2 x.l

x 5 x 1 x2

0 I 0 0

0 0 . 1 4

o 1.72

I - 0 . 8 6 0 -4.66

- 4 . 2 1 -7.s9 13.79 -87.52

1 0 896.5

0 0 26,207

0 0 6,897

0 1 -286,765

we terminate with (7.,()) because no x, coefficients in / are positive (in the bottom row). This example illustrates that the Simplex procedure does not necessarily take the shortest route to the optimum. If you had the foresight to select x, for a basis variable at the first iteration, you would reach the optimum after two cycles of the Simplex procedure. After the value obtained in the first iteration, / would increase to $243,000, which is an improvement over the value obtained in the first iteration using the conventional rules. It is possible to put a provision in the transformation rules to perform more than one set of ratio tests (evaluate more than one column to find the limiting constraint which allows the largest increase in/). Use of such a strategy would save eflort in transforming the arrays for this particular example, but it is difficult to predict whether this approach would save computation time on other problems.

7.6 OBTAINING A FIRST FEASIBLE SOLUTION

In many LP problems the choice of a first basic solution which satisfies all the constraints is not obvious. However, a basic solution can be obtained via a technique which utilizes a special type of variable called artificial uariable. There- after, the Simplex procedure can be applied. Consider the problem:

Minimize

"f(x) : x, * 2x, Subject to 3x1 * 4xr> 5

x r * x r 1 4

(7.4r)

Introduction of slack and surplus variables xo and x, changes the constraints to 3 x t l 4 x r - x r : 5

x r + x 2 l x n : 4

(7.42a) (7.42b) Suppose you tried xt: xz:0 for a basic solution; this requires xr : -5, vio- lating the nonnegativity restriction (however, X+: 4, which is satisfactory).

?.6 oBTATNTNG A FrRsr FEAsTBLE soLUTroN 273

6;i\v

-12.50

(25)

274 LINEAR PROGRAMMING AND APPLIcATIoNS

Therefore the origin is not in the feasible region and you must find a different starting point. Define an artificial slack variable, x5, ?nd introduce it into (7.42a) such that

3 x 1 l 4 x t - x z * x s : 5 (7.43)

Now x, - xz:0 is allowable, because positive values of x. and xs can satisfy Eq.Q.ar. We next must drive the value of x, to zero, by adding a penalty function (see Sec. 8.5) to the original objective function

f : f + t t ' t * t (7.44)

For M large, x, will hopefully approach zero in the minimization of f via the Simplex method. This technique, call the "Big M" method (Murty, 1983) allows you to initiate the minimization of f at a starting point outside the feasible region.

In practice, the "Big M" method suffers from several practical difficulties, especially for problems with many variables. Choice of the correct value of M is not at all clear. If the LP solution terminates with some artificial variables non- zero, is this because there is no feasible solution or because M is too small? If M is chosen too large, there may be problems with precision of computer arithme- tic; round-off error may lead to a nonoptimal solution. Below we discuss an alternative approach, referred to as "Phase l-Phase II."

Murty (1983) and Schrage (1983) have discussed the solution of an LP problem starting from a nonfeasible starting point utilizing these two phases. To drive the artificial variables to zero in an LP problem, phase I is carried out in which the sum of the artificial variables is minimized to obtain a basic feasible solution, or demonstrate that no feasible solution exists. In phase II, the Simplex procedure is executed starting with feasible solution obtained in phase I.

The phase I procedure is summarized below:

1. Change the signs of any equations as needed (by multiplying by - 1) so that the b's (the right-hand side coefficients) are all positive.

2. Convert the system of inequality constraints into a set of equalities as ex- plained before using slack andlor surplus variables.

3. Augment the set of equations by one artificial variable for each equation to get a new standard form. After step 3, the set of constraints will appear as follows:

a 1 1 x 1 * artx2 *...1elrxn - f x r + r

a r r x l * a22x2 + ... -l e2nxn - l x r * z

a ^ r x 1 I e^rx2 -l ... * e^rxn

A solution of (7.45) is:

(a) The basic variables are: xn+i : br, i : I, ..., m ( b ) The nonbasic v a r i a b l e s a r e i x i : 0 , j : 1 , . . . , f l

- b L

: b .

(7.4s) :

+ x r + ^ : b m

(26)

SOLUTION 275

4. Next proceed to drive all the artificial variables to zero by minimizing their sum, by using the following objective function.

w : X n + r * x r * z + . . . + x r + ^ (7.46) To minimize w using the Simplex method, you need to express w in terms of x, to xn instead of xn*, to x,*^. To accomplish this step, subtract the first equation in the set (7.45) from the equation for w, Eq. (7.46), repeat for the second equation, so as to set up the following standard form:

a r r x , I a r r x 2 l ' . . * a l n x n * X n * r . : bt

a)rx, -l Q^rx2 * "' I ajnxn -l xr+-: b^ Q '47)

(7.48)

Now use the Simplex procedure to minimize w.

5. Terminate phase L If the minimum of w is nonzero, then there is no solution to the problem. An example of this outcome might be improper specification of the constraints so that the feasible region is not convex, or does not exist.

If the minimum w is reduced to zero, then all the artificial variables have been reduced to 0 because w is the sum of nonnegative variables only.

You can now delete the artificial variables from further consideration because you have found a feasible solution for the original problem. The basis con- tains no artificial variable (except, perhaps, some with zero value only). If the artificial variables (at 0 value) are found to be basic variables at the end of the phase I calculations, it means that the original system of equations con- tained dependent equations (Schrage, 1983 ; Luenber ger, 197 3).

After completing the phase I procedure to generate an initial feasible solution, you proceed with phase Il-the solution of the original LP problem using the original objective function. You

Drop all the variables with di.O from the tableau (generally this in- cludes all of the artificial variables)

Retain all the variables with d, > 0

Introduce the original objective function in standard form using the feasi- ble solution from phase I.

For the problem considered earlier, Eq. (7.41), first add artificial variables to both constraints as follows:

3 x r * 4 x 2 - x : * x s : 5 x 7 + x z + x 4 + x a : 4

, * (,i o,,)*,_, ( ,i- o,')*,+ "' + (,i ,,)-, : (,i,r,)

d1 d2 dn

(a)

(b) (c)

(7.4e)

Riferimenti

Documenti correlati

An extremely naïve assumption has crumbled before our eyes: some used to believe science communication was a transfer of information between those who know (scientists) and those

La scienza – e la tecnologia che della scienza è, insieme, figlia e madre – sono sempre più elementi essenziali della nostra vita, in ogni e ciascuna delle sue

The 3 rd i-TREC 2018 was proudly organized by the Tropical Renewable Energy Center – Faculty of Engineering Universitas Indonesia.. The 3 rd i-TREC 2018, which was held in

Histology showed an ulcerative and infiltrative adenosquamous carcinoma of the esophagogastric junction, classified as type 3 according to the guidelines for clinical and

Subject to applicable law, Company and its Affiliates may, but shall not be required to, provide to you, a User, an insurance company and/or relevant authorities and/or

Elastomeric thermoplastic block copolymers, especially poly(styrene-b-butadiene-b-styrene) (SBS) are the most commonly used polymers. The rigid styrenic domains,

Separately for phone rate and month, analyze the (i) total income, (ii) the percentage of income with respect to the total revenue considering all the phone rates, (iii)

We need different methods for models with integer or binary variables..!. n ⇒