Economic subjects | Decision theory » Tánczos Lászlóné - Döntéselőkészítő módszerek

%8$3(67,0ĥ6=$.,(*<(7(0 Közlekedésgazdasági Tanszék g17e6(/ė.e6=Ë7ė0Ï6=(5( OKTATÁSI SEGÉDLET Összeállította: Tánczos Lászlóné dr. egyetemi tanár Budapest, 1995 Tartalomjegyzék 1. 2. 3. 4. 5. 6. 7. 8. 9. Döntési módszertan alapfogalmai Matematikai programozás Termékösszetétel optimalizálása Kétfázisú szimplex módszer Hozzárendelési probléma A kijelölési feladat Hálózati problémák Sorrendtervezés Körutazási probléma 2 Döntési módszertan alapfogalmai Döntés-elõkészítés: a döntési folyamat feltáró, elemzõ és modellalkotó része Döntéselemzés: azt vizsgálja, hogyan választhat a döntéshozó alternatív cselekvési lehetõségek között oKözelítésmód + módszerek tárháza Cél: A döntés, mint fogalom és jelenség meghatározása rendszerelemzési igényességgel. A döntési munka eredményességét támogató módszerek, technikák és eszközök ismertetése (a mikroszámítógépes támogatás

kihangsúlyozása). Tartalom: Döntés és döntéselmélet A döntési folyamat és összetevõi A döntési munkát segítõ módszerek, technikák és eszközök Számítógépes döntéstámogató programcsomagok és eszközök. A döntés fogalma, elemei, osztályozása Döntés = választás alternatívák között Alternatíva = lehetõséget jelent, valaminek a megvalósulását megelõzõ állapot (legalább 2 lehetõség!) A döntés objektív kényszer, amelynek tünete a probléma és forrása a célok és az adottságok között fennálló ellentmondás. Célotervezésocselekvés (átalakítás, tervezés, tanulás stb)o szervezéso irányítás = folyamat. A döntés mindig jövõorientált irányultságot fejt ki a jelenben. Megalapozott döntéshez tudni kell: x mit akarunk elérni (célok) x mi van (jelenlegi adottságok) 3 A döntés további ismérvei: az akarat hangsúlyozottsága a döntéshozók tudata A döntés hatékonysága érdekében megfelelõen

szervezett hatalmat és vezetõi tudást feltételez. Milyen korlátokkal kell számolniuk a döntéshozóknak Célkorlát: csak a szignifikáns célokat tudjuk kezelni Erõforráskorlát: a döntés idõbe, pénzbe kerül, információt igényel problémagazdák száma korlátozott. Hierarchiakorlát: döntünk nem hagyható figyelmen kívül, hogy kinek a számára Kompetenciakorlát: nem mindig azok döntenek, akiknek kellene. Módszertani korlát: észlelési korlát ( a döntési helyzet észlelése) felismerési korlát ( a döntési problémák felismerése) megkülönböztetési korlát (problémák, alternatívák kezelése) méréskorlát (megoldási lehetõségek értékelése, alapadatok megbízhatósága) Kommunkiácókorlát (a döntési folyamat jelkészlete, jelkódja és - -vevõje, a döntési folyamat dokumentálása) Döntések osztályozása : x programozott, vagy struktúrált x nem programozott, nem jól strukturált. Többcélú döntések Alapterminológia

x célok és attribútumok x érték és hasznosság 4 Érték-fa szerkesztése - annak mérése, hogyan teljesítik az egyes ajánlatok az attribútumokat x közvetlen arányok x értékfüggvények Az attribútumok súlyának meghatározása A hasznok aggregálása az additiv modell használatával A haszon szembeállítása a költséggel Érzékenység vizsgálat Elméleti megoldások x A módszer axiómái x Az értékek aggregálásánál alkalmazott feltételezések x Az intutív és az analitikus eredmények közötti konfliktusok %HYH]HWpVDYDOyV]tQĦVpJEH Kimenetek és események A valószínûség közelítése x A klasszikus megközelítés x Közelítés a relatív gyakorisággal x Szubjektív közelítés Kölcsönösen kizáró és elõforduló események Az addíciós szabály Kiegészítõ (komplementer) események Marginális (határ) és feltételes valószínûség Az összeszorzódási szabály Valószínûségi fák Valószínûségi eloszlások Várható

érték A valószínûségelmélet axiómái 5 Döntés bizonytalanság esetén A várt monetáris érték kritériuma (EMV) Az EMV érték korlátozásai Egyetlen attribútumú hasznosság Hasznossági függvények a nem monetáris attribútumokra A hasznosság axiómái Többet a hasznosság felderítésérõl Mennyire hasznos a hasznosság a gyakorlatban Több vonzatú (attribútumú) hasznosság x A kölcsönös hasznosság függetlenség x A több vonzatú hasznossági függvény levezetése x A több vonzatú hasznosságok interpetálása x További szempontok a több atributúmú hasznosságról. Döntési fák és hatás-diagramok A döntési fa megszerkesztése Az optimális politika meghatározása Döntési fák és hasznosság Folytonos valószínûségelosztásokat involváló döntési fák A döntési fák részleges alkalmazása Döntési struktúrák értékelése Döntési fa reprezentációk felderítése Szimuláció alkalmazása döntési problémákra Monte

Carlo Szimuláció A szimuláció alkalmazása egy döntési problémára 6 döntéshez: egykritériumú: többkritériumú: kérdés: egyetlen cél, vagy “közös nevezõre” hozható, egy dimenzióban, egyetlen értékelõ skálán elbírálható p optimális megoldás nem összemérhetõ, nem komparábilis értékelõ tényezõk szerint kell elbírálni milyen módon vezethetõ vissza a feladat az egykritériumú választásra x effienciens megoldások p a “legjobb” kompromisszumos megoldás Módszerek: x matematikai programozás (optimalizálás) = lincáris programozás (szimplex módszer) = kvadratikus programozás = egészértékû programozás = enumeráció = heurisztika = szimuláció =sztochasztikus programozás = vektormaximum probléma x súlyozott többkritériumú értékelés =mérési skálák =névleges = sorrendi = intervallum = arány =imponderábiliák (közvetlen minõsítés) =hasznossági függvények 8 =bizonytalanság, kockázat

értékelése = súlyozás: közvetlen Guilford-féle páros összehasonlítás = komplex értékelés Combinex Electre KI-PA Promethee A döntéstámogató módszerek rendszerbefoglalása x modularitás x interaktivitás x egyéni v. csoportos döntés x kompetencia x egyidejûség, hálózat x döntési konferencia 6]DNpUWĘLUHQGV]HUHN|QWpVLNRQIHUHQFLiN Számítógépes programcsomagok MAUD Multi Attribute Utility Decomposition Fõbb programfunkciók: szöveges útmutató oprobléma meghatározás, alternatívák azonosítása ojellemzõk megadása és az alternatívák osztályozásao preferenciák képzése, alternatívaként a jellemzõk preferálásávalo érzékenységvizsgálat OPCOM Option Consequen cies Model (bizonytalan kiemenetetlû döntések) A MEDI-T-ATOR rendszercsalád az alábbi követelményeket elégíti ki: x a döntéstámogató rendszer az eljárás egészét átfogja (alternatívák szempontrendszer súlyozás, szakértõk stb); x a feladat

különbözõ szinteken (szempont csoportokon) megoldható, elemezhetõ, x az egyes fázisokhoz kapcsoltan igénybevehetõk a mérlegelést támogató alternatív eszközök; 9 x súlyozásra, összemérésre többféle értékelési algoritmus is igénybevehetõ; lehetõvé teszi a döntésben résztvevõk szakmai kompetenciából adódó eltérõ jelentõségnek figyelembevételét x módot ad annak megválasztására, hogy a döntésben résztvevõk együtt vagy egymástól elkülönítve (de egyszerre) dolgozzanak, a csoportok közötti interaktívitás támogatásával vagy anélkül. A rendszercsalád funkcionális egységei: x x x x x x alternatívák felvétele szakértõi adatok felvétele szempont - gráf felépítése értékelési kritériumok súlyozása értékelési kritériumok hasznossági függvényeinek megadása szakértõk minõsítési kompetenciájának megadása x adott algoritmus, ill. paraméterek szerinti összesítés x az eredmények

numerikus/grafikus megjelenítése Matematikai programozás (optimálás) ^f MP: max: L ^x gi x  L  Rn x ¢ bi x ` ; i 1,., m` Lineáris programozás: LP: max ^c , x A x ¢ b ; x ² 0 ` 0 és egész (folytonos) Egészértékû lineáris programozás: ILP: max ^c , x A x ¢ b ; x ² (diszkrét) 0 >Bineáris (kétértékû), ha még X= 1 10 q Kevert egészértékû líneáris programozás: MILP: max ^c x1  c2 x2 x1, x2 ² 0 és x2 egész . 1 max: . ^x , P x  q, x x, P x ¢ 0 A1 x1  A2 x2 ¢ b ; ` A x ¢ b ; x ² 0 ` vagyis P negatív szemidefinit! A matematikai programozás feladata: (egykritériumú feladat) Van egy f ( x ) fgv. és a lehetséges megoldások halmaza (amely részhalmaza az n méretû euklideszi térnek). E fgvnek e halmaz felett keressük a maximumát (vagy min-t) L: = ^ ` elõírás az L halmazra; tartalmazza azokat a változókat, amelyekre a feltételeket vonatkoztatjuk: LP - az f ( x ) fgv. skalár fgv ( C

, x ) és lineáris fgv x a feltétel rendszer lineáris egyenlõtlenségekbõl áll x az x vektor negatív komponensei nem megengedettek x két pozitív szám különbsége negatív szám is lehet, így negatív tartalmú x is kezelhetõ lesz x ha az eredeti feltétel fordítotto (megszorzandó-1-gyel!) A fenti módon megadott halmaz max. feladatnál min. feladatnál ábra 11 Modell-szerkesztés x bármilyen valós értéket felvehetõ döntési változó (n méretû) j = 1,., n: a változók száma A, b, c: paraméterek A (m x n méretû) együttható mátrix aij: a jedik változó egységnyi elõállítása az i-edik erõforrásból mekkora ráfordítást igényel i=1,., m; j =1,n ahol m a feltételek száma b (m méretû) elõírás vektor (korlátok) c (n méretû) célkritérium-vektor (kívánalmak) Ha m = n Ÿhatározott egyenletrendszer, ez esetben c x = Q annak megállapítása, hogy az egyetlen megoldásnak mi az értéke? Ha m ! n Ÿ a feladat túlhatározott vagy

redundásns (felesleges) feltételek vannak benne, vagy ellentmondásosak a feltételek, ilyenkor nincs megoldás! Ha m  n ez o a feladat! n: változók száma m: korlátozó feltételek száma Ha a feladatot folytonos modellben fel lehet írni és a feladat lineáris o létezik megoldás (Könnyebb olyan feladatot megoldani, amelynek végtelen sok megoldása van ofolytonos) LP: feltételes szélsõérték számítás (régen a megoldás Laplace-féle multiplikátoros módszerrel) Ma lineáris programozással - Szimplex módszer! ILP onehezebb a diszkrét modellben felírt feladatot megoldani a kombinatorikus robbanás miatt, (ugyanis a kombinatorikában a megoldások száma faktorálisan növekszik) 12 modellek Determinisztikus Sztochasztikus Alkalmazások: Optimális termékösszetétel Hozzárendelési probléma Szállítási feladat Kijelölési feladat csak valószínûségeloszlások ismeretében alkalmazhatók Hálózati modellek maximális áramlat legrövidebb út

hálóterv kritikus útja Heurisztikus módszerek sorrend tervezés körutazási modell dinamikus programozás Példa: erõforrás A termékek gyártásának fajlagos erõforrásigénye 1. 2. gép energia anyag 1 2 5 2 1 0 fajlagos nyereség (Ft/db 500 200 13 Kapacitákorlát 200 >óra@ 200 kW@ 400 >m3@  200 x2 500 x1 ¢ max 1 x1  2 x2 ¢ 200 2 x1  1 x2 ¢ 200 5 x1  0 x2 ¢ 400 200 100 100 Optimális megoldás x1 = 80 db x2 Q = = 200 Visszahelyettesítve 1.80+240= 160 200 40 óra szabad kapacitás 40 db 48.000Ft 2.80+140= 200 =200 0 kw 5.80+040= 400 =400 0 m3 Szimplex módszer bázis vált megoldás döntési változók x1 x2 kiegyenlítõ hányados változók y3 y4 y5 -Q 0 -500 -200 0 0 0 y3 y4 y5 200 200 400 1 2 5 2 1 1 0 0 0 1 0 0 0 1 200 100 80 Normál alak: -500x1-200x2 -Q=0 x1+2x2 + y3 =200 2x1+1x2 +y4 =200 5x1+0x2 +y5 =400 200 100 p 14 100 200 bázis vált megoldás döntési x1 x2 -4000 0 -200 0 0

120 40 80 0 2 1 1 0 0 0 1 0 x2 y3 y4 -Q megoldás x1 -48000 0 0 0 200 y3 x2 x1 40 40 80 0 1 0 1 -2 0 0 1 0 -Q y3 m y4 x1 bázis 0 1 0 0 1 opt. megoldás hányados kiegyenlítõ y3 y4 y5 100 -1/5 -2/5 1/5 60 40 (-500) yr 20 3/5 -2/5 1/5 (-200) x1 = 80 db x2 = 40 db ---------------y3 = 40 óra y4 = 0 kw y5 = 0 m3 -------------Q= 48.000 Ft Árnyékár gépóra 0 Ft/ó mivel 40 óra szabad kapacitás energia 200 Ft/kw “ 0 kw nincs szabad kapacitás 3 3 anyag “ 0m nincs szabad kapacitás 20 Ft/m Duál feladat 200.W1 + 200W2 + 400W3 =Z0(min) Feltétel: 1 W1 + 2 W2 + 5 W3 > 500 2 W1+ 1 W2 + 0 W3 > 200 W1, W2, W3 > 0 15 Primal (maximum) x1 + 2x2 2x1 + x2 5x1 < < 200 [hour] 200 [KW] < 400 [m3] 500x1 + 200x2 = Q max Standard forma: x1  2x2  S3 2x1  x2  S4 5x1  0. x2  S5 500x1+200x2 200 200 400 -Q=0 Simplex tabla: x2 basics változó x1p S3 1 2 S4 2 1 5 S5m 0 500max 200 S3 1 0 0 0 S4 0 1 0 0 S5 0 0 1 0 megold hányados

S3 S4m >X1 1 0 0 0 1 0 -1/5 -2/5 1/5 120 40 80@ 0 0 -100 -40000 3/5 - 2,5 1/5 40 40@ 80 -20 -4800 0 0 1 0 S3 >X2 X1 2 1 0 200max 0 0 1 0 1 0 1 0 0 -2 1 0 0 0 0 -200 200 200 400 200 100 80 min 0 (1) (2) (500) (2)(10)(200) Optimalis megoldás: x1 = 80 pieces S3= 40 hour (-dual variables) (duális változók) x2 = 40 pieces S4= 0 m3 W1=0 $/ó S5= 0 kw W2=200 $/kw W3=20 $/m3 16 Primal minimum W1,,W2,,W3 > 0 w1  2w2  5w3 ² 500 2w1  w2 0w3 ² 200 200 w1  200 w2  400 w3 Z (min ) Standard forma: w1  2w2  5w3  4 2w  w1  w2 500 v5 200 w1  200 w2  400 w3 200 Z 0 Simplex tabla basic var W1p p W2 W3 V4 V5 1 2 2 solution ratio 5 W4 W5 -1 0 500 500/1 1 0 0 -1 200 200/2 mmin 200 200 400 0 0 0 0 3/2 5 -1 1/2 400 400/3/2 =266 1 1/2 0 0 -1/2 100@ 100/1/2 =200min 0 100 400 0 100 -20000 -3 0 5 -1 2 100 2 1 0 0 -1 200 -200 0 400 0 200 -40000 >W3 -3/5 0 1 -1/5 2/5

20@ W2 2 1 0 0 -1 200 -200+240= 0 =40 0 80 200-160= =40 -480000 V4 >W1 V4 >W2 17 100/5=20 min Megoldás (optimalis) W1 =0 $/h W2 =200 $/kw W3 =20 $/m3 V4 =80 db V5 =40 db Z (min)=48000$ 40 óra szabad kapacitás 0 m3 0kw “ “ Termékösszetétel optimalizálása Feladat: Meghatározandó az optimális termékösszetétel, amely az adott erõforráskorlátok mellett maximálja az összes nyereséget ismert piaci mozgástér esetén (értékesítési lehetõségek), alsó felsõ korlát. Matematikai modell x min ¢ x ¢ x A x ¢ b max ( c, x ) hol: x b az egyes termékekbõl gyártandó darabszám az egyes erõforrásokból rendelkezésre álló kapacitások aij a j-edik termék egységnyi elõállításához szükséges i-edik erõforrás-felhasználás a j-edik termék fajlagos hozama min. értékesítési alsó korlát max értékesítési felsõ korlát cj x x feladatot 2-termékes számpéldával illusztrálva (a grafikus ábrázolhatóság

érdekében), a kiinduló paraméterek: erõforrás termék aij 1 E1 gép E2 gép fajlagos hozam [Ft/db] 200 d x1 d 1000 ; (ó/db) 2 1 1 2 2 180 290 100 d x2 18 erõforrás bi 1200 1600 kapacitás [ó] A feladat grafikus megoldása 180x1+290x2=max 1. x1  x 2 d 1200 2. x1  2 x 2 d 1600 200 d x1 d 1000 x1= 800 db x2= 400 db Q= 260000 db Egy lineáris programozási feladatnál az optimális megoldás a feltételi egyenletek által meghatározott konvex poliéder (két termék esetén sokszög) valamely csúcsán található. Két dimenziós feladatnál a célfüggvény párhuzamos eltolásával választható ki az optimális megoldás Több dimenziós feladatnál a szimplex módszer alkalmazása biztosítja a maximális célfüggvényt adó csúcs szisztematikus megkeresését. A feladat megoldása szimplex módszerrel Matematikai modell A piaci alsó korlát (mivel azt mindenképpen le kell gyártani)-a figyelembevételénél a megfelelõ mennyiséget elõre el

kell készíteni és csak ezután fennmaradó kapacitást szabad figyelembe venni: xl min = 200 db x2 min = 100 db A kiinduló feltételi egyenlõtlenségeket ezzel módosítva: xl + x2 d 900 o (1200 óra 1 ó/db . 200 db =200 1 ó/db. 100 db =100 900 óra) 19 x1 + 2 .x2 d 1200 x1 d 800 o (1600 óra o 1.ó/db 200 db = 200 2 ó/db . 100 db = 200 1200 óra A célfüggvény: Q (max) = 180 x1 290 x2 (100 db-200db) Hiányváltozók (általában kiegyenlítõ változók) bevonásával egyenlõtlenségeket egyenlõséggé alakítjuk Ÿ standard forma: x1 + x1 + x1 x2 + y1 2x2+ y2 az = 900 = 1200 (1) = 800 -------------------------------------------------(18x +290x +y +y +y ) (2) 1 2 1 2 3 A hiány változók célfüggvény együtthatója mindig 0! A hiányváltozók száma megegyezik az egyenlõtlenségek számával! Az induló szimplex tábla és a bázismegoldás: A szimplex módszer lényege, hogy a standard formában írt feladatot sajátos módon táblázatba rendezi,

majd a végrehajtott bázistranszformációk eredményeként mindíg jobb (magasabb célfüggvényértékû) megoldást kapva, végül eljut az optimális megoldáshoz. A táblázat szerkezete: (1) feltUKDWyDN|YHWNH]ĘPyGRQ ahol pl. a1 = 1 1 0 vagy a4 = 1 1 0 ai-k háromdimenziós vektorok, amelyek 3 db lineárisan független un. bázisvektor segítségével elõállíthatók. Az a3, a4, a5 lineárisan független un bázisvektorok, lineáris kombinációjukkal a a elõállítható. Ezek tehát az a -k i 1, 2 egy bázisát adják. 20 Pl.: 1 a1 = 1 a3 + a4 + a5 1 0 = 1 0 + 0 1 0 + 0 0 1 . Természetesen nemcsak (a a a ) alkothatnak bázist, hanem pl. (a , a ,a ) is 3, 4, 5 1 2 5 Minden bázisban azonban más és más formát ölt az egyenlõségrendszer, illetve a célfüggvény. Minden bázishoz tartozik egy bázismegoldás A bázismegoldás lényege: x a bázist alkotó vektorokhoz tartozó változók értéke nem 0 (kivételes esetben lehet 0 is). x a nem

bázisbeli vektorokhoz tatozó változók értéke mindig 0. Az (1) a feladatnak az (a3, a4, a5) vektorok által alkotott bázisbeli képét mutatja. A hozzátartozó bázismegoldás együtthatója 0, tehát x1=0 x2=0 Ezt (1)-be helyettesítve y1=900 óra y2=1200 óra y3=800 db A célfüggvény pedig Q=180.0+2900+0900+01200+0800=0 Ez az induló megoldás (az ábrán a P. pontnak felel meg) >Nem gyártunk semmit, nincs hozam, a teljes kapacitás rendelkezésre áll!@ A szimplex módszer segítségével ezt a megoldást fokozatosan javítjuk, míg el nem érünk az optimumhoz. Az induló bázist mindig a hiányváltozókhoz tartozó vektorok alkotják. 21 A szimplex tábla szerkezete és kitöltési szabályai: x az oszlopokat az egyes változókhoz tartozó vektorok, valamint a kapacitás értékeket és piaci felsõ korlátokat tartalmazó vektor jelöli; x a sorokat a bázisvektorok jelölik. Az elsõ sor a célfüggvényre vonatkozik; x a táblázat legelsõ eleme az adott

bázishoz tartozó bázismegoldás melletti célfüggvényérték (induló megoldásnál 0). x az elsõ sor többi eleme a célfüggvény együtthatók mínusz egyszeresét tartalmazza; x a további elemek úgy adódnak, hogy megnézzük, hogyan állítható elõ az oszlopot jelölõ vektor a bázisvektorok segítségével és az együtthatókat tüntetjük fel. Az elsõ oszlopba a kapacitások és felsõkorlátok kerülnek (ami éppen a bázismegoldás), a további mezõkbe a (1) feladat együtthatói. Ha egy LP feladatnak van optimális megoldása, akkor van optimális bázismegoldása is, tehát ilyen bázismegoldás formájában keresve a legjobb termékösszetételt, tényleg az optimális megoldáshoz jutunk. B b a1 0 Célf. 900 a3 m a4 1200 a5 800 Célf. -180 1 1 1 a2 a3 a4 a5 0 1 0 0 0 0 1 0 0 0 0 1 Go(o) G1(o) G2(o) G3(o) Célf=o y1= 900 óra y2=1200 óra y3= 800db x1=x2=0 145 0 Go(1)=Go(o)-(-290)G2(1) Célf.174000 y2=600 db y3= 800db x1=0;y2=0 p -290 1 2 0

Transzformációs Bázisképletek megoldás 174000 -35 0 0 0,5 0 1 0,5 0 G1(1)=G1(o)-1G2(1) m a3 300 a2 600 0,5 1 0 0,5 0 G2(1)=o,5G2(o) a5 800 1 0 0 0 1 G3(1)=G3(o)-0G2(1) 0 0 1 0 70 2 -1 -2 110 -1 1 -1 0 0 0 1 Go(2)=Go(1)-(-35)G1(2) Célf a1 a2 a5 195000 600 300 200 0 1 0 0 22 G1(2)=2.G1(1) G2(2)=G2(1)-o,551(2) G3(2)=G3(1)-1.G1(2) Célf.: 195000 x1=600 x2=3000 y3=200 óra y1= y2=0 Bázistranszformáció: Valamilyen bázisbeli vektort kicserélünk egy bázison kívülivel. Az új bázisnak megfelelõ bázismegoldás (ha a bázistranszformáció szabályait betartjuk) egy jobb megoldást ad az elõzõnél. Ilyen cserék sorozata vezet el az optimumhoz. A báziscsere szabályai: x a bázisba belépõ vektor (aj) kiválasztása: azon vektorok kerülhetnek be a bázisba, amelyeknél (az elsõ sorban) a célfüggvénynek megfelelõ sorban levõ szám negatív. Ezekbõl célszerû a legnagyobb abszolút értékût választani x a bázisból kilépõ

vektor kiválasztása: Ehhez el kell osztani az elsõ oszlop minden elemét a bázisba belépõ vektorhoz tartozó oszlop megfelelõ elemével, és ennek minimumát kell megkeresni (az elsõ oszlop, valamint azok a hányadosok, melyeknél a nevezõben negatív szám van, nem számítanak!) x A belépõ és a kilépõ vektor metszete: pivot. (Ez a kiválasztási szabály biztosítja azt, hogy a báziscsere után is pozitív szám maradjon az elsõ oszlopban, tehát x ² 0 képlet feltétel teljesüljön.) x az új bázisnak megfelelõ tábla: Úgy kell sortranszformációkkal átalakítani a táblát, hogy az addig a4 alatt levõ egységvektor átkerüljön a2 alá. Ez úgy hajtható végre, hogy elosztjuk az a4-nek megfelelõ sort a pivot elemmel, majd az így kapott sort megfelelõ számokkal megszorozva, levonjuk a többi sorból. A transzformációs képlet általánosan (a2 a bázisba belépõ; aj a bázisból kilépõ vektor). bg o dik bg bg 0 o Gi  . Gj o bg G1 i b1g Gk d

jk i  IB 1 bg o .G j bg o d jk 1 ahol G i(o) - a régi szimplextábla sorvektorait jelöli G i(1) - az új szimplextábla sorvektorait jelöli djk(o) - a pivot elem dik(o) - a régi tábla egy általános eleme IB1- a bázisvektorok indexhalmaza 23 izk A szimplex tábla értékelése, eredmények: Az induló, illetve a transzformáció után kapott tábla 3 féle lehet: x az elsõ sorban nincs negatív elem; ekkor az adott bázishoz tartozó bázismegoldás a keresett optimális megoldás; x az elsõ sorban vannak negatív elemek, de ezek között van olyan, amely alatti oszlopban nincs pozitív szám, a minimum keresés nem végezhetõ el. Ekkor nincs véges optimuma a feladatnak (pl. ha nincs kapacitás korlát és csak az egyik termékre van értékesítési maximum); x van negatív elem az elsõ sorban és az ezekhez tartozó oszlopok mindegyikében van pozitív szám. Ekkor végrehajtható a báziscsere A báziscserét addig kell ismételni, amíg az elsõ vagy a

második típusú táblához nem jutunk. Ha az elsõ típusú táblához jutunk, kiolvashatjuk az optimális megoldást. A végeredményhez tartozó tábla a következõ információkat tartalmazza: x a célfüggvény-értékeket (az elsõ oszlop elsõ eleme). Q = 195000Ft (ehhez kell hozzá adni a már legyártott minimumok miatti 65000Ft-t. Ekkor megkapjuk a grafikusan kiszámított 260 000 Ft-ot. x az optimális termékösszetételt x1 = 600 db x2 = 300 db y3=200 db A már legyártott minimumokat hozzáadva: x1 opt = 600+200 =800 db x2 opt = 300 +100 = 400 db x az árnyékárakat (a duál változók értékét) a célfüggvény sorában, a hiányváltozókhoz tartozó vektorok alatt w1 w2 70Ft / ora 110Ft / ora w3 = 0 Ft/db ½ °° ¾ ° °¿ >0 mert mindkét kapacitás van használva! mert a piaci felsõ korlát nincs kihasználva! Érzékenységvizsgálat: a paraméter-csoportok változása hogyan befolyásolja az optimumot 24 x célfüggvény együtthatók: Milyen

mértékû változás esetén marad a megoldás optimális? ábra x jobb oldal (kapacitások, piaci korlátok) Árnyékárak vizsgálata (egységnyi kapacitás változásához tartozó célfüggvényérték változás) o szûk keresztmetszetek feltárása (extenzív kapacitás bõvítés, csökkentés). x Együttható elemek: (termék-erõforrás kocfficciensek) Mely technológiai módosítások a legkedvezõbbek gazdasági szemponbtból (intenzív - burkolt - kapacitásváltoztatás hatásának vizsgálata) A kétfázisú szimplex módszer csak a nem bázis változókat nyilvántartó tömör táblában max Q = 2x1 + 4x2 - x3 x1 + 2 x2 - x3 d 5 2x1 -x2 +2 x3 =2 x1 + 2x2+2x3 t1 xj t0 A feladat standard alakja x1 + 2x2 - x3 + x4 2x1- x2 +2x3 -x1+2x2 +2x3-x5 2x1- 4x2 - x3 =5 =2 =1 = -Q(min) Az ugyancsak minimalizálandó segédcélfüggvény: (-) -2x1-3x2- 3x3 -x4+x5-P= -8 25 Megoldás I. fázis: keressük a rendszernek azt a megoldását, amely minimálja a mesterséges

változók P-vel jelölt összegét. Ha a P értékét tovább már nem csökkenthetjük , akkor az I. fázis végéhez értünk Ha P!O, akkor a feladatnak nincs lehetséges megoldása. I. fázis induló sz. tábla x6 x7 x8 5 2 1 x1 x2 x3 x4 1 2 -1 2 -1 2 -1 2 2 1 x5 2,5 -1 0,5 Q 0 -2 -4 -1 -P -8 -2 -3 -3 I. fázis 2. sz tábla 1 x1 x8 x3 x4 x5 -3 3 1 1 1 -0,5 -0,5 3 x6 x7 x2 4 2,5 0,5 2 1,5 -0,5 -1 0,5 0,5 Q 2 -4 2 -P -6,5 -3,5 1,5 I. -1 2 1,67 -2 -1 -0,5 fázis 3. sz tábla x7 x8 x3 x6 x1 x2 0,67 1,67 1,33 -1,33 0,67 0,33 -1,67 -7 0,33 2 0,67 2 Q 8,67 2,67 3,33 11 -P -0,67 2,33 2,67 7 x4 1 x5 1,67 -0,33 -0,67 -3,33 -1 26 -1,67 I. fázis 4. sz tábla; II fázis induló sz tábla x5 x1 x2 0,4 1,80 1,60 Q 10 -P 0 x7 x8 x3 x4 -0,8 0,4 -0,2 -1 -4,2 0,6 0,8 0,6 0,6 0,2 -0,2 0,4 -0,4 -3 2 2 0 0 1 1 1 x6 n van lehetséges megoldás a mesterséges változók oszlopait töröljük. II.

fázis 5. sz tábla: optimális megoldás x1 x4 x5 x3 x2 13 3 4 7 1,67 1,33 2 0,33 0,66 Q 19 5 3 A feladat optimális megoldása x1= 0 x2= 4 x3= 3 x4= 0 x5= 13 Q =19 27 Degeneráció (elfajulás) esetei: DPyGRVtWyWpQH]ĘNVRUiEDQ DFpOIJJYpQVRUiEDQ a) nem bázis változó alatt is találunk 0 értéket Ÿalternatív optimum b) a bázismegoldásban valamely változó 0 értékkel szerepel elõfordulhat, hogy a Q érték több iteráción át változatlan marad (ciklusba kerülhet) Az esetek tanulmányozására oldja meg (grafikusan is) az alábbi feladatokat! Max Q = 3x1 + 9x2 x1 + 4x2 d 8 x1 + 2x2 d 4 x1,x2 t 0 Max Q = 4x1 +14x2 2x1 +7 x2 d 21 7x1 +2 x2 d 21 x1, x2 t 0 A dualitás A LP feladatok értékes tulajdonsága, hogy minden esetben kétféle módon egy primál és egy duál feladatként- fogalmazhatók meg. Pl. minimumfeladat a primálban , cx a (min) Ax ² a o a duálban , ao w , (A x ² 0 Z w max ) wc A ¢ c, wc ² 0 28 A

két feladat közötti kapcsolat: ª A ao º « , » «¬ c 0 »¼ , ª A1 cº « , » «¬ ao 0»¼ Tulajdonságok: x ahány feltétel a primálban, annyi változó a duálban x a primál feladat opt. megoldásának célfüggvényértéke = a duál feladat opt megoldásának célfüggvényértékével x “merõleges” olvasás 29 A hozzárendelési probléma Sok lineáris programozási feladat megfogalmazható az alábbi modellben: Keressük az xij ²0 (1=1,.,m; j=1,,n) változók olyan nem-negatív értékeit, amelyek kielégítik n i 1,., m Di t 0 V i Di 6 xij j 1 Ax j 1., n E j t 0 Vj m Ej 6 xij i 1 ª m « « 6 «¬i 1 n 6 m xij j 1 6 j 1 D i es n m 6 6 º 6 E j »» »¼ j 1 n xij j 1 i 1 lineáris egyenletrendszert, ahol szükségszerûen m n Di 6 i 1 6 Ej >A lineárisan független feltételek száma: m+n-1@ j 1 és minimálják a m 6 n 6 c xij i 1j 1 Q x lineáris célfüggvényt. Szállítási probléma vagy (Dantzig) hálózati

áramlás tipusú probléma. 30 a0 A matematikai modell jelöléseinek magyarázata: i; i=1,.,m feladóhelyek, források j; j= 1,.,n rendeltetési helyek, nyelõk xij: az i forrásból a j nyelõbe szállítandó mennyiség (meghatározandó döntési változó) Di: Ej : cij: az i forrásban rendelkezésre álló mennyiség a j nyelõben igényelt mennyiség az i forrás és a j nyelõ közötti fajlagos “szállítási költség” (távolság, eljutási idõ, stb). a “hozzárendelés” teljes költsége Q: Kombinációs tábla paraméterei: nyelõ 1 2 . j n D . C1n . C2n D1 D2 . forrás 1 . : C11 C12 C21 C22 : : i . . . Ci1 . . . m Cm1 Cm2 E1 E2 2 E Ci2 . . . . C1j C2j : : . Cij . . . . Cmj . Cmn Ej . En . : : . Cin . . . 31 : Di . . . Dm 6D=6E Kombinációs tábla döntési változói: nyelõ 1 2 . j . n forrás 1 . 2 . . . X11 X12 X21 X22 . . . . . . i . . . Xi1 . . . . m Xm1 Xm2 . Xi2 . . . . . . . X1j . X1n X2j .

X2n . . . . . . . . . Xij . . . . Xin . . . Xmj . Xmn A hozzárendelési probléma ábrázolása gráfelméleti felfogásban: J I ai cij xij bj I=®i ~ i = 1,.,m¾ J=®j ~ j = 1,.,n¾ A hozzárendelési feladat modelljében megfogalmazható feladatok típusai: x Szükségletek kielégítése céljából anyagok, termékek, energiahordozók stb. olymódon történõ elosztása, hogy azt optimális szállítással (minimális szállítási költséggel) vagy magasabb szintû hatékonyságra törekedve, minimális termelési és szállítási összköltséggel lehessen lebonyolítani (kombinált termelési-szállítási modell) x Egyidejûleg, vagy idõben eltolva jelentkezõ fuvarozási szükségleteknek megfelelõen a szállítóeszközök (tehergk., vagon) olymódon történõ szétosztása, hogy ezek a leghatékonyabb mozgatással (min. kocsikm) kerüljenek rendeltetési helyükre. x Különbözõ munkafeladatokhoz, szállítási feladatokhoz a rendelkezésre álló

dolgozók munkaeszközök, szállítóeszközök olyan beosztása, hogy azok együttes kapacitáskihasználása optimális legyen 32 x Különbözõ helyeken folyó azonos iparágú termelés méreteinek és arányainak (minõség, fajta) meghatározása úgy, hogy az alapanyag és a késztermék termelésének és szállításának együttes költsége minimális legyen, stb. A hozzárendelési probléma ‘zárttá” tétele. ­m °6 Di = ¯i=1 m a) Ha 6 ½ feltétel teljesítése » ¿ n 6 Ej j=1 n Di ² i 1 6 Ej j 1 akkor fiktív nyelõ beiktatása: “0” szállítási költségû oszlop felvétele. m b) Ha 6 j 1 m Ej ² 6 Di , i 1 akkor fiktív forrás beiktatása: “0” szállítási költségû sor felvétele a) j b) 1 2 .j j n n+1 1 2 .j n o o o i i 1 o 1 2 . . i . . o . . . . 2 . . i . . m o m m+1 Példa: 4 telephelyrõl 5 építkezési helyre kell téglát szállítani. Adottak a telephelyi kapacitások (Di) és az építkezési

