Simplex Algorithm (discussion continued from previous writeup)

We saw that the Simplex can be started at the origin and we know what to do if we are at the origin. But if our current vertex u is elsewhere. The trick is to transform u into the origin.And we shift the entire co-ordinate system from x1, x2, .. xn to  the local view from u and denoted by y1, y2 … yn to the n hyperplanes that define and enclose u. Specifically, if one of these enclosing inequalities is a.xi <= b, then the distance from a point x to the particular “wall” is yi = bi – ai.x

The n equations  of this type, one per wall, defines the yi’s as linear functions of xi’s and this relationship can be inverted to express the xi’s as a linear function of the yis. Thus we can represent the entire LP in terms of they y’s.

By shifting the co-ordinate system we don’t change anything from the earlier optimal value but the objective function does change. The transformations include:

1)   the inequalities y >= 0, which are simply the transformed versions of the inequalities defining u

2)   u itself is now the origin

3)   The cost function becomes max cu + transformed-cost-vector. y

The simplex algorithm is now fully defined. It moves from vertex to neighbouring vertex stopping when the objective function is locally optimal. At this point, the coordiantes of the local cost vector are all zero or negative. A vertex with this property must also be globally optimal.