NEMLINEÁRIS PROGRAMOZÁS: MÓDSZEREK ÉS GYAKORLATOK - MATEMATIKA - 2026

A nemlineáris programozás egy olyan funkció optimalizálásának folyamata, amely számos független változótól függ, amelyekre viszont korlátozások vonatkoznak.

Ha egy vagy több korlátozás, vagy ha a maximálandó vagy minimalizálható funkciót (az objektív függvényt nevezik) nem fejezik ki a változók lineáris kombinációjaként, akkor nemlineáris programozási probléma merül fel.

1. ábra. Nemlineáris programozási probléma (NLP). ahol G a zöld tartományban a korlátozások által meghatározott optimális (nemlineáris) függvény. Forrás: F. Zapata.

Ezért a lineáris programozás eljárásai és módszerei nem használhatók.

Például a jól ismert Simplex módszer nem használható, amely csak akkor alkalmazható, ha a célfüggvény és a korlátozások mind a problémaváltozók lineáris kombinációi.

Lineáris programozási módszerek

A nemlineáris programozási problémák esetén a főbb alkalmazandó módszerek a következők:

1.- Grafikus módszerek.

2.- Lagrange szorzók a megoldási régió határainak felfedezéséhez.

3.- A gradiens kiszámítása a célfüggvény szélsőségeinek feltárására.

4.- A csökkenő lépések módszere a null gradiens pontok megtalálására.

5.- A Lagrange szorzók módosított módszere (a Karush-Kuhn-Tucker feltétellel).

Példa a megoldásra grafikus módszerrel

A 2. ábrán látható példa a grafikus módszerrel történő megoldásra:

2. ábra. Példa egy nemlineáris problémára a nemlineáris korlátozásokkal és annak grafikus megoldása. Forrás: F. Zapata.

Feladatok

- 1. gyakorlat (grafikus módszer)

Egy bizonyos vállalat G nyeresége az X termék eladott mennyiségétől és az Y termék eladott mennyiségétől függ, ezen felül a nyereséget a következő képlettel határozzák meg:

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

Az X és Y összegekről ismert, hogy a következő korlátozásokkal rendelkeznek:

X≥0; Y≥0 és X + Y ≤ 7

Határozzuk meg az X és Y értékeket, amelyek a legnagyobb nyereséget eredményezik.

3. ábra: Egy vállalat nyeresége matematikailag modellezhető, hogy a nemlineáris programozás segítségével megkapjuk a maximális profitot. Forrás: Pixabay.

Megoldás

Ebben a problémában a célfüggvény nemlineáris, míg a korlátokat meghatározó egyenlőtlenségek. Ez egy nemlineáris programozási probléma.

A probléma megoldására a grafikus módszert kell választani.

Először meghatározzuk a megoldási régiót, amelyet a korlátozások adnak.

Mint X≥0; Y≥0, a megoldást az XY sík első negyedében kell megtalálni, de mivel igaznak kell lennie, hogy X + Y ≤ 7, a megoldás az X + Y = 7 vonal alsó félsíkjában található.

A megoldási régió az első kvadráns metszéspontja a vonal alsó félsíkjával, ami háromszög alakú régiót eredményez, ahol a megoldás megtalálható. Ez megegyezik az 1. ábrán láthatóval.

Másrészről, a G erősítés szintén ábrázolható a derékszög síkjában, mivel az egyenlete megegyezik egy (2,3) középpontú ellipszis egyenletével.

Az ellipszis az 1. ábrán látható G különféle értékeire. Minél nagyobb a G értéke, annál nagyobb a nyereség.

Vannak olyan megoldások, amelyek a régióhoz tartoznak, de nem adják meg a maximális G értéket, míg mások, például G = 92,4, a zöld zónán, azaz a megoldási zónán kívül helyezkednek el.

Ezután G maximális értéke, amely szerint X és Y az oldat régióba tartozik, megfelel:

G = 77 (maximális nyereség), amelyet X = 7 és Y = 0 esetén adunk meg.

Érdekes módon a maximális profit akkor fordul elő, ha az Y termék eladási mennyisége nulla, míg az X termék mennyisége eléri a lehető legmagasabb értéket.

