Economic subjects | Operational Research » Operációkutatás feladatok, megoldással

Operációkutatás Fejezetek - pénzügyi számítások - lineáris algebra - az operációkutatás feladatai - optimalizálás - lineáris programozás - hálós tervezések 1.Pénzügyi számítások 1.1 Kamatszámítás - Idegen tőke használatáért kamatot kell fizetni (kölcsönt kérünk, bankba rakjuk a pénzt) Jelölés Megnevezés Egysége C0 befektetett, kölcsönadott tőke (Cash-flow – pénzáramlásból, a 0. Pénzegység Időpillanatban) n időtartam időegység, általában év Cn kölcsön időtartamának lejárta után fizetendő összeg Pénzegység r kamatláb (az ország gazdasági viszonyait, két ember viszonyát, kifizető megbízhatóságát jellemezheti) Kamatláb: egységnyi idő után, egységnyi időre (hacsak másképp nem közlik 1 évre) fizetendő kamat Kamatszámítás módjai: - egyszerű kamatszámítás: - a periódusonként jóváírt kamatot nem kapcsolják a tőkéhez (kevésbé elterjedt, rövidebb időszakokra használják) - a

kifizetendő összeg az idő haladtával lineárisan növekszik - Képlete: C n =C 0 +C 0 ∙r∙n= C 0 ∙(1+r∙n) Példák 1.11 Mennyi a kifizetendő összeg, ha a befektetett tőke 100 000 Ft, a kamatláb 0,1, az időtartam 3 év n=3 r=0,1 C 0 = 100 000 C n= C 0 ·(1+r·n)=100000(1+3·0,1)=130 000 Ft A kifizetendő összeg 130 000 Ft 1.12 Kölcsönkaptunk 20 000 Ft-ot 60 napra 12%-os kamatra, mennyit kell majd visszafizetnünk? n=60 r=0,12 C 0 = 20 000 C n= C 0 ·(1+r·n)=20000(1+60/365·0,12)=20 395 Ft A visszafizetendő összeg 20 395 Ft 1.13 Hány százalékos kamatláb mellett lesz 30 000 Ft kölcsönként kapott összegből 6 hónap múlva 32 700 Ft? n=0,5 r=0,15 C 0 = 30 000 32 700=(30000(1+0,5r) r=0,18 C n= C 0 ·(1+r·n) 18%-os kamatláb mellett lesz a kölcsönkért összegből 32 700 Ft. - kamatos kamatszámítás - a periódusonként jóváírt kamatot a tőkéhez kapcsolják, azaz tőkésítik (elterjedtebb, hosszabb időszakokra ezt használják - a kamatot az

időszak végén kötik a tőkéhez - a kifizetés az idő haladtával exponenciálisan növekszik - C 1 = C 0 ∙(1+r) C 2 = C 1 ∙(1+r) - Képlete: C n = C 0 ∙(1+r)n Példák 1.14 Mennyi a kifizetendő összeg, ha a befektetett tőke 100 000 Ft, a kamatláb 0,1, az időtartam 3 év n=3 r=0,1 C 0 = 100 000 C n= C 0 ·(1+r)n=100000(1+0,1)3=133 100 Ft A kifizetendő összeg 133 100 Ft 1.15 Mekkora összeget kérhetünk kölcsön, 15%-os kamatláb mellett, ha 5 év múlva 500 000 Ft-ot tudunk visszafizetni? 1. oldal Operációkutatás 500 000= C 0 (1,15)5 C 0 =248588,368 A kölcsönkérhető összeg 248 588 Ft Kamatos kamatszámítás esetén, adott kamatláb mellett hány év alatt lesz pontosan a fele a felvehető összeg? 500 000= 250 000(1,15)n ln( 1 + r ) (1+r)n=2 ln(1+r)n=ln2 n= C n = C 0 ·(1+r)n=2C 0 ln 2 ha r=0,15 n=4,95 4,95 év alatt lesz a visszafizetendő összeg a kétszerese a felvett összegnek - vegyes kamatszámítás - az egész évekre kamatos, a maradék

napokra egyszerű kamatszámítást alkalmaznak (a befektető számára ez a legkedvezőbb) 1.16 Mennyit fizet ki a bank, ha vegyes kamatozással számol (C 0 =100 000, r = 0,1) a) 2 és fél év múlva C 2 = 100000 ⋅ (1 + 0 ,1)2 = 121000 C 2 ,5 = 121000( 1 + 0 ,5 ⋅ 0 ,1 ) = 127050 Két és fél év múlva 127050 Ft-ot fizet ki a bank b) 2 év 8 hónap múlva C 2év8hónap = 121000 ⋅  1 + 2 ⋅ 0 ,1  = 129067 3   Két év és nyolc hónap után 129 067 Ft-ot fizet ki a bank A pénzügyi gyakorlatban gyakran évente többször is tőkésítenek, azaz a kamat érvényességi időtartama (amely hacsak másképp nem közlik egy év) nem egyezik meg a tőkésítési periódussal  - évente m-szeri tőkésítés esetén C n = C 0 ∙ 1 +  r   m n ⋅m 1.17 Mennyi a kifizetendő összeg, ha a befektetett tőke 100 000 Ft, a kamatláb 0,1, az időtartam 3 év C 0 = 100 000 n=3 r=0,1  0 ,1  félévi tőkésítés esetén: 100000  1 +

 2   2⋅3 =134 010 Ft 12  0 ,1  negyedévi tőkésítés esetén: 100000  1 +  =134 489 Ft 4   - effektív kamatláb - az összehasonlítás lehetősége végett az úgynevezett névleges (nominális) kamatláb mellett megszokták adni az úgynevezett tényleges vagy effektív kamatlábat. Ez utóbbi megadja azt a kamatlábat, amely mellett a befektetett tőke évente egyszeri tőkésítés mellett ugyanannyi idő alatt ugyanakkorára növekedne. m m⋅n r  r    - C 0 1 +  = C 0 (1 + reff )m⋅n reff = 1 + n  − 1 m  m  1.18 Adjuk meg a 8% nominális kamatlábnak a 3 havonkénti tőkésítés melletti effektív értékét m 4 r    0 ,08  Az effektív kamatláb 8,243% reff =  1 + n  − 1 =  1 +  − 1 = 0 ,08243 m 4    - folytonos tőkésítésű kamatszámítás - a pénzvilágban gyakran naponta tőkésítenek. A nemzetgazdaságban pedig a növekedések folyamatosak is

lehetnek. m t  1 - ismétlés: lim 1 +  = e t ∞ t r   lim 1 +  m ∞ m m 2. oldal      1  = lim 1 +  m ∞ m   r   r r  1  t = lim  1 +  m t ∞  t  =t r     r =er Operációkutatás n ⋅m ( ) n r  (n általában nem egész szám) = C 0 e r = C 0 e r ⋅n  m ∞  m 1.19 Adjuk meg a 8%-os nominális kamatlábnak megfelelő folytonos tőkésítés melletti effektív kamatlábat!  - C n = lim C 0 1 +  reff = lim  1 + m∞ m r  r  −1 = e −1 m reff = e 0 ,08 − 1 = 0 ,08329 8,329% az effektív kamatláb 1.110 Kölcsönkaptunk 2 millió Ft-t 25%-os kamatra Bármikor visszafizethetjük, de az uzsorás folytonos kamatozással számol. Ha 500 nap múlva tudjuk törleszteni az adósságot mennyit kell visszafizetni? r=0,25 Millió Forint-ban számolva: C 0 =2 n=500/365=1,36986 2 816 832 Ft-ot

kell visszafizetni. C n = C 0 ern=2·e0,25·500/365=2,816832239 1.2 A pénz időértéke - különböző időpontokban esedékes pénzeket nem szabad számszerűen, közvetlenül összehasonlítani (mert az eltelt időközben a pénz értéke változik) ezért különböző időpontokban esedékes pénzeket összevetés előtt egy azonos időpontra számoljuk át, megadjuk az adott időpontbeli egyenértéküket, egy megfelelő „piaci kamatláb” segítségével. Ezt a kamatlábat adottnak és állandónak tekintjük Jövőérték számítás - egy jelenlegi pénzösszegnek számítjuk ki egy jövő időpontbeli ellenértékét. Ez egy kamatszámítási feladat, hacsak másképp nem közlik, akkor éves lekötésű kamatos kamatszámítással dolgozunk. - jelölések: PV: jelenbeli pénzösszeg (Present Value) FV n : jövőbeli pénzösszeg (az index a jelen és a jövő időpont közötti időtartamot jelenti) FV n =PV(1+r)n 1+r: kamattényező Jelenérték számítás -

