NELINEÁRNE PROGRAMOVANIE: METÓDY A CVIČENIA - MATEMATIKA - 2026

Nelineárne programovanie je proces optimalizácie funkcia, ktorá závisí od viacerých nezávislých premenných, čo sú vystavené obmedzeniam.

Ak jedno alebo viac obmedzení alebo funkcia, ktorá sa má maximalizovať alebo minimalizovať (nazývaná objektívna funkcia), nie je vyjadrená ako lineárna kombinácia premenných, máte problém s nelineárnym programovaním.

Obrázok 1. Problém nelineárneho programovania (NLP). kde G je (nelineárna) funkcia na optimalizáciu v zelenej oblasti určená obmedzeniami. Zdroj: F. Zapata.

Preto nemožno použiť postupy a metódy lineárneho programovania.

Napríklad nie je možné použiť dobre známu Simplexovu metódu, ktorá sa uplatňuje iba vtedy, keď sú objektívna funkcia a obmedzenia všetky lineárne kombinácie premenných v probléme.

Metódy lineárneho programovania

Pri problémoch nelineárneho programovania sa používajú tieto hlavné metódy:

1.- Grafické metódy.

2. - Lagrangeove multiplikátory na preskúmanie hranice oblasti riešenia.

3.- Výpočet gradientu na preskúmanie extrémov objektívnej funkcie.

4.- Metóda zostupných krokov na nájdenie nulových bodov gradientu.

5.- Upravená metóda Lagrangeových multiplikátorov (v podmienkach Karush-Kuhn-Tucker).

Príklad riešenia s grafickou metódou

Príkladom riešenia s grafickou metódou je riešenie, ktoré vidno na obrázku 2:

Obrázok 2. Príklad nelineárneho problému s nelineárnymi obmedzeniami a jeho grafické riešenie. Zdroj: F. Zapata.

cvičenie

- Cvičenie 1 (grafická metóda)

Zisk G určitej spoločnosti závisí od predaného množstva produktu X a od predaného množstva produktu Y, navyše sa zisk určuje podľa tohto vzorca:

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

O množstvách X a Y je známe, že majú tieto obmedzenia:

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

Stanovte hodnoty X a Y, ktoré vytvárajú maximálny zisk.

Obrázok 3. Zisk spoločnosti možno matematicky modelovať tak, aby sa pomocou nelineárneho programovania našiel maximálny zisk. Zdroj: Pixabay.

Riešenie

V tomto probléme je objektívna funkcia nelineárna, zatiaľ čo nerovnosti, ktoré definujú obmedzenia, sú. Toto je nelineárny programovací problém.

Pre riešenie tohto problému bude zvolená grafická metóda.

Najprv sa určí oblasť riešenia, ktorá je daná obmedzeniami.

Ako X≥0; Y≥0, riešenie sa musí nájsť v prvom kvadrante roviny XY, ale keďže musí platiť aj to, že X + Y ≤ 7, riešenie je v dolnej polovici roviny priamky X + Y = 7.

Oblasť riešenia je priesečníkom prvého kvadrantu s dolnou polovicou roviny čiary, čo vedie k trojuholníkovej oblasti, v ktorej sa nachádza riešenie. Je to rovnaké ako na obrázku 1.

Na druhej strane zisk G môže byť tiež vyjadrený v karteziánskej rovine, pretože jeho rovnica je rovnica elipsy so stredom (2,3).

Elipsa je znázornená na obrázku 1 pre rôzne hodnoty G. Čím vyššia je hodnota G, tým väčší je zisk.

Existujú riešenia, ktoré patria do oblasti, ale neuvádzajú maximálnu hodnotu G, zatiaľ čo iné, napríklad G = 92,4, sú mimo zelenej zóny, to znamená zóny riešenia.

Potom maximálna hodnota G tak, že X a Y patria do oblasti riešenia, zodpovedá:

G = 77 (maximálny zisk), ktorý je daný pre X = 7 a Y = 0.

Je zaujímavé, že maximálny zisk nastane, keď je objem predaja produktu Y nulový, zatiaľ čo množstvo produktu X dosiahne najvyššiu možnú hodnotu.

