KURZUS: Informatikai rendszerek alapjai

MODUL: Matematikai számítások Excellel

2. lecke: Lineáris egyenletrendszerek

Cél: Bár a lineáris egyenletrendszerek témaköre elméleti, "száraz" matematikának tűnhet, megfelelő elemzés után rájöhetünk, hogy nagyon sok gyakorlati feladat (keverési, szállítási típusok) megoldása is ezen a modellen alapul. Mondhatjuk tehát, hogy az ipari-gazdasági életben is gyakori problématípusról van szó.

A megoldásra többféle módszert is választhatunk: a kézi, papíros "rabszolgamunkától" kezdve a hatékony és gyors számítógépes megvalósításig. Már egy-két rendszer megoldása alapján is nyilvánvaló, hogy a triviális esetek kivételével célszerűbb az utóbbit választani, bonyolultabb esetekben pedig egyszerűen nincs is más lehetőség.

Az Excel nagyon hatékony támogatást nyújt ilyen feladatok kezelésére (a már megtanult mátrix- és blokkfüggvényekkel). A lecke elsajátítása után - a probléma megfelelő elemzése és értelmezése után - Ön is képes lesz a saját munkájában a módszerek gyors és ügyes alkalmazására. További "jó hír", hogy a megoldás ötlete eszközfüggetlen: a MATLAB részben is ugyanígy fogunk eljárni (természetesen a MATLAB megfelelő eszközeinek alkalmazásával).

Követelmények: Ön akkor sajátította el megfelelően a tananyagot, ha (az Excel segítségével)

  • el tudja dönteni, hogy egy négyzetes lineáris egyenletrendszer megoldása egyértelmű-e;
  • be tudja kapcsolni önállóan a Solver bővítményt;
  • a leckében szereplő feladattípusokra be tudja állítani a Solver ablakában a megfelelő paramétereket;
  • képes az inverz mátrixos módszerrel és a Solverrel is az egyértelmű eset megoldására;

Időszükséglet: A tananyag elsajátításához (a feladatok megoldásával együtt) hozzávetőlegesen 3 órára lesz szüksége.

Kulcsfogalmak

  • Lineáris egyenletrendszer, együtthatómátrix és determinánsa.
  • Pszeudoinverz (számon nem kérendő fogalom).
  • Célérték, változó cella/cellák, korlátozó feltétel(ek).
Lineáris egyenletrendszerek megoldása Excel segítségével
Lineáris egyenletrendszer megoldása inverz mátrix segítségével

Az n-ismeretlenes lineáris egyenletrendszer általános alakja a következő:

a 11 x 1 + a 12 x 2 +...+ a 1n x n = b 1

a 21 x 1 + a 22 x 2 +...+ a 2n x n = b 2

...

a m1 x 1 + a m2 x 2 +...+ a mn x n = b m

Speciálisan, ha m=n , akkor az egyenletrendszer négyzetes.

A legegyszerűbb esetben a négyzetes rendszer megoldása egyértelmű. Ekkor az a ij együtthatókból képzett mátrix ( A ¯ ¯ mátrix) oszlop-, illetve sorvektorai lineárisan független rendszert alkotnak.

A függetlenség mérése a determináns vagy a rang segítségével történhet.

Egy n×n -es mátrix determinánsa egy speciális n-dimenziós térfogatként tekinthető. Független rendszer determinánsa nem nulla, összefüggő esetben pedig nulla értéket kapunk. (Ilyenkor a rendszer legfeljebb n1 -dimenziós).

A rang egy mátrix lineárisan független oszlop- vagy sorvektorainak maximális száma. Ha a mátrix nem négyzetes, akkor a rang legfeljebb a kisebb méret lehet. Négyzetes n×n -es mátrix esetén a rang maximum n, ha az egyenlőség teljesül, akkor a rendszer független.

Excelben a rang beépített függvénnyel direkt módon nem határozható meg, itt csak a determinánssal dolgozhatunk.

Egyértelmű négyzetes lineáris egyenletrendszerek megoldására szolgáló klasszikus papír-ceruza módszer a Cramer-szabály alkalmazása. Ilyenkor determinánsokkal számolunk, a következők szerint. Legyen A i ¯ ¯ az a mátrix, amelyet úgy kapunk, hogy A ¯ ¯ -ban az i-edik oszlop helyére a b ¯ oszlopvektort írjuk. Ekkor x 1 ¯ =det A 1 ¯ ¯ /det A ¯ ¯ , x 2 ¯ =det A 2 ¯ ¯ /det A ¯ ¯ , ..., x n ¯ =det A n ¯ ¯ /det A ¯ ¯ . A módszer kisebb egyenletrendszerekre jól használható, de nagyobb n-ek esetén a sok determinánsszámítás reménytelenül lelassítja.

Próbálja ki a lineáris egyenletrendszer papír-ceruza megoldását egy 2×2-es és egy 3×3-as példán.

