A GAZDASÁGI ALLOKÁCIÓ MATEMATIKAI MODELLJEI

A GAZDASÁGI ALLOKÁCIÓ MATEMATIKAI MODELLJEI (előadások)

Dr. Nagy András főiskolai tanár

Budapest 1996 Pénzügyi és Számviteli Főiskola

Lektorálta: Dr. Csernyák László egyetemi tanár

2

TEMATIKA 1. téma

Történeti áttekintés Az allokáció problémái a közgazdaságtan fejlődéstörténetében. F. Quesnay újratermelési modellje (Quesnay doktor cikk-cakkjai). K. Marx újratermelési modellje (két és három szektoros változatok). L. Walras általános egyensúlyi modellje. L.V. Kantorovics, G.B. Dantzig - a lineáris programozás. W. Leontief input-output modellje. J.R. Hicks, K.J. Arrow, G. Debreu - a modern általános egyensúlyelmélet.

2. téma

Közgazdaságtan és operáció kutatás Néhány felidézendő alapfogalom. A közgazdasági irodalomban használt jelölések. Optimalitás, különböző optimalitási elvek. K.J. Arrow „lehetetlenségi tétele“.

3. téma

Egyszerű allokációs modellek Egyszerű, a gyakorlatban előforduló problémák megfogalmazása, megoldása. Lineáris programozás, dualitás, árnyékárak. L.V. Kantorovics gépterhelési feladata - egy megoldó algoritmussal. A hozzárendelési feladat - a „magyar módszer“.

4. téma

Allokációs modellek különleges terekben

A gyakorlatban fellépő bonyolultabb szituációkat több komponensű célfüggvénnyel, változókkal lehet modellezni. Nem hagyományos allokációs problémák (többcélfüggvényes, paraméteres stb. LP) A részben rendezett vektorterekről Lineáris programozás részben rendezett vektorterekben 5. téma

Az ágazati kapcsolatok mérlege

Az allokációs probléma egy igen általános megfogalmazása az input-output modell, amelyet neveznek sakktábla modellnek is. Legismertebb alkalmazása az ágazati kapcsolatok mérlege (ÁKM), amely összeköti a mikroökonómiai vizsgálatokat a makroszintű elemzésekkel. Az ÁKM fogalma, felépítése. Az ÁKM matematikája. Az ÁKM és a dualitás problémája. Árak, árjelzések az ÁKM-ben. Gazdasági számítások az ÁKM segítségével. Szimulációk, teljes tartalom számítások. Allokációs problémák megoldása az ÁKM (input-output elemzés) segítségével. Nem lineáris input-output modellek. Input-output elemzés részben rendezett vektorterekben.

BEVEZETÉS Az alábbiakban egy, a magyar gazdasági főiskolákon eddig még önálló tantárgyként nem tanított diszciplína anyagát próbáljuk meg összefoglalni néhány előadásban. Az írott előadás kissé különös műfaját azért választottuk, mivel a nehezen összefogható téma ismertetéséhez a kifejtésnek ez a módja adja meg a kívánatos szabadságot. Egy szabatos tankönyv megírásához még nem áll rendelkezésre elegendő oktatói tapasztalat. A diszciplína tárgya: a gazdasági allokáció. Bizonyos szempontból ez természetesen az egész közgazdaságtant jelenti (lásd például a T.C.Koopmans szerkesztette alapvető jelentőségű kötetet: „Activity Analysis of Production and Allocation“ New York 1951.), hiszen a közgazdaságtan - egyik klasszikus megközelítése szerint - nem más, mint a szűkösen rendelkezésre álló erőforrások racionális és hatékony szétosztása - allokálása - a különböző szükségletek között. Nyilván ebben a néhány előadásban mi nem kívánhatjuk, nem is kívánjuk ezt a teljességet felölelni. Témánkat erősen szűkíteni kellett. Az allokáció fogalmát ezért könyvünk szűkebb kereteihez igazítva elsősorban azokra a kérdésekre korlátozzuk, ahol az erőforrások a maguk fizikai valójában végeznek mozgásokat. A másik fontos szempont, hogy azokat az allokációs problémákat vizsgáljuk meg, ahol a matematika alkalmazása nem csupán az elméleti megfontolások szabatos modellezését szolgálják, hanem lehetőség szerint valóságos problémák számszerű megoldását is jelentik. Témánk tehát legkevesebb három tudományág találkozási pontját jelentik: •

az elméleti kérdéseket elemző közgazdaságtan (mikro- és makroökonómia);

•

a matematikai modellek felépítésével foglalkozó operációkutatás.

•

az elméleti modelleket valóságos adatokkal verifikáló ökonometria;

Ennek megfelelően az előadások feltételezik az elméleti közgazdaságtan és az operációkutatás ismeretét, azon a szinten, amelyen ezek a tárgyak a gazdasági főiskolák tantervében szerepelnek. Ugyanakkor a kifejtés kereksége érdekében néha ismétlésekbe is kell e tárgyakhoz képest bocsátkoznunk. Ilyen esetekben igyekszünk újszerű megközelítéssel vagy más módon többletet adni. Budapest, 1996. november Dr. Nagy András

2

TÖRTÉNETI ÁTTEKINTÉS (ELSŐ ELŐADÁS)

F. Quesnay Gazdasági Táblázatok

K. Marx

L. Walras

Újratermelési sémák

Általános egyensúly

L. Kantorovics, G.B. Dantzig

V. Leontyev

Lineáris programozás

Input-Output Elemzés

R. Hicks, K.J. Arrow, G. Debreu Általános egyensúly elmélet

Ágazati Kapcsolatok Modelljei

1. ábra A gazdasági allokációs modellek történelmi „családfája“

1. QUESNAY DOKTOR „CIKK-CAKKJAI“ - A GAZDASÁGI TÁBLÁZATOK A közgazdaságtan első matematikailag elemezhető modelljeit a fiziokrata iskola egyik vezető egyénisége, XV. Lajos, francia király háziorvosa, Francois Quesnay (16941774) alkotta meg. Ezek a modellek az allokációs elméletek ősmodelljei is, hiszen a javak áramlását, a pénz körforgását, vagyis a makroökonómiai allokációkat ábrázolják. Quesnay a fiziokrata felfogás szellemében 1 azokat tekintette az ország gazdagsága megtermelőinek, akik a javakat közvetlenül a természettel kapcsolatba lépve hozták létre, vagyis a mezőgazdasági bérlőket, a farmereket. A farmerek osztálya által termelt javak részben végső fogyasztásra kerülnek, részben további feldolgozásnak vetik alá azokat. Ez utóbbi ténykedés a javaknak a formáját ugyan megváltoztatja, de a gazdagságot nem növeli - vélte jó fiziokrataként Quesnay doktor. Az ezzel foglalkozó iparosok osztályát ezért terméketlen osztálynak nevezte. Tanításának, a fiziokrata gazdaságelméletnek a fő politikai éle a harmadik osztály (nem tévesztendő össze a negyedik renddel), a javakat csupán fogyasztó, a társadalmon élősködő földtulajdonosok osztálya ellen irányult. Mivel azonban Quesnay rendkívül összefogottan megfogalmazott (mindössze néhány oldalas) tanulmányainak a politikai tartalmát nem mindenki értette meg, az ország első földtulajdonosa, maga a király sem, aki orvosa által előírt gyakorlatok gyanánt sajátkezűleg nyomtatta ki e röpiratokat. 1

A fiziokraták a nagy francia forradalom szellemi előkészítői közé tartoztak. Szoros szellemi rokonságban álltak az enciklopédistákkal, hozzájuk hasonlóan a természetet tekintették a világ elsődleges megjelenési formájának.

3

Témánk szempontjából Quesnay a következő problémát vizsgálja: A farmerek osztálya termeli a mezőgazdasági termények formájában a gazdaság össztermékét. Ebből kell mindenek előtt fedezni a mezőgazdaság saját költségeit (vetőmag stb.), fedezni a mezőgazdaság azon költségeit, ami a „terméketlenek“ által iparcikkeké alakított termények (eszközök stb.) formájában jelentkezik, és végül fedezni a tulajdonosoknak fizetendő földjáradékot. Vagyis a társadalmi összterméket megfelelően kell allokálni. A dolgot bonyolítja, hogy mindenki a jövedelmét pénzformában kívánja megkapni azért, hogy azt szabadon, saját belátása szerint költhesse el. Vajon az allokációs folyamatok biztosítják-e, hogy a reál szükségletek fennakadás nélkül kielégítődjenek, a pénzmozgások fennakadás nélkül lezajlódjanak? Ezekre a kérdésekre (is) válaszolnak Quesnay röpiratai. Az első röpirat 1758-ban jelent meg „Gazdasági táblázatok (cikk-cakkok)“ címen. Lényege a következő ábra: Termelő ráfordítások a mezőgazdaságban stb.

Ráfordítások a profitból, az adók kivonása után, amelyek termelő és nem termelő ráfordításokra oszthatóak

Nem termelő ráfordítások az iparban stb.

Éves ráfordítások. 600 livres befektetés 600 livres megtermelésére

Éves jövedelem

Éves ráfordítások az iparban, nem termelőek

600 livres értékű mezőgazdasági termék

600 livres

Ipari termékek stb.

300 l.

300 l.

300 l.

150 l.

150 l.

150 l.

75 l.

75 l.

75 l.

37,5 l.

37,5 l.

37,5 l.

18,7 l.

18,7 l.

18,7 l.

9,38 l.

9,38 l.

9,38 l.

4,69 l.

4,69 l.

4,69 l.

stb.

2. ábra Quesnai doktor „Gazdasági Táblázata“ 1758-ból

4

A táblázat a következőkből indul ki: 1. A farmerek termelő ráfordításai 2. A farmerek eszközeinek ráfordításai 3. A tiszta termék vagy jövedelem

600 (millió) livres 300 (millió) livres 600 (millió) livres

Összesen a társadalmi termék

1500 (millió) livres

Ezek az összegek egyenlőre az előző évi eredmények alapján pénz formájában jelennek meg. Pontosabban a 600 (millió) livres eredeti termelő ráfordításnak nem kell feltétlenül pénz formájában megjelennie, hiszen itt esetleges árumozgások csak a farmerek osztályán belül jelentkeznek. Ezért ez az összeg a táblázatban nem is szerepel. Ugyancsak nincs itt feltüntetve, hogy a „terméketlenek“ megelőlegezve az eszközköltségeket, az előző évben felhalmoztak 300 (millió) livrest. A tiszta jövedelem 600 (millió) livres földjáradék formájában (pénzalakban) a tulajdonosokhoz került. Ebből felerészben (300 (millió) livres) élelmiszert, felerészben (300 (millió) livres) iparcikket vásárolnak. A 300 (millió) livres-ből 150 a farmerekhez kerül, hiszen bevételük feléből a „terméketlenek“ is élelmiszert vásárolnak. A másik felét félre teszik, hogy majd a következő évben nyersanyagot vehessenek. Ha a farmerek a bevételt befektetik, akkor megint keletkezik társadalmi termék: 1. A farmerek termelő ráfordításai 2. A farmerek eszközeinek ráfordításai 3. A tiszta termék vagy jövedelem Összesen a társadalmi termék

300 (millió) livres 150 (millió) livres 300 (millió) livres 750 (millió) livres

És ismét ugyanaz történik. A tulajdonos osztály kapja a 300 (millió) livres tiszta jövedelmet, amit fele-fele arányban költ el a két termelő osztálynál. Mivel valóságos termelése csak a farmereknek van, azért előbb-utóbb 225 (millió) livres visszakerül hozzájuk, amit fel is használnak. 75 (millió) livres-t a „terméketlenek“ tartalékolnak. Ezúttal: 1. A farmerek termelő ráfordításai 2. A farmerek eszközeinek ráfordításai 3. A tiszta termék vagy jövedelem Összesen a társadalmi termék

150 (millió) livres 75 (millió) livres 150 (millió) livres 375 (millió) livres

Stb. stb. stb. Vagyis a körforgás egy mértani haladvány mentén fejlődik, amelynek kvóciense 0,5. Az összes termelési költség így

300 = 600 (millió) livres 1 − 0, 5 . Az összes eszközráfordítás 150 = 300 (millió) livres 1 − 0, 5 . Végül a tiszta jövedelem éves összege 300 = 600 (millió) livres 1 − 0, 5 .

5

Vagyis a kör bezárult, az előző évi (pénzben) előlegezett költségek javakban testesültek meg és felhalmozódtak a következő év megfelelő pénzelőlegei is. A körforgás folyamatossága biztosított. Mindez persze elég bonyolult. Érezte ezt Quesnay doktor is, ezért 1766-ban újra fogalmazta sémáit. Ezúttal a „Aritmetikai gazdasági táblázat“ címet adta röpiratának. Ennek lényege egy, az előzőnél egyszerűbb és mégis átfogóbb ábra: A farmerek éves megelőlegezett tőkéje 2 milliárd livres

A tulajdonos osztály éves jövedelme

A „terméketlenek“ éves előlegei

2 milliárd livres

1 milliárd livres

1 milliárd livres A megelőlegezett tőke kamatai és jövedelmei

1 milliárd livres

1 milliárd livres

1 milliárd livres

1 milliárd livres A megelőlegezett tőke ráfordításai

2 milliárd livres

Mindösszesen

5 milliárd livres

2 milliárd livres Mindösszesen amiből ez az osztály visszatart 1 milliárd livres-t a jövő évi előlegre

3. ábra Quesnay „Gazdasági Táblázata (Aritmetikai formula)“ 1766-ból

Persze ezt az ábrát sem egyszerű áttekinteni. Több féle módon közelíthetjük meg. a.) Megpróbálhatjuk közvetlenül értelmezni az ábrát: Az első sorban az 5 milliárd előző évi termék elsődleges szétosztása látható. 2 milliárd maradt a farmereknél, 2 milliárdot a tulajdonosok kaptak - természetesen ellenszolgáltatás nélkül földjáradék gyanánt, 1 milliárdot pedig a terméketlenek kapnak - visszafizetendő előlegként. Ez az előző év végén kialakult állapot. A vonalak az éves mozgásokat mutatják. A farmerek jövedelmük felét saját szükségleteikre elfogyasztják, a másik felét iparcikk vásárlásra fordítják. A tulajdonosok befolyt jövedelmeiket fele-fele arányban költik élelmiszerekre és iparcikkekre. A „terméketlenek“ nyersanyagra elköltik az előleget, és 1 milliárdért élelmiszert vásárolnak. Ami náluk maradt, az a jövő évi nyersanyagvásárláshoz szükséges előleg.

Végül a baloldali számoszlop a társadalmi termék folyó évi realizálását mutatja: a farmerek az eredeti 2 milliárd tőkeelőlegük felett bevételeztek 3 milliárdot s így éppen megvan az általuk piacra dobott 5 milliárdnyi termék ellenértéke. b.) Értelmezhetjük az ábrát a jólismert számviteli módszerrel is. Három számlát fektetünk fel:

Tartozik

“Terméketlenek“

1.

Élelmiszer vásárlása

1 milliárd

2.

Nyersanyagok vásárlása

1 milliárd

Összesen

2 milliárd

1.

Késztermék eladása

Követel 1 milliárd

a farmereknek 2.

Késztermék eladása

1 milliárd

a tulajdonosoknak Összesen

6

2 milliárd

Tartozik

Tulajdonosok

1.

Élelmiszer vásárlása

1 milliárd

2.

Iparcikkek vásárlása

1 milliárd

Összesen

2 milliárd

Tartozik 1.

1.

A tiszta jövedelem

2 milliárd

földjáradék formájában Összesen

2 milliárd

Farmerek

Földjáradék kifizetése

2 milliárd

1.

a tulajdonosoknak 2.

Követel

Követel Nyersanyag eladása

1 milliárd

a „terméketleneknek“

Iparcikkek vásárlása

1 milliárd

Összesen

2.

3 milliárd

Élelmiszer eladása

1 milliárd

a „terméketleneknek“ 3.

Élelmiszer eladása

1 milliárd

a tulajdonosoknak Összesen

3 milliárd

A számlák csak 3 milliárd forgalmát rögzítik, 2 milliárd a farmerek tőkeelőlege. c.) Végül alkalmazhatjuk a makroökonómiából ismert blokksémát 2 is: Két sémát rajzolunk fel, egyet a reál-, egyet pedig a pénzfolyamatok ábrázolására. (lásd a 4. és 5. ábrákat!)

Föld

Föld

Tulajdonosok osztálya

Farmerek osztálya

Tulajdonosok osztálya

Farmerek osztálya

„Terméketlen“ osztály

„Terméketlen“ osztály

5. ábra Quesnay „Gazdasági Táblázatának“ pénzfolyamatai

4. ábra Quesnay „Gazdasági táblázatának“ reálfolyamatai

2Az

alábbiakban ábrázolt sémákat először J. Bernard írta le “Marx et Quesnay“ című tanulmányában. (In “Francois Quesnay et la phisiocratie“ Vol. I. Paris, 1958.)

7

Itt befejezzük Quesnay doktor Táblázatainak ismertetését. A továbbiakban ennyi is elegendő lesz annak belátásához, hogy a modern ágazati kapcsolati elemzések forrását kétségtelenül e minden kezdetlegességük ellenére zseniális Táblázatok jelentik. 2. MARX DOKTOR ÚJRATERMELÉSI SÉMÁI

F. Quesnay hagyatékát igen hatékonyan használta fel a XIX. század közgazdaságtanának két meghatározó egyénisége, Karl Marx (1813-1883) és Leon Walras (1834-1910). Marx alapművében, „A tőké“-ben a tőkés termelési viszonyok teljes kritikai jellemzésére törekedett. Hatalmas munkáját nem tudta befejezni, több kötetesre tervezett művének csak az első kötete jelent meg az ő felügyelete mellett. A további köteteket barátja és munkatársa F. Engels, illetve tanítványaik, K. Kautsky és E. Bernstein kísérelték meg összeállítani a hátrahagyott tengernyi kéziratból. Ennek során némileg eltértek Marx eredeti elképzeléseitől, de az első három kötet logikája végül is megfelel azoknak. Az első kötet (a mikroökonómiához közelálló módon) a tőke termelési folyamatáról, a második kötet (a makroökonómiával rokon vonásokat mutatva) a tőke forgalmi folyamatáról, míg a harmadik kötet - szintetizálva az első kettőt - a tőkés termelés összfolyamatáról szól. Kurzusunk szempontjából - mint az már az alcíméből is kiderül - a második kötet a legérdekesebb. Ennek a kötetnek a megírásával bajlódott Marx a legtöbbet, ennek maradt fenn a legtöbb kézirat-variánsa. Nem lehetünk meggyőződve arról, hogy Engels ezek között válogatva a leghelyesebben járt el. Minden esetre, az alábbiakban vizsgálandó újratermelési modell egyes elemeit nem az Engels által kiadott második kötetből, hanem a jóval később kiadott kéziratokból kellett kikeresni. Marx kritikai gazdaságtanát egy sajátos módszerrel, az osztályelemzés módszerével dolgozta ki. Ezt a módszert a pártállami szocializmus hivatalos ideológiája meglehetősen eltorzította, s ezért napjainkban elég sok félreértés tapad hozzá 3 . Nincs itt mód arra, hogy e torzítások részletes kritikájával foglalkozzunk, de szükség sincs rá, hiszen kurzusunk nem erről szól. Témánk szempontjából elég ha röviden rögzítjük: a marxi modellben a tőkés társadalom két alapvető osztályra bomlik. Az egyik osztály monopolisztikusan birtokolja az összes termelési eszközt 4 . Ez az osztály a tőkések osztálya. A másik osztály, a proletáriátus tagjai nem rendelkezvén termelési eszközökkel - kénytelenek az első osztály tagjainak azt eladni, amivel szabad emberként rendelkeznek, azaz saját magukat. Ez azonban nem úgy történik, hogy rabszolgaként a tőkések tulajdonai lesznek, hiszen ez általában nem fér bele a polgári jog kereteibe. Rabszolgaként nem rendelkezhetnének saját vételárukkal sem. Mellesleg ez a tőkések érdekeinek sem felelne meg, hiszen nekik a proletárokra csak azért, és csak addig van szükségük, amíg azok a tőkések tulajdonában levő termelési eszközöket rendeltetés szerint, azaz termelési céllal, használják. Tehát az adás-vétel tárgya nem a proletárok személye, hanem személyiségüknek csupán egy része, az a képességük, hogy a termelési 3Marx magát az osztályok elméletét “A tőke“ harmadik kötetében akarta kifejteni, azonban kézirataiban mindössze a fejezet címe maradt fenn. 4Az

osztályon belül nincsenek feltétlenül egyesek monopolhelyzetben. Sőt, Marx kifejezetten az úgynevezett szabadversenyes kapitalizmust vizsgálta, ahol a (tőkés) termelők egy kompetitív piacon jelennek meg. A termelési eszközök tulajdonának monopólisztikus jellege itt kizárólag a másik osztály vonatkozásában értendő.

8

eszközöket működésbe hozva, munkát végezve javakat képesek termelni - vagyis a munkaerejük. Mivel az újkori proletárokat éppen az különbözteti meg a rabszolgatartó ókori Róma nincstelen, ámde szabad proletárjaitól, hogy azok „kenyeret és cirkuszt“ követeltek, míg ezek „munkát és kenyeret“, azért helyes ezt az osztályt munkásosztálynak nevezni. Marx elméletét a Ricardotól átvett és jócskán átalakított munkaérték-elméletre építette, ezért nála a társadalmi termék forrása kizárólag a munkások munkája, amelyhez a tőkések csupán, bár nem elhanyagolható módon, a feltételeket biztosítják. Így a társadalmi termék egy részét a javak piacán a tőkések ellenszolgáltatás nélkül elsajátítják. Ezt nevezi Marx értéktöbbletnek. Nem nehéz észrevenni itt Quesnay hatását. Mindössze Marx - Smith és Ricardo eredményeire támaszkodva - az érték forrását a földből áthelyezte a munkába. Így egybeolvasztotta a farmerek osztályát a „terméketlenekével“ - ez utóbbiakat egyáltalán nem tartva terméketleneknek - majd leválasztott róluk minden tulajdont, saját munkaerejüket kivéve. A tulajdonosok osztálya is átformálódott Marx kezeiben. Azok most már nem csak és nem elsősorban a föld tulajdonosai, hanem minden termelési eszközé, főképpen a tőkeként funkcionáló pénzé. Ami Quesnay-ből megmaradt, az egyrészt a többlet és annak ellenszolgáltatás nélküli elsajátítása, másrészt - és kurzusunk szempontjából ez a döntő - a társadalmi termelés matematikailag leírható körmozgása. E körmozgás vizsgálata „A tőke“ első kötetében kezdődik. A tőke pénztőke formájában jelenik meg a piacokon. Itt termelési eszközöket és munkaerőt vásárol. A tőkés a birtokába került javakat rendeltetésszerűen használja, azaz javakat termeltet. A javakat - termékeket - a piacon értékesíti, ami - helyes döntések eredményeként megtéríti a megelőlegezett (pénz)tőkét és értéktöbbletet is eredményez: Pénz →

RSTermelési eszközök UV → Termék → c Pénz + Értéktöbblet h T Munkaerő W

Ezt a - Marx szavával élve - metamorfózist azért lehet megvalósítani, mert a munkaerő olyan különleges áru, amely értékénél nagyobb érték termelésére képes. 5 A folyamat, Marx szerint, egy kettős folyamat: egyrészt a munkások konkrét munkájukkal átviszik az új termékre az elhasznált termelési eszközök értékét, másrészt absztrakt 6 munkájukkal megtermelik a saját munkaerejük újratermeléséhez szükséges új értéket is, amely azonban a szükséges érték felett még az értéktöbbletet is tartalmazza. Ilyenformán a tőke a megtérülése szempontjából nem egységes. Az a rész, amelyet termelési eszközökre költöttek, változatlan formában térül meg - ezért Marx ezt állandó tőkének nevezi és c (constans) betűvel jelöli. A másik részt munkaerő vásárlásra költötték, azaz bért fizettek belőle. A bért a munkások - munkaerejük újratermelése céljából - elköltik, elfogyasztják, így az megsemmisül. Helyette egy új érték keletkezik, amely más, több, mint az eredeti tőkerész. Ezért ezt a tőkerészt Marx változó tőkének nevezi és v (variabilis) betűvel jelöli. Az értéktöbbletet m (mehrwert) betűvel jelzi. Így a tőkés módon megtermelt áru értéke c+v+m. Ha feltesszük, hogy a teljes társadalmi terméket tőkés módon termelik, akkor a c+v+m formula érvényes lesz arra is.

5

Mindez természetesen a munkaérték-elmélet érvényességének feltételezésén alapul.

6Marx

elméletében kulcsjelentősségű újítás Ricardohoz képest a munka kettős jellegének elmélete, amely szerint az árutermelő munka egyszerre az adott áru használati értékét megteremtő konkrét munka, illetve az adott árunak (csere)értéket adó elvont vagy absztrakt munka. A részleteket illetően az olvasót “A tőke“ első fejezeteire kell utalnunk.

9

A továbbiakban áttérünk „A tőke“ második kötetéhez, illetve annak kézirataihoz. Marx 1863 július 6-án levelet küldött Engelsnek, amelyben elhelyezett egy bonyolult ábrát (lásd a 6. ábrát a következő oldalon) és a hozzá tartozó magyarázatokat. Hogy Engelsnek világosabb legyen, a rajz alá odamásolta Quesnay 1766-os Gazdasági Táblázatát is (ezt mi itt lehagytuk). Marx a következőket írta barátjának: “Légy szíves, ha ebben a hőségben képes vagy rá, nézd át alaposan mellékelt „gazdasági táblázatomat“, amellyel Quesnay táblázatát helyettesítem, és közöld észrevételeidet, ha vannak. ... Munkabér 100

I.Fogyasztási javak

Ipari profit

Kamat

Járadék

Profit Állandó tőke 400

Változó tőke 100

II. Gépek és nyersanyagok

Termék 700

Értéktöbblet 200

Munkabér

Ipari profit

Kamat

Járadék

Profit Állandó tőke 533 1/3

Változó tőke 133 1/3

Értéktöbblet 266 2/3

Termék 933 1/3

III. Össztermék 700 Állandó tőke 933 1/3

Változó tőke 233 1/3

Értéktöbblet 466 2/3

Termék 1633 1/3

6. ábra Doktor Marx „cikk-cakkjai“ az 1863. VII. 6-i levelében

1. A számok lényegtelenek, milliókat jelentenek. 2. Fogyasztási javak alatt itt mindazt értjük, amit az éves fogyasztási alap magába foglal (vagy foglalhatna felhalmozás nélkül, mert az ebből a táblázatból kimarad). Az I. osztály 7 (fogyasztási cikkek) összes terméke (700) mindabból a fogyasztási cikkekből áll, amelyek - következésképpen - természetüknél fogva nem alkothatják az állandó tőkét (amely nyersanyagokból, gépekből, épületekből stb. áll). Pontosan ugyanígy a II. osztály összes terméke olyan áruféleségek, amelyek az állandó tőkét alkotják, azaz ismét belépnek az újratermelési folyamatba nyersanyagok és gépek formájában. 3. A felfelé mutató vonalakat szaggatott, a lefelé mutatókat folytonos vonalak jelölik. 4. Az állandó tőke - a tőke azon része, amely nyersanyagokból és gépekből áll. A változó tőke - az, amelyet munkára cserélnek. 7

Marx az újratermelési sémákban az “osztály“ kifejezést nem ugyanabban az értelemben használja, mint a társadalmi osztályok esetében. Ez az osztály-fogalom nagyjából az ágazat, illetve a szektor fogalmának felel meg. Később látni fogjuk, hogy valamiféle kapcsolat a két osztály-fogalom között mégis kimutatható.

10

5. A mezőgazdaságban, például, egy része valamely terméknek (például a búzának) fogyasztási cikket alkot, ugyanakkor egy másik része (szintén a búzáé) természetes formájában (például vetőmagként) ismét belép az újratermelési folyamatba nyersanyag gyanánt. Ez azonban a dolgokon mit sem változtat, mert a termelés ilyen típusú ágazatai az egyik tulajdonságnál fogva az I. osztályban, másik tulajdonságuknál fogva a II. osztályban szerepelnek. 6. A dolog lényege tehát a következő: I. Kategória. Fogyasztási javak.

A munkaanyagok és gépek (azaz a gépek azon része, amely a kopás következtében kerül az éves termékbe; a gépek el nem használt része a táblázatban egyáltalán nem szerepel) értéke egyenlő, mondjuk, 400 fonttal. A munkára cserélt változó tőke = 100. Ez 300 értékben termelődik újra, ebből a termékben 100 megtéríti a munkabért, 200 pedig az értéktöbblet (meg nem fizetett többlet munka). A termék = 700; ezen belül 400 jelenti annak az állandó tőkének az értékét, amelyet teljes egészében átvittek a termékbe, s ezért meg kell, hogy térüljön. A változó tőke és az értéktöbblet ilyen aránya feltételezi, hogy a munkás munkanapjának 1/3-át saját magának dolgozza le, 2/3-át pedig „természetes elöljárói“ számára. Tehát, 100 (változó tőke), mint azt a szaggatott vonal mutatja, pénzben kifizetésre kerül, mint munkabér. A munkás megveszi ezért a 100 egységért ugyanennek az osztálynak a termékét, azaz 100 értékben fogyasztási javakat vásárol. Ilyenformán a pénz visszafolyik az I. osztály tőkéseihez. A 200 értéktöbblet a maga általános formájában = profit, amely a maga részéről felbomlik ipari (beleértve a kereskedelmit is) profitra, azon kívül a kamatra, amelyet az ipari tőkés pénzben fizet ki, és a földjáradékra, amit szintén pénzben fizetnek meg. Ezek a pénzek, amiket ipari profit, kamat és földjáradék formájában kifizettek, visszaáramlanak (amit lefele mutató vonalak mutatnak) amiatt, hogy ezekért az I. osztály termékeit vásárolják. Ilyen formán az I. osztályon belül az ipari tőkés által elköltött összes pénz visszaáramlik hozzá annak köszönhetően, hogy 300-at az összes 700 értékű termékből a munkások, a vállalkozók, a pénztőkések és a földbirtokosok elfogyasztanak. Az I. osztályban marad feleslegben termék (fogyasztási javak formájában) = 400, és hiányzik állandó tőke = 400. II. Kategória. Gépek és nyersanyagok.

Mivel e kategória teljes terméke - nem csak a termék azon része, amely megtéríti az állandó tőkét, de az is amely a munkabér és az értéktöbblet egyenértékéül szolgál nyersanyagokból és gépekből áll, azért e kategória jövedelme nem realizálható saját termékeivel, hanem csak az I. kategória termékeivel. Ha eltekintünk a felhalmozástól, ahogy azt itt tesszük, akkor az I. kategória a II. kategóriánál csak annyit vásárolhat, amennyi neki szükséges az állandó tőkéje pótlásához, a II. kategória pedig termékének csak azt a részét költheti az I. kategória termékeire, amelyek a munkabért és az értéktöbbletet (a jövedelmet) jelenítik meg. Tehát, a II. kategória munkásai elköltik pénzüket = 133 1/3 az I. kategória termékeire. Ugyanez történik a II. kategória értéktöbbletével is, amely, akárcsak az előző esetben is, ipari profitra, kamatra és földjáradékra hasad szét. Ilyen formán az I. kategória ipari tőkéseihez a II. kategóriától átáramlik pénzben 400; az I. kategória ezért cserébe a II. kategória rendelkezésére bocsátja maradék termékét = 400. Az I. kategória ezért a 400-ért (ami pénzben van neki) megvásárolja a II. kategóriánál azt, amire szüksége van az állandó tőkéje = 400 pótlásához, és ezzel a II. kategóriához ismét visszaáramlik az általa munkabérre és fogyasztásra (maguknak az ipari tőkéseknek, a pénztő11

késeknek és a földbirtokosoknak a fogyasztására) költött pénz. Megmaradt összesen a II. kategóriánál 533 1/3 értékben termék, amit az saját elkopott állandó tőkéjének pótlására használ. A részben az I. kategórián belüli, részben az I. és a II. kategóriák közötti mozgás ugyanakkor megmutatja, milyen módon áramlik vissza a két kategória megfelelő ipari tőkéseihez a pénz, amiből azok ismét kifizethetik a munkabért, a kamatot és a földjáradékot. A III. kategória az egész újratermelést jeleníti meg. A II. kategória összterméke itt, mint az egész társadalom állandó tőkéje jelenik meg, az I. kategória összterméke pedig mint a társadalmi termék azon része, amely pótolja a változó tőkét (munkabér alap) és az értéktöbbletet maguk között felosztó osztályok jövedelmeit.“ 8 Ezt a hosszú idézetet két okból iktattuk ide. Egyrészt aligha tudtuk volna hitelesebben megmagyarázni a meglehetősen szövevényes ábrát, mint maga a szerző. Másrészt ebben a levélben látható, hogy Marx jól érzékelte a fellépő problémákat is, bár ezek egy részét ekkor még (s némelyiket később is) alábecsülte. Így a levélrészlet 1. pontja azt jelenti, hogy itt nem aritmetikai (számtani), hanem algebrai modellel van dolgunk. Kérdéses, hogy a konkrét számadatok (amelyek statisztikailag semmit sem jelentenek - ellentétben Quesnay számaival, amelyek nagyságrendileg helyes becslései voltak a korabeli tényeknek) segítik, vagy ellenkezőleg gátolják a megértést. Jelen könyv szerzője hajlik az utóbbi álláspont elfogadására, s szívesebben tárgyalja az újratermelési modelleket tisztán algebrai formában. A 2. és 6. pontokban tett megjegyzés a felhalmozás kiiktatására a későbbiek során érvényüket vesztették, mivel Marx szétválasztotta és külön-külön alapos elemzés tárgyává tette az egyszerű újratermelés (amikor a felhalmozástól eltekintünk) és a bővített újratermelés (amikor a felhalmozást beépítjük) modelljeit. Mindamellett a tőkefelhalmozás (az akkumuláció) problémáit meggyőzően nem tudta megoldani. Halála után széles nemzetközi vita alakult ki e problémáról. E vitában sokan kifejtették véleményüket, köztük M. Tugan-Baranovszkij, V. Lenin (Uljanov) orosz, O. Bauer, K. Kautsky osztrák és R. Luxemburg német szerzők. Nagyon fontos kérdést érint Marx az 5. pontban. Egyszerre két probléma is felmerül itt. Az egyik az ikertermékek problémája, vagyis az a probléma, hogy egy termelő folyamatban, szétválaszthatatlan ráfordításokkal több termék keletkezik. Ilyen például a távfűtés, amelynél a távhő szolgáltatás mellett villamos energiát is termelnek. Ez egy sor problémát jelent, köztük azt is, ami kapcsolódik Marx megjegyzéséhez, hogy tudniillik, lehetséges, az egyik ikertermék jellegzetesen fogyasztási cikk (távhő), a másik viszont ipari input tényező (elektromos energia). Az 5. pont azonban egy talán még lényegesebb problémát is felvet - az idő szerepét. A termelési döntéseket a piaci értékesítés előtt hozzák, azonban az, hogy a terméket fogyasztási cikként, vagy termelési eszközként használják fel, csak a piaci értékesítés után derül ki. Kornai János e problémának a marxitól eltérő megoldásával dolgozta ki a hiány elméletét. A letisztított modellek „A tőke“ Engels által sajtó alá rendezett II. kötetében szerepelnek. Nézzük először az egyszerű újratermelés modelljét:

