Principles of Mathematics in Operations Research

110 8 Linear Programming

"10

0 1

00

3-2

2-1

-4 3

6"

6

-18

X

y

2i y\x z 2 \\RHS-

-III 2

III ^

§0|0 -10

77ms, x* = 2 = y* => 2* 10.

Remark 8.2.2 AZZ i/ie pwo£ operation can be handled by multiplying the in-

verse of the following elementary matrix.

E =

1

0

0.

0.

\vi :0.

0 :. :.

liwjio.

. 0:. :1
.:. : 1

.:. : 0

• Q'-vm:
  . 0
  . 0

0

1_

<F> E~

— V\

Vl

1_

Vl

Thus, the pivot operation is

[^B^NWB-H} —> [E-^1 I\E-^1 B-^1 N\\E-^1 B-Ib].

New basis is BE (B except the Ith column is replaced byu = Ne) and basis

inverse is (BE)"^1 — E~^1 B~^1. This is called product form of the inverse.

Thus, if we store E"^1 's then we can implement the simplex method on a

simplex tableau.

8.3 Revised Simplex Method

Let us investigate what calculations are really necessary in the simplex
method. Each iteration exchanges a column of N with a column of B, and
one has to decide which columns to choose, beginning with a basis matrix B
and the current solution XB = B~lb.

SI. Compute row vector A = cjgB x and then cL — XN.