Engineering Optimization: Theory and Practice, Fourth Edition

(Martin Jones) #1
4.2 Revised Simplex Method 179

subject to
AX=A 1 x 1 +A 2 x 2 + · · · +Anxn=b (4.4)

X
n× 1

≥ 0

n× 1

(4.5)

where thejth column of the coefficient matrixAis given by


Aj
m× 1

=










a 1 j
a 2 j
..
.
amj










Assuming that the linear programming problem has a solution, let


B=[Aj 1 Aj 2 · · ·Aj m]

be a basis matrix with


XB

m× 1

=










xj 1
xj 2
..
.
xj m










and cB
m× 1

=










cj 1
cj 2
..
.
cj m










representing the corresponding vectors of basic variables and cost coefficients, respec-
tively. IfXBis feasible, we have


XB=B−^1 b=b≥ 0

As in the regular simplex method, the objective function is included as the (m+1)th
equation and−fis treated as a permanent basic variable. The augmented system can
be written as


∑n

j= 1

Pjxj+Pn+ 1 ( −f)=q (4.6)

where


Pj=














a 1 j
a 2 j
..
.
amj
cj














,j=1 ton, Pn+ 1 =














0

0

..

.

0

1














and q=














b 1
b 2
..
.
bm
0














SinceBis a feasible basis for the system of Eqs. (4.4), the matrixDdefined by


D

m+ 1 ×m+ 1

=[Pj 1 Pj 2 · · ·Pj mPn+ 1 ]=

[

B 0

cTB 1

]

will be a feasible basis for the augmented system of Eqs. (4.6). The inverse ofDcan
be found to be


D−^1 =

[

B−^10

−cTBB−^11

]
Free download pdf