ALKALMAZOTT MATEMATIKAI LAPOK 6. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1980)

1980 / 1-2. sz. - Maros István: A bázisból kilépő vektor meghatározásának egy módja a szimplex módszer első fázisában

MAROS I. Az (i)—(iii) feltételek még nem határozzák meg egyértelműen egy adott belépő vektor esetén a kilépő vektort. Ezt a lehetőséget kihasználva különféle eljárások készültek, melyek mind azt célozták, hogy az első fázis minél hamarabb befejeződjék. Az (ii) feltétel feloldásával új lehetőségek kínálják magukat, amelyektől — pusztán a kilépő vektor másként történő meghatározása által — még hatékonyabb iterációs lépések várhatók. Ezzel kapcsolatos ötletet említett TOMLIN is a Budapesten 1976-ban tartott IX. Matematikai Programozási Szimpozionon. A továbbiakban egy ilyen elgondolásnak a kidolgozásáról lesz szó, de utalás történik arra is, hogyan tudja szolgálni a degenerációs ciklizálás elkerülését és a nagyobb numerikus stabilitást az eljárás. Kimutatjuk, hogy tulajdonképpen az (i)—(iii) feltételek által meghatározott keretek általánosításáról van szó. Végül beszámolunk számítástechnikai tapasztalatokról, melyben egyúttal bemuta­tunk összehasonlító vizsgálati eredményeket egy, az (i)—(iii) feltételeket teljesítő, elég alaposan kidolgozott eljárással szemben. 2. A megoldandó LP feladat A következőkben az alábbi LP feladatról lesz szó, és az egyes változók az alábbi csoportok valamelyikébe esnek: A (2.1) alatti feltételrendszer bármelyik sorát lehet célfüggvénynek tekinteni. Az egyöntetűbb tárgyalás kedvéért feltesszük, hogy a célfüggvényhez tartozó új vál­tozót maximalizáljuk. Belátható (pl. [4]), hogy a (gyakorlatban felmerülő) legáltalánosabb alakú LP feladatok a fenti alakra hozhatók egyszerű transzformációk segítségével. Számító­gépes megoldás esetén ezek a transzformációk az input során könnyen elvégezhetők, ugyanakkor az implementált LP optimalizáló algoritmusok döntő többsége a (2.1)— (2.2)-vel felírt alakot használja csakúgy, mint a tárgyalásban később ismertetendő LIPROS LP programcsomag is. A (2.1)-ben szereplő Xj változókat strukturális változóknak, míg az yrket logikai változóknak nevezzük. A továbbiakban feltesszük, hogy a logikai változókat 1-től m-ig, a strukturálisakat m + 1-től m+n-ig számozzuk és a felső korlátokat egy­ségesen í/j-vel jelöljük. n (2.1) yf+ 2 auxi = bil­i = l,­..m j=1 (2.2) Típus Fizibilis értéktartomány Megjegyzés 0­­,=­ Xj=0 1 O^y^V, O^xj^uj Vi, Uj veges 2 O^XjiS + 3 — oogj/jg -f- °° — = Xj- = + oo Alkalmazott Matematikai Lapok­­ (1980)

Next