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éma­típusok. A diszkrét programozási feladatok megoldására az utóbbi időben igen sok mód­szer született. Ezek két fő csoportba sorolhatók. Az egyik a megfelelő folytonos feladat megoldása után pótlólagos feltételek­kel 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ódszerek­nek. 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 dol­gozat utolsó részében szereplő példán keresztül bemutatjuk azt is, hogy optima­lizá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ód­szerrel oldottak meg [10]. 3 Matematikai Lapok 33

Next