helyek igényei (Ej). A szállítási távolságok (illetve az ezekkel arányos fajlagos szállítási költségek az alábbi táblázatban vannak megadva): 33 j i 1 2 3 4 5 Di 1 6 3 5 2 7 200 2 3 7 4 4 1 80 3 5 2 3 1 6 130 4 3 5 2 3 6 90 Ej 30 210 60 80 120 500 Meghatározandók azok az xij szállítási minimalizálják az összes szállítási költséget! mennyiségek A feladat matematikai modellje: Korlátozó feltételek : X11+ X12+ X13+ X14+ X15= 200 X21+ X22+ X23+ X24+ X25= 80 X31+ X32+ X33+ X34+ X35=130 X41+X42+ X43+ X44+ X45= 90 --------------------------------------------X11+X21+X31+X41= 30 X12+X22+X32+X42=210 X13+X23+X33+X43= 60 X14+X24+X34+X44= 80 X15+X25+X35+X45=120 X11; X12,.;X15, X21,, X25; X31, X35; X41, X45 t 0 Célfüggvény: 6 . X11 + 3 X12 + 5 X13 + 2 X14 + 7 X15+ + 3 . X21 + 7 X22 + 4 X23 + 4 X24 + 1 X25+ + 5 . X31 + 2 X32 + 3 X33 + 1 X34 + 6 X35+ + 3. X 41 + 5 X42 + 2 X43 + 3 X44 + 6 X45= Q (min) A feladat

