Simplex algoritmo

Matematikan, simplex algoritmoa programazio linealeko ebazkizunak aztertu eta ebazteko metodo bat da. Programazio linealeko metodoak helburuko funtzio linealak, murrizketa linealekin batera, hobereneratzo erabiltzen dira. Hobezina murrizketek osatzen duten eskualde egingarriko eremuan aurkitu behar denez, simplex metodoak 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 metodoa George Dantzig matematikariak garatu zuen 1947 urtean.

Ebazkizuna

Programazio linealeko ebazkizun bat helburuko funtzio bat, zenbait aldagairen mendean, eta aldagai horiek har ditzaketen balioei buruz murrizketa linealak, ezberdintza moduan adierazita. Ohikoak aldagaiei buruzko ez-negatibotasun baldintzak. Murrizketek aldagaiek har ditzaketen balioez osaturiko eskualde egingarri bat definitzen dute. Helburuko funtzioa hoberenatu (maximotu edo minimotu) 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.

Orohar, horrela planteatzen da ebazkizuna:

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

murrizketa hauekin

${\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 ezberdintzak berdintza bihurtzeko. Adibidez:

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

$a_{11}x_{1}\geq b_{1}\rightarrow a_{1}x_{1}-x_{2}=b_{1}$

Ebazkizunak minimotzea eskatzen duenean, maximotze-ebazkizun bihurtzen da modu honetan:

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

Adibidea

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

$min\ \ 4x_{1}+2x_{2}$

murrizketa hauekin

${\begin{aligned}3x_{1}+x_{2}\leq 60\\2x_{1}+4x_{2}\leq 80\\x_{1},x_{2}\geq 0.\end{aligned}}$

$max\ \ -4x_{1}-2x_{2}$

murrizketa hauekin

${\begin{aligned}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{aligned}}$

Algoritmoa

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{aligned}x_{1}+2x_{2}\leq 100,\\6x_{1}+3x_{2}\leq 300,\end{aligned}}$

$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{aligned}x_{1}+2x_{2}+x_{3}&=100,\\6x_{1}+3x_{2}+x_{4}&=300,\end{aligned}}$

$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:

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 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 pibote-eragiketa izenekoa garatu behar da. Pibotea sartu behar den aldagaiaren zutabean eta atera behar den aldagaiaren errenkadan dagoen zenbakia da. Pibote hori 1 bihurtu behar da eta bere zutabeko beste balio guztiak 0 bihurtu behar dira. Bihurketa hauek Gauss-Jordan algoritmoa erabiliz egiten dira: pibotea 1 bihurtzeko bere lerroko koefizienete guztiak, konstanteak barne, pibotearen balioaz zatitu behar dira; bere zutabeko elementu guztiak 0 bihurtzeko, pibotaren lerroa konstante batez biderkatu eta beste lerroak gehitu behar dira.

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	5-(1/2)×8-(-3/2)×0=-4	0-0×8-1×0=0	Z=400

Bigarren taula osaturik, x₄ aldagaia atera eta x₁ aldagaia sartu behar da.