10.8 Linear Programming and the Simplex Method 435 The first step in the simplex method is to examine the top row of the tableau. which we will call the "z-row."Look at the entries in columns labeled by right-hand variables(we will call these"right-columns").We want to imagine in turn the effect of increasing each right-hand variable from its present value of zero,while leaving all the other right-hand variables at zero.Will the objective function increase or decrease?The answer is given by the sign of the entry in the z-row.Since we want to increase the objective function,only right columns having positive z-row entries are of interest.In(10.8.10)there is only one such column,whose z-row entry is 2. The second step is to examine the column entries below each z-row entry that was selected by step one.We want to ask how much we can increase the right-hand variable before one of the left-hand variables is driven negative,which is not allowed. If the tableau element at the intersection of the right-hand column and the left-hand variable's row is positive,then it poses no restriction:the corresponding left-hand variable will just be driven more and more positive.Ifal/the entries in any right-hand column are positive,then there is no bound on the objective function and(having said so)we are done with the problem. If one or more entries below a positive z-row entry are negative,then we have to figure out which such entry first limits the increase of that column's right-hand 2 variable.Evidently the limiting increase is given by dividing the element in the right- hand column(which is called the pivot element)into the element in the "constant column"(leftmost column)of the pivot element's row.A value that is small in magnitude is most restrictive.The increase in the objective function for this choice of pivot element is then that value multiplied by the z-row entry of that column.We repeat this procedure on all possible right-hand columns to find the pivot element 、么净)w with the largest such increase.That completes our "choice of a pivot element." OF SCIENTIFIC( In the above example,the only positive z-row entry is 2.There is only one negative entry below it,namely -6,so this is the pivot element.Its constant-column 6 entry is 2.This pivot will therefore allow x2 to be increased by 2:6,which results in an increase of the objective function by an amount(2 x 2)6. The third step is to do the increase of the selected right-hand variable,thus making it a left-hand variable;and simultaneously to modify the left-hand variables, reducing the pivot-row element to zero and thus making it a right-hand variable.For our above example let's do this first by hand:We begin by solving the pivot-row equation for the new left-hand variable x2 in favor of the old one z1,namely 人 Numerical Recipes 10621 43106 x1=2-6E2+x3 x2=专-言x1十吉3 (10.8.11) (outside 腿 North We then substitute this into the old z-row, 2=2x2-4红3=2[店-1+-4红3=号-31-号x3 (10.8.12) and into all other left-variable rows,in this case only 4, x4=8+3[3-x1+6x3]-4x3=9-2x1-x3 (10.8.13)10.8 Linear Programming and the Simplex Method 435 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). The first step in the simplex method is to examine the top row of the tableau, which we will call the “z-row.” Look at the entries in columns labeled by right-hand variables (we will call these “right-columns”). We want to imagine in turn the effect of increasing each right-hand variable from its present value of zero, while leaving all the other right-hand variables at zero. Will the objective function increase or decrease? The answer is given by the sign of the entry in the z-row. Since we want to increase the objective function, only right columns having positive z-row entries are of interest. In (10.8.10) there is only one such column, whose z-row entry is 2. The second step is to examine the column entries below each z-row entry that was selected by step one. We want to ask how much we can increase the right-hand variable before one of the left-hand variables is driven negative, which is not allowed. If the tableau element at the intersection of the right-hand column and the left-hand variable’s row is positive, then it poses no restriction: the corresponding left-hand variable will just be driven more and more positive. If all the entries in any right-hand column are positive, then there is no bound on the objective function and (having said so) we are done with the problem. If one or more entries below a positive z-row entry are negative, then we have to figure out which such entry first limits the increase of that column’s right-hand variable. Evidently the limiting increase is given by dividing the element in the right￾hand column (which is called the pivot element) into the element in the “constant column” (leftmost column) of the pivot element’s row. A value that is small in magnitude is most restrictive. The increase in the objective function for this choice of pivot element is then that value multiplied by the z-row entry of that column. We repeat this procedure on all possible right-hand columns to find the pivot element with the largest such increase. That completes our “choice of a pivot element.” In the above example, the only positive z-row entry is 2. There is only one negative entry below it, namely −6, so this is the pivot element. Its constant-column entry is 2. This pivot will therefore allow x2 to be increased by 2 ÷ |6|, which results in an increase of the objective function by an amount (2 × 2) ÷ |6|. The third step is to do the increase of the selected right-hand variable, thus making it a left-hand variable; and simultaneously to modify the left-hand variables, reducing the pivot-row element to zero and thus making it a right-hand variable. For our above example let’s do this first by hand: We begin by solving the pivot-row equation for the new left-hand variable x2 in favor of the old one x1, namely x1 = 2 − 6x2 + x3 → x2 = 1 3 − 1 6x1 + 1 6x3 (10.8.11) We then substitute this into the old z-row, z = 2x2 − 4x3 = 2
1 3 − 1 6x1 + 1 6x3 − 4x3 = 2 3 − 1 3x1 − 11 3 x3 (10.8.12) and into all other left-variable rows, in this case only x4, x4 =8+3
1 3 − 1 6x1 + 1 6x3 − 4x3 = 9 − 1 2x1 − 7 2x3 (10.8.13)