mátrixos felírása: c, x Q (min); A x ao A feladat együtthatómátrixának méretei: 34 ; x ² 0 amelyek Korlátozó feltételek száma: m+n; változók száma: m . n A X ao x11 x12 x13 x14 x15 = x21 x22 x23 x24 x25 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 11111 2 11111 3 1 1 1 1 1 4 1 1 1 1 1 . 5 1 1 1 1 6 1 1 1 1 7 1 1 1 1 8 1 1 1 1 9 1 1 1 1 200 80 130 90 30 210 60 80 120 D D D D D E E E E . . . x41 x42 x43 x44 x45 C’ [6 3 5 2 7 37 441 52 316 . 35 232 X = Q(min) ] . x11 x12 . . . x44 x45 A feladat sajátos szerkezete miatt mindig található egy lehetséges megoldás! Kiinduló megoldás megszerkesztése x Észak-nyugati sarok módszerrel m+n-1 = 4+5-1 = 8 j i 1 2 3 4 5 Di j i 1 6 3 5 2 7 200 1 2 3 3 7 4 4 2 3 1 80 130 2 5 1 6 4 3 5 2 3 2 90 Ej 3 1 2 3 4 30 170 40 Ej 40 20 80 30 90 40/40/ 0 110/30 /0 0 30/ 210/ 60/ 80/ 120/ 500 0 40/0 20/ 0 90/0 0 Q = 6.30 + 3170 + 740 + 440 + 320 + 180 +630

