Engineering Optimization: Theory and Practice, Fourth Edition

178 Linear Programming II: Additional Topics and Extensions

1.The relative cost coefficientscjto compute†

cs= inm (cj) (4.1)

csdetermines the variablexsthat has to be brought into the basis in the next

iteration.

2.By assuming thatcs< , the elements of the updated column 0

As=











a 1 s

a 2 s

..

.

ams











and the values of the basic variables

XB=











b 1

b 2

..

.

bm











have to be calculated. With this information, the variablexr that has to be

removed from the basis is found by computing the quantity

br

ars

= min

ais> 0

{

bi

ais

}

(4.2)

and a pivot operation is performed onars. Thus only one nonbasic columnAsof

the current tableau is useful in findingxr. Since most of the linear programming

problemsinvolve many more variables (columns) than constraints (rows), con-

siderable effort and storage is wasted in dealing with theAjfor j=s.Hence

it would be more efficient if we can generate the modified cost coefficientscj

and the columnAs, from the original problem data itself. The revised simplex

methodis used for this purpose; it makes use of the inverse of the current basis

matrix in generating the required quantities.

Theoretical Development. Although the revised simplex method is applicable for

both phase I and phase II computations, the method is initially developed by considering

linear programming in phase II for simplicity. Later, a step-by-step procedure is given

to solve the general linear programming problem involving both phases I and II.

Let the given linear programming problem (phase II) be written in column

form as

Minimize

f (X)=c 1 x 1 +c 2 x 2 + · · · +cnxn (4.3)

†The modified values ofbi, aij, andcjare denoted by overbars in this chapter (they were denoted by primes

in Chapter 3).