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 bemutatunk ö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áltozó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 egységesen í/j-vel jelöljük. n (2.1) yf+ 2 auxi = bili = 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)