+ 290 = 1630 35 Di 170/0 4 30 210 60 80 120 500 5 x Dantzig (legkisebb költség) módszerrel: j i 1 2 3 4 5 Di j i 1 6 3 5 2 o7 200 1 2 3 3 7 4 4 5 2 3 1 o1 6 80 130 2 4 3 5 2 3 2 90 Ej 30 210 60 80 120 500 1 3 4 Ej 2 3 4 Di 5 30 160 6 7 10 200/ 40/0 80/0 8 80 1 50 3 80 2 130/ 50/0 60 30 90/ 4 5 30/0 30/ 210/ 60/ 80/ 120/ 500 0 160/ 0 0 40/ 0 10/0 Q = 6.30 + 3160 + 710 + 180 + 250 + 180 + 250 + 180 + 260 + 230 =1170 x Vogel féle módszerrel (legnagyobb differencia) (optimálishoz közeli kiinduló megoldás!) j 1 2 3 4 5 6 3 5 3 7 2 5 4 3 2 4 1 o7 o1 6 3 30 5 210 2 60 3 80 1 1 1 1 1 4* * 1 Di i j 1 2 3 4 Ej 0 1 * 2 1 1 1 2* 200 80 130 2 90 120 500 1 2 3 4 5 Di i 80 1 2 3 10 4 30 Ej 30/ 0 * . 200/0 80/0 80 130/90/ 0 40 90/50/ 20/0 80/ 120 500 0 /40/ 0 80 40 20 210/ 200/ 0 60/ 40/0 *: azt preferáljuk, ahol a még programozható mennyiség a legkisebb >min (200, 130, 20. 210, 60,

80)@ “ >min (200, 90,. 210, 80)@ * * Q= 3.200 +180 + 210 + 340 + 180 + 330 + 220 + 240 = 1110 (ez egyben az optimális megoldás is!) Az opt. megoldáshoz tartozó szállítási terv: x12 = 200; x25= 80: x32= 10; x33 =40, x34 = 80; x41= 30; x43= 20; x45 =40 (a többi relációban nincs szállítás, azaz x11= x13 = x14= x15=x21=x22=x23=x24=.= 0 36 A legkisebb költség szabálya (Dantzig) a kombinációs tábla mezõin végigfutva mindig azt a kl mezõt tesszük kötötté, ahol kl ij : min ij ¦ C ij ; D i  ² 0 ; Ej Xij j  ¦X ij ²o i A Vogel féle kiinduló megoldás szabálya: a kombinációs tábla minden ki nem merített ( ¦ X j ij ¢ Di ; ¦ X ij ¢ Ej) i sorában és oszlopában ismétlõdõen meghatározza a szabad mezõkben levõ két legkisebb cij paraméter közötti differenciát és a programozást mindig abban a sorban vagy oszlopban folytatja, ahol a legnagyobb differenciát találja. Legyen ez most a g sor és C gh min ( C gj : E j

j  min (D g j  ¦X j gj ² 0) ij i Akkor az xgh változó értéke X gh ¦X ; Eh  ¦X ih ) i Ezután kihagyva a g sort (vagy ah oszlopot), újra megkeressük azt a sort, vagy oszlopot, amelyekben a fenti differencia a max. A hozzárendelési feladat optimális megoldásának meghatározása $V]LPSOH[PyGV]HUV]HULQWLPHJROGiV YDJLVDPyGRVtWyWpQH]ĘNV]iPtWiVDD generáló elem kiválasztása és az elemi bázistranszformáció) az A HJWWKDWyPiWUL[ VWDELO VWUXNW~UiMD HJV]HUĦ  IHOpStWpVH PLDWW OpQHJHVHQ HJV]HUĦEEpYiOLN Az A mátrix rangja (lineárisan független vektorainak száma): m+n-1 Az A mátrix m+n sorvektora között csak m+n-1 lineárisan független vektor van, akkor pedig a lineárisan független oszlopvektorok száma sem lehet több. (a példa szerinti mátrix utolsó, 9. sora, az elõzõ nyolc sorral kifejezhetõ!) A különbözõ kombinációkban választott m+n-1 lineárisan független oszlopvektor lineáris kombinációjaként az

