Simplex algoritmo

Programazio linealeko ebazkizun bat helburuko funtzio bat, zenbait aldagairen mendean, eta aldagai horiek har ditzaketen balioei buruz murrizketa linealak, desberdintza moduan adierazita. Ohikoak aldagaiei buruzko ez-negatibotasun baldintzak. Murrizketek aldagaiek har ditzaketen balioez osaturiko eskualde egingarri bat definitzen dute. Helburuko funtzioa hoberenatu (maximizatu edo minimizatu) egiten duten aldagaien balioak edo hobezina eskualde egingarriko erpin batean kokatzen da eskualde egingarria politopo konbexu bat osatzen duenean. Eskualde egingarria bornatua ez denean, baliteke hobezina mugatua ez izatea.

Oro har, horrela planteatzen da ebazkizuna modu kanonikoan:

${\displaystyle max\ \ \sum _{j=1}^{n}c_{j}x_{j}}$

murrizketa hauekin

${\displaystyle {\begin{aligned}\sum _{i=1}^{n}a_{ij}x_{j}\leq b_{i}\ \ \ i=1,2,\ldots ,n\\x_{j}\geq 0.\end{aligned}}}$

Simplex algoritmoa garatzeko, alegiazko aldagai izenekoak sortzen dira, zuzenean esanahirik ez dutenak, horiek gehitu edo kenduta murrizketak ezartzen dituzten desberdintzak berdintza bihurtu eta ebazkizuna modu estandarrean adierazteko. Handiago edo berdin motako murrizketak, (-1) balioaz biderkatzen dira, txikiago edo berdin motako murrizketa bihurtzeko. Adibidez:

${\displaystyle a_{11}x_{1}\leq b_{1}\rightarrow a_{11}x_{1}+x_{2}=b_{1}}$

${\displaystyle a_{11}x_{1}\geq b_{1}\rightarrow -a_{11}x_{1}\leq -b_{1}\rightarrow -a_{11}x_{1}+x_{2}\leq -b_{1}}$

Ebazkizunak minimizatzea eskatzen duenean, maximizatze-ebazkizun bihurtzen da modu honetan:

${\displaystyle min\ \ \sum _{j=1}^{n}c_{j}x_{j}\rightarrow max\ \ \sum _{j=1}^{n}-c_{j}x_{j}}$

Simplex algoritmoa taulaz taula garatu ohi da, taula bakoitzean balizko soluzio baten balorazio egin eta taula batetik bestera aldagai bat atera eta beste aldagai bat sartuz. Taula bateko balizko soluzioan parte hartzen duten aldagaien aldagai basiko deritze.

Adibide gisa, programazio linealeko ebazkizun hau planteatzen da:

${\displaystyle max\ \ z(\mathbf {x} )=5x_{1}+8x_{2}}$

murrizketa hauekin

${\displaystyle {\begin{aligned}x_{1}+2x_{2}\leq 100,\\6x_{1}+3x_{2}\leq 300,\end{aligned}}}$

${\displaystyle x_{1}\leq 0,\ x_{2}\leq 0}$.

Alegiazko aldagaiak sortuz:

${\displaystyle max\ \ z(\mathbf {x} )=5x_{1}+8x_{2}+0x_{3}+0x_{4}}$

murrizketa hauekin

${\displaystyle {\begin{aligned}x_{1}+2x_{2}+x_{3}&=100,\\6x_{1}+3x_{2}+x_{4}&=300,\end{aligned}}}$

${\displaystyle x_{1}\leq 0,\ x_{2}\leq 0,\ x_{3}\leq 0,x_{4}\leq 0.}$

Abiapuntu gisa, eskualde egingarriko edozein erpin har daiteke. Kalkulu gehigarririk ez egiteko, eskualde egingarrian izaten den (x₁=0, x₂=0) puntutik has daiteke. Lehenengo taula honela eratzen da:

Taulan murrizketa adina lerro osatzen dira. Lehenengo c_B zutabean, aldagai basikoek helburuko funtzioan dituzten koefizienteak jartzen dira. Koefiziente hauek aldagai guztiak agertzen diren lerroaren gainean ere agertzen dira lagungarri gisa. Bigarren zutabean aldagai basikoak (baloratzen ari den soluzioan agertzen diren aldagaiak) agertzen dira. Ondorengo zutabeetan, murrizketetako koefizienteak agertzen dira aldagai guztietarako. Balio hauek guztiak jarri ondoren, basikoak ez diren aldagaietan sartu beharrekoa zein den erabaki behar da.

Horretarako, aldagai guztiek unitate gehigarri bakoitzeko helburuko funtzioa dakartzaten ekarpenak (c_j-z_j) kalkulatu behar dira, taulan erakutsi bezala, azken lerroan. Ekarpen positibo handiena dakarrena sartzen da basean. Beraz, lehenengo taula honetan x₂ aldagaia sartu behar da basean.

