Engineering Optimization: Theory and Practice, Fourth Edition

184 Linear Programming II: Additional Topics and Extensions

Table 4.2 Tableau at the Beginning of Cycle 0

Columns of the canonical form Value of the
Basic variables xn+ 1 xn+ 2 · · · xn+r · · · xn+m −f −w basic variable xsa

xn+ 1 1 b 1

xn+ 2 1 b 2

..

.

..

.

xn+r 1 br

..

.

..

.

xn+m 1 bm

←−−−−−−Inverse of the basis←−−−−−−

−f 0 0 · · · 0 · · · 0 1 0

−w 0 0 · · · 0 · · · 0 1 −w 0 = −

∑m

i= 1

bi

aThis column is blank at the beginning of cycle 0 and filled up only at the end of cycle 0.

seen to be an identity matrix in Table 4.2. The rows corresponding to−f and

−win Table 4.2 give the negative of simplex multipliersπiandσi( i= 1 tom),

respectively. These are also zero sincecB=dB= 0 and hence

πT=cTBB−^1 = 0

σT=dTBB−^1 = 0

In general, at the start of some cyclek(k=0 to start with) we open a tableau

similar to Table 4.2, as shown in Table 4.4. This can also be interpreted as

composed of the inverse of the current basis,B−^1 =[βij], two rows for the

simplex multipliersπiandσi, a column for the values of the basic variables in

the basic solution, and a column for the variablexs. At the start of any cycle,

allentries in the tableau, except the last column, are known.

3.The values of the relative cost factorsdj(for phase I) orcj(for phase II) are

computed as

dj=dj−σTAj

cj=cj−πTAj

and entered in a tableau form as shown in Table 4.3. For cycle 0,σT= 0 and

hencedj≡dj.

4 .If the current cycle corresponds to phase I, find whether alldj≥. If all 0

dj≥ 0 andw 0 > 0 , there is no feasible solution to the linear programming

problem, so the process is terminated. If alldj≥ and 0 w 0 = 0,the current basic

solution is a basic feasible solution to the linear programming problem and hence

phase II is started by (a) dropping all variablesxj withdj> 0 , (b) dropping

the wrow of the tableau, and (c) restarting the cycle (step 3) using phase

II rules.