重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 4 ADAPTING TO OTHER MODEL FORMS Thus far we have presented the details of the simplex method under the assumptions that the problem is in our standard form (maximize Z subject to functional constraints in ≤ form and nonnegativity constraints on all variables) and that bi ≥ 0 for all i = 1, 2...., m. In this section we point out how to make the adjustments required for other legitimate forms of the linear programming model.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The only serious problem introduced by the other forms for functional constraints (the = or ≥ forms, or having a negative right-hand side) lies in identifying an initial BF solution. Before, this initial solution was found very conveniently by letting the slack variables be the initial basic variables, so that each one just equals the nonnegative, right- hand side of its equation, Now, something else must be done.  The standard approach that is used for all these cases is the artificial- variable technique. This technique constructs a more convenient artificial problem by introducing a dummy variable (called an artificial variable) into each constraint that needs one. This new variable is introduced just for the purpose of being the initial basic variable for that equation. The usual nonnegativity constraints are placed on these variables, and the objective function also is modified to impose an exorbitant penalty on their having values larger than zero. The iterations of the simplex method then automatically force the artificial variables to disappear (become zero), one at a time, until they are all gone, after which the real problem is solved.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  To illustrate the artificial-variable technique, first we consider the case where the only nonstandard form in the problem is the presence of one or more equality constraints.  EQUALITY CONSTRAINTS  Any equality constraint  a il X 1 + a i2 X a in X n = b i  actually is equivalent to a pair of inequality constraints  a il X 1 + a i2 X a in X n <= b i  a il X 1 + a i2 X a in X n >= b i.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  However, rather than making this substitution and thereby increasing the number of constraints, it is more convenient to use the artificial-variable technique.  Example  Suppose that the Wyndor Glass Co. problem in Sec. 3.1 is modified to require that Plant 3 be used at full capacity. The only resulting change in the linear programming model is that the third constraint, 3X 1 + 2X 2 <= 18, instead becomes an equality constraint 3x1 + 2x2 = 18, so that the complete model becomes the one shown in the upper right-hand corner of Fig This figure also shows in darker ink the feasible region which now consists of just the line segment connecting (2, 6) and (4, 3).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  After the slack variables still needed for the inequality constraints are introduced, the system of equations for the augmented form of the problem becomes  (0) Z- 3x1 - 5x2 = 0  (1) x1 + x3 = 4  (2) 2x2 + x4 = 12  (3) 3x1 + 2x2 = 18.  Unfortunately, these equations do not have an obvious initial BF solution because there is no longer a slack variable to use as the initial basic variable for Eq. (3).  It is necessary to find an initial BF solution to start the simplex method.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Obtaining an Initial BF Solution  The procedure is to construct an artificial problem that has the same optimal solution as the real problem by making two modifications of the real problem.  1. Apply the artificial-variable technique by introducing a nonnegative artificial variable (call it x5) into Eq. (3), just as if it were a slack variable  (3) 3x1 + 2x2 + X5 = 18.  2. Assign an overwhelming penalty to having X5 > 0 by changing the objective function  Z = 3x1 + 5x2 to  Z = 3x1 + 5x2 – MX5,  Where M symbolically represents a huge positive number.  This method of forcing X5 to be X5 = 0 in the optimal solution is called the Big M method.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Now find the optimal solution for the real problem by applying the simplex method to the artificial problem, starting with the following initial BF solution:  Initial BF Solution  Nonbasic variables: x1 = 0, x2 = 0  Basic variables: x3 = 4, x4 = 12, X5 = 18.  Because X5 plays the role of the slack variable for the third constraint in the artificial problem, this constraint is equivalent to 3x1 + 2x2 <= 18 (just as for the original Wyndor Glass Co. problem in Sec. 3.1). We show below the resulting artificial problem (before augmenting) next to the real problem.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Obtaining an Initial BF Solution

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Note that the simplex method moves counterclockwise here whereas it moved clockwise for the original Wyndor Glass Co. problem (see Fig. 4.2). The reason for this difference is the extra term - MX5 in the objective function for the artificial problem.  Before applying the simplex method and demonstrating that it follows the path shown in Fig. 4.4, the following preparatory step is needed.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Converting Equation (0) to Proper Form  The system of equations after the artificial problem is augmented is  (0) Z- 3x1 - 5x2 + MX5 = 0  (1) x1 + x3 = 4  (2) 2x2 + x4 = 12  (3) 3x1+ 2x2 + X5 = 18  where the initial basic variables (x3, x4, X5) are shown in green type. However, this system is not yet in proper form from Gaussian elimination because a basic variable X5 has a nonzero coefficient in Eq. (0). Recall that all basic variables must be algebraically eliminated from Eq. (0) before the simplex method can either apply the optimality test or find the entering basic variable. This elimination is necessary so that the negative of the coefficient of each nonbasic variable will give the rate at which Z would increase if that nonbasic variable were to be increased from 0 while adjusting the values of the basic variables accordingly.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Application of the Simplex Method  This new Eq. (0) gives Z in terms of just the nonbasic variables (xl, x2),  Z = -18M + (3M + 3)x1 + (2M + 5)x2.  Since 3M + 3 > 2M + 5 (remember that M represents a huge number), increasing x1 increases Z at a faster rate than increasing x2 does, so x1 is chosen as the entering basic variable. This leads to the move from (0, 0) to (4, 0) at iteration 1, shown in Fig. 4.4, thereby increasing Z by 4(3M + 3).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Negative Right-Hand Sides  The technique mentioned in the preceding sentence for dealing with an equality constraint with a negative right-hand side (namely, multiply through both sides by -1) also works for any inequality constraint with a negative right-hand side. Multiplying through both sides of an inequality by - 1 also reverses the direction of the inequality; i.e., = or vice versa.  For example, doing this to the constraint  x1 - x2 <= -1 (namely, x1 <= x2 - 1) gives the equivalent constraint  -x1 + x2 >= 1 (that is, x2 - 1 >= x1)  but now the right-hand side is positive. Having nonnegative right- hand sides for all the functional constraints enables the simplex method to begin, because (after augmenting) these right-hand sides become the respective values of the initial basic variables, which must satisfy nonnegativity constraints.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Functional Constraints in >= Form  To illustrate how the artificial-variable technique deals with functional constraints in >= form, we will use the model for designing Mary's radiation therapy, as presented in Sec For your convenience, this model is repeated right, where we have placed a box around the constraint of special interest here.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Our approach involves introducing both a surplus variable x5 (defined as x5 = 0.6xl + 0.4x2 - 6) and an artificial variable X6, as shown next. Here x5 is called a surplus variable because it subtracts the surplus of the left-hand side over the right-hand side to convert the inequality constraint to an equivalent equality constraint. Once this conversion is accomplished, the artificial variable is introduced just as for any equality constraint. Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  After a slack variable x3 is introduced into the first constraint, an artificial variable x4 is introduced into the second constraint, and the Big M method is applied, so the complete artificial problem (in augmented form) is Note that the coefficients of the artificial variables in the objective function are +M, instead of -M, because we now are minimizing Z. Thus, even though x4 > 0 and/or x6 > 0 is possible for a feasible solution for the artificial problem, the huge unit penalty of +M prevents this from occurring in an optimal solution. Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  As usual, introducing artificial variables enlarges the feasible region. Compare below the original constraints for the real problem with the corresponding constraints on (xl, x2) for the artificial problem. Introducing the artificial variable x4 to play the role of a slack variable in the second constraint allows values of (x1, x2) below the 0.5x x2 = 6 line in Fig Introducing x5 and X6 into the third constraint of the real problem (and moving these variables to the right-hand side) yields the equation Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Because both x5 and X6 are constrained only to be nonnegative, their difference x5 - x6 can be any positive or negative number. Therefore, 0.6x x2 can have any value, which has the effect of eliminating the third constraint from the artificial problem and allowing points on either side of the 0.6x x2 = 6 line in Fig. (We keep the third constraint in the system of equations only because it will become relevant again later, after the Big M method forces x6 to be zero.)  Consequently, the feasible region for the artificial problem is the entire polyhedron in figure whose vertices are (0, 0), (9, 0), (7.5, 4.5), and (0, 12). Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Since the origin now is feasible for the artificial problem, the simplex method starts with (0, 0) as the initial CPF solution, i.e., with (x1, x2, x3, X4, x5, X6) = (0, 0, 2.7, 6, 0, 6) as the initial BF solution. (Making the origin feasible as a convenient starting point for the simplex method is the whole point of creating the artificial problem.) We soon will trace the entire path followed by the simplex method from the origin to the optimal solution for both the artificial and real problems. But, first, how does the simplex method handle minimization? Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Minimization  One straightforward way of minimizing Z with the simplex method is to exchange the roles of the positive and negative coefficients in row 0 for both the optimality test and step 1 of an iteration. However, rather than changing our instructions for the simplex method for this case, we present the following simple way of converting any minimization problem to an equivalent maximization problem: i.e., the two formulations yield the same optimal solutions.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The two formulations are equivalent because the smaller Z is, the larger -Z is, so the solution that gives the smallest value of Z in the entire feasible region must also give the largest value of -Z in this region.  Therefore, in the radiation therapy example, we make the following change in the formulation:  Minimize Z = 0.4x x2  ---> Maximize -Z = -0.4x x2.  After artificial variables X4 and X6 are introduced and then the Big M method is applied, the corresponding conversion is  Minimize Z = 0.4x x2 + MX4 + MX6  --> Maximize -Z = -0.4x x2 - MX4 - MX6. Minimization

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  We now are nearly ready to apply the simplex method to the radiation therapy example. By using the maximization form just obtained, the entire system of equations is now  (0) -Z + 0.4x x2 + MX4 + MX6 = 0  (1) 0.3x x2 + x3 = 2.7  (2) 0.5x x2 + x4 = 6  (3) 0.6x x2 - x5 + X6 = 6.  The basic variables (x3, X4, X6) for the initial BF solution (for this artificial problem) are shown in green type. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Note that this system of equations is not yet in proper form from Gaussian elimination, as required by the simplex method, since the basic variables X4 and X6 still need to be algebraically eliminated from Eq. (0). Because X4 and X6 both have a coefficient of M, Eq. (0) needs to have subtracted from it both M times Eq. (2) and M times Eq. (3). The calculations for all the coefficients (and the right-hand sides) are summarized below, where the vectors are the relevant rows of the simplex tableau corresponding to the above system of equations. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The resulting initial simplex tableau, ready to begin the simplex method, is shown at the top of Table Applying the simplex method in just the usual way then yields the sequence of simplex tableaux shown in the rest of Table For the optimality test and the selection of the entering basic variable at each iteration, the quantities involving M are treated just as discussed in connection with Table Note in Table 4.12 the progression of values of the artificial variables X4 and X6 and of Z. We start with large values, X4 = 6 and X6 = 6, with Z = 12M (-Z = - 12M). The first iteration greatly reduces these values. The Big M method succeeds in driving X6 to zero (as a new nonbasic variable) at the second iteration and then in doing the same to X4 at the next iteration. With both X4 = 0 and X6 = 0, the basic solution given in the last tableau is guaranteed to be feasible for the real problem. Since it passes the optimality test, it also is optimal. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Now see what the Big M method has done graphically in Fig The feasible region for the artificial problem initially has four CPF solutions--(0, 0), (9, 0), (0, 12), and (7.5, 4.5)--and then replaces the first three with two new CPF solutions--(8, 3), (6, 6)- after X6 decreases to x6 = 0 so that 0.6x x2 >= 6 becomes an additional constraint. Starting with the origin as the convenient initial CPF solution for the artificial problem, we move around the boundary to three other CPF solutions--(9, 0), (8, 3), and (7.5, 4.5). The last of these is the first one that also is feasible for the real problem. Fortuitously, this first feasible solution also is optimal, so no additional iterations are needed. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  For other problems with artificial variables, it may be necessary to perform additional iterations to reach an optimal solution after the first feasible solution is obtained for the real problem. Thus, the Big M method can be thought of as having two phases. In the first phase, all the artificial variables are driven to zero (because of the penalty of M per unit for being greater than zero) in order to reach an initial BF solution for the real problem. In the second phase, all the artificial variables are kept at zero (because of this same penalty) while the simplex method generates a sequence of BF solutions for the real problem that leads to an optimal solution. The two-phase method described next is a streamlined procedure for performing these two phases directly, without even introducing M explicitly. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research The Two-Phase Method  For the radiation therapy example just solved in Table 4.12, recall its real objective function  Real problem: Minimize Z = 0.4x x2.  However, the Big M method uses the following objective function (or its equivalent in maximization form) throughout the entire procedure:  Big M method: Minimize Z = 0.4x x2 + MX4 + MX6.  Since the first two coefficients are negligible compared to M, the two-phase method is able to drop M by using the following two objective functions with completely different definitions of Z in turn.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Two-phase method:  Phase 1: Minimize Z = X4 + X6 (until X4 = 0, X6 = 0).  Phase 2: Minimize Z = 0.4x x2 (with X4 = 0, X6 = 0).  The phase 1 objective function is obtained by dividing the Big M method objective function by M and then dropping the negligible terms. Since phase 1 concludes by obtaining a BF solution for the real problem (one where X4 = 0 and X6 = 0), this solution is then used as the initial BF solution for applying the simplex method to the real problem (with its real objective function) in phase 2.  Before solving the example in this way, we summarize the general method. The Two-Phase Method

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Initialization: Revise the constraints of the original problem by introducing artificial variables as needed to obtain an obvious initial BF solution for the artificial problem.  Phase 1: The objective for this phase is to find a BF solution for the real problem. To do this, Minimize Z = ∑artificial variables, subject to revised constraints.  The optimal solution obtained for this problem (with Z = 0) will be a BF solution for the real problem.  Phase 2: The objective for this phase is to find an optimal solution for the real problem. Since the artificial variables are not part of the real problem, these variables can now be dropped (they are all zero now anyway). Starting from the BF solution obtained at the end of phase 1, use the simplex method to solve the real problem. Summary of the Two-Phase Method

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  For the example, the problems to be solved by the simplex method in the respective phases are summarized below. (Radiation Therapy Example):  Phase 1 Problem: Minimize Z = X4 + X6, subject to:  0.3xl + 0.1x2 + x3 = 2.7  0.5x x2 + X4 = 6  0.6xl + 0.4x2 - x5 +X6 = 6  and x1 >= 0, x2 >= 0, x3 >= 0, X4 >= 0, x5 >= 0, X6 >= 0.  Phase 2 Problem: Minimize Z = 0.4x x2, subject to:  0.3xl + 0.1x2 + x3 = 2.7  0.5x x2 = 6  0.6xl + 0.4x2 - x5 = 6  and x1 >= 0, x2 >= 0, x3 >= 0, x5 >= 0.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 1  The only differences between these two problems are in the objective function and in the inclusion (phase 1) or exclusion (phase 2) of the artificial variables x4 and X6. Without the artificial variables, the phase 2 problem does not have an obvious initial BF solution. The sole purpose of solving the phase 1 problem is to obtain a BF solution with x4 = 0 and X6 = 0 so that this solution (without the artificial variables) can be used as the initial BF solution for phase 2.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 1  Table 4.13 shows the result of applying the simplex method to this phase 1 problem. [Row 0 in the initial tableau is obtained by converting Minimize Z = X4 + X6 to Maximize (-Z) = -X4 - X6 and then using elementary row operations to eliminate the basic variables X4 and X6 from -Z + X4 + X6 = 0. In the next-to-last tableau, there is a tie for the entering basic variable between x3 and x5, which is broken arbitrarily in favor of x3. The solution obtained at the end of phase 1, then, is (xl, x2, x3, X4, x5, X6) = (6, 6, 0.3, 0, 0, 0) or, after X4 and X6 are dropped, (x1, x2, x3, x5) = (6, 6, 0.3, 0).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 1  As claimed in the summary, this solution from phase 1 is indeed a BF solution for the real problem (the phase 2 problem) because it is the solution (after you set x5 = 0) to the system of equations consisting of the three functional constraints for the phase 2 problem. In fact, after deleting the x4 and x6 columns as well as row 0 for each iteration, Table 4.13 shows one way of using Gaussian elimination to solve this system of equations by reducing the system to the form displayed in the final tableau.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 2  Table 4.14 shows the preparations for beginning phase 2 after phase 1 is completed. Starting from the final tableau in Table 4.13, we drop the artificial variables (x4 and X6), substitute the phase 2 objective function (-Z = -0.4x x2 in maximization form) into row 0, and then restore the proper form from Gaussian elimination (by algebraically eliminating the basic variables x1 and x2 from row 0). Thus, row 0 in the last tableau is obtained by performing the following elementary row operations in the next-to-last tableau: from row 0 subtract both the product, 0.4 times row 1, and the product, 0.5 times row 3. Except for the deletion of the two columns, note that rows 1 to 3 never change. The only adjustments occur in row 0 in order to replace the phase I objective function by the phase 2 objective function.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 2

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The last tableau in Table 4.14 is the initial tableau for applying the simplex method to the phase 2 problem, as shown at the top of Table Just one iteration then leads to the optimal solution shown in the second tableau: (x1, x2, x3, x5) = (7.5, 4.5, 0, 0.3). This solution is the desired optimal solution for the real problem of interest rather than the artificial problem constructed for phase 1. Phase 2

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 2

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Now we see what the two-phase method has done graphically in Fig Starting at the origin, phase 1 examines a total of four CPF solutions for the artificial problem. The first three actually were corner-point infeasible solutions for the real problem shown in Fig The fourth CPF solution, at (6, 6), is the first one that also is feasible for the real problem, so it becomes the initial CPF solution for phase 2. One iteration in phase 2 leads to the optimal CPF solution at (7.5, 4.5).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Compare the Big M and Two-Phase Methods  Begin with their objective functions.  Big M Method: Minimize Z = 0.4x x2 + MX4 + MX6.  Two-Phase Method:  Phase 1: Minimize Z = X4 + X6.  Phase 2: Minimize Z = 0.4x x2.  Because the MX4 and MX6 terms dominate the 0.4x1 and 0.5x2 terms in the objective function for the Big M method, this objective function is essentially equivalent to the phase 1 objective function as long as X4 and/or X6 is greater than zero. Then, when both X4 = 0 and X6 = 0, the objective function for the Big M method becomes completely equivalent to the phase 2 objective function.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Because of these virtual equivalencies in objective functions, the Big M and two- phase methods generally have the same sequence of BF solutions: The one possible exception occurs when there is a tie for the entering basic variable in phase 1 of the two- phase method, as happened in the third tableau of Table Notice that the first three tableaux of Tables 4.12 and 4.13 are almost identical, with the only difference being that the multiplicative factors of M in Table 4.12 become the sole quantities in the corresponding spots in Table Consequently, the additive terms that broke the tie for the entering basic variable in the third tableau of Table 4.12 were not present to break this same tie in Table The result for this example was an extra iteration for the two-phase method. Generally, however, the advantage of having the additive factors is minimal. Compare the Big M and Two-Phase Methods

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The two-phase method streamlines the Big M method by using only the multiplicative factors in phase 1 and by dropping the artificial variables in phase 2. (The Big M method could combine the multiplicative and additive factors by assigning an actual huge number to M, but this might create numerical instability problems.) For these reasons, the two-phase method is commonly used in computer codes. Compare the Big M and Two-Phase Methods