Programazio lineal

Lantegi batek x eta y produktuak ekoizten ditu A eta B makinak erabiliz. x produktuak ematen duen etekina unitate bakoitzeko 5€ da. y produktuak, berriz, 8€ko etekina ematen du unitate bakoitzeko. A makinak ordubeteko epea behar du x produktuaren unitate bat ekoizteko eta 2 ordu y unitate baterako. B makinak 4 eta 6 ordu behar ditu hurrenez hurren x eta y unitateak ekoizteko. A makinan 100 orduko epea dago bi produktuak ekoizteko eta 300 orduko epea B makinan. Zenbat unitate ekoiztu behar dira x eta y produktuetatik etekina maximoa izan dadin?

Programazio linealaren ebazkizunak era aljebraikoaz adierazi ohi dira, batetik maximizatu edo minimizatu beharreko ${\displaystyle z(x)\,}$ helburuko funtzioa eta bestetik murrizketak definituz. Ohikoa da murrizketetan aldagaiak ez-negatiboak izan behar direla ezartzea. Arestiko adibideari dagokion adierazpen aljebraiko eta matriziala hauek dira:

Era orokorrean, honela adierazten programazio linealeko ebazkizun bat:

${\displaystyle max\ \ z(\mathbf {x} )=\mathbf {c} ^{T}\mathbf {x} }$

murrizketa hauekin

${\displaystyle {\begin{aligned}\mathbf {A} \mathbf {x} \leqslant \mathbf {b} ,\\\mathbf {x} \geqslant 0,\end{aligned}}}$

Helburuko funtzioa optimizatu behar duten aldagaiak bi direnean, ebazkizunak modu grafikoan azal eta ebatz daiteke. Lehenengo pausoa murrizketa bakoitzak mugatzen duen eremua finkatzea da. Horretarako, desberdintza bakoitzari dagokion berdintza-ekuazioa irudikatu (murrizketak linealak direnez, zuzenak osatu beharko dira) eta desberdintza betetzen den aldea eman behar da. Ezberdintzek mugatzen dituzten eremuak bateratuz, murrizketa guztiak batera betetzen dituzten puntuen multzoa edo eskualde egingarria lortzen da. Murrizketak linealak direnez, eskualde egingarria multzo konbexu bat da, mugatua (politopo bat izenekoa) edo mugarik gabea. Programazio linealaren ebazkizunaren soluzioa eskualde egingarrian kokatzen da.

Ondoren, helburuko funtzioa irudikatzen da, edozein baliorako. Horrela, zuzen bat lortuko da. Zuzen hauekiko paraleloak helburuko funtzioa ematen dute funtzioaren balio ezberdinetarako. Horrela, helburuko funtzio batetik paraleloak osatuz ebazkizunak eskatzen duen norabidean (max edo min egin behar den), helburuko funtzioaren balioa maximizatu edo minimizatu egiten duen muturreko balioa edo balioak lortuko dira. Balio hauek eskualde egingarriko erpin (soluzio bakarra) edo ertz batean (soluzio anitz) izango dira. Eskualde egingarria ugarik gabea edo infinitua denean, gerta liteke soluzioa ere infinitua izatea (zehatzago, helburuko funtzioa maximizatu edo minimizatu egiten duten aldagaien balioak infinitu izatea).

Zuzen paraleloen norabidea bat dator helburuko funtzioaren koefizienteen bektorearen norabidearekin.

Eskualde egingarria politopo bat denean, soluzioa eskualdeko erpin guztietan helburuko funtzioa kalkulatuz eman daiteke. Helburuko funtzioaren balio handiena ematen duen puntua izango da soluzioa. Bi erpinek helburuko funtzioaren balio bera ematen dutenean, bi erpinak eta beraiek lotzen duten ertz osoko puntuak izango dira soluzio.