meghatározzuk azt a pénzösszeget, amelynek az adott jövő időpontbeli egyenértéke az akkor esedékes összeg lenne (diszkontálunk) PV= FVn (1 + r ) n  1    1+ r    = FVn n diszkonttényező 1.21 Ingatlanunk eladására két ajánlat közül kell döntenünk: az első vevő most kifizetne 10 millió Ftot és egy év múlva további 4 millió Ft-ot, a második most csak 8 millió Ft-ot tud fizetni, de egy év múlva 5 milliót, további egy év múlva még 1,3 millió Ft-ot fizetne. Melyik ajánlat előnyösebb, ha a piaci kamatláb 8%-nak vehető Millió Ft-ban számolva PVA = 10 + 4 ⋅ 1 = 13 ,703704 (1 + 0 ,08 ) PVB = 8 + 5 ⋅ 1 1 = 13 ,744170 + 1,3 ⋅ (1 + 0 ,08 ) (1 + 0 ,08 )2 A második vevő ajánlata előnyösebb Ha a kamatláb 0,1 lenne, akkor az első vevő ajánlata lenne a kedvezőbb. 1.3 Járadékok A meghatározott ideig esedékes, periódusonként egyenlő nagyságú pénzáramok (ki és befizetések) sorozatát

járadéknak vagy annuitásnak nevezzük. Pl hiteltörlesztő járadék, gyűjtőjáradék Egy ki vagy befizetést járadéktagnak hívünk. A továbbiakban feltesszük, hogy a járadéktagok fizetésének periódusa megegyezik a kamatozási periódussal (általában 1 év) Szokásos járadék: a pénzáramok fizetése a periódus végén esedékes 0 1 2 n idő(év) A be és kifizetés év végén tör- ténik Jelen PVAN N FVAN N 3. oldal Operációkutatás Esedékes annuitás: a pénzáramok a periódusok elején folynak 0 1 2 n-1 n idő(év) A be és kifizetés év elején tör- ténik Jelen PVAND N FVAND N D: Due - esedékes Jelölések Jelölés Megnevezés C Pénzáramok FVAN n Az n éven át fizetendő annuitás jövőértéke PVAN n Az n éven át fizetendő annuitás jelenértéke 1.3 Egysége Pénzegység Pénzegység Pénzegység 1.31 Tegyük fel, hogy négy éven keresztül minden év végén 200 000 Ft-ot helyezünk el a számlánkon, mennyi pénz gyűlik össze a

negyedik év végére, ha a bank 10%-os kamatot nyújt C=200 000 n=4 r=0,1 FVAN 4 = 200 000·(1+0,1)3+200 000·(1+0,1)2+200 000·(1+0,1)= 200 000·(1,13+1,12+1,1)= = 928 200 A negyedik év végére 928 000 Ft gyűlik össze Képlete [ ]  (1 + r )n − 1  C  = (1 + r )n − 1 FVAN n = C ⋅ (1 + r )n −1 + (1 + r )n − 2 + . + 1 = C ⋅   r  r   ( ) Ismétlés q n +1 − 1 q −1 1.32 5 éven keresztül minden év végén kapni fogunk 1 500 000 Eurót, mennyi ezen annuitás jelenértéke most, az év elején, ha a piaci kamatláb 10,5%? C= 1500 r=0,105 n=5 (Ezer Forintban számolva) Mértani sorozat összegképlete: 1 + q + . + q n = PVAN 5 = Képlete 1500 1500 1500 1500 1500 + + + + = 1,105 1,105 2 1,105 3 1,105 4 1,105 5  1 1 1 1 1 = 1500 ⋅  + + + + 2 3 4 5 1 , 105 1 , 105 1 , 105 1 , 105 1 , 105  Az adott járadék jelenlegi értéke 5 614 290 Forint   = 5614 ,29   n  1   −1  n  C   1 n 

  1 1 1  1+ r  1  − 1 + r   1  PVAN n = C ⋅ 1 + + = C⋅    − 1 = 1 −   ⋅    = C⋅1 r ⋅ 1 1 + r  r   1 + r  +  r   1 + r    1 + r (1 + r )n − 1   −1 1+ r - alkalmazható még: hiteltörlesztés egyenlő nagyságú törlesztőrészletekkel 1.33 Felveszünk a banktól év elején 800 000 Ft lakáshitelt 20% kamatláb mellett Mekkora lesz a törlesztő részlet, ha öt év alatt kell törlesztenünk 5 évi fizetésekkel. PVAN=800 000 r=0,2 n=5 C  1  1 −  = 267503 ,76 A törlesztőrészlet 267 504 Ft 800 000=  0 ,2  1,02 5  Törlesztési terv: Év Évi részlet Kamat Tőketölresztés Fennálló tartozás 0 0 0 0 800000 1 267504 160000 107504 692496 2 267504 138499 129005 563491 3 267504 112698 154806 408685 4 267504 81737 185767 222919 5 267504 44584 222920 -2 Ha a kifizetés nem az első évben indul meg, akkor először annak az

évnek az elejére konvertáljuk, amikor a fizetés elindul 4. oldal Operációkutatás 1.34 Mennyi pénzt helyezzünk el most a bankban, ha azt szeretnénk, hogy a kedvezményezett a harmadik évben indulva négy éven keresztül minden év végén 150 Ezer Ft-ot ebből felvehessen, ha a bank által nyújtott kamatláb 12%  1  1  = 455602 (ennyi pénzek kell lenni a számán a kifizetés PVAN = 150000 ⋅  −  4  0 ,12 0 ,12 ⋅ 1,12  megkezdésekor) C 0 =455602· 1 1,12 2 Örökjáradék Ha a járadékfizetés korlátlan ideig tart, akkor örökjáradékról beszélünk, örökjáradéknak csak a jelenértéke érdekes. Jelölés: PVP: örökjáradék jelenértéke Ismétlés Mértani sorozat összegképlete: 1 + q + . + q n = q n +1 − 1 q −1 q n +1 − 1 n ∞ q − 1 Végtelen mértani sorozat összegképlete: 1 + q + . + q n = lim lim q n = 0 (ha 0<q<1) n ∞ PVP= C ⋅ q n +1 − 1 1 1 (ha 0<q<1) =− = n ∞ q − 1 q −1

1− q lim 2 1 1  1  + C⋅  + . = C ⋅ 1+ r 1+ r 1+ r  2   1 1 1 1 1+ r C  1  ⋅ = C⋅ ⋅ = + 1 +  + . = C ⋅ 1 1+ r 1+ r r r  1 + r  1 + r   1− 1+ r Szemléletesen Ha elhelyeznek C/r tőkét r kamatláb mellett egy évre, kamata egy év után: C/r∙r=C, ez kifzetésre kerül, a tőke: C/r, a tőke ugyanaz marad, és a kamatot végtelenségig fizetik 1.35 Egy elektromos cég minden év végén 100 000 Ft jutalomban szeretné részesíteni a főiskola legeredményesebb hallgatóit. Mennyi pénzt helyezzen el az év elején az alapítványban, ha a banki kamatláb 5% C=100 000 r=0,05 PVP=100 000/0,05=2 000 000 2 000 000 Ft-ot kell elhelyeznie Növekvő örökjáradék Ha megkívánjuk, hogy a kifizetett összegek növekedjenek, akkor növekvő örökjáradékról beszélünk (tegyük fel, hogy a növekedés üteme állandó) Jelölés Megnevezés Egysége g Növekedési ráta (az a százalékláb, amellyel a

kifizetések Százalék növekednek) PVGP Present Value of Growing Perpetuity – növekvő örökjáradék Pénzegység jelenértéke 2  1 1 1 + g  1 + g  1 1 2  ( ) + + C1 (1 + g ) ⋅ + + ⋅ C 1 g . C + = ⋅ + . =   1 1 2 3 1+ r 1+ r 1+ r  1+ r   (1 + r ) (1 + r )  C 1 1 = C1 ⋅ ⋅ = 1 1+ g r − g 1+ r 1− 1+ r PVGP = C1 ⋅ 5. oldal Operációkutatás 2.Lineáris algebra elemei 2.1 Mátrixok - a közgazdaságtanban használt adatokat gyakran táblába elrendezve adjuk meg, pl: A termék B termék Ha rögzítjük a sorok és az oszlopok címkéjét, akkor elég a 1. üzem 2000 1000 számtéglalapot megadni. 2. üzem 3. üzem 5500 3000 -  Mátrixnak nevezzük bármely m∙n számú elem m sorba és n oszlopba való táblázatos elrendezését. Jelölése és általános alakja:  a 11 a A =  21  .  a m1 a 12 . a m2 . a 1n   = a ij   . a mn  [ ] a ij az i. sor és a j oszlop