8

Marx levele Engelshez 1863. július 6-án, MEM 30.

12

“I. Termelési eszközök termelése: Tőke ........................................... 4000c+1000v=5000. Árutermék .................................. 4000c+1000v+1000m=6000, ami termelési eszközökben létezik. II. Fogyasztási eszközök termelése: Tőke ........................................... 2000c+ 500v=5000. Árutermék .................................. 2000c+ 500v+ 500m=3000, ami fogyasztási eszközökben létezik. Összesítve, az évi összárutermék: I. II.

4000c + 1000v + 1000m = 6000 termelési eszköz, 2000c + 500v + 500m = 3000 fogyasztási eszköz.“ 9

Ha elhagyjuk Marx konkrét (bár semmit nem jelentő) számait, akkor ugyanez algebrai alakban a következő: I. c1 + v1 + m1 = T II. c 2 + v 2 + m2 = F Az első osztály c1 állandó tőkéjét saját termékeiből pótolja, így csupán v1+m1 értékű termékrészt kell a piacon realizálnia. A második osztály viszont a c2 értékű fogyasztási cikkekben megtestesülő termékét realizálja a piacon, hogy ellenértékéért az állandó tőkéjét pótolhassa. A két egyenlet a piac kínálati oldalát mutatja. Felírható a keresleti oldal is: I. c1 + c 2 = T II. v1 + m1 + v 2 + m2 = F Ebből jól kiolvasható az a marxi megállapítás, hogy amennyiben nincs felhalmozás (egyszerű újratermelés), akkor a teljes társadalmi (nemzeti) jövedelem a II. osztályban realizálódik. A zavartalan újratermelés tágabb feltétele a piaci egyensúly, azaz a két egyenletrendszerben a T és az F mindkét helyen ugyanazokat a terméktömegeket kell, hogy jelentse. Fontos azonban, hogy ez a feltétel szűkebben is megfogalmazható. Elegendő, ha c 2 = v1 + m1 Ez természetesen könnyedén levezethető a tágabb feltételből, de közvetlenül következik a fentebb kifejtett közgazdasági megfontolásokból is. Ezt ábrázolja Oskar Lange lengyel közgazdász sémája (a bekeretezett mennyiségek kerülnek valódi piaci cserére):

I. c1+ v1 + m 1= T II. c2 + v2 + m 2 = F A bővített újratermelés marxi sémái, ezúttal már csak az algebrai alakban felírva: I. c1 + v1 + m1F + m1C + m1V = T II. c 2 + v 2 + m2 F + m2C + m2 V = F

9

MEM 24. 361. oldal

13

Itt az m1 értéktöbbletnek csak egy részét (m1F) fogyasztják el az I. osztály tőkései, a fennmaradó részt az állandó és a változó tőke bővítésére használják (m1C és m2V). Teljesen analóg módon osztják fel a II. osztály értéktöbbletét is: m2=m2F+m2C+m2V. Nyilván az első osztály saját termékéből bővíti az állandó tőkéjét, a második osztály viszont a változó tőkéjét. Így a keresleti egyenletrendszer: I. c1 + c 2 + m1C + m2C = T II. v1 + v 2 + m1F + m2 F + m1V + m2 V = F Megint csak igen egyszerűen vezethető le a zavartalan újratermelés feltétele a két egyenletrendszerből: v1 + m1F + m1V = c 2 + m2C Természetesen most is felrajzolhatjuk O. Lange sémáját:

I. c1 + v1 + m 1F + m1C + m1V = T II. c2 + v2 + m 2 F + m2 C + m 2V = F A feladat bonyolítható a bővítés különböző feltételeivel. Közgazdaságtanilag értelmezhető feltételek például: •

a bővítés során változatlan marad az I. és a II. osztály termelésének aránya;

•

a bővítés során változatlan marad az állandó és a változó tőke aránya (a tőkeösszetétel).

Az egyszerű újratermelés zavartalanságához a kereslet és a kínálat hibátlan egyensúlyára van szükség, hogy a c 2 = v1 + m1 pontosan teljesüljön. Megmutatható, hogy ez a bővített újratermelés esetén nem így van. Tegyük ugyanis fel, hogy v1 + m1F + m1V >c 2 + m2C Ez azt jelenti, hogy a piacon fogyasztási cikkekből túlkereslet van. Ekkor a piac szabályai szerint a fogyasztási cikkek ára a termelési eszközökéhez képest emelkedik. Ugyanakkora költségek mellett így nagyobb lesz a II. osztály profit-kilátása. Ez arra ösztönzi a II. osztály tőkéseit, hogy fokozzák bővítésüket, azaz növeljék az m2C-t. Ha ezt megfelelő mértékben teszik, akkor az egyensúly helyre áll. Első pillantásra. Ha ugyanis jobban belegondolunk, akkor be kell látnunk, hogy az I. osztály a megnövekedett keresletet csak bővítéssel tudja kielégíteni, ezért nőni fog m1V is. Beáll tehát egy fokozódó bővítés időszaka, egy konjunktúra. Ez azonban nem tart örökké. Mivel az egyenlőtlenség fennmaradása a fogyasztási cikkeket továbbra is relatíve drágítja, azért az I. osztályt csak a piac bővülése, a II. osztályt viszont a magas ár is ösztönzi a termelése fokozására. Így m1V szükségszerűen lassabban nő, mint m2C, és az egyenlőtlenség fokozatosan kiegyenlítődik. A konjunktúraelméletből ismert akcelerátor hatás miatt a folyamat nem áll meg a kiegyenlítődésnél, hanem az egyenlőtlenség ellenkező irányba billen: v1 + m1F + m1V
14

Ez az előbbivel analóg, de ellentétes folyamatokat indít meg. Dekonjunktúra, negatív akcelerátor, az egyenlőtlenség kiegyenlítődése és átfordulása, s.i.t. s.i.t. s.i.t 10 . Marx modelljének sajátos interpretációját adta S. Koshimura japán közgazdász „Theory of capital reproduction and accumulátion“ című könyvében, amely japánul 1955ben, angolul 1975-ben jelent meg. Koshimura három szektorosra alakította Marx sémáit (ez nyomokban magánál Marxnál, illetve Leninnél is előfordul, akik harmadik szektorként a luxusjavakat termelő szektort említik.) A három szektor Koshimuránál már közvetlen kapcsolatban van a Marx által alapul vett szociális osztályokkal, amennyiben az első osztály (szektor) az állandó tőkét realizáló javakat, a termelési eszközöket állítja elő, ezeket kizárólag a tőkések vásárolják; a második osztály (szektor) a változó tőkét realizáló javakat állítja elő, amelyek fogyasztói a munkások, a harmadik osztály (szektor) azokat a javakat állítja elő, amelyek jellegzetesen nem a munkások szükségleteit elégítik ki, de nem is termelési eszközök. Ezeket a tőkések közvetlenül, vagy közvetve (az államon keresztül) az általuk elsajátított értéktöbbletből vásárolják meg. Ez mindenek előtt a tőkések személyes fogyasztását jelenti, ami Marx korában a munkások fogyasztásához képest jól megkülönböztethető luxusjavakból állt. Ma már nincs olyan jellegzetes különbség a munkások által fogyasztott és a tőkések által fogyasztott javak minősége között, bár még ma is sok luxusjószágot fogyaszt a társadalom felső jövedelmi rétege. Viszont napjainkban az értéktöbblet viszonylag csekély hányadát költik személyes szükséglet-kielégítésre, így kis absztrakcióval ma is elfogadható a harmadik osztályra vonatkozó feltételezés. Koshimura Marx-interpretációja az érték (kínálati) oldalon a következő: I . C = c1 + v1 + m1 II. V = c 2 + v 2 + m2 III. M = c 3 + v 3 + m3

A használati érték (keresleti) oldalon: I.

C = c1 + c 2 + c 3

II. V = v1 + v 2 + v 3 III. M = m1 + m2 + m3

A zavartalan újratermelés feltétele: c1 + v1 + m1 = c1 + c 2 + c 3 c 2 + v 2 + m 2 = v1 + v 2 + v 3 c 3 + v 3 + m3 = m1 + m2 + m3

azaz v1 + m1 = c 2 + c 3 c 2 + m 2 = v1 + v 3 c 3 + v 3 = m1 + m2

Megjegyezendő, hogy itt bármelyik egyenlet levezethető a másik kettőből, tehát bármely kettő is elegendő. 10

A részletes elemzés megtalálható: Erdős P. Adalékok a mai tőkés pénz, a konjunktúraingadozások és a gazdasági válságok elméletéhez KJK Budapest, 1974.

15

Marx kéziratai az újratermelési sémák kapcsán döbbenetes mennyiségű számítást tartalmaznak. Felületes szemlélő felesleges szőrszálhasogatásnak vélné ezeket. Valójában egy gigászi küzdelem nyomai ezek, amely küzdelemben Marx végül is - megfelelő fegyverzet híján - alul maradt. Előkerültek Marx matematikai kéziratai, amelyekből kitűnik, hogy Marx igen jól felismerte az akkoriban gyors fejlődésnek indult matematikai analízis jelentőségét. A hiányosan rendelkezésére álló irodalom segítségével valósággal újra felfedezte a határértékszámításon alapuló differenciálhányados fogalmát. Elképzelhető, hogy milyen lelkesedéssel töltötte volna el, ha legalább ugyanilyen hiányos irodalom állt volna rendelkezésére a modern lineáris algebra, a mátrixszámítás területéről. Ilyen matematikai eszköztár segítségével ki tudja, meddig jutott volna el. Ugyanezt elmondhatjuk Marx ifjabb kortársáról, a svájci Lausanne egyetemén tevékenykedő, francia születésű Leon Walrasról is. Ő egészen más ideológiai állásponton vizsgálódott, de ezeknek a matematikai eszközöknek ő is igencsak örült volna. Mit nem adott volna, ha ismeri a lineáris egyenletrendszerek modern elméletét! 3. LEON WALRAS EGYENLETRENDSZERE

Ha Marxnál a kapcsolat Quesnay modelljével nyilvánvaló (és Marx által soha nem tagadott, hanem éppen ellenkezőleg, kinyilvánított) tény, akkor L. Walras esetében erről szó sincs. A marxi modell Quesnay közvetlen hagyományai nyomán alakult, és összefonódott a Petty-Smith-Ricardo vonal munkaérték-elméletével. Ezzel szemben Walras kutatásaiban a Smith-Say-Gossen-Jevons vonal mentén kifejlődött marginalista közgazdaságtanra támaszkodott. Maga Walras ismerte a marxi elmélet alapjául szolgáló, „A tőke“ első kötetében kifejtett munkaérték-elméletet, azt hibásnak és elvetendőnek tartotta. Ugyanakkor aligha valószínű, hogy saját egyensúlyelméletének kidolgozásakor ismerte volna Marx újratermelési sémáit, hiszen „A tőke“ második kötete 1885-ben jelent meg, ezzel szemben Walras fő műve az „Éléments d' Économie Politique Pure“ 1874-ben látott napvilágot Lausanne-ban. Walras sokat merített a francia matematikus A. Cournot közgazdasági jellegű kutatásaiból (ezek közül az oligopóliumok Cournot-féle modelljét ismerhetjük a mikroökonómiai tanulmányainkból). Témánk szempontjából jelentős különbség a marxi és a walrasi modellek között, hogy amíg Marx modelljeiben a termelő szektorok (mint az Koshimura interpretációjából látható) az osztályviszonyokból származtathatóak, tehát a későbbi keynesi terminológiával makroökonómiai jellegűek, addig Walras, hűen a marginalista mikroökonómia elveihez, termékszintre lebontott, illetve azokból aggregálható ágazatokkal dolgozott. Walras feltételezi, hogy a gazdaságban m terméket termelnek n termelési tényező felhasználásával. Felteszi továbbá, hogy léteznek szilárd, alig vagy egyáltalán nem változó technológiai összefüggések, amelyeket egy konstans {aij} technolóiai koefficiens halmaz fejez ki, ahol aij az i-dik termék egységnyi előállításához szükséges j-ik tényezőmennyiséget jelenti (i=1,2, ... m; j=1,2, ... n). A modell egyenletrendszer formájában írható fel. Ismeretlenek: Di az i-dik termék kereslete; Sj a j-ik tényező kínálata; pi az i-dik termék ára; πj a j-ik tényező ára. 16

Az egyenletrendszer:

b = ϕ b p ,..., p

g , π ,..., π g

D i = fi p1 ,..., p m , π l ,..., π n

i = 1, 2, . .. m

Sj

j = 1, 2, . .. n

j

1

m

m

l

S j = ∑ a ij D i

n

j = 1, 2 , ... n

i =1 n

p i = ∑ a ij π j i = 1, 2 , ... m j= 1

Itt az első két egyenletcsoport a hagyományos keresleti, illetve kínálati függvények általánosításai, amennyiben az i-dik termék kínálata függ valamennyi termék árától (keresztárrugalmasságok!) és a termelési tényezők áraitól is. Ugyanígy a j-ik tényező kereslete is valamennyi piaci ártól függ (optimális tényező-felhasználás!). A második két egyenletcsoportnak a továbbiakban még nagy jelentőssége lesz. Ezek tulajdonképpen allokációs egyenletek. Az első (egészében harmadik) egyenletcsoport azt mutatja meg, hogy a j-ik tényezőből mennyit kell kínálni, hogy valamennyi (i=1,2, ... m) keresett termék előállítható legyen. Valóban Di mennyiségű termék előállításához a j-ik tényezőből aijDi mennyiség kínálata szükséges. Ezeket a mennyiségeket kell összegezni a teljes j-ik tényező kínálati szükségletének megállapításához. A második (negyedik) csoport az előző duális egyenletrendszerének tekinthető. Egy termék árát a felhasznált tényezők bekerülési költségei határozzák meg (a marginalista felfogás szerint). Mivel pi az i-dik termék egységára, azért nagysága az egységnyi termék előállításához szükséges aij mennyiségű (j=1,2, ... n) tényezők bekerülési költségének összege. Az aij mennyiségű tényező bekerülési költsége éppen aijπj. Walras úgy gondolta, hogy amennyiben ennek az egyenletrendszernek van megoldása, akkor a gazdaság egyensúlyban van. Walras számára korának matematikai színvonalán az egyenletrendszer megoldhatóságának megállapítása még nem kis feladatot jelentett. Mindenekelőtt ki kellett küszöbölnie a redundáns (a többitől függő, ezért felesleges) egyenleteket. Majd megszámolta a megmaradt egyenletek számát és a változók számát. Ekkoriban született az a matematikai tétel, hogy egy inhomogén, redundáns egyenletet nem tartalmazó és ellentmondás mentes egyenletrendszernek akkor és csak akkor van pontosan egy megoldása, ha ugyanannyi egyenletből áll, ahány változója van. Walras ezt próbálta meg felhasználni az egyensúly egyértelműségének kimutatására. Számításai kissé meglepő eredménnyel jártak. Kiderült, hogy a nem redundáns egyenletek száma modelljében eggyel kisebb a változók számánál. Mivel a keresleti-kínálati változók önálló jelentéssel bírnak, ezért azokhoz nyúlni nem lehetett. Más volt a helyzet az árváltozókkal. Ezek a Say-dogma szerint relatív nagyságok. A Say-dogma egyik következménye ugyanis az, hogy a piacon a pénzben számolt kereslet mindig megegyezik a pénzben számolt kínálattal, vagyis ha egy eladó nem tudja adott összegen eladni áruját, akkor a piacon valahol hiába próbálnak valakik ugyanezért az összegért árut venni, mert nem találnak (ez az összefüggés Walras-törvény néven került be a közgazdaságtudományba). De így az árak bármilyen szorzóval felszorozhatóak, ez a piac egyensúlyi viszonyain nem fog változtatni. Közgazdaságtanilag ez egybevág azzal a feltételezéssel, hogy amennyiben a pénznek a cserék lebonyolításán kívül nincs más szerepe, akkor ezt a pénzfunkciót bármelyik áru betöltheti. Tehát Walras az egyik árut (az egyszerűség kedvéért, mondjuk az i=1 árut) kinevezte pénznek, ennek árát konstansnak - mondjuk éppen 1-nek - vette és a maradék

17

változók száma most már megegyezett az egyenletek számával. Walras számára ezzel az egyértelmű egyensúly létezése bizonyítást nyert. De hogyan lehet ezt az egyensúlyt megtalálni? Ez volt a következő probléma. A megoldáshoz Walrasnak nem álltak rendelkezésre kielégítő matematikai módszerek, ezért egy kissé heurasztikus eljáráshoz folyamodott. Kitalált egy gazdaság felett álló személyt, az „árverezőt“ vagy „árkikiáltót“. Ez az árkikiáltó kikiáltott egy árrendszert. Ezzel az árrendszerrel az egyenletrendszer vagy megoldható volt, vagy sem. Pontosabban, az egyenletrendszer mindig megoldható, de nem mindig a nem negatív számok körében. Éppen a Walras-törvény következtében a keresletek és kínálatok pénzben kifejezett összege mindig 0. Ha tehát a kikiáltott ár nem biztosítja az egyensúly, akkor egyes kínálatok illetve keresletek negatív értéket fognak felvenni. Ha egy kínálat negatív, akkor az adott tényezőből túlkereslet van, tehát az ára túl alacsony. Ha viszont egy kereslet negatív, akkor az adott termékből túlkínálat van, vagyis az ára túl magas. Ezeket a megállapításokat figyelembe véve az árkikiáltó korrigálja az árakat. Teszi ezt egészen addig, amíg valamennyi kereslet és kínálat nemnegatív értéket nem vesz fel, azaz be nem áll az egyensúly. Hogy az árkikiáltónak ez a ténykedése, amit Walras „puhatolódzásnak“ - tâtonnement-nek - nevezett, eredményes, azt majd később, az árnyékárak apparátusának a kidolgozásakor sikerült korrektül bizonyítani. Walras modellje egy sor eredménnyel gyarapította a matematikai közgazdaságtan egészét, s azon belül az allokációk elméletét. A gazdasági feltételek zárt matematikai egyenletrendszerbe szervezése (ami Marxnál csak bújtatva, számpéldák mögé rejtve jelent meg) nagy lökést adott a matematikai modellezés és a matematikai programozás kidolgozóinak. A technológiai koefficiensek alkalmazása különösen termékeny ötlet volt. 4. A TÖRTÉNET FOLYTATÁSA

Quesnay, Marx és Walras eredményei a XX. században igen gyors fejlődés alapjaiul szolgáltak. A.) LINEÁRIS PROGRAMOZÁS

A walrasi egyenletrendszerek hatása aligha zárható ki a lineáris programozás megalkotásának történetéből. A lineáris programozás első általános modelljeit egymástól lényegében függetlenül a szovjet L. Kantorovics (1912-1986) és az amerikai G.B. Dantzig (1920- ) alkották meg. Mindkét kutatás konkrét, tipikusan allokációs feladatok megoldására irányult. Kantorovics egy bútoralapanyag gyár termelésének optimalizálására kapott feladatot. A drága funérlemezek előírt nagyságú darabokra szabását kellett megoldania, a legkisebb anyagveszteség mellett. Dantzig az USA hadügyminisztériumának speciális kutatóintézetében, a RAND Corporation-nél végzett kutatásokat. Csoportjának egyik nagy fegyverténye, s egyben a lineáris programozás egyik ősfeladata volt a II. világháború alatt egy japán megszállás alatt álló sziget inváziójának olyan megtervezése, hogy az a legkevesebb amerikai emberveszteséggel járjon. Ez a feladat egyszerre adott lökést a lineáris programozásnak és a vele szoros kapcsolatban álló játékelméletnek. Egészen pontosan ennek a feladatnak a kapcsán született az „operációkutatás“ kifejezés.

18

B.) INPUT-OUTPUT ELEMZÉS

1925-ben a Szovjetunióban publikálták az első népgazdasági mérlegszámítások eredményeit. Ezek között szerepelt egy sakktábla-szerkezetű 11 táblázat, amihez hasonló addig statisztikai jelentésekben még nem fordult elő. Az első oszlopba, illetve az első sorba a szovjet gazdaság főbb ágazatainak neve került, a belső négyzetekbe pedig az első oszlopban az adott sorhoz rendelt ágazat szállításai az első sorban az adott oszlophoz rendelt ágazatnak. A szokatlan adathalmaz felkeltette a leningrádi egyetem utolsó éves közgazdászhallgatójának, V. Leontyevnek az érdeklődését. A megjelent publikációról recenziót írt a szovjet Tervhivatal „Плановое хозяйство“ (Tervgazdaság) című lapjába. Ebben a következőket írta: „Elvileg új ebben a mérlegben, összehasonlítva az olyan szokásos gazdaságstatisztikai kutatásokkal, mint amilyenek például az amerikai és angol cenzusok, az a kísérlet, amely átfogja számokkal nem csak a társadalmi termék termelését, de az elosztását is azzal, hogy ezen az úton az egész újratermelési folyamatról képet kapjunk egy sajátos «tableu economique» formájában.“ Itt nyilvánvaló az utalás Quesnay gazdasági táblázataira. Magában a mérlegpublikációban a munkacsoport vezetője I.P.Popov Marx újratermelési sémáit jelöli meg módszertani kiindulópontként, s az eddigiek alapján világos, hogy ez nem (vagy legalábbis nem csak) az akkoriban szokásos ideológiai tiszteletkör volt csupán. Sokkal inkább valamiféle ideológiai anti-tiszteletkörnek tűnik, hogy évekkel később, a már az USA-ban dolgozó V. Leontyev (W. Leontief) az általa kidolgozott és az amerikai gazdaság adataival verifikált „input-output elemzés“ módszertani kiindulópontjának Walras egyenleteit jelölte meg. Kétségtelen, hogy az alapötletet az általa jól ismert 1923-1924 évi szovjet „sakktábla“ szolgálta, tehát a gyökerek Quesnay és Marx sémáiig nyúlnak vissza. Walrastól csupán a technológiai koefficiensek ötlete származik - ami persze szintén nem semmi. C.) AZ ÁLTALÁNOS EGYENSÚLY ELMÉLETE

A walrasi modell naivitásait a korszerű matematikai eszközök birtokában ki lehetett küszöbölni. Ez meg is történt. Egyfelől a marginalista „neoklasszikus“ elmélet - Gossen, Jevons, Edgeworth és Pareto - örökségének szigorú matematikai rendezése J.R. Hicks (19041989) által. Másfelől - Hicks eredményeinek felhasználásával - G. Debreu (1921-) és K.J. Arrow (1921-) rekonstruálták Walras általános egyensúly-elméletét, azt új, szabatos formába öntve. Az Arrow-Debreu féle általános egyensúlyi modell igen egyszerű interpretációi az úgynevezett Edgeworth-dobozok segítségével kifejtve szerepelnek a mikroökonómia majd minden jelentősebb tankönyvében.

11

Ez egy általánosan elterjedt képzavar. Valójában nem a 8*8-as négyzethálóról van szó, de még csak nem is a sorokban/oszlopokban váltakozó világos és sötét mezőkről. Sakktábla-szerkezetnek a sakkversenyeken (és más páros versenyeken) szokásos eredményjelző táblázat szerkezetét nevezik. Itt vízszintesen és függőlegesen ugyanaz a névsor szerepel a széleken, míg a táblázat belsejében minden négyszögbe a hozzá tartozó két versenyző egymás ellen elért eredményét írják be.

19

Mindezek az előzményei, s részben már szerves elemei, annak a hatalmas fejlődésnek, amely napjainkban az allokációs elméletek és a különféle ágazati kapcsolati modellek területén megfigyelhető.

20

KÖZGAZDASÁGTAN ÉS OPERÁCIÓKUTATÁS (MÁSODIK ELŐADÁS) 1. MATEMATIKAI JELÖLÉSEK A KÖZGAZDASÁGI IRODALOMBAN

A közgazdaságtudományi szakokra néhány évvel-évtizeddel ezelőtt még azok jelentkeztek, akiknek általában a matematika nem tartozott az erős oldalaik közé. Igaz, mint az előző előadásból látható, a matematikai közgazdaságtan gyökerei az általános közgazdaságtan legrégebbi időibe nyúlnak vissza, ám hosszú ideig ez az ága a közgazdaságtannak ugyancsak elkülönült a többitől, és a közgazdászoknak egy meglehetősen szűk csodabogár-jellegű csoportja foglalkozott vele. Gondoljuk csak meg, a marginalista közgazdaságtan talán legtekintélyesebb képviselője, Böhm-Bawerk, az osztrák iskola vezéregyénisége, szinte teljesen mellőzte a Jevons és Walras, illetve tanítványaik által használt matematikai apparátust. Marx követői sem igen alkalmaztak matematikai módszereket, sőt, a marxi tanokat kanonizálva kisajátító sztálinizmus a matematikai közgazdaságtant általában mint burzsoá áltudományt bélyegezte meg. A fordulat az 50-es évek végén következett be. Jellemző, például, hogy az 1969 óta odaítélt közgazdasági Nobel-díjakat szinte kivétel nélkül olyan közgazdászok kapták, akik a matematikai közgazdaságtan területén alkottak. A Szovjetunióban a matematikai közgazdaságtan - amit az SZKP XX. kongresszusa (1956) előtt burzsoá áltudományként kezeltek - 1959-ben kapott hivatalos elismerést, amikor megjelent „A matematika alkalmazása a közgazdaságtani kutatásokban“ című gyűjtemény és három kutató, V.Sz. Nyemcsinov, V.V. Novozsilov és L.V. Kantorovics a legmagasabb állami kitüntetést kapták az e téren kifejtett kutatásaikért. Kantorovics később megkapta a közgazdasági Nobel-díjat is. Ma már valamirevaló közgazdaságtani szakszöveget matematikai ismeretek nélkül aligha lehet megérteni. Itt azonban nem csak a matematikai ismeretek hiánya okozhat problémát, hanem az alkalmazott jelölések megértése is. Ugyanis szinte ahány szerző, annyi jelölést alkalmaznak. A.) A DERIVÁLÁS JELÖLÉSEI

Mint az általában ismeretes, a matematikai kalkulus (analizis, integrál-differenciál számítás) felfedezése (feltalálása?) egyszerre két tudós nevéhez fűződik: I. Newton és G.W. Leibniz szinte egyidejűleg érték el eredményeiket. Azonban, míg Newton elsősorban fizikai kutatásainak szükségleteire dolgozta ki a megfelelő matematikai apparátust, addig Leibniz filozófiai meditálásai során jutott el a kis léptékű változások vizsgálatához. Ennek megfelelően másképpen vezették le, és másképpen jelölték például a derivált függvényt. Tulajdonképpen derivált (leszármaztatott) függvényről csak Newton beszélt. Ő a mozgó testek kinetikáját vizsgálva jutott arra a felismerésre, hogy a test által befutott útvonal hossza ugyanúgy az eltelt idő függvényében alakul, mint a test sebessége, és a két függvény között kapcsolat van. Ha ismerem a megtett út hosszának függvényét az időtől, akkor kiszámítható, leszármaztatható, a sebesség függvénye, amely így az út időfüggvényének származtatott függvénye, deriváltja lesz. Ezt a felfedezett tényt Newton a következőképpen jelölte. Legyen a test által t idő által befutott táv s, azaz

bg

s = s t vagy s:t → s 21

Ekkor a sebesség v függvénye az s(t) függvény deriváltja lesz: v = v ( t ) = s ( t ) vagy v:t → s

Ebből a jelölésmódból fejlődött ki a modern jelölés:

bg

bg

ha y = f x , akkor a derivált y ′ = f ′ x

Az eredeti newtoni jelölést (a felső pontot) igen gyakran használják Newton eredeti szellemében, vagyis az idő szerinti deriválás jelölésére. Ugyancsak használják akkor, ha paraméteresen megadott függvényt a paraméter szerint deriválják. Ilyenkor a paraméterváltozót általában t betű jelöli. Leibnizet elsősorban filozófiai kérdések, a véges és végtelen, a diszkrét és a folytonos stb. problémái izgatták. Ö arra figyelt fel, hogy amennyiben kis mértékben megváltoztatja a független változót, akkor általában nem túl nagy mértékben változik a függő változó is, mégpedig nem akárhogyan, hanem valamiféle törvényszerűség szerint. Megpróbálta a két változás egymáshoz való viszonyát, arányát vizsgálni. Azt találta, hogy minél kisebb a független változó növekménye, annál nyilvánvalóbb, hogy a két növekmény aránya valamilyen törvényszerűséget követ. Úgy gondolta, hogyha minden határon túl csökkenti a független változó növekményét, akkor új típusú mennyiségek jönnek létre, az infinitezimális (végtelen kicsiny) mennyiségek. A növekmény csökkentésével létrejött infinitezimális mennyiségeket differenciáloknak (végtelen kicsiny változásoknak, differenciáknak), s az általa felfedezett összefüggést az infinitezimális mennyiségek közötti differenciálhányadosoknak nevezte. A differenciálok jelölésére a változó neve mellé balról írt d betűt használta. A differenciálhányados ennek megfelelően:

bg

ha y = f x , akkor a differenciálhányados

bg

dy df x = dx dx

Itt nem foglalkozunk azzal, hogy bebizonyítsuk s ( Newton szerint ) =

ds ( Leibniz szerint ) . dt

Érdekes azonban, hogy Leibniz tulajdonképpen egy zseniális tévedést követett el. A modern matematika elvetette a végtelen kicsiny mennyiségek fogalmát. A derivált függvényt d jel egyszerűen egy operátor jel, a határérték-számítás módszerével vezetik be, s így a dx amely az x változó szerinti deriválást jelenti. A fenti egyenlőség így nyilvánvaló, hiszen a d . Viszont a modern matematika, már felső vonás ugyanolyan operátorjel, mint a dx felhasználva a határérték-számítással bevezetett deriválás műveletét, a differenciál fogalmának új megközelítését adja: A 7. ábrán látható, hogy mi a különbség a Δy differencia és a dy differenciál között. A dy az ABC derékszögű háromszög függőleges befogója. Mivel az A pontba húzott érintő meredeksége y', azért dy=y'Δx. Tehát a differenciál egy kétváltozós függvény, amely függ xtől (a deriválton keresztül) és Δx-től. Ha viszont tekintjük az y=x függvényt, akkor annak deriváltja minden x-ben 1, tehát dy=dx=1·Δx=Δx. Ha ezt behelyettesítjük a differenciál általános képletébe, akkor azt kapjuk, hogy dy = y ′ ⋅ dx vagyis y ′ =

22

dy dx

tehát Leibniz végül is úgy tévedett, hogy - nem tévedett. y C

dy

Δy

A

y=f(x)

B

