NETIESINIS PROGRAMAVIMAS: METODAI IR PRATIMAI - MATEMATIKA - 2025

Netiesinė programavimas yra optimizuoti funkciją, kuri priklauso nuo kelių nepriklausomų kintamųjų, kurie savo ruožtu yra taikomi tam tikri ribojimai procesas.

Jei vienas ar keli apribojimai arba funkcija, kurią reikia maksimaliai padidinti arba sumažinti (vadinama objektyvia funkcija), nėra išreiškiama kaip tiesinė kintamųjų kombinacija, turite nelinijinio programavimo problemą.

1 paveikslas. Netiesinio programavimo problema (NLP). kur G yra (netiesinė) žaliojo regiono optimizavimo funkcija, kurią lemia apribojimai. Šaltinis: F. Zapata.

Todėl linijinio programavimo procedūros ir metodai negali būti naudojami.

Pvz., Negalima naudoti gerai žinomo Simplex metodo, kuris taikomas tik tada, kai tikslo funkcija ir apribojimai yra visos problemos kintamųjų linijinės kombinacijos.

Linijiniai programavimo metodai

Pagrindiniai nelinijinio programavimo problemoms spręsti naudojami šie metodai:

1.- Grafiniai metodai.

2.- „Lagrange“ daugikliai, norėdami ištirti sprendimo regiono ribas.

3.- Tikslo funkcijos kraštutinumų tyrimo gradiento apskaičiavimas.

4.- Mažėjančių žingsnių metodas nuliniams gradiento taškams surasti.

5.- Modifikuotas „Lagrange“ multiplikatorių metodas (su Karush-Kuhn-Tucker sąlygomis).

Sprendimo grafiniu metodu pavyzdys

Grafinio metodo sprendimo pavyzdys yra tas, kurį galima pamatyti 2 paveiksle:

2 pav. Netiesinės problemos su netiesiniais apribojimais pavyzdys ir jo grafinis sprendimas. Šaltinis: F. Zapata.

Pratimai

- 1 užduotis (grafinis metodas)

Tam tikros įmonės pelnas G priklauso nuo parduoto produkto X kiekio ir parduoto produkto Y kiekio, be to, pelnas nustatomas pagal šią formulę:

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

Yra žinoma, kad X ir Y sumoms taikomi šie apribojimai:

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

Nustatykite X ir Y reikšmes, kurios sukuria didžiausią padidėjimą.

3 pav. Norėdami gauti maksimalų pelną naudodami netiesinį programavimą, galite matematiškai modeliuoti įmonės pelną. Šaltinis: „Pixabay“.

Sprendimas

Šioje problemoje objektyvioji funkcija yra netiesinė, o nelygybės, apibrėžiančios apribojimus. Tai netiesinė programavimo problema.

Šiai problemai išspręsti bus pasirinktas grafinis metodas.

Pirmiausia bus nustatytas sprendimo regionas, kuriam suteikia apribojimai.

Kaip X≥0; Y≥0, sprendimas turi būti rastas pirmame XY plokštumos kvadrante, tačiau kadangi taip pat turi būti tiesa, kad X + Y ≤ 7, sprendimas yra apatinėje linijos linijoje X + Y = 7.

Tirpalo sritis yra pirmojo kvadranto sankirta su apatine linijos plokštuma ir susidaro trikampio sritis, kurioje randamas sprendimas. Tai yra tas pats, kaip nurodyta 1 paveiksle.

Kita vertus, padidėjimą G taip pat galima pavaizduoti Dekarto plokštumoje, nes jo lygtis yra elipsės su centru (2,3).

Įvairioms G. reikšmėms elipsė parodyta 1 paveiksle. Kuo didesnė G vertė, tuo didesnis padidėjimas.

Yra sprendimų, kurie priklauso regionui, tačiau nesuteikia didžiausios G vertės, o kiti, pavyzdžiui, G = 92,4, yra už žaliosios zonos ribų, tai yra tirpalo zonos.

Tada didžiausia G vertė, tokia, kad X ir Y priklauso tirpalo sričiai, atitinka:

G = 77 (didžiausias padidėjimas), kuris pateikiamas X = 7 ir Y = 0.

Įdomu tai, kad maksimalus pelnas atsiranda, kai produkto Y pardavimo suma yra lygi nuliui, o produkto X kiekis pasiekia didžiausią įmanomą vertę.

- 2 užduotis (analizės metodas: Lagrange daugikliai)

