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

Alkalmazott Matematikai Lapok 6 (1980) 1—16 A BÁZISBÓL KILÉPŐ VEKTOR MEGHATÁROZÁSÁNAK EGY MÓDJA A SZIMPLEX MÓDSZER ELSŐ FÁZISÁBAN MAROS ISTVÁN Budapest A szimplex módszer első fázisa a lineáris programozási (LP) feladatok egy lehetséges (fizibilis) megoldásának megkeresésére szolgál, de használható lineáris feltétellel rendelkező egyéb feladatok esetén is hasonló célra, sőt ilyen feltételrendszerek konzisztenciájának a megállapítására is. LP fel­adatok esetén a klasszikus első fázisú eljárások az alábbi feltételek mellett működnek : (i) A bázisba belépő változó fizibilis értéket vesz fel. (ii) A bázisban levő fizibilis változók a transzformáció után is fizibilis értéken maradnak. (iii) A bázisból kilépő vektor fizibilis értéken hagyja el a bázist (alsó vagy felső korláton). Az (ii) feltétel feloldásával új lehetőségek kínálják magukat a szimplex módszer keretein belül. A cikk is egy ehhez kapcsolódó eljárást mutat be, amitől — pusztán a bázisból kilépő változó más­ként történő meghatározása által — hatékonyabb iterációs lépések várhatók az első fázisban, külö­nösen degenerált bázisok esetén. 1. Bevezetés A szimplex módszer első fázisa közismerten a lineáris programozási (LP) fel­adatok egy lehetséges (fizibilis) megoldásának a megkeresésére szolgál, sőt a lineáris feltételrendszerrel rendelkező egyéb feladatok esetén is használják fizibilis pontok előállítására, illetve a feltételrendszer konzisztens/inkonzisztens voltának a kimuta­tására. A lineáris programozásban az első fázist tulajdonképpen „szükséges rossz"-nak szokták tekinteni, hiszen ekkor az LP feladat eredeti célfüggvénye egyáltalán nem, vagy csak igen korlátozottan érvényesül. Ennek a résznek a lerövidítése tehát az LP problémák megoldásának hatékonysága szempontjából fontos (gyakorlati) feladat. Már DANTZIG is a szimplex módszert hívta segítségül fizibilis megoldás elő­állítására és azóta is ennek különféle variánsai használatosak. Az ilyen irányú fej­lesztések mind a bázisba belépő, mind pedig a bázist elhagyó változó meghatározásá­nak mikéntjére kiterjednek (bizonyos esetekben ezek egymással erősen összefügg­hetnek), hogy csak az algoritmus jellegű fejlesztéseket említsük, nem beszélve a sta­bilabb numerikus viselkedést célzó eljárások kidolgozásáról. A klasszikus első fázisú eljárások (pl. [1], [5]) általában az alábbi feltételek mellett működnek : (i) a bázisba belépő változó fizibilis értéket vesz fel ; (ii) a bázisban levő fizibilis változók a transzformáció után is fizibilis értéken maradnak; (iii) a bázisból kilépő vektor fizibilis értéken hagyja el a bázist (alsó vagy felső korláton). Ezekből rögtön következik, hogy ha induláskor a bázison kívüli változók fizibilis értéken vannak, akkor ez végig igaz lesz a mindenkori bázison kívüliekre. Alkalmazott Matematikai Lapok 6 (1980)

Next