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

::::
   max\ \  z(\mathbf{x})=5x+8y

::*murrizketa hauekin*

::::
\begin{align}
   x+2y \leq 100,\\
   4x+6y \leq 300,\\
   x \leq 0,\  y \leq 0.
\end{align}

::::max \ \ \begin{bmatrix} 5 & 8 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} 

::*murrizketa hauekin*

::::\begin{bmatrix} 1 & 2 \\ 4 & 6  \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \le \begin{bmatrix} 100 \\ 300  \end{bmatrix}, \, \begin{bmatrix} x \\ y \end{bmatrix} \ge 0. 

Era orokorrean, honela adierazten programazio linealeko ebazkizun bat:

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

::*murrizketa hauekin*

::::::
\begin{align}
   \mathbf{A}\mathbf{x}\leqslant \mathbf{b},\\
   \mathbf{x}\geqslant 0,
\end{align}

## 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.

[thumb|erdian|650px|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

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