kereszteződésében álló elem Bár a definícióban nem kötöttük ki, a továbbiakban elemek valós számok lesznek, azon belül egész számok. Egy mátrix m∙n típusú, ha m sora és n oszlopa van: A m⋅n Speciális mátrixok Zérusmátrix: nullmátrix, minden eleme 0 (típusa bármilyen lehet) Jelölése: 0  a1  Oszlopvektor: olyan mátrix, amelynek egyetlen oszlopa van, azaz m∙1 típusú, jelölése: a =  .  a m  Sorvektor: olyan mátrix, amelynek egyetlen sora van, azaz 1∙n típusú, jelölése: b* = [b1 . b n ] Kvadratikus mátrix: négyzetes mátrix, formája nem téglalap, hanem négyzet, olyan mátrix, amely sorainak és oszlopainak száma megegyezik, ezt a közös számot a mátrix rendjének nevezzük. Egységmátrix:  a 11 . a 1n   Jelölése: n-ed rendű: A n =  .  a n1 . a nn  olyan kvadratikus mátrix, amelynek a főátlójában csupa 1 áll, az összes többi elem 0  1 0 . 0 0 1 

 Jelölése: E n =  . 0    1 0 Szimmetrikus mátrix: olyan kvadratikus mátrix, amelynek a főátlóra szimmetrikus elemei megegyeznek, azaz a ij =a ji (minden i ≠ j esetén), Pl. három város közötti páronkénti távolság Km-ben: 0 15 30 0 28 30 28 0  15 Egységvektor: olyan sor vagy oszlop vektor, amelynek az egyik eleme 1, a többi nulla Jelölése pl: 1 e1 = 0 e * 2 = [0 1] 0 Az index az 1-s helyére utal 6. oldal Operációkutatás 2.2 Műveletek mátrixokkal  Két mátrix megegyezik, ha azonos típusúak és a megfelelő elemeik (azonos indexű) megegyeznek (egyenlőek)  Egy mátrix transzponáltján a sorainak és oszlopainak felcserélésével kapott mátrixot értjük. Jelölése: A m⋅n  a 11 . a 1n   a 11    =  .  transzponáltja A * m⋅n =  . a m1 . a nm  a 1n . a m1    . a mn  Egy sorvektor egy

oszlopvektor transzponáltja transzponáltja az eredeti mátrix.  Két azonos típusú A és B mátrix A+B összegén azt a velük azonos típusú mátrixot értjük, melynek elemeit úgy kapjuk, hogy a mátrixok megfelelő elemeit összeadjuk (hasonlóan értelmezhető több azonos típusú mátrix összege).  Két azonos típusú A és B mátrix A-B különbségén azt a velük azonos típusú mátrixot értjük, amelynek elemeit úgy kapjuk, hogy az A mátrix elemeiből a B mátrix elemeit kivonjuk.  Egy A márix λ∙A skalárszorosán (ahol λ egy valós szám) azt, a vele azonos típusú mátrixot értjük, amelynek elemeit úgy kapjuk, hogy a mátrix minden elemét a λ skalárral megszorozzuk.  − 1 2 2.21 Adott az A =  3 0 − 2  1  0 3  és a B =  1  − 2 1  − 4 2  . Adjuk meg a C=3A-2B mátrixot! − 1 0  − 3 14 − 3 5  C=  1 − 2 3  2.22 Egy Kft három féle alkatrészből

szerel össze kész árukat Egy r* = [560 135 320] vektorban tárolja az alkatrészekre feladott rendeléseket, egy másik a* = [11 28 20] vektorban az alkatrészek egységárait. (természetesen azonos sorrendben közölve az alkatrészeket, a rendelés db-ban az egységár Ft-ban értendő) Hogyan számíthatjuk ki, hogy mennyibe kerül a rendelés? Az ár: 560·11+135·28+320·20=16 340  Két vektor skaláris szorzata egy n elemű a* sorvektor szorzatán azt a valós számot értjük, melyet úgy kapunk, hogy a vektorok megfelelő elemeit összeszorozzuk és ezeket a szorzatokat összeadjuk. Jelölése: a*∙b  b1  Tehát: a*∙b = [a 1 . a n ]⋅   = a 1 ⋅ b1 + a 2 ⋅ b 2 + + a n ⋅ b b Tulajdonsága: kommutatív: a*∙b= b∙a b n  2.23 Tegyük fel, hogy az előző Kft Három egymás utáni rendelését tárolja, és az ár mellett a rendelt alkatrészek összes tömege is lényeges adat Ár (Ft) Tömeg (db) ????????????? 11 8

28 9,2      8  5,6  Rendelések (db) 1 2 3 [560 [400 [400 135 320] 100 465] 175 210] 16340 7514 16500 6724 13500 5986  Egy m∙k típusú A mátrix és egy k∙n típusú B mátrix A∙B szorzatán azt a m∙n típusú mátrixot értjük, melynek c ij elemét úgy kapjuk, hogy az A i sorát, mint sorvektort skalárisan összeszorozzuk a B mátrix j. vektorával, mint oszlopvektorral Tehát: C ij =a i1 ∙b 1j +a i2 ∙b 2j ++a ik ∙b kj [a i1  b1 j    . a ik ]⋅   b kj    7. oldal Operációkutatás Vigyázni kell a mátrixok típusára. Az első mátrix oszlopainak száma megegyezik a második mátrix sorainak számával! A mátrixszorzás nem kommutatív! Pl. A 3∙4 B 4∙2 A 3∙4 ∙B 4∙2 =C 3∙2 B 4∙2 ∙A 3∙4 nem értelmezett 1 0   2.24 Legyen a =  0  és b =  1  A lehetséges szorzatok a következők: − 1 −

1 a∙b, b∙a skaláris szorzat nem értelmezett a*∙b, b∙a skaláris szorzat értelmezett: [1 0 −1] 0 1   −1 [1] a*∙b, b∙a skaláris szorzat nem értelmezett a∙b*=c 3 3 értelmezett [0 1 0   −1 1 −1] 0 1 − 1 0 1 0    0 − 1 1  b∙a*=c 3 3 értelmezett, de nem egyenlő a∙b-val [1 0 1   −1 0 −1] 1 0 0  1 0 − 1   − 1 0 1  A mátrixok gazdasági alkalmazása A termelési összefüggések leírására jól alkalmazhatók a mátrixok, és a közöttük értelmezett műveletek. Egy üzem m féle erőforrás (ε 1 , ε 2 ,ε m ) felhasználásával n féle terméket (τ 1 , τ 2 , τ m ) gyárt. T m∙n (technológiai mátrix) (sorai az erőforrásokkal, oszlopai a termékekkel vannak címkézve) t ij eleme megmutatja, hogy az ε i erőforrásból hány egységet használtak fel τ j termék

