Hatékony pivot algoritmusok hálózati- és többtermékes hálózati folyamfeladatokra
Témavezető:Illés Tibor, egyetemi docens
Hálózati- és többtermékes hálózati folyamfeladatok gyakorlati alkalmazása igen sokrétű. Az eszköz és személyzet hozzárendelési feladatoktól kezdve az ellátási láncoknál (supply chain) illetve a termeléstervezési feladatoknál, mint részfeladatok jelentkezhetnek hálózati folyamfeladatok. Ezeket a részfeladatokat célszerű hatékonyan megoldani és olyan keretalgoritmusokat kidolgozni, amelyek során a részfeladatok illetve a teljes feladat megoldását azonos (vagy nagyon hasonló) pivot algoritmusokkal oldjuk meg. Elméleti és gyakorlati szempontból az olyan pivot algoritmusok az érdekesek, amelyek egyszerűek és polinomiális futási idejűek. Goldfarb, Hao és mások az 1990-es évek elején a primál és duál szimplex módszer polinomiális változatait dolgozták ki maximális folyam minimális vágás feladatára illetve a minimális folyam problémára. Érdekes lenne olyam pivot algoritmusok (MBU szimplex algoritmus, criss-cross algoritmus) hálózati folyam feladatra alkalmazható változatait megvizsgálni, amelyekről eldöntendő, hogy lehetséges-e polinom futási idejű variánst készíteni vagy sem. A többtermékes hálózati folyamfeladatokról tudjuk, hogy az elvárt egészértékű megoldás előállítása NP-teljes feladat, hiszen erre a feladat osztályra már nem teljesül az, hogy bármelyik bázis megoldás egészértékű is egyben. Legjobb tudomásunk szerint viszont senki sem vizsgálta azt az érdekesnek tűnő kérdést, hogy többtermékes hálózati folyamfeladat lineáris programozási relaxáltja megoldható-e pivot algoritmussal polinom időben vagy sem. További érdekes elméleti és gyakorlati kérdéseket lehet megfogalmazni a hálózati folyamfeladatok témakörében. A téma iránt érdeklődő hallgatók számára a kutatásuk elkezdéséhez szakirodalmat és konzultációt biztosítunk.