# IE417 Lecture 24

7

Almost Complementary Basic Feasible Solutions

Iw Mz

z =q

w, z, z

≥0

•

A triplet w, z, z ) is called a almost complementary basic feasible solution (ACBFS) if

–

w, z, z ) is a basic feasible solution to

–

There is exactly complementary pair w

_{s}, z_{s}) such that neither w_{s }nor z_{s }is basic.–

z is basic.

•

All we need is pivot z out of the basis, as in Phase I of the two-phase

simplex algorithm.