artificial variables web

Artificial Variables [ This is an excellent presentation I found on the web at eal.asu.edu/lobos/iee476/Instructor's%20Section/ Others/Support%20Modules/Artificial.doc It even comments on handling equality constraints. Author is Mr. Lobos, a Professor of Industrial Engineering with the Electronics Assembly Lab at Arizona State University. The EAL research does sound very simplex oriented! -PhL 12.1.04 ] The previous example problem contained only Type I () inequalities. When other constraint types are present (Type II and equality constraints), the set-up is necessarily different. Recall earlier the need for an identity matrix embedded within the original tableau was indicated. When the problem involves only Type I inequalities, the slack variables automatically form this identity matrix. When other types of constraints are present this may be untrue so you must add “artificial variables” to form a starting basic solution (identity matrix). The complete set-up of the simplex method including artificial variables follows. For Type I inequalities of the form you need only add a slack variable to form a constraint equation of the form . For equality constraints you add an “artificial variable”, thus a constraint of the form becomes where is the artificial variable. For Type II inequalities you subtract a slack variable and add an artificial variable. Thus a constraint of the form becomes , where is the slack and is the artificial variable. For equality constraints we simply add a slack variable. Key insight Note that the slack variables added to Type I constraints and the artificials added to Type II and equality constraints have two important properties. They are unique to that equation (don’t appear anywhere else!), and they have a +1 coefficient. As a result a collection of their coefficient columns is always an identity matrix. The variables added to Type II inequalities and equality constraints are called “artificial variables” because they have no real physical meaning. Their only purpose is to provide a convenient starting basic solution. Note that the only value they can take on is zero if the equations are to truly represent the actual constraints. Thus the original basic solution (in which the artificial variables are positive) is not really feasible in terms of the original constraints. Therefore, in the subsequent iterations of the simplex method the artificial variables must be forced to become zero so that the solution becomes feasible in terms of the true problem constraints. There are several ways to do this. The classical method is referred to as the “Big-M method”, which will be discussed next. The Big-M Method Returning to the problem of forcing the artificial variables to be zero, one way which you could insure that these variables become zero is to attach a large penalty in the objective function for positive values. To do this we simply assign these artificial variables large negative coefficients (-M) in maximization problems and a large positive coefficients (+M) in minimization problems. Thus the objective function becomes in the maximization case: Max: And in the minimization case: Min: Where the M is some large number in comparison to the . To illustrate, consider the following example problem: Max: St: . Introducing slack and artificial variables, the constraints become: The objective should then be modified to become: Max: . Putting the problem in tableau format it becomes: Note that this tableau is not in the proper form; the objective row must be in terms of only non-basic variables; i.e. the objective row coefficients of the basic variables must be zero. The M’s in the and columns must then be changed to zeros using row operations. So you multiply Row 1 and Row 2 by –M and add them to Row 0 to obtain: Now proceed as normal to get the next tableau = MIN {7/1, 10/2}=5. In the next iteration enters and leaves, yielding: which is optimal since all . The Big-M method suffers from two important shortcomings. You must go all the way to the final tableau before discovering that the problem has no feasible solutions (artificial variables at positive level in final tableau). The use of the constant M is cumbersome and if a very large number is substituted for M it can cause numerical round-off problems on the digital computer. Two Phase Method Another artificial variable technique called the Two Phase Method removes these difficulties. The title of the method comes from the fact that computations proceed in two distinct phases. The first phase merely attempts to drive the artificials out of the basic solution using the simplex method and thereby form a feasible starting solution without artificials for the second phase. The second phase merely moves from this new feasible starting solution to optimality using the simplex method. The two phase method is summarized as follows: Phase I – Formulate the problem as you did for the Big-M method, i.e., adding artificials to Type II and equality constraints, however you replace the actual objective function with: Minimize: Where the are the K artificial variables. Now you solve this “artificial problem” by the simplex algorithm. If the optimal objective function is greater than zero when the simplex method terminates, stop! This indicates the problem has no feasible solution. However, if the objective function is zero when the simplex method terminates, then all the artificials have all been driven to zero (a true feasible solution) and you proceed to Phase II. Phase II – You now restore the original objective function into the row of the tableau and drop all non-basic artificial variables (and their columns) from the tableau. Then you obtain zeros for all basic variables in the row using row operaitons. Finally, you again apply the simplex method to move to the optimal solution which must exist. To illustrate, the prior example is resolved using the two phase method. Recall the problem was: Max: St: Phase I: The phase one problem is Min: St: Putting in the tableau form: Since and are the initial basic variables you must first get 0’s in the row for them before beginning the simplex method. You do this by row operations just like we did in the Big-M method (add row 1 and 2 to row 0). Adding the first and second rows to the row gives us: Now use the simplex method to minimize so select largest positive coefficient which is ’s and MIN ( leaves). Performing row operations the next tableau is: Next select as the entering variable since it has the largest row coefficient, MIN 4/7 and leaves. Performing the row operations yields the next tableau. Inspecting the row, note that this solution is optimal. Since the value of the objective function is zero, you know this problem has a feasible solution so proceed to Phase II. Phase II: First you rewrite the tableau with the true original objective function, note that you drop and and their columns. Again, this tableau is not in correct form since you do not have zeros for the basic variables in the row. So you must apply row operations (multiply first row by 3 and second by 2 and add to the row). When you examine the row you find this is optimal (if it were not you would continue with the simplex method). Question What if there were Type I equalities, since they don’t have artificial variables, could they be left out of Phase I? e.g., say the constant was also included in the model. Answer All constraints must be included in Phase I, otherwise the solution obtained in Phase I may not be feasible. Note that would be the case here, since the solution has ! So whether they have artificial variables or not ALL constraints are included in Phase I.