NELINEARNO PROGRAMIRANJE: METODE I VJEŽBE - MATEMATIKA - 2025

Nelinearno programiranje je proces optimiziranja funkciju koja ovisi o više nezavisnih varijabli, što zauzvrat su podvrgnuti ograničenjima.

Ako jedno ili više ograničenja ili ako funkcija koja se maksimizira ili minimizira (koja se naziva ciljna funkcija) nije izražena kao linearna kombinacija varijabli, tada imate nelinearni problem programiranja.

Slika 1. Problem nelinearnog programiranja (NLP). pri čemu je G (nelinearna) funkcija za optimizaciju u zelenoj regiji određenoj ograničenjima. Izvor: F. Zapata.

Stoga se ne mogu koristiti postupci i metode linearnog programiranja.

Na primjer, dobro poznata Simplex metoda se ne može koristiti, koja se primjenjuje samo kad su ciljna funkcija i ograničenja sve linearne kombinacije varijabli u problemu.

Linearne metode programiranja

Za probleme nelinearnog programiranja glavne metode koje se koriste su:

1.- Grafičke metode.

2. - Lagrangeov množitelj za istraživanje granice područja rješenja.

3. - Izračun gradijenta za istraživanje krajnosti ciljne funkcije.

4.- Metoda silaznih koraka za pronalaženje nulta gradijentnih točaka.

5.- Modificirana metoda Lagrangeovih množitelja (s uvjetom Karush-Kuhn-Tucker).

Primjer rješenja s grafičkom metodom

Primjer rješenja s grafičkom metodom je rješenje koje se može vidjeti na slici 2:

Slika 2. Primjer nelinearnog problema s nelinearnim ograničenjima i njegovo grafičko rješenje. Izvor: F. Zapata.

vježbe

- Vježba 1 (grafička metoda)

Zarada G određene tvrtke ovisi o prodanoj količini proizvoda X i količini prodane proizvoda Y, a dobit se određuje sljedećom formulom:

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

Poznato je da količine X i Y imaju sljedeća ograničenja:

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

Odredite vrijednosti X i Y koje stvaraju maksimalni dobitak.

Slika 3. Profit tvrtke može se matematički modelirati tako da se pronađe maksimalna dobit pomoću nelinearnog programiranja. Izvor: Pixabay.

Riješenje

U ovom je problemu ciljna funkcija nelinearna, dok su nejednakosti koje definiraju ograničenja. Ovo je problem nelinearnog programiranja.

Za rješenje ovog problema odabrat će se grafička metoda.

Prvo, utvrdit će se područje rješenja, koje je dano ograničenjima.

Kao X≥0; Y≥0, rješenje se mora naći u prvom kvadrantu ravnine XY, ali budući da mora biti istina i da je X + Y ≤ 7, rješenje je u ravnini donje polovice linije X + Y = 7.

Područje rješenja je sjecište prvog kvadranta s ravninom donje polovice crte, koja stvara trokutastu regiju u kojoj se rješenje nalazi. To je isto kao što je naznačeno na slici 1.

S druge strane, dobitak G može se prikazati i u kartezijanskoj ravnini, jer je njegova jednadžba elipsa sa središtem (2,3).

Elipsa je prikazana na slici 1 za različite vrijednosti G. Što je veća vrijednost G, to je veći dobitak.

Postoje rješenja koja pripadaju regiji, ali ne daju maksimalnu vrijednost G, dok su druga, poput G = 92,4, izvan zelene zone, odnosno zone rješenja.

Zatim, maksimalna vrijednost G, takva da X i Y pripadaju području rješenja, odgovara:

G = 77 (maksimalni dobitak), koji je dan za X = 7 i Y = 0.

Zanimljivo je da se maksimalna dobit događa kada prodajna količina proizvoda Y bude nula, dok količina proizvoda X dosegne najveću moguću vrijednost.

- Vježba 2 (Analitička metoda: Lagrangeovi množitelji)

