The Starting Point of the Simplex

The simplex is a method used in linear programming problems to obtain solutions to linear programming problems. As a recap a linear programming problem involves determining the maximum or minimum value of an objective function given a set of constraints. The constraints would form the boundary of a polyhedron. Under the assumptions of the constraint set being convex any vertex in the polyhedron would yield an extreme value of the objective function either maximum or minimum.

Due to the feasible boundary being convex a vertex will yield a local minimum which is also the global minimum. Similarly in a concave function the local maximum will also be the global maximum due to the function being concave. To recap a convex function is one where a point on the function always falls inside the line connected between any two points on the boundary of the function.

The Simplex method starts of by setting the value of the non-basic variables to 0 and then proceeds to find out the optimum value of the objective function by identifying directions of steepest gain or reduction of the value of the objective function. But the simplex assumes a starting point where the non-basic variables are set to 0 each. The optimum value of the objective function is found after several iterations where the algorithm chooses a vertex with maximum gain of the absolute value of the objective function. The Simplex method is efficient as it does not enumerate all possible solutions, but converges to the actual value in a fewer number of searches.

Here if there are 4 or 5 vertices of the polyhedron and the optimum solution is found after 5 iterations (for example) then one should understand that there is an inherent assumption that the first feasible solution is determined by setting the non-basic variables to 0 which is the (0,0) coordinate of the polyhedron.

Here it is be noted that by fixing the non-basic variables to 0 as the starting point of the simplex one may assume a starting point which is far away from the optimum. So the Simplex can be revised to make an intelligent guesstimate about the whereabouts of where the iterations need to begin. The no of runs of the Simplex is approximately proportional to the power of the number of constraints. One can apply some probabilistic methods and derive heuristic rules to make the Simplex begin at a point near the optimum.