KURZUS: Alkalmazott operációkutatás

MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell

9. lecke: Nemlineáris programozás

Tanulási útmutató

A nemlineáris programozás fogalma, grafikus szemléltetése és gyakorlati példák a tankönyv 7. fejezetében találhatók.

A közgazdaságban kitüntetett szerepe van a tört- vagy hiperbolikus programozásnak, ezért a tankönyv kiemelten csak ennek a feladattípusnak az algebrai megoldását tárgyalja. Ez található meg a tankönyv 7.3. alfejezetében. Figyelmesen tanulmányozza át a tankönyvben található módszert, mert ez azt mutatja be, hogy hogyan lehet lineáris programozási feladatra visszavezetni és szimplex módszerrel megoldani.

Tevékenységek

Figyelmesen olvassa el a tankönyvben található hiperbolikus programozás definícióját és jól jegyezze meg a mátrixvektor szimbólumokkal adott modelljét

A tankönyvben látható gyakorlati példára alkalmazza a "transzformációt". Vezesse be az y j és a t új változókat. Vegyen elő egy lapot és írja fel a feladat lineáris programozási modelljét.

A nemlineáris programozási feladatok megoldása Solver programmal.

A Solver program lehetővé teszi a nemlineáris célfüggvényű programozási feladatok megoldását is. A már korábban bemutatott Beállítások lenyíló menüben nem kell bejelölni a Lineáris modellt feltételez előtt álló jelölőnégyzetet!

Követelmények
  • Kulcsszavak alapján ki tudja egészíteni a nemlineáris programozásra, a kvadratikus, illetve hiperbolikus programozásra vonatkozó mondatot.
  • Az egyes programozási modellekre vonatkozó állításokról el tudja dönteni, hogy igazak vagy hamisak.
  • Egy adott hiperbolikus programozási feladat modelljét át tudja transzformálni lineáris programozási feladattá!
  • Solver segítségével meg tud oldani nemlineáris programozási feladatokat!

Bemutató feladat

1. Oldjuk meg Simplex módszer segítségével az alábbi feladatot!

x 1 ; x 2 ; x 3 0 2 x 1 +2 x 2 6 x 1 + x 2 + x 3 4 2 x 1 + x 2 + x 3 1 x 1 + x 2 + x 3 +1 max

Vezessünk be új ismereteket!

2 y 1 +2 y 2 6t0 y 1 + y 2 + y 3 4t0 y 1 + y 2 + y 3 +t=1 2 y 1 + y 2 + y 3 tmax

B0y1y2y3t
w1220-60
w2111-40
u311111
-z211-10
B1y1y2y3u3
w188666
w255544
t11111
-z32211
B2w1y2y3u3
y11/813/43/43/4
w2-5/801 1/41/41/4
t-1/801/41/41/4
-z-3/8-1-1/4-1 1/4-1 1/4
y1=3/4y2=0y3=0t=1/4
x1=y1/t=3x2=y2/t=0x3=y3/t=0

2. Példaként nézzük a tankönyvben látható kvadratikus programozási feladat Solverrel történő megoldását. Helyezze el a modell paramétereit az Excel-táblán az alábbiak szerint:

Korlátozó feltételek (egyenként kell felvenni őket):

  • $D$3<=$F$3
  • $D$4<=$F$4

Hívja meg a Solver programot és jelölje be a kért adatokat. A Beállítás menüben ne feledje el bejelölni, hogy ez nem lineáris modell (azaz ne tegyen jelet a Lineáris modellt feltételez négyzetbe)! Oldja meg a feladatot! A grafikus megoldáson látható értékeket kapja megoldásként.

Hasonlóan oldja meg a tankönyvben látható 7.1.2. példát. Javaslat az Excel-táblázaton való elhelyezésre: Vigye be az adatokat! A B7 cellába írja be a számláló képletét, a B8 cellába a nevező képletét.

A célfüggvény képletét az E9 cellába írjuk be.

Hívjuk be a Solvert, és adjuk meg a feltételeket. A beállítás menüben csak a nem negatív feltételezést jelöljük be!

