NELINEÁRNÍ PROGRAMOVÁNÍ: METODY A CVIČENÍ - MATEMATIKA - 2025

Nelineární programování je proces optimalizace funkce, která závisí na několika nezávislých proměnných, které pak podléhají omezením.

Pokud není jedno nebo více omezení nebo funkce, která má být maximalizována nebo minimalizována (nazývaná objektivní funkce), vyjádřeno jako lineární kombinace proměnných, máte nelineární problém s programováním.

Obrázek 1. Problém nelineárního programování (NLP). kde G je (nelineární) funkce pro optimalizaci v zelené oblasti, určená omezeními. Zdroj: F. Zapata.

Proto nelze použít postupy a metody lineárního programování.

Například nelze použít známou Simplexovu metodu, která platí pouze tehdy, když jsou objektivní funkce a omezení všechny lineární kombinace proměnných v problému.

Metody lineárního programování

V případě nelineárních problémů s programováním se používají tyto hlavní metody:

1.- Grafické metody.

2. - Lagrangeovy multiplikátory, aby prozkoumaly hranice oblasti řešení.

3.- Výpočet gradientu k prozkoumání extrémů objektivní funkce.

4.- Metoda sestupných kroků k nalezení nulových bodů přechodu.

5.- Upravená metoda Lagrangeových multiplikátorů (s podmínkou Karush-Kuhn-Tucker).

Příklad řešení s grafickou metodou

Příkladem řešení s grafickou metodou je řešení, které je vidět na obrázku 2:

Obrázek 2. Příklad nelineárního problému s nelineárními omezeními a jeho grafické řešení. Zdroj: F. Zapata.

Cvičení

- Cvičení 1 (Grafická metoda)

Zisk G určité společnosti závisí na množství prodaného produktu X a na množství prodaném produktu Y, navíc je zisk určen následujícím vzorcem:

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

Je známo, že množství X a Y mají následující omezení:

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

Určete hodnoty X a Y, které vedou k maximálnímu zisku.

Obrázek 3. Zisk společnosti lze matematicky modelovat tak, aby se pomocí nelineárního programování našel maximální zisk. Zdroj: Pixabay.

Řešení

V tomto problému je objektivní funkce nelineární, zatímco nerovnosti, které definují omezení, jsou. Toto je nelineární programovací problém.

Pro řešení tohoto problému bude vybrána grafická metoda.

Nejprve bude určena oblast řešení, která je dána omezeními.

Jako X≥0; Y≥0, řešení musí být nalezeno v prvním kvadrantu roviny XY, ale protože musí také platit, že X + Y ≤ 7, řešení je v dolní polovině roviny čáry X + Y = 7.

Oblast řešení je průnikem prvního kvadrantu s dolní polovinou roviny čáry, což vede k trojúhelníkové oblasti, kde je řešení nalezeno. Je to stejné jako na obrázku 1.

Na druhé straně, zisk G může být také reprezentován v karteziánské rovině, protože jeho rovnice je rovnicí elipsy se středem (2,3).

Elipsa je znázorněna na obrázku 1 pro různé hodnoty G. Čím vyšší je hodnota G, tím větší je zisk.

Existují řešení, která patří do oblasti, ale nedávají maximální hodnotu G, zatímco jiná, například G = 92,4, jsou mimo zelenou zónu, tj. Zónu řešení.

Potom maximální hodnota G, takže X a Y patří do oblasti řešení, odpovídá:

G = 77 (maximální zisk), který je uveden pro X = 7 a Y = 0.

Je zajímavé, že k maximálnímu zisku dochází, když je prodejní množství produktu Y nulové, zatímco množství produktu X dosáhne své nejvyšší možné hodnoty.

- Cvičení 2 (Analytická metoda: Lagrangeovy multiplikátory)

Najděte řešení (x, y), které dělá funkci f (x, y) = x ² + 2y ² maximum v oblasti g (x, y) = x ² + y ² - 1 = 0.

Řešení

Je to zjevně nelineární programovací problém, protože jak objektivní funkce f (x, y), tak omezení g (x, y) = 0, nejsou lineární kombinací proměnných xay.

Bude použita metoda Lagrangeových multiplikátorů, která nejprve vyžaduje definování Lagrangeovy funkce L (x, y, λ):

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

Kde λ je parametr nazývaný Lagrangeův multiplikátor.

Chcete-li určit krajní hodnoty objektivní funkce f, v oblasti řešení dané omezením g (x, y) = 0, postupujte takto:

- Najděte částečné deriváty Lagrangeovy funkce L s ohledem na x, y, λ.

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

Zde je sled těchto operací:

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

Možná systémová řešení

Možným řešením tohoto systému je λ = 1, takže je splněna první rovnice, v tomto případě y = 0, takže druhá je splněna.

Toto řešení znamená, že x = 1 nebo x = -1 pro splnění třetí rovnice. Tímto způsobem byly získány dvě řešení S1 a S2:

S1: (x = 1, y = 0)

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

Druhou alternativou je, že λ = 2, takže druhá rovnice je splněna, bez ohledu na hodnotu y.

V tomto případě je první rovnice, která má být splněna, rovna x = 0. Pokud vezmeme v úvahu třetí rovnici, existují pouze dvě možná řešení, které budeme nazvat S3 a S4:

S3: (x = 0, y = 1)

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

Abychom zjistili, která nebo která z těchto řešení maximalizují objektivní funkci, pokračujeme substitucí 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

Došli jsme k závěru, že řešení, která maximalizují f, když x a y patří k obvodu g (x, y) = 0, jsou S3 a S4.

Dvojice hodnot (x = 0, y = 1) a (x = 0, y = -1) maximalizují f (x, y) v oblasti řešení g (x, y) = 0.

- Cvičení 3 (nulový gradient)

Najděte řešení (x, y) pro objektivní funkci:

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

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

Řešení

Toto cvičení je podobné cvičení 2, ale oblast řešení (nebo restrikce) sahá do vnitřní oblasti obvodu g (x, y) = 0, to znamená do kruhu g (x, y) ≤ 0. To zahrnuje na obvod a jeho vnitřní oblast.

Řešení na hranici bylo již stanoveno ve cvičení 2, ale vnitřní oblast je třeba prozkoumat.

Aby to bylo možné, musí být vypočítán gradient funkce f (x, y) a nastaven na nulu, aby byly nalezeny extrémní hodnoty v oblasti řešení. To je ekvivalent k výpočtu dílčích derivátů f s ohledem na xay a nastavení na nulu:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Tento systém rovnic má jediné řešení (x = 0, y = 0), které patří do kruhu g (x, y) ≤ 0.

Nahrazení této hodnoty ve funkci f vede k:

f (0, 0) = 0

Závěrem lze říci, že maximální hodnota, kterou funkce zaujímá v oblasti řešení, je 2 a vyskytuje se na hranici oblasti řešení pro hodnoty (x = 0, y = 1) a (x = 0, y = -1).

Reference

1. Avriel, M. 2003. Nelineární programování. Dover Publishing.
2. Bazaraa. 1979. Nelineární programování. John Wiley a synové.
3. Bertsekas, D. 1999. Nelineární programování: 2. vydání. Athena Scientific.
4. Nocedal, J. 1999. Numerická optimalizace. Springer-Verlag.
5. Wikipedia. Nelineární programování. Obnoveno z: es.wikipedia.com