Hurrengo pausoan, basetik zein aldagai atera behar den erabaki behar da. Horretarako, ratioak izeneko azken zutabea eratu behar da. Zutabe hau konstanteen zutabea zati, murrizketa-matrizean, basera sartu behar den aldagaiaren koefizienteen zutabea eginez kalkulatzen da. Kasu honetan, x₂ aldagaia sartu behar denez, murrizketa-matrizeko bigarren zutabeko koefizienteak hartzen dira (2 eta 3). Ratio txikiena duen aldagaia atera behar da, murrizketa-matrizeko koefizientea positiboa den guztietan: kasu honetan, x₃ baztertu behar da.

Jarraian bigarren taula osatu behar da. Horretarako gontz-eragiketa izenekoa garatu behar da. Pibota sartu behar den aldagaiaren zutabean eta atera behar den aldagaiaren errenkadan dagoen zenbakia da. gontz hori 1 bihurtu behar da eta bere zutabeko beste balio guztiak 0 bihurtu behar dira. Bihurketa hauek Gauss-Jordan algoritmoa erabiliz egiten dira: gontza 1 bihurtzeko bere lerroko koefiziente guztiak, konstanteak barne, gontzaren balioaz zatitu behar dira; bere zutabeko elementu guztiak 0 bihurtzeko, pibotaren lerroa konstante batez biderkatu eta beste lerroak gehitu behar dira. Honako bigarren taula honetan, lehenengo lerroa lehenengo taulako lehenengo lerroa zati 2 da; bigarren lerroa lehenengo taulako lehenengo bider (-3/2) gehi bigarren lerroa da.

Bigarren taula osaturik, x₄ aldagaia atera eta x₁ aldagaia sartu behar da. Honako hirugarren taula honetan, Gauss Jordan algoritmoari jarraiki, bigarren lerroa aurreko bigarren lerroa bider (2/9) da; bigarren lerroa aurreko bigarren lerroa bider (-1/9) gehi aurreko lehenengo lerroa da.

x₁ eta x₂ aldagaiak basean daudelarik, aldagai guztien ekarpenak negatiboak edo 0 direnez, ez da ezer irabazten aldagai berriak sartzean. Beraz, soluzio optimora heldu da: x₁=33.33 eta x₂=33.33, horrela helburuko funtzioan 5x₁+8x₂=433.33 lortuz.

Jatorrizko simplex algoritmoaren bertsio ezberdinak garatu dira. Horietako bat simplex algoritmo berrikusia da, programazio linealeko ebazkizun handietan (hainbat aldagai eta murrizketa dutenetan, alegia) konputazio-lna txikiagoa eskatzen duena hobezin edo optimora heltzeko. Algoritmoaren bertsio berrikusi hau da, gainera, programazio linealeko softwarean erabili ohi dena.

Simplex algoritmoa eskualde egingarriko erpin batetik bestera mugitzen da, aldi bakoitzean soluzio hobetuz, harik eta hobezinera heldu arte. Hau da, simplex metodoan egingarritasuna ziurtatuz, hobezintasuna bilatzen da. Simplex algoritmo dualaren bitartez, berriz, hobezintasuna ziurtaturik, egingarritasuna bilatzen da, hau da, egingarria ez den soluzio hobezin batetik abiatzen da, pausoz pauso egingarritasunera joaz.

Aplikazio orokorra duen metodoa erabiltzen da, baina bereziki erabiltzen da abiapuntuko murrizketa matrizeko alde konstantean balio guztiak negatiboak direnean (murrizketak handiago edo berdin motakoak direnean gertatzen da hau), kasu horretan simplex metodo estandarra ezin baita aurrera eraman. Izan ere, aldagaien soluzio-balioak ematen dituen konstanteen zutabea negatiboa denean, soluzioa negatiboa da eta ez egingarria da, aurrez aldagaien ez-negatibotasun murrizketak ezarri direlako.

Abiapuntua simplex algoritmo estandarreko lehenengo taula da. Bertatik balio txikiena duen aldagai basikoa basetik ateratzen da. Sartu beharreko aldagaia zein den erabakitzeko, c_j-z_j zutabeko balioak basetik ateratako aldagairen lerroko koefiziente negatiboez zatitu eta bertatik txikiena ematen duen aldagaia hartzen da. Lerroko koefiziente guztiak positiboak edo 0 badira, ebazkizunak ez du soluzio egingarririk.

Taula batetik bestera aldatzeko, Gauss-Jordan aldakuntzak egiten dira, sinplex algoritmo estandarrean bezala. Soluzio hobezinera aldagai basikoen balio guztiak positiboak edo 0 direnean heltzen da.