NELINEĀRĀ PROGRAMMĒŠANA: METODES UN VINGRINĀJUMI - MATEMĀTIKA - 2025

Nelineāra programmēšana ir process, optimizēt funkcijas, kas ir atkarīgs no vairākiem neatkarīgiem mainīgajiem, kas savukārt ir pakļautas ierobežojumiem.

Ja viens vai vairāki ierobežojumi vai ja funkcija, kas jāpalielina vai jāsamazina (ko sauc par objekta funkciju), nav izteikta kā mainīgo lineārā kombinācija, jums rodas nelineāra programmēšanas problēma.

1. attēls. Nelineārā programmēšanas problēma (NLP). kur G ir (nelineāra) optimizācijas funkcija zaļajā reģionā, ko nosaka ierobežojumi. Avots: F. Zapata.

Tāpēc lineārās programmēšanas procedūras un metodes nevar izmantot.

Piemēram, nevar izmantot labi zināmo Simpleksa metodi, kas tiek piemērota tikai tad, ja objekta funkcija un ierobežojumi ir visas problēmas mainīgās lielumu lineāras kombinācijas.

Lineārās programmēšanas metodes

Nelineārās programmēšanas problēmu gadījumā galvenās izmantojamās metodes:

1.- Grafiskās metodes.

2.- Lagranžas reizinātāji, lai izpētītu risinājuma reģiona robežu.

3.- Gradienta aprēķināšana, lai izpētītu objektīvās funkcijas galējības.

4.- Dilstošu pakāpienu metode nulles gradienta punktu atrašanai.

5.- Modificētā Lagranža reizinātāju metode (ar Karuša-Kuhna-Tuckera nosacījumu).

Risinājuma piemērs ar grafisko metodi

Risinājuma piemērs ar grafisko metodi ir tāds, ko var redzēt 2. attēlā:

2. attēls. Nelineāras problēmas ar nelineāriem ierobežojumiem piemērs un tā grafiskais risinājums. Avots: F. Zapata.

Vingrinājumi

- 1. vingrinājums (grafiskā metode)

Konkrēta uzņēmuma peļņa G ir atkarīga no produkta X pārdotā apjoma un produkta Y pārdotā daudzuma, turklāt peļņu nosaka pēc šādas formulas:

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

Ir zināms, ka summām X un Y ir šādi ierobežojumi:

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

Nosakiet X un Y vērtības, kas rada maksimālo pieaugumu.

3. attēls. Lai iegūtu maksimālo peļņu, izmantojot nelineāru programmēšanu, var matemātiski modelēt uzņēmuma peļņu. Avots: Pixabay.

Risinājums

Šajā problēmā objektīvā funkcija ir nelineāra, bet nevienādības, kas nosaka ierobežojumus, ir. Tā ir nelineāra programmēšanas problēma.

Šīs problēmas risināšanai tiks izvēlēta grafiskā metode.

Pirmkārt, tiks noteikts risinājuma reģions, kuru piešķir ierobežojumi.

Kā X≥0; Y≥0, risinājums jāatrod XY plaknes pirmajā kvadrantā, bet, tā kā ir jābūt arī patiesam, ka X + Y ≤ 7, risinājums ir līnijas X + Y = 7 apakšējā pusplaknē.

Risinājuma reģions ir pirmā kvadranta krustojums ar līnijas apakšējo pusplakni, kā rezultātā veidojas trīsstūrveida reģions, kurā tiek atrasts risinājums. Tas ir tāds pats, kā norādīts 1. attēlā.

No otras puses, pastiprinājumu G var attēlot arī Dekarta plaknē, jo tā vienādojums ir tāds, kāds piemīt elipsei ar centru (2,3).

Elipse parādīta 1. attēlā dažādām G vērtībām. Jo augstāka ir G vērtība, jo lielāks ir ieguvums.

Ir risinājumi, kas pieder reģionam, bet nedod maksimālo G vērtību, savukārt citi, piemēram, G = 92,4, atrodas ārpus zaļās zonas, tas ir, risinājumu zonas.

Tad maksimālā G vērtība, kas X un Y pieder pie šķīduma apgabala, atbilst:

G = 77 (maksimālais pieaugums), kas dots X = 7 un Y = 0.

Interesanti, ka maksimālā peļņa rodas, ja produkta Y pārdošanas apjoms ir nulle, bet produkta X daudzums sasniedz augstāko iespējamo vērtību.