Δx

x

7. ábra A differenciál modern fogalma

B.) A LINEÁRIS EGYENLETRENDSZEREK ÁBRÁZOLÁSA

A matematikai közgazdaságtanban, s különösen az allokációs modellekben talán a leggyakrabban előforduló matematikai objektumok a lineáris egyenletek és egyenlőtlenségek rendszere, amelyeknek sokféle jelölése található az irodalomban. Tudjuk, hogy az egyenlőtlenségek mindig átírhatóak egyenletté, ha egy újabb változóval egészítjük ki. Például a 3x1 + 2 x 2 − 4 x 3 ≤ 6 egyenlőtlenség az u ≥ 0 változó bevezetésével átalakítható az x-ekben ekvivalens 3x1 + 2 x 2 − 4 x 3 + u = 6

egyenletre. Így tehát elegendő az egyenletrendszerek jelöléseivel foglalkoznunk. Egy általános lineáris egyenletrendszer a következőképpen írható fel: a11 x1 + a12 x 2 +... + a 1 j x j +... + a 1n x n = b1 a 21 x1 + a 22 x 2 +... + a 2 j x j +... + a 2 n x n = b 2 ... a i1 x1 + a i2 x 2 +... + a ij x j +... + a in x n = b i ... a m1x1 + a m2 x 2 +... + a mj x j +... + a mn x n = b m Mint látható, ez a felírási mód eléggé hosszadalmas. Több úton is egyszerűsíthető. A legegyszerűbb, ha középről kiemeljük az i-dik, általános egyenletet: a i1 x 1 + a i2 x 2 + ... + a ij x j + ... + a in x n = b i (i = 1,2, ...m)

A teljes Walras-modell felírása még így is elég bonyolult lenne. További, és felettébb hasznos rövidítés a szummajel (Σ) alkalmazása: n

∑a

ij

x j = b i (i = 1,2, ...m)

j=1

23

Ez a felírási mód annak, aki jól begyakorolta alkalmazását igen sok trükköt tesz lehetővé, amivel levezetések, bizonyítások leegyszerűsíthetőek. Például az alábbi egyenletrendszerek teljesen ekvivalensek egymással: n

a.)

∑a x ij

= b i (i = 1,2, ... m)

j

j=1 n

b.)

∑a

ik

x k = b i (i = 1,2, ... m)

k =1

n −1

c.)

∑a

i ( j+1)

x j+1 = b i (i = 1,2, ... m)

j= 0

n

d .) a 11x1 + ∑ a ij x j = b i (i = 1,2, ... m) j= 2

n

e.) a it x t + ∑ a ij x j = b i (i = 1,2, ... m) j=1 j≠ t

n −1

f .) a in x n + ∑ a ij x j = b i (i = 1,2, ... m) j=1

F a x I +F a x I = b GH ∑ JK GH ∑ JK n−k

g.)

n

ij

j

ij

j=1

j

i

(i = 1,2, ... m)

j= k

stb. A példákból látható, hogy a szummajel alá írt egyenlőség az úgynevezett futóindexnek, vagy indexváltozónak az első értékét adja meg, míg a szummajel tetejére elhelyezett szám a futóindex utolsó értékét rögzíti. A futóindex tetszés szerint átnevezhető. A szummajel mögül bármely tag kiemelhető, a szumma ketté vagy több részre is vágható. És így tovább ... Amennyiben a szövegből nyilvánvaló a futóindex kezdeti értéke (általában 1 vagy 0), akkor a szummajel alá szokták csupán az összegzést levezénylő futóindex nevét írni: n

∑a x ij

j

= b i (i = 1,2, ...m)

j

További lustaság és még egyértelműbb szövegkörnyezet fennforgása esetén a szummajel alja teljesen üres is maradhat. Nagy megátalkodottság szükséges hozzá, de előfordul, hogy a felső jelet is elhagyják. Az egyszerűsített felírás felsőfoka kétségtelenül a mátrixos felírási mód. Legyen

LM a MM a ... A=M MM a MM a... N

11 21

i1

m1

a 12 a 22 ... a i2 ... a m2

... ... ... ... ... ...

a1 j a2 j ... a ij ... a mj

... ... ... ... ... ...

OP PP PP PP PQ

a 1n a 2n ... ; x= a in ... a mn

24

LM x OP LM b OP MMx PP MM b PP MM x... PP; b = MM ...b PP. MM ... PP MM ... PP MNx PQ MNb PQ 1

1

2

2

j

i

n

m

Ekkor az egyenletrendszer egyszerűen az Ax=b alakot ölti. Ennek kezelését az operációkutatás keretében általában előadott lineáris algebrai bevezetések ismertetik 12 . Itt mindössze azt említjük meg, hogy a félkövér szedés helyett egyéb jelölési módokkal is találkozhatunk: a.) Ax =b b.) Ax=b c.) Ax=b d.) Ax = b e.) ⎡⎣a ij ⎤⎦ ⋅ ⎡⎣ x j ⎤⎦ = [ bi ] stb. egymással ekvivalens jelölések. Azok a könyvek, ahol a b.) jelölést alkalmazzák, a skalár számokat általában görög kisbetűkkel jelölik. Természetesen nincs akadálya annak, hogy az itt felidézett jelölési módokat keverve használják. A mátrixok transzponálását jelölik felső indexbe írt csillaggal illetve nagy T betűvel. 2. NÉHÁNY SZÓ AZ OPTIMUMOKRÓL Optimumról a racionális gazdálkodással kapcsolatban szokás beszélni. A szó maga az adott körülmények között legjobb választható megoldást, az optimális döntés pedig az optimális megoldás (optimum) választását jelenti. Sokféle optimalitási elv létezik. Tegyük fel, hogy valamilyen módon meghatározható az összes lehetséges választható megoldás halmaza. Jelöljük ezt X-szel. X a döntési halmaz. Ha ki tudjuk fejezni döntési célunkat egy függvénnyel, amely a döntési halmaz elemeihez egy (valós) számot rendel, akkor ez lesz a célfüggvény. A célfüggvény egy rendezést valósít meg a döntési halmazon, amennyiben x

y ( x,y ∈ X ) akkor és csak akkor, ha f ( x ) > f ( y ) ,

ahol f: X→R (R a valós számok halmaza) a célfüggvény. A rendezési relációt természetesen lehet bármilyen gazdasági interpretációval felruházni: x lehet „jobb“, „hasznosabb“, „előnyösebb“, „hatékonyabb“ stb., de ugyanígy lehet „rosszabb“, „kártékonyabb“, „hátrányosabb“, „hatékonytalanabb“ stb. mint y és ettől az interpretációtól függ tulajdonképpen, hogy melyik megoldást tekintjük optimálisnak. Ahhoz, hogy a célfüggvénnyel meghatározható legyen az optimális döntés, annyi kell, hogy az X a rendezés szerint korlátos legyen, vagyis legyen olyan w elem (nem feltétlenül X eleme, hanem azé az „univerzumé“, amelynek maga X a részhalmaza 13 ) amelyre w

x (vagy w ≺ x) minden x-re ( x ∈ X )

12

Lásd például Matematika üzemgazdászoknak Operációkutatás I. (szerk. Dr. Tóth Irén) 3. fejezet, vagy Krekó B. Lineáris programozás KJK Budapest, 1966 157-179. oldalak 13

Ebben az esetben fel kell tételeznünk, hogy a

rendezést ki lehet terjeszteni az „univerzumra“.

25

és az ilyen w elemek között legyen legalább egy, amely eleme X-nek. Ez a w ∈ X elem lesz az optimális döntés. Nem nehéz belátni, hogy amennyiben két ilyen elem is van, például w1 és w2, akkor f(w1)=f(w2), ami azt jelenti: a két döntés ekvivalens az optimalitás szempontjából. Az itt vázolt optimalitási elv a klasszikus szélsőérték-számításokból fejlődött ki (de nem azonos azokkal, hiszen nem mindenütt deriválható függvényekkel leírt döntési halmazok esetében - bizonyos szempontból például ilyen a lineáris programozás - a szélsőértékszámítás hagyományos módszerei nem alkalmazhatóak). Mivel a szélsőérték-számításon alapuló optimalizálási eljárások egyik legrégebbi eszközei a Lagrange-együtthatók, azért ezt az elvet Lagrange-féle optimalitási elvnek nevezik. Ennek lényege, hogy egy számértékű célfüggvény maximumát, illetve minimumát keressük a döntési halmazon. Ilyen értelemben beszélünk maximizációs és minimizációs optimumszámításról. Egészen más a helyzet, ha a célfüggvény a döntési halmaz elemeihez nem a tökéletesen rendezett valós számok valamelyikét rendeli, hanem egy csupán részben rendezett halmaz valamely elemét. 14 Tipikusan ilyen a csoportos döntések esete, amikor a csoport egy közös döntési halmaz felett hozza meg döntését, de minden csoporttagnak saját, a többiekétől valószínűleg eltérő (számértékű) célfüggvénye van. Ekkor mindenki szeretne magának Lagrange-optimumot találni, de mivel a célfüggvények különbözőek, semmi sem garantálja, hogy a döntési halmaz egyik szereplő számára optimális eleme optimális lesz a többiek számára is. Ilyen helyzet fordul elő például a Walras-Arrow-Debreu féle általános egyensúly modelljének allokációs problémáiban. A bevezető jellegű mikroökonómia kurzusokban e helyzet megoldására az úgynevezett Pareto- vagy efficiens (hatékony) optimalitási elvet szokták bevezetni. Egy csoport döntési halmazában az az elem Pareto-optimális, vagy efficiens, amelyikből bármely olyan döntésre áttérve, amely a csoport valamely tagjának célfüggvény-értékét közelíti az illető (Lagrange-)optimális célfüggvény-értékéhez (vagyis az illető a döntés következtében „jól jár“), az legalább egy másik csoporttag célfüggvényértékét eltávolítja az illető (Lagrange-)optimális célfüggvényértékétől (vagyis az illető a döntés megváltoztatása következtében „rosszabbul jár“). Rövidebben (és talán kevésbé precízen) szólva: az a megengedett döntés Pareto-optimális, amelyikből már a csoport egyik tagjának célfüggvénye („helyzete“) sem javítható anélkül, hogy legalább egy másvalakié ne romolna.

Legyen a döntésben érdekelt csoportnak n tagja. Legyen F: X→Rn a csoport „célfüggvénye“, azaz a döntési halmaz egy olyan leképezése az n elemű vektorok euklideszi terére, ahol a képvektor komponensei a csoport tagjainak a döntési halmaz adott eleméhez tartozó

14 Tökéletesen vagy lineárisan rendezett egy halmaz, amikor a rendezési relációval bármelyik két elem összehasonlítható. Részben rendezett halmazról akkor beszélünk, amikor egyes elemek a rendezési relációval nem összehasonlíthatóak. Nyilván a természetes, az egész illetve a valós számok a nagyság szerinti rendezéssel (ami megegyezik a számegyenesen való egymás után rendezéssel) tökéletesen rendezett halmazt alkotnak. Éppen innen ered a „lineáris rendezés“ elnevezés. Részben rendezett halmazt alkotnak az euklideszi tér n elemű vektorai a komponensek páronkénti nagyságszerinti összehasonlításán alapuló rendezéssel, amikor az a vektor a nagyobb, amelynek egyik komponense sem kisebb a másik megfelelő komponensénél és legalább egy nagyobb (vagyis amelyik dominálja a másikat). Ugyancsak részben rendezett a szakaszosan folytonos függvények tere a pontonkénti összehasonlítás alapján rendezve (kihagyva esetleg a szakadási pontokat). Minderről később még szó lesz.

26

egyéni célfüggvényértékei. Nevezzük továbbá félpozitívaknak az Rn azon elemeit, amelyeknek komponensei nem negatívak, de legalább egy közülük pozitív. Ekkor x∈X akkor és csak akkor Pareto-optimális döntés, ha nincs olyan y∈X, amelyre F(y)-F(x) félpozitív volna. Röviden jelölve: nincs olyan y, amelyre F(y)»F(x) 15 . A Pareto-optimalitás elve igen népszerű a gazdasági döntések (és ezeken belül az allokációk) elméleteiben, de nem mindig kielégítő. Tegyük fel, hogy a célfüggvények a csoport tagjainak pénzben kifejezett hasznát jelentik, és természetesen maximalizálásuk a cél. Ha most minden döntés amely a csoport egyik tagjának a célfüggvényét növeli, az legalább egy másik tag célfüggvényét csökkenti, akkor a döntési halmaz kiindulópontja természetesen Pareto-optimális, ahonnan a Paretooptimalitási elv szerint már sehova sem lehet elmozdulni. Ám miért ne lenne érdemes egy olyan döntést hozni, amely az egyik szereplőnek annyi pénztöbbletet okoz, amelyből az képes lenne a veszteséget szenvedőt kárpótolni, és még valami maradna is? A kárpótlás lehetőségéről van szó, nem a tényéről. Ha kötelező kárpótolni, akkor a valóságos célfüggvényekbe a kárpótlást is bele kell kalkulálni (az adottat és a kapottat egyaránt), és akkor a módosított célfüggvények szerint a kiindulópont nem volt Pareto-optimális. N. Káldor szerint optimális döntésről beszélünk akkor, ha a csoport tagjainak célfüggvényértékei azonos természetűek, lehetőség van a célfüggvényérték egy részének átruházására és nincs olyan újabb döntésre lehetőség, amely úgy javítaná a csoport legalább egy tagjának célfüggvényértékét, hogy azok akik nyernének a döntésen, képesek lennének nyereségük egy valódi részének átengedésével kompenzálni a vesztesek veszteségeit. A Káldor-kritérium - szemben a Pareto-kritériummal - elsősorban nem akkor érdekes, amikor beáll a Káldor-optimum, hanem amikor egy döntés még javítható. Ha egy döntés nem Pareto-optimális, ezért áttérünk egy hatékonyabb pontba (vagyis az új döntés némelyek helyzetét javította, miközben másokét nem rontotta) akkor nyilvánvaló, hogy a visszatérés a régi döntéshez Pareto szerint nem lesz hatékony lépés (akiknek javult a helyzetük, azoké most romlik, akiké nem változott - nem javult, de nem is romlott - azoké most sem változik). Tegyük fel, egy társasház egyik lakásához sem tartozik külső TV antenna. Döntést hoznak, hogy aki igényli, annak bevezetik a helyi kábel TV-t. Ha a kábelen vezetett műsor a szobaantennák nyújtotta vételi lehetőséget nem zavarja, akkor ez Pareto szerint hatékonyságjavító döntés volt, hiszen a kábelt bevezetők jobb vételhez jutottak, a többiek helyzete nem változott (a kábel költségeit hagyjuk figyelmen kívül). Nyilván a visszalépés az előző állapothoz (a kábel kikapcsolása) rontja a hatékonyságot. Nem ugyanez a helyzet a Káldor-féle optimalitási elv mellett. Itt előfordulhat, hogy áttérve egy Káldor szerint hatékonyabb helyzetbe, az onnan való visszalépés is Káldor szerint hatékony lesz. Nézzünk erre is egy példát. Egy másik társasház tagjainak egy része műholdvevő parabolaantennát szerel fel, hogy idegen nyelveket tanuljon, megspórolva a nyelviskola költségeket, amelyek 150.000 Ft-ot tennének ki. Itt a parabola erősen rontja a szobaantennák vételét. A kárt a szobaantennások 60.000 Ft-ra becsülik, míg a parabolát felszerelők 100.000 15

Itt a „»“ jel azt jelenti két vektor között, hogy az első egyetlen komponense sem kisebb a második megfelelő komponenseinél, de legalább egy nagyobb, vagyis ha a»b, akkor minden ai≥bi (i=1,2, ... n), de legalább egy i-re ai>bi. Nyilván, ha a félpozitív, akkor a»0.

27

Ft haszonra számítanak a felszerelés 50.000 Ft-os költsége felett, tehát a parabola felszerelése Káldor szerint hatékony, hiszen a parabolát felszerelők nyeresége a vesztesek kárpótlása után is 40.000 Ft lenne. A felszerelés után kiderül, hogy a parabolán fogható műsorokat mind kódolták, ezért egyáltalán nem alkalmasak olcsó nyelvtanulásra, viszont a parabola tényleg erősen rontja a szobaantennák működését. A parabolaantenna leszerelése ezért csak 50.000 Ft veszteséget jelent a felszerelőknek, míg a szobaantennások visszanyerik mind a 60.000 Ft veszteségüket 16 . Tehát a visszalépés is Káldor szerint hatékony. T. Scitovsky szerint egy döntés akkor hatékony, ha Káldor szerint hatékony, de viszszacsinálása nem az. Mind a Káldor féle, mind a javított Scitovsky féle optimalitási elv közös hibája, hogy egyáltalán nem demokratikus. Ha egy döntés a gazdagoknak nagy hasznot hoz, a szegényeknek kis kárt okozva, akkor ez mindkettőjük szerint hatékony döntés, feltéve, hogy a visszacsinálása nem okoz nagyobb hasznot a szegényeknek, mint amekkora kárt a gazdagoknak. A Pareto-elvvel pedig az a baj, hogy egyáltalán nem igazságos, vagyis másképpen, mint a Káldor-Scitovsky elv, de szintén nem demokratikus. Hiszen ha egy két tagú csoportban minden jószágot az első taghoz allokáltak, a másik nem kapott semmit, akkor ez egy Pareto-optimális döntés, hiszen a javak legkisebb újraallokálása úgy javítaná a második helyzetét, hogy rontaná az elsőjét. A. Bergson és mások is úgy gondolták, hogy a legjobb megoldás a hatékony csoportdöntések kialakítására az lenne, ha sikerülne megszerkeszteni a csoport közös Lagrangetípusú célfüggvényét a csoport tagjainak preferenciái alapján. Ilyen célfüggvény alkotható például a csoport megszavaztatása útján. Mindössze megfelelő, demokratikus szavazási eljárást kellene kidolgozni. K.J. Arrow (az általános egyensúly modern elméletének társszerzője) megpróbált egy ilyen eljárást a neoklasszikus mikroökonómia eszközrendszerével (preferenciarendezés) kialakítani. Ennek lényege a következő:

Tegyük fel, hogy egy n tagú csoport minden tagja rendelkezik egy-egy megfelelő preferenciarendezéssel a döntési halmaz felett, azaz a Pi (i=1,2, ... n) preferenciarendezések eleget tesznek a mikroökonómiából ismert axiómáknak: P1. Teljesség. Ha x,y∈X akkor vagy xPiy, vagy yPix, vagy x és y közömbösek. P2. Reflexivitás. Minden x∈X esetén x közömbös önmagával. P3. Tranzitivitás. Ha x,y,z∈X és xPiy valamint yPiz akkor xPiz 17 Ha bevezetjük az Ri relációt, ahol xRiy, ha vagy xPiy vagy x és y közömbösek, akkor egyszerűbben is felírhatóak az axiómák: P1. Teljesség. Ha x,y∈X akkor vagy xRiy, vagy yRix. 16

Hogy a remélt nyereség nem lép fel, az csak az antenna felszerelése után derülhetett ki!

17

A mikroökonómia tankönyvekben a preferenciaelmélet e három axiómáján kívül még további kettő is szerepelni szokott: P4. A dominancia elve P5. Az átlag preferálásának elve Ezek az axiómák azonban csak a döntések egy speciális csoportjánál, a termékkosaras fogyasztási típusú döntéseknél értelmezhetőek. Arrow tételének bizonyításánál nincs rájuk szükség.

28

P2. Reflexivitás. Minden x∈X esetén xRix. P3. Tranzitivitás. Ha x,y,z∈X és xRiy valamint yRiz akkor xRiz Legyen R az összes lehetséges P1.-P3. axiómáknak eleget tevő reláció halmaza. Legyen továbbá D a csoport összes lehetséges {Ri}i=1,2, ... n preferenciarendezéshalmazainak (preferenciarendszereinek) halmaza, azaz D tartalmazza a csoport minden lehetséges ízlésvilágát. Ha valakinek a csoportból megváltozik a preferenciája, az új preferenciarendszer szintén eleme lesz a D-nek. Nevezzük ezután a kollektív preferencia függvényének az F: D→R leképezést, amely a preferenciarendszerekhez egy-egy kollektív preferenciarendezést rendel. Arrow a következő - nagyon természetesnek tűnő - követelményeket állította fel: 1. Az F-nek az értelmezési tartománya tartalmazza az összes lehetséges preferenciarendszert, azaz bármilyen is az ízlése a csoport tagjainak, és bárhogy is változik az, mindig létezik kollektív preferenciarendezés. Vagyis a szavazást mindig meg lehet tartani. 2. Ha x,y∈X és minden i-re (i=1,2, ... n) xRiy, akkor xRy, ahol R=F({Ri}), azaz az egybehangzó vélemények érvényesülnek. Ha egyenként mindenki „Jézust kiált“, akkor a csoport nem „zúghat Barabást“. 3. Ha x,y∈X és minden i-re (i=1,2, ... n) xRiy akkor és csak akkor ekvivalens x R ′i y-nal, ha xRy ekvivalens x R ′ y-nal, ahol természetesen R=F({Ri}) és R ′ =F({ R ′i }). Ez a matematikailag körülményes feltétel azt fejezi ki, hogy x és y megítélése nem függhet a többi döntési alternatíva megítélésétől. Valóban, ha ez így van, akkor például lehetséges, hogy valamely z∈X esetében előbb xRiz, de azután z R ′i x, ám ennek ellenére, ha előbb xRiy és utána x R ′i y akkor elvárható, hogy a kollektív preferencia is így alakuljon (előbb xRy, majd x R ′ y), és persze fordítva is. Még világosabban. Ha az X halmazon kialakult az egyéni preferenciákból egy közösségi preferencia, akkor ez nem változhat meg attól, hogy felveszünk X-be még egy döntési lehetőséget - egy újonnan fellépő döntési lehetőség a korábban megvolt alternatívák egymáshoz viszonyított értékelésén nem változtathat. Ha még így sem elég világos, íme egy egyszerű példa. Egy részvénytársaság igazgatótanácsa vezérigazgatót választ. Három jelölt van: Kiss, Nagy és Kovács. Tegyük fel, hogy egy Arrow feltételeinek eleget tevő szavazási eljárásban a következő sorrend alakult ki: 1. Kovács 2. Kiss 3. Nagy Ha most ugyanez az igazgatótanács ugyanezen jelöltekre szavazna, ugyanazon információk alapján, de lenne egy negyedik jelölt is, Szabó, akkor elvárható, hogy a döntés a következők közül kerüljön ki: 1. Kovács 2. Kiss 3. Nagy 4. Szabó

1. Kovács 2. Kiss 3. Szabó 4. Nagy

1. Kovács 2. Szabó 3. Kiss 4. Nagy

De ki kell zárni például a 29

1 Szabó 2. Kovács 3. Kiss 4. Nagy

1. Nagy 2. Kiss 3. Kovács 4. Szabó lehetőségét, hiszen az azt jelentené, hogy Szabó harcba szállása megváltoztatta Kovács, Kiss és Nagy egymáshoz viszonyított értékelését és Arrow 3. feltétele pedig éppen ezt nem engedi meg. 4. Nincs olyan i, amelyre igaz lenne, hogy minden {Ri}∈D esetében F({Ri})= Ri azaz a csoportban nincs diktátor. Ugyanis ennek a feltételnek a tagadása azt jelentené, hogy bárhogyan is döntene az i-dik tag, a többiek véleményétől függetlenül az ő preferenciái egyben a csoport preferenciái is lennének. Tehát az i-dik lenne a csoport diktátora, az ő döntései lennének automatikusan a csoport döntései. Néhány dolgot azonnal megállapíthatunk. Először is, ha megengednénk a diktátor létezését, akkor evidens módon teljesülne az első három feltétel. Valóban, 1. nyilvánvalóan teljesülne, mert minden lehetséges preferenciarendszer mellett értelmezve lenne a kollektív preferencia, hiszen az azonos lenne a preferenciarendszer egyik elemével, nevezetesen a diktátor preferenciájával. De érvényes lenne a 2. feltétel is, hiszen, ha x-et mindenki preferálja y-nal szemben, akkor köztük a diktátor is, tehát a kollektív preferencia nem ellenkezne az egybehangzó véleménnyel. (Ez azt a meglepő tényt jelenti, hogy egy diktátor csak akkor tudja konzekvensen semmibe venni az alattvalói véleményét, ha néha a sajátját is semmibe veszi.) Végül a 3. feltétel is evidensen teljesül, mert minden i-re (i=1,2, ... n) xRiy akkor és csak akkor ekvivalens x R ′i y-nal, ha bármelyik i-re is xRiy ekvivalens x R ′i y-nal, tehát a diktátor i-jére is, viszont nyilván xRiy akkor és csak akkor ekvivalens x R ′i y-nal, ha xRiy ekvivalens x R ′i y-nal, ami utóbbi „összefüggés“ itt már a diktált kollektív preferenciára vonatkozik. Második megjegyzésünk, hogy a rendkívül természetesnek tűnő kikötések nem is olyan természetesek. Az egyik legelterjedtebb szavazási rend a többségi szavazás: az az alternatíva kerül előbbre, amelyik több szavazatot kap. Vajon kielégíti ez a rend Arrow feltételeit, ha nincs diktátor? Tekintsük az előbbi példát. Véletlenül Kiss, Nagy és Kovács maguk alkotják az igazgatótanácsot, és mint ismeretes, „minden szentnek magafelé hajlik a keze“. Kiss szerint a sorrend: Nagy szerint a sorrend: Kovács szerint a sorrend:

1. Kiss; 2. Nagy; 3. Kovács 1. Nagy; 2. Kovács; 3. Kiss 1. Kovács; 2. Kiss; 3. Nagy

Valaki azt mondhatja, hogy ez meglehetősen kimódolt preferenciarendszer. Semmi baj, az 1. feltétel szerint ehhez is kell, hogy tartozzon egy érvényes kollektív preferencia. A többségi szavazás alapján Kiss 2:1 arányban jobb Nagynál, Nagy 2:1 arányban jobb Kovácsnál és végül Kovács 2:1 arányban jobb Kissnél. A többségi szavazás alkotta kollektív preferencia tehát megsérti a P3. axiómát és így ∉R, azaz a többségi szavazás nem felel meg

30

Arrow 1. feltételének, mivel lehetséges olyan preferenciarendszer, amely mellett nem lehet érvényes szavazást tartani. Helyes, akkor alkalmazzunk egy másik közkedvelt zsürizési módszert. A zsüritagok minden jelöltnek adjanak annyi (hiba)pontot, amennyi a helyezésük. A kollektív sorrendet a összegzett pontok adják, növekvő sorrendben. Ez a súlyozásos módszer. Hogy ne legyen hiba, hívják meg Szabót is a választásra jelöltnek. Persze eddigi véleményét mindenki fenntartja. Kiss szerint a sorrend: Nagy szerint a sorrend: Kovács szerint a sorrend:

1. Kiss; 2. Szabó; 3. Nagy; 4. Kovács 1. Nagy; 2. Kovács; 3. Kiss; 4. Szabó 1. Kovács; 2. Kiss; 3. Szabó; 4. Nagy

Az eredmény tehát: 1. 2.-3. 2.-3. 4.

Kiss Nagy Kovács Szabó

(6) (7) (7) (9)

Kiderült, hogy formai hibák miatt nem vették figyelembe Szakács jelölését. A szavazást meg kell ismételni, de most már az 5 jelölttel. Megtörtént. A korábbi jelöltek iránt a vélemények most sem változtak: Kiss szerint a sorrend: 1. Kiss; 2. Szabó; 3. Nagy; 4. Kovács; 5. Szakács Nagy szerint a sorrend: 1. Nagy; 2. Kovács; 3. Szakács; 4. Kiss; 5. Szabó Kovács szerint a sorrend: 1. Kovács; 2. Szakács; 3. Kiss; 4. Szabó; 5. Nagy Mindennek ellenére az eredmény: 1. 2. 3. 4. 5.

Kovács (7) Kiss (8) Nagy (9) Szakács (10) Szabó (11)

Vagyis az esélytelen Szakács beszállása megváltoztatta a sorrendet - Kiss és Kovács között. Ezúttal tehát a 3. feltétel nem teljesült. Most már rendet kell végre teremteni. A sportversenyekhez hasonlóan ezért mindenki listájáról törlik az első és az utolsó helyezettet. Ez is egy gyakori szavazási rend, a szélsőségektől korrigált súlyozás módszere. Az eredmény: 1. 2. 3.-4. 3.-4. 5.

Nagy (5) Szakács (6) Szabó (7) Kovács (7) Kiss (8)

Az eredmény igazán megdöbbentő. Nem az a legmegdöbbentőbb, hogy Kiss favoritból immár utolsó lett, hiszen most nem az előző eredményekkel kell ezt a listát egybevetni. A megdöbbentő az, hogy Kisst mindenki jobbnak ítélte Szabónál, Kovácsot mindenki többre tartotta Szakácsnál és íme „mindenki egyenként Jézust kiáltott, s a tömeg mégis Barabást zúgott“. Vagyis ezzel a szavazási renddel a 2. feltételt nem tartják be. Mindezek után már nem csodálkozhatunk Arrow híres-hírhedt „lehetetlenségi tételén“: 31

TÉTEL

(Arrow) Egy csoport kollektív preferenciarendezése akkor és csak akkor tesz eleget egyszerre Arrow valamennyi (1.-3.) feltételének, ha a csoportban diktátor van, vagyis ha nem teljesül a 4. feltétel. Másképpen megfogalmazva: (Arrow) Nincs olyan kollektív preferenciarendezés, amely egyszerre tesz eleget Arow valamennyi (1.-4.) feltételének.

TÉTEL

A tétel egyik felét már igazoltuk (ha van diktátor, akkor az 1.-3. feltételek teljesülnek), a másik - nehezebbik - felének bizonyítása meghaladja ennek az előadásnak a kereteit, ezért az érdeklődő olvasót az irodalomra utaljuk. 18

18

A tétel bizonyítása megtalálható például Zalai Ernő „Bevezetés a matematikai közgazdaságtanba“ KJK, Budapest, 1989. 150-155. oldalak. Magának a tételnek az ismertetéséhez is felhasználtuk ezt a könyvet, azonban a 3. feltétel megfogalmazását máshonnan (I. Ekeland „Éléments D' Économie Mathematique“ Paris, 1979) vettük, ahol egyébként szintén szerepel a bizonyítás.

32

EGYSZERŰ ALLOKÁCIÓS MODELLEK (HARMADIK ELŐADÁS) 1. NÉHÁNY SZÓ A LINEÁRIS PROGRAMOZÁSRÓL - A DUALITÁS ÉS AZ ERŐFORRÁSOK GAZDASÁGI ÉRTÉKELÉSE A.) A DUALITÁS ELVE

Az előző előadásban már érintettük, hogy az optimalitás fogalma szoros kapcsolatban van a hatékonysággal, azaz az eredmény és az eléréséhez szükséges ráfordítás viszonyával. O. Lange fontosnak tartotta szembeszállni azzal a köznapi elképzeléssel, hogy az optimális hatékonyság a legnagyobb eredmény elérését jelenti a legkisebb ráfordítások mellett. Ez az elképzelés ugyanis tulajdonképpen értelmezhetetlen. A legkisebb ráfordítás a ráfordítás teljes hiánya, amely mellett az elérhető legnagyobb eredmény a semmi. Másrészt viszont a legnagyobb eredmény a „végtelen“ eredmény, vagyis nincs olyan eredmény, aminél ne lehetne nagyobb eredményt elérni, feltéve persze, hogy nem sajnáljuk a „végtelen“ ráfordítást, azaz ha felkészülünk arra, hogy nincs olyan ráfordítás, aminél ne kellene többet rászánnunk. Nyilván a „semmiből semmit“ nem lehet ugyanaz, mint a „végtelenből végtelent“, de mégis a fenti elképzelésnek mind a kettő egyaránt megfeleltethető. Vagyis logikai ellentmondásba ütköztünk. Lange szerint a hibás köznapi elképzelés két hatékonysági elv helytelen egybemosásának eredménye: 1. A maximális eredmény elve Egy gazdasági döntés akkor optimális, ha az a d o t t ráfordítások mellett az elérhető legnagyobb eredményt adja.

2. A minimális ráfordítás elve Egy gazdasági döntés akkor optimális ha egy a d o t t eredményt a lehetséges legkisebb ráfordítással éri el.

Valószínűleg maga Lange is téved, amikor azt állítja, hogy ez a két elv ekvivalens egymással. Hiszen általában a két elv két eltérő feladattípust jelent. Általában nem mindegy, hogy az eredményt rögzítjük és megpróbáljuk lefaragni a ráfordításokat, vagy pedig csak adott erőforrásaink vannak és azokból igyekezünk maximális eredményt kihozni. Az allokációs feladatok esetében azonban igen gyakran érvényesül a dualitás elve: 3. A dualitás elve Ha rögzítünk egy X ráfordítást és a maximális eredmény elve alapján elérjük az Y optimális (maximális) eredményt, akkor ezt a maximális Y eredményt rögzítve a minimális ráfordítás elve alapján éppen az X lesz az optimális (minimális) ráfordítás.

