10.8 Linear Programming and the Simplex Method 437 For example,introducing slack variables leaves (10.8.6)unchanged but turns (10.8.7)into x1+2x3+h=740 2x2-7x4+2=0 (10.8.15) x2-x3+2x4-3= E1+x2+3+x4=9 三 (Notice how the sign of the coefficient of the slack variable is determined by which sense of inequality it is replacing. Second,we need to insure that there is a set of M left-hand vectors,so that we can set up a starting tableau in restricted normal form.(In other words,we need to find a "feasible basic starting vector.")The trick is again to invent new variables! 、新M There are M of these,and they are called artificial variables;we denote them by zi. You put exactly one artificial variable into each constraint equation on the following model for the example (10.8.15): 9 21=740-x1-2x3-y1 22=-2x2+7x4-2 (10.8.16) 28=2-x2+3-2x4十g 24=9-工1-x2-T3-T4 Our example is now in restricted normal form. 6 Now you may object that (10.8.16)is not the same problem as (10.8.15)or (10.8.7)unless all the zi's are zero.Right you are!There is some subtlety here! We must proceed to solve our problem in two phases.First phase:We replace our objective function (10.8.6)by a so-called auxiliary objective function 10-521 2三-a1-22-23-24=-(7495-2x1-4x2-2x3+4x4-1-2+3) 豆2 Numerica (10.8.17) (where the last equality follows from using 10.8.16).We now perform the simplex method on the auxiliary objective function (10.8.17)with the constraints (10.8.16). 5@g3 Obviously the auxiliary objective function will be maximized for nonnegative zi's if 腿 all the zi's are zero.We therefore expect the simplex method in this first phase to produce a set of left-hand variables drawn from the xi's and yi's only,with all the zi's being right-hand variables.Aha!We then cross out the zi's,leaving a problem involving only i's and yi's in restricted normal form.In other words,the first phase produces an initial feasible basic vector.Second phase:Solve the problem produced by the first phase,using the original objective function,not the auxiliary. And what if the first phase doesn't produce zero values for all the zi's?That signals that there is no initial feasible basic vector,i.e.,that the constraints given to us are inconsistent among themselves.Report that fact,and you are done. Here is how to translate into tableau format the information needed for both the first and second phases of the overall method.As before,the underlying problem10.8 Linear Programming and the Simplex Method 437 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). For example, introducing slack variables leaves (10.8.6) unchanged but turns (10.8.7) into x1 + 2x3 + y1 = 740 2x2 − 7x4 + y2 = 0 x2 − x3 + 2x4 − y3 = 1 2 x1 + x2 + x3 + x4 = 9 (10.8.15) (Notice how the sign of the coefficient of the slack variable is determined by which sense of inequality it is replacing.) Second, we need to insure that there is a set of M left-hand vectors, so that we can set up a starting tableau in restricted normal form. (In other words, we need to find a “feasible basic starting vector.”) The trick is again to invent new variables! There are M of these, and they are called artificial variables; we denote them by z i. You put exactly one artificial variable into each constraint equation on the following model for the example (10.8.15): z1 = 740 − x1 − 2x3 − y1 z2 = −2x2 + 7x4 − y2 z3 = 1 2 − x2 + x3 − 2x4 + y3 z4 = 9 − x1 − x2 − x3 − x4 (10.8.16) Our example is now in restricted normal form. Now you may object that (10.8.16) is not the same problem as (10.8.15) or (10.8.7) unless all the zi’s are zero. Right you are! There is some subtlety here! We must proceed to solve our problem in two phases. First phase: We replace our objective function (10.8.6) by a so-called auxiliary objective function z
≡ −z1 − z2 − z3 − z4 = −(749 1 2 − 2x1 − 4x2 − 2x3 + 4x4 − y1 − y2 + y3) (10.8.17) (where the last equality follows from using 10.8.16). We now perform the simplex method on the auxiliary objective function (10.8.17) with the constraints (10.8.16). Obviously the auxiliary objective function will be maximized for nonnegative z i’s if all the zi’s are zero. We therefore expect the simplex method in this first phase to produce a set of left-hand variables drawn from the xi’s and yi’s only, with all the zi’s being right-hand variables. Aha! We then cross out the z i’s, leaving a problem involving only xi’s and yi’s in restricted normal form. In other words, the first phase produces an initial feasible basic vector. Second phase: Solve the problem produced by the first phase, using the original objective function, not the auxiliary. And what if the first phase doesn’t produce zero values for all the z i’s? That signals that there is no initial feasible basic vector, i.e., that the constraints given to us are inconsistent among themselves. Report that fact, and you are done. Here is how to translate into tableau format the information needed for both the first and second phases of the overall method. As before, the underlying problem