IKKE-LINEÆR PROGRAMMERING: METODER OG ØVELSER - MATEMATIK - 2025

Den ikke-lineære programmering er processen med at optimere en funktion, der afhænger af flere uafhængige variabler, som igen er underlagt begrænsninger.

Hvis en eller flere af begrænsningerne, eller hvis den funktion, der skal maksimeres eller minimeres (kaldes objektivfunktionen), ikke udtrykkes som en lineær kombination af variablerne, har du et ikke-lineært programmeringsproblem.

Figur 1. Ikke-lineært programmeringsproblem (NLP). hvor G er den (ikke-lineære) funktion, der skal optimeres i det grønne område, bestemt af begrænsningerne. Kilde: F. Zapata.

Og derfor kan procedurerne og metoderne for lineær programmering ikke bruges.

For eksempel kan den velkendte Simplex-metode ikke bruges, hvilket kun gælder, når objektivfunktionen og begrænsningerne alle er lineære kombinationer af variablerne i problemet.

Lineære programmeringsmetoder

For ikke-lineære programmeringsproblemer er de vigtigste metoder, der skal bruges:

1.- Grafiske metoder.

2.- Lagrange-multiplikatorer for at udforske grænsen for løsningsregionen.

3.- Beregning af gradienten for at undersøge ytterpunkterne i objektivfunktionen.

4.- Metoden til faldende trin til at finde nulgradientpunkter.

5.- Ændret metode til Lagrange-multiplikatorerne (med tilstanden Karush-Kuhn-Tucker).

Eksempel på løsning med grafisk metode

Et eksempel på en løsning med den grafiske metode er den, der kan ses i figur 2:

Figur 2. Eksempel på et ikke-lineært problem med ikke-lineære begrænsninger og dets grafiske løsning. Kilde: F. Zapata.

Øvelser

- Øvelse 1 (Grafisk metode)

Overskuddet G for et bestemt firma afhænger af det solgte beløb for produkt X og det solgte beløb af produkt Y, derudover bestemmes overskuddet af følgende formel:

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

Beløb X og Y vides at have følgende begrænsninger:

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

Bestem værdierne for X og Y, der giver den maksimale forstærkning.

Figur 3. Virksomhedens fortjeneste kan matematisk modelleres for at finde den maksimale fortjeneste ved hjælp af ikke-lineær programmering. Kilde: Pixabay.

Løsning

I dette problem er den objektive funktion ikke-lineær, mens ulighederne, der definerer begrænsningerne er. Dette er et ikke-lineært programmeringsproblem.

Til løsning af dette problem vælges den grafiske metode.

Først bestemmes opløsningsområdet, hvilket er givet ved begrænsningerne.

Som X≥0; Y≥0, skal løsningen findes i den første kvadrant af XY-planet, men da det også skal være sandt, at X + Y ≤ 7, er løsningen i det nedre halvplan af linjen X + Y = 7.

Opløsningsområdet er skæringspunktet mellem den første kvadrant med det nedre halvplan af linjen, hvilket giver anledning til et trekantet område, hvor opløsningen findes. Det er det samme som angivet i figur 1.

På den anden side kan forstærkningen G også repræsenteres i det kartesiske plan, da dens ligning er for en ellipse med centrum (2,3).

Ellipsen er vist i figur 1 for forskellige værdier af G. Jo højere værdien af ​​G, jo større er forstærkningen.

Der er løsninger, der hører til regionen, men giver ikke den maksimale G-værdi, mens andre, såsom G = 92.4, er uden for den grønne zone, dvs. løsningszonen.

Derefter svarer den maksimale værdi af G, således at X og Y hører til opløsningsområdet:

G = 77 (maksimal forstærkning), der er angivet for X = 7 og Y = 0.

Interessant nok forekommer den maksimale fortjeneste, når salgsmængden af ​​produkt Y er nul, mens mængden af ​​produkt X når sin højest mulige værdi.

