Principles of Mathematics in Operations Research

8.1 The Simplex Method 105

Definition 8.1.3 The extreme points of the feasible set are exactly the basic
feasible solutions of Ax = b. A solution is basic when n of its m+n components
are zero, and is feasible when it satisfies x > 6. Phase I of the simplex method
finds one basic feasible solution, and Phase II moves step by step to the optimal
one.

If we are already at a basic feasible solution x, and for convenience we

reorder its components so that the n zeros correspond to free variables.

XB

xN = <

,A = [B,N], (cB,cN)

Min z =(cB',cJf)

s.t.

[B\N]

xB

XN -

XB

XN = 6

= b

<=>

XB

XN = '

Min z —CQXB + CNXN

s.t.

BxB + NxN = b

XB,XN >0

>e.

Let us take the constraints

BXB+NXN =bo Bxb = b-NxN «• xB - B~^1 [b-NxN] - B~^1 b-B~^1 NxN-

Now plug XB in the objective function

z = CTBXB + CNXN = c%[B~^1 b - B_1NXN] + CNXN

= cTBB~lb + {cTN - cBB-lN)xN.

If we let XN = 0, then xB = B~lb > 6 => z — cB'B~^1 b.

Proposition 8.1.4 (Optimality Condition) If the vector (cN - cBB~^1 N)
is nonnegative, then no reduction in z can be achieved. The current extreme
point (XB = B~^1 b,XN = 0) is optimal and the minimum objective function
value is CBB~^1 b.

Assume that the optimality condition fails, the usual greedy strategy is to
choose the most negative component of CJV — CBB~^1 N, known as Dantzig's
rule. Thus, we have determined which component will move from free to basic,
called as entering variable xe. We have to decide which basic component is
to become free, called as leaving variable, x. Let Ne be the column of N
corresponding to xe. xB = B~lb- B~^1 Nexe. If we increase xe from 0, some
entries of XB may begin to decrease, and we reach a a neighboring extreme
point when a component of XB reaches 0. It is the component corresponding
to x. At this extreme point, we have reached a new x which is both feasible