Simplex algoritmo

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu

Matematikan, simplex algoritmoa programazio linealeko ebazkizunak aztertu eta ebazteko metodo bat da. Programazio linealeko metodoak helburuko funtzio linealak, murrizketa linealekin batera, optimizatzeko erabiltzen dira. Hobezina edo optimoa murrizketek osatzen duten eskualde egingarriko eremuan aurkitu behar denez, simplex algoritmoak erpin hauetan zehar egiten du soluzioaren bilaketa, ondoko erpin batera aldatzeak helburu funtzioaren balioren hobekuntza dakarren egiaztatuz. Erpinaren aldaketak soluzio hobea ekartzen ez badu, aztertzen ari den erpina hobezina izango da. Simplex algoritmoa George Dantzig matematikariak garatu zuen 1947 urtean.

Ebazkizuna[aldatu | aldatu iturburu kodea]

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:


   max\ \  \sum_{j=1}^nc_jx_j


murrizketa hauekin



\begin{align}
\sum_{i=1}^na_{ij}x_j \leq b_i  \ \ \ i=1,2,\ldots,n \\
x_j \geq 0.
\end{align}

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:


a_{11}x_1 \leq b_1 \rightarrow a_{11}x_1 +x_2 =  b_1


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:



   min\ \  \sum_{j=1}^nc_jx_j \rightarrow max \ \ \sum_{j=1}^n-c_jx_j

Adibidea[aldatu | aldatu iturburu kodea]

Minimizatze ebazkizuna baten bihurketa eta alegiazko aldagaien sorrera adibide honetan ikus daitezke:


   min\ \  4x_1+2x_2
murrizketa hauekin

\begin{align}
3x_1+x_2 \leq 60\\
2x_1+4x_2 \leq 80\\
x_1,x_2 \geq 0.
\end{align}

   max\ \  -4x_1-2x_2
murrizketa hauekin

\begin{align}
3x_1+x_2+x_3 &= 60\\
2x_1+4x_2+x_4 &= 80\\
x_1,x_2, x_3, x_4 \geq 0.
\end{align}

Simplex algoritmoa[aldatu | aldatu iturburu kodea]

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:


   max\ \  z(\mathbf{x})=5x_1+8x_2


murrizketa hauekin



\begin{align}
   x_1+2x_2 \leq 100,\\
   6x_1+3x_2 \leq 300,
   \end{align}
x_1 \leq 0,\  x_2 \leq 0.


Alegiazko aldagaiak sortuz:


   max\ \  z(\mathbf{x})=5x_1+8x_2+0x_3+0x_4


murrizketa hauekin



\begin{align}
   x_1+2x_2+x_3 &= 100,\\
   6x_1+3x_2+x_4 &= 300,
   \end{align}
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 (x1=0, x2=0) puntutik has daiteke. Lehenengo taula honela eratzen da:


1. taula
cB B basea cj Konstanteak Ratioak
5 8 0 0
x1 x2 x3 x4
0 x3 1 2 1 0 100 100/2=50
0 x4 6 3 0 1 300 300/3=100
cj-zj 5-1×0-4×0=5 8-6×0-3×0=8 0-1×0-0×0=0 0-0×0-0×0=0 Z=0


Taulan murrizketa adina lerro osatzen dira. Lehenengo cB 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 (cj-zj) kalkulatu behar dira, taulan erakutsi bezala, azken lerroan. Ekarpen positibo handiena dakarrena sartzen da basean. Beraz, lehenengo taula honetan x2 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, x2 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, x3 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.

2. taula
cB B basea cj Konstanteak Ratioak
5 8 0 0
x1 x2 x3 x4
8 x2 1/2 1 1/2 0 50 50/(1/2)=100
0 x4 9/2 0 -3/2 1 150 150/(9/2)=22.22
cj-zj 5-(1/2)×8-(9/2)×0=1 8-1×8-0×0=0 0-(1/2)×8-(-3/2)×0=-4 0-0×8-1×0=0 Z=400


Bigarren taula osaturik, x4 aldagaia atera eta x1 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.


3. taula
cB B basea cj Konstanteak Ratioak
5 8 0 0
x1 x2 x3 x4
8 x2 0 1 4/6 -1/9 33.33 -
5 x1 1 0 -3/9 2/9 33.33 -
cj-zj 5-0×8-5×1=5 8-1×8-0×0=0 0-(4/6)×8-(-3/9)×5=-66/18 0- (-1/9)×8-(2/9)×5=-2/9 Z=433.33


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

Simplex algoritmo berrikusia[aldatu | aldatu iturburu kodea]

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 algoritmo duala[aldatu | aldatu iturburu kodea]

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, cj-zj 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.