ICKE-LINJÄR PROGRAMMERING: METODER OCH ÖVNINGAR - MATTE - 2025

Den icke-linjära programmeringen är processen för att optimera en funktion som beror på flera oberoende variabler, som i sin tur utsätts för begränsningar.

Om en eller flera av begränsningarna, eller om funktionen som ska maximeras eller minimeras (kallas objektivfunktionen) inte uttrycks som en linjär kombination av variablerna, har du ett olinjärt programmeringsproblem.

Bild 1. Icke-linjärt programmeringsproblem (NLP). där G är den (icke-linjära) funktionen för att optimera i det gröna området, bestämt av begränsningarna. Källa: F. Zapata.

Och därför kan procedurerna och metoderna för linjär programmering inte användas.

Till exempel kan den välkända Simplex-metoden inte användas, som endast gäller när objektfunktionen och begränsningarna är linjära kombinationer av variablerna i problemet.

Linjära programmeringsmetoder

För icke-linjära programmeringsproblem är de viktigaste metoderna som används:

1.- Grafiska metoder.

2.- Lagrange-multiplikatorer för att utforska gränsen för lösningsområdet.

3.- Beräkning av lutningen för att utforska ytterpunkter i objektivfunktionen.

4.- Metoden för fallande steg för att hitta nollgradientpunkterna.

5.- Modifierad metod för Lagrange-multiplikatorerna (med Karush-Kuhn-Tucker-villkoret).

Exempel på lösning med grafisk metod

Ett exempel på en lösning med den grafiska metoden är den som kan ses i figur 2:

Figur 2. Exempel på ett icke-linjärt problem med icke-linjära begränsningar och dess grafiska lösning. Källa: F. Zapata.

övningar

- Övning 1 (grafisk metod)

Vinsten G för ett visst företag beror på det sålda beloppet av produkten X och det sålda beloppet av produkten Y, och vinsten bestäms av följande formel:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Beloppen X och Y är kända för att ha följande begränsningar:

X≥0; Y≥0 och X + Y ≤ 7

Bestäm värdena för X och Y som ger maximal vinst.

Figur 3. Ett företags vinst kan matematiskt modelleras för att hitta den maximala vinsten med icke-linjär programmering. Källa: Pixabay.

Lösning

I detta problem är den objektiva funktionen icke-linjär, medan ojämlikheterna som definierar begränsningarna är. Detta är ett olinjärt programmeringsproblem.

För att lösa detta problem kommer den grafiska metoden att väljas.

Först kommer lösningsområdet att bestämmas, vilket ges av begränsningarna.

Som X≥0; Y≥0, måste lösningen hittas i den första kvadranten på XY-planet, men eftersom det också måste vara sant att X + Y ≤ 7 ligger lösningen i det nedre halvplanet för linjen X + Y = 7.

Lösningsområdet är skärningspunkten mellan den första kvadranten med linjens nedre halva plan, vilket resulterar i ett triangulärt område där lösningen finns. Det är samma som anges i figur 1.

Å andra sidan kan förstärkningen G också representeras i det kartesiska planet, eftersom dess ekvation är den för en ellips med centrum (2,3).

Ellipsen visas i figur 1 för olika värden på G. Ju högre värde på G, desto större är förstärkningen.

Det finns lösningar som tillhör regionen, men ger inte det maximala G-värdet, medan andra, som G = 92.4, är utanför den gröna zonen, det vill säga lösningszonen.

Därefter motsvarar det maximala värdet på G, så att X och Y tillhör lösningsområdet:

G = 77 (maximal förstärkning), vilket ges för X = 7 och Y = 0.

Intressant nog inträffar den maximala vinsten när försäljningsbeloppet för produkt Y är noll, medan mängden produkt X når sitt högsta möjliga värde.

- Övning 2 (Analytisk metod: Lagrange-multiplikatorer)

Hitta lösningen (x, y) som gör funktionen f (x, y) = x ² + 2y ² maximalt i området g (x, y) = x ² + y ² - 1 = 0.