összes többi oszlopvektor is elõállítható. Az m.n oszlopvektorból véges, de igen nagy számú bázis választható Ha m =4 és n=5, akkor az együtthatómátrix oszlopvektoraiból (ismétléses permentáció) o3200 különbözõ bázis képezhetõ (az elõjel korlátozás miatt ezeknek csak egy részéhez tartozik lehetséges megoldás!) o egyszerûsített szimplex módszer: hurok módszer 37 A minimum feladat optimum kritériuma: ha a kombinációs tábla szabad elemeire cij - zij t 0 ahol zij = ui + vj ui és vj : a kötött elemekre (xij!0) számított potenciálpár. $]RSWLPXPNHUHVĘHOMiUiVEHPXWDWiVDDSpOGiQ 1. Kiinduló megoldást a Dantzig módszerrel felvéve 1 2 3 4 5 Di vj -ui j i 1 6 3 5 2 7 200 0 1 2 3 7 4 4 1 80 6 2 3 5 2 3 1 6 130 1 3 4 3 5 2 3 2 90 5 4 Ej 30 210 60 80 120 500 j i A szabad elemekre (xij = 0) cij (ui+vj) kiszámítása ij: cij - (-ui+vi) = 13 14 21 22 23 24 31 33 35 41 42 44 5 2 3 7 4

4 5 3 6 3 5 3 - (-0+7) (-0+2) (-6+6) (-6+3) (-6+7) (-6+2) (-1+6) (-1+7) (-1+7) (-5+6) (-5+3) (-5+2) = = = = = = = = = = = = Ej - -2 ! 0 3 10 3 8 0 -3 ! 0 2 7 6 javítási lehetõség p a nagyobb negatív számot mutató elemet vonjuk be a bázisba! 38 6 1 3 2 30 160 7 3 50 2 4 Di 10 200 80 80 130 80 60 30 7 5 210 60 30 80 90 120 500 2. iteráció j Di -ui vj j i 6 1 3 2 7 200 0 1 30 170 4 1 80 3 2 3 1 6 130 1 3 2 3 2 90 2 4 80 120 500 1 2 3 4 5 1 6 3 5 2 2 3 7 4 3 5 2 4 3 5 Ej 30 210 60 i i j : cij  (ui 3. 1 5 1 3 2 4 3 0 1 3 2 1 3 2 4 30 20 Ej 30 210 60 2 4 4 5 Di 200 200 80 10 40 80 130 80 40 90 80 120 500 2 4 4 5 optimális megoldás Q=1110 4. iteráció vj -ui j i 5 1 3 2 4 3 0 1 3 2 1 3 2 4 30 20 Ej 30 210 60 120 Di 200 80 80 90 4 5 80 40 10 210 60 40 80 80 130 40 40 80 90 120 500 alternatív optimum Q= 1110 39 80 130 80 50 30

Di 200 90 120 500 egyetlen negatív módosító tényezõjû szabad mezõ! iteráció vj -ui j i 2 4  vj ) 3  ( 2 6) 4 1 Ej 4 3 A kijelölési feladat (assignment problem) A modell a hozzárendelési probléma (két vagy több halmaz elemeinek bizonyos összekapcsolása) egy elfajult (degenerált) esete az un. kijelölési probléma (m=n) Pl.: különbözõ munkafeladatokhoz a rendelkezésre álló dolgozók olymódon való beosztása, hogy azok együttes költsége a minimális legyen. (A feladat zárttá tétele itt is biztosítandó!) A feladat matematikai modellje: ­1 l j ahol ha il egyébként Xij = ® ¯0 i=1,.n a munkafeladatok száma j=1,.n az elvégzésre alkalmas dolgozók száma nt3 n 6 X ij 1 i 1 n 6 X ij j 1 n 6 1 n 6 C ij i 1j 1 X ij Q (min ) xij = j - jelentése: az i-edik munka-feladat elvégzésére a j-edik dolgozót jelölik ki xij = 0 - jelentése: az i-edik munkafeladatot nem a j-edik dolgozó vézi el cij - azt a költséget jelöli,