egy egységének előállításához. Az erőforrásokkal kapcsolatos vektorok (m elemű oszlopvektorok) k: kapacitás (mennyi áll az adott erőforrásból rendelkezésre. k i eleme megadja, hogy az ε i erőforrásból mennyi áll rendelkezésre a: árvektor a i eleme megadja, hogy az ε i erőforrásnak mennyi az egységára A termékekkel kapcsolatos vektorok (n elemű sorvektorok) p*:program vektor. p i eleme megmutatja, hogy τ i termékből mennyit kívánnak gyártani t*: a további költségeket tartalmazza. k i elem megmutatja, hogy egységnyi τ i terméknek mik a további költségei c*: bevételvektor. c i eleme megmutatja, hogy τ i terméket mennyiért lehet értékesíteni Ellenőrizni lehet, hogy végrehajtható-e a program. T∙p megadja, hogy az erőforrásokból mennyit használnak fel a program során. Szükséges feltétel: T∙p≤k Megjegyzés: Ha A és B azonos típusúak, akkor A < B, ha ez elemenként teljesül. A program profitja (amennyiben

végrehajtható) Költségek: az erőforrások költsége: a*∙T∙p további költségek: t*∙p Bevételek: c*∙p Profit = c*∙p – (a∙T∙p + t∙p) = (c - a∙T - t)∙p 8. oldal Operációkutatás 2.25 Egy pékség alapvetően 4 nyersanyag (tojás, liszt, cukor, margarin) felhasználásával kétféle teasüteményt gyárt. A termelést az alábbi adatokkal írjuk le, a fenti jelöléseket használva. Egységek: tojás esetében db, többi nyersanyag esetében Kg, az áraknál Ft 3 270 4  25  160  0,7 0,8     k=  a =  80  p* = [30 50] t = [252 168] c = [200 550] T=  50  0,2 0,3 140         20  0,2 0,2 300 Végrehajtható-e a program? (T·p≤k) 30 50   3 4 0,7 0,8   0,2 0,3   0,2 0,2 Mennyi a profit? 270  61     21     16  ≤ 270 160    Tehát a program

végrehajtható.  50     20   25   80  Költségek erőforrásra: [270 61 21 16]⋅   = 19370 további 140   300 30 30 [252 168]⋅   = 15960 Bevétel: [700 500]⋅   = 48500 50 50 A profit: 48500-19370-15960=13170 Ft. 2.3 költségek: Lineáris egyenletrendszerek megoldása Egy szállodában 68 szoba van, mindegyik 2 illetve 3 férőhelyes, melyikből mennyi van, ha összesen 161 vendéget tudnak elhelyezni? x 1 : 2 férőhelyes szobák száma x 2 : 3 férőhelyes szobák száma x 1 + x 2 =68 2x 1 +3x 2 =161 2x 1 +3x 2 =161 -2x 1 +2x 2 =136 x 2 =25 x 1 =43 25 db 3, és 43 darab két férőhelyes szoba van.  Az x1, x2 xn ismeretleneket tartalmazó a 11 x 1 +a 12 x 2 ++a 1n x n =b 1 a 21 x 1 +a 22 x 2 ++a 2n x n =b 2 a m1 x 1 +a m2 x 2 ++a mn x n =b m egyenletrendszert lineáris egyenletrendszernek nevezzük. a ij i. egyenletben j ismeretlen együtthatója bi i. egyenlet jobboldalán

álló konstans hacsak másképp nem említjük ezek valós számok és az ismeretleneket is a valós számok körében keressük. A lineáris egyenletrendszer homogén, ha a jobb oldalon álló konstansok mindegyike 0, ellenkező esetben inhomogén. Lineáris egyenletrendszer megadása mátrixok segítségével A m ⋅n  a 11 =  . a m1 a 12 a m2 . a 1n    . a mn   x1  x  x =  2  .    x n   b1  b =  .  b m  A∙x=b  Az x 1 =S 1 , x 2 =S 2 x n =S n a lineáris egyenletrendszernek egy megoldása van, ha behelyettesítéssel az összes egyenletet igazzá teszil. Megoldási lehetőségek - 1 db megoldás van (pl. fenti feladat) - nincs megoldás: x 1 + x 2 =68 2x 1 +2x 2 =161 2x 1 +2x 2 =161 2x 1 +2x 2 =136 0=25 A két egyenlet között ellentmondás van 9. oldal Operációkutatás - végtelen sok megoldás van: x 1 + x 2 =68 2x 1 +2x 2 = 136 Elhagyható az egyik egyenlet,

mert ugyanaz teszi igazzá: x 1 =R x 2 =68- x 1 Lineáris egyenletrendszer megoldása Gauss-módszerrel A Gauss módszer alapja: Ha a lineáris egyenletrendszerben az egyik egyenlet valahány szorosát hozzáadjuk egy másik egyenlethez, akkor az így kapott egyenletrendszer ekvivalens az eredeti egyenletrendszerrel. További megengedett lépések: egy egyenlet megszorzása egy nem nulla skalárral (0x 1 ++0 x n =0 egyenleteket el lehet hagyni) 2.311 2.32 Oldjuk meg az alábbi egyenletrendszert Gauss-módszer segítségével: x 1 +2x 2 +3x 3 =7 /+(-1)-szer az első sor x 1 -3x 2 +2x 3 =5 /+(-2)-szer az első sor 2x 1 +5x 2 -x 3 =0 A megengedett lépés segítségével az első egyenlet felhasználásával a többiből kiejtjük az x 1 ismeretlent x 1 +2x 2 +3x 3 =7 x 1 +2x 2 +3x 3 =7 x 2 -7x 3 =-14 -5x 2 -x 3 =-2 /5-ször a harmadik sor 36x 3 =-72 x 2 -2x 3 =-14 Redukált egyenletrendszer, ebből alulról felfelé haladva sorra meghatározzuk az ismeretlenek értékét Megoldás: x 3

=2 x 2 =0 x 1 =1 3. Az operációkutatás alapfeladata 3.1 Mivel foglalkozik az operációkutatás Kialakulása - Nagy-Britanniában, a második világháború elején összehívták a tudósokat, hogy a hadvezetésben használható tudományos módszereket hozzanak létre (innen ered az elnevezése: operációkkal – hadműveletekkel kapcsolatos kutatás) - pl. konvoj: minél többen vannak, annál biztonságosabb, de annál lassabb is (a leglassabb hajó sebességével lehet haladni) ilyen kérdésekre kerestek tudományos választ - Kantarovics már a világháború előtt felvetett olyan kérdéseket, amik az operációkutatás kialakulásához vezethettek volna, gazdasági vonatkozásban - valós alkalmazásában a számítógépek alkalmazása elkerülhetetlen (nagy rendszerek irányításához) - fejlődésében löketet jelentett a számítástechnika fejlődése - alkalmazása: haditudományban, közgazdaságtanban, államigazgatásban, ahol nagy rendszereket kell

irányítani, műveleteket összehangolni Jellemzői - számítástechnika, számítógépek alkalmazása elkerülhetetlen - összekapcsolódik a való élet és a tudománnyal - kialakulása team-ek közös munkájának eredménye Feladata - optimalizálás 3.2 Modellezés - matematikai modellek segítségével oldjuk meg az életből vett problémákat A közgazdasági folyamatok matematikai modellezésének folyamatábrája 1. A modellezendő gazdasági folyamat megadása 1 2. A folyamat elemzése, a főbb jellemzők kiválasztása 3. Közgazdasági modell felállítása !!! 2 4. Matematikai aparátus (analízis, valószínűségszámítás, statisztika, lineáris algebra) 5. Matematikai modell felállítása !!! 6. Matematikai modell megoldása (gyakran számítógép segítségével) 4 3 7. Eredmények közgazdasági értelmezése Ez az analitikus modellelemzés 5 6 7 10. oldal Operációkutatás Szimulációs modellelemzés A közgazdasági modellt sokszor lejátszuk

(leggyakrabban számítógépen) és az eredmények alapján hozzuk meg a döntésünket Különösen akkor hasznos, ha a folyamatot a véletlen is befolyásolja – szotchasztikus szimuláció A közgazdasági modellek általában döntési modellek, ennek alapfogalmai: - döntési változók: aminek az értékét a modell segítségével döntjük el - feltételi rendszer: feltételek összessége, aminek teljesülni kell – a közgazdasági modell - célfüggvény: a döntési változók függvénye, ennek az optimalizálása a cél 3.3 Készletgazdálkodás Az üzemeknek nyersanyagokból, az üzleteknek a portékából készleteket kell fenntartani. A hiány és raktározás is költségekkel jár, keressük azt a megoldást, ahol a felmerült költségek a legkisebbek, optimálisak. Csoportosítás - determinisztikus (minden információ előre meghatározott, semmi nem függ az ismeretlentől) - sztochasztikus (vannak véletlentől függő tényezők) -

költségminimalizáló modellek - megbízhatósági modellek (nem vesszük figyelembe a költségeket, a folyamatos termelés fenntartása a cél, sztochatsztikus) Optimális tételezés klasszikus modellje Feltételrendszere (1) A vizsgálat egy bizonyos terméknek egy meghatározott időszakban fellépő készletezési problémájára vonatkozik (2) Adott az időszak összes szükséglete (3) A vizsgált anyagból minden időegység alatt ugyanakkora mennyiség fogy a készletből. (4) A termékből nem engedhető meg hiány (5) A megrendelt tétel azonnal megérkezik (6) Háromféle költségtényezőt veszünk figyelembe: - a beszerzett mennyiséggel arányos, attól független költségeket illetve a raktározási költségeket A kérdés, hogy hányszor, mely időpontokban és mekkora tételeket rendeljünk, hogy a felmerülő összes költség minimális legyen. Matematikailag a jelölések (1) Az időszak a [0;T], tehát az időszak hossza T (2) Az időszak szükséglete R (3)

Az időegységre eső felhasználás r=R/T állandó (6) c m (megrendelési költség): egy beszerzés mennyiségtől független költsége c p (beszerzési költség): egységnyi termék beszerzési költsége (ára) c r (raktározási költség): egységnyi termék egységnyi időszakra vonatkozó raktározási költsége Költségek, amit minimalizálni szeretnénk Fizetünk: a megrendelésekért: n-szeri rendelés esetén c m ∙n a termékért (független n értékétől) c b ∙R a raktározásért ??? A készletek folyamatosan változnak Hogy néz ki a meglévő készlet az idő függvényében (példák) a) b) c) d) R T T/3 T/3 T T 11. oldal T Operációkutatás A helyes politika: csak akkor rendelünk ha az előző tétel elfogy és a végére is elfogy a rendelt mennyiség. A készletfüggvény képe fürészfog görbe A raktározási költség adott intervallumon Készlet q Δt Idő A függvény alatti terület: q∙Δt∙c r Idő T R ⋅ TR b) esetben C r ⋅ 3

⋅ 3 3 = C r ⋅ 2 6 TR a) esetben: C r ⋅ 2 Cr ⋅ TR TR > Cr ⋅ 2 6 Belátható, hogy n-szeri rendelés esetén akkor minimális a raktározási költség (készletfüggvény alatti terület), ha egyenlő időközönként egyenlő nagyságú tételeket rendelünk. 1 T R T⋅R = Cr 2 n n 2n Raktározási költség: Cr ⋅ n ⋅ ⋅ ⋅ R/N T n T Célfüggvény: az összes költség (ennek keressük a minimumát) k(n)=C b ∙R+ C m ∙n+ C r ∙ TR k(n)= C b ⋅ R + C ⋅ n + Cr ⋅ m   2 n  beszerzési megrendelési  költség n2= raktározási költség költség C r TR ⋅ Cm 2 n= k’(n)=C m + C r ⋅ TR  1  TR  1  ⋅− ⋅  − 2  = 0 C m= C r ⋅  2  n2  2  n  C r TR minden konstans pozitív, a gyökvonás értelmes ⋅ Cm 2 Optimális rendelésszám n= C r TR ⋅ Cm 2 Optimális rendelési időköz T = n T C r TR ⋅ Cm 2 = T⋅ Cm 2 ⋅ = C r TR Cm 2 2 ⋅T ⋅ = Cr TR C m 2T

