Icke-linjär programmering

Icke-linjär programmering ( NLP , N on Linear P rogramming ) är  ett fall av matematisk programmering som inte går ut på att sätta ett linjärt programmeringsproblem (till exempel där objektivfunktionen eller restriktionen är en icke-linjär funktion ) [1] .

Problemet med icke-linjär programmering ställs som problemet med att hitta det optimala för en viss objektiv funktion under de förhållanden

där  - parametrar,  - begränsningar,  - antal parametrar,  - antal begränsningar.

I motsats till ett linjärt programmeringsproblem, i ett icke-linjärt programmeringsproblem, ligger optimum inte nödvändigtvis på gränsen för det område som definieras av begränsningarna.

Metoder för att lösa problemet

En av metoderna som gör att vi kan reducera problemet med olinjär programmering till att lösa ett ekvationssystem är metoden med obestämda Lagrange-multiplikatorer .

Om objektivfunktionen är linjär och det avgränsade rummet är en polytop , så är problemet ett linjärt programmeringsproblem som kan lösas med välkända linjära programmeringslösningar .

Om objektivfunktionen är konkav (maximeringsproblem) eller konvex (minimeringsproblem) och begränsningsuppsättningen är konvex, kallas problemet konvex , och i de flesta fall kan allmänna konvexa optimeringsmetoder användas .

Om den objektiva funktionen är förhållandet mellan konkava och konvexa funktioner (vid maximering) och begränsningarna är konvexa, kan problemet omvandlas till ett konvext optimeringsproblem med hjälp av fraktionerad programmeringsteknik.

Det finns flera metoder för att lösa icke-konvexa problem. Ett tillvägagångssätt är att använda speciella formuleringar av linjära programmeringsproblem. En annan metod involverar användningen av gren- och bundna metoder , där problemet delas upp för att lösas med konvexa (minimeringsproblem) eller linjära approximationer som bildar en nedre gräns för den totala kostnaden inom partitionen. I de följande avsnitten kommer någon gång en faktisk lösning att erhållas, vars kostnad är lika med den bästa nedre gränsen som erhålls för någon av de ungefärliga lösningarna. Denna lösning är optimal, om än kanske inte den enda. Algoritmen kan avslutas i ett tidigt skede, med förtroende för att den optimala lösningen ligger inom den acceptabla avvikelsen från den hittade bästa punkten; sådana punkter kallas ε-optimala. Avslutning av ε-optimala punkter är som regel nödvändigt för att säkerställa ändlighet av avslutning. Detta är särskilt användbart för stora, komplexa problem och problem med osäkra kostnader eller värden, där osäkerheten kan fastställas från en lämplig tillförlitlighetsuppskattning.

Differentierings- och regularitetsförhållanden , Karush-Kuhn-Tucker (KKT)-förhållandena ger de nödvändiga förutsättningarna för lösningens optimalitet. För konvexitet är dessa förhållanden också tillräckliga.

En annan metod för att lösa icke-linjära programmeringsproblem är dynamisk programmering [2] .

Se även

• Linjär programmering

Länkar

• Hitta det optimala online med hjälp av komplex

Anteckningar

1. ↑ Hadley, 1967 , sid. 11, 12.
2. ↑ Hadley, 1967 , sid. femton.

Litteratur

• Headley J. Icke-linjär och dynamisk programmering. - M . : Mir, 1967. - 506 sid.

Ordböcker och uppslagsverk	Stor ryss Britannica (online)
I bibliografiska kataloger	BNF : 122677537 J9U : 987007533977205171 LCCN : sh85092331 NKC : ph293203