IKKE-LINEÆR PROGRAMMERING: METODER OG ØVELSER - MATTE - 2026

Den ikke-lineære programmeringen er prosessen med å optimalisere en funksjon som er avhengig av flere uavhengige variabler, som igjen er underlagt begrensninger.

Hvis en eller flere av begrensningene, eller hvis funksjonen som skal maksimeres eller minimeres (kalt objektivfunksjonen) ikke er uttrykt som en lineær kombinasjon av variablene, har du et ikke-lineært programmeringsproblem.

Figur 1. Ikke-lineært programmeringsproblem (NLP). der G er den (ikke-lineære) funksjonen for å optimalisere i det grønne området, bestemt av begrensningene. Kilde: F. Zapata.

Og derfor kan ikke prosedyrene og metodene for lineær programmering brukes.

Den velkjente Simplex-metoden kan for eksempel ikke brukes, som bare gjelder når objektivfunksjonen og begrensningene alle er lineære kombinasjoner av variablene i problemet.

Lineære programmeringsmetoder

For ikke-lineære programmeringsproblemer er de viktigste metodene som skal brukes:

1.- Grafiske metoder.

2.- Lagrange-multiplikatorer for å utforske grensen for løsningsområdet.

3.- Beregning av gradienten for å utforske ytterpunktene i objektivfunksjonen.

4.- Metoden for å synke ned trinn for å finne nullgradientpunktene.

5.- Endret metode for Lagrange-multiplikatorene (med Karush-Kuhn-Tucker-tilstand).

Eksempel på løsning med grafisk metode

Et eksempel på en løsning med den grafiske metoden er den som kan sees i figur 2:

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

Øvelser

- Oppgave 1 (grafisk metode)

Overskuddet G for et visst selskap avhenger av mengden solgt av produkt X og mengde solgt av produkt Y, i tillegg bestemmes overskuddet av følgende formel:

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

Beløpene X og Y er kjent for å ha følgende begrensninger:

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

Bestem verdiene til X og Y som gir maksimal forsterkning.

Figur 3. Overskuddet til et selskap kan matematisk modelleres for å finne maksimal fortjeneste ved å bruke ikke-lineær programmering. Kilde: Pixabay.

Løsning

I dette problemet er den objektive funksjonen ikke-lineær, mens ulikhetene som definerer begrensningene er. Dette er et ikke-lineært programmeringsproblem.

For løsning av dette problemet blir den grafiske metoden valgt.

Først vil løsningsregionen bestemmes, noe som er gitt av begrensningene.

Som X≥0; Y≥0, må løsningen finnes i den første kvadranten av XY-planet, men siden det også må være sant at X + Y ≤ 7, er løsningen i det nedre halvplanet av linjen X + Y = 7.

Løsningsregionen er skjæringspunktet mellom den første kvadranten med den nedre halvplan av linjen, noe som resulterer i et trekantet område der løsningen er funnet. Det er det samme som angitt i figur 1.

På den annen side kan forsterkningen G også representeres i det kartesiske planet, siden ligningen er den for en ellipse med sentrum (2,3).

Ellipsen er vist i figur 1 for forskjellige verdier av G. Jo høyere verdi på G, desto større er forsterkningen.

Det er løsninger som hører til regionen, men gir ikke maksimal G-verdi, mens andre, som G = 92.4, er utenfor den grønne sonen, det vil si løsningssonen.

Deretter tilsvarer den maksimale verdien av G, slik at X og Y tilhører løsningsområdet:

G = 77 (maksimal forsterkning), som er gitt for X = 7 og Y = 0.

Interessant nok oppstår den maksimale fortjenesten når salgsmengden på produkt Y er null, mens mengden av produkt X når sin høyest mulige verdi.

- Oppgave 2 (Analytisk metode: Lagrange multiplikatorer)

Finn løsningen (x, y) som gjør funksjonen 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, siden både objektivfunksjonen f (x, y) og begrensningen g (x, y) = 0, ikke er en lineær kombinasjon av variablene x og y.

Lagrange-multiplikator-metoden vil bli brukt, som først krever definering av Lagrange-funksjonen L (x, y, λ):

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

Hvor λ er en parameter som heter Lagrange-multiplikatoren.

Følg disse trinnene for å bestemme ekstreme verdier for objektivfunksjonen f i løsningsområdet gitt av begrensningen g (x, y) = 0:

-Finn de partielle derivatene av Lagrange-funksjonen L, med hensyn til x, y, λ.

-Kvalifiser hvert derivat til null.

Her er sekvensen av disse operasjonene:

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 av dette systemet er λ = 1 slik at den første ligningen er tilfreds, i så fall y = 0 slik at den andre blir tilfreds.

Denne løsningen innebærer at x = 1 eller x = -1 for at den tredje ligningen skal være fornøyd. På denne måten er to løsninger S1 og S2 oppnådd:

S1: (x = 1, y = 0)

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

Det andre alternativet er at λ = 2 slik at den andre ligningen er tilfreds, uavhengig av y-verdien.

I dette tilfellet er den eneste måten for den første ligningen å være fornøyd med x = 0. Tatt i betraktning den tredje ligningen, er det bare to mulige løsninger, som vi vil kalle S3 og S4:

S3: (x = 0, y = 1)

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

For å finne ut hvilke eller hvilke av disse løsningene som maksimerer objektivfunksjonen, fortsetter vi å 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 med at løsningene som maksimerer f, når x og y tilhører omkretsen g (x, y) = 0, er S3 og S4.

Verdiene par (x = 0, y = 1) og (x = 0, y = -1) maksimerer f (x, y) i løsningsområdet g (x, y) = 0.

- Oppgave 3 (Null gradient)

Finn løsninger (x, y) for objektivfunksjonen:

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

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

Løsning

Denne øvelsen er lik øvelse 2, men løsningsområdet (eller begrensningen) strekker seg til det indre området av omkretsen g (x, y) = 0, det vil si til sirkelen g (x, y) ≤ 0. Dette inkluderer til omkretsen og dens indre region.

Løsningen ved grensen er allerede bestemt i øvelse 2, men det indre området gjenstår å utforske.

For å gjøre dette må gradienten til funksjonen f (x, y) beregnes og settes lik null for å finne ekstreme verdier i løsningsområdet. Dette tilsvarer beregning av partielle derivater av f med hensyn til henholdsvis x og y og innstilling av det lik null:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Dette ligningssystemet har den eneste løsningen (x = 0, y = 0) som hører til sirkelen g (x, y) ≤ 0.

Å erstatte denne verdien i funksjonen f resulterer:

f (0, 0) = 0

Avslutningsvis er den maksimale verdien som funksjonen tar i løsningsområdet 2 og forekommer ved grensen for løsningsområdet, for verdiene (x = 0, y = 1) og (x = 0, y = -1) .

referanser

1. Avriel, M. 2003. Ikke-lineær programmering. Dover Publishing.
2. Bazaraa. 1979. Ikke-lineær programmering. John Wiley & Sons.
3. Bertsekas, D. 1999. Ikke-lineær programmering: 2. utgave. Athena Scientific.
4. Nocedal, J. 1999. Numerisk optimalisering. Springer-Verlag.
5. Wikipedia. Ikke-lineær programmering. Gjenopprettet fra: es.wikipedia.com