Cím:	Mit rakjunk a hátizsákba, hogyan váltsunk fel pénzt ? I. rész
Szerző(k):	Vízvári Béla
Füzet:	1996/október, 386 - 391. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.     1. A kényelmes turista     Egyszer volt, hol nem volt, volt egyszer egy turista. Volt ennek a turistának mindenféle tárgya, amit elvihetett magával. Minden tárgynak megvolt a maga súlya, amivel húzta bizony a szegény turista hátát. Egy-egy tárgynak azonban nemcsak súlya, hanem értéke is volt, a turista által meghatározott absztrakt, eszmei értéke, amellyel a tárgy hozzájárult a kirándulás öröméhez. Gondolkodóba esett egyszer a turista, mit is vigyen magával. Mert, ugye, túl sokat nem akart cipelni, de azt is szerette volna, ha a vele lévő tárgyak összértéke minél nagyobb. Végül arra az elhatározásra jutott, hogy megállapít egy súlyhatárt, aminél többet biztosan nem visz, a tárgyakat pedig úgy válogatja össze, hogy az együttes súlyuk ezt a korlátot ne haladja meg, de az értékük a lehető legnagyobb legyen. Ekkor azonban újabb nehézsége támadt. Az elv ugyanis egyszerű, de hogyan lehet megvalósítani? Próbáljunk a turista gondjain segíteni. Tegyük fel, hogy a turistának $n$ különböző tárgya van. Az $1$, $2$, $\text{...}$, $j$, $\text{...}$, $n$ tárgy súlyát és értékét jelölje rendre $a_1$, $a_2$, $\text{...}$, $a_j$, $\text{...}$, $a_n$, illetve $c_1$, $c_2$, $\text{...}$, $c_j$, $\text{...}$, $c_n$. Végül legyen $b$ a turista által a tárgyakra megszabott súlykorlát. Az első megállapítás az, hogy egy tárggyal mindössze két dolgot tehet a turista: vagy elviszi a kirándulásra vagy otthon hagyja. Ha elviszi a $j$ tárgyat, akkor az $a_j$ súllyal húzza a hátát, ennek ellenében viszont a kiránduláson $c_j$ értéke lesz. Ha nem viszi el, akkor úgy vehetjük, hogy a tárgy 0 súllyal terheli gazdáját, de egyúttal 0 az értéke is. Vezessünk be minden $j$ tárgyhoz egy $x_j$ változót. Ez írja le azt a döntést, amit az adott tárggyal kapcsolatban meg kell hozni. $x_j$ csak a 0 és az 1 értéket veheti fel. Legyen a 0 jelentése az, hogy a tárgy otthon marad, míg 1 azt mutatja, hogy a tárgyat el kell vinni. Tekintsük most az $a_j{x}_j$ szorzatot. Ennek is csak két értéke lehet: vagy 0, ha $x_j=0$ vagy $a_j$, ha $x_j=1$. Mindkét esetben tehát ez a szorzat pontosan akkora, amekkora súllyal a tárgy a kiránduláson a turista hátát húzza. Hasonlóképpen a $c_j{x}_j$ szorzat vagy 0, vagy $c_j$, és ez is pontosan akkora, amekkora értéket a tárgy a túra során képvisel, akár otthon marad, akár nem. Ezért az elvitt tárgyak összsúlya $\begin{array}{c}{\displaystyle a_1{x}_1+a_2{x}_2+\text{...}+a_j{x}_j+\text{...}+a_n{x}_n=\sum _{j=1}^n{a}_j{x}_j\mathrm{.}}\end{array}$ Ez a mennyiség nem lehet nagyobb, mint $b$. Ugyanilyen jelöléssel, az elvitt tárgyak összértéke (az ún. célfüggvény): $\begin{array}{c}{\displaystyle \sum _{j=1}^n{c}_j{x}_j\mathrm{.}}\end{array}$ Úgy kell az $x_j$ változók értékét meghatározni, vagyis az elviendő tárgyakat úgy kell összeválogatni, hogy ez az összeg minél nagyobb legyen. Eddigi megállapításainkat összefoglalva a következő optimalizálási feladathoz jutunk, amelyet hátizsák feladatnak neveznek: meghatározandó $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle \underset{}{\overset{}{\text{max}}}}& {\displaystyle \sum _{j=1}^n{c}_j{x}_j\mathrm{,}}\hfill \\ \hfill {\displaystyle \text{ha}}& {\displaystyle \sum _{j=1}^n{a}_j{x}_j\le b\text{és}}\hfill & \hfill {\displaystyle \left(1\right)}\\ \hfill {\displaystyle }& {\displaystyle x_1\mathrm{,}\text{...}\mathrm{,}{x}_n=0\text{ vagy }1.}\hfill \end{array}}}\end{array}$ A hátizsák feladat a problémák egy nehéz osztályába esik. Eddig nem találtak olyan egyszerű képletet, ami megadná az optimális megoldást, és általános vélemény szerint ilyen képlet nincs is, bár ezt még nem sikerült bizonyítani. (Ellentétben az ötödfokú egyenlettel, amiről tudjuk, hogy nincs megoldóképlete.) Ezért a feladat megoldásán egy olyan számítási eljárást, azaz algoritmust értünk, amely biztosan megadja az optimális megoldást. Mivel az optimalizálási feladatok körében gyakoriak a hasonlóan nehéz problémák, ezért az operációkutatás egyik fontos területe hatékony algoritmusok keresése. Azért kell itt az eljárás hatékonyságát kiemelni, mert sok esetben magától értetődően adódik egy módszer, amivel azonban csak kicsi feladatokat lehet megoldani. A hátizsák feladat esetében ez nem volna más, mint a változók összes lehetséges értékének megfelelő $2^n$ eset megvizsgálása. De gondoljuk meg, hogy ez már 30 tárgy esetén is $1073741824$ eset, azaz több, mint egy milliárd. Nem nehéz a tárgyakra olyan számot megadni, ahol már annyi esetet kellene megvizsgálni, amennyivel a számítógépek sem bírnak. Ugyanakkor nem okoz problémát akár $10000$ tárgyat tartalmazó hátizsák feladat megoldása sem. Ekkor persze sokkal célszerűbben kell eljárni.     2. Mindenféle tárgyak     A fentiekben tárgyak súlyáról és értékéről beszéltünk. Nem mondtuk ki, de mindenki joggal úgy érthette, hogy minden tárgy súlya is, értéke is pozitív. Azonban egy hátizsákra felkötött léggömb például, amint igyekszik felszállni, emeli a hátizsákot, vagyis a súlya negatív. A pálpusztai pedig ‐ egy, az érettebb sajtokat nem kedvelő turista esetében ‐ negatív értékkel bír, hiszen ,,illata'' elrontja a jó erdei levegőt. Négy esetet különböztetünk meg, amelyeket egy-egy jellegzetes képviselőjükről neveztünk el: (i) az ,,iránytű'' esete: az iránytű a kirándulás alkalmával hasznos tárgy, amely valamekkora pozitív súllyal rendelkezik, azaz $c_j>0$, $a_j>0$, (ii) a ,,pozitív léggömb'' esete: amikor a léggömb örömet okoz a kiránduláson, és még az az előnye is megvan, hogy emeli a hátizsákot, azaz $c_j\ge 0$, $a_j<0$, (iii) a ,,pálpusztai'' esete, ami húzza a turista vállát, és büdösíti a levegőt, azaz $c_j\le 0$, $a_j\ge 0$, (iv) a ,,negatív léggömb'' esete, amikor igaz ugyan, hogy segít emelni a hátizsákot, de zavart okoz, hogy amikor a bozóton átcsörtetünk, a madzagja minduntalan beleakad az ágakba, azaz $c_j<0$, $a_j<0$. A (iii) esetbe csempésztük be azt is, amikor a tárgy jelenléte közömbös, azaz $c_j=0$, de a súlya nemnegatív. Könnyű látni, hogy a pozitív léggömb és a pálpusztai esete azonnal eldönthető. A (ii)-be tartozókat ugyanis mindenképpen el kell vinni, és biztosan nem rontjuk (ha $c_j=0$), sőt az esetek többségében kifejezetten javítjuk (ha $c_j<0$) a megoldást, ha a (iii)-ba tartozó tárgyakat otthon hagyjuk. A gond az (i) és (iv) esetekkel van. Az iránytűnél azt kell valamilyen értelemben eldönteni, hogy több értéket jelent-e, mint amekkora a súlya, a negatív léggömbnél pedig azt, hogy jobban emeli-e a hátizsákot, mint amekkora bajt okoz. Szerencsére a két eset egységesen kezelhető. Ha ugyanis a $j$ tárgy egy negatív léggömb, akkor vezessük be az $y_j$ változót, amit az $\begin{array}{c}{\displaystyle y_j=1-x_j}\end{array}$ egyenlettel definiálunk. Nyilvánvalóan $y_j$ maga is csak a 0 és az 1 értéket veheti fel. Továbbá $a_j{x}_j=a_j\left(1-y_j\right)=a_j-a_j{y}_j$. Itt $y_j$ együtthatója $-a_j>0$. Ha tehát mind a célfüggvényben, mind az egyenlőtlenségben $x_j$ helyére behelyettesítjük az $1-y_j$ értéket, akkor a bevezetett új változó együtthatója mindkét helyen pozitív lesz. Így az általánosság megszorítása nélkül feltehető, hogy az (1) feladatban minden együttható pozitív. Elterjedt az a szokás, hogy ha ez igaz egy optimalizálási feladatban, és annak csak egy feltétele van, akkor azt hátizsák feladatnak nevezik. Más hátizsák feladatokról még szó lesz.     3. Hátizsák mindenhol     Furcsa, de a turista igen mesterségesnek ható problémája az élet számos területén felmerül. Egy befektető vállalat javaslatokat kap, hogy pénzét mire használja. Minden javaslat tartalmazza a befektetendő összeget ($a_j$) és a várható éves nyereséget ($c_j$). Ismert a vállalat tőkéjének nagysága ($b$). Egy javaslat vagy teljes egészében megvalósul, vagy semmi se lesz belőle. Ekkor tehát a súlyhatár a befektethető tőke, a tárgyak a javasolt projektek, és a maximális hasznot akarjuk elérni. Néha az állami pénzköltés haszna szellemi természetű, forintban nem fejezhető ki. Ilyen a tudomány támogatása. Az erre fordítható pénzekért kutatási programokkal kell pályázni a pénzről döntő állami szervnél. A pályázatokat szakértők értékelik, akik a bírált pályázatokat különböző szempontok alapján pontozzák. Így a vélemények összegeként kialakul az egyes pályázatok eszmei értéke ($c_j$), míg a súlya a kért összeg nagysága ($a_j$). A súlykorlát a felhasználható keret ($b$). A pénz legjobb elosztásakor a támogatást a maximális szellemi érték kapja meg. Nézzünk valami egészen mást. Egy gyárban van két azonos célú, de technikai paramétereiben különböző gép. Minden terméket a kettő közül pontosan az egyik munkálja meg. Vannak olyan termékek, amelyek csak az egyikre kerülhetnek, vannak olyanok, amelyek csak a másikra, és végül a többség bármelyikre. Az utóbbi esetben nekünk kell eldönteni, hogy melyikre. Mivel már előrehaladott tárgyalásokat folytatunk, ezért arra számítunk, hogy be fog érkezni egy nagyobb rendelés olyan termékre, amely csak az egyik, mondjuk, az első gépen munkálható meg. Úgy kell szétosztani tehát a két gép mindegyikén legyártható termékeket a gépek között, hogy az első gépnek minél több szabad kapacitása maradjon. Tegyük fel, hogy a második gép kapacitása, miután legyártotta a csak rajta megmunkálható termékeket időben kifejezve, $b$. Tegyük fel továbbá, hogy $n$ olyan megrendelt termék van, amely mindkét gépen gyártható. Az első, ill. a második gépen a megmunkálási idejük legyen rendre $p_{11}$, $\text{...}$, $p_{1j}$, $\text{...}$, $p_{1n}$, ill. $p_{21}$, $\text{...}$, $p_{2j}$, $\text{...}$, $p_{2n}$. Minden termékhez vezessünk be ismét egy $x_j$ változót, ami 0 vagy 1; 1 akkor, ha a terméket a második gépen gyártjuk, és 0 különben. Mivel a termék mindenképpen rákerül a gépek valamelyikére, ezért $1-x_j$ pontosan akkor $1$, ha a terméket az első gép gyártja. A fentiekhez hasonlóan $p_{2j}{x}_j$ az az idő, amit a $j$ termék a második gépen eltölt. Ez vagy 0, ha a terméket az első gép készíti, vagy $p_{2j}$ ha a második. Tehát az ilyen szorzatok összege nem haladhatja meg $b$-t. Hasonlóképp, $p_{1j}\left(1-x_j\right)$ az az idő, amit a termék az első gépen tölt el. Az ilyen szorzatok összegét kell minimalizálnunk. Végül a $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle \underset{}{\overset{}{\text{min}}}}& {\displaystyle \sum _{j=1}^n{p}_{1j}\left(1-x_j\right)}\hfill \\ \hfill {\displaystyle }& {\displaystyle \sum _{j=1}^n{p}_{2j}{x}_j\le b}\hfill & \hfill {\displaystyle \left(2\right)}\\ \hfill {\displaystyle }& {\displaystyle x_1\mathrm{,}\text{...}\mathrm{,}{x}_n=0\text{ vagy }1}\hfill \end{array}}}\end{array}$ feladatot kapjuk. Ez látszólag különbözik a hátizsák feladattól. A feltétellel nincs baj, mert az csak elnevezés kérdése, hogy az együtthatókat $a_j$-vel vagy $p_{2j}$-vel jelöljük, de a célfüggvényben most nem maximalizálni kell, hanem minimalizálni. Vegyük szemügyre hát a célfüggvényt: $\begin{array}{c}{\displaystyle \sum _{j=1}^n{p}_{1j}\left(1-x_j\right)=\sum _{j=1}^n{p}_{1j}-\sum _{j=1}^n{p}_{1j}{x}_j\mathrm{.}}\end{array}$ A jobb oldalon az első tag állandó, tehát nem befolyásolja az optimum helyét. A negatív előjel miatt a célfüggvény akkor lesz minél kisebb, ha jobb oldal második összege minél nagyobb. Tehát azt kapjuk, hogy a (2) feladattal ekvivalens a $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle \underset{}{\overset{}{\text{max}}}}& {\displaystyle \sum _{j=1}^n{p}_{1j}{x}_j}\hfill \\ \hfill {\displaystyle }& {\displaystyle \sum _{j=1}^n{p}_{2j}{x}_j\le b}\hfill & \hfill {\displaystyle \left(3\right)}\\ \hfill {\displaystyle }& {\displaystyle x_1\mathrm{,}\text{...}\mathrm{,}{x}_n=0\text{ vagy }1}\hfill \end{array}}}\end{array}$ problémával, ami már valóban egy hátizsák feladat.     4. Hogyan fizetik ki a fizetést?     Fizetésnapon azoknak a fizetését, akik nem utaltatják át bankszámlájukra, borítékba rakják. A cél ennél a műveletnél, hogy a lehető legkevesebb pénzdarabot használják fel. Ezt szinte kivétel nélkül minden pénzrendszerben egy úgynevezett mohó eljárással lehet elérni. Vesszük a lehető legnagyobb címletet, mégpedig annyiszor, ahányszor lehet, utána a következő lehető legnagyobb címletet ismét csak annyiszor, ahányszor csak lehet, és így tovább. Tegyük fel, hogy $n$ különböző címlet van, ezek $1=a_1<a_2<a_3<\text{...}<a_n$. Azért tesszük fel, hogy a legkisebb címlet $1$, mert ha nem így volna, akkor nem lehetne minden összeget kifizetni. Feltesszük továbbá, hogy a címletek mind egész számok. Legyen $\alpha$ egy valós szám, ekkor $\left[\alpha \right]$ az $\alpha$ egész része, vagyis az a legnagyobb egész, ami nem nagyobb nála. Például $\left[\mathrm{0,51}\right]=0$, $\left[2\right]=2$, $\left[-\mathrm{2,51}\right]=-3$. Ekkor a mohó módszer a következő képletekkel írható le. Legyen $b$ a kifizetendő összeg, $x_j^m\left(j=\mathrm{1,}\text{...}\mathrm{,}n\right)$ az a szám, hogy az $a_j$ címletet hányszor használjuk fel ezen módszer szerint. A mondottak szerint először azt kell meghatározni, hogy a legnagyobb címletből hányat veszünk, vagyis mekkora $x_n$ értéke a mohó megoldásban: $\begin{array}{c}{\displaystyle x_n^m=\left[\frac{b}{a_n}\right]\mathrm{.}}\end{array}$ (4) Ettől függ, hogy az $a_{n-1}$ címletet hányszor lehet felhasználni, hiszen a szabályt a maradék összegre kell alkalmazni: $\begin{array}{c}{\displaystyle x_{n-1}^m=\left[\frac{b-a_n{x}_n^m}{a_{n-1}}\right]\mathrm{.}}\end{array}$ Ha ezt folytatjuk az indexeken visszafelé (csökkenő sorrendben) haladva, akkor a következő általános szabályt kapjuk: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle \left(5\right)x_j^m=\left[\frac{b-a_n{x}_n^m-\text{...}-a_{j+1}{x}_{j+1}^m}{a_j}\right]=\left[\frac{b-\sum _{i=j+1}^n{a}_i{x}_i^m}{a_j}\right]}\\ \hfill {\displaystyle j=n-\mathrm{1,}n-\mathrm{2,}\text{...}\mathrm{,}1.}\end{array}}}\end{array}$ A magyar pénzrendszer elég egyszerű, minden egység esetében van 1-es, 2-es, 5-ös, majd ez egy 10-szer nagyobb egységgel megismétlődik. Tehát van például 1, 2 és 5 forintos, majd a forint után a következő nagyobb egység a 10 Ft, ebből van 10 forintos, 20 forintos, 50 forintos. A százasoknál hasonlóan (a 200 forintos érme). Hiányzik viszont a 2000 forintos. Tehát amikor a fenti formalizált szabályt $23567$ Ft-ra alkalmazzuk, akkor a (4) képlet alapján a jelenlegi legnagyobb címletre, az 5000 forintosra 4-et kapunk. Így marad 3567 Ft. Ehhez kell 3 db 1000 forintos, 1 db 500 forintos, majd 0 db 200 és 100 forintos, 1 db 50 forintos, 0 db 20 forintos, 1 db 10, 5 és 2 forintos és 0 db 1 forintos. Itt most nem bizonyítjuk, de igaz, hogy ha egy pénzrendszer olyan, hogy az alacsonyabb címletek mindig osztói a magasabb címleteknek, akkor a fenti mohó szabály mindig a lehető legkevesebb darab pénzt használja fel. Ha azonban az alacsonyabb címletek nem osztói a magasabb címleteknek, akkor könnyű olyan rendszert csinálni, amiben a mohó módszer nem minden esetben adja ki az optimális megoldást. Például, ha bevezetnénk a 21 forintost, ahogy régen Angliában létezett az 1 fontos (= 20 shilling) mellett a guinea, ami 21 shilling volt, akkor a 40 Ft-tal máris bajban lennénk. Ugyanis a mohó szabály szerint ezt 1 db 21, 10 és 5 forintossal és 2 db 2 forintossal kellene kifizetni, vagyis összesen 5 db pénzzel, miközben a 2 db 20 forintos továbbra is az optimális megoldás lenne. Ha a pénz kifizetését egy matematikai feladattal akarjuk leírni, akkor az egyetlen dolog, amit észre kell venni, hogy minden címletet csak egész számszor lehet felhasználni. Erre a tényre már a mohó módszer megfogalmazásánál is tekintettel voltunk. Használva a fenti jelöléseket, így a következő feladathoz jutunk: (6) Itt a célfüggvény értéke éppen azt adja meg, hogy a megoldás hány pénzdarabot használ, az egyenlet nemnegativitással együtt azt biztosítja, hogy pontosan az előírt összeget fizetjük ki, hiszen a negatív $x$ érték azt jelenti, hogy egy bizonyos pénzt visszakapunk. Az utolsó feltétel, ahogy már említettük, minden címletből csak egész darab felhasználását engedi. Felfoghatjuk a feladatot kissé általánosabban is. Például egy-egy pénzdarab előállításának van valamekkora költsége, ami mindig csak a címlettől függ. Így beszélhetünk minimális darabszámú kifizetés helyett ebben az értelemben vett minimális költségű kifizetésről. De hasonlóképpen értelme lehet minimális súlyú kifizetésről beszélni, mert a pénzdarabok súlya ismét csak a címlettől függ, sőt a súly a címlet egyik nagyon fontos jellemzője fémpénzek esetén. Ugyanis a különböző automatákban a pénz azonosítása erősen támaszkodik a súlyra. Ha a feladatot így fogjuk fel, akkor legyen $c_1$, $c_2$, $\text{...}$, $c_n$ az egyes címletek immár absztrakt költsége vagy súlya. Ezekről feltesszük, hogy pozitív egészek. Ekkor a probléma általánosabb alakja (7) A korábban mondottak szerint ez a feladat is a hátizsák feladatok közé tartozik. Megoldása szintén nehéz abban az értelemben, hogy a megfelelő számításokhoz sok művelet elvégzésére van szükség. Erre a feladatra a mohó módszert ugyanúgy a (4), (5) képletekkel definiáljuk. Emögött az a megfontolás van, hogy a jegybanknak akkor éri meg egy új, nagyobb $\left(n+1\right)$-edik címletet kibocsájtani, ha ennek fajlagos előállítási költsége, vagyis a $\frac{c_{n+1}}{a_{n+1}}$ hányados kisebb a korábbi címletek fajlagos előállítási költségénél. A jegybank szempontjából az a jó, ha a nagyobb címleteket használják. Ettől függetlenül egy-egy konkrét összeg kifizetésénél más lehet a helyzet. A fenti példát felfoghatjuk úgy is, hogy ott minden címlet előállításának költsége 1 Ft. Ha a létező címletek 1, 2, 5, 10 és 20 Ft, és bevezetjük a 21 forintos címletet, akkor csökkent a minimális fajlagos költség 1/20-ról 1/21-re, mégis van olyan összeg, amire a mohó megoldás nem optimális. A mohó módszer csak közelítő megoldást ad, ami persze sokszor azonos az optimális megoldással. Arról, hogyan lehet biztosan megtalálni az optimális megoldást, a következő részben lesz szó. Vizvári Béla Budapest, ELTE