- 2. uzdevums (analītiskā metode: Lagrange reizinātāji)

Atrodiet risinājumu (x, y), kas funkcijai f (x, y) = x ² + 2y ² piešķir maksimumu apgabalā g (x, y) = x ² + y ² - 1 = 0.

Risinājums

Tā acīmredzami ir nelineāra programmēšanas problēma, jo gan objekta funkcija f (x, y), gan ierobežojums g (x, y) = 0 nav mainīgo x un y lineāra kombinācija.

Tiks izmantota Lagranža reizinātāju metode, kurai vispirms jādefinē Lagranža funkcija L (x, y, λ):

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

Kur λ ir parametrs, ko sauc par Lagranža reizinātāju.

Lai noteiktu objekta funkcijas f galējās vērtības šķīduma apgabalā, ko piešķir ierobežojums g (x, y) = 0, rīkojieties šādi:

-Atrodiet Lagranža funkcijas L daļējos atvasinājumus attiecībā pret x, y, λ.

-Ikvalificējiet katru atvasinājumu uz nulli.

Šeit tiek parādīta šo darbību secība:

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

Iespējamie sistēmas risinājumi

Šīs sistēmas iespējamais risinājums ir λ = 1, lai pirmais vienādojums būtu izpildīts, šādā gadījumā y = 0, lai otrais būtu apmierināts.

Šis risinājums nozīmē, ka trešā vienādojuma izpildei x = 1 vai x = -1. Tādā veidā ir iegūti divi risinājumi S1 un S2:

S1: (x = 1, y = 0)

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

Otra alternatīva ir tāda, ka λ = 2, lai otrais vienādojums tiktu izpildīts neatkarīgi no y vērtības.

Šajā gadījumā vienīgais veids, kā izpildīt pirmo vienādojumu, ir x = 0. Ņemot vērā trešo vienādojumu, ir tikai divi iespējamie risinājumi, kurus mēs sauksim par S3 un S4:

S3: (x = 0, y = 1)

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

Lai uzzinātu, kurš vai kurš no šiem risinājumiem palielina mērķa funkciju, mēs aizstājam ar 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

Secinām, ka risinājumi, kas maksimizē f, kad x un y pieder pie apkārtmēra g (x, y) = 0, ir S3 un S4.

Vērtību pāri (x = 0, y = 1) un (x = 0, y = -1) maksimizē f (x, y) šķīduma apgabalā g (x, y) = 0.

- 3. vingrinājums (nulles gradients)

Atrodi risinājumus (x, y) mērķa funkcijai:

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

Ļaujiet būt maksimālam apgabalā g (x, y) = x ² + y ² - 1 ≤ 0.

Risinājums

Šis vingrinājums ir līdzīgs 2. vingrinājumam, bet risinājuma (vai ierobežojuma) reģions sniedzas līdz apkārtmēra g (x, y) = 0 iekšējam reģionam, tas ir, ar apli g (x, y) ≤ 0. Tas ietver uz apkārtmēru un tā iekšējo reģionu.

Risinājums uz robežas jau ir noteikts 2. vingrinājumā, bet iekšējais reģions vēl ir jāizpēta.

Lai to izdarītu, jāaprēķina funkcijas f (x, y) gradients un jānosaka vienāds ar nulli, lai šķīduma reģionā atrastu galējās vērtības. Tas ir līdzvērtīgs f daļējo atvasinājumu aprēķināšanai attiecībā uz attiecīgi x un y un nulles iestatīšanai:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Šai vienādojumu sistēmai ir vienīgais risinājums (x = 0, y = 0), kas pieder aplim g (x, y) ≤ 0.

Aizstājot šo vērtību funkcijā f, iegūst rezultātu:

f (0, 0) = 0

Noslēgumā var secināt, ka vērtību (x = 0, y = 1) un (x = 0, y = -1) maksimālā vērtība, ko funkcija uzņem risinājuma reģionā, ir 2 un notiek uz šķīduma apgabala robežas. .

Atsauces

1. Avriel, M. 2003. Nelineārā programmēšana. Dovera izdevniecība.
2. Bazaraa. 1979. Nelineārā programmēšana. Džons Vilijs un dēli.
3. Bertsekas, D. 1999. Nelineārā programmēšana: 2. izdevums. Atēna zinātniskā.
4. Nocedal, J. 1999. Skaitliskā optimizācija. Springer-Verlag.
5. Wikipedia. Nelineārā programmēšana. Atgūts no: es.wikipedia.com