Ikke-lineær programmering
Ikke- lineær programmering ( NLP , N on Linear P rogramming ) er et tilfælde af matematisk programmering , der ikke bunder i at sætte et lineært programmeringsproblem (f.eks. hvor den objektive funktion eller begrænsning er en ikke-lineær funktion ) [1] .
Problemet med ikke-lineær programmering stilles som problemet med at finde det optimale af en bestemt objektiv funktion under betingelserne
hvor - parametre, - restriktioner, - antal parametre, - antal restriktioner.
I modsætning til et lineært programmeringsproblem ligger det optimale i et ikke-lineært programmeringsproblem ikke nødvendigvis på grænsen af det område, der er defineret af begrænsningerne.
Metoder til at løse problemet
En af de metoder, der tillader os at reducere problemet med ikke-lineær programmering til at løse et ligningssystem , er metoden med ubestemte Lagrange-multiplikatorer .
Hvis objektivfunktionen er lineær , og det afgrænsede rum er en polytop , så er problemet et lineært programmeringsproblem, der kan løses ved hjælp af velkendte lineære programmeringsløsninger .
Hvis objektivfunktionen er konkav (maksimeringsproblem) eller konveks (minimeringsproblem), og begrænsningssættet er konveks, så kaldes problemet konveks , og i de fleste tilfælde kan generelle konvekse optimeringsmetoder bruges .
Hvis den objektive funktion er forholdet mellem konkave og konvekse funktioner (ved maksimering), og begrænsningerne er konvekse, så kan problemet transformeres til et konveks optimeringsproblem ved hjælp af fraktioneret programmeringsteknikker.
Der er flere metoder til at løse ikke-konvekse problemer. En tilgang er at bruge specielle formuleringer af lineære programmeringsproblemer. En anden metode involverer brugen af branch and bound metoder , hvor problemet er underopdelt for at blive løst med konvekse (minimeringsproblem) eller lineære tilnærmelser, der danner en nedre grænse for de samlede omkostninger inden for partitionen. I de følgende afsnit vil der på et tidspunkt blive opnået en egentlig løsning, hvis pris er lig med den bedste nedre grænse opnået for nogen af de omtrentlige løsninger. Denne løsning er optimal, men måske ikke den eneste. Algoritmen kan afsluttes på et tidligt tidspunkt med tillid til, at den optimale løsning er inden for den acceptable afvigelse fra det fundne bedste punkt; sådanne punkter kaldes ε-optimale. Afslutning af ε-optimale punkter er som regel nødvendig for at sikre endeligheden af afslutningen. Dette er især nyttigt ved store, komplekse problemer og problemer med usikre omkostninger eller værdier, hvor usikkerheden kan bestemmes ud fra et passende pålidelighedsestimat.
Differentierings- og regularitetsforhold , Karush-Kuhn-Tucker (KKT)-forholdene giver de nødvendige betingelser for løsningens optimalitet. For konveksitet er disse betingelser også tilstrækkelige.
En anden metode til at løse ikke-lineære programmeringsproblemer er dynamisk programmering [2] .
Se også
Links
Noter
- ↑ Hadley, 1967 , s. 11, 12.
- ↑ Hadley, 1967 , s. femten.
Litteratur
- Headley J. Ikke- lineær og dynamisk programmering. - M . : Mir, 1967. - 506 s.
 Ordbøger og encyklopædier | |
|---|---|
| I bibliografiske kataloger |
|
| Optimeringsmetoder _ | |
|---|---|
| Endimensionel |
|
| Nul orden | |
| Første ordre | |
| anden orden | |
| Stokastisk | |
| Lineære programmeringsmetoder _ | |
| Ikke-lineære programmeringsmetoder | |