Az egyszerű számítógépes megoldásnál (egyértelmű eset) azt használhatjuk ki, hogy az A ¯ ¯ mátrix pontosan akkor invertálható, ha a determinánsa nem nulla. A kezdetben A ¯ ¯ x ¯ = b ¯ alakban adott egyenletrendszer egyértelmű megoldása tehát az x ¯ = A ¯ ¯ 1 b ¯ képlet segítségével kiszámolható.

Ez a feladat Excelben a beépített blokkfüggvények segítségével gyorsan megoldható.

Tekintsük a következő lineáris egyenletrendszert:

6 x 1 6 x 2 2 x 3 +5 x 4 =20 x 1 +8 x 2 +5 x 3 +5 x 4 =15 2 x 1 9 x 2 9 x 3 3 x 4 =22 4 x 1 2 x 2 +3 x 3 +10 x 4 =10

A megoldás és ellenőrzés lépéseit a következő ábra illusztrálja.

(Ellenőrizzük a determináns értékét, kiszámoljuk az inverz mátrixot, meghatározzuk a megoldást, visszaszorzással ellenőrizzük, eltérési hibavektort számolunk.)

Lineáris egyenletrendszer megoldása inverz mátrix segítségével
1. ábra

Ha az A és b blokkokat megfelelően nevesítettük, akkor az x megoldásvektor értéke az {=Mszorzat(Inverz.Mátrix(A); b)} blokkművelettel számítható.

Itt nem érdemes az inverz mátrixot törtalakban megjeleníteni, mert a determináns már négyjegyű szám, és ilyenkor a megjelenített törtalakok a törtek szintjén kerekített, közelítő értékek lesznek.

A következő táblázat egy A ¯ ¯ x ¯ = b ¯ alakú lineáris egyenletrendszer együtthatóit és oszlopvektorát tartalmazza.

Ellenőrizze, hogy a rendszer megoldása egyértelmű, majd állítsa elő a megoldást!

Lineáris egyenletrendszer együtthatói:

3-154 35
510-12 -7
2-246 32
-1028 13

Végezze el a kapott megoldás segítségével az A ¯ ¯ x ¯ b ¯ =0 ellenőrzést is!

Lineáris egyenletrendszerek megoldása Solverrel
A Solver bővítmény

A Solver eszköz az Excel egyik legfontosabb bővítménye és része.

Ha a mi Excelünkben eddig még nem használtuk, akkor először aktiválni kell. Egy bővítményt (Solver, Analysis ToolPak stb.) aktiválni a Fájl/Beállítások/Bővítmények ugrás paranccsal lehet. Az aktivált bővítmény az Adatok menüszalagon lesz látható (a 2003-as Excelben az Eszközök főmenü alatt találjuk).

Jegyezze meg a Solver bővítmény bekapcsolásához szükséges lépéseket!

Mi a 2010-es Excel Solver bővítményének használatát ismertetjük, de bármelyik Solver verzió használata hasonló.

Megjegyezzük továbbá, hogy a jegyzet keretein belül a Solver matematikai és algoritmikus hátterével (hogyan dolgozik a Solver) csak a feltétlenül szükséges mértékben foglalkozunk. A részletek iránt mélyebben érdeklődőknek a http://www.solver.com weboldal meglátogatását ajánljuk.

Lineáris egyenletrendszer megoldása (egyértelmű eset)

Bár az inverz mátrix felhasználásával egy lineáris egyenletrendszer az egyértelmű esetben egyszerűen megoldható, a továbbiak szempontjából hasznos, ha a Solver segítségével történő megoldást is megismerjük.

Ugyanazt az egyenletrendszert fogjuk megoldani, amit korábban az inverz mátrix segítségével oldottunk meg.

A tényleges megoldás előtt bemutatjuk a Solver fontosabb megadandó paramétereit. A most következő leírás a későbbi leckék feldolgozása során is használható referenciaként (v. ö.: 3. lecke, termelési és optimalizálási feladatok).

A Célérték egy (!) olyan cella, amelyik a Változó cellák tartalmára közvetlenül vagy közvetve hivatkozik és a célfüggvényt előállító képletet tartalmaz. A Változó cellák (döntési változók cellái, módosuló cellák) nem tartalmazhatnak hivatkozást, csak konkrét értékeket. Ezen cellacsoport (egy darab cella is lehet) tartalma a célfüggvény értékét befolyásolja. A Solver a célcella értékét a kért Cél (Min, Max, megadott Érték) szerint próbálja a változó cellák tartalmának módosítása révén beállítani.

