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

1987-88 / 1-2. sz. - Klafszky Emil és Terlaky Tamás: A Bland szabály a prímál és a duál szimplex módszer esetén

1 Alkalmazott Matematikai Lapok 13 (1987—88) 1—7 A BLAND SZABÁLY A PRIMÁL ÉS A DUÁL SZIMPLEX MÓDSZER ESETÉN KLAFSZKY EMIL—TERLAKY TAMÁS Budapest Cikkünkben megmutatjuk, hogy a BLAND által [1]-ben megfogalmazott pivotálási szabály nem csak a primál, hanem a duál szimplex módszer esetén is biztosítja az algoritmus végességét. A teljességre törekvés, valamint az analógia megmutatása céljából megismételjük a primál szimplex módszerre adott BLAND bizonyítást is. 1. Bevezetés R. G. BLAND [1] cikkében új pivotálási szabályt fogalmazott meg a szimplex módszerhez, amely alkalmazásával bizonyítani lehet a szimplex algoritmus végessé­gét. Dolgozatunkban a továbbiakban az alábbi lineáris programozási feladattal foglalkozunk : min cx (1.1) Ax = b xs. Ahol X, c£Rn, b£Rm és A: mXn teljes sorrangú mátrix. A továbbiakban a mátrixokat nagy, a vektorokat kis latin betűkkel jelöljük, a vektorok komponenseit pedig görög betűkkel, így pl. x—(Ok­ ..., Ç„) és ι„ а szimplex tábla r-edik sorának ”-edik eleme. Feltételezzük, hogy az olvasó ismeri a primál és a duál szimplex módszert, de az egységes és teljes tárgyalásmód érdekében a primál és duál szimplex módszer legfontosabb tulajdonságait a következő fejezetben röviden összefoglaljuk. 2. A primál és a duál szimplex módszer alaptulajdonságai a) A primál szimplex módszer A szimplex tábla adatait az alábbi ábra szemlélteti : 1. ábra Alkalmazott Matematikai Lapok 13 (1987—88)

Next