| Advertisement |
There are two two linear programming Theorems : The trial and error and simplex methods are based on the concept of slack variables and theorems described below:
Extreme point theorem : It states that an optimal solution to a LPP occurs at one of the vertices of the feasible region. This should be obvious from the discussion on the graphical method. Now the vertices are defined by the intersection of equations. The first step of the method is, therefore, to convert the inequalities into equalities by the addition (or subtraction) of the slack (or surplus variables) depending on the direction of the inequality.
It is to be noted that the system of equations (A) above has more variables than the number of equations. Such a system of equations has an infinite number of solutions; yet it has finite and few vertices, the co-ordinates of which can be determined by applying the Basis theorem.
Basis theorem : It states that for a system of m equations in n variables (where n > m) has a solution in which at least (n-m) of the variables have value of zero as a vertex. This solution is called a basic solution.
Extreme point theorem can be extended to state that the objective function is optimal at least at one of the basic solutions. Some of the vertices may be infeasible in that they have (-)ve coordinates and have to be dropped in view of the non-negativity condition on all variables including the slack and surplus variables.
