c10-8 (779546), страница 5
Текст из файла (страница 5)
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).if (iposv[ip] >= (n+m1+m2+1)) {Exchanged out an artificial variablefor (k=1;k<=nl1;k++)for an equality constraint. Makeif (l1[k] == kp) break;sure it stays out by removing it--nl1;from the l1 list.for (is=k;is<=nl1;is++) l1[is]=l1[is+1];} else {kh=iposv[ip]-m1-n;if (kh >= 1 && l3[kh]) {Exchanged out an m2 type constraintl3[kh]=0;for the first time.
Correct the++a[m+2][kp+1];pivot column for the minus signfor (i=1;i<=m+2;i++)and the implicit artificial varia[i][kp+1] = -a[i][kp+1];able.}}is=izrov[kp];Update lists of left- and right-handizrov[kp]=iposv[ip];variables.iposv[ip]=is;}Still in phase one, go back to the}for(;;).End of phase one code for finding an initial feasible solution. Now, in phase two, optimizeit.for (;;) {simp1(a,0,l1,nl1,0,&kp,&bmax);Test the z-row for doneness.if (bmax <= EPS) {Done. Solution found. Return with*icase=0;the good news.FREEALL return;}simp2(a,m,n,&ip,kp);Locate a pivot element (phase two).if (ip == 0) {Objective function is unbounded. Re*icase=1;port and return.FREEALL return;}simp3(a,m,n,ip,kp);Exchange a left- and a right-handis=izrov[kp];variable (phase two),izrov[kp]=iposv[ip];iposv[ip]=is;}and return for another iteration.442Chapter 10.Minimization or Maximization of Functionselsetest=fabs(a[mm+1][ll[k]+1])-fabs(*bmax);if (test > 0.0) {*bmax=a[mm+1][ll[k]+1];*kp=ll[k];}}}#define EPS 1.0e-6void simp2(float **a, int m, int n, int *ip, int kp)Locate a pivot element, taking degeneracy into account.{int k,i;float qp,q0,q,q1;*ip=0;for (i=1;i<=m;i++)if (a[i+1][kp+1] < -EPS) break;Any possible pivots?if (i>m) return;q1 = -a[i+1][1]/a[i+1][kp+1];*ip=i;for (i=*ip+1;i<=m;i++) {if (a[i+1][kp+1] < -EPS) {q = -a[i+1][1]/a[i+1][kp+1];if (q < q1) {*ip=i;q1=q;} else if (q == q1) {We have a degeneracy.for (k=1;k<=n;k++) {qp = -a[*ip+1][k+1]/a[*ip+1][kp+1];q0 = -a[i+1][k+1]/a[i+1][kp+1];if (q0 != qp) break;}if (q0 < qp) *ip=i;}}}}void simp3(float **a, int i1, int k1, int ip, int kp)Matrix operations to exchange a left-hand and right-hand variable (see text).{int kk,ii;float piv;piv=1.0/a[ip+1][kp+1];for (ii=1;ii<=i1+1;ii++)if (ii-1 != ip) {a[ii][kp+1] *= piv;for (kk=1;kk<=k1+1;kk++)if (kk-1 != kp)a[ii][kk] -= a[ip+1][kk]*a[ii][kp+1];}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).}10.8 Linear Programming and the Simplex Method443for (kk=1;kk<=k1+1;kk++)if (kk-1 != kp) a[ip+1][kk] *= -piv;a[ip+1][kp+1]=piv;}Every linear programming problem in normal form with N variables and Mconstraints has a corresponding dual problem with M variables and N constraints.The tableau of the dual problem is, in essence, the transpose of the tableau of theoriginal (sometimes called primal) problem.
It is possible to go from a solutionof the dual to a solution of the primal. This can occasionally be computationallyuseful, but generally it is no big deal.The revised simplex method is exactly equivalent to the simplex method in itschoice of which left-hand and right-hand variables are exchanged. Its computationaleffort is not significantly less than that of the simplex method. It does differ inthe organization of its storage, requiring only a matrix of size M × M , rather thanM × N , in its intermediate stages. If you have a lot of constraints, and memorysize is one of them, then you should look into it.The primal-dual algorithm and the composite simplex algorithm are two different methods for avoiding the two phases of the usual simplex method: Progressis made simultaneously towards finding a feasible solution and finding an optimalsolution.
There seems to be no clearcut evidence that these methods are superiorto the usual method by any factor substantially larger than the “tender-loving-carefactor” (which reflects the programming effort of the proponents).Problems where the objective function and/or one or more of the constraints arereplaced by expressions nonlinear in the variables are called nonlinear programmingproblems.
The literature on such problems is vast, but outside our scope. The specialcase of quadratic expressions is called quadratic programming. Optimization problems where the variables take on only integer values are called integer programmingproblems, a special case of discrete optimization generally. The next section looksat a particular kind of discrete optimization problem.CITED REFERENCES AND FURTHER READING:Bland, R.G. 1981, Scientific American, vol. 244 (June), pp.
126–144. [1]Dantzig, G.B. 1963, Linear Programming and Extensions (Princeton, NJ: Princeton UniversityPress). [2]Kolata, G. 1982, Science, vol. 217, p. 39. [3]Gill, P.E., Murray, W., and Wright, M.H. 1991, Numerical Linear Algebra and Optimization, vol. 1(Redwood City, CA: Addison-Wesley), Chapters 7–8.Cooper, L., and Steinberg, D. 1970, Introduction to Methods of Optimization (Philadelphia: Saunders).Gass, S.T. 1969, Linear Programming, 3rd ed. (New York: McGraw-Hill).Murty, K.G. 1976, Linear and Combinatorial Programming (New York: Wiley).Land, A.H., and Powell, S.
1973, Fortran Codes for Mathematical Programming (London: WileyInterscience).Kuenzi, H.P., Tzschach, H.G., and Zehnder, C.A. 1971, Numerical Methods of MathematicalOptimization (New York: Academic Press). [4]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).Other Topics Briefly Mentioned444Chapter 10.Minimization or Maximization of FunctionsStoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag),§4.10.Wilkinson, J.H., and Reinsch, C.
1971, Linear Algebra, vol. II of Handbook for Automatic Computation (New York: Springer-Verlag). [5]The method of simulated annealing [1,2] is a technique that has attracted significant attention as suitable for optimization problems of large scale, especially oneswhere a desired global extremum is hidden among many, poorer, local extrema. Forpractical purposes, simulated annealing has effectively “solved” the famous travelingsalesman problem of finding the shortest cyclical itinerary for a traveling salesmanwho must visit each of N cities in turn.
(Other practical methods have also beenfound.) The method has also been used successfully for designing complex integratedcircuits: The arrangement of several hundred thousand circuit elements on a tinysilicon substrate is optimized so as to minimize interference among their connectingwires [3,4] . Surprisingly, the implementation of the algorithm is relatively simple.Notice that the two applications cited are both examples of combinatorialminimization. There is an objective function to be minimized, as usual; but the spaceover which that function is defined is not simply the N -dimensional space of Ncontinuously variable parameters. Rather, it is a discrete, but very large, configurationspace, like the set of possible orders of cities, or the set of possible allocations ofsilicon “real estate” blocks to circuit elements.
The number of elements in theconfiguration space is factorially large, so that they cannot be explored exhaustively.Furthermore, since the set is discrete, we are deprived of any notion of “continuingdownhill in a favorable direction.” The concept of “direction” may not have anymeaning in the configuration space.Below, we will also discuss how to use simulated annealing methods for spaceswith continuous control parameters, like those of §§10.4–10.7. This application isactually more complicated than the combinatorial one, since the familiar problem of“long, narrow valleys” again asserts itself.
Simulated annealing, as we will see, tries“random” steps; but in a long, narrow valley, almost all random steps are uphill!Some additional finesse is therefore required.At the heart of the method of simulated annealing is an analogy with thermodynamics, specifically with the way that liquids freeze and crystallize, or metals cooland anneal. At high temperatures, the molecules of a liquid move freely with respectto one another.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
