Introduction to Simplex Method

We must concentrate our efforts on developing a procedure which will exploit the speacial features of LPPs.

• No method has been found which will yield an optimal solution to a LPP in a single step.
• All techniques for solving such problems are iterative.
• If there are numerous constraints, it can be extremely difficult to find any feasible solution.
• The most widely used procedure for solving LPP is called the Simplex Method which was developed George B. Dantzig in 1947.
• The term Simplex has nothing to do with the method as it is now used.
• It had its origin in a special problem that was studied in the early development of the method.
• Simplex Method is an algebraic iterative procedure which will solve exactly any LPP in a finite number of steps or give an indication that there is an unbounded solution.
• Simplex Method can be given a very simple geonetrical interpretation. It is stated that if there exists an optimal solution, one of the extreme points is optimal. There are only finite number of extreme points in case of an optimal solution.
• Simplex Method is a procedure which will solve the LPP by moving step by step from a given extreme point to an optimal extreme point.
• At each extreme point, the simplex method tells us whether that extreme point is optimal, and if not, what the next extreme point will be.
• If at any stage, the simplex method comes to an extreme point which has an edge leading to infinity and if the objective function can be increased (or decreased) by moving along that edge, the simplex method informs us that there is an unbounded solution.
• As indicated above, Simple Method starts with a given extreme point. The question now arises how to find an initial extreme point.

Why not differential calculus to solve LPP?

• The difficulty starts from the fact that optimal solutions lie on the boundary of the feasible region at the corners of the boundary.
• Also the methods of differential calculus determine relative maxima and minima; and these are of considerably less value when absolute maxima and minima are to be obtained.
• In fact, if an optimal solution exist, differential calculus does not tell us that one of the extreme points is optimal. Unfortunately, it does not specify which extreme point is optimal.
• Hence, the idea of using differential calculus to solve LPPs has to be discarded.