The Simplex method

The fundamental theorem of linear programmingfundamental theorem of linear programming gives us an algorithm for quickly finding an optimal solution. One way is to check all possible choices of basic indices, but this quickly becomes slow. The idea with the Simplex method is to repeatedly walk from a basic solution to a neighbouring one with lower cost, until this cannot be done.

We assume that we have a basic feasible solution and we wish to move to one with lower cost. "Moving" away from the basic feasible solution means increasing a non-basic variable from zero. Let be the current solution and be the current cost. We must at all times have

We then have For the cost, we have

This gives us and Since the non-basic variables must be increased from zero, it is possible to decrease the cost if and only if there is some negative component of .

If , then we want to swap some element of with some element of . In other words, we want to increase one component of from precisely until one component of becomes . The component of to increase is just any component with , since this gives a reduced cost. Recall that we have In particular, when we choose to increase and leave the rest of zero we have This means that if at least one element of is positive, some component in will become zero when we increase . Otherwise, we can increase indefinitely and the objective value can thus become arbitrarily small, so then there is no finite optimum. From now on, we assume there is a finite optimum. Then we of course want to increase as little as possible, i.e. only such that one component in is zeroed. We thus choose With the Simplex method we always want to move to the corner that gives the maximally reduced cost, i.e. we choose such that is maximized. This can however be computationally inefficient since we need to compute each time, so instead we sometimes greedily choose the minimum component of .