Matematikai Lapok, 1968 (19. évfolyam, 1-4. szám)
1968-11-01 / 1-2. szám
LESZÁMLÁLÁSI STRUKTÚRÁK ÉS ALKALMAZÁSUK DISZKRÉT PROGRAMOZÁSI FELADATOK MEGOLDÁSÁRA KOVÁCS LÁSZLÓ BÉLA 1. A diszkrét programozási feladatok általános alakja. 2. Az egész értékű programozási feladatok alkalmazásai. 3. A feladat megfogalmazása, valamint néhány algebrai alapfogalom és lemma. 4. Leszámlálási struktúrák 5. Egy alapvető jelentőségű leszámlálási struktúra 6. Egy feladat megoldása leszámlálási struktúra segítségével. Az utóbbi időben egyre nagyobb jelentőséget kap a matematikai programozás egy fiatal ága, a diszkrét programozás. Az igény, ilyen feladatok megoldására már korábban is megvolt, erről tanúskodnak a 2. pontban felsorolt problématípusok. A diszkrét programozási feladatok megoldására az utóbbi időben igen sok módszer született. Ezek két fő csoportba sorolhatók. Az egyik a megfelelő folytonos feladat megoldása után pótlólagos feltételekkel levágja a folytonos optimumot anélkül azonban, hogy a megengedett egészértékű megoldások közül kizárna. Ilyen például R. E. Gomory [1], [2] módszere. A másik megoldási módszer csoportot nevezhetjük kombinatorikus módszereknek. Ezek közül is talán a leglényegesebbek az ún. leszámlálási algoritmusok. Ezek lényege az, hogy az összes megoldásokat egy képzeletbeli sorrendbe állítjuk, és ezek között igen nagy lépésekkel haladunk előre. A módszer jelentőségét az adja meg, hogy általános típusú feladatok megoldására is felhasználható, továbbá más módszerekkel együttesen alkalmazható. Jelen dolgozat célja, hogy a leszámlálási algoritmusoknak a vázát adja, azaz a 0—1 komponensű, a dimenziós vektorok egy valamilyen feltételek által nyert S részhalmazának pontjait előállítsa. Alapul egy kombinatorikus módszer, az ún. „back-track” (~ visszafelé nyomon követés) eljárás szolgált, amely megtalálható például R. J. Walker [17] munkájában. A dolgozat utolsó részében szereplő példán keresztül bemutatjuk azt is, hogy optimalizálási feladatok esetén hogyan egyszerűsödnek a számítások. „Tiszta” leszámlálási algoritmusra példa Lawler és Bell [3] dolgozata, de sok más módszer tartalmazza segédeszközként a leszámlálás valamilyen formáját, például F. Glover [4] és E. Balas [5], [6]. A kombinatorikus típusú algoritmusokhoz tartozik az ún. korlátozás és csoportosítás módszere is, melynek igen sok alkalmazása van. Példaként említjük J. D. C. Little és mások [7] módszerét az utazó ügynök probléma megoldására, valamint A. H. Land és A. Deig [8] algoritmusát a vegyes egész értékű feladatokra. (Folytonos és egész változók egyaránt vannak a feladatban.) Végül megemlítjük még a — R. Bellman által kidolgozott — dinamikus programozás alkalmazását egész értékű feladatokra, amely vázlatosan megtalálható például G. Hadley [9] könyvében, valamint egy többtermékes terhelési problémát, amelyet ezzel a módszerrel oldottak meg [10]. 3 Matematikai Lapok 33