Mètode símplex
En optimització matemàtica, el mètode símplex (o algorisme símplex) de Dantzig és un algorisme popular de programació linal.[1][2][3][4][5] La revista Computing in Science and Engineering el va llistar com un del 10 algorisme més importants del segle xx.[6]
El nom de l'algorisme es deriva del concepte d'un símplex i va ser derivat per T. S. Motzkin.[7] Els símplex no s'utilitzen en el mètode, de fet, però una interpretació del mètode és que opera amb cons simplicials, i això es converteix en símplexs amb una restricció addicional.[8][9][10][11] Els cons simplicials en qüestió són les cantonades (per exemple, els veïns dels vèrtexs) d'un objecte geomètric anomenat polítop. La forma d'aquest polítop és definida per les restriccions aplicades en la funció objectiu.
Visió global[modifica]
El mètode símplex opera en programació lineal en forma canònica:
- Maximitzar
- Subjecte a
amb les variables del problema, són els coeficients de la funció objectiu, A és una matriu p×n, i constants amb . Hi ha un procés directe per passar qualsevol programa lineal a forma canònica, així que aquest resultat és general per a tots els casos.
En termes geomètrics, la regió factible
També es pot demostrar que si un punt extrem no és un punt que maximitza la funció objectiu, llavors sempre hi ha una aresta (o vora) que conté aquest punt tal que la funció objectiu augmenta estrictament a través de l'aresta a mesura que s'allunya del punt.[12] Si la vora és finita llavors la vora connecta a un altre punt extrem on la funció objectiva té un valor més gran, altrament la funció objectiva és il·limitada sobre la vora i el programa lineal no té cap solució. L'algoritme símplex aplica aquesta idea recurrent al llarg de les vores del polítop a punts extrems amb valors objectius cada vegada més grans. Això continua fins que el valor màxim és assolit o s'arriba a una vora il·limitada, arribant a la conclusió que el problema no té cap solució. L'algoritme sempre acaba perquè el nombre de vèrtexs en el polítop és finit; a més com que sempre es salta entre vèrtexs cap a la mateixa direcció (la de la funció objectiva), s'espera que el nombre de vèrtexs pels quals es passa serà petit.
La solució d'un programa lineal s'obté en dos passos. En el primer pas, anomenat Fase I, es troba un punt extrem inicial. Depenent de la naturalesa del programa això pot ser trivial, però en general pot ser solucionat aplicant l'algorisme símplex a una versió modificada del programa original. Els resultats possibles de la Fase I són que o bé es troba una solució factible bàsica o bé la regió factible és buida. En aquest últim cas el programa lineal s'anomena inviable. En el segon pas, la Fase II, s'aplica l'algorisme de símplex utilitzant la solució factible bàsica trobada a la Fase I com a punt inicial. Els resultats possibles de la Fase II són o bé una solució factible bàsica òptima o bé una vora infinita en el qual la funció objectiu no té frontera inferior.[3][13][14]
Història[modifica]
George Dantzig treballava planejant mètodes per a les forces aèries de l'exèrcit americà durant la Segona Guerra Mundial utilitzant una calculadora. L'any 1946 els seus companys el van desafiar a mecanitzar el procés de planificació per atreure'l a no haver de treballar més. Dantzig va formular el problema com a inequacions lineals inspirat pel treball de Wassily Leontief. Tanmateix, en aquell moment no havia afegir encara la funció objectiu com a part de la formulació. Sense un objectiu, una gran quantitat de solucions poden ser factibles, i per tant, per trobar la "millor" solució factible, s'han d'utilitzar les regles bàsiques especificades per l'exèrcit per descriure com s'obtenen els objectius en comptes d'especificar un objectiu en si. La visió principal de Dantzig va ser descobrir que la majoria d'aquestes regles bàsiques es poden traduir a funcions objectiu lineals que s'han de maximitzar.[15] El desenvolupament del mètode símplex va evolucionar durant un període que va durar el voltant d'un any.[16]
Forma binòmica[modifica]
La transformació d'un programa lineal a un en forma canònica es pot obtenir de la següent manera.[17] Primer, per cada variable amb una frontera inferior inferior a 0, s'introdueix una variable nova que representa la diferència entre el variable i la frontera. La variable original llavors pot ser eliminada per substitució. Per exemple, donat la restriccióː
Vegeu també[modifica]
Referències[modifica]
- ↑ Murty, Katta G. (1983).
- ↑ Richard W. Cottle, ed.
- ↑ 3,0 3,1 George B. Dantzig and Mukund N. Thapa. 1997.
- ↑ George B. Dantzig and Mukund N. Thapa. 2003.
- ↑ Michael J. Todd (February 2002).
- ↑ Computing in Science and Engineering, volume 2, no. 1, 2000 html version
- ↑ Murty (1983, Comment 2.2)
- ↑ Murty (1983, Note 3.9)
- ↑ Stone, Richard E.; Tovey, Craig A. (1991).
- ↑ Stone, Richard E.; Tovey, Craig A. (1991).
- ↑ Strang, Gilbert (1 June 1987).
- ↑ Murty (1983, p. 137, Section 3.8)
- ↑ Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
- ↑ Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008.
- ↑ "Reminiscences about the origins of linear programming"[Enllaç no actiu] (PDF).
- ↑ Albers and Reid (1986).
- ↑ Murty (1983, Section 2.2)