A két döntési elv akkor és csak akkor ekvivalensek, ha a dualitás szimmetrikus, vagyis ha a 3.-ból következik 3'. A dualitás (szimmetrikus) elve

33

Ha rögzítünk egy Y eredményt és a minimális ráfordítás elve alapján azt elérjük X optimális (minimális) ráfordítás révén, akkor ezt a minimális X ráfordítást rögzítve a maximális eredmény elve alapján éppen Y lesz az optimális (maximális) eredmény.

A szimmetrikus dualitás elve igen jól érvényesül a lineáris programozás alapfeladata esetén. B.) DUALITÁS A LINEÁRIS PROGRAMOZÁSBAN

A lineáris programozás alapfeladatát például a következő módon interpretálhatjuk, mint allokációs feladatot. Álljon rendelkezésre m erőforrás egyenként bi (i=1,2,...,m) készlettel. Ezeknek az erőforrásoknak a felhasználásával (allokálásával) n különböző jószág állítható elő. Az egyes jószágoknak a piaci ára pj (j=1,2,...,n). A rendelkezésünkre álló technológia alapján egy egységnyi j-ik termék előállításához aij i-dik erőforrásra van szükség. Mivel az erőforrásokat már beszereztük, ezért a ráfordításaink adottak. Alkalmazva a maximális eredmény elvét az adott ráfordításokból a maximális árbevételt (s egyben maximális profitot) hozó eredményt kell elérnünk. Ezt a következő lineáris programozási (LP) feladattal tervezhetjük meg:

p T x → max Ax ≤ b x≥0 ahol természetesen xj (j=1,2,...,n) a j-ik termék megtermelendő mennyiségét jelenti. A célfüggvény az árbevétel maximalizálását jelenti. A peremfeltételek első csoportja azt írja elő, hogy egyik erőforrásból sem használhatunk fel többet a rendelkezésre álló készleteknél, a második csoport azt a majdnem evidens feltételt írja elő, hogy nem termelhető negatív mennyiségű jószág. Ezt a feladatot nevezzük primál feladatnak. Azonban ugyanezekkel a technológiai koefficiensekkel, ár- és készletadatokkal egy másik feladat is felírható. Legyen λi az i-dik erőforrás árnyékára, azaz az a feláldozott haszon, amibe ennek az erőforrásnak egy egysége kerül 19 . Így a teljes feláldozott haszon λTb . Ezt mint ráfordítást kell minimalizálni, ha adott - egységnyi - eredményt akarunk elérni. Mivel az aij technológiai koefficiensek meghatározzák, hogy egységnyi j-ik termék előállításához hány egységnyi i-dik erőforrás szükséges, kiszámítható egy egységnyi termék teljes feláldozott haszna. Ez az összes fajtájú termékre mátrixalakban λT A lesz. A neoklasszikus mikroökonómiából tudjuk, hogy a konkurencia miatt a hozam nem lehet nagyobb a teljes költségnél, tehát felírható egy LP feladat, amely egyfelől kifejezi a legkisebb ráfordítás elvét, minimizálva a feláldozott hasznot, másfelől peremfeltételként tükrözi a konkurencia profitkorlátozó hatását. Természetesen az árnyékárak sem lehetnek negatívak: λTb → min λT A ≥ p T λT ≥ 0

Ez a feladat lesz a duális feladat.

19

Ennek korrekt értelmezésére még visszatérünk.

34

Egy LP feladat esetében a peremfeltételek által behatárolt konvex poliéder a feladat döntési halmaza, s ha e halmaz nem üres, akkor elemei a feladat megengedett vektorai. Az LP elméletéből levezethető, hogy ez a két feladat a fenti értelemben szimmetrikus duálisa egymásnak. Érvényesek a következő (dualitási) tételek: I. dualitási tétel Ha x vektor a primál feladat megengedett vektora és λ vektor a duális feladat megengedett vektora léteznek, akkor p T x ≤ λTb

II. dualitási tétel Ha x vektor a primál feladat megengedett vektora és λ vektor a duális feladat megengedett vektora léteznek, és p T x = λTb , akkor és csak akkor x a primál, λ a duális feladat optimális megoldása.

III. dualitási tétel Amennyiben a duális feladatok közül az egyiknek van optimális megoldása, akkor a másiknak is van és a két célfüggvény optimális értéke egyenlő.

IV. dualitási tétel Ha mindkét duális feladatnak van megengedett vektora, akkor és csak akkor van mind a két feladatnak optimális megoldása.

V.

dualitási tétel Ha a maximizációs (minimizációs) feladat döntési halmaza nem üres és felülről (alulról) korlátos, akkor és csak akkor a duális feladatpárosnak van optimális megoldása.

VI. dualitási tétel Ha a duális feladatok közül az egyiknek van megengedett vektora, de a célfügvénye a döntési halmazon a megfelelő irányban nem korlátos, akkor a másik feladatnak nincs megengedett vektora.

VII. dualitási tétel Ha a duális feladatoknak van optimális megoldásuk, akkor az egyik feladat optimális vektorával egyenlőtlenségként teljesülő (nem efficiens) peremfeltételének indexéhez tartozó komponens a másik feladat optimális vektorában pontosan 0.

Itt kell megjegyezni, hogy a VII. dualitási tétel állítása általában nem megfordítható, azaz az egyik feladat optimális megoldása 0 komponensének az indexen keresztül a másik feladatban megfeleltetett peremfeltétel nem feltétlenül teljesül egyenlőtlenségként. Amennyiben a 0 komponensnek efficiens peremfeltétel felel meg a másik feladatban, akkor az a feladat degenerált. Ezzel kapcsolatos a

VIII. dualitási tétel Egy LP feladatnak akkor és csak akkor van több optimális megoldása 20 , ha a duálisa degenerált.

A dualitási tételeknek, vagy azok ekvivalens változatainak bizonyításai szinte minden lineáris programozással foglalkozó tankönyvben benne vannak 21 .

20

Természetesen a több megoldáshoz ugyanaz a célfüggvényérték tartozik.

35

C.) AZ ÁRNYÉKÁRAK KÖZGAZDASÁGTANI INTERPRETÁCIÓJA

A dualitási tételek segítségével megadható a duális változók (az árnyékárak) korrekt közgazdasági interpretációja. Egyes részletek mellőzésével ismertetjük ezt a gondolatmenetet. Nem nehéz belátni, hogy a primál feladat célfüggvényének maximuma megváltozhat, ha bármelyik erőforrás készlete megváltozik. Tegyük fel, hogy az előbb tárgyalt primál LP feladatban az első erőforrás 22 mennyiségét némileg, Δ>0 mennyiséggel megnöveljük. Ekkor az erőforrás-vektor a következő lesz (hullámvonallal a változatlanul maradt részeket jelöljük): ⎡ b1 + Δ ⎤ bˆ = ⎢ ⎥ ⎣b ⎦

Ennek megfelelően az LP primál feladat: p T x → max ⎡a1T ⎤ ⎡ b1 + Δ ⎤ ⎢ ⎥⋅x ≤ ⎢ ⎥ ⎣b ⎦ ⎣⎢ A ⎦⎥ x≥0 A duális feladat:

( b1 + Δ ) ⋅ λ1 + λ Tb = Δ ⋅ λ1 + λ Tb → min ⎡a T ⎤ ⎡⎣λ1 , λ T ⎤⎦ ⋅ ⎢ 1 ⎥ = λ T A ≥ p T ⎣⎢ A ⎦⎥ λ≥0

Azt sem nehéz belátni, hogy a módosítás előtti optimális vektorok az új feladatokban legalább is megengedett vektorok lesznek, hiszen a duális feladat peremfeltétel-rendszere nem változott, a primál feladat új döntési halmaza viszont teljes egészében tartalmazza a régit. Vagyis a módosított feladatoknak van optimális megoldásuk (IV. tétel). Legyen ez a primál feladat esetében x', a duál feladat esetében λ'. A II. tétel szerint:

p T x′ = Δ ⋅ λ1′ + λ′T b Tekintsük a következő függvényt:

bg

n

s

F b = max p T x Ax ≤ b , x ≥ 0 .

Ekkor

()

ΔF ( b ) = F bˆ − F ( b ) = Δλ1 + λ ′T b − λ T b . Innen 21 Lásd például Krekó B. Lineáris programozás KJK Budapest 1966 305-311 oldalak, illetve részben Matematika üzemgazdászoknak Operációkutatás II. (szerk. Csernyák L.) 19-26. oldalak. 22

Ez egyáltalán nem megy az általánosság rovására, hiszen az erőforrások és velük együtt a peremfeltételek átcsoportosítása a feladat megoldása szempontjából közömbös.

36

ΔF ( b ) λ ′T b − λ T b = λ1 − Δ Δ Könnyen ellenőrizhető (például geometriai megfontolásokkal), hogy ha Δ→0, akkor a jobboldali tört is nulla lesz (a számláló egy elég kicsiny, de még pozitív Δ esetén már nullázódik), tehát

ΔF ( b ) ∂F ( b ) = Δ→ 0 Δ ∂b1

λ1 = lim

Ez minden további nélkül általánosítható (lásd a 22 lábjegyzetet) a duális feladat optimális megoldásának valamennyi komponensére: λi =

bg

∂F b ∂b i

Az F függvény a maximális árbevétel függvénye, tehát a parciális deriváltja az i-dik termelési tényező tényező-határárbevétele (MRP). A mikroökonómiából ismert, hogy profitmaximum esetén a tényező-határárbevétel egyenlő a tényező-határköltséggel (MFC) mely utóbbi profitmaximum esetén egyenlő a tényező árával. Mivel feltételezhetjük, hogy a b vektorral megjelenített készleteket be kellett szerezni, és a termelésnek ezen kívül nincs költsége, azért elfogadható, hogy a primál feladat optimális megoldása nem csak az árbevételt, de a profitot (árbevétel-költség) is maximizálja. Így a duális feladat optimális megoldásául szolgáló λ vektor valóban az erőforrások értékelését jelenti 23 . Érdekes megjegyezni, hogy a VII. tétel szerint a nem degenerált feladatban a nem hatékonyan kihasznált erőforrás árnyékára 0. Ez nem azt jelenti, hogy az adott erőforrást ingyen lehet beszerezni, hanem azt, hogy kis mértékű pótlólagos beszerzésére semmit nem érdemes költeni, hiszen határárbevétele 0. Ez arra is felhívja a figyelmet, hogy az „árnyékárak“ általában nem a beszerzési árak, hanem azok az árak, amiket egy-egy pótlólagos erőforrás-egységért még érdemes fizetni. Ha úgy tetszik, ezek az „ajánlott rezervációs árak“. Ha a piaci ár ennél nagyobb, akkor nem szabad az adott erőforrást növelni, ha kisebb akkor bátran növelhetünk. Természetesen egy tökéletesen versenyző piacon ez olyan mozgásokat indukál, amely az „árnyékárakat“ a valóságos piaci árak árcentrumává változtatja. Ennek taglalása azonban túl mutat ennek az előadásnak a keretein.

23

Az olvasó itt könnyen azt gondolhatja, hogy egy hibás körben mozgunk, hiszen az előző pontban a duális változókat éppen úgy határoztuk meg, mint az erőforrások „árnyékárát“, „feláldozott hasznát“. Valójában nincs szó hibás körről, hiszen a duális feladat csupán egy alkalmasan megválasztott matematikai konstrukció, amit meghatározott szabályok szerint a primál feladat adataiból hoztunk létre. Az előző pontban a közgazdasági interpretációt csupán megelőlegeztük, hogy bemutathassunk egy példát a szimmetrikus dualitás létezésére. A fenti gondolatsor, a mellőzőtt részletekkel együtt, tisztán matematikai levezetéseket tartalmaz és a λ közgazdaságtani értelmezése kizárólag a primál feladat közgazdasági premisszáitól függ.

37

2. EGY JELLEGZETES ALLOKÁCIÓS LP FELADAT: KANTOROVICS GÉPTERHELÉSI FELADATA A.) A FELADAT

Mint azt a történeti ismertetésben említettük, L.V. Kantorovics egy bútoripari alapanyaggyár, a „Фанерный трест“ (Funér-tröszt) termelés-optimalizálására kapott megbízást, és ennek teljesítése során dolgozta ki az LP első feladat-típusát, az úgynevezett „gépterhelési feladatot“. Kantorovics 1939-es publikációjában 24 ezt „A“ feladatnak nevezte, tekintettel arra, hogy mindjárt kidolgozta a feladat általánosításait is, amelyek a „B“ („Б“) és a „C“ („В“) jelzést kapták. Az alábbiakban csupán az „A“ típusú feladattal fogunk foglalkozni. A feladat a következő. Adva van n darab, nem feltétlenül különböző gép. Ezeken m darab, nem feltétlenül különböző alkatrészt lehet gyártani, amely alkatrészek egy készgyártmány összeszereléséhez szükségesek. Minden alkatrészből pontosan egy van a késztermékben. A j-ik (j=1,2,...,n) gépen egységnyi idő alatt az i-dik (i=1,2,...,m) alkatrészből aij mennyiség készíthető. Keressük azt az X=[xij] terhelési tervet, amelyben xij a j-ik gépen az idik alkatrész előállítására fordított időhányad, és maximizálja az egységnyi idő alatt komplekten kibocsátott késztermék (komplett) számát. Természetesen másféle interpretáció is lehetséges. Például, adva van n darab, nem feltétlenül különböző, katonai szállítóeszköz. Ezeken lehet szállítani embert, löveget, muníciót, élelmiszert stb., összesen m - nem feltétlenül különböző - objektumot, amelyek együttesen alkotnak egy komplett lőállást. A jik szállítóeszközön a megadott idő alatt aij mennyiségű (egyszerre csak egyféle) i-dik objektum szállítható a hadtáp területről a hadműveleti területre. Keressük azt az X=[xij] szállítási tervet, amelyikkel a kitűzött idő alatt a hadműveleti területen a legnagyobb számú komplett lőállás létesíthető. Természetesen xij az adott időből a j-ik eszközön szállított i-dik objektum szállítására fordított időhányad 25 . Kantorovics 1939-es dolgozatában több ilyen több ilyen konkretizált interpretációt is felsorol. Mielőtt tovább mennénk, tegyünk egy logikusnak tűnő megszorítást. Mivel sem az olyan gépnek, amin nem termelnek semmit, sem az olyan alkatrésznek, amelyet semmilyen gépen nem termelnek nem sok értelme van, azért nem túl erős megkötés feltételezni, hogy az A mátrix oszlop- és sorvektorai egyenként félpozitívak, amit úgy is mondhatunk röviden, hogy az A mátrix félpozitív. Tovább menve, azt is feltehetjük, hogy az A mátrix pozitív (minden eleme pozitív), ugyanis esetleges 0 értékű elemei helyére tehetünk egy-egy igen kicsiny η segédváltozót, amely bármely, a számítások menetében előforduló számnál kisebb, bármely a,b>0 számokra 1.) ha a
24 Канторович Л. В. Математические методы организации и планирования производства, ЛГУ, Ленинград 1939. Újra kiadva egy gyüjteményes kötetben: Применение математики в экономических исследованиях Соцэкгиз Москва 1959. (A könyv magyarul is megjelent 1961-ben a KJK-nál) 25

Elnézést kérünk a katonai szakértőktől, ha a feladat ilyen megfogalmazása nem eléggé szakszerű.

38

z → max 2. Az X mátrix definíciójából következik, hogy oszlopvektorainak összege (i szerint) mindig 1. Tehát:

XT 1 ≤ 1 ahol 1 a csupa egyesekből álló úgynevezett összegző vektor. Természetesen a két összegző vektor nem egyforma, hiszen a baloldalon állónak m eleme van, míg a jobb oldalinak n. Ez azonban nyilvánvaló, nem szükséges tehát jelölni. Ez a feltétel az egységnyi idő feltétele. 3. Legyen A°X=[aijxij]m*n. Ekkor az egyes alkatrészek megtermelt mennyiségét az (A°X)1 szorzatvektor komponensei mutatják. Mivel a komplettek száma a „dongaelv“ 26 alapján e vektor legkisebb elemével egyenlő, azért

b

g

z1 − A oX 1 ≤ 0 Nyilván az a maximális z szám, amelyre ez a feltétel igaz, egyben a (A°X)1 vektor minimális komponense is, tehát ez a feltétel - a célfüggvény figyelembevételével - a komplettezés feltétele, amit úgy is felírhattunk volna, hogy n

z = min ∑ a ij ⋅ x ij i

j=1

ez a felírás azonban elfedné, hogy itt valójában LP feladattal van dolgunk. 4.

Végül csatoljuk a nemnegativitás feltételét is: z ≥ 0, X ≥ 0 A teljes feladat tehát:

U| X 1 ≤ 1| V bA g z1 − b A oXg1 ≤ 0 | z ≥ 0, X ≥ 0 |W z → max T

Ez egy standart LP feladat, amely Dantzig szimplex módszerével minden további nélkül megoldható. Ehhez mindössze a következő szimplex táblázatot kellene felírnunk és megoldanunk (a 0-k megfelelő méretű nullákból álló nullvektorok, En az n-ed rendű egységmátrix, a Ti az A, x Ti az X mátrix i-dik sorvektora):

26

z

x 1T

x T2

...

x Tm

t

0

En

En

...

En

1

λ1

1

−a 1T

0T

...

0T

0

λ2

1

0T

−a T2

...

0T

0

...

...

...

...

...

...

...

λm

1

0T

0T

...

−a Tm

0

f(z,X)

1

0T

0T

...

0T

0

A fakádat a legrövidebb donga szintjéig lehet tölteni, mert utána már kifolyik a többlet.

39

Itt a t és a λ a duális változók vektorai, t n, λ m elemű. Vagyis a szimplex táblázat belső négyszöge (m+n)⋅(m⋅n+1) elemből áll. Ez például m=2, n=3 esetén (2+3)⋅(2⋅3+1)=35, m=4, n=6 esetén (4+6)⋅(4⋅6+1)=250, m=8, n=12 esetén pedig már (8+12)⋅(8⋅12+1)=1940! Vagyis miközben a gépek és alkatrészek száma megkétszereződött, a számítási mező mérete előbb több mint hétszeresére, másodszor pedig már közel nyolcszorosára nőtt (vagyis az alapadatok megnégyszerezése a szimplextábla elemeinek számát több mint 60-szorosára növeli)! Nagyon kívánatos tehát egy, a szimplex módszernél kevesebb számítást jelentő módszert találni. Ezt tette (a szimplex módszer feltalálása előtt) Kantorovics a megoldó együtthatók módszerének kidolgozásával. A módszer lényege, hogy egy együttható-vektorral előállítható a feladat egy megengedett vektora, amiről Kantorovics tétele segítségével megállapítható, hogy optimális-e vagy sem. Amennyiben nem, akkor az együtthatók célszerű megváltoztatásával új, az előzőnél jobb vektort állítható elő. Bizonyítható, hogy az eljárás véges lépésben elvezet az optimumhoz. A módszer ismertetésekor láthatóvá válik, hogy a megoldó együtthatók éppen a fenti szimplex-táblázatban szereplő λi számok, vagyis a feladat duális változói lesznek. A Kantorovics-tétel ilyen módon igen közeli rokonságban van a dualitási tételekkel. Ugyanakkor a módszer, mint látni fogjuk, erősen emlékeztet Walras árkikiáltójának tapogatódzó árkorrekcióira. Ez sem véletlen. Ugyanakkor Kantorovics publikációjában csupán a Kantorovics tétel bizonyítása van korrektül levezetve. Magának a módszernek a leírása tele van heurasztikus elemekkel (valóban nagy a hasonlóság a walrasi tâtonnement-nel!). Indoklásul Kantorovics így ír: „Mindezek az egyszerűsítések, amelyek gyakran csökkentik a számítások idejét, a megoldás lényegét nem érintik, mivel a lényeg a λi megtalálása, és az ehhez vezető út semmilyen szerepet nem játszik.“ 27 A gyakorlat nem igazolta Kantorovics nagyvonalúságát. Módszere pontosításra szorult. Erre két kísérlet is történt. 28 Az alábbiakban az egyik pontosított módszert ismertetjük. Kantorovics módszerének lépéseit egy igen egyszerű feladaton mutatta be. Később mindazokban a publikációkban, ahol ismertették Kantorovics módszerét, általában ezt a példát reprodukálták. 29 Legyen az alkatrészek száma kettő, a gépeké három:

27

Канторович Л.В. Математические методы ... 1959-es kiadás 287-288. oldalak

28 Hoang Thuy - Nguyen Quang Thai „Новый метод решения одной задачи распределения“ Экономика и Матемаческие Методы III.6. Москва 1967. Nagy András „Egy algoritmus L.V. Kantorovics megoldó együtthatós módszeréhez“ Matematikai Lapok 24. 3-4. Budapest, 1973 29

Például Krekó B. Lineáris programozás 408-412. oldalakon

40

A=

LM30 N60

LM N

OP Q

30 x11 60x12 60 30 , A oX = 60x 21 90 x 22 90 80

OP Q

30x13 80x 23 .

Legyen például λ1=0,7, λ2=0,3. Ezekben a számokban csupán az a heurasztikus sejtés érvényesül, hogy az első alkatrészt nehezebb előállítani és így az ehhez tartozó értékelésnek nagyobbnak kell lennie 30 . Továbbá a szépség kedvéért olyan együtthatókat választottunk, amelyek összege 1. Mindez valóban lényegtelen. Az induló együtthatókat tetszőlegesen válaszhatjuk meg. Mielőtt elkezdenénk a megoldást, idézzük Kantorovics tételét: (Kantorovics, 1939) Ha létezik olyan pozitív λ vektor, nem negatív X mátrix és nem negatív z szám, amelyekre fennállnak a következő összefüggések:

TÉTEL

a.) X T 1 = 1

b

g

b.) z1 = A oX 1 c.) x ij ≡ 0, ha a ijλ j < t i = max a ijλ j j

vagy ami ugyanaz

b

g

c'.) λ T A oX = t T = max a ijλ i

T

i

akkor az (X,z) páros az A feladat optimális megoldása.

A bizonyítás megtalálható Kantorovics, vagy Krekó idézett munkájában. A bizonyításból az derül ki, hogy az optimális megoldás mindig létezik, s az ehhez tartozó (egy skalár szorzó erejéig egyértelmű 31 ) λ vektorból az optimális megoldás megkonstruálható. A konstruálás az a.) b.) c'.) egyenletrendszer megoldásával történik. Magát a λ vektort nevezi Kantorovics a megoldó együtthatók vektorának. A módszer tehát arra épül, hogy választunk egy pozitív λ vektort, a z1 helyébe egy z vektort írunk és így kapunk egy

a.) XT 1 = 1 b.) z = ( A X ) 1 c′.) λ T ( A X ) = t T = ⎡ max a ijλ i ⎤ ⎣ i ⎦

T

egyenletrendszert, ahol λ−ból kiszámítható t, majd megoldható az egyenletrendszer. Ha X nem negatívnak bizonyul és z elemei azonosak lesznek egymás között, akkor a Kantorovicstétel szerint X és z=zi (i bármelyik lehet) az A feladat optimális megoldása. Ha z elemei különbözőek, akkor úgy korrigáljuk λ megfelelő komponensét, hogy vagy a legnagyobb zi csökkenjen, közelítve z többi komponenséhez, vagy a legkisebb zi nőjön - ugyanazért. Ha X valamelyik eleme negatívnak bizonyulna, akkor egyszerűen azonosan egyenlővé tesszük 0val, és újra megoldjuk az egyenletrendszert. Ekkor természetesen új X-et és új z-t fogunk kapni. Ezekre azonban ugyanúgy alkalmazható a megoldó együtthatók korrekciója. Ez eddig Kantorovics eredeti gondolatmenete. Alkalmazzuk ezt a fenti számpéldára. 30 Ezek a számok Krekó könyvéből származnak. Kantorovics javaslata: λ =α/Σa , ahol α tetszőleges i ij, pozitív szám.

A c'.) feltételből látható, hogy ha λ helyett α⋅λ szerepel, akkor t helyett is α⋅t fog szerepelni és semmi más nem változik. 31

41

Mindenek előtt számítsuk ki a λ i a ij mátrixot, és keressük meg minden sorban a maximumot: λ i a ij =

LM21 N18

OP Q

42 27

21 24

Ebből t1=21, t2=42, t3=24. Ennek alapján a c.) feltételt alkalmazva: X=

LMx N0

Az a.) feltétel szerint ebből X=

x12 0

11

LM1 N0

0 x 23

1 0 0 1

OP Q

OP Q

amiből viszont

OP LM OP LM OP Q MMN PPQ N Q

L30 z = bA oX g1 = M N0

1 60 0 90 1 = 0 80 80 1 .

Látható, z-nek nem egyenlőek a komponensei, ezért a Kantorovics tétel alapján ez még nem az optimum. Az is látszik, hogy az első alkatrészből több, vagy a másik alkatrészből kevesebb készült a kelleténél, ezért vagy a λ1 „értékelést“ 32 kell csökkenteni (ez az alkatrész a jelenlegi értékeléssel - 0,7 szemben a 0,3-mal - túl van értékelve), vagy a λ2 „értékelést“ kell növelni (mert a második alkatrészt alulértékeltük). Mivel a λ nagysága csak egy pozitív konstanssal való beszorzás erejéig számít, azért a két eljárás természetesen teljesen ekvivalens. Mindenképpen azt kell elérni, hogy egy olyan gépet, amely eddig nem termelt második alkatrészt, most bevonjuk annak termelésébe. Ugyanakkor vigyázni kell, hogy mást lehetőleg ne változtassunk meg. Így érhetjük el, hogy az új termelt mennyiségek 80 és 90 között lesznek, tehát valóban közelebb kerülünk az optimális megoldáshoz. Az eljárás a következő. Legyen zi a z vektor legnagyobb komponense. Jegyezzük meg az i indexet! Legyen t j = max a il λ i . Jegyezzük meg a j indexet is! Ezek után vagy a λi-t kell l

b g

addig csökkenteni, amíg tj értéke le nem csökken a hozzá legközelebbi akj⋅λk szintjére, vagy valamennyi λk-t (k≠i) kell egyszerre addig növelni, hogy ugyanez a kiegyenlítődés bekövetkezzen. Maradjunk az első megoldásnál. Ekkor λi-t a következő szorzóval kell korrigálni: δi =

max a kjλ k k ≠i

tj

Ez számpéldánknál i=1, j=1 mellett

δ1 =

32

max a k1λ k k ≠1

t1

=

.

l q = 18 = 6

max 18 21

21

7.

Kantorovics később bevezetett terminológiájával: objektíve megalapozott értékelést

42

A korrigált λ1=0,6. Tehát az új λ i a ij mátrix: λ i a ij =

LM18 N18

36 27

18 24

OP Q

Az új tT vektor [18, 36, 24]. A Kantorovics tétel alkalmazása számára:

LM x Nx

X=

illetve X=

OP Q

x12 0

11 21

LM x N1 − x 11

11

0 x 23 ,

OP Q

1 0 0 1 ,

tehát

L 30x z = bA oX g1 = M N60b1 − x g 11

11

OP LM OP LM Q MMN PPQ N b

OP g Q .

1 30 x11 + 60 60 0 1 = 60 1 − x11 + 80 0 80 1

Ha találunk olyan nem negatív x11-et, amelyre ennek a vektornak a komponensei megegyeznek, akkor a feladatot megoldottuk. Vagyis keressük a

b

g

60 1 − x11 + 80 = 30 x11 + 60 8 egyenlet megoldását. Ez x11 = . Ekkor 9

LM 8 X = M9 MN 91

OP P1P ≥ 0 Q

1 0 0

azaz a feladatot valóban megoldottuk: z=86,666. Foglaljuk össze az algoritmust!

43

1. Megadunk egy tetszőleges pozitív λ vektort. 2. Start 3. Kiszámítjuk a λ i a ij mátrixot. 4. Megjelöljük a t vektor elemeit. 5. Felírjuk a pontosított X mátrixot: x ij ≡ 0, ha a ijλ j < t i = max a ijλ j .

b

j

g

6. Megoldjuk az XT1=1, z = A oX 1 egyenletrendszert. 7. Ha z=z1, a feladatot megoldottuk, a megoldás (X, z). A duális feladat megoldása (λ, t). Vége. 8. Ha zi a z vektor maximális eleme, de z ≠ z i 1 és t j = max a il λ i , akkor a λi-t korrigáljuk a δi =

l

max a kjλ k k ≠i

korrekciós szorzóval és vissza a starthoz.

tj

Ez tehát Kantorovics algoritmusa. Két alkatrész, három gép esetén remekül működik. Nézzük meg, nagyobb feladat esetén működik-e? Tekintsük a következő A mátrixszal leírható gépterhelési feladatot:

LM1 2 A=M MM1 N3

4 3 1 0

3 3 1 1

1 1 4 0

5 4 2 0

OP PP PQ

Látható: a mátrix félpozitív, de nem pozitív. Ha szükséges, akkor az utolsó sor három nullája helyére egy elég kis számot fogunk írni, mondjuk 10-22-t. Egyenlőre kíséreljük meg alkalmazni a fenti algoritmust. 1. Legyen λ=1. 2. Start. 3. [λiaij]=A.

4. λ i a ij

LM1 2 =M MM1 N3

LM0 0 5. X = M MM0 N1

1

4

3

1

3 1

3 1

1 4

0

1

0

x13

T

0 1

0 1 − x13 0 0

0 1

0

0

0

OP 0P 0P P 0Q

OP 4P tehát t =[3, 4, 3, 4, 5]. 2P P 0Q 5

44

R|4 + 3x + 5 = z | 3 − 3x = z 6. A S 4=z || 3= z T 13

12

13

12

egyenletrendszer megoldása x13

3 4

LM6OP 6 = -1, z = M P , MM4PP N 3Q

és máris megakadtunk, hiszen X nem nemnegatív! Próbáljuk meg módosítani az eljárást. Ha x13 nem akar pozitív lenni, akkor legyen 0. Tehát legyen

LM0 0 5. X = M MM0 N1 LM9OP 3 6. z = M P MM4PP N 3Q

OP PP P 0Q

1 0 0 1 0 1 0 0 0 0 1 0 0 0 0

7. Mivel max z i ⋅ 1 = 9 ⋅ 1 ≠ z , azért még nem vagyunk az optimális megoldásnál. 8. i=1, max a 1 jλ 1 = 5 = t 5 , tehát j=5, vagyis j

δ1 =

max a k5λ k k ≠1

t5

= max

RS 4 , 2 , 0 UV = 4 T5 5 5W 5 ,

tehát λT=[0,8 1 1 1], és 2'. start.

3'. λ i a ij

LM0, 8 b3, 2g 2, 7 0, 8 b4gOP b3g 1 b4gP 2 3 =M MM 1 1 1 b4g 2 PP MN b3g 0 1 0 0 PQ

4'. tT=[3 3,2 3 4 4]

LM0 1 0 0 0 1 5'. X = M MM0 0 0 N1 0 0 R| 4 + 5x = z |4 − 4 x = z 6'. S || 4 = z T 3= z 15

12

15

12

0

x15

0 1 − x15 1 0 0

0

OP PP PQ

egyenletrendszer megoldása: x15

3 4

7'. A megoldás nem optimális 45

LM4OP 4 =0 z = M P MM4PP N 3Q

8'. i=1,2,3, max a ijλ i = 4 = t 4 = t 5 , tehát j=4,5 és így j i =1,2 ,3

max a kjλ k

δ1,2,3 =

k ≠1,2 ,3 j= 4 ,5

t 4,5

= max

RS 0 , 0 UV = 0 T4 4 W .

Most azonban tényleg bajban vagyunk. Melyik λi-t korrigáljuk ezzel a „szorzóval“? Esetleg mindet? Nem sokra fogunk menni az új λT=[0 0 0 1] „megoldó vektorral“. Vagy csak az egyik komponenst tegyük nullává - próbáljuk meg a λT=[0 1 1 1] vektort! 2''. Start.

3''. λ i a ij

LM0 2 =M MM1 N3

0 3 1

0 3 1

0 1 3

0

1

0

OP PP P 0Q

0 3 . 2

Itt már nyilvánvaló, hogy ez az út sehova sem vezet. Az algoritmus korrekcióra szorul. Mi okozza a problémát? Vegyük szemügyre az első menet 3. lépésében felírt mátrixot. Készítsünk egy sematikus ábrát a „megjelölt elemek“ kapcsolatáról:

8. ábra Az induló mátrix „megjelölt“ elemeinek struktúrája

Az ábrán azt látjuk, hogy a „megjelölt“ elemeket sormenti és oszlopmenti vonalakkal összekötve az i=1,2 sorok, illetve a j=2,3,5 oszlopok „összefüggőké“ váltak, míg az i=3, az i=4 sorok, illetve a j=1, j=4 oszlopok sem egymással, sem az előzőekkel nincsenek „összekötve“. Nézzük meg mi történt az első lépés után:

9. ábra A második mátrix „megjelölt“ elemeinek struktúrája

