Principles of Mathematics in Operations Research

106 8 Linear Programming

and basic: it is feasible because x > 0, it is basic since we again have n zero

components. xe is gone from zero to a, replaces xi which is dropped to zero.

The other components of XB might have changed their values, but remain

positive.

Proposition 8.1.5 (Min Ratio) Suppose u = Ne, then the value of' xe will

be:

. {B-lb)j (B^b),
a = min —r^1 - = , ,
Xj-.basic (B~lU)j (B LU)l
and the objective function will decrease to cBB~^1 b — aB~^1 u.

Remark 8.1.6 (Unboundedness) The minimum is taken only over posi-
tive components of B~^1 u, since negative entries will increase XB and zero
entries keeps XB as their previous values. If there are no positive components,
then the next extreme point is infinitely far away, then the cost can be reduced
forever; z — — oo/ In this case we term the optimization problem as unbounded.

Remark 8.1.7 (Degeneracy) Suppose that more thann of the variables are
zero or two different components if the minimum ratio formula give the same
minimum ratio. We can choose either one of them to be made free, but the
other will still be in the basis at zero level. Thus, the new extreme point will
have (n + 1) zero components. Geometrically, there is an extra supporting
plane at the extreme point. In degeneracy, there is the possibility of cycling
forever around the same set of extreme points without moving toward x*,
the optimal solution. In general, one may assume nondegeneracy hypothesis
{xB=B~lb>6).

Example 8.1.8 Assume that we are at the extreme point V in Figure 8.1,

corresponding to the following basic feasible solution:

XB

[xN\

"6"

6

U

0_

' Zl'

y

X

.z2.

A = [B\N] =

zi y

-1 2

0 1

x z 2

1 0

2-l_

CN

rT __ (rT\T\

c — \CB\CN)

cTBB-lN = [2 0] - [0 3]

-12

01

-l

zi y X Z2

0 3

1 0

2-1

2 0

-12

01

10'

01 —>

[1 -2

0 1

-10]

01 —>

[10

01

-12]

01

^B-^1 ^

-12

01