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:

$x_{n+i}=b_{i}-\sum _{i=1}^{n}a_{ij}x_{j}$

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

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

Artikulu hau matematikari buruzko zirriborroa da. Wikipedia lagun dezakezu edukia osatuz.