NELINEARNO PROGRAMIRANJE: METODE IN VAJE - MATEMATIKA - 2025

Nelinearno programiranje je proces optimizacije funkcijo, ki je odvisna od več neodvisnih spremenljivk, ki so v zameno za katera veljajo omejitve.

Če ena ali več omejitev ali če funkcija, ki jo je treba maksimizirati ali zmanjšati (imenovano ciljna funkcija), ni izražena kot linearna kombinacija spremenljivk, imate težavo z nelinearnim programiranjem.

Slika 1. Problem nelinearnega programiranja (NLP). kjer je G (nelinearna) funkcija za optimizacijo v zelenem območju, določena z omejitvami. Vir: F. Zapata.

Zato postopkov in metod linearnega programiranja ni mogoče uporabiti.

Na primer, dobro znane Simplex metode ni mogoče uporabiti, kar velja le, kadar sta ciljna funkcija in omejitve vse linearne kombinacije spremenljivk v problemu.

Metode linearnega programiranja

Za težave z nelinearnim programiranjem so glavne metode, ki se uporabljajo:

1.- Grafične metode.

2. - Lagrangevi množitelji za raziskovanje meje območja raztopine.

3. - Izračun naklona za raziskovanje skrajnosti ciljne funkcije.

4.- Metoda spuščanja po korakih za iskanje ničelnih točk naklona.

5.- Spremenjena metoda multiplikatorjev Lagrange (s pogojem Karush-Kuhn-Tucker).

Primer raztopine z grafično metodo

Primer rešitve z grafično metodo je tista, ki jo lahko vidimo na sliki 2:

Slika 2. Primer nelinearnega problema z nelinearnimi omejitvami in njegova grafična rešitev. Vir: F. Zapata.

Vaje

- Vaja 1 (Grafična metoda)

Dobiček G določenega podjetja je odvisen od prodane količine izdelka X in prodane količine izdelka Y, dobiček pa je določen z naslednjo formulo:

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

Znano je, da sta za količino X in Y naslednje omejitve:

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

Določite vrednosti X in Y, ki ustvarjata največji dobiček.

Slika 3. Dobiček podjetja lahko matematično modeliramo tako, da s pomočjo nelinearnega programiranja poiščemo največji dobiček. Vir: Pixabay.

Rešitev

V tem problemu je ciljna funkcija nelinearna, medtem ko so neenakosti, ki definirajo omejitve. To je nelinearna programska težava.

Za rešitev tega problema bo izbrana grafična metoda.

Najprej bo določeno območje rešitve, ki ga dajejo omejitve.

Kot X≥0; Y≥0 je rešitev treba najti v prvem kvadrantu ravnine XY, ker pa mora biti tudi res, da je X + Y ≤ 7, je raztopina v spodnji polovici ravnine premice X + Y = 7.

Območje raztopine je presečišče prvega kvadranta s spodnjo polovico ravnine črte, kar ima za posledico trikotno območje, kjer najdemo rešitev. Je enako, kot je prikazano na sliki 1.

Po drugi strani lahko dobitek G predstavljamo tudi v kartezijanski ravnini, saj je enačba elipse s središčem (2,3).

Elipsa je prikazana na sliki 1 za različne vrednosti G. Večja kot je vrednost G, večji je dobitak.

Obstajajo rešitve, ki spadajo v regijo, vendar ne dajejo največje vrednosti G, medtem ko so druge, na primer G = 92,4, zunaj zelene cone, torej območja raztopine.

Nato največja vrednost G, tako da X in Y pripadata raztopinskemu območju, ustreza:

G = 77 (največji dobiček), ki je dan za X = 7 in Y = 0.

Zanimivo je, da največji dobiček nastane, ko je količina izdelka Y enaka nič, količina izdelka X pa doseže najvišjo možno vrednost.

- Vaja 2 (Analitična metoda: Lagrangevi množitelji)

Poiščite rešitev (x, y), zaradi katere je funkcija f (x, y) = x ² + 2y ² največja v območju g (x, y) = x ² + y ² - 1 = 0.

Rešitev

Jasno gre za problem nelinearnega programiranja, saj tako ciljna funkcija f (x, y) kot omejitev g (x, y) = 0 nista linearni kombinaciji spremenljivk x in y.

Uporabljena bo metoda multiplikatorjev Lagrange, ki najprej zahteva določitev funkcije Lagrange L (x, y, λ):

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

Kjer je λ parameter, imenovan Lagrangeov množitelj.

Če želite določiti skrajne vrednosti ciljne funkcije f, v območju rešitve, podanem z omejitvijo g (x, y) = 0, sledite tem korakom:

-Poiščite delne izpeljanke Lagrangeove funkcije L glede na x, y, λ.

-Vrednost vsakega izpeljave izenačite na nič.

Tu je zaporedje teh operacij:

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

Možne sistemske rešitve

Možna rešitev tega sistema je λ = 1, tako da je izpolnjena prva enačba, v tem primeru y = 0, tako da je drugi izpolnjen.

Ta rešitev pomeni, da je x = 1 ali x = -1 za izpolnitev tretje enačbe. Na ta način dobimo dve rešitvi S1 in S2:

S1: (x = 1, y = 0)

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

Druga možnost je, da je λ = 2, tako da je izpolnjena druga enačba, ne glede na vrednost y.

V tem primeru je edini način, da je prva enačba izpolnjena, za x = 0. Glede na tretjo enačbo obstajata le dve možni rešitvi, ki ju bomo poimenovali S3 in S4:

S3: (x = 0, y = 1)

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

Da bi ugotovili, katere ali katere od teh rešitev maksimirajo ciljno funkcijo, nadomestimo v 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

Sklepamo, da so rešitve, ki maksimizirajo f, ko x in y spadata v obod g (x, y) = 0, sta S3 in S4.

Parovi vrednosti (x = 0, y = 1) in (x = 0, y = -1) maksimizirajo f (x, y) v območju raztopine g (x, y) = 0.

- Vaja 3 (ničelni naklon)

Poiščite rešitve (x, y) za ciljno funkcijo:

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

Naj bo največ v območju g (x, y) = x ² + y ² - 1 ≤ 0.

Rešitev

Ta vaja je podobna vaji 2, vendar se raztopina (ali omejitev) razširi na notranje območje oboda g (x, y) = 0, to je na krog g (x, y) ≤ 0. To vključuje do oboda in njegovega notranjega območja.

Rešitev na meji je že določena v vaji 2, vendar je treba še raziskati notranjost.

Če želite to narediti, je treba izračunati gradient funkcije f (x, y) in ga nastaviti enako nič, da bi našli najnižje vrednosti v območju raztopine. To je ekvivalentno izračunavanju delnih izpeljank f glede na x in y oziroma nastavitev na nič:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Ta sistem enačb ima edino rešitev (x = 0, y = 0), ki spada v krog g (x, y) ≤ 0.

Nadomestitev te vrednosti v funkciji f rezultatov:

f (0, 0) = 0

Za zaključek je največja vrednost, ki jo funkcija sprejme v območju raztopine, 2 in se pojavi na meji območja raztopine, za vrednosti (x = 0, y = 1) in (x = 0, y = -1) .

Reference

1. Avriel, M. 2003. Nelinearno programiranje. Doverjeva založba.
2. Bazaraa. 1979. Nelinearno programiranje. John Wiley & Sons.
3. Bertsekas, D. 1999. Nelinearno programiranje: 2. izdaja. Atena Znanstvena.
4. Nocedal, J. 1999. Numerična optimizacija. Springer-Verlag
5. Wikipedija. Nelinearno programiranje. Pridobljeno: es.wikipedia.com