46

Látható, hogy a „megjelölt“ elemek ugyan megváltoztak, de a sorok és oszlopok „öszszeköttetése“ azonos maradt az előzővel. A harmadik lépésben ki akartunk törni ebből a struktúrából és ez okozta a kudarcot. Könnyen belátható, hogy egy „két gép, három alkatrész“, vagy egy „három gép, két alkatrész“ típusú feladatnál akármit csinálunk is, minden oszlop és minden sor „összefügg“. Ezért működött ott hibátlanul az algoritmus. Meg kell oldani a „független“ sorok „függésbe hozásának“ problémáját. B.) A JAVÍTOTT ALGORITMUS

Hogy a továbbiakban ne kelljen állandóan titokzatos „macskakörmökkel“ bajlódnunk, kezdjük három definícióval: 1. DEFINÍCIÓ (Aλ feladat) Valamely pozitív λ vektorhoz megalkotjuk a következő LP feladatot, amelyet Aλ feladatnak nevezünk:

U| X 1 = 1| | z1 − b A oX g1 ≤ 0 V dA i x ≡ 0 ha a λ < t || z ≥ 0, X ≥ 0 |W z → max T

λ

ij

j

ij

Szemmel láthatóan az Aλ feladat minden optimális megoldása az A feladatnak megengedett (nem feltétlenül optimális) vektora lesz. Fordítva ez nem igaz, nem minden A feladatban megengedett vektor lesz egyben az Aλ feladat optimális megoldása. Viszont Kantorovics tétele alapján az A feladat optimális megoldása egyben a megoldó együtthatókkal alkotott Aλ feladatnak is optimális megoldása. Ezért a továbbiakban az A feladat helyett az Aλ feladatok megoldásával fogunk foglalkozni. 2. DEFINÍCIÓ (megjelölt elemek) Valamely Aλ feladatban az (i,j) cellát és a benne levő elemeket (aij, xij, stb.) megjelöltnek nevezzük, ha aijλi=ti. Az i-dik sor megjelölt elemeinek j indexeiből álló halmazt Pi-vel jelöljük. Nyilván minden j eleme valamelyik Pi halmaznak. 3. DEFINÍCIÓ (az összefüggés rekurzív meghatározása) a.) Ha Pi∩Pk nem üres, akkor az i és k sorok közvetlenül összefüggőek. b.) Ha valamely sorok közvetlenül összefüggőek, akkor összefüggőek c.) Ha i és k sorok, illetve k és r sorok páronként összefüggőek, akkor i és r sorok is összefüggőek - az összefüggés tranzitív. Valamely λ vektor esetén feltehetjük, hogy minden sorban van megjelölt elem. Ha ugyanis az i sorban nincs, akkor λi-t meg kell szorozni a következő korrekciós tényezővel: ε i = min j

tj a ijλ i

>1 ,

és a módosított λ-hoz tartozó Aλ feladatban már lesz az i-dik sorban megjelölt elem. Az eljárás nem megy az általánosság rovására, mivel az A feladat optimális megoldásában biztosan van minden sorban megjelölt elem (különben nem jönne ki a komplett), tehát azokat az Aλ feladatokat, amelyekben vannak üres Pi halmazok, nyugodtan ki lehet dobni. Pontosan erre szolgál a fenti korrekció. 47

Az összefüggési reláció - a fenti korrekcióval - osztályokba sorolja a sorokat. Legyen Ks egy összefüggési osztály. Nyilván az oszlopok is összefüggési osztályokra bonthatóak. Legyen Hs a Ks-hez tartozó sorok összes megjelölt j indexeinek halmaza 33

l

q

H s = j ∈ Pi | i ∈ K s = U Pi i ∈K s

A gépek és alkatrészek mindig átsorszámozhatóak úgy, hogy az egy osztályba tartozó sorok egymás alatt, oszlopok egymás mellett legyenek. Ekkor az A és az X mátrixok a következő blokkos szerkezetet veszik fel:

LM A MM ... A= A MM ... MNA

1

s1

S1

az

Aλ

OP PP PP PQ

... A 1s ... ... ... A s ... ... ... A Ss

... A 1S ... ... ... A sS , X = ... ... ... A S

LM X MM ... MM X... MNX

1

s1

S1

... X1s ... ... ... X s ... ... ... XSs

... X1S ... ... ... X sS ... ... ... XS

OP PP PP PQ

Ebben a szerkezetben az összes megjelölt elem a diagonális blokkokban (As) van, így feladat felbontható az A sλ feladatokra:

U| X 1 = 1| | z 1 − b A oX g1 ≤ 0 V d A i (s=1,2,...S) x ≡ 0 ha a λ < t || z ≥ 0, X ≥ 0 |W z s → max T s

s

s

λ s

s

ij

ij

s

j

s

Az egyes diagonális blokkokban a megjelölt elemek egy vonalon helyezkednek el (hiszen a blokkba egy összefüggési osztály sorai, oszlopai kerültek). Ez a vonal - az indexek megfelelő átcsoportosítása után - háromféle típusú lehet (lásd a 10. ábrát): a.) Lépcső b.) Kör c.) Lépcsők és körök A lépcső esetén sokban támaszkodhatunk a szállítási feladatok elméletére. A köröket meg kell szakítani, ezzel lépcsővé (vagy lépcsőkké) alakítva. Ehhez a kör egyik csúcsát ki kell tiltani a megjelölt elemek közül, azaz a cellához tartozó xij-t azonosan egyenlővé kell tenni 0-val. Később persze ez az elem ismét válhat megjelöltté.

a.)

b.)

c.)

33

Az egyszerűség kedvéért a sorokat és oszlopokat azonosítjuk saját indexeikkel. Igy a Ks ugyan az összefüggő sorok halmaza, de azt is mondjuk, hogy i∈Ks, ahol i a Ks-be tartozó sor indexe.

48

10. ábra Lépcsők és körök

Amennyiben csak lépcső maradt, akkor megoldható a következő egyenletrendszer (a nem megjelölt xij≡0): X Ts 1 = 1

b A oX g1 = z 1 s

s

s

Ismét két eset lehetséges: Xs vagy nem negatív vagy van negatív eleme. Az első esetben közelebb kerültünk a megoldáshoz, megjegyezve az A sλ feladat értékét, ami a zs. Ha viszont a megjelölt xij-k valamelyike negatívnak bizonyul - hatástalan elem, akkor ezt a változót is lenullázzuk. Ha a kiiktatandó elem egy korábban felszámolt kör része volt, akkor vissza kell venni az akkor kiiktatott változót, egyébként a lépcsőből kihagyott elem miatt a lépcső szétszakad, a Ks osztály szétesik új osztályokra. Ez persze nem megy a végtelenségig, hiszen az új osztályok egyre kisebbek lesznek és egy eleműnél kisebbek nem lehetnek. Viszont egy egyelemű osztály esetén nyilván xij=1 és zs=aij, vagyis az A sλ feladat értéke kiszámítható. Végső soron az összes A sλ feladat értéke meghatározható. Ha ezek egyenlőek, akkor a feladatot megoldottuk. Ha nem egyenlőek, akkor van köztük legnagyobb és legkisebb is. Ha ezek kiválasztása nem egyértelmű 34 , akkor egy megfelelő korrekciós szorzóval végig szorozva az azonos maximális (minimális) értékhez tartozó osztályok valamennyi megoldó együtthatóit a probléma véges lépésben megszűnik. Tehát előbb-utóbb egyértelműen ki lehet választani például a legnagyobb értékű osztályt. Ezt összeolvaszthatjuk egy másik osztállyal, ha végig szorozzuk az osztály valamennyi megoldó együtthatóját a következő korrekciós tényezővel: δ = max s

j∈H s

max a kjλ k k ∉K s

tj

<1

Az új megjelölt elemek meghatározása után az összeolvasztás nem biztos, hogy csökkenti az osztályok számát, mert a hatástalan elemek az új osztályt részekre szakíthatják. Bizonyítható azonban, hogy az új osztályok értékei kisebbek lesznek a maximális értéknél, de nagyobbak a második legnagyobb értéknél 35 . Tehát közeledünk a megoldáshoz. A véges struktúrák miatt véges lépésben el is jutunk a megoldáshoz. Az algoritmus tehát a következő:

34

Ekkor beszélünk a degeneráció esetéről.

35

Lásd az „Egy algoritmus ...“ című idézett tanulmányt (Nagy A.).

49

1. Megadunk egy tetszőleges pozitív λ vektort. 2. Start 3. Kiszámítjuk a λ i a ij mátrixot. 4. Megjelöljük a t vektor elemeit. 5. Felírjuk a pontosított X mátrixot: x ij ≡ 0, ha a ijλ j < t i = max a ijλ j . j

6. Meghatározzuk az összefüggési osztályokat, felszámoljuk a köröket.

b

g

7. Minden összefüggési osztályra megoldjuk az X Ts 1 = 1, A s oX s 1 = z s 1 egyenletrendszert, kiiktatjuk a hatástalan elemeket, az új osztályokra ismét megoldjuk a megfelelő egyenletrendszereket, addig amíg az összes osztálynak meg nem határoztuk az értékét. 7. Ha z=z1, a feladatot megoldottuk, a megoldás (X, z). A duális feladat megoldása (λ, t). Vége. 8. Ha zs az osztályok maximális értéke, de z ≠ z s 1, akkor az összes λi-t (i∈Ks) korrigáljuk a max a kjλ k k ∉K s δ s = max < 1 korrekciós szorzóval és vissza a starthoz. j∈H s tj És most oldjuk végre meg az előbb vizsgált számpéldát! A megoldás menetét a következő oldalakon táblázatokba foglalva ábrázoljuk. Az egyes lépésekhez tartozó táblázatok szerkezete a következő. Az első négy sor az A mátrixot és a λ vektort tartalmazza. A következő négy sor a λ i a ij mátrix. Ez alatt vastag keretben a t vektor elemei szerepelnek. A következő négy sor, az utolsó oszlopot kivéve az X mátrix kiszámított értékeit tartalmazza, az utolsó, dupla keretbe zárt oszlop pedig a z vektort. Végül az utolsó sor (ez a 4. lépésnél már nem kellett) a z vektor maximumához tartozó λi elemek korrekciós együtthatójának számítási részeredményei, illetve az utolsó cellában maga a δs korrekciós szorzó szerepelnek.

50

1

4

3

1

5

1

2

3

3

1

4

1

1

1

1

4

2

1

3

0

1

0

0

1

1

4

3

1

5

Meg kell jegyezni, hogy az utolsó lépésben, amikor már az egész mátrix egyetlen összefüggési osztállyá vált, a megjelölt elemek közül a

2

3

3

1

4

{(1,4)(1,5)(3,4)(3,5)}

1

1

1

4

2

3

0

1

0

0

3

4

3

4

5

0

1

0

0

1

9

0

0

1

0

0

3

0

0

0

1

0

4

1

0

0

0

0

3

cellák kört alkottak. Ezt az x15=0 behelyettesítéssel számoltuk fel. Az egyenletrendszer megoldása során az x14 és x35 elemek is 0nak adódtak (hatástalan elemek!).

0,8

0,8

1. lépés

0,75

2. lépés 1

4

3

1

5

0,8

2

3

3

1

4

1

1

1

1

4

2

1

3

0

1

0

0

1

0,8

3,2

2,4

0,8

4

2

3

3

1

4

1

1

1

4

2

3

0

1

0

0

3

3,2

3

4

4

0

1

0

0

0,26667

5,66667

0

0

1

0

0,73333

5,66667

0

0

0

1

0

4

1

0

0

0

0

3

0,5

0,5

0,3125

51

3. lépés 1

4

3

1

5

0,4

2

3

3

1

4

0,5

1

1

1

4

2

1

3

0

1

0

0

1

0,4

1,6

1,2

0,4

2

1

1,5

1,5

0,5

2

1

1

1

4

2

3

0

1

0

0

3

1,6

1,5

4

2

0

1

0

0

0,05263

4,78947

0

0

1

0

0,31579

4,78947

0

0

0

1

0,63158

4,78947

1

0

0

0

0

3

0

0,66667

0

0

0,66667

1

4

3

1

5

0,26667

2

3

3

1

4

0,33333

1

1

1

4

2

0,66667

3

0

1

0

0

1

0,26667

1,06667

0,8

0,26667

1,33333

0,66667

1

1

0,33333

1,33333

0,66667

0,66667

0,66667

2,66667

1,33333

3

0

1

0

0

3

1,06667

1

2,66667

1,33333

0

1

0

0

0

4

0

0

0

0

1

4

0

0

0

1

0

4

1

0

1

0

0

4

4. lépés

52

3. A HOZZÁRENDELÉSI FELADAT A.) A „MAGYAR MÓDSZER“

A lineáris programozás egyik legismertebb, leggyakrabban alkalmazott feladattípusa a szállítási feladat. Ebben - mint ismeretes - arról van szó, hogy például m raktárból, ahol az i-dik raktár készlete egy adott áruféleségből ai, n boltba kell kiszállítani - a j-ik boltba bj mennyiséget (i=1,2,...,m; j=1,2,...,n). Adott az i-j relációk szállítási költsége, azaz az [cij] költségmátrix. Keressük a legolcsóbb [xij] kiszállítási tervet. Ennek a feladatnak is - az előzőekben tárgyalt gépterhelési feladathoz hasonlóan - a szabványos szimplex táblázata hatványozottan nő a forrásadatok (m, n) növekedésével. Itt is lehetőség van az egyszerűbb tárgyalásra a szimplex módszerből származtatható disztribúciós módszerrel, amit neveznek a potenciálok módszerének is (a potenciálok a feladat speciális szerkezetéből adódó duális változók) 36 . Van azonban más módszer is, amelyet kidolgozója, H.W. Kuhn „magyar módszernek“ nevezett, mivel a magyar König Dénes és Egerváry Jenő gráfelméleti tételein alapszik. A módszert Kuhn eredetileg az úgynevezett „hozzárendelési“ vagy „kinevezési“ feladathoz dolgozta ki, de igen egyszerűen általánosítható a szállítási feladatra. A feladat - a második elnevezést magyarázóan - a következő. Van n munkafeladat és n munkás, aki jól-rosszul el tudja látni bármelyik feladatot. Az cij szám jellemezze a j-ik feladat i-dik munkás által történő elvégzését. Ha ez a szám például a relatív költséget jelenti, akkor keressük azt a „kinevezési“ tervet, amelynek megvalósítása a legkisebb költséggel jár. De jelentheti a szám az adott „kinevezés“ hozadékát is, ekkor természetesen az összhozadék maximalizálására törekszünk. Vagyis a feladat lehet minimizációs is, meg maximizációs is. Az első elnevezés szerinti interpretáció közelebb áll a szállítási feladathoz, s így kurzusunk témájához is. E szerint például egy taxis társulás n tagját küldi a diszpécser n megrendelőhöz úgy, hogy az „üres“ fuvar összességében minimális legyen. A taxisoknak különböző drosztokról kell különböző címekre eljutni. Minden taxisnak minden címhez ismert a távolsága. A címekhez „hozzárendelt“ taxik által befutott „üres“ kilométerek összegét kell minimalizálni. A feladat némileg emlékeztet arra a fejtörőre, ahol egy sakktáblán kell elhelyezni 8 bástyát úgy, hogy azok ne üssék egymást. Egy négyzetes mátrixban az e szabály szerint megjelölt elemeket független pontoknak nevezzük. Tehát az [aij] olyan független pontjainak a kijelölése a feladatat, amelyeknek hozzátartozó aij elemeik összege minimális (vagy maximális). Elvileg a megoldás roppant egyszerű. Legyen X=[xij] a megoldás-mátrix, ahol xij=1, ha cij megjelölt és xij=0 egyébként. Mivel a megjelölt elemek függetlenek, azért a megoldást az úgynevezett permutáló mátrixok között kell keresni. A permutáló mátrixokat az egységmátrix (E) oszlopainak (vagy ami ezzel ekvivalens - sorainak) minden lehetséges felcserélésével (permutálásával) kapjuk. Magától értetődik, hogy E maga is permutáló mátrix. A megoldás tehát abból áll, hogy az összes n-ed rendű permutáló mátrixra kiszámítjuk a megjelölt aij-k összegét, és kiválasztjuk az optimálist. Ez valóban egyszerű. Sajnos az n-ed rendű permutáló mátrixok száma éppen n! (n-faktoriális), azaz 1⋅ 2 ⋅ 3⋅...⋅n - ez pedig n növelésével elképesztő mértékben növekszik: 10!=3 628 800. 36

A szállítási feladat megoldása a disztribúciós módszerrel lényegében minden LP-, illetve operációkutatási tankönyvben megtalálható. Lásd például Krekó B. „Lineáris programozás“ 346-383. oldalak, vagy Matematika üzemgazdászoknak Operációkutatás II. (szerk. Csernyák L.) 71-115. oldalak

53

Egy tíz taxiból álló társulás pedig még csak nagynak sem mondható! Tegyük fel, hogy a költségmátrixban vannak 0 költségű cellák is. Ha ráadásul ezek a cellák függetlenek, akkor nyilván ezekre érdemes a (költségminimalizáló) hozzárendeléseket programozni. Ha ráadásul olyan szerencsénk van, hogy minden sorban van egy ilyen független 0, akkor már meg is találtuk a megoldást. Nem lehetne ezt a szerencsét mesterségesen elősegíteni? A „magyar módszer“ lényege éppen ez. Írjuk fel a hozzárendelési feladat matematikai modelljét 37 !

R| ∑ ∑ c x → min || |∑ x = 1 b j = 1,2,..., ng S| ||∑ x = 1 bi = 1,2,..., ng || X = x ≥ 0 T n

n

ij

ij

i =1 j=1

n

ij

i =1 n

ij

j=1

ij

Tegyük fel, hogy X' ennek a feladatnak az optimális megoldása. Legyen C* a költségmátrix olyan módosítása, amelyben valamely i-re és minden j-re c∗ij = c ij + k , ahol k egy tetszőleges konstans. Ekkor n

m

n

m

m

n

m

∑ ∑ c∗ijx ij = ∑ ∑ cijx ij + ∑ kx ij = ∑ ∑ cijxij + k i =1 j=1

i =1 j=1

j=1

i =1 j = 1

tekintettel arra, hogy minden „megengedett vektor“ permutáló mátrix, amelyben az i-dik sorban is csak egy nem nulla, nevezetesen egységnyi elem van. Mivel pedig n

m

n

m

∑ ∑ c x′ ≤ ∑ ∑ c x ij ij

i =1 j=1

ij ij

minden X esetén

i =1 j=1

azért n

m

n

m

∑ ∑ cijx′ij + k ≤ ∑ ∑ cijxij + k i =1 j=1

i =1 j=1

is igaz. Tehát X' a módosított költségmátrix esetén is optimális megoldás, azaz igaz a következő Tétel Amennyiben a hozzárendelési feladat költségmátrixa valamely sorának vagy oszlopának minden elemét ugyanazzal a k konstanssal módosítjuk, akkor az az optimális hozzárendelést nem változtatja meg, csupán az új optimális célfüggvényérték módosul k értékkel.

A tétel alapján kirajzolódik egy megoldás lehetősége. Addig kell egy-egy konstanssal csökkenteni a költségmátrix oszlopait és/vagy sorait, amíg n darab független 0 nem keletkezik. Ekkor az optimális hozzárendelés mátrixában a költségmátrix független 0-inak 37

A modell explicíte nem tartalmazza azt a feltételt, hogy X elemei csak 0-ák vagy 1-esek lehetnek. Viszont ismert, hogy a szállítási feladat úgynevezett egészértékű probléma, ahol ha a feladat paraméterei egész számok, akkor azok lesznek a megoldás elemei is. A korlátozó feltételek így egyértelműen csak permutáló mátrixokat engednek meg megoldásoknak.

54

megfelelő helyre 1, a többi cellába 0 kerül. Ez a tétel szerint az eredeti feladat optimális megoldása is lesz. Az optimális célfüggvényérték pedig a levont konstansok összegével lesz azonos. Próbáljuk ki ezt egy nagyon egyszerű, mindössze másodrendű feladaton. Legyen a költségmátrix:

LM12 34OP N23 6 Q

Vonjuk ki mind a két sorból a minimális elemet:

LM 0 22OP N17 0 Q

Vagyis a megoldás éppen az egységmátrix, a célfüggvény értéke pedig 12+6=18. Valóban, a másik lehetséges permutáló mátrix (az egyesek a mellékdiagonálison) 23+34=57 költséget jelentene, ami nyilván rosszabb. Nézzünk ezután egy nagyobb feladatot. Legyen 38 n=5:

LM5 MM8 MM24 MN3

OP PP 8 P 6P 3PQ

3 4 2 6 3 5 5 4 5 3 6 2 8 3 6 9 5

Vonjuk le valamennyi sorból a minimális elemet:

LM5 MM8 MM24 MN3

OP PP PP PQ

3 4 2 6 /−2 3 5 5 4 /−3 5 3 6 8 /−2→ 2 8 3 6 /−2 6 9 5 3 /−3

LM3 MM5 MM20 MN0

OP P 6P P 4P 0PQ

1 2 0 4 0 2 2 1 3 1 4 0 6 1 3 6 2

Most már minden sorban van egy 0, de nem minden oszlopban. Ezért most minden oszlopból is levonjuk a minimális elemet. Ott ahol már van 0, ott ezt levonva természetesen nem változik semmi. Ne felejtsük azonban el, hogy a célfüggvény értéke pillanatnyilag 2+3+2+2+3=12. Tehát az oszlopok redukálása:

38

LM3 MM5 MM20 MN0

1 0 3 0 3

2 2 1 6 6

0 2 4 1 2

−0

−0

−1

−0

OP PP PP PQ

LM MM MM MN

3 4 5 1 6 → 0 2 4 0 0 −0

A példa Krekó B. idézett könyvéből való.

55

1 0 3 0 3

1 1 0 5 5

0 2 4 1 2

OP 1P 6P P 4P 0PQ 4

Most már csak az az apróság maradt hátra, hogy kiválasszunk öt független zérust, amihez még lehet, hogy további redukciókra is sor kerülhet. Ehhez lesz szükségünk a KönigEgerváry tételre. Egyben nem felejtjük el, hogy eddigi redukcióink a célfüggvény értékét pillanatnyilag 12+1=13 szinten valószínűsítik. Ez további redukciókkal még változhat. Egy független zérust nem nehéz találni. Bármelyik lehet az. De ha nem akarjuk a többi esélyét csökkenteni, akkor lehetőleg olyat kell választani, amelyikkel egy „vonalon“ (sorban, vagy oszlopban) nincs másik zérus. Ha ilyen nincs, akkor legalább olyat keressünk, amelyikkel vagy egy sorban, vagy egy oszlopban nincs másik zérus. Ha ez sem lehetséges, akkor azt választhatjuk amelyik eszünkbe jut. A számpéldánkban van „jó“ zérus, például az első sor negyedik eleme. Jelöljük meg és a vonalait tiltsuk le.

LM3 MM5 MM20 MN0

1

1

0

0

1

2

3

0

4

0

5

1

3

5

2

P1PO 6P P 4P 0 PQ 4

A maradékon ismételjük meg ezeket a lépéseket, ahányszor csak lehet:

LM3 MM5 MM20 MN0

1

1

0

0 3

1 0

2 4

0 3

5 5

1 2

P1PO 6P P 4P 0 PQ

4

Négy független zérust találtunk. De vajon másképpen választva nem találhattunk volna többet? A választ a König-Egerváry tétel alapján adhatjuk meg. TÉTEL

(König-Egerváry) Egy mátrix elemei közül maximum annyi független nulla jelölhető ki, amennyi vonallal minimum lefedhető a mátrix összes nullája 39 .

A fenti ábrán a tiltó vonalak lefedik ugyan valamennyi nullát, de rögtön látható, hogy az első két sor és az utolsó oszlop nélkül, a maradék 5 vonal is elegendő:

LM3 MM5 MM20 MN0

1 0 3 0 3

1 1 0 5 5

0 2 4 1 2

4 1 6 4 0

PPO PP PP Q

Erre az öt vonalra azonban mintha szükség lenne. Ha ez így van, akkor a tétel szerint nem választottuk ki a maximális számú független nullát. A tétel (annak bizonyítása) egyben módszert ad a minimális számú fedővonal megkeresésére. Használjuk ezt.

39

A bizonyítás megtalálható például Krekó B. idézett könyvében az 536-540. oldalakon.

56

A harmadik oszlop és a negyedik sor nem tartalmaznak független nullát. Fedjük le azokat a sorokat, amelyek harmadik eleme 0, és azokat az oszlopokat, amelyek negyedik eleme 0. Az így lefedett vonalak száma esetünkben 2:

LM3 MM5 MM20 MN0

1 0

1 1

0 2

3 0 3

0 5 5

4 1 2

O PP 6P P 4P 0 PQ 4 1

Hagyjuk el a független nullákat nem tartalmazó sort-oszlopot és a segítségükkel lefedett vonalakat:

LM 3 MM5 MM MN0

0 2

2

O P1P PPP P 0Q

4

Az így előállított almátrixban az első oszlopban és a második sorban nincs független nulla, de a második sorban egyáltalán nincs nulla. Így csak egy új fedővonalat húzhatunk az utolsó sorba:

LM 3 MM5 MM M N0

0 2

2

O PP PP PP 0Q 4 1

Ismét törölve az érintett vonalakat olyan almátrixot kapunk, amiben már csak egy és következésképpen független nulla maradt, amit egy utolsó 4-dik vonallal lefedhetünk:

LM MM MM NM

0 2

O P1P PP PP Q

4

Nézzük meg most már a teljes minimális lefedést:

LM3 MM5 MM20 MN0

1 0

1 1

0 2

3 0 3

0 5 5

4 1 2

57

O PP 6P P 4P 0 PQ

4 1

Tehát a minimális lefedés megtalálásának algoritmusa: 1. A foglalt vonalak fokozatos letiltásával kijelöljük a független nullák egy lehetséges, tovább nem bővíthető halmazát. Megkeressük azokat a sorokat és oszlopokat, amelyekben nincs független nulla. 3. Ha ilyen nincs, akkor megtaláltuk az eredeti feladat optimális megoldását, a fedővonalak megkeresésére nincs szükség. Kilépés Egyébként 4. Start 5. A független nullákat nem tartalmazó vonalakon (amiket célszerű megjelölni) az ott levő nullákra merőleges fedővonalakat rakunk. Ha nincs rajtuk nulla akkor megtaláltuk valamennyi fedővonalat - Vége Egyébként 6. Töröljük a mátrixból az előző lépésekben érintett vonalakat és vissza a Start-hoz. Egy fontos részlet tisztázása végett rakjuk félre eredeti számpéldánkat, és vegyünk elő egy másikat 40 . Tekintsük a következő mátrixot, amiben már kijelöltünk egy nem bővíthető független nulla halmazt 6 elemmel:

LM0 MM0 MM10 MM1 MM1 N1

1 1 0 0 1 1

1 1 0 1 0 1

0 1 1 1 0 1

0 1 1 1 0 0

0 1 1 1 0 0

0

0

1

1

1

OP PP PPP PP 1PQ 0 0 1 1 0 1

Az algoritmust alkalmazva 7 lefedő vonalat találunk:

LM0 MM0 MM10 MM1 MM1 N1

1 1 0 0 1 1 0

1 1 0 1 0 1 0

0 1 1 1 0 1 1

0 1 1 1 0 0 1

0 1 1 1 0 0 1

0 0 1 1 0 1 1

O PP PP PP PP PQ

Tehát a König-Egerváry tétel szerint nem a maximális számú független nullát jelöltük ki. Ennek felismeréséhez meg sem kell számolni a független nullákat és a fedővonalakat, mivel biztos jel a negyedik sor második nullája, amely független létére két fedővonal kereszte-

40

Ami szintén Krekó B. könyvéből való.

58

ződésében van. Nézzük meg a következő „lépcsőt“ (aminek szükségszerű létezése bizonyítható). Ebben a lépcsőben a sarkokon eggyel több meg nem jelölt nulla van, mint megjelölt, viszont ha felcseréljük szerepeiket, az új megjelölt nullák is függetlenek lesznek.

LM0 MM0 MM10 MM1 MM1 N1

1 1 0 0 1 1 0

1 1 0 1 0 1 0

0 1 1 1 0 1 1

0 1 1 1 0 0 1

0 1 1 1 0 0 1

0 0 1 1 0 1 1

O PP PP PP PP PQ

Összefoglalva: Ha kevesebb független nullát vettünk fel, mint a minimális lefedő vonalak száma, ezt az mutatja, hogy legalább egy független nulla a lefedő vonalak metszéspontjában van. Ez a független nulla egy lépcső egyik sarokpontja. A sarokpontok között eggyel több függő nulla van mint független, de ezek szerepei felcserélhetőek, így a független nullák száma növelhető. Most pedig visszatérhetünk az eredeti számpéldánkhoz. Abban a König-Egerváry tétel szerint maximális számú független nullát találtunk, de kevesebbet a kelleténél. A nullákat lefedő minimális vonalak segítségével javíthatunk a helyzeten. Keressük meg a lefedetlen elemek közül a legkisebbet. Ez nem lehet 0, tehát pozitív szám lesz. Vonjuk ki ezt minden lefedetlen elemből és adjuk hozzá a kétszer lefedett elemekhez. Az egyszer lefedett elemeket változatlanul hagyjuk. Ez nyilván azt jelenti, hogy a korrekciót tulajdonképpen nem fedővonal soronként (kivonás) és fedővonal oszloponként (hozzáadás) végeztük el, tehát az első tétel szerint az optimális megoldás nem változik, csupán a célfüggvény értékét kell tovább módosítani. Bizonyítható, hogy a célfüggvény értékéhez a legkisebb lefedetlen elem annyiszorosát kell hozzáadni, ahánnyal kevesebb független nulla van a kelleténél. Tehát legyen ε=1 a legkisebb lefedetlen elem, s így a korrigált költségmátrix:

LM3 MM4 MM01 MN0

2 0 4 0 4

1 0 0 4 5

0 1 4 0 2

OP P 6P P 3P 0PQ

4 0

Erre az új mátrixra alkalmazzuk az előző algoritmusokat:

LM3 MM4 MM01 MN0

2 0 4 0 4

1 0 0 4 5

0 1 4 0 2

4 0 6 3 0

O PP PP PP Q

Ebben az esetben már meg is találtuk az optimális hozzárendelést. Ennek költsége az utolsó korrekciókkal 13+1=14.

59

Általában lehet, hogy a megtalált független nullák száma nem csupán eggyel kisebb a költségmátrix rendjénél, s ilyenkor a megoldáshoz csak több lépés vezet el. Ezek összefoglalva a következők: 1. A sorok és az oszlopok korrekciója a minimális elemek kivonásával. A célfüggvény értéke = Σsorkorrekciós konstans + Σoszlopkorrekciós konstans 2. Start-0 3. A foglalt vonalak fokozatos letiltásával kijelöljük a független nullák egy lehetséges, tovább nem bővíthető halmazát. 4. Megkeressük azokat a sorokat és oszlopokat, amelyekben nincs független nulla. Ha ilyen nincs, akkor megtaláltuk az eredeti feladat optimális megoldását, Vége. Egyébként 5. Start-1 a minimális lefedés megtalálásához 6. A független nullákat nem tartalmazó vonalakon (amiket célszerű megjelölni) az ott levő nullákra merőleges fedővonalakat rakunk. Ha nincs rajtuk nulla akkor megtaláltuk valamennyi fedővonalat - ugrás a Start-2-höz. Egyébként 7. Töröljük a mátrixból az előző lépésekben érintett vonalakat és vissza a Start-1-hez. 8. Start-2 a valóban maximális független nullák megtalálásához 9. Ha nincs a fedővonalak metszéspontjában kijelölt független nulla, akkor a minimális lefedés vonalszáma megegyezik a kijelölt független nullák számával, ugrás a Start-3hoz. Egyébként 10. A fedővonalak metszéspontjában levő független nullához tartozó lépcsőben felcseréljük a független és a nem független nullák szerepét. Ezzel eggyel nő a független nullák száma. Vissza a 4.-hez 11. Start-3 a hiányzó független nullák előállításához 12. Megkeressük a le nem fedett elemek minimumát (ε) és azt levonjuk az összes le nem fedett elemből, hozzáadjuk az összes kétszer lefedett elemhez. Az egyszer lefedett elemeket változatlanul hagyjuk. A célfüggvény értéke az ε annyiszorosával nő, amennyivel kevesebb független nulla van az optimálisnál. Vissza a Start-0-hoz B.) A SZÁLLÍTÁSI FELADAT

Nézzük meg a fejezet elején említett szállítási feladatot, hogy azt hogyan lehet a „magyar módszerrel“ megoldani? Magának a szállítási feladatnak a modellje a következőképpen néz ki. A célfüggvény a költségmátrix elemeiből épül fel: m

n

∑∑c x ij

ij

→ min

i =1 j=1

60

A szállítási terv az összes árukészlet elszállítását és az összes megrendelés kielégítését kell, hogy megoldja: n

∑x

