Principles of Mathematics in Operations Research

108 8 Linear Programming

Adding the cost row

I \B-lN\\B-lb

-N^0

B-lN B~xb

Oc^-c^B-^ll-cSB-^

The last result is the complete tableau. It contains the solution B~^1 b, the

crucial vector CNT — cBTB~^1 N and the current objective function value

cBTB~^1 b with a superfluous minus sign indicating that our problem is mini-

mization. The simplex tableau also contains reduced coefficient matrix B~lN

that is used in the minimum ratio. After determining the entering variable

xe, we examine the positive entries in the corresponding column of B~XN,

(v = B~lu = B~^1 Ne) and a is determined by taking the ratio of tB-iNl\.

for all positive Vj's.

If the smallest ratio occurs in Ith component, then the Ith column of B

should be replaced by u. The Ith element of (B~lNe)i = V[ is distinguished

as pivot element.

It is not necessary to return the starting tableau, exchange two columns

and start again. Instead we can continue with the current tableau. Without

loss of generality, we may assume that the first row corresponds to the leaving

variable, that is the pivot element is vi.

1 :0---0

0

:0:0---0

V2

B^N: :B-XN

• • :cR CT BV. •

(B-'bh

B~lb

-cTBB~lb.
The first step in the pivot operation is to divide the leaving variable's row
by the pivot element to create 1 in the pivot entry. Then, we have