Tow Phase and M-Method for Solving Linear Programming

Tow Phase and M-Method for Solving Linear Programming

The simplex method is very useful and appropriate method for solving linear programming problem having more than two variables. The slack variables are introduced for less than or equal to type, surplus variables are introduce for greater than or equal to type of linear programming problem. The basic feasible solution is important in order to solve the problem using the simplex method. A basic feasible solution of a system with m-equations and n-variables has m non-negative variables called as basic variables. The Surplus variables can’t provide the basic feasible solution instead artificial variables are used to get the basic feasible solutions and it initiate the simplex procedure. The Two phases and M-Method are available to solve linear programming problem in this case. The simplex method is also used to identify the multiple, unbounded and infeasible solutions.
Generally, the linear programming problem can be characterized by the presence of both ‘less than or equal to (?)’ type or ‘greater than or equal to (?)’type constraints. In such case it is not always possible to obtain an initial basic feasible solution using slack variables. The (greater than or equal to) type of linear programming problem can be solved by using the following methods:

1. Two Phase Method
2. M Method



Two Phases Method
Example:
Minimize 12.5x1 + 14.5x2
Subject to:
x1 + x2 ? 2000
0.4x1 + 0.75x2 ? 1000
0.075x1 + 0.1x2 ? 200
x1, x2 ? 0
Solution:
Here the objective function is to be minimized; the values of x1 and x2 (which minimized this objective function) are also the values which maximize the revised objective function i.e.
Maximize -12.5 x1 – 14.5 x2
We can multiply the second and the third constraints by 100 and 1000 respectively for the convenience of calculation.
Thus, the revised linear programming problem is:
Maximize -12.5 x1 – 14.5 x2
Subject to:
x1 + x2 ? 2000
40 x1 + 75 x2 ? 100000
75 x1 + 100 x2 ? 200000
x1, x2 ? 0
Now we convert the two inequalities by introducing surplus variables s3 and s4 respectively.
The third constraint is changed into an equation by introducing a slack variable s5.
Thus, the linear programming problem becomes as

Even though the surplus variables can convert greater than or equal to type constraints into equations they are unable to provide initial basic variables to start the simplex method calculation. So we may have to introduce two more additional variables a6 and a7 called as artificial variable to facilitate the calculation of an initial basic feasible solution.
In this method the calculation is carried out in two phases hence two phases method.