Nemlineáris programozás
A nemlineáris programozás ( NLP , N on Linear P programing ) a matematikai programozás olyan esete , amely nem merül ki lineáris programozási probléma felállításában (például, amelyben a célfüggvény vagy megszorítás nemlineáris függvény ) [1] .
A nemlineáris programozás problémája egy bizonyos célfüggvény optimumának megtalálásának problémája a feltételek mellett.
ahol - paraméterek, - korlátozások, - paraméterek száma, - korlátozások száma.
A lineáris programozási problémával ellentétben egy nemlineáris programozási feladatban az optimum nem feltétlenül a megszorítások által meghatározott tartomány határán van.
A probléma megoldásának módszerei
Az egyik módszer, amely lehetővé teszi számunkra, hogy a nemlineáris programozás problémáját egy egyenletrendszer megoldására redukáljuk, a határozatlan Lagrange-szorzók módszere .
Ha a célfüggvény lineáris , a korlátos tér pedig politóp , akkor a probléma egy lineáris programozási probléma, amely jól ismert lineáris programozási megoldásokkal megoldható .
Ha a célfüggvény konkáv (maximalizálási probléma) vagy konvex (minimalizálási probléma), és a kényszerhalmaz konvex, akkor a problémát konvexnek nevezzük, és a legtöbb esetben általános konvex optimalizálási módszerek használhatók .
Ha a célfüggvény a konkáv és konvex függvények aránya (maximalizáláskor), és a megszorítások konvexek, akkor a probléma törtprogramozási technikákkal konvex optimalizálási feladattá alakítható.
A nem konvex feladatok megoldására többféle módszer létezik. Az egyik megközelítés a lineáris programozási problémák speciális megfogalmazásai alkalmazása. Egy másik módszer elágazó és kötött módszereket használ , ahol a probléma konvex (minimalizálási probléma) vagy lineáris közelítésekkel van felosztva, amelyek a partíción belüli összköltség alsó korlátját képezik. A következő szakaszokban egy bizonyos ponton tényleges megoldást kapunk, amelynek költsége megegyezik bármelyik közelítő megoldásra kapott legjobb alsó korláttal. Ez a megoldás optimális, bár talán nem az egyetlen. Az algoritmus korai szakaszában leállítható, biztos lehet benne, hogy az optimális megoldás a talált legjobb ponttól való elfogadható eltérésen belül van; az ilyen pontokat ε-optimálisnak nevezzük. Az ε-optimális pontok lezárása általában szükséges a lezárás végességének biztosításához. Ez különösen nagy, összetett és bizonytalan költségekkel vagy értékekkel járó problémák esetén hasznos, ahol a bizonytalanság megfelelő megbízhatósági becslés alapján határozható meg.
A differenciálási és szabályossági feltételek, a Karush-Kuhn-Tucker (KKT) feltételek biztosítják a szükséges feltételeket a megoldás optimálisságához. A konvexitáshoz ezek a feltételek is elegendőek.
Egy másik módszer a nemlineáris programozási problémák megoldására a dinamikus programozás [2] .
Lásd még
Linkek
Jegyzetek
- ↑ Hadley, 1967 , p. 11, 12.
- ↑ Hadley, 1967 , p. tizenöt.
Irodalom
- Headley J. Nemlineáris és dinamikus programozás. - M . : Mir, 1967. - 506 p.
 Szótárak és enciklopédiák | |
|---|---|
| Bibliográfiai katalógusokban |
|
| Optimalizálási módszerek | |
|---|---|
| Egydimenziós |
|
| Nulla sorrend | |
| Első rendelés | |
| másodrendű | |
| Sztochasztikus | |
| Lineáris programozási módszerek | |
| Nemlineáris programozási módszerek | |