4.2 Revised Simplex Method 179subject 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≥ 0As 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
∑nj= 1Pjxj+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