amely akkor merül fel, ha az i-edik munkafeladatot a jedik dolgozó végzi el. A feladat degenerált, mivel a bázisra jellemzõ m+n-1 (mivel itt m=n, tehát 2n-1) változó helyett csak a változó értéke lesz, a többié 0. (Ez ugyanis azt jelenti, hogy minden feladathoz kell egy dolgozó; a többi összekapcsolás nem jön létre, xij=0) 40 0HJROGiVLOHKHWĘVpJHN A primál feladat lehetséges megoldásai az ilyen feladatban n-1 zéro értékû bázisváltozót tartalmaznak (ezek kezelése az optimálás során nem “gazdaságos”). Ezért célszerûbb a lehetséges duál változókhoz ragaszkodni Ezt teszi a magyar módszer (minimális fedõvonalak meghatározása, de erre nem ad algoritmust!) Ezt a hiányosságot a Ford-Fulkerson féle cimkézõ eljárás kiküszöböli o ezt az eljárást hasznosítja a primál-duál algoritmus is. Kiinduló lépés: a mátrix redukciója (minden sorban és oszlopban legyen 0) Feladat j 1 2 3 Di 4 i 1 654 10 321 43 1 2 210

54 765 10 1 3 432 10 210 65 1 532 20 1 1 421 86 1 1 4 Ej i 1 6V j 0 1 ui = min cij j 1 1 1 2 . ¦ min = 5 1 4 0 2 uj = min (cij - ui) Redukált mátrix. Megoldó algoritmus: 1. lépés: képezzük a mátrix “megengedett’’ mezõit (amelyben cij redukált értéke 0) 2. lépés: a megengedett mezõket figyelembe véve elvégzünk annyi kijelölést (xij=1), amennyi lehetséges; ezután az xij=1 értéket tartalmazó mezõket kötöttnek tekintjük. 3. lépés (Cimkézés) a.) jelöljük meg (-) azokat a sorokat, amelyekben nincs kötött mezõ. Ha ilyen sor nincs, akkor ¦ ¦i xij = ¦jEj, és az optimális kijelölés feladatát megoldottuk; b) jelöljük meg a sor indexével azokat az oszlopokat, amelyeknek van jelzett sorban megengedett, de még nem kötött (vagyis szabad) mezõje, 41 c) jelöljük meg azokat a sorokat az oszlop indexével, amelyeknek van jelzett oszlopban kötött mezõje, d) ismételjük a b) és c) lépéseket, amíg csak több sort

vagy oszlopot már nem tehetünk így jelzetté, e) ha a cimkézõ eljárssal sikerült jelzetté tenni olyan oszlopot, amelybõl újabb sor már nem cimkézhetõ, akkor a 3. lépés oszlopban fejezõdik be. (Ez azt jelenti, hogy mód van újabb mezõ kötötté tételével a kijelölések továbbfejlesztésére) o folytatás 4. lépéssel (áramlatbõvítés); ha az utolsó cimkézés sorban történt, akkor újabb kijelölésre nincs mód, ellenben újabb megengedett mezõre van szükség o folytatás az 5. lépéssel (hálózatbõvítés). 4.lépés: a kijelölések számát, vagyis a ¦i ¦j xij nagyságú áramlatot 1 egységgel növelhetjük a következõképpen: az utolsó cimkézett, vagyis kijelölést (kötött mezõt) még nem tartalmazó oszlopnak a cimke által megnevezett sorban fekvõ mezejébe beírjuk az 1-et, majd ugyanabban a sorban, a sor cimkéje szerinti oszlopban fekvõ mezõbõl töröljük az 1-et; ez utóbbi oszlopban továbbhaladva, annak cimkéje

megmutatja, hogy melyik mezõt kell kötötté tenni stb. Ilymódon végül egy oszlop cimkéjének iránymutatásával elérkezünk egy olyan sorhoz, amelyet a 3. a) lépésben (-) -val jelöltünk meg, amely ben tehát eddig még nem volt kötött mezõ, most azonban e sor kapacitását is felhasználhatjuk és ezzel az 1 egységes áramlatbõvítés megtörtént. Folytatás a 3 lépéssel 5. lépés: Jelöljük I-vel a jelzett sorok és J-vel a jelzett oszlopok halmazát. Húzzunk fedõvonalat a jelzetlen sorokon és a jelzett oszlopokon keresztül (iI). Válasszuk ki azokból a mezõkbõl, amelyeken nem megy fedõvonal keresztül, a legkisebb elemet: h = min (cij - ui - vj ) ! 0 iI jJ Vonjuk le a h értéket a költségmátrix minden olyan elemébõl, amelyet fedõvonal nem takar (iI š jJ) és adjuk hozzá a fedõvonalak metszéspontjában (iI š jJ) levõ elemekhez. Majd térjünk vissza a 2. lépéshez (vagy megõrizve az elõzõ xij=1 kijelöléseket a 3.

lépéshez) 42 1 iteráció j 1 2 3 4 Di min(4,1,3,2,1,6)=1 i 1 4 -1 01 1 -1 3 -1 1 2 3 01 4 +1 5 0 2 0 +1 01 5 1 1 4 2 -1 0 1 -1 6 -1 1 Ej 1 1 1 1 4 2 3 4 Di min (3,2,2,5,1,5)=1 2 bef. cimke hálózatbõvítés (5. lépés) - 4 2 iteráció j 1 i 1 3 -1 01 0 2 -1 1 2 2 3 01 5 +1 5 +1 0 2 -1 1 01 5 -1 1 1 3. bef cimke 4 1 -1 1 1 -1 5 -1 1 Ej 1 1 1 1 4 Di 4 o hálózatbõvítés (5. lépés) 4 3 iteráció j 1 2 3 4 01 0 1 i 1 2 1 2 4 1 1 1 3 0 4 1 - 1 1 4 01 6 6 0 1 1 01 4 01 0 Ej 1 1 2 3 4 4 4 1 2 bef cimke o 43 áramlatbõvítés 4. iteráció j 1 2 3 4 Di i 1 1 1 1 2 3 1 4 1 Ej 1 1 1 1 1 1 1 4 Optimális megoldás ¦i ¦j cij x ij 9 44 Hálózati problémák A közlekedési alkalmazások szempontjából 2 speciális probléma: x Adott élkapacitásokkal rendelkezõ hálózaton átbocsátható maximális áramlat meghatározása x Adott