Korlátozó feltételek (egyenként kell felvenni őket):

  • $E$3<=$G$3
  • $E$4=$G$4
  • $E$5<=$G$5

A megoldás gombra kattintva láthatjuk az eredményt

Önellenőrző feladat

1. Fogalmazza meg az alábbi kulcsszavak felhasználásával a nemlineáris és a hiperbolikus programozás fogalmát, valamint a gazdasági jelentőségét.

12345678
költségelsőfokúnemlineárismásodfokútörtnemnegatívárbevételhatvány
a) Írja be a fenti számokat a megfelelő helyre!

Nemlineáris programozásról akkor beszélünk, ha a modell feltételrendszere egyenlőtlenségrendszer, célfüggvénye pedig függvény.

b) Írja be a fenti számokat a megfelelő helyre!

Kvadratikus programozásról akkor beszélünk, ha a modell feltételrendszere egyenlőtlenség rendszer, a célfüggvénye pedig függvény.

c) Írja be a fenti számokat a megfelelő helyre!

Hiperbolikus programozásról akkor beszélünk, ha a modell feltételrendszere egyenlőtlenség rendszer, a célfüggvénye pedig függvény, azaz számlálója , a nevezője függvény.

d) Írja be a fenti számokat a megfelelő helyre!

Hiperbolikus programozási modell alkalmas arra, hogy megfogalmazzuk azt a célt, hogy az 1 Ft ráfordításra jutó nyereség legyen a legnagyobb azzal, hogy a számlálóba és függvények különbségét írjuk, a nevezőbe pedig a(z) függvényt.

2. Döntse el, hogy az alábbi állítások igazak vagy hamisak!
Nemlineáris programozási modellben mind a feltételrendszer mind a célfüggvény nem lineáris.
Hiperbolikus programozási modellben csak a célfüggvény hatványfüggvény, a feltételrendszer lineáris rendszer.
Kvadratikus programozási modellben a feltételrendszer lineáris, a célfüggvény pedig másodfokú függvény.
Hiperbolikus programozási modellben a célfüggvény elsőfokú törtfüggvény, a feltételrendszer pedig elsőfokú egyenlőtlenségekből áll.
Hiperbolikus programozási modellel a ráfordítás hatékonyságát, mint kívánatos célt tudjuk megfogalmazni.

3. Egy hiperbolikus programozási feladat matematikai modellje a következőképpen néz ki:

x 1 x 2 x 3 0 2 x 1 + x 2 x 3 10 x 2 +2 x 3 = 8 x 1 +5 x 2 12 z= 3 x 1 +5 x 2 + x 3 3 x 1 +2 x 2 + x 3 +1 max

Transzformálja át új változók bevezetésével lineáris modellé. Vegyen elő egy munkalapot, írja le a lineáris modellt, majd ezután értelem szerint töltse ki az alábbi táblázatot:

A modell változói, egyenlőtlenségei és együtthatói, reláció jelei, valamint a jobb oldal értékei:

A nagyobb egyenlő és a kisebb egyenlő relációkat így adja meg: <= és >=!
Írja ezeket a mellékelt táblázat megfelelő helyére!
Változók y 1 y 2 y 3 trelációjobb oldal
Együtthatók
célfüggvény

4. Oldja meg a Solver segítségével a következő matematikai programozási feladatot!

x 1 x 2 x 3 0 2 x 1 + x 2 +2 x 3 20 x 1 + x 2 15 x 2 + x 3 10 z= 2 x 2 +2 x 1 + x 2 + x 3 +1 max

Váltson át az Excel táblázatkezelőre!

A gyors megoldás érdekében javaslom a következőt: A változók helyének kijelölése után a feltételek bal oldalának képleteit írja be egy-egy cellába. Hasonlóan a célfüggvény képleteit. Ezután hívja meg a Solver programot.

Megjegyzés: az eredményeket egész számra kerekítse!
Az optimális megoldás eredményét írja ide.

x 1 =
x 2 =
x 3 =
z opt =