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:

$\max _{x\in X}f(x)$ funtzio objektibo bat maximizatzea

edo

$\min _{x\in X}f(x)$ objektibo (kostu) funtzio bat minimizatu

non

$f:R^{n}\to R$

$X\subseteq R^{n}.$

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

Lerroaren muga-espazioarekin ebakitzeak soluzioa adierazten du.

Arazo sinple bat honako mugen bitartez defini daiteke:

x1 ≥ ₀

x2 ≥ ₀

x ₁ ² + x ₂ ² ≥ 1

x ₁ ² + x ₂ ² ≤ 2

maximizatu beharreko funtzio objektibo batekin

f (x) = x1 _{+ x2}

non x = (x ₁, x ₂) den

Hiru dimentsioko adibidea

Goiko gainazalaren erdiguneko muga-espazioaren ebakidurak adierazten du soluzioa.

Beste problema sinple bat honako mugak definitzen du: x ₁ ² − x ₂ ² + x ₃ ² ≤ 2

x ₁ ² + x ₂ ² + x ₃ ² ≤ 10

maximizatu beharreko funtzio objektibo batekin

f ( x ) = x ₁ x ₂ + x ₂ x ₃

non x = (x ₁, x ₂, x ₃) den

Bibliografia

• Avriel, Mordecai (2003). Programazio ez-lineala: analisia eta metodoak. Dover argitaletxea. ISBN 0-486-43227-0 .
• Bazaraa, Mokhtar S. eta Shetty, C.M. (1979). Programazio ez-lineala. Teoria eta algoritmoak. John Wiley & Sons . ISBN 0-471-78610-1 .
• Nocedal, Jorge eta Wright, Stephen J. (1999). Zenbakizko Optimizazioa. Springer. ISBN 0-387-98793-2 .
• Bertsekas, Dimitri P. (1999). Programazio ez-lineala: 2. edizioa. Atenea Zientifikoa. ISBN 1-886529-00-0 .

Ikus, gainera

• optimizazioa
• Lerro doikuntza
• Karratu txikienen metodoa
• Programazio lineala

Kanpo estekak

• Programazio ez lineal (Gaztelaniaz)
• Programazio ez-linealaren ohiko galderak (Ingelesez)
• Matematika Programazio Glosarioa (Ingelesez)
• 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

• Datuak: Q769909