élhosszúságokkal rendelkezõ hálózat kezdõ és végpontja(i) közötti legrövidebb út meghatározása A feladatok megoldó algoritmusait példákon keresztül mutatjuk be: Maximális áramlat Matematikai modell N ¦ xig N - ¦ xg-1 xgj i=1 i=1,.,N; xij d dij -Q (s,t) +Q (s,t) 0 ­ -Q(s,t); g=s ; gzs,t =®0 ¯ +Q(s,t); g=t g=1 j=1.,N; g V=^1,.N` V i, j E : a forrásból kimenõ nettó áramlat : a nyelõbe befolyó áramlat : a közbensõ pontokban a nettó áramlat 0 Példa: 2 1 6 4 4 1 2 6 5 3 5 5 3 1 U1 = (1,2,4,6) = min (4,6,5)= 4 = c1 45 4 5 1 2 2 1 4 6 5 5 5 1 4 3 5 U2 = (1,3,4,6)= min (5,5,1)=C2 2 2 4 1 6 4 4 5 4 3 5 U3 = (1,3,5,6) =min (4,4,5) =4=C3 2 2 4 6 1 3 5 46 47 Hálótervezés, kritikus út számítása PERT CPM MPM Tervezési fázisok: Tevékenységorientált Eseményorientált logikai tervezés idõtervezés: kritikus út tartalék idõk költségtervezés kapacitás hálóábrázolás

Hurokmentes, irányított, egybefüggõ gráf. A logikai tervezés szabályai: Látszat tevékenység. Idõtervezés, kritikus út számítása Eseményre vonatkozó idõadatok: x esemény lehetõ legkorábbi bekövetkezése x esemény megengedhetõ legkésõbbi kezdése Tevékenységre vonatkozó idõadatok: x tev. legkorábbi kezdése x tev. legkorábbi befejezése x terv. legkésõbbi befejezése x terv. legkésõbbi kezdése Tartalékidõk: eseményre, tevékenységre Teljes, feltételes, sabad, független tart, idõ 48 Példa: AB,C, D; BE,F; CG,J; FJ; GH; HM; IK; JM DG; ÁBRA Kritikus út: A-C G-H-M=22 ÁBRA 49 DI,M; EL; Költségtervezés Ábra Költségmutató: Kmax - Kmin topt - t min Gyorsítás a kritikus úton fekvõ tevékenységekkel, a legkisebb költségmutatójú tevékenységgel kezdve; a gyorsítás mértékét az adott tevékentség tmin értékének, illetve a szubkritikus útnak a figyelembe vételével kell végrehajtani. Kapacitás

tervezés: fokozatos közelítés az egyenletes kihasználáshoz a tartalék idõk és a tevékenységi költségmutatók figyelembevételével. 50 Sorrendtervezés A sorrendtervezés általános szempontjai Probléma felismerés o rendszerelemzés Általában ismerni kell: a termelõ rendszert, a technológiát a megbízásokat (rendeléseket) a kívánt határidõket az esetleges soronkívûliséget és a prioritást a tervezés célját Cél: a megbízót a költségek és a határidõ érdekli, a vállalkozót (kivitelezõt) az elérhetõ nyereség, amely összefügg a kapacitás kihasználással. $WHUYH]pVFpOMiQDNPHJKDWiUR]iViQiOV]yEDM|KHWĘV]HPSRQWRN 1. az átfutási idõ minimalizálása 2. a kapacitáskihasználás maximalizálása 3. a teljes költség (késedelmi kötbér, a termelésben lekötött készletek költség, szállítási költség stb) minmalizálása. utáni E szempontok közül egyesek egymással ellentétes irántban hatnak. A célfüggvényben

egyedejüleg több (azonos mértékegységgel mérhetõ) szempontnai is érvényt lehet szerezni. A sorolási problámát bonyolító feltételek: x x x x x lehetséges átfedések minõségi hibák soron kívüli javítása sürgõsság es etén bizonyos munkák kiemelése a várakozó sorból esetleges anyaghiány és egyéb akadályok figyelembevétele a szükséges gépidõk esetleges változásai stb. A gyakorlatban felmerülõ problémák (feladatok) megoldásához o egyszerû feladattípusok felimserése, kombinálása. 51 A feladat megoldása: teljes enumerációval (mind a 720 változatra meghatározandó a teljes kötbér és a minimális kötbért okozó sorrend kiválasztása) m növekedésével az eljárás munkaigényes! A feladat megoldása: LP-sal (egészértékû!) : ILP Matematikai modell felállítása: m Jelölések: T = ¦di : teljes idõszükséglet i=1 t = 1,.,T : az egyes idõegységek Döntési változó : xit : készenléti mutató i: munkaszám

t: az i-edik munkáig kummulált gépidõszükségletek ­0 xit = ® ha az i-edik munkát a t-edik idõszakra éppen befejezik ¯1 minden más esetben Korlátozó feltételek: T ¦ xit = 1 i = 1,., m minden munka egyszer befejezõdik a teljes feldolgozási idõszak alatt. t=1 m z+di -1 ¦ ¦ x it t=1 t=z =1 Z=1,.,T az i munka befejezését megelõzõ di idõszakban a gép csak az i munkával van leterhelve, mivel a munkák nem megszakíthatók m Célfüggvény: xo = ¦ i=1 ­ 0, ha t d hi ahol kit = ¯ (t -hi).ki ha t d hi A teljes kötbér minimálása T ¦ x itkit t=1 Változók száma : m.T ( 6.26 = 156) Feltételek száma : m+T (6+26 = 32) (a független egyenletek és így a bázisváltozók számai: m+T-1) Megoldás: határidõk szerint heurisztikával rajz 53 Összes késedelmi kötbér : ¦ (ti-hi) ki.xit x0= 3.5 + 54 + 42 + 51+ 67 + 91 = 99eFt A fenti heurisztikus szabállyal kapott sorrend esetén az xit változók értékei: t 1, 2,. 5 i 1 2 3 9. 12 17 19 25

26 di 6di 1 1 1 4 5 6 1 1 Megoldás 1 1 5 4 3 5 9 12 2 2 7 17 15 26 x1,5 =1 a többi xit =0 x2,9 =1 x3,12 =1 x4,17 =1 x5,17 =1 x6,26 =1 x0 =99eFt Három munka sorolása egy gépen teljes enumerációval pl. i 1 2 3 hi(h) 2 3 4 di(h) 3 2 1 ki (Ft/h) 5 4 6 ¦di=6 1. munka 2. munka 3. munka Tehát az optimális sorrend: 1, 3,2 A minimális összes kötbér: 17eFt A szimplex módszer, a teljes enumeráció és a heurisztika hatékonyságának összehasonlítása. 54 Több munka sorolása két gépen Határidõk, kötbérek nincsenek; cél: minimális átfutási idõ ŸJohnson szabály (1954) Pl. i 1 2 3 4 5 6 7 d1 3 8 2 5 3 4 7 d2 4 5 6 5 5 2 3 választási sorrend (min di) 3. 7. 2. 6. 4. 1. 5. (elõlrõl) (hátulról) (elõlrõl) (mindegy) (2. “opt”) (elõlrõl) (hátulról) (hátulról) A munkák optimális sorrendje; i: 3 - 1 -5 - 4 - 2 -7 -6 vagy 31-5-2-4-7-6 A teljes átfutási idõ kiszámítása: munka 1 gép 2 gép i 3 1 5 2 4 7 6 K 0 2 5 8 16 21 28 B

2 5 8 16 21 28 32 K 2 8 12 17 22 28 32 B 8 12 17 22 27 31 34 55 A 20 gép 1 órát vár a 7. és a 6 munkára Alternatív optimumnál mérlegelendõ! Több munka besorolása három gépen min di1 t max di2 Ha és min di3 t di2 akkor optimumkeresés: di1 + di2; di2 +di3 2 fiktív gépidõ szerint Pl. i di1 1 2 3 4 5 di2 5 7 8 6 9 di3 4 3 1 2 2 di1+ di2 di2+di3 Választási sorrend 9 10 9 8 11 12 8 6 9 8 5. 3. 1. 2. 4. 8 5 5 7 6 Optimális sorrend: 4-1-5-2-3 Teljes átfutási idõ: 41 Ha az elõzõ feltétel nem teljesül, akkor 3 változatra kell ez átfutási idõt kiszámítani és a minimálisat kiválasztani: G1;G2+G3 G1+G2;G2+G3 szerint G1+G2;G3; Több munka sorolása négy, ill. több gépen G1;G2+G3+G4 G1+G2;G3+G4 G1;G2+G3;G4 56 Két munka sorolása n gépen grafikus módszerrel Pl. Munka Gépsorrend és szükséges gépidõ 1 2 A B C D 4 2 4 3 C B A D 2 5 4 4 ¦ 13 15 rajz Ha a 45o-os egyenes metszi a négyszögeket, akkor

olyan várakozási idõket kell beiktatni, hogy a 45o-os egyenes csak érintse a négyszögeket. Az eltolást az x vagy az y tengely irányában kell alkalmazni, úgy, hogy a burkoló négyszög hosszabbik oldala a lehetõ legrövidebb legyen. 57 Körutazási probléma/ Branoh and bound módszer/Little -féle megoldás/ A feladat: 6 pont végigjárása és visszaérkezés az indulóhelyre a legrövidebb útvonallal. Az egyes pontok közötti távolságokat tartalmazza a C mátrix C=>>cij=i-bõl j-be vezetõ legrövidebb út. Modellezés: Minden i,j elemhez hozzárendelünk egy yij ^0,1` változót. yij akkor egy, ha i-bõl j-be megyünk. n Hozzárendelési feltétel: n ¦ yij = 1; ¦ yij = 1 i=1 j=1 Körutazási feltétel:Az 1 értékû változók indexei sorrenben legyenek: I =^ili2, i2i3,.,in-lin, ini1` Célfüggvény: n n ¦ yij = 1; ¦ ciyi i=1 o min j=1 Megoldás: indulásnál az összes lehetséges körutak Lo halmazára alsó becslést kapunk a C

redukiójával /f=M/ 58 C= M 7 20 21 12 23 27 M 13 16 46 43 16 M 25 27 16 1 35 M 48 30 30 5 18 M 5 5 9 5 p1 =16 p2 =1 p3 =0 p4 =16 p5 =5 p6 =5 26 25 0 18 5 M Sorszerinti redukció: minden sorban a legkisebb elemet levonjuk a sor többi elemébõl; ezek az értékek a pi-k, melyeket külön ki is irunk. C c= M 6 11 M 27 15 0 0 14 29 10 24 20 5 7 18 q1=5 13 0 41 0 q2=0 M 9 22 0 q3=0 35 M 43 4 q4=0 5 2 M 0 q5=0 0 2 0 M q6=0 Oszlop szerinti redukció: minden oszlop legkisebb elemét levonjuk az oszlop többi elemébõl: ezek az elemek a qj-k. Ekkor kapjuk a C o= t n n Az Lo-hoz tartozó alsó becslés Ko = 6 Pi  i 1 j 1 = 16 +1+ 0+16+ 5+ 5+ 5+0+0+0+0+0=48 C = M q 11 27 0 14 10 1 15 0 2 13 M 13 0 41 0 15 M 9 22 0 0 35 M 43 4 29 5 2 M 0 24 0 2 0 M r14 = 10 + 0 = 10 59 6 r14 = 10 + 0 = 10 r24 = 1 + 0 = 1 r36 = 5 + 0 = 5 r41 = 0 + 1 = 1 r42 = 0 + 0 = 0 r56 = 2 + 0 = r62 = 0 + 0 = r63 =10 + 9 = r65 = 0 + 2 = 2 0 9 2 max=r14 =10 Lo ko =48

k1 = 58 L2 1,4 L1 1,4 K2 =49 C = M q 11 27 0 14 10 1 15 0 2 13 M 13 0 41 0 15 M 9 22 0 0 35 M 43 4 29 5 2 M 0 24 0 2 0 M x L halmaz felbontása: a C q minden 0 elemére kiszámitjuk rij= min ^okj k=1,.j+1,n` +min ^okj k=1,,i-1,i+1,n`; vagyis minden 0 elem sorában és oszlopában található legkisebb elemet összeadjuk. Az rij értékek közül a legnagyobbat választva, megkaptuk azt az i1 j1 mezõt, mely segítségével szétválasztjuk Lo-t.L2 lesz az a halmaz, melyben i1 j1 viszonylat szerepel,vagyis yi1 J1 = 1, és L1 lesz az a halmaz, melyben nem vagyis yi1 J1 = 0. C C x L1-hez tartozó alsó becslés meghatározása: 1-t -gy nyerjük q -ból, hogy ci1 J1 /c1,4/ helyébe M-et 1runk, majd az így nyert mátixot redukáljuk. A redukció értéke éppen ri1, j1 /r1,4=10/ lesz, tehát k1=ko+ri1 ,j1 / k1 = 48 + 10 =58./ C co -t most csak akkor kell redukálni /minden oszlopban van 0/. 60 C 1= M 1 15 0 2 13 1 M 13 0 41 0 17 15 M 9 22 0 M 0 35 M 43 4 4 29 5

2 M 0 0 24 0 2 0 M x L2 -höz tartozó alsó becslés: A C o-ból elhagyjuk az i1 /1/ indexû sort és a j1 /4/ indexû oszlopot és a j1, i1 /4,1/ indexû elem értékét M-re változtatjuk . Az így nyert n-1 /6-1=5/-ed rendû mátrixot rdeukáljuk. A redukció nagysága = ri1, j1 /r1,4/. Az alsó becslése L2-nek k2 = ko + ri1, j1 C2 mátrix számítása C *o= M 15 1 15 13 M 0 0 9 2 41 22 13 0 0 - 29 5 2 M 0 24 0 2 0 - 28 5 2 M 0 23 0 2 0 M M Sorszerinti redukció után C *o= 0 15 M 2 13 M 13 0 41 0 14 M 9 22 0 oszloszerint mást nem is kell redukálni mint tehát C *o = C 2; r 1,4 6  6 1  0  0  0. 1 48  49 p1 qj k2 61 r21 = 14+2=16 r36 = 5+0=5 r42 = 2+0=2 r56 = 2+0=2 r62 = 0+0=0 r63 = 5+9=9 r65 =0+2=2 max.=r1=16 Lo ko=48 k2 L1 k1 58 49 L2 1, 4 1,4 L3 k3 2,1Lk44 2,1 k2  r21 4 y  2 51 49  16 65 Ezek után azt a halmazt bontjuk tovább, melyhez alacsonyabb becslés tartozik, esetünkben ez az L2, mivel k2 = 49k1=58. x L2 halmaz felbontása

/lásd az Lo felbontásánál leírtakat/. C minden 0 2 elemét megvizsgáljuk és kapjuk rij -ket; ezek közül a maximum lesz az a viszonylat, melynek alapján ismét szétválasztunk. Ez a viszonylat a 2,1 lett. L3 az a halmaz melyben y2,1 =0; az ehhet tartozó alsó becslés k3 = k2+ r2,1 = 49+16=65 L4 -ben y21=1. Elõször célszerû a C 4 mátrixot kiszámítani, mert ha, k4 k3, akkor C 3-ra már nem is lesz szükség, tehát nem számoljuk. C 4 mátric számítása: mátrixból elhagyjuk a 2, sort és az 1, oszlopot és mivel az enumerációs fa Lo L2 - L4 ágán y21= 1 és y14= 1; azaz 21 és 14 index lánc alakítható ki, ezért a teljes körút kialakulása elõtt meg kell akadályozni az alkör kialakulását;Ÿ C42-t M-nek (f)tekintjük; majd az így kapott mátricot redukáljuk: C2 = 0 15 - - - - M 13 - 28 5 23 0 C *2 = - 62 - - - - - P4 13 M - 5 0 M 0 2 2 - M 9 - 2 2 2 2 41 M 0 - 41 22 - M 0 13 0 0 M - 0 0 - 0 M A sor szerinti redukció már C

4 mátrixhoz vezet (mivel minden oszlopban is van 0 elem): C 4= - - - - - - M - 13 7 41 0 M 7 22 0 - 5 0 M 0 0 0 0 M A redukció mértéke: r 4, c 2 Az L4-hez tartozó alsó becslés: k4 k2  r4,6 49  2 51 Mivel az L4-hez tartozó alsó becslés kisebb, L4  L3,ezért az L4-t bontjuk tovább. ( C 3 kiszámítására nincs szükség) Most a C mátric 0 elemeit kell megvizsgálni a max r -t kiválasztani. 4 ij r36 = 5+5=5 r45 = 0+0=0 r46 = 0+0=0 r56 = 22+0=22 r62 = 0+13=13 r63 = 0+7=7 r65 = 0+0=0 max = r56=22 63 k5= k4+r56= 51+22=73 Lo ko=48 k1 58 L1 L2 1, 4 1, 4 k3 65 k2 49 L3 L4 2,1 2,1 k5 L5 L6 73 5, 6 5, 6 k4 51 k6 51  5 56 Elõször ismét a C mátrixot számítjuk, ugyanis, ha, k 6 6  k5=73, akkor C 5 számításra nincs szükség. C 6 mátrix számítása: Ehhez C -bõl elhagyjuk a 5. sort és a 6 oszlopot; a C mezõbe M-t (f) írunk,; 4 65 majd az így kapott mátrixot redukáljuk. C *4 = - - - - - - - - - - - - -

13 M - 5 - - M 7 - 0 - - - - - 0 0 - P3 C *6 = - - - - - - - - - - - - - - - 8 M - 0 0 - - - M 7 - 0 0 - - - - - - - - - - M - - 0 0 - M M - 5 Csak sor szerinti redukció szükséges- a redukció mértéke: r 56 5. Az L6 -hoz tartozó alsó becslés: k6 k4  r56 51  5 56 Mivel k6 = 5673 =ks, ezért L6 -t bontjuk tovább. Megvizsgáljuk C 6 0 mezõit és kiválasztjuk a max rij-t. r35= 8+0=8 r45= 7+0 =7 max =r35 =8 64 r62=8+0=8 r63=0+7=7 (Választható r62 is. Az eredmény ugyanaz) Tehát az L7 azon körutak halmaza, ahol y35=0 (tehát a 3. várost nem az 5 város követi), az azon körútak halmaza, amelyeknél y35 =1 (azaz a 3. várost az 5 város követi). A L7 -hez tartozó alsó becslés: k6+r35=56+8=64 Elõször ismét C 8 mátrixot számítjuk, mert ha k8k7=64, akkor C 7 mátrix meghatározására nincs szükség. C 8 mátrix számítása: C 6mátrixból elhagyjuk a 3. sort és az 5 oszlopot és

mivel az enumerációs faágon, Lo -L2 -L4-L6-L8 y56=1; y35=1; emiatt 35 és 56 indexlánc alakítható ki, ezért az alkörképzõdés kizárásához C63-t M-nek tekintjük; majd az így kapott mátrixot redukáljuk: Lo ko=48 k1 58 L1 L2 1, 4 14 k3 65 k5 k2 49 L3 L4 21 21 73 k7 k6  r 35 C *6 = 51 L5 L6 56 56 64 - - - - - - - - - - - 56 L8 35 35 56  7 63 - k6 L7 Az L8-hoz tartozó alsõ becslés k8 k4 65 k8 56  7 63 p4 =7 - M 7 - - - - - - - - - - 0 M - -- - Csak sor szerinti redukció: C8 = - - - - - - - - - - - - - M 0 - - - - - - - - - - 0 M - -- A redukció mértéke : r 35 7 A C 8 mátrix már másodrendû mátrix. Az átlóirányban vett két-két elemét összeadjuk és azt a két mezõt választjuk, amelyek összeges kisebb. Az ezekhez tartozó változó yij értékét 1-nek tekintjük. Mivel C mátrix alapján 8= C43+C62= 0+0+0 (C42+C43=M+M ezért L9 hlamazhoz tatozó

körutakban y43 =1 y62=1 (azaz a 4. várost a 3, a 6 várost pedig a 2 követi ez e halmazba tartozó körutakban) és L9-hez tartozó alsó becslés: k9 = k8 + 0 = 63 + 0 = 63 amely egyben az optimális (legrövidebb) körút hossza. Lo ko=48 k1 58 L1 L2 14 14 k3 65 k2 49 L3 L4 21 21 66 k4 51 k5 73 k7 L5 L6 56 56 64 k6 56 L7 L8 35 35 k8 63 L9 43 62 k9 Az = 1 -es értéken rögzített döntési változók indexei: 14 21 56 35 43 62 az alábbi sorrendben alkotnak index lkáncot: 1 - 4 - 3 - 5 - 6 - 2 - 1 16 + 25 + 5 + 5+ 5 + 7 = a körút = 63 : a körút hossza 67 63