⋅ Cr R Optimális tételnagyság R = n R C r TR ⋅ Cm 2 = R⋅ Cm 2 ⋅ = C r TR C m 2R ⋅ =q Cr T Folyamatos készletezés esetén r=R/T (egységnyi időszakra eső szükséglet) ismeretében az optimális tételnagyság: q= Cm ⋅ 2r Akkor rendelünk újra, amikor az aktuális készlet elfogy. Cr 12. oldal Operációkutatás Optimális összes költség Cb ⋅R + Cm ⋅ C r TR ⋅ + Cr ⋅ Cm 2 TR 2 C r TR ⋅ Cm 2 = Cb ⋅R + C r ⋅ C m ⋅ TR C r ⋅ C m ⋅ TR + = C b ⋅ R + 2C r ⋅ C m ⋅ TR 2 2     optimálisesetbenmegegyeznek 3.31 Egy malom naponta 50 tonna búzát dolgoz fel A búza tonnánkénti ára 24 000 forint egy tétel leszállításának fix költsége 10 000 forint, a raktározás napi költsége pedig 25 forint tonnánként. Mekkora tételekben rendeljék meg a szükséges gabonát, hogy a készletezéshez kapcsolódó összes költség minimális legyen? Mi a teendő, ha az őrlést július

1-én akarják kezdeni és a rendeléstől számított beérkezési idő egy hét? C m =10 000 C r =25 Adatok: k=50 tonna C b =24 000 q= 2C m ⋅ r = Cr 2 ⋅10000 ⋅ 50 = 200 Az optimális tételnagyság 200 tonna, 4 naponta kell rendelni 25 Terv: először június 24-én rendelünk 200 tonna búzát és 4 naponta újra rendelünk. Mennyi lesz a napi költség? 100 nap alatt: beszerzési költség: 5 000·24 000=120 000 000 Ft megrendelési költség: 25·10 000=250 000 Ft 4 ⋅ 200 =250 000 Ft raktározási költség: 25·25· 2 Összköltség: 120 500 000 Ft 100 napra. Napi költség: 120 500 000 / 100 = 1 205 000 Ft 3.32 Egy bizonyos terméket összeszerelő üzemnek az elkövetkezendő 200 nap alatt 3600 darab félkész termékre van szüksége, melyet egy távoli beszállító megbízhatóan szolgáltat. A termelés folyamatos és minden nap azonos mennyiséget dolgoznak fel. Adjuk meg a költségminimalizáló paramétereket (optimális), ha a költségek a következők: egy

beszállítás fix költsége 30 000 forint, a raktározás pedig 45 forintba kerül darabonként naponta. A beszerzési költségeknek nincs szerepe a minimalizálásban. C r =45 T=200 R=3600 r=R/T=3600/200=18 C m =30000 r= 2⋅Cm ⋅ r =154,92 Cr t= 2⋅Cm =8,61 optimális időköz Cr ⋅ r n= C r TR =23,24 ⋅ Cm 2 optimális tételnagyság optimális rendelés Mi a teendő, ha az eredménnyel értelmezési problémáink vannak? A paramétereket az optimálishoz közel választjuk meg, de a hiány nem engedhető meg. Rendelési terv (Az optimális költség értéke k= 2 ⋅ 45 ⋅ 30000 ⋅ 200 ⋅ 3600 =1 394 274 Ft a beszerzési ár nélkül) t=8,61 t=8 8 napra szükséges 8·18= 144 darabos tétel 2= 144. 8 naponta 25-ször kell rendelni (200/8=25) n=25 8 ⋅144 Költség: 25 ⋅ 30000    + 45 ⋅ 25 ⋅ 2 = 1398000   rendelésiköltség  raktározásiköltség Sztochasztikus modellek Feltesszük, hogy a beszállítási adatokra, mint

valószínűségi változókra ismertek statisztikai közelítések. Költségminimalizáló sztochasztikus modellek esetén azt a programot tekintjük optimálisnak, ahol a költségfüggvény várható értéke minimális. Megbízhatósági sztochasztikus modellek Alapja az előszállításos rendszer: a szállító csak arra kötelezi magát, hogy a megrendelt mennyiséget a határidő végéig leszállítja, de, hogy pontosan mely időpontokban és mekkora tételekben az csak tőle függ. Ekkor a folyamatos termelés fenntartásához kezdőkészlettel kell rendelkezni. 13. oldal Operációkutatás Pl. Prékopa-Ziermann A modell Feltétel rendszer: (1) Az igény és teljesítése is a [0;T] intervallumra vonatkozik (2) A felhasználás egyenletes: időegység alatt r=R/T (3) Az adott összes igény: R egység (4) A rendelt mennyiség n alkalommal, egyenlő R/n nagyságú tételekben érkezik meg (5) A szállítások időpontjai egymástól független és a [0;T] intervallumban

folytonos, egyenletes eloszlású valószínűségi változó (6) A termelést 1-ε megbízhatósági szinten biztosítani akarjuk. Kérdés: Mekkora legyen M minimális kezdőkészlet 1 ε Prékopa-Ziermann közelítés: M ≅ r ⋅ T ⋅ n≥20 esetén jó közelítés 2n 3.33 500 napon át napi 10 alkatrészt kell biztosítani 90%-os valószínűséggel, melyek 20 egyenlő részletben fognak megérkezni. A szállítási időpontok bármely realizációja egyformán valószínű Mekkora legyen az indulókészlet? T=500 r=10 n=20 1-ε=0,9 ε=0,1 ln M ≅ 10 ⋅ 500 ⋅ ln 10 = 1199,6 40 A kezdőkészlet 1200 darab alkatrész. 4. 14. oldal Operációkutatás 5.Lineáris Programozás (LP) 5.1 Lineáris programozás modellalkotás Az n-változós matematikai programozási feladatban a g 1 (x 1 , x 2 , x n )≤b 1 g 2 (x 1 , x 2 , x n )≤b 2 g m (x 1 , x 2 , x n )≤b m korlátos feltételek mellett keressük az f(x 1 , x 2 , x n ) célfüggvény szélsőértékét.

Példa (kétváltozós): keressük meg az f(x,y)= x2+2y2+y függvény szélsőértékeit az x2+y2≤1 feltétel mellett. Ha a célfüggvény és a korlátozó feltételek is lineárisak, akkor lineáris programozási feladatról beszélünk.  5.11 Tegyük fel, hogy egy varróműhely kétféle ruhamodellt tervez gyártani Minden műszakban a munkafolyamatokhoz rendelkezésre álló munkaidő korlátozott. Egy műszakra vonatkoztatva az alábbi adatok ismertek Megmunkálási idő (perc/db) Haszon (Ft/db) Szabás Varrás Hímzés A modell 3 1 1 600 B modell 3 4 0 300 Maximális idő(perc) 420 440 80 Hány darabot gyártson a cég az egyes modellekből, ha a lehető legtöbb haszonra szeretne szert tenni? Matematikai modell A modellből x darabot B modellből y darabot gyárt x,y≥0 3x+3y≤420 a szabásidő korlátozottsága miatt x+4y≤440 a varrásidő korlátozottsága miatt feltételek x≤80 a hímzésidő korlátozottsága miatt Célfüggvény: a haszon: 600x+300y, ennek

keressük a maximumát. Ez egy lineáris programozás feladat, mivel a feltételek és a célfüggvény i lineáris Forma: 3x+3y≤420 x+4y≤440 x,y≥0 (nem negativitási feltétel) x≤80 600x+300ymax Az n-változós lineáris programozási feladatban (LP feladatban) az α 11 x 1 +α 12 x 2 ++α 1n x n ≤b 1 α 21 x 1 +α 22 x 2 ++α 2n x n ≤b 2 α m1 x 1 +α m2 x 2 ++α mn x n ≤b m korlátozó feltételek és az x 1 ≥0 x n ≥0 nemnegativitási feltételek mellett keressük a z= c 1 x 1 +c 2 x 2 ++c n x n célfüggvény szélsőértékét. Ez az LP feladat standard formája (reláció jelek: ≤) Minden LP feladat standard formába hozható: - egyenlőségi feltétel: az egyenlőségi feltételeket helyettesítjük két egyenlőtlenséggel (a=b megegyezik: a≥b a≤b) - fordított állású egyenlőségeket mínusz eggyel szorozzuk (-1) Ha a standard formába hozott feladatban a b konstansok mindegyike pozitív normál feladatról beszélünk. A standard LP feladat