Zuzen gorriz eta urdinez, murrizketa-desberdintzei dagokien zuzenak irudikatu dira. Murrizketa-desberdintzei dagozkien aldeak beherantz daude (beherantz dagoen (x=0,y=0) puntuan, 4x+4y<300 eta x+2y<100 betetzen direlako. Bi murrizketen ebaketaz bi murrizketak batera betetzen dituzten puntuen multzoa edo eskualde egingarria (horiz) lortzen da. Ondoren, helburuko funtzioa (5x+8y) irudikatzen da, lehendabizi 250 baliorako, esaterako. Helburu funtzioaren zuzenaren paraleloak marrazten badira, helburuko funtzioaren balio handiagoak lortzen direla ikus daiteke. Eskualde egingarrian (murrizketak betetzen dituzten puntuen multzoan, alegia), helburuko funtzioa (x=50,y=25) puntuan maximizatzen da. Puntu horixe izango da programazio linealaren soluzio-puntua. Bertan z=5×50+8×25=450€ko etekina lortzen da. Ikus daitekeenez, helburuko funtzioari dagokion paraleloen norabidea bat dator helburuko funtzioko koefizienteen (5,8) bektorearen norabidearekin (edo, aiseago ikusteko, (50, 80) bektorearekin norabidearekin). Soluzioa politopoko erpinetarako helburuko funtzioak hartzen dituen balioak kalkulatuz ere eman daiteke soluzioa. Kasu honetan , erpinek helburuko funtzioan ematen dituzten balioak hauek dira: (x=0,y=0)→z=0, (x=0,y=50)→z=400, (x=50,y=25)→z=450, (x=75,y=0)→z=375. Beraz, soluzioa (x=50,y=25) puntuan dago.

Tableau metodoa taula batean garatzen da, izenak adierazten duen bezala, eta helburu-aldagaietarako balio finkoak, ekuazio linealek osatzen duten sinplexaren bitartez ebatziak, txandakatuz frogatzen dira soluzio egingarriaren balioa hobetzen duten ala ez, motxilaren probleman egiten den bezala, lasaierak betez, hau da, ezberdintzak berdintza bihurtuz, aldagai fiktizioen bitartez.

Programazio linealerako algoritmo orokor bat, aldagai kopuru guztietarako erabil daitekeena, simplex metodoa da. 1947 urtean garatua, geroztik bertsio anitz izan dituen algoritmoa izan da, baina guztietan jarraitzen diren oinarrizko pausoak hauek dira:

• Hobezin edo optimoaren bilaketa eskualde egingarriko erpin batetik abiatzen da.
• Ondoko erpin baterako mugimenduak helburuko funtzioaren balioa gehitzen duen egiaztatu behar da.
  • Ondoko erpin batera aldatuz helburuko funtzioaren balioa gehitzen ez bada, erpin hori optimo lokala da (ondoko guztiek baino emaitza hobea ematen baitu) eta eskualde egingarriaren konbexutasuna dela eta, hobezin globala ere badela esan daiteke. Bilaketa hemen bukatzen da.
  • Ondoko erpin batera aldatuz, helburuko funtzioaren balio hobea lortzen bada, erpina aldatu eta balizko soluzio berria berriz ere aztertzen da, helburuko funtzioaren balioa ondoko erpin batera aldatuz gehitu daitekeen egiaztatuz.

Programazio linealeko primal deritzon ebazkizun batetik, bere modu kanonikoan, beste ebazkizun dual bat erator daiteke:

Ebazkizun primala	Ebazkizun duala
${\displaystyle {\begin{aligned}max\ \ c^{T}x;\\Ax\leq b,\\x\geq 0\end{aligned}}}$	${\displaystyle {\begin{aligned}min\ \ b^{T}\lambda$ ;\\A^{T}\lambda \geq c,\\\lambda \geq 0\end{aligned}}}

Ebazkizun primal baten dualaren duala bat dator ebazkizun primalarekin. Aldi berean, ebazkizun primal eta dualaren soluzioak ere loturik daude: soluzio mugatua badu batak, besteak ere hala izango du eta helburuko funtzioen balio optimoak berdinak izango dira; batak soluzio mugagabea badu, besteak ez du soluzio egingarririk izango. Lasaiera osagarriaren teoremaren arabera gainera:

• ebazkizun batean aldagaiaren balio optimoa positiboa bada, beste ebazkizunean dagokion murrizketa saturatu edo betea da;
• ebazkizun batean murrizketa bat saturatzen ez bada, beste ebazkizunean dagokion aldagaiaren balio hobezina 0 da.