- 2. gyakorlat (Analitikai módszer: Lagrange szorzók)

Keresse meg azt a (x, y) megoldást, amely az f (x, y) = x ² + 2y ² függvényt maximálissá teszi g (x, y) = x ² + y ² - 1 = 0 tartományban.

Megoldás

Ez egyértelműen egy nemlineáris programozási probléma, mivel mind az f (x, y) objektumfüggvény, mind a g (x, y) = 0 korlátozás nem az x és y változók lineáris kombinációja.

A Lagrange szorzó módszerét kell használni, amelyhez először meg kell határozni az L (Lagrange) függvényt (x, y, λ):

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

Ahol λ egy Lagrange szorzónak nevezett paraméter.

Az f célfüggvény szélsőséges értékeinek meghatározásához a g (x, y) = 0 korlátozással megadott megoldási régióban tegye a következőket:

- Keresse meg az L Lagrange függvény parciális derivációit x, y, λ viszonylatában.

- Minősítse az egyes származékokat nullára.

Itt a műveletek sorrendje:

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

Lehetséges rendszermegoldások

Ennek a rendszernek a lehetséges megoldása λ = 1, így az első egyenlet teljesül, ebben az esetben y = 0, így a második teljesül.

Ez a megoldás azt jelenti, hogy x = 1 vagy x = -1 a harmadik egyenlet teljesüléséhez. Ily módon két S1 és S2 megoldást kaptunk:

S1: (x = 1, y = 0)

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

A másik alternatíva az, hogy λ = 2, tehát a második egyenlet teljesül, y értékétől függetlenül.

Ebben az esetben az első egyenlet teljesítésének egyetlen módja az x = 0. A harmadik egyenletet figyelembe véve csak két lehetséges megoldás létezik, amelyeket S3-nak és S4-nek hívunk:

S3: (x = 0, y = 1)

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

Ahhoz, hogy megtudja, melyik megoldás vagy melyik maximalizálja a célfüggvényt, az f (x, y) helyettesítésével járunk el:

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

Megállapítottuk, hogy az f megoldást maximalizáló megoldások S3 és S4, amikor x és y a g (x, y) = 0 kerülethez tartoznak.

Az értékpárok (x = 0, y = 1) és (x = 0, y = -1) maximalizálják f (x, y) értékét g (x, y) = 0 oldat-régióban.

- 3. gyakorlat (Null gradiens)

Keressen megoldásokat (x, y) a célfüggvényhez:

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

Legyen maximális a g (x, y) = x ² + y ² - 1 ≤ 0 tartományban.

Megoldás

Ez a gyakorlat hasonló a 2. gyakorlathoz, de a megoldás (vagy korlátozás) régiója kiterjed a g (x, y) = 0 kerület belső területére, azaz a g (x, y) ≤ 0 körre. Ez magában foglalja a kerületére és annak belső részére.

A határon átnyúló megoldást már a 2. gyakorlat során meghatározták, de a belső régiót még meg kell vizsgálni.

Ehhez kiszámolnia kell az f (x, y) függvény gradienst, és nullára kell állítani, hogy a szélsőséges értékeket megtalálja a megoldás régiójában. Ez megegyezik az f parciális deriváltjának kiszámításával x és y vonatkozásában, és nullával megegyező értékre állításával:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Ennek az egyenletrendszernek az egyetlen megoldása (x = 0, y = 0), amely a g (x, y) ≤ 0 körbe tartozik.

Ezt az értéket helyettesítve az f függvényben:

f (0, 0) = 0

Összegezve, a függvény maximális értéke, amelyet a megoldási régióban vesz, 2 és a megoldási régió határán fordul elő (x = 0, y = 1) és (x = 0, y = -1) értékeknél..

Irodalom

1. Avriel, M. 2003. Nemlineáris programozás. Dover Publishing.
2. Bazaraa. 1979. Nemlineáris programozás. John Wiley & Sons.
3. Bertsekas, D. 1999. Nemlineáris programozás: 2. kiadás. Athena Scientific.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Nemlineáris programozás. Helyreállítva: es.wikipedia.com