c10-8 (779546), страница 3
Текст из файла (страница 3)
If all the entries inany right-hand column are positive, then there is no bound on the objective functionand (having said so) we are done with the problem.If one or more entries below a positive z-row entry are negative, then we haveto figure out which such entry first limits the increase of that column’s right-handvariable. Evidently the limiting increase is given by dividing the element in the righthand column (which is called the pivot element) into the element in the “constantcolumn” (leftmost column) of the pivot element’s row. A value that is small inmagnitude is most restrictive.
The increase in the objective function for this choiceof pivot element is then that value multiplied by the z-row entry of that column. Werepeat this procedure on all possible right-hand columns to find the pivot elementwith 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 onenegative entry below it, namely −6, so this is the pivot element.
Its constant-columnentry is 2. This pivot will therefore allow x2 to be increased by 2 ÷ |6|, which resultsin 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, thusmaking 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.
Forour above example let’s do this first by hand: We begin by solving the pivot-rowequation for the new left-hand variable x2 in favor of the old one x1 , namely436Chapter 10.Minimization or Maximization of FunctionsEquations (10.8.11)–(10.8.13) form the new tableaux1x323− 13− 113x213− 1616x49− 12− 72(10.8.14)The fourth step is to go back and repeat the first step, looking for another possibleincrease of the objective function. We do this as many times as possible, that is, untilall the right-hand entries in the z-row are negative, signaling that no further increaseis possible.
In the present example, this already occurs in (10.8.14), so we are done.The answer can now be read from the constant column of the final tableau. In(10.8.14) we see that the objective function is maximized to a value of 2/3 for thesolution vector x2 = 1/3, x4 = 9, x1 = x3 = 0.Now look back over the procedure that led from (10.8.10) to (10.8.14). You willfind that it could be summarized entirely in tableau format as a series of prescribedelementary matrix operations:• Locate the pivot element and save it.• Save the whole pivot column.• Replace each row, except the pivot row, by that linear combination of itselfand the pivot row which makes its pivot-column entry zero.• Divide the pivot row by the negative of the pivot.• Replace the pivot element by the reciprocal of its saved value.• Replace the rest of the pivot column by its saved values divided by thesaved pivot element.This is the sequence of operations actually performed by a linear programmingroutine, such as the one that we will presently give.You should now be able to solve almost any linear programming problem thatstarts in restricted normal form.
The only special case that might stump you isif an entry in the constant column turns out to be zero at some stage, so that aleft-hand variable is zero at the same time as all the right-hand variables are zero.This is called a degenerate feasible vector. To proceed, you may need to exchangethe degenerate left-hand variable for one of the right-hand variables, perhaps evenmaking several such exchanges.Writing the General Problem in Restricted Normal FormHere is a pleasant surprise. There exist a couple of clever tricks that rendertrivial the task of translating a general linear programming problem into restrictednormal form!First, we need to get rid of the inequalities of the form (10.8.3) or (10.8.4), forexample, the first three constraints in (10.8.7).
We do this by adding to the problemso-called slack variables which, when their nonnegativity is required, convert theinequalities to equalities. We will denote slack variables as yi . There will bem1 + m2 of them. Once they are introduced, you treat them on an equal footingwith the original variables xi ; then, at the very end, you simply ignore them.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).z10.8 Linear Programming and the Simplex Method437For example, introducing slack variables leaves (10.8.6) unchanged but turns(10.8.7) intox1 + 2x3 + y1 = 7402x2 − 7x4 + y2 = 012(10.8.15)x1 + x2 + x3 + x4 = 9(Notice how the sign of the coefficient of the slack variable is determined by whichsense of inequality it is replacing.)Second, we need to insure that there is a set of M left-hand vectors, so that wecan set up a starting tableau in restricted normal form.
(In other words, we need tofind 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 zi .You put exactly one artificial variable into each constraint equation on the followingmodel for the example (10.8.15):z1 = 740 − x1 − 2x3 − y1z2 = −2x2 + 7x4 − y2z3 =12− x2 + x3 − 2x4 + y3(10.8.16)z4 = 9 − x1 − x2 − x3 − x4Our 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 ourobjective function (10.8.6) by a so-called auxiliary objective functionz 0 ≡ −z1 − z2 − z3 − z4 = −(749 12 − 2x1 − 4x2 − 2x3 + 4x4 − y1 − y2 + y3 )(10.8.17)(where the last equality follows from using 10.8.16). We now perform the simplexmethod on the auxiliary objective function (10.8.17) with the constraints (10.8.16).Obviously the auxiliary objective function will be maximized for nonnegative zi ’s ifall the zi ’s are zero.
We therefore expect the simplex method in this first phase toproduce a set of left-hand variables drawn from the xi ’s and yi ’s only, with all thezi ’s being right-hand variables. Aha! We then cross out the zi ’s, leaving a probleminvolving only xi ’s and yi ’s in restricted normal form. In other words, the first phaseproduces an initial feasible basic vector. Second phase: Solve the problem producedby 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? Thatsignals that there is no initial feasible basic vector, i.e., that the constraints given tous are inconsistent among themselves.
Report that fact, and you are done.Here is how to translate into tableau format the information needed for both thefirst and second phases of the overall method. As before, the underlying problemSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).x2 − x3 + 2x4 − y3 =438Chapter 10.Minimization or Maximization of Functionsto be solved is as posed in equations (10.8.6)–(10.8.7).x1x2x3x4y1y2y30113− 12000z1740−10−20−100z200−2070−10z3120−11−2001z49−1−1−1−1000z0−749 12242−411−1(10.8.18)This is not as daunting as it may, at first sight, appear.
The table entries insidethe box of double lines are no more than the coefficients of the original problem(10.8.6)–(10.8.7) organized into a tabular form. In fact, these entries, along withthe values of N , M , m1 , m2 , and m3 , are the only input that is needed by thesimplex method routine below. The columns under the slack variables yi simplyrecord whether each of the M constraints is of the form ≤, ≥, or =; this is redundantinformation with the values m1 , m2 , m3 , as long as we are sure to enter the rows ofthe tableau in the correct respective order.
The coefficients of the auxiliary objectivefunction (bottom row) are just the negatives of the column sums of the rows above,so these are easily calculated automatically.The output from a simplex routine will be (i) a flag telling whether a finitesolution, no solution,or an unbounded solution was found,and (ii) an updated tableau.The output tableau that derives from (10.8.18), given to two significant figures, iszx2x3x4y117.033.334.73.95730.55x1y2y3···−.95−.35−.55−.10.10−.05−.15.05.10−.10−1.05.35−.45.10.90···············(10.8.19)A little counting of the xi ’s and yi ’s will convince you that there are M + 1rows (including the z-row) in both the input and the output tableaux, but that onlyN + 1 − m3 columns of the output tableau (including the constant column) containany useful information, the other columns belonging to now-discarded artificialvariables.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