b

g

b

g

ij

= a i i = 1,2,..., m

ij

= b j i = 1,2,..., n

j=1 m

∑x i =1

és természetesen érvényes a nem negativítási feltétel: x ij = X ≥ 0

A teljes feladat tehát

R| ∑ ∑ c x → min || |S∑ x = a bi = 1,2,..., mg || || ∑ x = b bi = 1,2,..., ng X≥0 T m

n

ij

ij

i =1 j=1

n

ij

i

j=1 m

ij

j

i =1

Ez feltűnően hasonlít a hozzárendelési feladathoz. Vajon csak hasonlít? Tekintsük a következő hozzárendelési feladatot. Egy taxi társulás két garázzsal két kerületet lát el. Az üres kilométerek száma a következő: A kerület

B kerület

1. garázs

12

34

2. garázs

23

6

Ez teljesen megfelel a korábban már tárgyalt igen egyszerű hozzárendelési feladatnak. Csakhogy tegyük fel, az 1. garázsban nem egy, hanem 3, a 2. garázsban pedig nem egy, hanem 4 gépkocsi van. Az A kerületben öten, a B kerületben ketten várnak kocsira. Ekkor a feladat a következő hozzárendelési modellel írható le: A költségmátrix

LM12 MM12 MM1223 MM23 MM23 N23

12 12 12

12 12 12

12 12 12

12 12 12

34 34 34

23 23 23 23

23 23 23 23

23 23 23 23

23 23 23 23

6 6 6 6

61

OP PP P 6P 6P P 6P 6 PQ

34 34 34

A modell

F ∑ ∑ 12 ⋅ x I + F ∑ ∑ 34 ⋅ x I + F ∑ ∑ 23⋅ x I + F ∑ ∑ 6 ⋅ x I → min GH JK GH JK GH JK GH JK ∑ x = 1 b j = 1,2,...,7g ∑ x = 1 bi = 1,2,...,7g 3

5

3

7

7

ij

i =1 j=1

5

7

ij

i =1 j= 6

7

ij

i = 4 j=1

ij

i = 4 j= 6

7

ij

i =1 7

ij

j=1

X≥0 Legyen 3

5

∑ ∑ x ij = χ11 , i =1 j=1

3

7

∑ ∑ x ij = χ12 , i =1 j= 6

7

5

∑ ∑ xij = χ 21 , i = 4 j =1

7

7

∑∑x

ij

= χ 22

i = 4 j= 6

Ekkor az előző modell felírható a következő ekvivalens alakban: 12 χ11 + 34 χ12 + 23χ 21 + 6χ 22 → min χ11 + χ12 = 3 χ 21 + χ 22 = 4 χ11 + χ 21 = 5 χ12 + χ 22 = 2 χ = χ ij ≥ 0 Ez viszont egy szabályos szállítási feladat. Tehát a hozzárendelési és a szállítási feladatok modelljeinek hasonlósága lényegi. A szállítási feladatban szereplő ai és bj adatok az ekvivalens hozzárendelési feladat multiplicitásai („sokszorosságai“) Ez azt jelenti, hogy a hozzárendelendő egységek egy-egy csoportja költség szempontjából azonos. Mindennek megfelelően a „magyar módszer“ fenti algoritmusát minden további nélkül alkalmazhatjuk a szállítási feladatokra is, csupán azt kell figyelembe venni, hogy egy cellában valójában nem egy szám van, hanem a cellához tartozó multiplicitások szorzatszorosa - persze valamennyi azonos. Így az a cella, amelyben a szállítási feladat hagyományos táblázatában 0 áll, ott a hozzárendelési mátrixban a következő van:

0 0 ... 0 0 0 ... 0 a -szer ... ... ... ... i 0 0 ... 0 bj -szer Természetesen, ha ezt a cellát mint független nullát jelöljük meg, akkor valójában a két multiplicitás közül a kisebbik számú független nullát jelöltünk meg.

62

ALLOKÁCIÓS MODELLEK KÜLÖNLEGES TEREKBEN (NEGYEDIK ELŐADÁS) 1. NEM HAGYOMÁNYOS ALLOKÁCIÓS PROBLÉMÁK

A lineáris (és nem lineáris) programozás hagyományos feladataira az a jellemző, hogy a döntési halmaz és a célfüggvény leírásához számokkal jellemezhető mennyiségeket használunk fel. Például a korlátokat megszabó rendelkezésre álló erőforrások valamilyen mértékegységben megadott, de egy-egy számmal jellemezhető mennyiségek (b1 tonna cement, b2 darab tégla, stb.), ugyanígy a maximizálandó (minimizálandó) célfüggvény is mértékegységgel ellátott szám (z darab felépítendő ház, y forint költség stb.). A gyakorlatban azonban más típusú feladatok is előfordulnak. A korlátozó feltételek időben változhatnak és ennek megfelelően változhat az optimális döntés is. Lehetséges egyszerre több cél egyidejű optimalizálásával próbálkozni. Ilyen és ehhez hasonló problémákra az LP (és/vagy az NLP) hagyományos módszerei vagy csak nagy nehézségekkel, vagy egyáltalán nem alkalmazhatóak. A közkeletű tankönyvek két részterületen ismertetnek koránt sem kimerítő - megoldási lehetőségeket: a parametrikus programozás bizonyos esetekben alkalmas a változó feltételű feladatok megoldására, valamint történtek lépések a többcélfüggvényes programozás problémájának megoldására. Mindamellett ezek a feladatok rendelkeznek bizonyos közös vonásokkal, ami lehetővé teszi sokkal egységesebb kezelésüket. A.) TÖBB CÉLFÜGGVÉNYES FELADAT.

A legegyszerűbben felírható és talán legnehezebben megoldható nem hagyományos feladat a több célfüggvényes feladat. Ennek a feladatnak a döntési (megengedett megoldások) halmaza nem különbözik a hagyományos feladatokétól. Általában valamilyen korlátozó feltételek (szűkösen rendelkezésre álló erőforrások) által behatárolt halmazról van szó, amely szerencsés esetben (a lineáris korlátok esetén mindig szerencsés az eset) konvex struktúrájú. A problémát az optimalizálandó cél jelenti. Ez ennél a feladat-típusnál ugyanis nem írható le egy (cél-)függvénnyel. Összetett célról van itt szó, ahol több különböző kritériumot kell maximalizálni és/vagy minimalizálni. A feladat matematikailag a következő alakú: f k ( x ) → max ( k=1,2,...r ) f l ( x ) → min

( l=1,2,...p )

x∈X ahol

r a maximalizálandó célok száma p a minimalizálandó célok száma x a döntési alternatíva X a döntési halmaz és valamennyi fk illetve fl függvény az X halmazt a valós számok R terébe képezi le.

63

bg

Nyilván minden fl függvényre igaz, hogy ha fl x → min akkor és csak akkor − fl x → max , ezért a feladat felírható egyszerűbben is, anélkül, hogy ez az általánosság rovására menne:

bg

⎡ f1 ( x ) ⎤ ⎢ ⎥ f ( x ) = ⎢ ... ⎥ → max ⎢⎣ f s ( x ) ⎥⎦ x∈X

(f : X → Rs )

ahol s az összes célfüggvény száma. A megoldásban az a problematikus, hogy az s-elemű vektorok Rs euklideszi tere úgynevezett részben rendezett tér a szokásos, komponensenkénti rendezéssel. E szerint a rendezés szerint az a vektor a nagyobb, amelyik dominálja a másikat, azaz amelyiknek egyik komponense sem kisebb a másik megfelelő komponensénél, de legalább egy nagyobb. Könnyen belátható, hogy ez a rendezés eleget tesz a rendezés szokásos axiómáinak, az antireflexívitás és a tranzitívitás axiómáinak: R1.)

(Antireflexívitás) Ha x, y∈Rs és x > y, akkor nem lehet x = y

R2.)

(Tranzitivítás) Ha x, y, z∈Rs és x > y illetve y > z, akkor x > z

Ugyanakkor azt is látni kell, hogy ezzel a rendezéssel nem lehet összehasonlítani bármely két vektort, hiszen ha egyik sem dominálja a másikat, akkor nem összehasonlíthatóak. Így azután a fenti feladatban nem biztos, hogy az f(X)⊆Rs halmaznak van domináns, az összes többivel összehasonlítható és azoknál nagyobb eleme, azaz maximuma. Vagyis a többcélú feladat hagyományos értelmű megoldása 41 általában kérdéses. B.) PARAMETRIKUS PROGRAMOZÁS

Gyakorlati feladatoknál gyakran előfordul, hogy sem a döntési halmaz, sem a célfüggvény nem adható meg állandó (determinisztikus) paraméterekkel. Vagy azért, mert például a feltételek időben változnak, vagy azért mert egyáltalán ezek a feltételek csak valószínűségi változókkal írhatóak le, nem határozható meg a paraméterek pontos értéke. LP feladatok esetében viszonylag jól kidolgozott ezeknek a szituációknak a speciális közelítése lineáris parametrikus függvényekkel. Legyen adott egy determinisztikus LP feladat standart alakban: c T x → max Ax ≤ b x≥0

Ennek (lineáris) parametrikus változatát az rc rb és RA vektorok illetve mátrix és a t parametrikus változó bevezetésével alkothatjuk meg 42 :

41 A többcélfüggvényes programozás kérdéseiről lásd például Matematika üzemgazdászoknak Operációkutatás II. (szerk. Dr. Csernyák L.) 153-162. oldalak 42

A parametrikus programozásról lásd ugyanott 116-127. oldalak, illetve Krekó idézett könyvében 135-145. oldalak.

64

bc + r t g x → max b A + R t gx ≤ bb + r t g T

c

A

b

x≥0

Természetesen tovább általánosítható a dolog, ha a paraméterek a parametrikus változónak nem lineáris függvényei. Ezzel azonban a nehézségek nagyot nőnek. Azonban itt is fel kell valamire figyelni. Legyen F a szakaszosan folytonos függvények 43 tere. Mivel két szakaszosan folytonos függvény összege is, valamint egy szakaszosan folytonos függvény tetszőleges többszöröse is szakaszosan folytonos (a műveletek a független változó azonos értékeire kell érteni - ezt nevezik természetes értelmezésnek), ezért nyilvánvaló, hogy F egy lineáris tér 44 . Ebben a térben értelmezhető a természetes (pontonkénti) összehasonlítás fogalma, amelynek megfelel egy a dominancián alapuló „természetes“ rendezési elv: két szakaszosan folytonos függvény közül az a nagyobb, amely egyik pontjában sem kisebb a másiknál, de legalább egy pontban nagyobb. Ez kielégíti a részben rendezés két axiómáját: R1.)

(Antireflexívitás) Ha f, g ∈F és f > g akkor nem lehet f = g

R2.)

(Tranzitívitás) Ha f, g, és h ∈F és f > g illetve g > h, akkor f > h Nyilván itt is problémát okozhatnak az össze nem hasonlítható függvények. Összességében ez a tér struktúrájában az euklideszi térrel közös vonásokkal bír.

C.) FELADATOK, AMELYEK TELJESEN KILÓGNAK A HAGYOMÁNYOS LP KERETEIBŐL

Bemutatunk két feladatot, amelyek közeli rokonságban vannak az előbb ismertettekkel, s mégsem oldhatóak meg egyszerűen az LP hagyományos eszközeivel. 1. FELADAT.

Egy kereskedelmi hálózat m boltból és n beszállító üzemből áll. A hálózat p különböző árucikk forgalmazásával foglalkozik. Az i-dik bolt a kereslet statisztikai felmérése alapján a k-ik áruból aik mennyiséget rendel (i=1,2, ... m; k=1,2, ... p). A j-ik üzem a k-ik áruból maximálisan bjk mennyiséget tud szállítani (j=1,2, ... n). A k-ik áru egy egysége az i-dik boltba a j-ik üzemből cijk költséggel szállítható. A feladat olyan szállítási terv összeállítása, ahol valamennyi áru eljut a megrendelőkhöz, miközben a teljes szállítási költség minimális.

A feladat modelljének felírásához vezessük be a következő jelöléseket: a i = a ik

k =1,2 ,..., p

; b j = b jk

k =1,2 ,..., p

c ij = c ijk

k =1,2 ,..., p

; x ij = x ijk

k =1,2 ,..., p

c ij ox ij = c ijk x ijk

k =1,2 ,..., p

Itt xij a kiszámítandó i-j viszonylatú kontingens p-elemű vektora. 43 Szakaszosan folytonos (deriválható, stb.) az a függvény, amely legfeljebb megszámlálható számú pontban nem rendelkezik a jelzett tulajdonsággal 44

Egészen pontosan az említett tények csak az F tér affinitását igazolják, de számunkra most lényegtelen az affinitás és a lineáritás közötti különbség.

65

A modell a következő lesz: m

n

∑∑c

ij

ox ij → min

i =1 j =1

m

∑x

= b j j = 1,2,..., n

ij

= ai

n

∑x

b g bi = 1,2,..., mg

ij

i =1

j =1

b

x ij ≥ 0 i = 1,2,..., m; j = 1,2,..., n

g

A feladat szemmel láthatólag emlékeztet a szállítási feladat klasszikus alakjára. Ugyanakkor a célfüggvény értéke itt nem számértéket vesz fel, hanem p elemű vektor fejezi ki. Ez viszont a több célfüggvényű feladatra emlékeztet. Ugyanakkor a feladat ekvivalens p darab hagyományos szállítási feladattal (minden árura külön-külön felírva). Ez egyrészt azt jelenti, hogy szemben a több célfüggvényes problémával, itt biztosan létezik optimális megoldás, másrészt viszont ennek megtalálásához p darab szállítási feladatot kellene megoldani, ahol a p akár több ezres nagyságrendű is lehet. Gyanítható, hogy léteznie kell valami egyszerűsítő fogásnak. 2. FELADAT

Egy mezőgazdasági vállalkozás m különböző primőr zöldséget termeszt n különböző erőforrás felhasználásával. A primőr szezonban (T=[t0,ts]) a termékek termelésének feltételei előre láthatóan az idő függvényében alakulnak. Legyen az i-dik termék ára ci(t) (i=1,2,...,m; t∈T), a j-ik erőforrás készlete bj(t) (j=1,2,...,n), az i-dik termék igénye a j-ik erőforrásból aij(t). A feladat olyan termelési terv összeállítása, amely folyamatosan maximális bevételt eredményez 45 .

A feladat matematikai alakja:

∑ c b t gx b t g → max m

i

i

i =1

m

∑a i =1

ij

b t gx bt g ≤ b bt g b j = 1,2,..., ng x b t g ≥ 0 bi = 1,2,..., mg i

j

i

t ∈T

Alakját tekintve ez a feladat is emlékeztet a hagyományos LP feladatra. A célfüggvény értéke itt a T szakaszon értelmezett (szakaszosan folytonos) függvények közül kerül ki. Ez ismét a többcélúságra hasonlít, ám - szemben a szokásos többcélfüggvényes feladatokkal - itt is garantált a maximum létezése, feltéve, hogy a t minden konkrét értéke mellett keletkező közönséges LP feladat megoldható. Csakhogy ez az elv itt semmiképpen nem ad valóságos megoldási algoritmust a kezünkbe, hiszen a t kontinuum sokaságú értéket vehet fel. Másfelől viszont a parametrikus programozás tapasztalatai, az LP érzékenységi vizsgálatainak eredményei sejtetik, hogy itt is van kivitelezhető megoldás.

45

Itt figyelmen kívül hagyjuk azt a problémát, hogy egy ilyen terv az egész időszakra is maximalizálja-e az árbevételt. Vagyis nem bonyolódunk dinamikus vizsgálatokba.

66

2. A RÉSZBEN RENDEZETT LINEÁRIS TEREKRŐL 46

Az előzőekben ismertetetett feladatokban olyan terek elemei szerepeltek számok helyett, amelyek igencsak különbözőfélék és mégis van bennük valami közös. Ilyen típusú feladatokat megfogalmazhatunk a következő lineáris terek segítségével: • • • •

Az n elemű vektorok euklídeszi tere; Szakaszosan folytonos függvények tere; Szakaszosan deriválható függvények tere; (Valamilyen módon) integrálható függvények tere; stb.

Ezeknek a tereknek, mint azt láttuk, a következő közös tulajdonsága van: mindegyikben megadható egy természetes rendezés. Az n elemű vektorok euklideszi terében két vektor közül az a nagyobb, amelyik dominálja a másikat, vagyis egyik eleme sem kisebb a másik vektor megfelelő eleménél, de legalább egy nagyobb. A különböző függvény-terekben hasonlóan értelmezhető a rendezés, csak ott az értelmezési tartomány pontjaiban mért függvényértékek alapján pontonként elvégzett összehasonlítással. Ezek a rendezések nem teszik lehetővé, hogy a terek bármely két elemét összehasonlíthassuk, azért nevezik az ilyen struktúrákat részben (más forrásokban - félig) rendezett lineáris tereknek 47 . Ezeknek a tereknek a vizsgálata a matematika egyik fontos részterülete. Ezen a területen az első vizsgálódások a magyar Riesz Frigyes nevéhez fűződnek. Az elmélet alapos elemzését L.V. Kantorovics és munkatársai végezték el. A nemzetközi szakirodalom egyaránt használja a Riesz-, illetve a K-tér elnevezést a részben rendezett terek legfontosabb osztályára. A fent megnevezett terek mind ebbe az osztályba tartoznak. Nézzük meg azokat a tulajdonságokat, amelyek ezt az osztályt jellemzik - mondjuk az n dimenziós euklideszi lineáris vektortér (Rn) példáján. A tetszőleges véges számú n elemű vektorokból álló halmazhoz mindig hozzárendelhető legalább egy felső korlát, azaz olyan n elemű vektor, amely nagyobb a halmaz bármelyik eleménél (de legalább is egyenlő vele). Ez úgy látható be, hogy tudjuk, bármelyik véges számhalmaznak van felső korlátja, és így a véges halmazhoz tartozó vektorok azonos indexű koordinátából alkotott halmaznak is van. A halmaz felső korlátja az ezekből a felső korlátokból alkotott vektor lesz. Mivel egy véges számhalmaz legkisebb felső korlátja (supremuma) is mindig létezik 48 , azért a vektorokból alkotott halmaznak is mindig van supremuma:

46

Ez az alpont nem megtanulandó, csak az érdeklődő olvasó számára ad egy kis ízelítőt a matematika e Magyarországon kevéssé ismert fejezetéből. A továbbiak csupán néhány egyszerűbb fogalmat tartalmaznak mindebből.

lq

47

A valós számegyenest a nagyság szerinti rendezés teljesen vagy lineárisan (sorba) rendezi.

48

A supremum nem csak véges halmazokra értelmezhető. Véges számhalmazok esetében egyébként

lq

sup a i = max a i , ami vektorhalmazokra már nem igaz (egy rendezett halmaz maximális eleme per definíció eleme a halmaznak - egy vektorokból álló halmaznak nem mindig van maximális eleme, például, ha a halmaz mindössze két, össze nem hasonlítható elemből áll, supremuma azonban ekkor is van).

67

R|L a OU| LM supla qOP MMa PP| Msupla qP | supla q = sup S = ||MM ... PPV|| MM ... PP TNa QW MNsupla qPQ i

i

i1

i

i2

i

in

i

i1

i2

i

in

Ugyanezzel a gondolatmenettel látható be, hogy bármely véges számú n elemű vektorokból álló halmazhoz hozzárendelhető egy legnagyobb alsó korlát (infimum) is. Két vektor (a és b) esetében szokás a következő jelöléseket használni 49 :

l q

l q

sup a , b = a ∨ b; inf a , b = a ∧ b Legyen E valamely vektorok halmaza. Az olvasó könnyen bebizonyíthatja, hogy

b g R|supbαEg ha α ≥ 0 α sup E = S |Tinf bαEg ha α < 0 a + sup E = sup a + E

ahol az a+E olyan halmazt jelent, ahol E minden eleméhez hozzáadtuk a-t, az αE pedig olyant, ahol E minden elemét megszoroztuk α-val. Azt sem nehéz igazolni, hogy a + b = a ∧ b + a ∨ b . Egy vektor mindig felbontható két nem negatív vektor különbségére:

a = a 1 − a 2 ahol a 1 , a 2 ≥ 0 A bizonyíthatóan legkisebb ilyen vektorpáros a következő módon képezhető:

a = a + − a − , ahol a +i =

RSa ha a ≥ 0 és a = RS0 T0 ha a < 0 T− a i

i

ha a i ≥ 0

i

i

i

ha a i < 0

a+ az a vektor pozitív, a- az a vektor negatív része. Nyilván

b g = b−a g ∨ 0

a + = a ∨ 0 és a - = − a

+

Az a vektor abszolút értéke (nem tévesztendő össze a vektor hosszával!) az a vektor pozitív és negatív részeinek összegével egyenlő:

a = a+ + a− Nem nehéz belátni, hogy a vektor abszolút értéke a koordinátáinak abszolút értékéből felépülő vektor. Ha két vektor azonos indexű koordinátái egyidejűleg nem különbözhetnek nullától, akkor a két vektor diszjunkt. Könnyű belátni, hogy a és b akkor és csak akkor diszjunktak, ha

a ∧ b = 0. A diszjunktság viszonyát adb felírással jelöljük. Könnyű igazolni, hogy egy vektort a fentebb jelzett módon felbontó két nem negatív vektor akkor és csak akkor diszjunktak, ha azok az eredeti vektor pozitív és negatív részei, vagyis ha 49

Hamarosan látni fogjuk, hogy ez a jelölési mód nem véletlenül hasonlít a logikai „vagy“ (OR) és „és“ (AND) műveletek elterjedt jelölésére.

68

a = a 1 − a 2 , ahol a 1 , a 2 ≥ 0 , és a 1da 2 akkor a 1 = a + és a 2 = a -

.

Az euklideszi teret sokféleképpen lehet rendezni. Az eddig tárgyalttól eltérő rendezés például az úgynevezett lexikografikus rendezés, amely szerint két vektort az első elem szerint hasonlítunk össze, vagyis az a vektor a (lexikografikusan) nagyobb, amelyiknek az első eleme nagyobb. Ha az első elemek egyenlőek, akkor a második elemeket vetjük össze és így tovább. Az elnevezés érthető, hiszen a lexikonok, szótárak szócikkei is ezen elv alapján vannak sorba rendezve. Ebből is látszik, hogy a lexikografikus rendezés nem részben, hanem teljesen rendezi az euklideszi teret. Mindamellett ez a rendezés „rosszabb“, mint a „természetes“ rendezés. Az utóbbi ugyanis - szemben az előbbivel - kielégíti az úgynevezett Arkhimedesz-elvet: DEFINÍCIÓ.

(Arkhimedesz elve) Legyen a egy nem negatív vektor. Az {na}n=1,2... sorozat csak úgy lehet felülről korlátos, ha a=0.

Az olvasóra bízzuk annak bizonyítását, hogy ezt az elvet a „természetes“ rendezés kielégíti, a lexikografikus viszont nem. Az n elemű vektorok között jónéhány olyan van, amely csak és kizárólag a 0 vektorral diszjunktak. Ezek az euklideszi tér egységelemei. Nem minden részben rendezett térnek van meg ez a tulajdonsága, de példáinknak igen. Ezek a terek az egységelemes vagy unitér terek. Célszerű a végtelen sok egységelem közül egyet kiválasztani. A vektortérben kézenfekvőnek tűnik erre a célra a csupa egyesből álló összegző vektort választani. Az egységelem jele u. Megegyezésünk szerint tehát példánkban u=1. Az egységelemet „fel lehet szabdalni“. Egységdarabnak nevezzük azokat az e vektorokat, amelyekre igaz az e∧(u-e)=0 összefüggés. Nyilván, ha e egységdarab, akkor

0≤e≤u Azt sem nehéz igazolni, hogy a 0 és az u maguk is az egységdarabok közé tartoznak. A mi megegyezésünk szerint példánkban az egység darabok a különböző csak 1 és 0 komponenseket tartalmazó vektorok lesznek. Az unitér tér összes vektora előállítható az egységdarabok lineáris kombinációjaként, ezért az egységdarabok halmazát az unitér tér (rendezési vagy háló-)bázisának nevezik. Ez a bázis semmiképpen nem azonos a lineáris algebrában megismert bázissal, jóllehet, ha az összegző vektort választottuk egységelemnek, akkor a triviális bázis (az egységvektorok) a rendezési bázis részhalmazát alkotják. Feltétlenül meg kell még jegyezni, hogy az egységdarabok a ∧ és ∨ műveletekkel valamint az e = u − e komplementer képzési szabállyal Boole-algebrát alkotnak, ami magyarázatot ad a supremum és az infimum logikai jelekkel való ábrázolására. Állításunk igazolását ezúttal is az olvasóra bízzuk. A rendezési bázis segítségével újabb hasznos fogalmakat definiálhatunk. Legyen E egy vektorokból álló halmaz. A Riesz-tér mindazon elemei alkotják E diszjunkt kiegészítését, amelyek E valamennyi elemével diszjunktak. Jelben Ed. Nem nehéz belátni, hogy ha a és b elemei Ed-nek akkor bármely α és β számra αa + βb ∈E d , vagyis Ed az eredeti tér lineáris altere. Természetesen ez igaz az Ed diszjunkt kiegészítésére is, amit Edd-vel jelölünk. Ez a lineáris altér egy bizonyos szempontból a legszűkebb, ami tartalmazza az E halmazt, és az E által kifeszített komponens altérnek vagy sávnak nevezik. Az elnevezések magyarázatához a rendezési bázis vezet el bennünket. 69

Legyen E={a} az a vektorból álló egy elemű halmaz. Ekkor Edd=Xa az a vektor által kifeszített komponens altér vagy sáv. Tekintsük mindazokat az egységdarabokat, amelyek diszjunktak az a vektorral. A rendezési háló Boole-algebra mivoltából következik, hogy ezeknek az egységdaraboknak a supremuma egyik lesz közülük, tehát szintén az a vektorral diszjunkt. Nem nehéz belátni, hogy ennek az egységdarabnak a komplementere szintén az Xa komponens alteret fogja kifeszíteni. Ezzel beláttuk, hogy a rendezési bázis elemei feszítik ki az összes lehetséges komponens alteret. A mi példánkban ez azt jelenti, hogy az egységdarabok alkotják a komponens alterek „karakterisztikus“ vektorait, amennyiben egy komponens altér valamennyi elemének azok a komponensei különbözhetnek csak 0-tól, amelyek azonos indexűek az egységdarab 1 értékű komponenseivel. Legyen például

y

eT=[1,1,0,1,0,0,0]

az R6 euklideszi tér egyik egységdarabja. Ekkor

aT = [ 4,12, 0, 234, 0, 0, 0] ∈ X e b T = [32, 0, 0, 0.02, 0, 0, 0] ∈ X e

1

de cT = [ 4,12, 2, 234, 0, 0, 0] ∉ X e x

11. ábra Egységdarab a szakaszosan folytonos függvények terében y

1

x

12. ábra Az előbbi egységdarab által kifeszített sáv egy eleme

Ebből a példából jól látható, miért nevezik a komponens alteret komponens altérnek. Az olvasó mindazt, amit eddig a Riesz-terekről az euklideszi tér példáján elsajátított, könynyűszerrel alkalmazhatja a többi felsorolt példa-térre is. A komponens altér „sáv“ elnevezése világossá válik, ha például a szakaszosan folytonos függvények terében gondolkodunk. Itt egységelemnek választható bármely függvény, ami legfeljebb véges számú pontban vesz fel 0 értéket. Célszerű a minden pontban 1 értékű konstans függvényt választani egységnek. Ekkor a rendezési bázis elemei - az egységdarabok az értelmezési tartomány összes lehetséges kompakt részhalmazainak karakterisztikus függvényei 50 lesznek. Az egyszerűség kedvéért tekintsünk egy néhány zárt intervallumból álló ilyen halmazt (11. ábra) Az egységdarab által kifeszített sáv elemei olyan függvények, amelyek csak az

50

Egy halmaz részhalmaza karakterisztikus függvényének értéke 1 a részhalmaz elemei felett és 0 a halmaz részhalmazon kívüli elemei felett.

70

egységdarab által jellemzett kompakt részhalmaz felett különbözhetnek a 0-tól. A 12. ábráról világosan látszik a „sáv“ elnevezés értelme. Azt a gondolatmenetet, amellyel a komponens alterek fogalmát bevezettük bizonyos értelemben meg is fordíthatjuk. Egy a vektornak az X1 komponens altéri vetülete alatt azt a vektort értjük, amely a komponens altér eleme és minden nem 0 komponense azonos az a vektor megfelelő komponensével. A vetület jele: prX 1 a . Ha nyilvánvaló a vetületképzés iránya, akkor annak feltüntetése el is hagyható. A vetületképzést tisztán a rendezési relációval is lehet definiálni: prX 1 a = sup {b ( b ∈ X1 ; b ≤ a} ha a ≥ 0 ,

illetve tetszőleges a vektorra: prX 1 a = prX 1 a + − prX 1 a − , vagyis például a függvényterekben a vetület az adott pozitív függvénynél a sávban kisebb valamennyi függvény felső burkoló görbéje. A vetületképzés (vetítés) operátora lineáris és rendezéstartó, azaz:

b

g

pr αa + βb = α ⋅ pr a + β ⋅ pr b a > b → pr a > pr b Ezen kívül a akkor és csak akkor eleme X1-nek ha prX 1 a = a , illetve akkor és csak akkor eleme X1d − nek , ha prX 1 a = 0 . Végül, de nem utolsó sorban a = prX 1 a + prX d a . 1

Ez az utóbbi összefüggés azt mutatja, hogy a Riesz-tér sajátosan felbontható egy komponens alterére és annak diszjunkt kiegészítésére. Mindez általánosítható: Az {Xi }i∈I komponens altér-család az X Riesz-tér felbontását adja, ha

DEFINÍCIÓ. •

{Xi }i∈I

•

A 0 kivételével nincs olyan eleme X-nek, amely

elemei páronként diszjunktak;

{Xi }i∈I

minden elemével

diszjunkt volna. Amennyiben {Xi }i∈I az X Riesz-tér felbontása, akkor minden a∈X vektorra

a = ∑ prX i a . i ∈I

A teljesség kedvéért megemlítjük - bár ennek témánkhoz nincs közvetlen köze - hogy a rendezési struktúra lehetővé teszi a sorozatok konvergenciájának az euklideszi térben megszokottól eltérő definiálását. DEFINÍCIÓ.

(o-konvergencia) Az {ai} vektorsorozat akkor konvergens a rendezés szerint (o-konvergens), ha léteznek olyan {bi} és {ci} vektorsorozatok, hogy b i ≤ a i ≤ c i minden i - re, és sup b i = a = inf c i Ebben az esetben a=o-lim ai.

l q

lq

Az o-konvergencia, illetve o-lim elnevezések az ordering (rendezési) jelzőt jelentik. A rendezés szerinti konvergencia fogalma lehetővé teszi az o-zárt és o-nyílt halmazok bevezetését is. Azt mondják, hogy az o-konvergencia o-topológiát generál a Riesz-terekben. Ez azonban, természetesen, már messze túlmutat előadásaink keretén.

71

3. LINEÁRIS PROGRAMOZÁS RÉSZBEN RENDEZETT VEKTORTEREKBEN A fentebbi példákhoz hasonló LP szerű feladatok általános elméletét L.V. Kantorovics munkatársa, A.G. Pinszker alkotta meg. Pinszker a következő feladattípusokat vizsgálta: DEFINÍCIÓ.

(LP feladatok Riesz-terekben) Legyen X egy Riesz-tér és legyen

U R max S∑ c x ∑ a x ≤ b b j = 1,2,...n g; x ≥ 0 bi = 1,2,...mgV l qT W m

xi

m

i

i =1

i

ij i

j

i

i =1

egy általános standart alakú LP feladat. Ekkor ez egy A. feladat

ha xi és bj ∈X minden i-re és j-re, a többi paraméter valós szám.

B. feladat

ha ci ∈X minden i-re, a többi paraméter és változó valós szám.

C. feladat

ha xi, ci és bj ∈X minden i-re és j-re, a többi paraméter valós szám.

D. feladat

ha minden paraméter és változó az X elemei. Az A, B, C, és D feladatok optimális megoldása az {xi} olyan értékeit jelenti, amelyek kielégítik a korlátozó feltételeket, azaz megengedettek, és a célfüggvény értéke összehasonlítható a többi megengedett {xi} értékekhez tartozó célfüggvény értékekkel, azokkal egyenlő, vagy azoknál nagyobb 51 .

A C és D típusú feladatok esetében az X tér elemei között egy szorzási műveletnek is értelmezve kell lennie. Ez lehet példáinkban a komponensenkénti illetve pontonkénti összeszorzás:

LM a OP LM b OP LM a b OP a b a b P a = M P; b = M P ⇒ a ∗ b = M MM ... PP MM ... PP MM ... PP Na Q N b Q Na b Q f = f b t g; g = gb t g ⇒ f ∗ gb t g = f b t ggb t g 1

1

1 n

2

2

2

n

n

n

n

n

A D feladat kezelése, bár a különbség nem lényegi a többihez képest, mégis meglehetősen körülményes, ezért ennek tárgyalásától eltekintünk. Ugyancsak problematikus a B feladat is, mivel az szemmel láthatólag a többcélfüggvényes feladat egyenes általánosítása. Így ennek a feladattípusnak a megoldása végső soron ugyanazokba a nehézségekbe ütközik, mint a hagyományos többcélfüggvényes feladatok. Az A és a C feladatok azonban igen jól kezelhetőnek bizonyulnak. A továbbiakban az előző alpont módszerét követve a feladatok kezelését a természetes módon részben rendezett euklideszi vektortér példáján mutatjuk be, alkalmanként megmutatva, hogy ugyanez hogyan fest a függvényterekben 52 . 51

A dolog természetéből következik ez a bonyolultnak tűnő megfogalmazás, hiszen itt nem alkalmazható az egyszerűbbnek látszó „nem kisebb“ fordulat. Ami nem kisebb, az ugyanis lehet össze nem hasonlítható is. 52 A kérdés alaposabb tárgyalását lásd Nagy András (B. Nagy András) Lineáris programozás részben rendezett vektorterekben (A.G. Pinszker eredményei) Alkalmazott Matematikai Lapok 6 (1980) 105-122. oldalak. Ugyanebben a számban található Nagy András (B. Nagy András) Realizálható LP algoritmus részben rendezett vektorterekben 123-130. oldalak.

72

A feladatok megoldásához a következő tényeket kell figyelembe venni. 1.) Ha van egy olyan E halmazunk X-ben, amelynek elemei összehasonlíthatóak X null-elemével (θ) akkor mindig megadható egy olyan f : X → R pozitív additív leképezés, amelyre