mátrixos alakja   x1   b1   α 11 . α 1n   c1        A =  . x =  .  b =  .  c =  .    x n  b n  α m1 c n  α mn  A⋅x ≤ b és x≥0 feltételek mellett z=c*∙xszélsőérték 5.12 Egy háziállat egy heti táplálékának négyféle tápanyagból kell tartalmaznia előírt mennyiséget Háromféle gyárilag előállított takarmányból válogathatunk melyek kilógrammonként a táblázatból kiolvasható kilogrammnyi mennyiséget tartalmaznak a tápanyagokból. Melyik 15. oldal Operációkutatás takarmányból mennyit vásároljunk, hogy a legolcsóbban állíthassuk elő a megfelelő minőségű keveréket? I. takarmány II takarmány III takarmány Minimum (kg) 1. tápanyag 0,2 0,4 0 4 2. tápanyag 0,5 0,1 0,1 2,5 3. tápanyag 0 0 0,6 3,6 4. tápanyag 0,3 0,3 0,2 5,2 Ár (Ft/kg) 40 35 55 LP modell: I. takarmányból x 1 kg-t vásárolunk x 1 ,x 2

,x 3 ≥0 II. takarmányból x 2 kg-t vásárolunk III. takarmányból x 3 kg-t vásárolunk 1. tápanyagra vonatkozó feltétel 0,2x 1 +0,4 x 2 ≥4 2. tápanyagra vonatkozó feltétel 0,5x 1 +0,1x 2 +0,1x 3 ≥2,5 3. tápanyagra vonatkozó feltétel 0,6x 3 ≥3,6 4. tápanyagra vonatkozó feltétel 0,3x 1 +0,3x 2 +0,2x 3 ≥5,2 Ez egy minimumfeladat A célfüggvény az ár: 40x 1 +35x 2 +55x 3 minimum Többváltozós LP feladat megoldása az úgynevezett szimplex-módszerrel történhet számítógép segítségével.  Egy n változós LP-feladatnak egy lehetséges megoldása egy olyan (x 1 ,x 2 ,x n ) szám n-es, amely a feltételeket kielégíti. Az optimális megoldás egy olyan lehetséges megoldás, ahol a célfüggvény értéke optimális. 5.2 A kétváltozós LP feladat grafikus megoldása Kétváltozós LP feladat (változók x 1 ,x 2): a 11 x 1 +a 12 x 2 ≤b 1 a m1 x 1 +a m2 x 2 ≤b m korlátozó feltételek x 1 ,x 2 ≥0 nemnegativitási feltétel c 1 x 1 +c 2 x

2 maximum vagy minimum A lehetséges megoldások halmazát (L) ábrázoljuk az x 1 ,x 2 síkon. x2 x1 A nemnegativitási feltétel miatt L az I. síknegyedben van αx+βy≤δ a képe az x,y-síkon αx+βy=δ δ   δ képe egyenes, amely az x-tengelyt a  ;0  pontban, az y tengelyt a  0;  pontban metszi. Ha a δ α   β értékét megváltoztatjuk, akkor az előzővel párhuzamos egyenest kapunk, mégpedig, ha növelem δ-t, akkor az egyik irányba mozdul el az egyenes, ha csökkentjük a másikba. αx+βy≤δ’ αx+βy≤δ αx+βy≤δ” Az αx+βy≤δ képe az αx+βy=δ egyenletű egyenes által határolt egyik félsík (zárt félsík). Úgy döntjük el, hogy melyik félsík, hogy egy, az egyenesen kívüli pontról eldöntjük, hogy benne van-e (általában az origót helyettesítjük). L ábrázolása 1. Ábrázoljuk a feltételeknek megfelelő egyeneseket 2. Bejelöljük a feltételeknek megfelelő zárt síkokat 3. Vesszük

ezen félsíkok metszetét az első síknegyedben 16. oldal Operációkutatás 5.21 Ábrázoljuk a koordináta-rendszerben az alábbi feltételeknek eleget tevő tartományt a) x+y≤140 x+4y≤440 x≤80 x,y≥0 y 140 130 40 80 140 x+y=140 440 x+4y=440 x+y=140 A kapott tartomány mindig zárt és mindig konvex, de nem mindig korlátos. x+4y=440 -x-y=-140 x+4y=440 3y=300 2x 1 -2x 2 ≥-8 y=100 x=140-y=140-100=40 x2 b) x 1 -2x 2 ≤2 x 1 -2x 2 ≤2 2x 1 -2x 2 ≥-8 x 1 +4x 2 ≥8 x 1 +4x 2 ≥8 x 1 ,x 2 ≥0 -4 -1 2 8 Az LP feladat L tartománya mindig zárt, mindig konvex, de lehet, korlátos vagy nem korlátos is Hogyan keressük meg az L-en az optimális megoldást? A célfüggvény: c 1 x 1 +c 2 x 2 Ennek a lineáris függvénynek a szintvonalai (tehát azon pontok halmaza, ahol az érétke egyenlő) c 1 x 1 +c 2 x 2 = γ képletű egyenesek. A szintvonalak egymással párhuzamos egyenesek, a γ növelésével az egyik irányba, csökkenésével a másik irányba

mozdulnak el. Kétváltozós LP feladat grafikus megoldása 1. felrajzoljuk L-et 2. a tartomány egyik pontján át felvesszük a célfüggvény szintvonalát 3. képzeletben elmozdítjuk a szintvonalat a megfelelő irányba (maxnövekedés, mincsökkenés) 4. megállapítjuk, hogy a szintvonalak hol hagyják el a tartományt 5.22 Megoldjuk az 511 példát -3x+3y≤420 z=600x+300ymax x+4y≤440 x≤80 x,y≥0 140 P(0;110) L R 4055 80 140 z=33000 x=80 csökken nő 17. oldal x+y=140 440 x+4y=440 Operációkutatás P(0;10)-ban a célfüggvény értéke 33 000. Egy másik pont, ahol ugyanennyi a célfüggvény értéke Q(55;0). Az origóban a célfüggvény értéke 0 A célfüggvény maximuma R(80;60) pontban van, értéke 66000. 5.23 Oldjuk meg az alábbi LP feladatot x 1 -2x 2 ≤2 a)Z= x 1 +x 2 max 2x 1 -2x 2 ≥-8 b)Z= x 1 +x 2 min x 1 +4x 2 ≥8 x 1 ,x 2 ≥0 x2 P(0;4) 2 -4 4 8 x1 csökken z=4 nő P(0;4)-ben a célfüggvény 4. Q(4;0)-ban a célfüggvény 4 a) nincs

optimális megoldás b) R(0;2) pontban van minimum, értéke 2 5.24 Keressük meg a 523 példa lehetséges megoldásainak halmazán a z= -2x 1 -8x 2 célfüggvény maximumát. Csökkenx 2 nő -4 2 P(0;4) 2 2 4 x1 x 1 +4x 2 =8 - egyenlővé tesszük valamivel a célfüggvényt, és megrajzoljuk a szintvonalat (legyen osztható –2vel és –8-cal) - vagy kiválasztunk egy pontot(0;4), kiszámítjuk a célfüggvény értékét a pontban: -32; keresünk egy másik pontot, ahol ugyanennyi az értéke: -32=-2x 1 -8x 2 pl. a (16;0) pontban - az origóban a célfüggvény értéke 0>-32 - párhuzamos-e a szintvonal és az alsó határoló szakasz? - a szintvonal nomrálvektora (-2;8) és a határoló szakasz normálvektora (1;4) számszorosok, tehát párhuzamos - maximum: a (0;2) és (4;1) potnokat összekötő szakasz pontjaiban van, értéke -16 Megjegyzés - egy szakasz pontjai A(a 1 ;a 2 ) P P(λa 1 +(1-λ)b 1 ;λa 2 +(1-λ)b 2 ) 0≤λ≤1 (λ=0 B; λ=1A) 8 B(b 1 ;b 2 ) A

(0;2) és (4;1) pontokat összekötő szakasz azon pontok halmaza: P(2∙0+(1-λ)4;2∙2+(1λ)1)=P(4-4 λ;λ+1) Ellenőrzés: λ=1/2 (2;1,5) Egy LP feladat optimális megoldásainak száma háromféle lehet - nincs optimális megoldás: - a lehetséges tartomány korlátos - egy optimális megoldás van (egy extremális pontban) - végtelen sok optimális megoldás van (az egyik határoló szakaszon) - a lehetséges tartomány nem korlátos - nincs optimális megoldás - egy optimális megoldás van (egy extremális pontban) - végtelen sok optimális megoldás van (az egyik határoló szakaszon vagy félegyenesen) 18. oldal Operációkutatás Gazdasági alkalmazások, következtetések - kapacitáskihasználásra lehet rákérdezni - szűk keresztmetszet - árnyékárak 5.25 Az 511 példa alapján Az optimális megoldás: 80 db A modell 60 db B modell (80;60) 80 x+4y=440 varrás hímzés x+3y=420 szabás Kapacitás kihasználás az optimális megoldásban: A hímzés