Lösning

Det är helt klart ett icke-linjärt programmeringsproblem, eftersom både objektfunktionen f (x, y) och begränsningen g (x, y) = 0, inte är en linjär kombination av variablerna x och y.

Lagrange-multiplikatormetoden kommer att användas, vilket först kräver att Lagrange-funktionen L (x, y, λ) definieras:

L (x, y, X) = f (x, y) - X g (x, y) = x ² + 2y ² - X (x ² + y ² - 1)

Där λ är en parameter som heter Lagrange-multiplikatorn.

För att bestämma de extrema värdena för objektfunktionen f, i lösningsområdet som ges av begränsningen g (x, y) = 0, följ dessa steg:

-Find de partiella derivat av Lagrange-funktionen L, med avseende på x, y, λ.

-Kvalificera varje derivat till noll.

Här sekvensen för dessa operationer:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Möjliga systemlösningar

En möjlig lösning av detta system är λ = 1 så att den första ekvationen är nöjd, i vilket fall y = 0 så att den andra är nöjd.

Denna lösning innebär att x = 1 eller x = -1 för att den tredje ekvationen ska vara uppfylld. På detta sätt har två lösningar S1 och S2 erhållits:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Det andra alternativet är att λ = 2 så att den andra ekvationen är nöjd, oavsett y-värdet.

I detta fall är det enda sättet för den första ekvationen att vara nöjd med x = 0. Med tanke på den tredje ekvationen finns det bara två möjliga lösningar, som vi kommer att kalla S3 och S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

För att ta reda på vilka eller vilka av dessa lösningar som maximerar objektivfunktionen fortsätter vi att ersätta i f (x, y):

S1: f (1, 0) = 1 ² + 2,0 ² = 1

S2: f (-1, 0) = (-1) ² + 2,0 ² = 1

S3: f (0, 1) = 0 ² + 2,1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Vi drar slutsatsen att lösningarna som maximerar f, när x och y tillhör periferin g (x, y) = 0 är S3 och S4.

Paren av värden (x = 0, y = 1) och (x = 0, y = -1) maximerar f (x, y) i lösningsområdet g (x, y) = 0.

- Övning 3 (Null lutning)

Hitta lösningar (x, y) för objektivfunktionen:

f (x, y) = x ² + 2 y ²

Låt vara maximalt i området g (x, y) = x ² + y ² - 1 ≤ 0.

Lösning

Denna övning liknar övning 2, men lösningsområdet (eller begränsningen) sträcker sig till det inre området av omkretsen g (x, y) = 0, det vill säga cirkeln g (x, y) ≤ 0. Detta inkluderar till omkretsen och dess inre region.

Lösningen vid gränsen har redan fastställts i övning 2, men det inre området återstår att utforska.

För att göra detta måste gradienten för funktionen f (x, y) beräknas och ställas lika med noll för att hitta extrema värden i lösningsområdet. Detta motsvarar beräkningen av partiella derivat av f med avseende på x respektive y och inställning av det lika med noll:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Detta ekvationssystem har den enda lösningen (x = 0, y = 0) som tillhör cirkeln g (x, y) ≤ 0.

Att ersätta detta värde i funktionen f resulterar i:

f (0, 0) = 0

Sammanfattningsvis är det maximala värdet som funktionen tar i lösningsområdet 2 och sker vid gränsen för lösningsområdet, för värdena (x = 0, y = 1) och (x = 0, y = -1) .

referenser

1. Avriel, M. 2003. Icke-linjär programmering. Dover Publishing.
2. Bazaraa. 1979. Icke-linjär programmering. John Wiley & Sons.
3. Bertsekas, D. 1999. Icke-linjär programmering: 2: a upplagan. Athena Scientific.
4. Nocedal, J. 1999. Numerisk optimering. Springer-Verlag.
5. Wikipedia. Icke-linjär programmering. Återställd från: es.wikipedia.com