Raskite sprendimą (x, y), pagal kurį funkcija f (x, y) = x ² + 2y ^{2 yra} didžiausia g srityje (x, y) = x ² + y ² - 1 = 0.

Sprendimas

Aišku, tai netiesinė programavimo problema, nes ir objektyvo funkcija f (x, y), ir apribojimas g (x, y) = 0, nėra tiesinė kintamųjų x ir y kombinacija.

Bus naudojamas Lagrange koeficientų metodas, kuris pirmiausia reikalauja apibrėžti Lagrange funkciją L (x, y, λ):

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

Kur λ yra parametras, vadinamas Lagrange daugikliu.

Norėdami nustatyti kraštines tikslo funkcijos f reikšmes tirpalo srityje, kuriai suteiktas apribojimas g (x, y) = 0, atlikite šiuos veiksmus:

-Rasti dalinius Lagrangeo funkcijos L išvestinius x, y, λ atžvilgiu.

- Kiekvieną darinį išmatuokite iki nulio.

Čia pateikiama šių operacijų seka:

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

Galimi sistemos sprendimai

Galimas šios sistemos sprendimas yra λ = 1, kad būtų įvykdyta pirmoji lygtis, tokiu atveju y = 0, kad antroji būtų patenkinta.

Šis sprendimas reiškia, kad trečioji lygtis turi būti įvykdyta x = 1 arba x = -1. Tokiu būdu buvo gauti du sprendimai S1 ir S2:

S1: (x = 1, y = 0)

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

Kita alternatyva yra ta, kad λ = 2, kad būtų įvykdyta antroji lygtis, nepriklausomai nuo y vertės.

Tokiu atveju vienintelis būdas patenkinti pirmąją lygtį yra x = 0. Atsižvelgiant į trečiąjį lygtį, yra tik du galimi sprendimai, kuriuos mes vadinsime S3 ir S4:

S3: (x = 0, y = 1)

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

Norėdami sužinoti, kuris iš šių sprendimų maksimaliai padidina tikslo funkciją, toliau keičiame 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

Darome išvadą, kad sprendimai, maksimaliai padidinantys f, kai x ir y priklauso apskritimui g (x, y) = 0, yra S3 ir S4.

Vertių poros (x = 0, y = 1) ir (x = 0, y = -1) maksimaliai padidina f (x, y) tirpalo srityje g (x, y) = 0.

- 3 pratimas (nulinis gradientas)

Raskite tikslo funkcijos sprendimus (x, y):

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

Leiskite būti didžiausias g (x, y) = x ² + y ² - 1 ≤ 0 srityje.

Sprendimas

Šis pratimas yra panašus į 2 pratimą, tačiau tirpalo (arba apribojimo) sritis tęsiasi iki vidinės apskritimo g (x, y) = 0, tai yra, apskritimo g (x, y) ≤ 0. Tai apima į perimetrą ir jo vidinę sritį.

Sprendimas pasienyje jau buvo nustatytas atliekant 2 pratimą, tačiau vidaus regionas dar turi būti ištirtas.

Tam reikia apskaičiuoti funkcijos f (x, y) gradientą ir nustatyti jį lygų nuliui, kad būtų galima rasti kraštutines vertes tirpalo srityje. Tai reiškia, kad apskaičiuojami daliniai f išvestiniai atitinkamai x ir y atžvilgiu ir nustatomi lygūs nuliui:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Ši lygčių sistema turi vienintelį sprendimą (x = 0, y = 0), priklausantį apskritimui g (x, y) ≤ 0.

Pakeitus šią vertę funkcijoje f, gaunami:

f (0, 0) = 0

Apibendrinant galima pasakyti, kad maksimali reikšmė, kurią funkcija imasi tirpalo srityje, yra 2 ir atsiranda tirpalo srities riboje, kai nurodomos reikšmės (x = 0, y = 1) ir (x = 0, y = -1). .

Nuorodos

1. Avriel, M. 2003. Netiesinis programavimas. „Dover“ leidyba.
2. Bazaraa. 1979. Netiesinis programavimas. Johnas Wiley ir sūnūs.
3. Bertsekas, D. 1999. Netiesinis programavimas: 2-asis leidimas. Atėnų mokslinis.
4. Nocedal, J. 1999. Skaitmeninis optimizavimas. „Springer-Verlag“.
5. Vikipedija. Netiesinis programavimas. Atkurta iš: es.wikipedia.com