Programazio ez lineal

Matematikan, programazio ez lineala (PEL) da: aldagai erreal ezezagunen multzo batean, murrizketa multzo baten mende dauden berdintasun eta desberdintasunen sistema ebazteko prozesua, maximizatzeko (edo minimizatzeko) funtzio objektibo batekin, murrizketa batzuk edo funtzio objektiboa linealak ez direnean.

Problemaren formulazio matematikoa 
Programazio ez linealaren problema oso erraz adieraz daiteke:

  funtzio objektibo bat maximizatzea

edo

  objektibo (kostu) funtzio bat minimizatu

non

Arazoak konpontzeko metodoak 
f funtzio objektiboa lineala bada eta espazio mugatua politopoa bada, problema programazio linealeko problema da, eta programazio linealeko algoritmo ezagunetako bat erabiliz ebatz daiteke.

Funtzio objektiboa ahurra (maximizazio-arazoa) edo ganbila (minimizazio-arazoa) bada eta muga-multzoa ganbila bada, orduan, optimizazio-metodo orokorra erabil daiteke.

Hainbat metodo daude ganbilak ez diren problemak ebazteko. Horietako bat programazio linealeko probleman formulazio bereziak erabiltzea da. Beste metodo batek Adarkatze- eta Inausketa-teknikak erabiltzean datza, arazoa azpi-zatiketatan banatzen denean, azpi-zatiketa bakoitzeko kostu osoaren muga txikiago bat osatzen duten hurbilketen bidez ebazteko. Ondoz ondoko azpizatiketen bidez, gutxi gorabeherako soluzioren batek lortutako behe-mugarik onenaren kostua berdina edo txikiagoa den soluzio bat lortuko du. Irtenbide hori ezin hobea da, agian bakarra ez den arren. Algoritmoa lehenago gelditu daiteke, irtenbide onena ehuneko mugatu baten aurkitutako soluzioa baino hobea izango dela bermatuta. Hori bereziki arazo garrantzitsuetan eta bereziki zailetan erabiltzen da eta arazoak kostu edo balio ziurgabeak dituenean, non ziurgabetasuna fidagarritasun-maila egoki batean balioetsi daiteken.

Karush-Kuhn-Tucker-en baldintzek irtenbide optimoa izateko beharrezko baldintzak eskaintzen dituzte.

Adibideak

Bi dimentsioko adibidea 

Arazo sinple bat honako mugen bitartez defini daiteke:

 x1 ≥ 0
 x2 ≥ 0
 x 1 2 + x 2 2 ≥ 1
 x 1 2 + x 2 2 ≤ 2

maximizatu beharreko funtzio objektibo batekin

 f (x) = x1 + x2

non x = (x 1, x 2) den

Hiru dimentsioko adibidea 

Beste problema sinple bat honako mugak definitzen du: x 1 2 − x 2 2 + x 3 2 ≤ 2

 x 1 2 + x 2 2 + x 3 2 ≤ 10

maximizatu beharreko funtzio objektibo batekin

 f ( x ) = x 1 x 2 + x 2 x 3

non x = (x 1, x 2, x 3) den

Erreferentziak

Bibliografia 
 Avriel, Mordecai (2003). Programazio ez-lineala: analisia eta metodoak. Dover argitaletxea.  .
 Bazaraa, Mokhtar S. eta Shetty, C.M. (1979). Programazio ez-lineala. Teoria eta algoritmoak. John Wiley &amp; Sons .  .
 Nocedal, Jorge eta Wright, Stephen J. (1999). Zenbakizko Optimizazioa. Springer.  .
 Bertsekas, Dimitri P. (1999). Programazio ez-lineala: 2. edizioa. Atenea Zientifikoa.  .

Ikus, gainera 
 optimizazioa
 Lerro doikuntza
 Karratu txikienen metodoa
 Programazio lineala

Kanpo estekak 

 Programazio ez lineal 
 Programazio ez-linealaren ohiko galderak 
 Matematika Programazio Glosarioa 
 Programazio ez-linealaren inkesta OR/MS Gaur

Softwarea 
 AIMMS Optimization Modeling AIMMS — Programazio ez-lineala barne hartzen du industriako soluzioetan (doako proba, proba lizentzia eskuragarri);
 AMPL ebazteko softwarea - Doakoa ikasleentzat
 Artelys Knitro optimizatzailea programazio ez-linealean espezializatua ( probako bertsioa eskuragarri )
 GAMS - Doako bertsioa eskuragarri dago ikasleentzat

Ikerketa operatiboa