R|> 0 ha x ≥ és ≠ θ U| bx ∈ Eg f b x gS= 0 ha x = θ V |T< 0 ha x ≤ de ≠ θ|W

Az euklideszi térben ez a leképezés lehet például az összegző vektorral való skaláris szorzat. A függvényterekben a leképezés szerepét egy-egy alkalmasan megválasztott integrál-operátor játszhatja el. A szakaszosan deriválható függvények terében például a matematikai analízis kereteiben megismert határozott integrál kiválóan megfelel e célra. 2.) X mindig felbontható véges számú komponens altérre úgy, hogy X véges számú elemének vetületei ezekre a komponens alterekre mind összehasonlíthatóak legyenek a nullelemmel. Ennek az állításnak az igazságát egyszerű belátni a teljes indukció segítségével és ez a bizonyítás egyben eljárást is ad a felbontás előállítására. Legyen {x1,x2, ... xs} a véges számú elem részhalmaza. Képezzük x1 pozitív és negatív részét, és az ezek által kifeszített komponens alterekből álló {X1+ , X1− } felbontást. Ha csupán erről az egy x1 elemről lenne szó, akkor ez a felbontás eleget tenne a feltevésnek. Az állítás tehát s=1 esetén igaz. Tegyük fel, hogy az {X1 , X 2 ,..., X r } ( r ≤ s -1) felbontás eleget tesz a feltételeknek az első s-1 elemre. Képezzük a xs elem vetületeinek pozitív és negatív részeit. Minden egyes Xi komponens alteret (i=1,2,...,r) felbonthatjuk ezeknek a kifeszített komponens altereire {Xis+ , Xis− } , ahol már az xs vetületei is összehasonlíthatóak lesznek a null-elemmel. Az

{X

+ 1s

, X1s- , X +2s , X-2s ,..., X +r s , X-rs } ( r ≤ s-1)

felbontás tehát a kívánt felbontás lesz. Nézzük meg ezt egy példán: Keressük R6 olyan komponensekre bontását, ahol az

a1

LM -3 OP MM 5 PP 12 = M P, a MM 0 PP MN -43 PQ

2

LM 6 OP MM 8 PP -2 = M P, a MM 2 PP MN 11 PQ

3

LM 4 OP MM 6 PP 1 = M P, a MM34PP MN791 PQ

vektorok vetületei mind összehasonlíthatóak 0-val. Kezdjük az első vektorral:

73

4

LM −3 OP MM −2 PP −13 =M ,a MM −1 PPP MN −04 PQ

5

LM−12OP MM 0 PP −23 =M MM 25 PPP MN1022 PQ

LM 0 OP LM3OP * MM 5 PP MM0PP ** 0 ** 12 = M P−M P MM 0 PP MM0PP ** MN 03 PQ MN40PQ ***

a 1 = a 1+ − a 1−

Vagyis az első felbontás:

a1

LM -3 OP * MM 5 PP ** 12 ** =M P , a MM 0 PP ** MN -43 PQ ***

2

LM 6OP MM 8 PP -2 = M P, a MM 2 PP MN 11PQ

3

LM 4 OP MM 6 PP 1 = M P, a MM34PP MN791 PQ

4

LM −3 OP MM −2 PP −13 ,a =M MM −1 PPP MN −04 PQ

5

LM−12OP MM 0 PP −23 =M MM 25 PPP MN1022 PQ

A második elem az egycsillagos sávban összehasonlítható a null-elemmel, a kétcsillagosban nem. Tehát az a2 vetülete a kétcsillagos sávra felbontható:

pr **a 2

LM 0 OP LM0OP LM0OP * MM 8 PP MM8PP MM0PP ** o 2 ** oo 0 -2 = M P = M P−M P MM 2 PP MM2PP MM0PP ** o MN 01 PQ MN01PQ MN00PQ *** o

Az ebből adódó felbontás:

a1

LM -3 OP * MM 5 PP ** 12 ** =M P , a MM 0 PP ** MN -43 PQ ***

2

LM 6OP MM 8 PP o -2 oo =M P , a MM 2PP o MN 11PQ o

3

LM 4 OP MM 6 PP 1 = M P, a MM34PP MN791 PQ

4

LM −3 OP MM −2 PP −13 ,a =M MM −1 PPP MN −04 PQ

5

LM −12 OP MM 0 PP −23 =M MM 25PPP MN1022 PQ

Most már három sávra bontottuk az R6-t, az R6*, R6**° és az R6**°° komponens alterekre. a3>0 és a4<0 eleve nem jelentenek problémát. Az a5 vetületekre bontása:

a 5 = pr *a 5 + pr ∗∗oa 5 + pr ∗∗ooa 5

LM −12 OP LM−12OP LM 0 OP LM 0 OP MM 0 PP MM 0 PP MM 0 PP MM 0 PP 0 0 −23 −23 =M =M +M P+M P P MM 25PP MM 0 PP MM25PP MM 0 PPP MN1022 PQ MN1020 PQ MN 20 PQ MN 00 PQ 74

Sajnos az R6* komponens altérben az a5 vetülete nem hasonlítható össze a null-elemmel, ezért tovább kell bontani a teret:

pr *a 5

LM−12OP LM 0 OP LM12OP ∗• MM 0 PP MM 0 PP MM 0 PP ∗∗ o 0 ∗∗ oo 0 0 =M = M P−M P P MM 0 PP MM 0 PP MM 0 PP ∗∗ o MN1020 PQ MN1020PQ MN 00 PQ ∗•∗∗•o

Ezzel tehát megkaptuk a teljes felbontást:

LMa OP LM 0 OP LM 0 OP LM 0 OP MM 0 PP MM 0 PP MMa0 PP MM 0 PP 0 0 a a = M P+M P+M P+M P MM 0 PP MM 0 PP MMa PP MM 0 PP MN 00 PQ MNa0 PQ MMNa0 PPQ MN 00 PQ 1

2

3

4

5

6

∗•

∗• •

∗∗ o ∗∗ oo

Pinszker abból a tényből indul ki, hogy az általa „absztraktnak“ nevezett LP-szerű feladatok „megengedett vektorainak“ 53 halmaza „konvex poliédert“ alkotnak. Ennek az „absztrakt poliédernek“ véges számú „csúcspontja“ van, amit a feladat paraméterei között szereplő véges számú „absztrakt elem“ lineáris kombinációjával lehet leírni. Ez abból az ismert tényből következik, hogy a poliéder csúcsai a Gauss-transzformációval „bejárhatóak“ 54 . Pinszker ezeket a kombinációkat nevezi a feladat megoldó kombinációinak és összességüket megoldó halmaznak. A megoldó halmaz számossága véges, így alkalmazható rá a 2.) megállapítás: a feladatot jellemző Riesz-tér felbontható olyan komponens alterekre, hogy a megoldó halmaz elemeinek vetületei az egyes alterekben összehasonlítható a tér null-elemével. Ezekből a vetületekből felépíthető az alapfeladat vetületfeladatainak serege 55 . A vetületképzés linearitásából következik, hogy a.) ha az eredeti feladat megengedett halmaza nem üres, akkor a vetületfeladatoké sem az; b.) ha az eredeti feladat célfügvénye a megengedett halmazon korlátos, akkor a vetületfeladatok célfüggvényei is így viselkednek; c.) ha a vetületfeladatoknak van optimális megoldása, akkor ezek összege az eredeti feladat optimális megoldását adja. Az A és C feladatok esetén ez azt jelenti, hogy elegendő azt az esetet vizsgálni, amikor a megoldó halmaz elemei összehasonlíthatóak a null-elemmel. Ellenkező esetben

53 Amelyek persze nem vektorok a szó hagyományos értelmében, hiszen komponenseik nem valós számok, hanem „absztrak elemek“ egy részben rendezett vektortérből. 54

Ez az alapja a szimplex-módszernek.

55

Ez úgy történik, hogy a feladat minden „absztrakt“ eleme helyére annak megfelelő vetülete kerül.

75

képezhetőek a vetületfeladatok és azokra már ez a feltételezés igaz lesz. A c.) megállapítás szerint a vetületfeladatok kezelése a kiinduló feladatot is kezeli. Pinszker bebizonyította elmélete alaptételét: TÉTEL.

(Pinszker) Ha az „absztrakt“ feladat megengedett halmaza nem üres, a megoldó halmaz elemei összehasonlíthatóak a null-elemmel, és a célfüggvény a megengedett halmaz felett korlátos, akkor a feladatnak van optimális megoldása.

A tétel szemmel láthatólag a dualitás V. tételének általánosítása. A bizonyítás arra épül, hogy az 1.) megállapításban szereplő pozitív additív leképezéssel a feladathoz rendelhető egy közönséges LP feladat, amelyre természetesen igaz a dualitás V. tétele. Ezután reprodukáljuk az V. tétel bizonyítását lépésről lépésre, és megmutatjuk, hogy a megfeleltetés mindvégig fennáll. Így az V. tétel bizonyításával párhuzamosan bebizonyítódik Pinszker tétele is 56 . A tétel alapján az A és C feladatokra megadható egy elméleti megoldó algoritmus: 1. Start. Meg kell határozni a megoldó halmaz elemeit. 2. A 2.) megállapítás bizonyításában leírt eljárással fel kell bontani a Riesz-teret olyan sávokra, amelyekben a megoldó halmaz elemei összehasonlíthatóak a null-elemmel. 3. Képezni kell a 2.-ben létrehozott sávokon az alapfeladat vetületfeladatait. 4. Minden vetületfeladathoz az 1.)-ben leírt pozitív additív leképezéssel meg kell alkotni a megfelelő hozzárendelt feladatot. 5. Valamilyen numerikus módszerrel (például a szimplex módszerrel) lépésről lépésre meg kell oldani a hozzárendelt feladatokat. Minden elvégzett lépést a vetületfeladatokon is analóg módon megismétlünk. Ha a hozzárendelt feladat megoldható, akkor Pinszker tétele szerint a vetületfeladat is megoldható. Ha véges lépésben eljutunk a hozzárendelt feladat optimális megoldásához, akkor a párhuzamos lépések elvezetnek a vetületfeladat optimális megoldásához. 6. Ha valamennyi vetületfeladat megoldható, akkor megoldásaik összege kiadja az eredeti feladat megoldását. Vége. Az algoritmus kisebb feladatok megoldására alkalmas ugyan, de az 1. és 2. pontok végrehajtása egy nagyobb feladat esetén már komoly nehézséget okoz. A megoldás menetének vizsgálata azonban felveti az A és C feladatok esetében egy hatékonyabb eljárás lehetőségét. Arról van szó, hogy a megoldás a vetületfeladatok poliédereinek csúcspontjai egy-egy meghatározott részének bejárását jelenti. Ezen csúcspontok közül nyílván az indulási pontok a teljes feladat ugyanazon csúcspontjának vetületei. Menet közben a vetületi utak, mint egy fa ágai, szétválhatnak. Ha meg tudjuk adni e szétválás technikáját, akkor sok felesleges munkától kímélhetjük meg magunkat. Ez a technika meglepően egyszerű. Kiderül, hogy sem a megoldó halmaz teljes meghatározására, sem az összes lehetséges sáv szétbontására, sem a pozitív additív leképezéssel előállított hozzárendelt feladatok felírására és megoldására nincs szükség.

56

A teljes bizonyítást lásd Nagy András (B. Nagy András) idézett cikkében a 111-113. oldalakon.

76

A részben rendezett Riesz-terek null-elemmel összehasonlítható elemeivel az osztást leszámítva ugyanúgy „számolhatunk“, mint a számokkal. Az A és C feladatokban pedig a szimplex-módszer alkalmazása során „absztrakt“ elemmel nem kell osztani (az osztásokat a technológiai mátrix - A - elemeivel kell elvégezni.) Így az A és C típusú feladatot úgy kell megoldani, mintha közönséges LP feladat lenne, egészen addig, amíg olyan ponthoz nem érünk, ahol a megoldásba vont valamely „absztrakt“ elem(ek) nem hasonlíthatóak össze a null-elemmel. Itt fel kell bontani a Riesz-teret olyan mértékben, hogy ezeknek a kritikus elemeknek a vetületei már összehasonlíthatóak legyenek a null-elemmel. Ezután minden új sávban tovább kell folytatni az eljárást, ugyanúgy mint azt fent leírtuk. Az eljárás menetét két egyszerű A típusú feladaton mutatjuk meg. A.) EGY ABSZTRAKT SZÁLLÍTÁSI FELADAT MEGOLDÁSA.

Tekintsük a következő A típusú szállítási feladatot. Az „absztrakt részben rendezett vektortér“ a [0, 3] intervallumon szakaszosan folytonos függvények tere. 3 feladóhelyről kell „függvényeket szállítani“ 4 fogadóhelyre. Ismertek a szállítandó függvények és a különböző útvonalak fajlagos költségei az alábbi táblázat szerint:

t3

t

t2

t

2t

4

3

1

0

t2

1

0

4

2

t3

0

3

2

5

[0 , 3 ]

Tehát a feladat függvények „szállítása“. De tegyünk úgy, mintha az első oszlopban és sorban is számok lennének. Válasszuk a legegyszerűbbnek tűnő induló bázismegoldást, azaz minden felvevőhelyet egy feladó szolgáljon ki. Ekkor a szállitási terv a következő lesz:

t3 θ 2t t2 t3

t3

θ

t 4

θ

1 0

t2

t 3 θ θ

0 3

t t

1 t2 θ

4

0 θ θ

2

77

2 5

[0 , 3 ]

Ebben a (nem optimális) megoldásban a teljes [0, 3] intervallumon pozitív valamennyi szállitandó elem. A program javításához kiszámítjuk a potenciálokat, ahogyan az a szállítási feladatok elméletéből ismeretes.

0

-1

3

-4

4

0

0

-6

0

1

0

0

0

5

0

0

2

-1

9

A minimális potenciál -6, tehát a második sor negyedik cellájában lehet a programot javítani. Az ehhez tartozó kör:

t

3

1

0

4 t2

A kérdés, hogy melyik elemet kell elmozdítani. Ez attól függ, hogy a t-t2 kifejezésnek hogyan alakul az előjele. Kiszámítható, hogy a [0, 1) félig zárt intervallumon t nagyobb, mint t2, a maradék [1, 3] zárt intervallum felett viszont t2 nagyobb, mint t. Ezért itt számításaink elágaznak. Folytassuk előbb a [0, 1) intervallumban az optimális program keresését. A kijelölt kör mentén mozgassuk át az átlón a t2 elemet:

t3 t-t 2

θ

2t

4

t

2

θ

t

3

t3

t2

t

1 0

t2 θ

t2

t

3

1

0

4

3

t

θ

2

0 θ θ

2 5

[0 , 1 )

A potenciálok mind pozitívak, ezért ebben a sávban elértük az optimumot:

78

0

-1

-3

-4

4

0

0

0

0

1

0

0

6

5

0

0

4

5

9

Az [1, 3] intervallumban a t fügvény a kisebb, így azt kell mozgatni:

t3

t2

t

θ

2t t

2

θ

t

3

t3

t

t 4 1 0

1

3 t

0

θ

3

t

t2 -t

4

θ

2

0 θ θ

2 5

[1, 3]

A potenciálok:

0

-1

3

2

-2

6

6

0

0

1

0

0

0

-1

0

0

3

-1

3

Itt két minimális potenciál is van (-1), ami azt mutatja, hogy a feladatnak több megoldása is van (degeneráció). A programot javító kört a harmadik sor utolsó eleméhez igazítjuk:

t 1

2 t -t 4

0 t

2 79

A javító átlón t2-t és t közül kell a kisebbet választani. Ez az [1, 2) intervallumon a t2t, a maradék [2, 3] intervallumon t-t kell elmozgatni. A feladat tehát az új sáv jelentkezésével ismét szétágazik. Folytassuk az [1, 2) intervallum ágán. A javított program:

t3 θ

2t t2 3

t

4 θ

t3

1 0

t2

t

t 2t -t 2

t2

θ

3

t

0

θ

3

1

0 t 2-t

θ

4

θ

2

2 θ

5

[1, 2)

A potenciálok itt is mindenütt nem negatívak, ezért ebben a sávban is elérkeztünk az optimumhoz:

-1

0

2

1

-1

5

5

0

0

1

0

0

1

0

0

0

4

0

4

A [2, 3] intervallumban folytatjuk, ahol a t függvényt fogjuk a kör mentén elmozdítani:

t3 θ

2t

4

t

2

θ

t

3

t3

1 0

t2

t θ

t θ

t θ

2t 3 0 3

1 t 2-2t 4 θ

2

0 t 2 θ

5

A potenciálok tanusága szerint ez a program még javítható: 80

[2, 3]

-1

0

3

1

-2

6

6

0

1

1

0

0

0

0

0

0

4

-1

4

Az utolsó sor utolsó előtti cellájában negatív a potenciál, itt javítható még a program. Az ehhez tartozó kör:

t 1

4 t 2-2t

t3 0

2

A [2, 3] intervallum teljes terjedelmében a t2-2t a kisebb, tehát ezt kell elmozdítani a kör mentén:

t3 θ

2t t

2

t3

t2

t

4 t 2-2t

θ

t 1

t 3-t 2 +2t θ 0

t θ

2t 3 0

1 θ

0 t

4

t 2-2t 3

2

2 θ

5

[2, 3]

A potenciálok végre itt is nem negatívakká váltak, ezért itt is elértük az optimumot:

81

-1

0

2

1

-1

5

5

0

0

1

0

0

1

0

0

0

4

0

4

Az optimális megoldás tehát: ⎧t ha t ∈ [ 0, 1) 2 2 ⎧ ⎧ t t ha t 0, 1 t ha t 0, 2 − ∈ ∈ ⎪ ) ) [ [ ⎪ ⎪ 0 0 0 0 x11 ; x13 ; x14 = θ; x12 =⎨ =⎨ = ⎨2t − t 2 ha t ∈ [1, 2 ) ; ha t ∈ [ 2, 3] ⎪⎩2t ha t ∈ [ 2, 3] ⎪ ⎩⎪θ ha t ∈ [ 2, 3] ⎩θ ⎧θ ha t ∈ [ 0, 1) 2 ⎧ ⎧θ ha t 0, 2 ∈ t ha t 0, 1 ∈ ) [ ⎪ ) [ ⎪ ⎪ ; x 023 = θ; x 024 = ⎨ t 2 − t ha t ∈ [1, 2 ) ; x 021 = ⎨ 2 ; x 022 = ⎨ ⎪⎩ t − 2t ha t ∈ [ 2, 3] ⎪ ⎩⎪ t ha t ∈ [1, 3] ha t ∈ [ 2, 3] ⎩t ⎧⎪ t 3 ⎧⎪θ ha t ∈ [ 0, 2 ) 0 ha t ∈ [ 0, 2 ) 0 0 0 ; x 34 = θ x 31 = ⎨ 3 2 ; x 32 = θ; x 33 =⎨ 2 ⎪⎩ t − 2 t ha t ∈ [ 2, 3] ⎪⎩ t − t + 2t ha t ∈ [ 2, 3] m n ⎧⎪3t − 2t 2 ha t ∈ [ 0, 1) 0 max ∑∑ cij x ij = ⎨ 2 i =1 j=1 ⎪⎩3t − 2t ha t ∈ [1, 3] B.) EGY ABSZTRAKT STANDART LP FELADAT

Második illusztrációnk legyen egy standart alakban megadott A típusú általánosított LP feladat. A részben rendezett Riesz-tér szerepét itt az R5 euklideszi tér játsza:

b

g

f x1 , x 2 = x1 + x 2 → max x1 − x 2 ≤ 5

3

2

4

5

− x1 + x 2 ≤ 3

3

2

1

6

2 x1 + x 2 ≤ 8

8

5

5

10

x1 , x 2 ≥ 0

0

0

0

0

Első lépésben felírjuk a standart szimplex táblázatot 57 :

57

Többféle „standart szimplex táblázat“ létezik. Mi itt olyat alkalmazunk, amelyben jól nyomon követhetők az „események“. Krekó B. többször idézett művében egy egyszerűsített változat szerepel, amely céljainknak kevésbé felel meg.

82

b

x1

x2

u1

u2

u3

u1

1

-1

1

0

0

5

3

2

4

5

u2

-1

1

0

1

0

3

3

2

1

6

u3

2

1

0

0

1

8

8

5

5

10

f

-1

-1

0

0

0

0

0

0

0

0

Látható, hogy az x1 változót az u1 vagy az u3 bázisvektor helyére lehet a bázisba bevonni. Válasszuk, mondjuk, az u1-et. Ekkor a megfelelő bázistranformációs lépéseket elvégezve a következő táblázatot kapjuk:

b

x1

x2

u1

u2

u3

x1

1

-1

1

0

0

5

3

2

4

5

u2

0

0

1

1

0

8

6

4

5

11

u3

0

3

-2

0

1

-2

2

1

-3

0

f

0

-2

1

0

0

5

3

2

4

5

Az új bázismegoldás a kijelölt sávban nem megengedett, azért ott majd a szaggatott kerettel megjelölt elemet kell generáló elemnek választani. Most azonban folytatjuk a megoldást b ki nem jelölt komponensére. Az x2 alatt az f sorában negatív érték van, tehát x2 a harmadik báziselem helyére vonható be:

x1

x2

u1

x1

1

0

1/3 0

u2

0

0

1

x2

0

1

f

0

0

u2

b

u3

11/3 7/3

1/3

5

1

0

8

6

-2/3

0

1/3

-2

2/3

-1/3

0

2/3

5

3

4

15/3

4

5

11

1/3

-3

0

2

4

5

Itt a b vizsgált sávja pozitív maradt, tehát nem kell tovább bontani. Az f sor tanusága szerint a bázisban u1 felcserélhető u2-vel, ez javítani fogja a programot:

83

x1

x2

u1

u2

u3

x1

1

0

0

-1/3

1/3

5

5/3

1

4

4/3

u1

0

0

1

1

0

8

6

4

5

11

x2

0

1

0

-2/3

1/3

-2 14/3

9/3

-3

22/3

f

0

0

0

1/3

2/3

5 19/3

4

4

26/3

b

Az f sor minden eleme nemnegatív, tehát ebben a komponens altérben eljutottunk az optimális megoldáshoz: pr1x10 = 0

5/ 3

pr1x 02 = 0

14 / 3

3

0

22 / 3

pr1f X 0 = 0

19 / 3

4

0

26 / 3

d i

1

0

4/ 3

Most pedig ezt a komponens alteret takarjuk le és a számításokat újrakezdjük az első táblázatban a szaggatott keretes generáló elemmel:

b

x1

x2

u1

u2

u3

u1

0

-3/2

1

0

-1/2

1

3

2

3/2

5

u2

0

3/2

0

1

1/2

7

3

2

7/2

6

x1

1

1/2

0

0

1/2

4

8

5

5/2

10

f

0

-1/2

0

0

1/2

4

0

0

5/2

0

Az x2 is bevihető a bázisba, hiszen az f sorában még van negatív elem:

x1

x2

u1

u2

u3

u1

0

0

1

1

0

x2

0

1

0

x1

1

0

0

f

0

0

0

b 8

3

2

5

5

2/3 1/3

14/3

3

2

7/3

6

-1/3

0

5/3

8

5

9/6

10

2/6

2/6

14/3

0

0

23/6

0

Ez már a sáv optimális táblázata, ahonnan leolvasható az optimális megoldás is:

84

pr2 x10 = 5 / 3

0

0

3/ 2

0

pr2 x 02 = 14 / 3

0

0

7/ 3

pr2 f X 0 = 14 / 3

0

0

23 / 6

d i

0 0

A két vetületi megoldást összevonva megkapjuk a feladat teljes megoldását: x10 = 5 / 3

5/ 3

1

3/ 2

x 02 = 14 / 3

14 / 3

3

7/ 3

f X 0 = 14 / 3

19 / 3

4

23 / 6

d i

85

4/ 3 22 / 3 26 / 3

INPUT-OUTPUT ELEMZÉS, AZ ÁGAZATI KAPCSOLATOK MODELLJE (ÖTÖDIK ELŐADÁS) 1. A MODELL A.) AZ ÁGAZATI KAPCSOLATOK MÉRLEGE

A következő allokációs feladatot kell megoldanunk. Egy termelési rendszerben (például egy ország nemzetgazdaságában) minden résztvevő (például az ország nemzetgazdasági ágazatai.) egy-egy egymástól különböző, egymást nem helyettesítő terméket gyárt. A rendszeren kívülről elsődleges források áramlanak a rendszerbe (input), a rendszer termékei részben a rendszeren belül kerülnek felhasználásra, részben kiáramlanak a rendszeren kívülre a végső felhasználókhoz (output). A rendszeren belüli felhasználás esetén a termelő outputja egyben a felhasználó inputja is. Minden résztvevő legalább egy másik résztvevőnek termel, és minden résztvevő felhasználja legalább egy másik termelő termékét. A rendszernek s elsődleges forrása és t végső felhasználási módja van, magában a rendszerben résztvevők, és így az általuk előállított termékek száma n. Legyen xij az i-dik résztvevő által a j-dik résztvevőnek szállított termékmennyiség. A fenti feltételek szerint minden i esetén legalább egy j-re és minden j esetén legalább egy i-re xij>0. Az X=[xij] mátrix az úgynevezett „sakktábla-mátrix“ 58 . Vezessünk be két további mátrixot is. Jelölje zkj a k-dik elsődleges erőforrás j-dik résztvevő által igénybe vett mennyiségét, yil pedig az i-dik résztvevő által az l-dik végső felhasználásra termelt mennyiséget. Ennek megfelelően Z=[zkj] az elsődleges erőforrások, Y=[yil] a végső felhasználás mátrixai. Végül jelöljük xi-vel az i-dik résztvevő kibocsátását. Az x=[xi] vektor a brutto kibocsátás vektora. Alkalmazzuk a következő szinte triviális alapelvet: semmiből nem lesz semmi. E szerint az elv szerint valamely résztvevő kibocsátása egyfelöl az inputokból tevődik össze, és másfelöl az outputokra bomlik szét, azaz n

s

i =1

k =1

n

t

j=1

l =1

b g bi = 1,2,..., ng

x j = ∑ x ij + ∑ z kj j = 1,2,...n x i = ∑ x ij + ∑ y il

Ezeket az összefüggéseket egy táblázatban is összefoglalhatjuk:

X belső négyzet

z alsó szárny

Y jobboldali szárny

x netto kibocsátás

?

külső négyszög

xT

netto kibocsátás

13. ábra Az ágazati kapcsolatok mérlege

58

Az elnevezést illetően lásd a 11 lábjegyzetet a 19. oldal alján

86

Ezt a táblázatot hívják az ágazati kapcsolatok mérlegének - ÁKM-nek. Az elnevezés egyrészt azt takarja, hogy a fent elemzett szituáció jellemző a teljes népgazdaságra. A résztvevők a gazdasági ágazatok, azzal a feltételezéssel, hogy minden ágazat termékei aggregálhatók egyetlen ágazati termékbe és ezek az ágazati aggregátumok nem helyettesítik egymást. Másrészt a táblázat minden eleme kiszámítható a nemzeti számlakeret szerinti egységes számviteli rendszer adatai alapján. Így a táblázat valóban egy nemzetgazdasági mérleg. A táblázat, az összegző keretektől eltekintve, négy részből, négy „negyedből“ áll. A belső négyzet tartalmazza az X mátrixot, a „sakktáblát“. Az alsó szárny az elsődleges erőforrások elosztási mátrixát tartalmazza. A legegyszerűbb esetben ez egyetlen zT sorvektor. Ez lehet a Z mátrix aggregátuma, de felfogható úgy is, hogy csak egy külső erőforrást feltételezünk. Ez utóbbi például a marxi közgazdaságtan felfogása, amely egyetlen külső erőforrásként az emberi munkát tekinti. A jobboldali szárny a végső felhasználás Y mátrixát tartalmazza, ami egy egyszerűsített modellben szintén aggregálható egyetlen y oszlopvektorba. A külső négyszögbe egy kérdőjelet írtunk. Ha itt is szerepelne egy, a mérlegbe illeszthető mátrix, akkor az megmutatná, milyen arányban alakulnak át az elsődleges források végső felhasználásokká. Ennek ismerete roppant izgalmas lenne legalább is a közgazdászok számára - hiszen felvilágosítást adna az erőforrások tényleges allokációjának természetéről. Sajnos a nemzeti számlakeretrendszer adatai nem teszik lehetővé ennek a mátrixnak a megalkotását. Így marad a kérdőjel ... A rendelkezésünkre álló három „negyed“ adatai is hatékony allokáció-elemzési eszközt adnak a kezünkbe. B.) A STATIKUS LEONTYEV-MODELL 59 A továbbiakban az egyszerűsített modellt fogjuk vizsgálni egy elsődleges erőforrással és egy végső felhasználási móddal. Ekkor a Z mátrix helyett a zT sorvektort, az Y mátrix helyett az y álló vektort alkalmazzuk, és így a mérleg-egyenletek mátrix alakban is könnyen felírhatóak:

x T = 1T X + zT x = X ⋅1 + y Ha következetesen végig visszük a teljes absztrakcióig azt a feltételezést, hogy az ágazatok termékei nem helyettesítik egymást, akkor - mivel valamilyen mértékben minden termék részt vesz a többi termék előállításában - előáll az egymást tökéletesen nem helyettesítő, de egymást tökéletesen kiegészítő erőforrások esete. Az ilyen erőforrásokra épülő termelési függvények a Leontyev-féle termelési függvények. Nevüket éppen onnan kapták, hogy az irodalomban először a V. Leontyev által kidolgozott input-output elemzés kapcsán jelentek meg. A mikroökonómiából ismert, hogy a Leontyev-féle termelési függvény izokvantjai sajátos alakzatok. Két erőforrás esetén a 13. ábra szemlélteti ezt az alakzatot.

59

A dinamikus Leontyev-modellek a növekedés témakörébe tartoznak, így kívül esnek e könyv

keretein.

87

x1 q x1 x 2 = konstans

x2

13. ábra A két tényezős Leontyev-típusú termelési függvény izokvantjai

Látható, hogy a tényezők adott (konstans) aránya mellett a növekvő ráfordítások növekvő kibocsátást eredményeznek. Ha azonban eltérünk az előírt aránytól, akkor érvényesül a „donga-elv“, és mindig a minimális tényező fogja meghatározni az összkibocsátást.

Ha feltesszük, hogy egységnyi q előállításához a1 egységnyi első és a2 egységnyi második tényező felhasználása szükséges és az elsőből x1-et, a 2-dikból x2-őt használnak fel, akkor q = min

RS x ; x UV, Ta a W 1

2

1

2

Az ágazati kapcsolatok mérlegére is alkalmazhatjuk ezt a gondolatmenetet. Mivel ott xj termeléséhez [xij](i=1,2,...,n) mennyiségeket használnak fel a többi termékből és zj mennyiséget az elsődleges erőforrásból, azért

R| U| x1j x2 j x1j z j | | x = min S , ,..., , || x x x z V|| Tx x x x W j

1j

2j

nj

j

j

j

j

j

Ez így természetesen semmit sem mond. Viszont fordítsuk figyelmünket a nevezőkre. Leontyev - Walras gondolatát felhasználva - azzal az egyszerűsítő feltételezéssel élt, hogy a j-dik ágazat xj kibocsátása és az i-dik ágazat által szállított xij mennyiségek aránya a termelés technológiájára jellemző objektíve létező állandó 60 : x ij xj

