I got my answer from other source. It clears all my confusion. Show The general idea behind two-phase methods is create an auxiliary problem, with an obvious starting solution (which may be infeasible for the original problem), and with the objective of eliminating the infeasibilities. If the optimal auxiliary solution eliminates the infeasibilities, then the auxiliary solution values of the variables from the original problem can be used to start phase 2 with a basic feasible solution. The artificial variables in phase 1 are introduced so that we can make the original problem variables nonbasic and set them to zero even though that may not be feasible to the original problem. The artificial variables take on the resulting infeasibilities and are basic at the start of phase 1. The phase 1 objective is to drive those variables to zero, at which point the original problem variables are feasible and the current basis consists of original problem variables. (Some minor cleanup may be necessary in the case of degeneracy.) Then one can use that basis as the start of phase 2. If one can’t drive all the artificials to zero, that means the original problem has no feasible solution
When George Dantzig originally put forward the simplex method, it was limited only to LP problems having a known feasible solution, commonly called the initial basic feasible solution. When the traditional simplex method is applied to larger LP problems, the number of variables and number of iterations is increased considerably and with this, also the complexity. Because simplex method is possibly the best and most universally applied pivot algorithm for solving LP problems, it became important to develop more general methods to solve LP problems, where an arbitrary initial basic solution (which was not necessarily a feasible solution) may be used to begin the pivoting process. Dantzig (1955) and Wagner (1956) highlighted that for LPs without an initial basic feasible solution, almost all the current variants of the simplex method are applicable in two phases. In Phase I, a basic feasible solution is generated by adding variables known as artificial variables to the problem with a specially constructed auxiliary objective, aiming to minimise the sum of all the artificial variables while maintaining feasibility. When all the artificial variables reach a value of zero, it means all the infeasibilities have been eliminated and we can continue with the normal simplex method in Phase II. If not, the problem does not have a feasible solution. Artificial variables are also used in another simplex method that predates the two-phase method and is known as the Big M method. The Big M method allows the simplex algorithm to be applied to problems that contain a greater-than type of constraints by introducing a large negative constant M which would not be part of the final optimal solution if there is any. In this article, readers will gain an insight into artificial variables and the two methods that use them to extend the simplex method to solve LP problems. Artificial Variables TechniqueIn the previous article, you studied problems where slack and surplus variables readily provided an initial basic feasible solution. You assign zero cost to these variables in the objective function. A problem may arise when slack variables do not provide an initial basic feasible solution and it becomes difficult to start and proceed with the initial simplex tableau. This happens when the slack variables have negative values. For example, let us consider a constraint: x + 3y ≥ 175 To replace this inequality with an equation, you need to subtract a slack variable so that you have: x + 3y – S = 175 Now, if x and y are non-basic variables in the problem, then S is taken as the starting basic variable. But this means that the value of S = –175 which is infeasible. You cannot continue any more iterations of the simplex method with an infeasible basic solution. To generate an initial solution, you need to use the artificial variable technique so that you can proceed with the simplex method until the optimal solution is reached. Artificial variables are added to constraints with greater than or equal to sign to generate an initial solution to an LP problem. In a physical sense, artificial variables have no meaning, they are purely a means for getting an initial solution to an LP problem and are eliminated later. Big M Method (Penalty Method/ Charnes Method)In some LP problems, the slack variables cannot give the initial basic feasible solution. In these types of LP problems, a minimum of one constraint is of ≥ type. Since a basis matrix cannot be obtained as an identity matrix in the initial simplex tableau, you use a new type of variable called the artificial variable to generate the initial basic solution. You can extend the simplex method to solve such LP problems with artificial variables using either of the two methods:
Big M Algorithm Step 1: Express the LP problem in the standard form by adding slack and/or surplus variables. Step 2: Introduce non-negative artificial variables to the left side of all equations with constraints of the type >, or =. Remember that adding these artificial variables results in violation of the corresponding constraints. Hence, we have to eliminate these variables and cannot allow them to appear in the final solution. In order to do this, we have to assign a very large penalty (–M for maximisation and + M for minimisation) in the objective function. Step 3: Use the simplex method to solve the modified LP problem, until any one of the three cases arise at an iteration:
Inserting Slack, Surplus and Artificial Variables in the Big M Method A slack variable is added to less than or equal to type of constraints to convert them to equalities. A surplus variable is added to greater than or equal to type of constraints to convert them to equalities. For a binding constraint, the corresponding slack or surplus value will equal zero. Artificial variable is introduced in the LP model to obtain the initial basic feasible solution. It is used for the equality constraints and for the greater than or equal to type of inequality constraints. Comparison Between the Different Types of Variables
Let us now see where the variables are inserted in the Big M method: In Step 1 of the Big M method, the constraints of the given LP problem are expressed in the equation form by including slack variables for constraint of the type ≤ or surplus variables for constraint of the type ≥. Now, the basic solution for the problem, an infeasible one can be determined as the basic variable is negative for constraints of the type ≥. In Step 2 of the Big M method, non-negative artificial variables are added to the left-hand side of each of the equations corresponding to the constraints of the types > and = to generate a starting basic feasible solution. Two Phase MethodThe two-phase method is so named because the LP problem is solved in two phases. Simplex method is applied to a specially constructed auxiliary LP problem in Phase I, and the problem is solved by applying the simplex method which helps in generating a basic feasible solution to the original problem. The process of elimination of artificial variables is performed in Phase I of the solution and Phase II is used to obtain an optimal solution using a simplex. In Phase I, the artificial variables are introduced for making the vari- ables of the original problem non-basic and set them to zero even though this might be infeasible to the original problem. The resulting infeasibilities are taken on by the artificial variables and they are basic at the beginning of Phase I. Let us now look into the steps of the two-phase method: PHASE 1 Step 1: Express the given LP problem into standard form and check if a starting basic feasible solution to the problem exists. One of the two cases might arise:
Step 2: Add the artificial variable to the left-hand side of each equation that does not have the required starting basic variables. Construct an auxiliary objective function whose aim is to minimise the sum of all artificial variables. Therefore, Minimise Z= A1 + A2 + A3 + ………. + An becomes Maximize Z* = – A1 – A2 – A3 – ………. – An where Ai (i = 1,2,3…m) are the non-negative artificial variables. Step 3: Apply the simplex algorithm to the specially constructed auxiliary LP problem. At the last iteration, we may have one of the follow- ing three cases:
PHASE 2 The optimum basic feasible solution of phase I is used as the initial basic feasible solution for the original LP problem. Assign actual coefficients to the variables in the objective function and zero value to the artificial variables that show zero value in the final simplex tableau of Phase I. Use the normal simplex algorithm on the modified simplex tableau to obtain the optimum solution of the original problem. Comparison of Big M Simplex Method and the Two-phase Simplex Method
The drawback to Big M method is related to how we choose the penalty M. If M is too small, the final solution to the original problem may not even be feasible, let alone optimal, since the penalty for infeasibility was not big enough. On the other hand, if M is very large, the original problem can have numerical issues and the final solution may not be optimal. Sometimes, no M value exists that can prevent both these issues. Another limitation of the big M method over the two-phase method is that in the former, feasibility is not known until optimality is reached.
|