gépidő kapacitás maximálisan ki van használva, mert az x=80 teljesül A szabás gépidő kapacitása a hímzés gépidőhöz hasonlóan ki van használva A varrás gépidő kapacitása nincs kihasználva teljesen 80+4∙60=320<440, rendelkezésre áll még 120 perc gépidő A szűk keresztmetszetet a hímzés és a szabás gépidő kapacitása adja. Árnyékárak: A varrásidő kapacitását nem érdemes tovább növelni. A másik kettőnél megvizsgáljuk, hogy egy egységnyi kapacitásnövekedéssel mekkora haszönnövekedésre tehetnénk szert, ezt nevezzük árnyékárnak, ez a szám az adott művelet gépidő-kapacitásának a haszonra vonatkozó árnyékára. A hímzés árnyékára 3x+3y=420 (x+y=140) x=81 P’(81;59) Hímzés Szabás x=80 x=81 z=600+300y z=600+300y=66300 P’(81;59) Az új optimális megoldásban a célfüggvény értéke 66 300 Ft. A haszonnövekedés 300 egység. A hímzés gépidőkapacitásának haszonra vonatkozó árnyékára 300 A szabás

árnyékára 3x+3y=421 x=80 y=60+1/3 P”(80;60+1/3) 3x+3y=421 Hímzés Szabás x=80 3x+3y=420 P’(80;60+1/3) Az új optimális megoldásban a célfüggvény értéke 66 100 Ft. A szabás árnyékára 100, mert a haszonnövekedés 100. Következtetés: hacsak más feltételek nincsenek a hímzés gépidejét növeljük. 19. oldal Operációkutatás 5.3 Szállítási probléma A szállítási probléma alapszituációja a következő: egy bizonyos árut több feladóhelyről több felvevőhelyre szeretnénk elszállíttatni optimálisan (legolcsóbban vagy leggyorsabban). Ismertek a szállítási útvonalakra vonatkozó adatok (költség vagy időadatok) 5.31 Egy gyár négy összeszerelő üzemét (a,b,c,d) három raktárról (A,B,C) kell félkész áruval ellátni Megadjuk a raktárak készleteit és az üzemek igényeit egységekben. Adottak továbbá egységnyi árunak a raktárakból az üzemekbe való szállításának költségei (1 000 Ft-ban). Fogalmazzuk meg a

matematikai modellt! Üzemek, felvevőhelyek a b c d Készlet Raktárak, A 5 4 3 2 5 feladóhelyek B 10 8 4 7 5 C 9 9 8 4 5 Igény 1 6 2 6 (15) Kérdés: melyik raktárból, melyik üzembe, mennyit szállítsunk a lehető legkisebb költséggel Modell: x ij : az i-edik raktárból j-edik üzembe szállítandó mennyiség (a sorrendben a táblázat sorrendjét tartjuk) A raktárak készletei: Az üzemek igényei: x 11 +x 21 +x 31 ≥1 x 11 +x 12 +x 13 +x 14 ≤5 x 12 +x 22 +x 32 ≥6 x 21 +x 22 +x 23 +x 24 ≤5 x 13 +x 23 +x 33 ≥2 x 31 +x 32 +x 33 +x 34 ≤5 x 14 +x 24 +x 34 ≥6 A célfüggvény: költség: 5x 11 +4x 12 +3x 13 +2x 14 +10x 21 +8x 22 +4x 23 +7x 24 +9x 31 +9x 32 +8x 33 +4x 34 minimum Tehát ez egy lineáris programozási feladat. A táblázat neve költségmátrix (úthossz vagyidőmátrix) Az elemei nem negatívak. Ha az összes készlet és az összes igény megegyezik, akkor minden készlet el lesz szállítva és minden igény ki lesz elégítve. Ekkor

elvégezhetjük a megoldás előtt a költségmátrix redukálását. 5.32 Redukáljuk az 531 példa költségmátrixát:  5 4 3 2 A = 10 8 4 7   9 9 8 4 A raktárból minden készlet el lesz szállítva, az első sor legkisebb eleme 2. Ezért az első sorból kivonunk 2-t, ezzel a lépéssel az összköltségen változtatunk, de az optimális elszállítási útvonalon nem. Hasonlóan a többi sort is csökkentjük a legkisebb elemmel, ez a sorredukció, hasonlóan elvégezhető a redukálás oszloponként is: 3 2 1 0  0 0 1 0 A(1) = 6 4 0 3 A(2) = 3 2 0 3 5 5 4 0 2 3 4 0 Tétel: egy szállítási feladat optimális programja (a szállítási útvonalak és tételek) nem változik, ha a költségmátrixon sor, majd oszlopredukálást hajtunk végre (vagy fordítva). Megjegyzés: az összköltség változik, ezért azt a feladat megoldása végén az eredeti költségmátrixból számítjuk. Az

induló program keresése (olcsó program, igényeknek és a készleteknek megfelel) 5.33 Készítsünk indulóprogramot az 531 példához (a redukált költségmátrix felhasználásával) Az induló program: a B c d Készlet 1 4 A a: 1 egység költsége: 1·5 pénzegység A 1 0 5,4,0 0 0 2 2 1 b: 4 egység költsége: 4·4 pénzegység B 3 5,3,1,0 2 0 3 5 B b: 2 egység költsége: 2·8 pénzegység C 2 3 4 5,0 0 c: 2 egység költsége: 2·4 pénzegység Igény 1 6 2 6 (15) d: 1 egység költsége: 1·7 pénzegység 0 2 0 5 C d: 5 egység költsége: 5·4 pénzegység 0 0 Az összes költség: 72 pénzegység 20. oldal Operációkutatás A lépések - mindig a lehető legolcsóbb útvonalat választjuk - a választott útvonalon az igényelt készlet alapján határozzuk meg a szállítandó mennyiséget (kisebb) - bástyamozgás szerint haladunk - egy sorban, vagy oszlopban addig maradunk, amíg azt ki nem merítettük - ha egy sort és oszlopot egyszerre merítünk ki (ezt

az esetet degenerációnak hívjuk) akkor megkeressük az adott sor és oszlop legkisebb elemét és odaugrunk, 0 egységet szállítottunk és fordulunk. A program javítása (a legolcsóbb program megkeresése) A programba bevont elemek úgynevezett kötött elemek ( ) azok az útvonalak, amelyeken szálítunk,. A többi elem az úgynevezett szabad elem Belátható, hogy a kötött elemek száma megegyezik az úgynevezett kritikus számmal (m+n-1, ahol a költségmátrix típusa m∙n) El kell döntetnünk a szabad elemekről, hogy érdemes-e őket bevonni a programba (költségcsökkenést okoznak-e) 5.34 Döntsük el az 533 példa indulóprogramjában, hogy érdemes-e bevonni az Ad útvonalat a b c d Készlet A költségmátrixból kiszámítva a program változik, a költségek: A 1 0 + 5,4,0 0 02-4+8-7=-1<0 (A költségváltozás –1) B 3 5,3,1,0 2+ 0 3C 2 3 4 5,0 0 Igény (15) Az átcsoportosított tétel csak 1 egység lehet, mert a Bd útvonalról csak egyet

csökkenthetek. Tétel: ha a kötött elemek száma megegyezik a kritikus számmal, akkor minden szabad elemhez található hurok, azaz egy olyan zárt út, ami a szabad elemből indul, kötött elemeknél fordul és visszatér. Mindig hurok mentén kísérelünk meg javítani, amelyben a legnagyobb költségcsökkenést érjük el. Megjegyzés: a program optimális, ha semelyik hurok mentén nem érhető el javítás, a hurok mentén való javítást disztribúciós lépésnek nevezzük. Adjuk meg az 5.31 példa optimális programját Ac elem bevonható-e? a b c d Készlet A költségmátrixból kiszámítva a program változik, a költségek: A 1+ 0 5,4,0 0 - 03-4+8-4=+3 > 0 nem érdemes bevonni B 3 5,3,1,0 2+ 03 C 2 3 4 5,0 0 Igény (15) Hasonlóképpen megvizsgálható a többi is, azokat sem érdemes bevonni. Például az aA elem a b c d Készlet A költségmátrixból kiszámítva a program változik, a költségek: A 0 5,4,0 0 - 0+ 1 2-4+8-7=-1<0 (A költségváltozás

–1) B 3 20 3+ 5,3,1,0 C 2 3 4 5,0 0+ Igény (15) A program javítása Ad szabad elem bevonásával a b c d Készlet 1 -3 1 A 1 5,4,0 0 0 0 2 B 3 3 5,3,1,0 23 0 C 2 3 4 5,0 05 Igény (15) Meg kellene vizsgálni az új programban is, hogy a szabad elemek bevonhatók-e (Nem) A a: 1 egység költsége: 1·5 pénzegység b: 3 egység költsége: 3·4 pénzegység d: 1 egység költsége: 1·2 pénzegység B b: 3 egység költsége: 3·8 pénzegység c: 2 egység költsége: 2·4 pénzegység C d: 5 egység költsége: 5·4 pénzegység Az összes költség: 71 pénzegység Ha kevesebb készlet van, mint igény, akkor felveszünk egy fiktív tárolóhelyet a hiányzó készlettel. A költségmátrix fiktív sorába 0 elemeket írunk (mert a fiktív helyről szállítás helyben 21. oldal Operációkutatás maradást jelent.) Ezt az új sort a redukálás előtt kell beírni a program érdelmezésekor az a felvevőhely, amely a fiktív tárolóhelyről szállít, hiányt könyvelhet

