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