= a ij

Az aij arányszámokat technológiai koefficienseknek, az [aij]=A mátrixot a modell technológiai mátrixának nevezik. Ha ezeket objektív adottságnak vesszük, akkor a fenti

60

Ezt úgy kell elképzelni, mint a villamosságtanban az ellenállás fogalmát. Ohm törvénye szerint az ellenállás az áramkör-darabon mérhető feszültségesés és az átfolyó áram erősségének aránya. Azonban ez az arány adott áramköri elem esetén általában állandónak tekinthető, és az áramkörbe épített alkaltrész belső tulajdonságaként jelenik meg, az áramkörtől függetlenül is meghatározható.

88

összefüggés már nem lesz annyira triviális, és teljesen megfelel a Leontyev-típusú termelési függvénynek: ⎧⎪ x1j x 2 j x nj z j ⎫⎪ x j = min ⎨ , ,..., , ⎬ , a nj zˆ j ⎪⎭ ⎪⎩ a1j a 2 j ahol z$ =

zj xj

és szintén objektíve adott koefficiens.

A koefficienseket definiáló formulát átrendezve a feltételezett oksági kapcsolatot jobban kifejező - matematikailag természetesen ekvivalens - alakot kapunk: x ij = a ij ⋅ x j Ezt a mérleg-egyenletekbe helyettesítve: n

x j = ∑ a ij x j + z j i =1 n

x i = ∑ a ij x j + y i j=1

vagy mátrix alakban a definiciós összefüggés:

X=A x ahol a hegyes zárójelek a közéjük zárt vektort a főátlóban tartalmazó diagonális mátrixot jelentik. Nyilván x ⋅ 1 = x , így a mérleg-egyenletek: x T = 1T A x + zT x = A x ⋅ 1 + y = Ax + y

A konstans technológiai koefficiensek feltételezése, mint azt a Leontyev-típusú termelési függvény mutatja, egyenértékű az egymást tökéletesen nem helyettesítő, egymást tökéletesen kiegészítő ágazati termékek feltételezésével. A feltételezés elfogadható mértékű egyezését a valósággal először Leontyev mutatta ki az USA több éves gazdasági adatainak felhasználásával. A magyar Központi Statisztikai Hivatalban végzett több éves ÁKMmunkálatok szintén a technológiai koefficiensek nagy fokú stabilitását mutatták ki 61 .

2. A LEONTYEV-MODELL MATEMATIKAI ELEMZÉSE A.) ZÁRT LEONTYEV-MODELL

A zárt Leontyev-modellben nincs elsődleges erőforrás és nincs végső felhasználás sem. Felvetődik a kérdés, hogy van-e egyáltalán relevanciája az ilyen modellnek? Természetesen egy ilyen modell a végletekig leegyszerűsített, de nincs teljesen híján a

61

A vizsgálatok a technológiai koefficiensek stabilitását támasztották alá, és nem az ágazati termékek egymás közötti nem helyettesíthetőségét - ami általában természetesen nem is igaz. Bródy András „Az ágazati kapcsolatok modellje“ című munkájában a koefficiensek változatlanságának feltételezését elméletileg megalapozatlannak tartja, de kimutatja, hogy az ÁKM sajátos „hibajavító“ képessége miatt a koefficiensek elméleti ingadozása kisebb, mint a mérleg összeállításához felhasznált adatok eredeti hibája, így a koefficiensek instabilitása rövid távon szignifikánsan nem verifikálható.

89

realitásoknak. Ha például a munkaértékelmélet álláspontjára helyezkedünk (adott esetben mindegy, hogy ebben Ricardot vagy Marxot követjük) és egyetlen elsődleges erőforrásként a munkát fogadjuk el, akkor nem okoz különösebb problémát, hogy a munkát „termelő“ háztartást bevonjuk a termelő ágazatok közé. Ezzel egyben a végső felhasználástól is „megszabadulunk“, hiszen az is felfogható, mint a háztartás „termelő fogyasztása“. Általában bármely ágazat kivihető lefelé az elsődleges erőforrások és jobbra a végső felhasználás módjai közé (egy ágazat externalizálása), illetve fordítva, ha az elsődleges erőforrások valamelyikét közgazdaságilag össze lehet párosítani valamely végső felhasználási móddal, akkor ezek egy ágazatként bevonhatók a belső négyzetbe (egy erőforrás internalizálása). Matematikailag ez a következő három ábra alapján látható be, amelyek ekvivalens szituációkat ábrázolnak. Az alaphelyzet, ahol nem tudjuk, mi van a „külső négyszögben“:

LM x MMx MMx... MM z MM ... MM zx N

11 21

n1

11

s1 1

x12 x 22

... ...

x1n x 2n

y11 y 21

... ...

y1t y 2t

... x n2 z12 ... z s2 x2

... ... ... ... ... ...

... x nn z1n ... z sn xn

... y n1

... ...

... y nt

OP P ... P P x P PP PP PP Q x1 x2 n

Amennyiben az n-ik ágazat (megfelelő átindexeléssel ez bármelyik lehet) „önszállítása“, belső forgalma xnn=0, akkor minden további nélkül az n-dik sort ki lehet vinni az alsó szárnyba, mint sajátos elsődleges forrást, az n-dik oszlopot ki lehet vinni a jobb szárnyba, mint sajátos végső felhasználást. Igy lehet például a külkereskedelem ágazatát - ha eltekintünk a „reexport“ jelenségétől - szétbontani az import elsődleges erőforrására és az export végső felhasználására. Ezt az eljárást az ágazat externalizálásának neveztük:

LM x MMx MMx... MM z MM ... MM zx N

11 21

n1

11

s1 1

x12 x 22 ...

... ... ...

x1n x2n ...

x n2 z12 ...

... ... ...

0

z s2 x2

... ...

y11 y 21 ...

... ... ...

y1t y2t ...

x1 x2 ...

OP PP PP PP PP PP Q

Még egyszerűbben lehet bármelyik elsődleges erőforrást beemelni - internalizálni - a belső négyzetbe, feltéve, hogy tudunk neki „párt“ választani a végső felhasználási módok között. A kettős könyvelés elvéből következik, hogy ez nem okozhat problémát. A zárt modell előállítása legegyszerűbben úgy történhet, hogy az alsó és a jobb szárnyakat egy-egy vektorrá aggregáljuk, majd ezeket internalizáljuk. Természtesen a titokzatos külső négyszög kezelése nem megoldott, de egyes konkrét esetekben ez megoldható, elméletileg pedig - a zárt modell felírásának szempontjából - a kérdés nem lényeges. 90

LM x MMx MMx... MM z MM ... MM zx N

11 21

n1

11

s1 1

x12 x 22

... ...

x1n x 2n

y11 y 21

... ...

y1t y 2t

... x n2 z12 ...

... ... ... ...

... x nn z1n ...

... y n1 0 ...

... ... ...

... y nt 0

z s2 x2

... ...

z sn xn

0 x n +1

OP PP ... P x P x P PP PP PQ x1 x2

n

n +1

A zárt modellnél is él természetesen a Walras-Leontyev feltételezés a stabil, változatlan technológiai koefficiensekről, az A technológiai mátrixról, így a zárt modell felírható a következő mérleg-egyenlettel:

x = Ax Ez szemmel láthatólag egy sajátérték problémát rejt magában. Vezessünk be néhány fontos matematikai-közgazdaságtani kategóriát. Nyilván nem mindegy, hogy a rendszer által megtermelt termék milyen arányban áll a rendszer által elfogyasztott termékkel. Ha rendszer nem termeli meg azt a mennyiséget, amelyet el kíván fogyasztani, akkor - külső erőforrások híján - nem lesz képes a termelési folyamatot fenntartani. DEFINICIÓ 1

A zárt Leontyev-modell működőképes, ha van olyan x>0, amelyre Ax≤x.

DEFINICIÓ 2

A zárt Leontyev-modell Gale szerint termelékeny (produktív), ha van olyan x>0, amelyre Ax<x.

DEFINICIÓ 3

a.) Egy j-dik ágazat közvetlenül függ egy másik i-dik ágazattól, ha aij>0. b.) Egy ágazat függ a másik ágazattól, ha közvetlenül függ tőle. c.) Ha a j-dik ágazat függ a k-dik ágazattól és a k-dik ágazat függ az i-dik ágazattól, akkor a j-dik ágazat (közvetve) függ az i-dik ágazattól. d.) A rendszer ágazatai teljesen összefüggőek, ha bármely két ágazata közvetlenül vagy közvetve függ egymástól.

Az ágazatok közvetlen vagy közvetett függése egymástól jellemezhető a technológiai mátrix belső szerkezetével. DEFINICIÓ 4

Az A technológiai mátrix reducibilis, ha az ágazatok megfelelő átszámozásával előállítható a következő alakú particiója:

A=

LMA N0

11

A 12 A 22

OP Q

Az A tecnológiai mátrix széteső, ha az ágazatok megfelelő átszámozásával előállítható a következő alakú particiója:

LMA 0 A=M MM ... N0

11

0 A 22 ... 0

... ... ... ... 91

0 0 ... A rr

OP PP PQ

Nyílván a széteső technológiai mátrix egyben reducibilis is. A reducibilitás ugyanakkor egyoldalú függetlenséget jelez (az i-dik ágazat független a j-dik ágazattól, de a jdik függhet az i-diktől - az ágazatok függősége nem reflexív reláció!), viszont a széteső rendszer két, különböző függőségi osztályba tartozó ágazata kölcsönösen függetlenek egymástól. Könnyen bizonyítható a TÉTEL 62

Az A technológiai mátrix jellemezte rendszer ágazatai akkor és csak akkor teljesen összefüggőek, ha az A technológiai mátrix nem reducibilis (irreducibilis).

A továbbiakban feltételezzük, hogy az általunk tárgyalt modell technológiai mátrixa nem reducibilis, azaz az ágazatok közvetlenül vagy közvetve függenek egymástól. Az irreducibilitásból következik, hogy az A mátrix félpozitív, azaz minden i-re van olyan j, és minden j-re van olyan i, hogy aij>0. Az irreducibilis, félpozitív mátrixokra érvényes egy sor fontos tétel: TÉTEL 63

(Perron-Frobenius) Ha A irreducibilis, félpozitiv négyzetes mátrix, akkor sajátértékei között van egy λ* és a hozzátartozó x* sajátvektor, amelyekre

a.)

λ* valós pozitív szám

b.)

λ* a legnagyobb abszolút értékű sajátértéke az A mátrixnak

c.)

x* pozitív vektor és az A mátrix egyetlen (egy skalár szorzó pontosságáig) pozitív sajátvektora

d.)

ha μ≥λ*, akkor és csak akkor a μE-A mátrix nem szinguláris és (μE-A)-1 pozitív minden elemében

e.)

min ∑ a ij ≤ λ* ≤ max ∑ a ij és min ∑ a ij ≤ λ* ≤ max ∑ a ij , ahol az egyenlőség

n

i

j=1

n

i

j=1

n

j

i =1

n

j

i =1

csak akkor állhat fenn, ha a sor- illetve az oszlopösszegek külön-külön egyenlőek. A tételben szereplő λ* sajátértéket a b.) miatt nevezik domináns sajátértéknek, illetve a tétel első megfogalmazói után Perron-Frobenius sajátértéknek vagy számnak is. Tegyük fel, hogy egy gazdaságban egy adott évben a nemzeti számviteli rendszerből kinyerhető statisztikai adatok alapján összeállítják az ágazati kapcsolatok mérlegét. Ennek adataiból az elsődleges erőforrásokra és végső felhasználásra vonatkozó adatok internalizálásával egy zárt rendszerhez jutnak, amit az X félpozítív négyzetes mátrix jellemez. Feltehetjük azt is, hogy ez a mátrix irreducibilis. A nemzeti számviteli rendszer logikájából következik, hogy helyes adatfelvétel esetén az inputok és az outputok egyensúlyban vannak, azaz ha

1T X = x 1T , illetve X1 = x 2 akkor 62 A tétel bizonyítása megtalálható például Zalai Ernő „Bevezetés a matematikai közgazdaságtanba“ (KJK, Budapest, 1989) 57-58. oldalak. 63

A tétel sokféle változatban ismert. Egyik lehetséges kifejtése és bizonyítása Zalai Ernő előbb említett könyvének 61-65. oldalain található.

92

x1 = x 2 = x ahol x a GDP ágazatokra bontott vektora lesz. Ha elfogadjuk Walras-Leontyev hipotézisét a stabil technológiai koefficiensekről, akkor a fenti statisztikai adatokból „rekonstruálható“ az egyébként - feltevésünk szerint - objektíve adott technológiai mátrix: A=X x

−1

Ha beszorozzuk balról mindkét oldalt az összegző vektorral, akkor 1T A = 1T X x n

Azaz minden j-re

∑a

ij

−1

= xT x

−1

= 1T x x

−1

= 1T

= 1 , így a Perron-Frobenius tétel e.) pontja szerint λ*=1. Ez

i =1

viszont a d.) pont szerint azt jelenti, hogy az E-A mátrix nem szinguláris és inverze, a Leontyev-inverz, (E-A)-1 minden elemében pozitív. B.) NYÍLT LEONTYEV-MODELL

Mint láttuk, a zárt Leontyev-modell meglehetősen tetszetős matematikai elemzéseket tesz lehetővé, ám közgazdasági szempontból a nyílt modell, amelyben egy elsődleges erőforrás és egy végső felhasználási mód van externálisan elkülönítve, sokkal érdekesebb. A nyílt modell, mint azt korábban már láttuk, a következő mátrix-egyenlettel írható fel:

x = Ax + y ahol y a végső felhasználás vektora. Közgazdasági szempontból az a kérdés lehet érdekes, hogy vajon bármilyen nem negatív y-ra megoldható-e ez az egyenlet valamilyen nem negatív x vektorral? Másképpen fogalmazva, képes-e a gazdaság bármilyen összetételű végső felhasználást kielégíteni? Nyilván az elsődleges erőforrás végessége (vagy - ami nem egészen ugyanaz - szűkössége) korlátot jelent a gazdaság teljesítőképességét illetően, de itt nem az y abszolút nagyságáról van szó, hanem a tetszőleges összetételéről. A fenti egyenlet ugyanis nyilván végig szorozható egy pozitív ρ skalárral, így ha y0 esetén x0 a megfelelő megoldás, akkor ρy0 esetén ρx0 lesz a megfelelő, nem negatív megoldás. A működőképesség, illetve a produktívitás fogalma a nyílt Leontyev-modellnél is értelmezhető. DEFINICIÓ 1

A nyílt Leontyev-modell működőképes, ha minden y≥0 esetén van olyan x≥ 0, amelyre (E-A)x=y.

DEFINICIÓ 2

A nyílt Leontyev-modell Gale szerint termelékeny (produktív), ha minden y>0 esetén van olyan x>0, amelyre (E-A)x=y.

Bebizonyítható továbbá az úgynevezett produktivitási tétel:

93

TÉTEL 64

(Gale) Ha a nyílt Leontyev modellnek legalább egy y>0 végső fogyasztási vektorhoz van nem negatív megoldása, akkor és csak akkor működőképes.

A tétel többek között a következőre alkalmazható. Az előbbihez hasonlóan feltételezzük, hogy a nemzeti számviteli rendszer adatait felhasználva összeállítják valamely évre ezúttal a nyílt ÁKM-et a következő egyenlet formájában: x = X ⋅1 + y ahol

x

a GDP ágazati bontásban

X

a „sakktábla“

y

a végső felhasználás vektora.

Majd megint élve a Walras-Leontyev hipotézissel „rekonstruálják“ a technológiai koefficiensek mátrixát A=X x

−1

.

A statisztikai gyakorlat alapján valószínű, hogy y>0 és x≥0 lesznek. Ha ez így van, akkor teljesülnek a Gale-tétel feltételei, tehát bármilyen arányú végsőfelhasználást „ki tud termelni“ az A technológiával jellemzett gazdaság. Továbbá 1T A = 1T X x

ahol

−1

= ( x T − zT ) x

−1

= xT x

−1

− zT x

−1

z az elsődleges erőforrás-felhasználás vektora. Mivel x is és z is nem negatív vektorok, A nem negatív mátrix, azért nyílván xT x

−1

≥ zT x

−1

tehát 1T A ≤ x T x

−1

= 1T x x

−1

= 1T .

Ez azt jelenti, hogy a valamennyi oszlopösszeg - így a minimális is, meg a maximális is - kisebb mint 1, tehát az A technológiai mátrix Perron-Frobenius sajátértéke is kisebb mint 1. Ez pedig a Perron-Frobenius tétel d.) pontja szerint azt jelenti, hogy a Leontyev-inverz létezik és szigorúan pozitív. Ebből pedig az következik, hogy bármely pozitív y-ra

b

x = E−A

g

−1

y>0

Tehát a Walras-Leontyev hipotézis fontos következménye, hogy amennyiben a gazdaság egyszer produktívnak bizonyul, akkor amíg mélyreható technológiai változások nem következnek be (a koefficiensek stabilak maradnak), addig biztosan az is marad. Nem is olyan könnyű tehát egy működő gazdaságot tönkre tenni!

64

A bizonyítás ezúttal is megtalálható Zala Ernő könyvében, az 56-57. oldalakon. Az egész elméletnek igen kerek és teljes tárgyalása található H. Nikaido „Convex Structures and Economic Theory“ (Academic Press, N.Y. & London, 1968) című könyvének II. fejezetében. A könyv 1972-ben megjelent oroszul is.

94

C. A LEONTYEV-INVERZ ÉS A HALMOZOTT, VAGY TELJES RÁFORDÍTÁSOK

A Leontyev-modell (mind a nyílt, mind a zárt) A mátrixa, mint technológiai mátrix a közvetlen ráfordításokat tükrözi. A definiciónak megfelelően az aij koefficiens azt mutatja meg, hogy egységnyi j-dik termék előállításához hány egység i-dik terméket használnak fel közvetlenül. Ha például 1 tonna acél (j-dik termék) előállításához 1,8 tonna kőszénre (i-dik termék) van szükség, akkor a kőszén sorának és az acél oszlopának kereszteződésében 1,8 áll 65 . Ugyanakkor az acél gyártásához acélt is használnak, amelynek előállítására szintén kell kőszenet használni. A kőszén előállításához szintén szükség van acélra, amihez viszont kőszénre van szükség. A többi termékről még nem is beszéltünk, pedig a feltételezésünk, hogy az A mátrix irreducibilis közgazdaságtanilag azt jelenti, hogy valamely termék (például az acél) előállításához közvetlenül vagy közvetve az összes többi terméket felhasználják. Az a benyomásunk támadhat, hogy ha minden közvetett felhasználást számbaveszünk, akkor végtelen mennyiségeket kapunk. Ez azonban nem így van. Egységnyi j-dik termék előállításához aij i-dik terméket használnak fel közvetlenül. De az egységnyi j-dik termékhez minden termékből kell valamennyit ráfordítani. Ezt az a Tj = a 1 j , a 2 j ,..., a ij ,..., a nj

vektor elemei fejezik ki. Az i-dik terméket ezeknek az előállításához is fel kell használni, összesen

b2g

a ij = a 1 ja i1 + a 2 ja i2 +... + a ija ii +... + a nja in = a Tj a i

mennyiségben, ahol a Tj az A mátrix j-dik oszlopa, ai pedig az i-dik sora. Az ezekből az elemekből felépített A(2) mátrix a másodlagos ráfordítások mátrixa:

A

b2 g = A ⋅ A = A 2

Analóg módon megkaphatjuk a harmadlagos, negyedleges, stb. ráfordítások mátrixait: A

b3g = A b2g ⋅ A = A 3 , A b4g = A b3g ⋅ A = A 4 , stb.

A teljes közvetett ráfordítás mátrixa ∞

A = ∑A s=1

b sg =

∞

∑A

s

s =1

Ez persze csak egy szimbólikus felírás. Egyenlőre nem bizonyított az A létezése, a végtelen mátrixsor konvergenciája. Mindenestre, ha a sor konvergens, akkor a végső felhasználás és a végső felhasználás teljes ráfordítása együttesen a kibocsátást kell, hogy adja:

65

Előző okfejtéseinkből az következett, hogy az A mátrix oszlopösszegei nem nagyobbak 1-nél, tehát a koefficiensek biztosan kisebbek 1-nél. Az itt közölt 1,8 senkit ne tévesszen meg. Az előző levezetések ugyanis feltételezték, hogy a technológiai mátrix elemei egyneműek. Itt az 1,8 tonna kőszén/tonna acélban van mérve. Nyugodtan kijelenthetjük, hogy 1,8 tonna kőszén/tonna acél kisebb mint 1 - feltéve, hogy a gazdaság valóban működőképes. Ha például az összehasonlító árakkal a koefficienseket „közös nevezőre“ hozzuk, akkor ez az állítás valóban igaz lesz. Ezzel a következő pontban fogunk foglalkozni.

95

d

i

x = y + Ay = Ey + Ay = E + A + A 2 + A 3 +... y

A zárójelben szereplő mátrixsor neve Neumann-sor, amelynek az összege, ha létezik, a teljes ráfordítás mátrixa. A Neumann-sor konvergenciájának kérdése az elmélet fontos problémája. Korábban már megmutattuk, hogy a Perron-Frobenius tétel alapján a statisztisztikailag előállított ÁKM-ből a Walras-Leontyev hipotézis alapján megalkotott technológiai mátrixnak létezik az (E-A)-1 szigorúan pozitív Leontyev-inverze. Ehhez csak az kellett, hogy belássuk, az A mátrix oszlopösszegei kisebbek 1-nél. A Leontyev-inverz segítségével kifejezhető a kibocsátás vektora a végső felhasználás vektorából:

b

x = E−A

g

−1

y

A két összefüggés szoros kapcsolatot sejtet a Leontyev-inverz és a Neumann-sor között. Azonban ne feledjük el, a Leontyev-inverz létezését már igazoltuk, a Neumann-sor konvergenciája viszont még bizonyításra szorul. Nem tekinthető tehát evidenciának, hogy a Neumann-sor összege egyenlő a Leontyev-inverzzel. Ugyanakkor bizonyítható a következő Egy nem negatív négyzetes mátrixnak akkor és csak akkor konvergens a Neumann-sora, ha létezik félpozitív Leontyev-inverze, amely éppen a Neumannsor összege lesz.

TÉTEL

Tegyük fel, hogy a Neumann-sor konvergens, azaz

S = E + A + A 2 + A 3 +...

Ekkor AS = SA = A + A 2 + A 3 +... = S − E

azaz

b

g

b

g

b

g

S − AS = S − AS = E − A S = S E − A = E

tehát

S = E−A

−1

.

Mivel A nem negatív, és a létező S első tagja az egységmátrix, azért a Neumann-sor konvergenciájából nem csak a Leontyev-inverz létezése és nem negativitása következik, hanem az is, hogy a főátlón levő elemei nem kisebbek 1-nél, tehát félpozitív. Nem nehéz a tétel másik felének bizonyítása sem. Ha létezik félpozitív Leontyev-inverz, akkor valamely y>0 vektorra létezik x=(E-A)-1y>0 vektor, amely kielégíti az x>Ax egyenlőtlenséget. Ekkor található olyan 0
Tekintsük az E+A+A2+A3+...+An véges mátrixsort. Ennek összege legyen Sn. A közönséges mértani sorozatok elméletéből ismert eljárás analógiájára belátható, hogy

96

d

ib

S n = E − A n +1 E − A

b

gb

Mivel lim A n = 0 , azért lim S n = E − 0 E − A n →∞

n →∞

g

−1

g = bE − A g −1

−1

. Ez viszont éppen a Ne-

umann-sor összege. A tételt tehát bebizonyítottuk. Nem nehéz belátni, hogy irreducibilis A mátrix esetén a Leontyev-inverz e tétel alapján szigorúan pozitív lesz. Ez tökéletesen összhangban van a Perron-Frobenius tétellel. 3. DUALITÁS AZ ÁKM-BEN, AZ ÁKM ALKALMAZÁSAI A.) DUALITÁS

Láttuk, hogy ha az A technológiai mátrix minden oszlopösszege nem nagyobb, mint 1, akkor a Neumann-sora biztosan konvergens, a Leontyev-inverz biztosan létezik és nem negatív (sőt félpozitív). Legyen azonban A egy naturális technológiai mátrix, amelynek egyes oszlopösszegei esetleg nagyobbak 1-nél. A feladat: keresni egy olyan mértékegységvektort, amellyel „közös nevezőre hozva“ a mátrixot, az megfelelő alakúvá válik, vagyis az új oszlopösszegek maximuma nem lesz nagyobb 1-nél. Legyen a mértékegység-vektor p. Ennek elemeivel az oszlopokat el kell osztani, a sorokat meg kell szorozni. Megoldandó tehát a következő egyenlőtlenség: 1T p A p

−1

≤ 1T

Ha ezt beszorozzuk jobbról a p diagonális mátrix-szal, akkor a következő egyenlőtlenséget kapjuk: pT A ≤ pT

Ez feltűnően hasonlít a nyílt Leontyev-modell Ax ≤ x alakjához. A hasonlóság jóval több, mint véletlen. Itt dualitási kapcsolatról van szó. Érvényes az alábbi TÉTEL

(Gale duális produktivitási tétele) Az Ax ≤ x egyenlőtlenségnek akkor és csak akkor van pozitív megoldása, ha a p T A ≤ p T egyenletnek van pozitív megoldása. Milyen interpretációja lehetséges a duális modellnek?

Amikor olyan új egységeket kerestünk a naturális technológiai mátrixnak, amelyek mintegy „közös nevezőre“ hozzák a koefficienseket, akkor tulajdonképpen valamiféle árakkal próbáltuk beárazni modellünket. Balról szorozva a technológiai mátrixot egy fekvő árvektorral az egységnyi termelés fajlagos költségeit határoztuk meg. Maga az árvektor, mint egységárak vektora egyben az egységnyi kibocsátás árbevétel-vektora is. A különbség pT − pT A

tehát az egységnyi kibocsátások tiszta jövedelme. Így Gale duális tételének közgazdasági értélme: Egy Leontyev-modell akkor és csak akkor produktív, ha legalább egy pozitív árvektorra jövedelmező, illetve akkor és csak akkor jövedelmező, ha legalább egy pozitív kibocsátás vektorra produktív.

97

B.) ALKALMAZÁSOK

Az ÁKM alkalmazásainak többsége azon a fentebb igazolt tételen alapszik, hogy a Leontyev-inverz egyben a teljes ráfordítások mátrixa is. Az ÁKM segítségével két alapszámítás végezhető el, mint az az eddigiekből kiderült. Egyrészt megkereshető adott y>0 végfelhasználáshoz az azt biztosító x≥0 kibocsátásvektor

a.)

b

x = E−A

g

−1

y.

Másrészt megkereshető adott fajlagos π>0 jövedelemszinthez az azt biztosító p>0 árvektor

b

pT = π T E − A

b.)

g

−1

.

Az árvektor matematikailag (és megfelelő interpretáció esetén közgazdaságtanilag is) ekvivalens viselkedésű az elsődleges erőforrások teljes ráfordítás-vektoraival. Így a π helyére bármilyen elsődleges erőforrás-vektort írva az a.) pont második egyenlete teljes tartalom számításokra válik alkalmassá. Szokásosan a következő számításokat lehet felsorolni: •

a bruttó kibocsátás (GDP) teljes import tartalma

•

a bruttó kibocsátás teljes munka tartalma

•

a bruttó kibocsátás teljes energia tartalma stb.

c.)

Az ÁKM alkalmas szimulációs számítások végzésére. Itt ismét kétféle számításra nyílik lehetőség a primál és duál modell felhasználásával. Egyrészt, megváltoztatható valamely i-ik ágazat yi végső felhasználásának volumene és az új y1 vektorral kiszámítható az új x1GDP-vektor. Képezve ezután a Δix=x0-x1

GDP-különbözet vektort, következtetéseket vonhatunk le az ágazati igények megváltozásának nemzetgazdasági következményeiről. Másrészt, analóg módon megváltoztatva egy j-ik ágazat pj árát az új p1 árvektorral kiszámítható az új π1 fajlagos nyereség vektor. Ezután meghatározható a Δjπ=π0-π1

nyereség-differencia vektor elemezhetővé válnak az árváltozások hatásai a jövedelmezőségi viszonyokra. Az ilyen számítások hasznosan készíthetik elő a gazdaságpolitikai döntéseket. d.)

Végül a b.) és a c.) alatti számítások kombinálhatóak, amennyiben szimulálható valamely ágazat valamely elsődleges erőforrás-felhasználásának változása és annak nemzetgazdasági következményei.

98

TARTALOMJEGYZÉK A gazdasági allokáció matematikai modelljei ...............................................................................................1 Tematika...........................................................................................................................................................1 Bevezetés...........................................................................................................................................................2 Történeti áttekintés (Első előadás).................................................................................................................3 1. QUESNAY DOKTOR „CIKK-CAKKJAI“ - A GAZDASÁGI TÁBLÁZATOK .........................3 2. MARX DOKTOR ÚJRATERMELÉSI SÉMÁI .............................................................................8 3. LEON WALRAS EGYENLETRENDSZERE ...............................................................................16 4. A TÖRTÉNET FOLYTATÁSA .....................................................................................................18 A.) LINEÁRIS PROGRAMOZÁS.........................................................................................18 B.) INPUT-OUTPUT ELEMZÉS ..........................................................................................19 C.) AZ ÁLTALÁNOS EGYENSÚLY ELMÉLETE .............................................................19 Közgazdaságtan és operációkutatás (Második előadás) ..............................................................................21 1. MATEMATIKAI JELÖLÉSEK A KÖZGAZDASÁGI IRODALOMBAN ..................................21 A.) A DERIVÁLÁS JELÖLÉSEI ..........................................................................................21 B.) A LINEÁRIS EGYENLETRENDSZEREK ÁBRÁZOLÁSA.........................................23 2. NÉHÁNY SZÓ AZ OPTIMUMOKRÓL .......................................................................................25 Egyszerű allokációs modellek (Harmadik előadás) ......................................................................................33 1. NÉHÁNY SZÓ A LINEÁRIS PROGRAMOZÁSRÓL - A DUALITÁS ÉS AZ ERŐFORRÁSOK GAZDASÁGI ÉRTÉKELÉSE .............................................................................33 A.) A DUALITÁS ELVE.......................................................................................................33 B.) DUALITÁS A LINEÁRIS PROGRAMOZÁSBAN........................................................34 C.) AZ ÁRNYÉKÁRAK KÖZGAZDASÁGTANI INTERPRETÁCIÓJA...........................36 2. EGY JELLEGZETES ALLOKÁCIÓS LP FELADAT: KANTOROVICS GÉPTERHELÉSI FELADATA..........................................................................................................38 A.) A FELADAT....................................................................................................................38 B.) A JAVÍTOTT ALGORITMUS ........................................................................................47 3. A HOZZÁRENDELÉSI FELADAT ..............................................................................................53 A.) A „MAGYAR MÓDSZER“.............................................................................................53 B.) A SZÁLLÍTÁSI FELADAT.............................................................................................60 Allokációs modellek különleges terekben (Negyedik előadás).....................................................................63 1. NEM HAGYOMÁNYOS ALLOKÁCIÓS PROBLÉMÁK ...........................................................63 A.) TÖBB CÉLFÜGGVÉNYES FELADAT. ........................................................................63 B.) PARAMETRIKUS PROGRAMOZÁS ............................................................................64 C.) FELADATOK, AMELYEK TELJESEN KILÓGNAK A HAGYOMÁNYOS LP KERETEIBŐL ................................................................................65 2. A RÉSZBEN RENDEZETT LINEÁRIS TEREKRŐL ..................................................................67 3. LINEÁRIS PROGRAMOZÁS RÉSZBEN RENDEZETT VEKTORTEREKBEN.......................72 A.) EGY ABSZTRAKT SZÁLLÍTÁSI FELADAT MEGOLDÁSA.....................................77 B.) EGY ABSZTRAKT STANDART LP FELADAT ..........................................................82

99

Input-output elemzés, az ágazati kapcsolatok modellje (Ötödik előadás)..................................................86 1. A MODELL ....................................................................................................................................86 A.) AZ ÁGAZATI KAPCSOLATOK MÉRLEGE................................................................86 B.) A STATIKUS LEONTYEV-MODELL...........................................................................87 2. A LEONTYEV-MODELL MATEMATIKAI ELEMZÉSE...........................................................89 A.) ZÁRT LEONTYEV-MODELL .......................................................................................89 B.) NYÍLT LEONTYEV-MODELL ......................................................................................93 C. A LEONTYEV-INVERZ ÉS A HALMOZOTT, VAGY TELJES RÁFORDÍTÁSOK .................................................................................................................95 3. DUALITÁS AZ ÁKM-BEN, AZ ÁKM ALKALMAZÁSAI.........................................................97 A.) DUALITÁS ......................................................................................................................97 B.) ALKALMAZÁSOK .........................................................................................................98 Tartalomjegyzék ..............................................................................................................................................99

100