Programazio lineal

Matematikan, programazio lineala helburu-funtzio lineal bat eta murrizketa linealak (berdintzazkoak zein desberdintzazkoak) dituen optimizazio-ebazkizunak aztertu eta optimo edo hobezina, hau da, helburuko funtzioa optimizatzen duten aldagaien balioak, aurkitzeko teknika-multzoa da. Ikerketa operatiboaren barnean kokatzen den teknika-multzoa da eta aplikazio anitz ditu, hala nola baliabideen esleipenean (eskura dagoen baliabide bakoitzetik zer kopuru hartu behar den etekina maximizatu eta kostua minimizatzeko), dieta-diseinuan (zein elikagai hautatu behar diren kostu txikienarekin, mineral eta bestelako gaien beharrak betez aldi berean), logistikan (garraio-kostuak minimizatzeko enpresa bateko lantegiek zenbat ekoiztu behar duten, lantegien ahalmena eta merkatuen eskariak asetzeko eta joko-teorian (jokalariek burutu beharreko estrategiak itxarondako etekina maximoa izan dadin).

Adibide bat 

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?

Adierazpen aljebraikoa 

Programazio linealaren ebazkizunak era aljebraikoaz adierazi ohi dira, batetik maximizatu edo minimizatu beharreko  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:

murrizketa hauekin

murrizketa hauekin

Era orokorrean, honela adierazten programazio linealeko ebazkizun bat:

</center>

murrizketa hauekin

Ebazpen grafikoa 

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.

Tableau metodoa 

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.

Simplex metodoa 

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.

Ebazkizun primala eta duala 

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

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.

Kanpo estekak 

Ikerketa operatiboa
Optimizazio matematikoa
Algoritmo geometrikoak