Pronađite rješenje (x, y) koje funkciju f (x, y) = x ² + 2y ^{2 čini} maksimumom u području g (x, y) = x ² + y ² - 1 = 0.

Riješenje

Jasno je nelinearni problem programiranja, jer obje ciljne funkcije f (x, y) i ograničenje g (x, y) = 0, nisu linearna kombinacija varijabli x i y.

Koristit će se metoda Lagrangeovih množitelja koja prvo zahtijeva definiranje Lagrangeove funkcije L (x, y, λ):

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

Gdje je λ parametar koji se zove Lagrangeov množitelj.

Da biste odredili ekstremne vrijednosti ciljne funkcije f, u području rješenja dato ograničenjem g (x, y) = 0, slijedite ove korake:

-Zaznajte parcijalne derivate Lagrangeove funkcije L, u odnosu na x, y, λ.

-Ujednačite svaki derivat na nulu.

Slijedi redoslijed ovih operacija:

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

Moguća sistemska rješenja

Moguće rješenje ovog sustava je λ = 1, tako da je prva jednadžba zadovoljena, u tom slučaju y = 0, tako da je drugi zadovoljan.

Ovo rješenje podrazumijeva da je x = 1 ili x = -1 za treću jednadžbu koja je zadovoljena. Na taj su način dobili dvije otopine S1 i S2:

S1: (x = 1, y = 0)

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

Druga alternativa je da je λ = 2 tako da je zadovoljena druga jednadžba, bez obzira na vrijednost y.

U ovom je slučaju jedini način da se zadovolji prva jednadžba za x = 0. S obzirom na treću jednadžbu, postoje samo dva moguća rješenja, koja ćemo nazvati S3 i S4:

S3: (x = 0, y = 1)

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

Da bismo otkrili koja ili koja od tih rješenja maksimiziraju ciljnu funkciju, prelazimo na supstituciju u 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

Zaključujemo da su rješenja koja maksimiziraju f, kada x i y pripadaju obodu g (x, y) = 0 jesu S3 i S4.

Parovi vrijednosti (x = 0, y = 1) i (x = 0, y = -1) maksimiziraju f (x, y) u području rješenja g (x, y) = 0.

- Vježba 3 (nulti gradijent)

Pronađite rješenja (x, y) za ciljnu funkciju:

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

Neka je maksimum u regiji g (x, y) = x ² + y ² - 1 ≤ 0.

Riješenje

Ova vježba je slična vježbi 2, ali se rješenje (ili ograničenje) područje proteže na unutarnju regiju obima g (x, y) = 0, to jest na krug g (x, y) ≤ 0. To uključuje na obod i njegovu unutarnju regiju.

Rješenje na granici već je određeno u vježbi 2, ali unutrašnjost tek treba istražiti.

Da biste to učinili, mora se izračunati gradijent funkcije f (x, y) i postaviti jednak nuli, kako bi se pronašle ekstremne vrijednosti u području rješenja. To je ekvivalentno izračunavanju parcijalnih derivata f u odnosu na x i y, odnosno postavljanju jednake nuli:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Ovaj sustav jednadžbi ima jedino rješenje (x = 0, y = 0) koje pripada kružnici g (x, y) ≤ 0.

Zamjena ove vrijednosti u funkciji f rezultata:

f (0, 0) = 0

Zaključno, maksimalna vrijednost koju funkcija uzima u području rješenja je 2 i javlja se na granici područja rješenja, za vrijednosti (x = 0, y = 1) i (x = 0, y = -1),

Reference

1. Avriel, M. 2003. Nelinearno programiranje. Dover Publishing.
2. Bazaraa. 1979. Nelinearno programiranje. John Wiley & Sinovi.
3. Bertsekas, D. 1999. Nelinearno programiranje: drugo izdanje. Atena znanstvena.
4. Nocedal, J. 1999. Numerička optimizacija. Springer-Verlag.
5. Wikipedia. Nelinearno programiranje. Oporavak od: es.wikipedia.com