Simplex method

Consider the Linear program: ” Minimize over , subject to ” where is an identity matrix is an matrix and , are vectors and

Consider a vector It has a Basis The corresponding columns in is the matrix Thus is a Basic Solution and so is a Basic Feasible Solution.

Now apply the Optimality condition in Linear Programming which simplifies to: is optimal if and only if

Otherwise, find an index such that is negative (usually the most negative one). Then find s.t. is the smallest possible positive value. If they are all negative the problem is unbounded.

Now pivot around , i.e. use row operations to make the -th column be . Note that these operations will preserve . Now by swapping columns we have arrived at the same form as the starting problem. Repeat these steps until done.

Two-phase algorithm

If our initial problem is not of the desired form, we do two phases, as follows.

Phase 1

Suppose we are given the problem of minimizing s.t. and . We can WLOG take . First consider the problem of minimizing s.t. , with . Now this is of the form , so we can apply the Simplex method. This has to terminate at a solution if the original problem is feasible. But now is a BFS of the original problem. Now, given that we also tracked the function in this algorithm, we are sure to have a good setup for Phase 2.

Phase 2

We can remove from our consideration and apply the Simplex method again, now only looking at .