---

Tartalom

Előszó

1. DETERMINISZTIKUS IDŐTERVEZÉSI FELADAT (CPM)
1.1. Gráfelméleti bevezetés
1.2. A legrövidebb út probléma
1.3. Az időtervezési feladat

2. SZTOCHASZTIKUS IDŐTERVEZÉSI FELADAT (PERT)
2.1. A PERT modell
2.2. A többdimenziós normális eloszlás
2.3. A centrális határeloszlás tétel alkalmazása
2.4. Sztochasztikus programozási megközelítés

---

Előszó

Ez a jegyzet a hálózati optimalizálás gyakorlati alkalmazások szempontjából egyik legfontosabb problémájával, az időtervezési, vagy más szóval tervütemezési feladattal foglalkozik. Célunk az, hogy a sztochasztikus időtervezési feladat néhány legújabb elemzési módszerét ismertessük. Ehhez az első fejezetben megadjuk a gráfelmélet néhány alapfogalmát és algoritmusát. Ezután ismertetjük a determinisztikus időtervezési feladatot (CPM), majd áttekintjük az annak megoldására szolgáló legfontosabb hálózati optimalizálási algoritmusokat. Ezt a fejezetet Klafszky Emilnek a mgyar nyelvű szakirodalomban klasszikusnak tekinthető "Bolyai jegyzete", illetve a későbbiek során Klafszky Emil miskolci egyetemi előadásai alapján tanítványai által lejegyzett előadásai angol nyelven megjelent jegyzete alapján tárgyaljuk. Ezekben a jegyzetekben a legrövidebb útkereső algoritmus és a tervütemezési feladat legkorábbi, illetve legkésőbbi kezdési időpontokat meghatározó algoritmusai egységes keretben, a feladatra kimondott primál-duál feladatpár dualitás tételére alapozva vannak kidolgozva. A legrövidebb út keresésére megadjuk Ford egy algoritmusát is, leginkább csak azért, hogy példát mutassunk olyan algoritmusra is, amely hurokmentes hálózatban negatív élhosszak mellett is működik. Nem célja a jegyzetnek az e célra rendelkezésre álló sok kiváló és hatékony algoritmus ismertetése.

A második fejezetben először röviden ismertetjük a sztochasztikus időtervezési feladatot (PERT), majd megmutatjuk, hogy Prékopa András és J. Long nem túl nagyméretű PERT modellekre milyen módszert dolgoztak ki arra, hogy a projekt véletlen nagyságú megvalósítási idejének a valószínűségi eloszlásfüggvényére alsó és felső korlátokat tudjanak számítani, illetve nagy megbízhatósággal becsülni tudják annak az értékeit. Ennek a módszernek a továbbfejlesztéseként Prékopa András, Szántai Tamás és J. Long dolgozata alapján megmutatjuk, hogy ezek a módszerek hatékonyabbá tehetők, és ezáltal a gyakorlati alkalmazások számára reális méretű PERT modellek esetén is sikerrel alkalmazhatókká válnak. Numerikus tesztfeladatokon mutatjuk be az új módszerek alkalmazhatóságát. Végül az utolsó szakaszban egy együttes valószínűséggel korlátozott sztochasztikus programozási modellt mutatunk be, amely a PERT modellek elemzésére egy egészen más megközelítést alkalmaz. Ez a megközelítés a tevékenységi idők valószínűségi modellezésére a Dirichlet eloszlás alkalmazását is lehetővé teszi. Tekintettel arra, hogy a PERT modellekben általánosnak tekinthető a béta eloszlás ilyen célú alkalmazása és a Dirichlet eloszlás egydimenziós peremeloszlásai közismerten béta eloszlások, ez az új modellezés az eddigi modellezési módszerek fontos általánosításának tekinthető. A Dirichlet eloszlás ilyen célú alkalmazását a jegyzet szerzője egy 1992 márciusában a Berlin közeli Gosen-ben tartott nemzetközi konferencián ismertette először D. Monhorral közös előadás keretében. A valószínűséggel korlátozott sztochasztikus programozási feladat megoldását Dirichlet eloszlás esetén is lehetővé tevő számítógépes program kifejlesztéséről a jegyzet szerzője 1996-ban Prágában számolt be, mely konferencia kötetében ezek az eredmények írásban is megjelentek.

---