el. Hasonlóan ha az igény kisebb fiktív felvevőhelyet (oszlopot) veszünk fel. 5.35 Készítsünk jó indulóprogramot az alábbi szállítási problémához Az F i (1≤i≤3) feladóhelyeken álló vagonokat kell az R j (1≤j≤2) rendeltetési helyekre elszállítani, hogy a szállítás összes ideje a lehető legrövidebb legyen, akkor a cellákban az adott útvonalon való szállítás idejét látjuk órában, cél az összes idő minimalizálása R 1 R 2 Készlet 15 vagon helyben fog maradni. Indulótábla: F1 8 8 10 R 1 R 2 R 3* Készlet F2 6 9 15 45 F3 8 4 20 F1 2 4 0 10 F2 0 5 0 15 Igény 12 18 F3 2 0 0 20 Igény 12 18 15 45 30 Degeneráció: ha egyszerre merül ki egy sor és egy oszlop. A sor és az oszlop összes eleme körül a legkisebbe ugrunk, oda 0 egységet programozunk és folytatjuk az eljárást. F1 F2 F3 Igény Programunk nem optimális, de az optimális leolvasható: R 1 R 2 R 3* Készlet F1 2 4 0 10 10,0 12 3 F2 5 15,3,0 0 0 F3 2 0 18 0 2 20,2,0 Igény

12 18 15 0 0 13 10 0 R1 R2 2 10 4 0 5 22 12 2 0 R 3* Készlet 10,0 00 15 15,0 0 0 18 0 20,18,0 18 15 0 0  Adott egy nem negatív mátrix, amelynek minden sorához és oszlopához adott egy-egy nem negatív egész szám. A szállítási feladatban a mátrix minden eleméhez hozzárendelünk egy-egy nem negatív egész számot, úgy, hogy a hozzárendelt értékek soronkénti és oszloponkénti összege a sorhoz ill. oszlophoz előre adott szám legyen (ezt az indulóprogram is teljesíti) és a mátrix elemeit a hozzárendelt értékkel megszorozva és ezeket a szorzatokat összegezve kapott érték a lehető legkisebb legyen. 6.Hálós tervezések 6.1 Gráfelméleti alapfogalmak  A gráf szögpontok (pontok, csúcsok) és élek halmaza, ahol az élek végpontjai szögpontok Megjegyzés: a gráf nem geometriai objektum, hanem szimbolikus objektum (csak a akapcsolatokra utal) Hol használható? - Euler Königsbergben élt, a város egy folyó két partjain és két szigeten

fekszik, a sétálgató polgárok megkérdezték, hogy köre lehet-e úgy menni, hogy minden hidat csak egyszer érintenek. A B A szögpontok a városrészek Az élek a hidak D C - egy mérkőzés négyes döntője: a négy csapat, vagy négy játékos a szögpontok, a mérkőzések az élek (négycsúcsú teljes gráf: minden él be van húzva) A B D 22. oldal C Operációkutatás Fogalmak Izolált pont: Hurok: Párhuzamos élek: Egyszerű gráf: Út: a ponton Kör: Izomorf: egy olyan pont, amelyből nem indul ki él A egy olyan él, amelynek a két végpontja megegyezik B olyan élek, melyeknek végpontjai megegyeznek egymással olyan gráf, amiben nincs se hurok, se párhozamos él olyan egymáshoz kapcsolódó élek sorozata, amely nem megy át kétszer ugyanazon olyan út, aminek a két végpontja egybeesik A B C D Összefüggő gráf: olyan gráf, amelyben bármely két pont között vezet út  Az irányított gráf olyan gráf, amelynek élei irányítottak.

Példák: Vállalatok közötti áruforgalom: A B (a pontok a vállaltoknak felelnek meg, az élek az áruszállításnak, az irányítás: honnan-hova) C A Négyes döntő pillanatnyi állása: D B (szögpontok a játékosok, az élek a már lejátszott játszmák, irányítás: ki győzött le kit) D C Az irányított út és az irányított kör analóg fogalmak. Forrás: olyan szögpont, amelyikből csak kifelé indul él, felé nem érkezik irányított él Nyelő: olyan szögpont, amelybe csak érkezik, de belőle nem indul ki irányított él  A hálózat olyan irányított gráf, amelynek éleihez valós számot rendelünk. 6.2 Determinisztikus időütemezés (CPM) A program egy cél érdekében szükséges tevékenységek halmaza, amelyek között sorrendi kapcsolat van. Tevékenységháló egy program hálózattal való szemléltetése, ahol: - az élek a tevékenységek - az élekhez rendelt értékek a tevékenységhez szükséges idők - a pontok egy él kezdete

vagy vége: események (tevékenységek kezdetei és végei) X<<Y: X megelőzi Y-t 6.21 Rajzoljuk meg az alábbi gyártmánytervezési program tevékenységi hálóját Tevékenységek és a hozzájuk szükséges idő: A: tervezés 6 hét E: mintakollekció szétküldése 9 hét B: piackutatás 4 hét F: gyártás előkészítés 6 hét C: mintagyártás 12 hét G: gyártás 6 hét D: eladás előkészítés 10 hét H: eladás 15 hét A<<C, C<<E, C<<F, F<<G, B<<D, D<<H, E<<H A tevékenység háló: 0 A 6 1 B 4 3 C 12 D 10 2 E 9 4 F 6 5 H 4 6 G 6 Hálózat: Forrás: 0 esemény, Nyelő 6 esemény, mint irányítatlan gráf összefüggő, mint irányított gráf nem tartalmazhat irányított kört. Mindig egyetlen forrás és nyelő lehet Időütemezés: minden i eseményhez megadjuk a legkorábbi időpontját (t i ) és a legkésőbbi időpontját (ˆ t i ). Formája: i ti ˆ ti 23. oldal Operációkutatás 6 6 0 0 0 1

A 6 B 4 3 12 4 17 18 18 C D 2 E 9 F 5 6 27 27 24 36 6 G H 42 42 6 4 10 4 t i : a nyilak mentén előrehaladva összeadással, ha több beérkező nyíl van a legnagyobbat választjuk ˆ t i : a nyilak mentén visszafelé haladva kivonással, ha több induló nyíl van a legkisebbet választjuk. 6.3 Véletlentől függő hálós tervezés (PERT módszer) - 1958-ban az USA-ban találták fel egy rakétaprogram kialakításánál - a tevékenységi idők nem determinisztikusak, a véletlentől függő valószínűségi változók Közelítése Legyen adott a tevékenység időknek egy legvalószínűbb becslése (m), egy optimista (a) és egy pesszimista (b) becslése. a<m<b A tevékenységi időket, mint valószínűségi változókat a PERT módszerben úgynevezett β eloszlással szokták közelíteni. A β eloszlás sűrűség függvénye f(x) = c∙(x-a)α∙ (b-x)β a≤x≤b 0, különben ∞ a m b ∫ f (x)dx = 1 c értékét úgy számítjuk, hogy

−∞ A β eloszlás várható értéke: M= a + 4m + b b−a , a β eloszlás szórása D= . 6 6 A tevékenység idők kiszámolt várható értéke segítségével ugyanúgy járunk el az eseményütemezésben, mint a CPM-ben. A tevékenységidők független valószínűségi változók, így összegzésükkor a várható értékek összeadódnak és a megfelelő szórásnégyzetek is. 6.31 Adott az alábbi tevékenységlista, ahol a a tevékenységi idő optimista, b a pesszimista, m a legvalószínűbb becslése. i 0 1 1 2 2 3 j 1 2 3 3 4 4 a 10 5 8 3 12 9 m 12 7 9 5 15 11 b 16 9 12 7 18 13 a) számítsuk ki a tevékenységidők várható értékét és szórásnégyzetét b) rajzoljuk meg a hálót c) adjuk meg az eseményütemezést d) számítsuk ki a program befejezési idejének várható értékét és szórását e) mennyi a valószínűsége, hogy a program 37 napon belül befejeződik a) i-j 0-1 1-2 1-3 2-3 2-4 3-4 M 37/3 7 28/3 5 15 11 D2 1 4/9 4/9 4/9 1 4/9 b) 58/3 0

0 0 37/3 37/3 37/3 1 7 28/3 24. oldal 2 3 58/3 5 15 33/3 73/3 73/3 4 106/3 106/3 Operációkutatás c) A program befejezési idejének várható értéke 106/3 nap (35,33 nap) szórása (a kritikus úton összegezzük a szórásnégyzetet): D2=1+4/9+4/9+4/9=7/3 D=1,528 nap e) Sok független valószínűségi változó összegét általában normális eloszlással közelíthetjük. m=35,33, σ=1,53 paraméterű normális eloszlással közelítjük a befejezési időt (ξ)  37 − 35,33  A keresett valószínűség 0,86 P(ξ<37)=F(37)= φ  = φ(1,09 ) =0,8621  1,53  25. oldal