- Øvelse 2 (Analytisk metode: Lagrange-multiplikatorer)

Find løsningen (x, y), der gør funktionen f (x, y) = x ² + 2y ² maksimal i området g (x, y) = x ² + y ² - 1 = 0.

Løsning

Det er helt klart et ikke-lineært programmeringsproblem, da både objektfunktionen f (x, y) og begrænsningen g (x, y) = 0 ikke er en lineær kombination af variablerne x og y.

Lagrange-multiplikator-metoden vil blive brugt, som først kræver, at Lagrange-funktionen L (x, y, λ) defineres:

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

Hvor λ er en parameter kaldet Lagrange-multiplikatoren.

Følg disse trin for at bestemme de ekstreme værdier for objektivfunktionen f i opløsningsområdet givet af begrænsningen g (x, y) = 0:

-Find de partielle derivater af Lagrange-funktionen L med hensyn til x, y, λ.

-Kvalificer hvert derivat til nul.

Her er sekvensen af ​​disse operationer:

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

Mulige systemløsninger

En mulig løsning af dette system er λ = 1, så den første ligning er tilfreds, i hvilket tilfælde y = 0, så den anden er tilfreds.

Denne løsning indebærer, at x = 1 eller x = -1, for at den tredje ligning skal være tilfreds. På denne måde er to løsninger S1 og S2 opnået:

S1: (x = 1, y = 0)

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

Det andet alternativ er, at λ = 2, så den anden ligning er tilfreds, uanset y-værdien.

I dette tilfælde er den eneste måde for den første ligning at være tilfreds med x = 0. I betragtning af den tredje ligning er der kun to mulige løsninger, som vi vil kalde S3 og S4:

S3: (x = 0, y = 1)

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

For at finde ud af, hvilke eller hvilke af disse løsninger, der maksimerer objektivfunktionen, fortsætter vi med at erstatte 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 konkluderer, at de løsninger, der maksimerer f, når x og y hører til omkredsen g (x, y) = 0, er S3 og S4.

Værdeparrene (x = 0, y = 1) og (x = 0, y = -1) maksimerer f (x, y) i opløsningsområdet g (x, y) = 0.

- Øvelse 3 (Nul gradient)

Find løsninger (x, y) til objektivfunktionen:

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

Lad være maksimal i området g (x, y) = x ² + y ² - 1 ≤ 0.

Løsning

Denne øvelse ligner øvelse 2, men opløsnings- (eller begrænsnings) -området strækker sig til det indre område af omkredsen g (x, y) = 0, det vil sige til cirklen g (x, y) ≤ 0. Dette inkluderer til omkredsen og dens indre region.

Løsningen ved grænsen er allerede bestemt i øvelse 2, men det indre område skal stadig undersøges.

For at gøre dette skal gradienten af ​​funktionen f (x, y) beregnes og indstilles lig med nul for at finde ekstreme værdier i opløsningsområdet. Dette svarer til beregningen af ​​de partielle derivater af f med hensyn til henholdsvis x og y og indstilling af det lig med nul:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Dette ligningssystem har den eneste løsning (x = 0, y = 0), der hører til cirklen g (x, y) ≤ 0.

Udskiftning af denne værdi i funktionen f resulterer i:

f (0, 0) = 0

Afslutningsvis er den maksimale værdi, som funktionen tager i opløsningsområdet, 2 og forekommer ved grænsen for opløsningsområdet, for værdierne (x = 0, y = 1) og (x = 0, y = -1).

Referencer

1. Avriel, M. 2003. Ikke-lineær programmering. Dover Publishing.
2. Bazaraa. 1979. Ikke-lineær programmering. John Wiley & sønner.
3. Bertsekas, D. 1999. Ikke-lineær programmering: 2. udgave. Athena Scientific.
4. Nocedal, J. 1999. Numerisk optimering. Springer-Verlag.
5. Wikipedia. Ikke-lineær programmering. Gendannet fra: es.wikipedia.com