Kritikus út keresése lineáris programozási eszközökkel

Absztrakt (kivonat)

Az operációkutatás a matematika egy viszonylag fiatal, a huszadik század hirtelen kitáguló követelményrendszere által generált ága, amely napjainkban is igen dinamikusan fejlődik. E tudományon belül az egyes problémákhoz tartozó duálisok igen fontos szerephez jutnak, hiszen segítségükkel bizonyos feladattípusok megoldása vagy értelmezhetősége jelentős mértékben leegyszerűsíthető (például Ford és Fulkerson maximális folyam - minimális vágás tétele). A fentiekben kifejtett rendkívüli potenciális előnyök ellenére számos olyan operációkutatási probléma létezik, amelynek egyelőre igen keveset vagy éppen egyáltalán nem foglalkoztak a duálisával, illetve annak gyakorlati interpretációjával. Ezek közé tartoznak az általunk vizsgált tevékenységütemezési feladatok is, valamint az azok megoldására alkalmazott kritikus út keresési eljárás (CPM - critical path method), amellyel kapcsolatban meglepően kevés írás készült eddig, s ez különösen furcsának mondható annak tudatában, hogy egy széles körben elterjedt metódusról van szó, amit már 50-es évekbeli kidolgozása óta rendszeresen használnak a gazdasági élet berkein belül. Ezzel pedig elérkeztünk a dolgozat fő témájához, ami lényegében három részből áll. A kritikus út keresési algoritmussal történő megoldás rövid ismertetése után a feladattípus primál és duál LP-felírását vizsgáljuk majd. A különböző megközelítések tüzetes áttekintése során általánosan igazoljuk a lehetséges, valamint optimális megoldások halmazára vonatkozó állításainkat, s azokat egy-egy példa segítségével is szemléltetjük. Mindemellett igyekszünk rávilágítani ezen eltérő megoldási módszerek közötti összefüggésekre, amelyeket gyakran felhasználunk majd megállapításaink bizonyításához.