SIMPLEX METHOD
Most real-life problems when formulated as an LP(Linear programming) the model has more than two variables and is too large for the graphical solution method. Thus, we need a more efficient method to suggest an optimal solution for such problems. In this chapter, we shall discuss a procedure called the simplex method for solving an LP model of such problems. The method was developed by G B Dantzig in 1947. The simplex is an important term in mathematics that represents an object in n-dimensional space connecting n + 1 points. In one dimension, a simplex is a line segment connecting two points; in two dimensions, it is a triangle formed by joining three points; in three dimensions, it is a four-sided pyramid having four corners. The concept of the simplex method is similar to the graphical method. In the graphical method, extreme points of the feasible solution space are examined to search for an optimal solution for one of them. For LP problems with several variables, we may not be able to graph the feasible region, but the optimal solution will still lie at an extreme point of the many-sided, multidimensional figure [called an n-dimensional polyhedron] that represents the feasible solution space. The simplex method examines the extreme points in a systematic manner, repeating the same set of steps of the algorithm until an optimal solution is reached. It is for this reason that it is also called the iterative method. Since the number of extreme points [corners or vertices] of feasible solution space and finite, the method assures improvement in the value of the objective function as we move from one iteration [extreme point] to another and achieve the optimal solution in a finite number of steps and also indicates when an unbounded is reached.
STANDARD FORM OF AN LP PROBLEM
The use of the simplex method to solve an LP(Linear programming) problem requires that the problem be converted into its standard form.
The simplex method both for the minimization and the maximization LP problem may be summarized in the form of a flow chart:
0 Comments