180 Linear Programming II: Additional Topics and Extensions

Definition. The row vector

cTBB−^1 =πT=











π 1

π 2

..

.

πm











T

(4.7)

is called the vector of simplex multipliers relative to thefequation. If the computations

correspond to phase I, two vectors of simplex multipliers, one relative to thefequation,

and the other relative to thewequation are to be defined as

πT=cTBB−^1 =











π 1

π 2

..

.

πm











T

σT=dTBB−^1 =











σ 1

σ 2

..

.

σm











T

By premultiplying each column of Eq. (4.6) byD−^1 , we obtain the following canonical

system of equations†:

xj 1 b 1

xj 2 b 2

..

. +

∑

j onbasicn

Ajxj = ...

xj m bm

−f +

∑

j onbasicn

cjxj = −f 0

where

{

Aj

cj

}

=D−^1 Pj=

[

B−^10

−πT 1

]{

Aj

cj

}

(4.8)

From Eq. (4.8), the updated columnAjcan be identified as

Aj=B−^1 Aj (4.9)

†Premultiplication ofPjxjbyD− (^1) gives
D−^1 Pjxj=
[
B−^10
−πT 1
]{
Aj
cj
}
xj

{
B−^1 Aj
−πTAj+cj
}
xj=
{
xj ifxjis a basic variable
D−^1 Pjxj ifxjis not a basic variable