Lineáris egyenletrendszerek megoldása szimplex módszerrel = Solution of a System of Linear Equations with the Simplex Method

Krekó, Béla (1959) Lineáris egyenletrendszerek megoldása szimplex módszerrel = Solution of a System of Linear Equations with the Simplex Method. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 4 (3-4). pp. 265-275.

Preview

Text cut_MATKUTINT_4_3_-_4_1959_pp265_-_275.pdf Download (4MB) | Preview

Abstract

A gazdasági életben felmerülő matematikai problémák megoldása számos esetben a lineáris programozás néven ismert módszerre vezethető vissza [1]. A lineáris programozásnál egy olyan elsőfokú függvény extremális értékének meghatározásáról van szó, amelynek értelmezési tartományát egy — az adott gazdasági feltételeket reprezentáló — lineáris egyenlőtlenségrendszer szabja meg. Ennek következtében a kérdéses értelmezési tartomány olyan konvex halmazt alkot, amelynek véges számú csúcspontja van. Ha a vizsgálandó függvénynek van extremális értéke, azt e csúcspontok valamelyikében feltétlenül felveszi. A megoldásra szolgáló módszerek közül legelterjedtebb a G. B. Dantzigtól származó szimplex módszer [2]. A szimplex módszernek az az alapgondolata, hogy az értelmezési tartomány egyik csúcspontjából kiindulva úgy haladjunk csúcspontról csúcspontra, hogy közben a függvény helyettesítési értékei monoton sorozatot alkossanak. S mivel a csúcspontok száma véges, a kérdéses extrómum — amennyiben létezik — véges számú lépésben meghatározható. A szimplex módszer elemzése közben kiderült, hogy annak alapvető mozzanata az az eljárás, amelyet a továbbiakban elemi transzformációnak fogunk nevezni. Ez olyan speciális lineáris transzformációt jelent, amelynek révén egy adott bázisból olyan új bázisba térünk át, amely csupán egyik vektorában különbözik az eredetitől. S mivel bármely lineáris transzformáció elemi transzformációk sorozatára bontható fel, érthető, hogy ezen az úton lehetőség nyílik számos lineáris algebrai probléma egyszerű — determinánsmentes — tárgyalására. Ebben a dolgozatban csupán a lineáris egyenletrendszerek megoldásával kívánunk foglalkozni. A bemutatandó eljárással kapcsolatban, amelyet az előzőek alapján ugyancsak szimplex módszernek fogunk nevezni, előrebocsátjuk a következőket: a) Közvetlenül alkalmazható bármilyen végesdimenziójú lineáris egyenletrendszer megoldására. (Az inhomogén rendszereket nem kell előbb átalakítani homogén rendszerekké.) b) A kompatibilitás és a rang kérdésének eldöntésével egyidejűleg explicit formában kapjuk meg a megoldást is. Nincs tehát szükség további rekurzív számítások elvégzésére, mint a diadikus felbontáson alapuló egyéb módszereknél. c) Az alkalmazandó numerikus számítások mennyisége azonos nagyságrendű, mint a mátrix-számításon alapuló egyéb módszereknél. A továbbiakban először az elemi transzformációval foglalkozunk, majd megmutatjuk, hogyan lehet felhasználni az elemi transzformációkat valamely adott A matrix egy speciális bázisfelbontására. Ez a felbontás teszi lehetővé a lineáris egyenletrendszerek megoldásának egyszerű tárgyalását. Ehhez kapcsolódik a mátrixok inverziója, amely lényegében több olyan egyenletrendszer szimultán megoldását jelenti, amelyek azonos együtthatómátrixszal bírnak. A módszer hatékonyságát néhány numerikus példa bemutatásával kívánjuk illusztrálni.

Actions (login required)

Edit Item