A feladat a megoldás körülményeire vonatkozó korlátozásokat is tartalmazhat (korlátozó feltételek), amelyeket a Hozzáadás nyomógomb megnyomása után adhatunk meg. A korlátozások gyakran olyan egyenlőtlenségek, amelyek egyik oldala konstans adat, de pl. előírhatjuk azt is, hogy a módosuló cellák csak bináris értékeket vehessenek fel. A korlátozó feltételekben (egyenlőtlenségekben) szereplő konstans adatok az ún. korlátozáscellákban helyezkednek el.

Jegyezze meg, hogy mit jelentenek a következő fogalmak: célérték, változó cella/cellák, korlátozó feltétel(ek).

A "Nem korlátozott változók nem negatívvá tétele" jelölőnégyzetet csak akkor célszerű bejelölni, ha a változó cella értéke a feladat jellege miatt nem lehet negatív. Például egy termelési feladatnál a gyártandó termékmennyiségek értelemszerűen nem lehetnek negatívok. Mi azonban az Informatika tananyagban úgy dolgozunk, hogy az ilyen jellegű beállításokat korlátozásokkal adjuk meg, tehát ezt a kapcsolót nem használjuk.

A Solver pontosságának beállítása
2. ábra

A megoldási módszerek közül a Szimplex LP lineáris feladatokhoz alkalmazható, a Nemlineáris ÁRG pedig általános eszközként a legtöbb problémához használható. Az ÁRG rövidítésben szereplő gradiens kifejezés elárulja, hogy ez a megoldó az érintőmódszer (változatainak) felhasználásával dolgozik, ezért a siker nem garantálható olyan függvényeknél, amelyeknek a meredeksége rövid szakaszon igen gyorsan változik (pl. "fűszálszerű kiugrások"). Ilyen, ún. nem sima problémák esetén az Evolutív módszer használható, amely genetikus algoritmus segítségével keres megoldást. (Nem sima problémákkal mi az Informatika tananyagunkban nem foglalkozunk).

A Beállítások nyomógombbal olyan párbeszédablakba lépünk (előző ábra), amelyen a megoldó algoritmusok működését szabályozhatjuk. Itt most csak a "Korlátozó feltétel pontossága" cellára hívjuk fel a figyelmet. Célszerűen érdemes a pontossági értéket kicsire választani. Mostani feladatunkban ezt 1E-15-re fogjuk átállítani.

Fontos: a mi feladatainknál az 1E-10 és 1E-15 közötti pontosságértékek a megfelelők.

Megjegyezzük még, hogy szintén a Beállítások párbeszédablakban szabályozható (szükség esetén, időigényes iteratív módszereknél) a közelítésre szánt maximális idő és lépésszám.

A Solver paraméterezése lineáris egyenletrendszer megoldásakor
3. ábra

Egyértelmű lineáris egyenletrendszer Solveres megoldásakor nem kell célcellát és célt választani! Elegendő az egyenletrendszer teljesülését a korlátozó feltételek között megkövetelni (előző ábra).

A Változó cellákra nevesítve is hivatkozhatunk, és nevesített blokkokat is megadhatunk a korlátozó feltételek között.

A változó cellák értékeit valamilyen (nem teljesen lehetetlen) kezdőértékekre állítjuk. Ez most a keresett x ¯ vektor kezdeti koordinátáit jelenti, amelyeket mind 1-nek választunk. Azt kell tudnunk, hogy több megoldással rendelkező feladatnál azt a megoldást fogja a Solver megtalálni, amelynek közeléből indultunk.

A Solver eredményének elfogadása
4. ábra

Látható, hogy amíg a direkt megoldásban az x 4 =0 helyett a gépi epszilon környéki érték jelentkezett, addig a Solveres megoldás a teljesen pontos értékeket szolgáltatta.

Segítség: Vegyen fel az A ¯ ¯ mátrix és a b ¯ vektor mellé egy alkalmas kezdő x ¯ vektort, paraméterezze fel a Solvert a megfelelő módon stb.

Oldja meg a fenti táblázattal adott lineáris egyenletrendszert a Solver segítségével a most megismert módon!

Önellenőrző kérdések

1. Oldja meg az alábbi A ¯ ¯ x ¯ = b ¯ alakú egyenletrendszert a következő feladatok alapján!

2 x 2 + x 3 +5 x 4 =21
5 x 1 +5 x 2 +3 x 3 + x 4 =50
x 1 +2 x 2 +5 x 3 =19
x 1 x 2 2 x 3 x 4 =13

Vegye fel az A ¯ ¯ mátrixot és a b ¯ vektort egy új munkalapra, majd nevezze el a blokkokat "A"-nak és "b"-nek!

Hány megoldása van az egyenletrendszernek?

Megoldások száma:

A változócellák kezdeti értéke 1, a Solver számítási pontossága 1E-10 legyen, megoldási módszerként pedig a Nemlineáris ÁRG-t használja!
Oldja meg az egyenletrendszert! Mennyi az x 2 értéke?

x 2 :

Végezze el az A ¯ ¯ x ¯ b ¯ =0 ellenőrzést!