- Cvičenie 2 (Analytická metóda: Lagrangeove multiplikátory)

Nájdite riešenie (x, y), ktoré robí funkciu f (x, y) = x ² + 2y ² maximum v oblasti g (x, y) = x ² + y ² - 1 = 0.

Riešenie

Je to jednoznačne nelineárny programovací problém, pretože tak objektívna funkcia f (x, y), ako aj obmedzenie g (x, y) = 0, nie sú lineárnou kombináciou premenných xay.

Použije sa metóda Lagrangeových multiplikátorov, ktorá si najskôr vyžaduje definovanie Lagrangeovej funkcie L (x, y, λ):

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

Kde λ je parameter nazývaný Lagrangeov multiplikátor.

Ak chcete určiť extrémne hodnoty objektívnej funkcie f, v oblasti riešenia určenej obmedzením g (x, y) = 0, postupujte takto:

- Nájdite čiastkové deriváty Lagrangeovej funkcie L vzhľadom na x, y, λ.

- Vyrovnajte každý derivát na nulu.

Tu je postupnosť týchto operácií:

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

Možné systémové riešenia

Možným riešením tohto systému je λ = 1, takže prvá rovnica je splnená, v tomto prípade y = 0, takže druhá je splnená.

Toto riešenie znamená, že x = 1 alebo x = -1 pre tretiu rovnicu, ktorá má byť splnená. Týmto spôsobom boli získané dve riešenia S1 a S2:

S1: (x = 1, y = 0)

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

Druhou alternatívou je, že λ = 2, takže druhá rovnica je splnená bez ohľadu na hodnotu y.

V tomto prípade je jediný spôsob splnenia prvej rovnice x = 0. Vzhľadom na tretiu rovnicu existujú iba dve možné riešenia, ktoré budeme nazývať S3 a S4:

S3: (x = 0, y = 1)

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

Aby sme zistili, ktoré z týchto riešení maximalizujú cieľovú funkciu, pokračujeme 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

Dospeli sme k záveru, že riešenia, ktoré maximalizujú f, keď x a y patria do obvodu g (x, y) = 0, sú S3 a S4.

Páry hodnôt (x = 0, y = 1) a (x = 0, y = -1) maximalizujú f (x, y) v oblasti roztoku g (x, y) = 0.

- Cvičenie 3 (nulový gradient)

Nájdite riešenia (x, y) pre objektívnu funkciu:

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

Dovoliť je maximum v oblasti g (x, y) = x ² + y ² - 1 ≤ 0.

Riešenie

Toto cvičenie je podobné cvičeniu 2, ale oblasť riešenia (alebo obmedzenia) sa rozprestiera do vnútornej oblasti obvodu g (x, y) = 0, to znamená do kruhu g (x, y) ≤ 0. To zahŕňa po obvode a jeho vnútornej oblasti.

Riešenie na hranici už bolo stanovené v cvičení 2, je však potrebné preskúmať vnútorný región.

Aby sa to dosiahlo, musí sa vypočítať gradient funkcie f (x, y) a nastaviť na nulu, aby sa našli extrémne hodnoty v oblasti riešenia. Je to ekvivalent k výpočtu čiastkových derivátov f vzhľadom na x a y a ich nastaveniu na nulu:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Tento systém rovníc má jediné riešenie (x = 0, y = 0), ktoré patrí do kruhu g (x, y) ≤ 0.

Nahradenie tejto hodnoty funkciou f vedie k:

f (0, 0) = 0

Záverom možno povedať, že maximálna hodnota, ktorú funkcia prijíma v oblasti riešenia, je 2 a vyskytuje sa na hranici oblasti riešenia pre hodnoty (x = 0, y = 1) a (x = 0, y = -1). ,

Referencie

1. Avriel, M. 2003. Nelineárne programovanie. Dover Publishing.
2. Bazaraa. 1979. Nelineárne programovanie. John Wiley a synovia.
3. Bertsekas, D. 1999. Nelineárne programovanie: 2. vydanie. Athena Scientific.
4. Nocedal, J. 1999. Numerická optimalizácia. Springer-Verlag.
5. Wikipedia. Nelineárne programovanie. Obnovené z: es.wikipedia.com