1. el˝oad´as Eg´ esz´ ert´ ek˝ u programoz´ as v´ ag´ asokkal A kor´ abbiakban megismerkedt¨ unk az eg´esz ´ert´ek˝ u line´aris programoz´asi feladatokkal, jelent˝ os´eg¨ ukkel ´es egy hat´ekony megold´asi m´odszerrel. Most Gomorynak egy 1959-b˝ ol sz´armaz´o elj´ar´as´at v´azoljuk, amely eg´eszen m´as, geometriai megfontol´ ason alapszik. Az elgondol´as legnagyobb el˝onye ´es h´ atr´ anya is egyben a nagyfok´ u ´altal´anoss´aga, amely miatt f˝ok´ent elm´eleti jelent˝ os´eg˝ u. B´ ar az eredeti algoritmust elv´etve haszn´alj´ak, az alapgondolata sok l´enyeges eredm´eny kiindul´opontj´aban szerepel. Ez a gondolat a k¨ ovetkez˝o. Ha adott egy IP eg´esz ´ert´ek´ u probl´ema, oldjuk meg a folytonos relax´aci´oj´at. Amennyiben a kapott x∗ megold´as (tulajdonk´eppen egy poli´eder cs´ ucspont) eg´esz koordin´at´aj´ u, akkor k´eszen ∗ vagyunk. Ha nem, akkor hagyjuk el x -ot a lehets´eges megold´asok k¨oz¨ ul, ´es pr´ ob´ alkozzunk u ´jra. Term´eszetesen nem ak´arhogy kell megszabadulnunk x∗ -t´ ol, hiszen a c´elunk, hogy a l´etrej¨ov˝o u ´j feladat(ok) is LP feladat(ok) ∗ legyen(ek). Ez u ´gy ´erhet˝ o el, ha x -ot egy hipers´ıkkal v´agjuk le a lehets´eges megold´ asok poli´eder´er˝ ol, ami algebrailag azt jelenti, hogy egy plussz felt´etelt adtunk az eddigi egyenl˝ otlens´egeinkhez. P´ elda: grafikus m´ odszer max
2x1 +
x2
−x1 + 3x2 x1 + 2x2 x1 − x2 x1 , x2
≤ ≤ ≤ ≥
6 7 3 0 ´es eg´eszek
A probl´em´ ank a s´ıkban ´ abr´azolhat´o. A lehets´eges megold´asai nem m´asok, mint a folytonos relax´ aci´ o P poli´eder´enek ´es a s´ık eg´esz koordin´at´aj´ u pontjainak metszete. Az a ´br´ akon ny´ıllal jel¨olj¨ uk az optimum hely´et.
1
x2
6
b b b b b b b HH H HH Hb b b b b b b HH H HH b Hb b b b b b HH H HH Hb b b b b b b 1 HH b
b
b
0
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
bx1
b
b
b
b
b
b
b
1
b
b
b
b
4 A folytonos feladat megold´asa x∗ = ( 13 esz. Vegy¨ uk fel az 3 , 3 ), nem eg´ x1 ≤ 4 felt´etelt, illetve metssz¨ uk le ezzel a polit´opunkat.
x2
6
b b b b b b b HH H HH b b b b b Hb b HH H HH b b b b b Hb b HH H HH b b b b b Hb 1b HH
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b 0
b
b
b
b
b
b
b
b
bx1
b
b
b
b
b
b
b
1
b
Nagyon fontos, hogy a v´ag´assal nem veszt¨ unk az eredeti IP lehets´eges megold´ asaib´ ol, azaz az eg´esz koordin´at´aj´ u pontokb´ol. Az u ´j folytonos LP optimuma x∗ = (4, 32 ), ami tov´abbra sem eg´esz. Legyen az u ´jabb felt´etel¨ unk az x1 + x2 ≤ 5.
2
x2
6
b b b b b b b HH H HH Hb b b b b b @b HH @ H H@ b b b b HH b b @b H @HH @ HH Hb b b b b b @ b 1 HH @ b
b
b 0
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
bx1
b
b
b
b
b
b
b
1
b
A megold´ as x∗ = (4, 1), ami eg´esz koordin´at´aj´ u. Az eredeti feladatnak lehets´eges megold´ asa, ´ıgy optimuma is egyben. Az optimum ´ert´eke 9. A kezelhet˝ os´eg kedv´e´ert sz¨ uks´eg¨ unk van n´eh´any megszor´ıt´asra a megoldand´ o feladatban. A szok´ asos m´odon a feladat max
cx Ax ≤ b x ≥ 0 ´es x eg´esz
valamint feltessz¨ uk, hogy 1. A, b, c minden komponense eg´esz, 2. b ≥ 0, 3. az Ax ≤ b-vel defini´ alt poli´eder korl´atos. Az 1. felt´etel nem jelent˝os megszor´ıt´as, m´ıg a 2.-re a megoldhat´os´ag garant´ al´ asa miatt van sz¨ uks´eg. Egy teljesen ´altal´anos eg´esz ´ert´ek˝ u probl´em´ anak m´ ar egy lehets´eges megold´ as´ at is nagyon neh´ez megadni, ´ıgy viszont az x = 0 mindig lehets´eges megold´as. A 3.-b´ol k¨ovetkezik, hogy v´eges sok lehets´eges megold´ as van csak, azaz az optimum l´etezik. A v´ ag´ asok prec´ız defin´ıci´oj´ahoz az eg´esz r´esz, illetve a t¨ ortr´esz fogalm´at haszn´ aljuk: egy r val´ os sz´ am [r] eg´esz r´esze a legnagyobb r-n´el kisebb eg´esz, m´ıg az {r} t¨ ortr´esz az {r} := r − [r] egyenl˝os´eggel defini´alt. Az a1 x1 + 3
. . . + an xn ≤ b egyenl˝ otlens´eg Gomory-f´ele metszete pedig az {a1 }x1 + . . . + {an }xn ≥ {b} egyenl˝ otlens´eg. Vezess¨ unk be mesters´eges v´altoz´okat! Ezzel a megszokott sz´ot´aralakra hozhatjuk a feladatot xn+j
= bi −
n P
aij xi (j = 1, . . . , m)
i=1
(∗) z
= 0
+
n P
ci xi
i=1
A felt´etelb˝ ol k¨ ovetkezik, ha x ˜ = (˜ x1 , . . . , x ˜n+m ) a (∗) LP olyan lehets´eges megold´ asa, ahol x˜1 , . . . , x ˜n eg´esz, akkor x ˜n+1 , . . . , x ˜n+m is eg´esz. Oldjuk meg a (∗) feladatot, ´es tegy¨ uk fel, hogy a kapott x∗ = (x∗1 , . . . , x∗n+m ) optim´alis megold´ as nem eg´esz. (Ha ugyanis eg´esz, akkor k´eszen vagyunk.) Az el˝oz˝o megjegyz´es alapj´ an van olyan xi term´eszetes v´altoz´o a v´egs˝o B b´azisban, hogy az x∗i nem eg´esz. Az xi sora a sz´ot´arban (∗∗)
xi = b∗i −
X
a∗ij xj
j6∈B
Mivel x∗i = b∗i ≥ 0 (a sz´ ot´ar lehets´eges), ´ıgy ezt elhagyva a (∗∗) baloldal´ ar´ ol ´es ´ atrendezve az egyenletet kapjuk, hogy X
a∗ij xj ≤ b∗i ,
j6∈B
majd vegy¨ uk ennek a Gomory-f´ele metszet´et: (∗ ∗ ∗)
X
{a∗ij }xj ≥ {b∗i }.
j6∈B
T´ etel 1 A (∗ ∗ ∗) egyenl˝ otlens´eg lemetszi a (∗) LP-r˝ ol az x∗ optim´ alis megold´ ast, de nem metsz le egyetlen eg´esz megold´ ast sem. Bizony´ıt´ as. Az x∗ b´ azismegold´as, ´ıgy x∗j = 0, ha j 6∈ B, s ezzel a (∗ ∗ ∗) ∗ bal oldala az x pontban 0. Az x∗i = b∗i , ´es feltett¨ uk, hogy x∗i nem eg´esz. Ebb˝ ol {b∗i } > 0 ad´ odik, teh´ at az x∗ nem el´eg´ıti ki a (∗ ∗ ∗) egyenl˝otlens´eget. M´ asr´eszr˝ ol legyen x ˜ = (˜ x1 , . . . , x ˜n+m ) a (∗) LP egy tetsz˝oleges eg´esz megold´ asa. Ekkor persze x ˜ kiel´eg´ıti a sz´ot´ar (∗∗) egyenlet´et. Ezt ´at´ırva a jel¨ ol´eseinkkel
4
x ˜i = [b∗i ] + {b∗i } −
X
([a∗ij ] + {a∗ij })˜ xj ,
j6∈B
atrendezve a´ ´ odik, az x ˜i +
X
[a∗ij ]xj − [b∗i ] = {b∗i } −
j6∈B
X
{a∗ij }˜ xj .
j6∈B
Az ut´ obbi egyenl˝ os´eg baloldal´an csak eg´esz sz´amok vannak, ez´ert a bal oldal ´ert´eke eg´esz. Viszont j 6∈ B-re x˜j ≥ 0 ´es {a∗ij } ≥ 0, azaz a jobb oldal ´ert´eke ≤ {b∗i } < 1. Mivel a jobb oldal szint´en eg´esz, az ´ert´ek nem lehet pozit´ıv; vagyis X {b∗i } ≤ {a∗ij }˜ xj , j6∈B
2
azaz x ˜ kiel´eg´ıti a (∗ ∗ ∗) egyenl˝otlens´eget.
T´erj¨ unk vissza a grafikusan m´ar megoldott probl´em´ankhoz ´es vizsg´aljuk meg ezt a Gomory-f´ele metszetek seg´ıts´eg´evel algebrai u ´ton. A x3 x4 x5 z
= 6 +x1 −3x3 = 7 −x1 −2x2 = 3 −x1 +x2 = 0 +2x1 +x2
kezdeti sz´ ot´ arb´ ol k´et iter´ aci´o ut´an befejez˝odik az algoritmus ´es a folytonos relax´ aci´ o megold´ asa: x1 =
13 3
−
2 3 x5
−
1 3 x4
x2 =
4 3
+
1 3 x5
−
1 3 x4
x3 =
19 3
−
5 3 x5
+
2 3 x4
z
= 10 − x5
− x4
2 1 A kapott x∗ megold´ as nem eg´esz, ´ıgy p´eld´aul az x1 = 13 3 − 3 x5 − 3 x4 sor a 23 x5 + 31 x4 ≥ 31 Gomory v´ ag´ast induk´alja. (Ha a kezdeti sz´ot´ar seg´ıts´eg´evel kik¨ usz¨ ob¨ olj¨ uk x4 -et ´es x5 -¨ ot a v´ag´asb´ol, az x1 ≤ 4 egyenl˝otlens´eget kapjuk. ´ Eppen azt, amit a grafikus megold´asban haszn´altunk. Ez r´avil´ag´ıt a Gomory metszet term´eszet´ere ´es mutatja, hogy j´o u ´ton j´arunk.) A 32 x5 + 31 x4 ≥ 13
5
egyenl˝ otlens´eget a nemnegat´ıv x6 v´altoz´o bevezet´es´evel x6 = − 13 + 23 x5 + 13 x4 alakra hozhatjuk. A c´elunk az u ´j feladat folytonos relax´aci´oj´anak megold´asa. Hozz´ av´eve ezt a felt´etelt az utols´o sz´ot´arhoz, egy nagyon ´erdekes sz´ot´art kapunk, amely “optim´ alis” csak ´eppen nem lehets´eges: x1 =
13 3
−
2 3 x5
−
1 3 x4
x2 =
4 3
+
1 3 x5
−
1 3 x4
x3 =
19 3
−
5 3 x5
+
2 3 x4
x6 = − 31
+
2 3 x5
+
1 3 x4
z
− x5
= 10
− x4
Term´eszetes gondolat, hogy a lehets´egess´eget s´ert˝o x6 v´altoz´ot vegy¨ uk ki a b´ azisb´ ol, ´es vigy¨ uk be a hely´ere p´eld´aul az x5 -¨ot: x1 = 4
− x6
+ 0x4
x2 =
3 2
+
1 2 x6
−
1 2 x4
x3 =
11 2
−
5 2 x6
+
3 2 x4
x5 =
1 2
+
3 2 x6
−
1 2 x4
z
19 2
−
3 2 x6
−
1 2 x4
=
A kapott sz´ ot´ ar az u ´j feladat optim´alis megold´as´at k´odolja. Vegy¨ uk ´eszre, hogy tulajdonk´eppen a feladat du´alis´at oldottuk meg. A kezdeti sz´ot´ar “optimalit´ asa” a du´ alis egy lehets´eges megold´as´at adta, illetve mikor a feladat lehets´egess´e v´ alik, az egyben a du´alis optimum´at jelzi. Ekkor viszont a du´ alit´ as t´etel miatt az eredeti feladat optimum´at is megkaptuk. A fenti form´ aban v´egrehajtott algoritmust du´ alis szimplex m´ odszernek nevezz¨ uk, ´es a kifejleszt´ese Lemke (1954) nev´ehez f˝ uz˝odik. Ez eset¨ unkben roppant hasznos, mert a Gomory metszettel b˝ov´ıtett sz´ot´ar ´altal k´odolt vektor nem lehets´eges megold´ asa a prim´al feladatnak, de a c´elf¨ uggv´eny egy¨ utthat´okb´ol 6
kiolvashat´ o a du´ alisnak egy lehets´eges megold´as´ar´ol van sz´o. Ez´ert az u ´j feladat megold´ asa sem a “null´ ar´ol” indul, hanem egy v´elhet˝oen az optimumhoz k¨ ozelebb es˝ o pontb´ ol. A k¨ ovetkez˝ o l´ep´esben az x2 = 23 + 12 x6 − 12 x4 egyenletb˝ol indulunk ki. Az ehhez tartoz´ o Gomory metszet: 12 x6 + 21 x4 ≥ 12 , amivel az u ´j feladat x1 = 4
− x6
x2 =
3 2
+
1 2 x6
−
1 2 x4
x3 =
11 2
−
5 2 x6
+
3 2 x4
x5 =
1 2
+
3 2 x6
+
1 2 x4
x7 =
−1 2
+
1 2 x6
+
1 2 x4
z
19 2
−
3 2 x6
−
1 2 x4
=
Vegy¨ uk ´eszre, hogy az 12 x6 + 21 x4 ≥ 12 -b˝ol kifejezve az x6 ´es x4 v´altoz´okat, ´eppen x1 + x2 ≤ 5, a p´eld´ ankban alkalmazott m´asodik v´ag´as. ´Igy nem t´ ul meglep˝ o, hogy a fenti sz´ ot´ arb´ol egy iter´aci´o elv´egz´ese ut´an megkapjuk az eg´esz ´ert´ek˝ u probl´ema optim´alis megold´as´at: x1 = 4 − x6 x2 = 1 + x6
− x7
x3 = 7 − 4x6 + 3x7 x4 = 1 − x6
+ 2x7
x5 = 0 + 2x6 − x7
z
= 9 − x6
− x7
Ezek ut´ an Gomory algoritmusa egyszer˝ uen le´ırhat´o. Az el˝ ok´esz´ıt˝ o r´eszben ´ırjuk fel az eg´esz ´ert´ek˝ u probl´ema folytonos relax´aci´oj´anak egy lehets´eges sz´ ot´ ar´ at, ´es oldjuk meg a szimplex algoritmussal. Ha a kapott 7
megold´ as eg´esz, akkor az egyben az eg´esz ´ert´ek˝ u feladatnak is optimuma. Ha nem, akkor az al´ abbi iter´aci´ot v´egezz¨ uk el az r-edik l´ep´esben: Vegy¨ uk a sz´ ot´ ar azon X xi = b∗i − a∗ij xj j6∈B
b∗i
sor´ at, ahol 1 ≤ i ≤ m ´es nem eg´esz. Az ehhez tartoz´o Gomory-f´ele metszet X {a∗ij }xj ≥ {b∗i }. j6∈B
Vezess¨ uk be a nem negat´ıv xn+m+r v´altoz´ot a k´et oldal k¨ ul¨onbs´eg´enek jel¨ ol´es´ere, azaz xn+m+r = −{b∗i } +
X
{a∗ij }xj
j6∈B
1. A Gomory algoritmus fenti v´altozata nem felt´etlen¨ ul ´er v´eget. Megmutathat´ o, hogy p´eld´ aul mind a szimplex, mind a du´al szimplex algoritmusnak a lexikografikus v´altozat´at alkalmazzuk, akkor a termin´aci´o garant´ alhat´ o. 2. A Gomory algoritmus v´eges v´altozatai ´altal ig´enyelt iter´aci´ok sz´ama sem korl´ atozhat´ o a feladat m´eret´evel. Ezt Jeroszlov ´es Kortanek l´atta be 1969-ben, majd 1970-ben Rubin olyan, csup´an k´et v´altoz´ot ´es egyetlen egyenl˝ otlens´eget tartalmaz´o feladatokat konstru´alt, melyekn´el b´ armely k ∈ N-re v´ alaszthat´o olyan, amely t¨obb, mint k iter´aci´ot ig´enyel. (A szimplex m´odszer alkalmaz´as´an´al bizonyosak lehett¨ unk, n+m hogy m iter´ aci´ on´ al t¨obb nem sz¨ uks´eges.) 3. Tov´ abbi kellemetlens´eget okoz, hogy a megoldand´o feladat m´erete minden iter´ aci´ o ut´ an n¨ovekszik. Az u ´j v´ag´asok a r´egiek egy r´esz´et sz¨ uks´egtelenn´e tehetik, ´ıgy azok elhagyhat´ok, de nem egyszer˝ u ezek nyomon k¨ ovet´ese sem. 4. V´eg¨ ul felmer¨ ul a numerikus stabilit´as k´erd´ese is, mert a kerek´ıt´esek sor´ an esetleg feln¨ ovekedhetnek a hib´ak. Jelen esetben ez k¨ ul¨on¨osen komplik´ alt, hiszen azt kell eld¨onten¨ unk, hogy egy adott ´ert´ek eg´esze vagy sem. Ezt elker¨ ulend˝o Gomory 1960-ban kidolgozott egy olyan v´ altozatot, amelyben a gener´al´o elem ±1 lehet csak, ´ıgy az egy¨ utthat´ok v´egig eg´eszek az elj´ ar´ as folyam´an.
8
2. el˝oad´as Tot´ alisan unimodul´ aris m´ atrixok Az eg´esz´ert´ek˝ u programoz´as f˝o neh´ezs´ege abban rejlik, hogy a lehets´eges megold´ asokb´ ol ´ all´ o poli´edernek esetleg nem eg´esz koordin´at´aj´ u cs´ ucspontjai vannak. Ha valamik´eppen el˝ore tudn´ank, hogy csak eg´esz cs´ ucspontok vannak, akkor a folytonos relax´aci´o b´armely optim´alis b´azismegold´asa automatikusan az eg´esz´ert´ek˝ u probl´ema optim´alis megold´asa lenne. Mint azt A. J. Hoffman ´es S. B. Kruskal 1956-ban megmutatta az eg´esz´ert´ek˝ u probl´em´ ak egy elm´eleti ´es gyakorlati szempontb´ol egyar´ant l´enyeges oszt´aly´ara teljes¨ ul a felt´etel. Eredm´eny¨ uk k¨ozponti jelent˝os´eg˝ u az u ´n. h´ al´ ozati vagy network probl´em´ ak vizsg´ alat´aban. Az al´ abbi fogalomra lesz sz¨ uks´eg¨ unk: Egy A m´atrix tot´ alisan unimodul´ aris, ha b´ armely n´egyzetes r´eszm´ atrix´anak a determin´ansa 1, −1 vagy 0. (Speci´alisan A elemei csak a ±1 ´es a 0 sz´amok lehetnek.) T´ etel 2 Ha A tot´ alisan unimodul´ aris, b ´es c eg´esz vektorok, akkor a max cx, Ax ≤ b LP b´ azismegold´ asai, (k¨ ozt¨ uk az optim´ alis b´ azismegold´ asai) eg´esz ´ert´ek˝ uek. M´ ask´eppen a P = {x|Ax ≤ b} poli´eder cs´ ucsai eg´esz koordin´ at´ aj´ uak. Bizony´ıt´ as. sz´ ot´ ara:
Ha adott egy B b´azis, a hozz´atartoz´o xB b´azismegold´as xB =
−1 A−1 B b − AB AN xN
−1 z = cB A−1 B b + (cN − cB AB AN )xN
(A m´ odos´ıtott szimplex algoritmus le´ır´as´aval haszn´altuk ezt a formul´at; AB az A m´ atrix B b´ azis ´ altal kijel¨olt oszlopaib´ol ´all. Konvencion´alisan az AB -t B-vel jel¨ olik, a f´elre´ert´es elker¨ ul´ese miatt haszn´aljuk az AB form´at.) −1 Az AB m´ atrix elemeit line´ aris algebr´aban megismert Cramer szab´ aly szerint i,j A az a m´ sz´ amolhatjuk ki. Ha (A−1 ) a m´ a trix i, j-edik eleme, atrix, B B i,j amit AB -b˝ ol a i-edik sor ´es j-edik oszlop elt¨orl´es´evel kapunk, det(AB ) pedig a m´ atrix determin´ ansa, akkor (A−1 B )i,j =
(−1)i+j det(ji AB ) . det(AB )
Mivel A tot´ alisan unimodul´aris, ´es det(AB ) 6= 0, ´ıgy det(AB ) = ±1. Term´eszetesen a det(ij A−1 atrix minden eleme eg´esz. Mivel xB = A−1 B ) m´ B b, 9
egy eg´esz m´ atrix ´es eg´esz vektor szorzata, xB is eg´esz.
2
Megjegyz´ es: Term´eszetesen ha a szimplex m´odszerrel oldjuk meg a probl´e−1 −1 m´ at, a sz´ ot´ ar t¨ obbi eleme (A−1 B AN xN , ill. z = cB AB b+(cN −cB AB AN )xN ) is eg´esz sz´ amokb´ ol ´ all, ´ıgy kerek´ıt´esi hib´ak sem l´epnek fel. Nem nyilv´ anval´ o viszont, hogyan d¨onthetj¨ uk el egy adott m´atrix tot´alisan unimodul´ aris-e vagy sem. A tot´alisan unimodul´aris m´atrixok karakteriz´alhat´ ok, mi t¨ obb, gyors algoritmus is megadhat´o ennek a tulajdons´agnak az eld¨ ont´es´ere. Sajnos az erre vonatkoz´o t´etelek ´es algoritmusok ismertet´ese meghaladja lehet˝ os´egeinket. (Megjegyezz¨ uk azonban, hogy a fent eml´ıtett karakteriz´ aci´ o´ altal´ anos´ıt´ ask´eppen 1981-ben Paul Seymour bebizony´ıtotta a kombinatorika egyik legm´elyebb t´etel´et az u ´n. regul´ aris matroidok dekompoz´ıci´ os t´etel´et.) Mi egy szer´enyebb utat fogunk k¨ovetni. Bevezetj¨ uk a v´eges matematika leghasznosabb fogalm´at, a gr´afokat ´es az ezekkel val´o modellez´es lehet˝ os´egeit vizsg´aljuk. Megmutatjuk majd, hogy egy gr´afhoz tartoz´ o u ´n. incidencia m´ atrix tot´alisan unimodul´aris, aminek messzehat´o k¨ ovetkezm´enyei vannak, melyek k¨oz¨ ul n´eh´anyat t´argyalni fogunk. Gr´ afelm´ eleti alapfogalmak A form´ alis defin´ıci´ ok el˝ ott l´assuk, mik motiv´alj´ak a bevezetend˝o fogalmainkat. A XVIII. sz´ azadban vet˝od¨ott fel az u ´n. K¨ onigsbergi probl´ema, melyet Euler 1736-ban ´ altal´anosan is megoldott. K¨onigsberg v´aros´at a Pregel foly´ o osztotta r´eszekre, melyet az ´abr´an l´athat´o m´odon k¨ot¨ottek ¨ossze hidak. Felmer¨ ult a k´erd´es, lehet-e olyan s´et´at tenni, amelyben minden h´ıdon pontosan egyszer haladunk ´at.
10
3
AA AA AAAA
AA AA 1
CC CC CCC
3 r
1r @
2
4
r2 @ @
@r 4
A probl´ema nyilv´ anval´ oan ekvivalens azzal, hogy a jobboldalon ´all´o objektum lerajzolhat´ o-e egyetlen vonallal. Az ilyen objektumokat, melyek pontokb´ ol ´es az ˝ oket ¨ osszek¨ ot˝ o vonalakb´ol, ´elekb˝ ol ´allnak nevezz¨ uk majd gr´ afnak. K¨ onnyen l´ athat´ o k¨ ul¨ onben, hogy a probl´ema megoldhatatlan, mert h´arom olyan pont van (1, 3 ´es 4), amelyhez p´aratlan sz´am´ u ´el csatlakozik. Ezt ´altal´ aban is igen hasznos elnevezni; egy x ponthoz csatlakoz´o ´elek sz´ama az x pont foksz´ ama. Az ´elekre ir´any´ıt´ast tehet¨ unk, pl. ha olyan u ´th´al´ozatot modellez¨ unk, ahol egyir´ any´ u utak is el˝ofordulnak.
r @
r @
-
@
@ @
@ R @ @
@
r @
@ R @ @ @ R
? @
@ @r
@ @ -
@r
@r
Ezt a felfog´ ast tov´ abbvive (azaz u ´th´al´ozatnak tekintve a gr´afot) felmer¨ ul a pontok k¨ ozti t´ avols´ ag k´erd´ese, illetve egy x ´es y pont k¨oz¨otti legr¨ ovidebb 11
u ´t megkeres´ese. El˝ ofordul, hogy a gr´afok ´eleire sz´amokat ´ırunk. Ezzel jel¨ olhetj¨ uk az adott ´el hossz´ at, esetleg ´atereszt˝o k´epess´eg´et kapacit´ as´ at vagy ´eppen k¨ olts´eg´et.
vr @ @
1
@ ?1
x@ @ R 1@ @
rw
3-
@ @ 1 I @ @ @
?1
@
@r u
-
4
@r y
A fenti ´ abr´ an, ha a sz´ amokat t´avols´agk´ent interpret´aljuk, x ´es y k¨ozt a legr¨ ovidebb u ´t az (x, u, w, y), hossza 3. Ha kapacit´ask´ent, akkor az x-b˝ol y-ba 2 egys´egnyi anyag sz´ all´ıthat´o maxim´alisan. Jelenthetnek a gr´af pontjai egy adott helyzetben alternat´ıv´akat is, ahol az “x jobb, mint y”-t egy y → x ir´ any´ıtott ´ellel jel¨ ol¨ unk. (A racion´alisan megval´osul´o lehet˝os´egek halmaz´at fogjuk majd magnak nevezni). Haszn´alhatjuk a gr´afokat t´erk´epsz´ınez´esekre, rakt´ aroz´ asi probl´em´ ak vizsg´alat´ara (l´asd kromatikus sz´ am), vagy munkafolyamatok sz´etoszt´ as´ ara (l´ asd p´ aros´ıt´ as), ´es ezen fel¨ ul ezer m´as probl´ema modellez´es´ere. L´ assuk h´ at a p´eld´aink ´altal sugallt fogalmak defin´ıci´oj´at! Egy G gr´ af egy G = (V (G), E(G), I(G)) h´armast jelent, ahol V (G)-t a gr´ af pontjainak, E(G)-t pedig a gr´af ´eleinek nevezz¨ uk. I(G) egy f¨ uggv´eny, mely G ´eleihez G pontjainak egy, vagy k´et elem˝ u rendezett vagy rendezetlen halmazait rendeli. Szeml´eletesen a G gr´af egyes pontjait ´elek (ir´ any´ıtott vagy ir´ any´ıtatlan) k¨ otik ¨ ossze. Megenged¨ unk tov´abb´a t¨ obbsz¨ or¨ os ´eleket ´es hurkokat is. Az ut´ obbin term´eszetesen olyan e ∈ I(G) ´elt ´ert¨ unk, amelyhez rendelt halmaznak egy eleme van. Egy hurok´el mentes G gr´af pontj´anak foksz´ am´ an azon ´elek sz´am´at ´ertj¨ uk, amelyekhez I(G) a v-t tartalmaz´o halmazt rendeli, a jele d(v). Tetsz˝oleges G gr´ af eset´eben a hurok´eleket dupl´an sz´am´ıtjuk be a foksz´amba. Megk¨ ul¨onb¨ oztethetj¨ uk a befut´ o ´es a kifut´ o ´eleket, ezek sz´am´at d− (v) ´es d+ (v) jel¨oli. Term´eszetesen d− (v) + d+ (v) = d(v). Az I(G) ´ altal az e ∈ E(G) ´elhez rendelt x ´es y pontot (ha k´etelem˝ u 12
halmazr´ ol van sz´ o) az e ´el ¨ osszek¨ oti, vagy x ´es y illeszkedik az e ´elre. Tov´ abb´ a k hossz´ u s´et´ anak nevezz¨ unk egy (x1 , e1 , . . . , ek , xk+1 ) sorozatot, ha xi ∈ V (G), i = 1, . . . , k + 1, valamint az ei ∈ E(G) ¨osszek¨oti xi -t ´es xi+1 -et, ha i = 1, . . . , k. Az el˝obbi s´eta ir´ any´ıtott, ha az ei -hez xi ´es xi+1 az (xi , xi+1 ) ir´ any´ıt´ assal van hozz´arendelve. Ha a s´et´aban x1 , . . . , xk+1 k¨ ul¨ onb¨ oz˝ oek, akkor u ´tr´ ol, ha x1 , . . . , xk k¨ ul¨onb¨oz˝oek ´es x1 = xk+1 , akkor k¨ orr˝ ol besz´el¨ unk. (Ir´ any´ıtott s´eta eset´en ir´ any´ıtott u ´tr´ ol, illetve k¨ orr˝ ol.) Besz´elhet¨ unk s´ ulyozott gr´afokr´ol. Egy ponts´ ulyoz´ as alatt egy w : V (G) → R, m´ıg ´els´ ulyoz´ as alatt egy w : E(G) → R f¨ uggv´enyt ´ert¨ unk. Egy S halmaz P s´ ulya, w(S) := x∈S w(x). Az ´els´ ulyozott G gr´afban egy (x1 , e1 , . . . , ek , xk+1 ) P u ´t hossza ki=1 w(ei ). (A w jel¨ol´es helyett t¨obbnyire l-et haszn´alunk, ha t´ avols´ agot vagy valamilyen als´o korl´atot, c-t ha k¨olts´eget, ´es u-t ha egy kapacit´ as fels˝ o korl´ atj´ at k´ıv´anjuk jel¨olni.) A G gr´ af pontjainak egy S halmaza f¨ uggetlen, ha S elemeit nem k¨oti ¨ossze ´el. Egy f¨ uggetlen S halmaz mag, ha minden x ∈ V (G)\S est´en van olyan y ∈ S, melyre (y, x) ∈ E(G). Egy G gr´ af ¨ osszef¨ ugg˝ o, ha b´armely k´et pontja k¨oz¨ott van u ´t. Ha b´armely k´et pont k¨ oz¨ ott ir´ any´ıtott u ´t is van, er˝ osen ¨ osszef¨ ugg˝ o. Egy G gr´ af fa ha ¨ osszef¨ ugg˝o, de b´armely e ´el´et elhagyva a marad´ek G\e gr´ af m´ ar nem ¨ osszef¨ ugg˝ o. T´ etel 3 Egy n pont´ u G gr´ afra az al´ abbi tulajdons´ agok ekvivalensek: a, G fa (azaz o ¨sszef¨ ugg˝ o ´es k¨ ormentes). b, G ¨ osszef¨ ugg˝ o, ´es b´ armely ´elt elt´ avol´ıtva G-bol a marad´ek gr´ af m´ ar nem ¨ osszef¨ ugg˝ o. c, G k¨ ormentes, de egy tetsz˝ oleges ´ellel b˝ ov´ıtve az E(G) ´elhalmazt, m´ ar keletkezik k¨ or. d, G k¨ ormentes, ´es n - 1 ´ele van. e, G ¨ osszef¨ ugg˝ o, ´es n - 1 ´ele van. Egy G gr´ af kromatikus sz´ ama, χ(G), azon sz´ınek sz´am´anak minimuma, melyekkel kifesthet˝ o a gr´ af ponthalmaza u ´gy, hogy az egym´assal ¨osszek¨ot¨ott pontok k¨ ul¨ onb¨ oz˝ o sz´ın˝ uek. Egy M ⊆ E(G) halmazt p´ aros´ıt´ asnak nevez¨ unk, ha b´ armely x ∈ V (G) M -nek legfeljebb egy elem´ere illeszkedik. M maxim´ alis, ha nem b˝ ov´ıthet˝ o, s teljes, ha minden x ∈ V (G) pontra van olyan e ∈ M , hogy x illeszkedik az e ´elre.
13
A gr´ afokat nagyon eleg´ansan reprezent´alhatjuk a lerajzol´asukon k´ıv¨ ul k¨ ul¨ onb¨ oz˝ o m´ atrixok seg´ıts´eg´evel is. Sz´amunkra a legfontosabbak az incidencia vagy illeszked´esi m´ atrix ´es az adjacencia vagy szomsz´eds´ agi m´ atrix. Egy ir´ any´ıtott gr´ af incidencia m´atrixa a k¨ovetkez˝ok´eppen konstru´alhat´o: G minden x ∈ V (G) pontj´ahoz tartozik a m´atrix egy sora, ´es minden e ∈ E(G) ´el´ehez egy oszlopa. Az x-hez tartoz´o sor ´es e-hez tartoz´o oszlop keresztez˝ od´es´es´ebe +1 ker¨ ul, ha e az x-be befut´o, −1, ha e az x-b˝ol kifut´o ´el, m´ıg 0, ha e nem illeszkedik x-re. Az egyszer˝ us´eg kedv´e´ert az adjacencia m´ atrixot ir´ any´ıtatlan, t¨ obbsz¨or¨os ´eleket hurok´eleket nem tartalmaz´o gr´afra defini´ aljuk. Ez egy n´egyzetes m´atrix |V (G)| sorral (´es oszloppal), ahol a sorokat ´es oszlopokat egy r¨ ogz´ıtett sorrendben rendelj¨ uk a gr´af pontjaihoz. Egy sor ´es oszlop tal´ alkoz´ as´aban 1 van, ha a megfelel˝o pontok k¨oz¨ott van ´el, 0 k¨ ul¨ onben. P´ eld´ ak: 1 2 3 4
e1 -1 1 0 0
e2 0 -1 1 0
e3 0 0 1 -1
e4 1 0 0 -1
e5
?
4
1r
1 2 3 4 5
1 0 1 0 0 0
2 1 0 1 1 0
3 0 1 0 1 0
4 0 1 1 0 1
e1 -
1r
e5 -1 0 0 1
5 0 0 0 1 0
r1
6e4
r
?e2
r
e3
3
r2 @ @ @ @ @r 3
5
r
r
4
Nem t´erhet¨ unk ki ezen m´atrixok tulajdons´againak r´eszletes ismertet´es´ere, vagy ´ altal´ anos´ıt´ asi lehet˝ os´egeire. Egyetlen, a t´emak¨or¨ unkbe v´ag´ot t´argyalunk; ez viszont sz´ amukra centr´ alis jelent˝os´eg˝ u. 14
T´ etel 4 Egy ir´ any´ıtott gr´ af A illeszked´esi m´ atrixa tot´ alisan unimodul´ aris. Bizony´ıt´ as. Haszn´ aljunk indukci´ot a r´eszdetermin´ansok m´erete szerint. Az A m´ atrix 1 × 1-es r´eszm´ atrixai ±1-ek ´es 0-´ak, ´ıgy k = 1-re igaz a felt´etel. Ha adott egy B (k + 1) × (k + 1)-es r´eszm´atrix, akkor k´et esetre bomlik a bizony´ıt´ as. Ha a B m´ atrixnak van olyan oszlopa, amelynek legfeljebb egy nem nulla eleme van, akkor determin´ans´at ezen oszlop szerinti kifejt´essel kapjuk. Az indukci´ os felt´etel miatt ez 0 vagy ±1. Ha B minden oszlopa pontosan k´et nem nulla elemet tartalmaz (azaz +1-et ´es −1-et), akkor B sorainak ¨ osszege a z´erus vektor, vagyis B sorai line´arisan f¨ ugg˝oek. Ekkor det(B) = 0, ´es ezzel igazoltuk a t´etelt. 2 Megjegyz´ es: Az el˝ oz˝ o t´etel¨ unkkel kombin´alva lesz˝ urhetj¨ uk, hogy minden az illeszked´esi m´ atrix seg´ıts´eg´evel defini´alt eg´esz´ert´ek˝ u programoz´asi feladat egy LP feladatt´ a egyszer˝ us¨odik. Ez megk¨onny´ıti a feladat megold´as´at (tulajdonk´eppen polinom idej˝ uv´e teszi), m´asr´eszt a dualit´asi t´etelt teljes erej´eben kihaszn´ alhat´ ov´ a teszi. Ennek pontos t´argyal´asa messzire vezetne, ´ıgy a k´es˝ obbiekben csup´ an illusztr´alni tudjuk ezt egy-egy p´eld´aval.
15
3. el˝oad´as
1
Legr¨ ovidebb utak
Az egyik leggyakrabban felvet˝od˝o gr´af optimaliz´al´asi probl´ema a legr¨ovidebb utak keres´ese. Tegy¨ uk fel, hogy adott a G ir´any´ıtott gr´af, amelynek ´eleihez s´ ulyokat rendel¨ unk. A hagyom´anynak megfelel˝oen a (v, w) ´el s´ uly´at (hossz´at) l(v, w)-vel jel¨ olj¨ uk, m´ıg egy p u ´t´et, ami nem m´as, mint a p-ben l´ev˝o ´elek s´ uly´ anak ¨ osszege, l(p)-vel. Feltehetj¨ uk azt is, hogy (v, v) ∈ E(G) minden v ∈ V (G)-re, ´es l(v, v) = 0. (a) R¨ ogz´ıts¨ uk most G k´et pontj´at, s-et ´es t-t ´es keress¨ uk meg azt a p utat, mely s-b˝ ol t-be vezet ´es l(p) minim´alis. ´ (b) Altal´ anosabban kereshetj¨ uk a legkisebb s´ uly´ u (legr¨ovidebb) utakat s ´es minden v 6= s pont k¨oz¨ott. Meglep˝ o m´ odon az ¨ osszes olyan ismert algoritmus, ami megoldja a-t, b-t is megoldja egyben. Miel˝ ott r´ at´ern´enk a megold´asra, vizsg´aljuk meg mikor l´etezik ez. Ha az s-b˝ ol el´erhet˝ o egy C negat´ıv s´ uly´ u k¨or (l(C) < 0) ´es C-b˝ol el´erhet˝o t, akkor az a feladatnak nem lehet megold´asa. (C-n tetsz˝olegesen sokszor “k¨ orbemehet¨ unk”, ´ıgy az u ´t s´ ulya tetsz˝olegesen kicsi lehet.) M´asr´eszt, ha nincs ilyen k¨ or, akkor lehets´eges megold´asaink halmaz´ar´ol feltehetj¨ uk, hogy v´eges, ´ıgy - amennyiben az nem u ¨res - van optimum. A (b) feladat megold´ as´ ara Bellman 1956-ban publik´alt iterat´ıv m´odszer´et az u ´n. dinamikus programoz´ ast haszn´aljuk. Az elj´ar´as le´ır´as´ahoz sz¨ uks´eg¨ unk van n´eh´ any jel¨ ol´esre. Egy v ∈ V (G) pontra jelentse d(v) az s-b˝ol v-be vezet˝o legr¨ ovidebb u ´t hossz´ at, m´ıg dk (v) az s-b˝ol v-be a legfeljebb k ´elt tartalmaz´ o legr¨ ovidebb u ´t hossz´ at. Amennyiben a fenti utak nem l´eteznek, d(v) vagy dk (v) ´ert´eke v´egtelen (jelben ∞). Haszn´aljuk m´eg a p : V (G) → V (G) ∪ {∅} f¨ uggv´enyt a megfelel˝ o utak nyilv´antart´as´ara. 1. Kezdetben legyen dˆ0 (s) := 0, p0 (s) := ∅, dˆ0 (v) := ∞, p0 (v) := ∅, ha v 6= s. 2. A k-adik l´ep´esben legyen dˆk (v) := min{dˆk−1 (w) + l(w, v) : (w, v) ∈ E(G)}, pk−1 (v) ´ert´eke pedig v´altozzon arra a w-re, amely az el˝obbi minimumot megval´ os´ıtja, ha dˆk (v) < dˆk−1 (v).
16
T´ etel 5 A fenti algoritmus helyesen sz´ amolja ki a dk f¨ uggv´enyt, azaz dˆk ≡ dk . Ha G-ben nincs negat´ıv s´ uly´ u k¨ or, akkor dn−1 (v) = d(v) minden v ∈ V (G)-re, ahol n = |V (G)|, a gr´ af pontjainak sz´ ama. Tov´ abb´ a ebben az esetben egy legr¨ ovidebb s − v u ´t pontjai ford´ıtott sorrendben v, p(v), p2 (v), i . . . , p (v) = s, ha d(v) < ∞, ahol p = pn−1 . Bizony´ıt´ as. Az els˝ o´ all´ıt´ ast k szerinti indukci´oval l´athatjuk be. A kezd˝o´ert´ekekre, azaz k = 0-ra az ´all´ıt´as nyilv´anval´o. Tegy¨ uk fel, hogy egy adott v-re a legr¨ ovidebb legfeljebb k + 1 ´elb˝ol ´all´o s − v u ´t ´eppen (s, . . . , w, v). Az indukci´ os feltev´esb˝ ol k¨ ovetkezik, hogy l´etezik dˆk (w) = dk (w) hossz´ us´ag´ u, legfeljebb k ´elb˝ ol ´ all´ o s−w u ´t, ´ıgy dk+1 (v) ≥ dˆk (w) + l(w, v) ≥ dˆk+1 (v). Mivel dk+1 (v) ≤ dˆk+1 (v), ad´odik az ´all´ıt´as. Ha G-ben nincsenek negat´ıv k¨or¨ok, akkor b´armely s´eta ´atalak´ıthat´o u ´tt´a u ´gy, hogy a hossza nem n¨ ovekszik. Ez viszont azt jelenti, hogy dn−1 ≡ dn−1+i b´ armely i ∈ N eset´en ´es ´ıgy dn−1 ≡ d. A p szerep´et szint´en a legr¨ovidebb utak ´elsz´ama szerinti indukci´oval l´ athatjuk be. (Ugyanis a (p(v), p2 (v), . . . , pi (v) = s) legr¨ovidebb s − p(v) u ´t lesz a felt´etel szerint. Ekkor a (p(v), v) ´el hozz´av´etel´evel legr¨ovidebb s − v utat kapunk.) 2 P´ elda: Legyen G az ´ abr´ an l´athat´o gr´af; ekkor az algoritmus l´ep´esei az al´abbi t´ abl´ azatban foglalhat´ ok ¨ ossze:
xr @ 1
@ @
r s@ @
rz @ @ -1 @ R @ @
2-
@ 1 6
@ 1 R @ @
R -2@ @ @ yr
@ @ -
5
@r
w
2
@r
u
A t´ abl´ azatot oszloponk´ent t¨oltj¨ uk ki, a d0 (s) = 0, d0 (v) = ∞ minden s-t˝ ol k¨ ul¨ onb¨ oz˝ o v-re, m´ıg p = ∅. Ezek ut´an a dk ´es pk f¨ uggv´enyek ´ert´ekeit rekurzi´ oval kapjuk meg k ≥ 1-re.
17
0 s x y z u w
1
d0 0 ∞ ∞ ∞ ∞ ∞
p ∅ ∅ ∅ ∅ ∅ ∅
d1 0 1 -2 ∞ ∞ ∞
2 p ∅ s s ∅ ∅ ∅
d2 0 -1 -2 3 2 ∞
3 p ∅ y s x x ∅
d3 0 -1 -2 1 0 2
4 p ∅ y s x x z
d4 0 -1 -2 1 0 0
5 p ∅ y s x x z
d5 0 -1 -2 1 0 0
A t´ abl´ azat utols´ o oszlop´ab´ol nemcsak a legr¨ovidebb s − v utak (v ∈ G) hosszai olvashat´ ok ki, hanem meghat´arozhat´ok ezek az utak. Ha csak a legr¨ ovidebb utak ´ altal haszn´alt ´eleket ´abr´azoljuk, ezek a p f¨ uggv´eny ´ert´ekei, akkor az u ´n. legr¨ ovidebb utak f´ aj´ at kapjuk. Ez, ha s-b˝ol el´erhet˝o b´armely pont, egy gy¨ okeres fa, s gy¨ ok´erponttal, ami azt jelenti, hogy deg− (s) = 0 ´es deg− (v) = 1, ha s 6= v ∈ V (G).
xr @ 1
rz @ @ -1 @ R @ @
2-
@ @ @
r s@
1 6
@ R -2@ @
@ 1 R @ @ @ @
@ yr
@r
@r
w
u
Ebb˝ ol k¨ onnyen kiolvashat´ok a legr¨ovidebb s − v utak ´es hosszaik. s−x u ´t: (s, y, x), hossza d(x) = −1 s−y u ´t: (s, y), hossza d(y) = −2 s−u u ´t: (s, y, x, u), hossza d(u) = 0 s−z u ´t: (s, y, x, z), hossza d(z) = 1 s−w u ´t: (s, y, x, z, w) hossza d(w) = 0 Megjegyz´ esek: 1. Az elj´ ar´ as alkalmazhat´o abban az esetben is, ha G-ben van negat´ıv k¨ or. Ekkor egy C negat´ıv k¨or l´etez´es´et a v = pi (v) jelzi valamely 18
p ∅ y s x x z
v ∈ V (G)-re ´es i ∈ N-re, tov´abb´a a p seg´ıts´eg´evel meghat´arozhat´o C. Szint´en van m´ od annak eld¨ont´es´ere, hogy egy adott v pont rajta van-e egy negat´ıv s´et´ an. Vegy¨ unk hozz´a a gr´afhoz egy u ´j q pontot, ´es a (q, v), (v, q) ´eleket nulla s´ ullyal. Ekkor vil´agos, hogy dn (q) < 0 akkor ´es csak akkor, ha v rajta van egy negat´ıv s´et´an. 2. Egy ir´ any´ıtatlan G gr´af ¨osszef¨ ugg˝os´ege is tesztelhet˝o; vegy¨ uk fel az ir´ any´ıtatlan (i, j) hely´ere az ir´any´ıtott (i, j), (j, i) ´eleket 1-1 s´ ullyal. Ha minden s − v legr¨ ovidebb u ´t hossza v´eges, akkor G ¨osszef¨ ugg˝o, ha d(v) = ∞, akkor s ´es v k¨ ul¨onb¨oz˝o komponensekben vannak. 3. Az algoritmus m˝ uk¨ od´ese azon m´ ulott, minden v ∈ V (G)-re van olyan w ∈ V (G), hogy dk (v) = dk−1 (w) + l(w, v). Ez durv´an azt jelenti, hogy az optim´ alis strukt´ ur´ank k¨oz¨ott kapcsolat van, a “nagyobb” fel´ep´ıthet˝ o a “kisebb˝ ol”. Ilyen jelleg˝ u kapcsolat gyakran kihaszn´alhat´o egy hat´ekony algoritmus fel´ep´ıt´es´ere a fentihez hasonl´o m´odon. Ezt a m´ odszert dinamikus programoz´ asnak nevezz¨ uk.
Alkalmaz´ asok
A legr¨ ovidebb utakkal meglep˝oen sok probl´ema modellezhet˝o, illetve fontos r´esze m´ as algoritmusoknak. Az ut´obbit k´es˝obb l´atni fogjuk. Itt h´ arom, nem k´ezenfekv˝ o alkalmaz´asra t´er¨ unk ki. 1. A kritikus u ´ t m´ odszere Tegy¨ uk fel, hogy adott egy projekt, amely t¨obb, egym´ast´ol nem f¨ uggetlen r´esztev´ekenys´egb˝ ol ´ all. Tudjuk a r´esztev´ekenys´egek v´egrehajt´as´ahoz sz¨ uks´eges id˝ ot ´es azt, hogy egy adott tev´ekenys´eg elkezd´es´enek mely m´as tev´ekenys´egek befejezetts´ege felt´etele. (Pl. egy ´ep´ıtkez´esn´el csak az alapoz´as ut´an lehet falazni.) A c´elunk annak meghat´aroz´asa, hogy minim´alisan mennyi id˝o alatt teljes´ıthet˝ o a projekt, ha nincs egy´eb korl´atoz´as. A javasolt modellt ´es a megold´ ast egy p´eld´ an illusztr´aljuk. P´ elda: Jel¨ olj¨ uk a r´eszfeladatokat f1 , . . . , f6 -tal, az elv´egz´eshez sz¨ uks´eges id˝ oket t1 , . . . , t6 -tal ´es ha az fj elkezd´es´enek az fi befejezetts´ege felt´etele, azt fi < fj -vel. Legyen t1 = 2, t2 = 1, t3 = 4, t4 = 1, t5 = 2, t6 = 2 ´es a felt´etelek: f1 < f2 , f1 < f3 , f2 < f4 , f2 < f5 , f3 < f5 , f4 < f5 , f5 < f6 . ´ azoljuk ezt egy ir´ Abr´ any´ıtott gr´af seg´ıts´eg´evel, ahol a fi pontot rendelj¨ uk az fi feladathoz, (fi , fj ) ´el a gr´afban, ha fi < fj , ´es ekkor l(fi , fj ) = ti . 19
Vegy¨ unk fel egy fikt´ıv feladatot, f7 -et, ´es legyen (fi , f7 ) ´el a gr´afban, ha fi nem felt´etele m´ as feladatnak.
f2r @ 2
r f4
1-
r f7 2
@ @
6 @
r f1 @
@ 1 R @ @
@ R 2@ @ @r f3
@ @ -
4
r
?1
f6
2
@r
f5
Vegy¨ unk egy ir´ any´ıtott utat, az (f1 , f2 , f5 , f6 , f7 )-et a gr´afb´ol. Ennek hossza t1 + t2 + t5 + t6 ´es mivel az ir´any´ıt´as szerint az f1 , f2 , f5 ´es f6 tev´ekenys´egek csak ebben a sorrendben ´es egym´as ut´an hajthat´ok v´egre, az u ´t hossza als´ o korl´ atja a sz¨ uks´eges minim´alis id˝onek. Mi t¨obb ez a minim´alis id˝ o egybeesik egy ilyen t´ıpus´ u als´o korl´attal, mert a modell¨ unkben fell´ep˝o gr´ afok k¨ ormentesek. Egy G k¨ormentes ir´any´ıtott, s´ ulyozott gr´af leghosszabb u ´tj´ at nevezz¨ uk kritikus u ´tnak. T´ etel 6 Egy projekt v´egrehajt´ as´ ahoz sz¨ uks´eges minim´ alis id˝ o egyenl˝ o a kritikus u ´t hossz´ aval. Bizony´ıt´ as. Teljes indukci´oval a kritikus u ´t ´elsz´ama szerint.
2
A p´eld´ ankban k¨ onnyen l´athat´o: a (f1 , f3 , f5 , f6 , f7 ) kritikus u ´t, melynek hossza t1 + t3 + t5 + t6 = 10. ´Igy a t´etelb˝ol k¨ovetkez˝oen a projekt id˝oig´enye pontosan t´ız egys´eg. Egy tetsz˝ oleges ir´ any´ıtott gr´afban a leghosszabb u ´t megtal´al´asa rendk´ıv¨ ul neh´ez feladat. Eset¨ unkben a helyzet j´oval kedvez˝obb: vegy¨ uk az ´elekhez rendelt s´ ulyok −1-szeres´et, ´es keress¨ uk meg a legr¨ ovidebb utat. Mivel a gr´afunk k¨ ormentes, ´ıgy nincs negat´ıv k¨or, azaz haszn´alhat´o Bellman algoritmusa ´es a kapott legr¨ ovidebb u ´t a leghosszabb lesz az eredeti gr´afban. Megjegyz´ es: A m´ odszer alkalmaz´as´anak egyik legszebb p´eld´aja az Apoll´o program volt. Ebben ezern´el t¨obb alv´allalkoz´o ´altal v´egzett, igen nagy sz´ am´ u r´eszfeladatot siker¨ ult ¨osszehangolni m´ıgnem 1969-ben az ember a 20
Holdra l´ephetett. 2. Nem line´ aris c´ elf¨ uggv´ eny Tegy¨ uk fel, hogy adott egy ir´any´ıtott gr´af, amelynek az ´elein egym´ast´ol f¨ uggetlen¨ ul, ismert val´ osz´ın˝ us´egekkel lehet ´athaladni. Kijel¨olve egy s ´es t pontot, szeretn´enk meghat´ arozni azt az utat, amelyen legnagyobb val´osz´ın˝ us´eggel eljutunk s-b˝ ol t-be. P´ elda:
xr
rv
0,2
0,8
s@ @
0,8
0,7
0,7
@ 0,5 @
@r y
r
0,4
t
Ha r¨ ogz´ıt¨ unk n´eh´ any ´elt, akkor annak val´osz´ın˝ us´ege, hogy mindegyik j´ arhat´ o, a f¨ uggetlens´eg miatt a hozz´ajuk rendelt val´osz´ın˝ us´egek szorzata. Jelen esetben a legnagyobb val´osz´ın˝ us´eggel nyitva lev˝o s − t u ´t az (s, x, y, v, t), ´ a j´ ahat´ os´ ag val´ osz´ın˝ us´ege 0, 8 × 0, 8 × 0, 7 × 0, 7 = 0, 3156. Altal´ aban 1 a k¨ ovetkez˝ ot tehetj¨ uk: cser´elj¨ uk ki minden e ´elre az ´elhez tartoz´o p(e) val´ osz´ın˝ us´eget − ln p(e)-re, ´es keress¨ uk a legr¨ovidebb s − t utat ezen s´ ulyoz´as mellett. Legyenek R ´es Q k´et k¨ ul¨onb¨oz˝o s − t u ´t ´elhalmazai; ekkor az utak j´ arhat´ os´ ag´ anak val´ osz´ın˝ us´egei rendre Y
Y
p(e) ´es
p(e),
e∈Q
e∈R
m´ıg a transzform´ aci´ o mellett a hosszuk −
X
ln p(e) ´es −
e∈R
X
ln p(e).
e∈Q
1
Val´ oban, ez az o ¨tlet nagyon a ´ltal´ anos, a szorzatok kisz´ am´ıt´ as´ anak o ¨sszead´ asra val´ o visszavezet´ese a logaritmus f¨ uggv´eny bevezet´es´enek egyik f˝ o motiv´ aci´ oja.
21
Ha −
X
ln p(e) < −
e∈R
X
ln p(e),
e∈Q
akkor X
ln p(e) >
e∈R
X
ln p(e).
e∈Q
Ebb˝ ol ln(
Y
p(e)) > ln(
e∈R
Y
p(e)),
e∈Q
´es a logaritmus monotonit´ asa miatt kapjuk a Y
p(e) >
e∈R
Y
p(e)
e∈Q
egyenl˝ otlens´eget, ami bizony´ıtja ´all´ıt´asunkat.
3. F´ azisterek A f´ azisterek alapgondolata az, hogy a vizsg´alni k´ıv´ant rendszer teljes ´allapot´ at egyetlen pont seg´ıts´eg´evel ´ırjuk le.2 Itt egy k¨ozismert, de m´egsem trivi´ alis p´eld´ an illusztr´ aljuk a f´azistereken alapul´o modellez´est. Az u ´n. aut´ overseny j´ at´ekot egy kock´as lapon j´atszhatjuk, ahol az aut´o egy l´ep´es´et egy ny´ıl reprezent´alja. (A ny´ıl az aut´o egys´egnyi id˝o alatt megtett u ´tja. Mivel a gyorsul´ as nem tetsz˝olegesen nagy, ez´ert l´ep´esenk´ent csak α1 e1 + α2 e2 -vel v´ altoztathat´ o, ahol e1 , e2 a s´ık mer˝oleges egys´egvektorai α1 , α2 ∈ {−1, 0, 1}.) Adott tov´ abb´ a egy p´alya, amit az aut´o nem hagyhat el, egy rajt´es c´elvonal, ahonnan indul, illetve ahova ´erkeznie kell a lehet˝o legkevesebb l´ep´es alatt. 2
Ez rendk´ıv¨ ul hasznosnak bizonyult a fizik´ aban, ahol p´eld´ aul egy n t¨ omegpontb´ ol ´ all´ o rendszer mozg´ as´ at 6n koordin´ ata (pontonk´ent 3 t´er ´es 3 sebess´eg) ´ırja le. Ez felfoghat´ o az R6n egyetlen pontjak´ent, m´ıg a rendszer id˝ obeli v´ altoz´ asa egy t´erg¨ orbek´ent. T¨ obbnyire ez a hozz´ aa ´ll´ as seg´ıt a Markov l´ ancokkal val´ o modellez´esben is: a l´ anc egy-egy a ´llapota a rendszer teljes le´ır´ as´ at k´ odolja.
22
i
i
i
i ` ` `` i `i
i i
y
A jobboldali ´ abr´ an l´ athat´o, hogyan lehet meghat´arozni a k¨ovetkez˝o lehets´eges l´ep´est: megism´etelj¨ uk az el˝oz˝o l´ep´es vektor´at (a szaggatott vektor) ´es a v´egponthoz tartoz´ o r´ acspontba, valamint ennek szomsz´edaiba l´ephet¨ unk. A keletkez˝ ou ´t nem gr´ af´ ut, hiszen ak´arhov´a nem l´ephet¨ unk; ez a sebess´egt˝ol is f¨ ugg. K´esz´ıthet¨ unk azonban egy f´ azist´er gr´ afot, amelynek pontjai mind az aut´ o hely´et, mind a sebess´eg´et k´odolj´ak ´es a pontok k¨oz¨ott akkor van ´el, ha az ´ atmenet egyik ´ allapotb´ol a m´asikba egy l´ep´es alatt megt¨ort´enhet. Egy (a, b) s´ıkbeli pontp´ arnak megfelelt egy gr´afpont, ahol a pontbeli ´allapot azt jelzi, hogy az aut´ o a b pontban van ´es oda az a-b´ol l´epett. Ekkor az ´ allapotgr´ afnak olyan (b, c) pontjaira lehet ´atl´epni (van ´el), amelyekre a bc vektor az ab vektort´ ol b´armely koordin´at´aj´aban legfeljebb eggyel t´er el. S´ ulyozzunk minden ´elt eggyel, akkor az ´allapotgr´af legr¨ovidebb u ´tja a rajt ´es c´el k¨ oz¨ ott a minim´ alis l´ep´essz´am´ uu ´tvonalnak felel majd meg. Megjegyz´ es: 1. Ha a p´ alya n pontb´ ol ´all, az ´allapotgr´af n2 pontb´ol fog. A p´eld´ankban n ≤ 100, ´ıgy az ´ allapotgr´afnak t´ızezern´el kevesebb pontja van. 2. Az elj´ ar´ assal modellezhet˝ok egy´eb felt´etelek: olajfolt, amin nem lehet lass´ıtani, homok´ agy, ami lass´ıt stb.
23
4. el˝oad´as H´ al´ ozati probl´ em´ ak Az u ´n. h´ al´ ozati vagy network probl´em´ak rendk´ıv¨ ul elterjedtek az oper´aci´ okutat´ asban. Ennek h´ arom f˝o oka van: (i) m´ odfelett alkalmasak gyakorlati probl´em´ak modellez´es´ere (ii) hat´ekony algoritmusok dolgozhat´ok ki megold´asukra (iii) matematikai szempontb´ol nagyon eleg´ans elm´elet¨ uk van. Ennek megfelel˝ oen a 40-es ´evekt˝ol kezdve sz´amos modellel foglalkoztak a t´emak¨ or kutat´ oi, amib˝ ol itt csak n´eh´anyat ´es ´erint˝olegesen t´argyalhatunk. Az egyik legfontosabb a transshipment probl´ema.3 Adott egy G ir´any´ıtott gr´ af, melynek ´eleihez val´ os sz´amokat (k¨ olts´egeket) rendel¨ unk. Sz´amokat rendel¨ unk a gr´ af pontjaihoz is. Ha ez a sz´am pozit´ıv, akkor a pontot nyel˝ onek, ha negat´ıv forr´ asnak, ha nulla bels˝ o pontnak nevezz¨ uk. Feltehetj¨ uk, hogy a pontokhoz rendelt sz´ amok ¨ osszege nulla. (Ha nem, egy u ´j pont felv´etel´evel ilyen form´ ara hozhatjuk G-t.) Tegy¨ uk fel, hogy valamilyen ´arut kell sz´all´ıtanunk a forr´asokb´ol a nyel˝okbe a gr´ af ´elei ment´en u ´gy, hogy b´armely forr´asban a k´ın´ alat, illetve nyel˝oben a kereslet a hozz´ arendelt a hozz´arendelt sz´am abszol´ ult ´ert´eke (a bels˝o pontokban nulla). Egy ´el ment´en a sz´all´ıt´asi k¨olts´ege az ´elhez rendelt sz´am ´es a sz´ all´ıtott ´ aru mennyis´eg´enek szorzata, m´ıg az ¨osszk¨olts´eg a sz´all´ıt´asi k¨ olts´egek ¨ osszege. P´ elda: A pontok mell´e ´ırt sz´am a pont neve, z´ar´ojelben a kereslet/k´ın´alat. A k´et megold´ asban csak a sz´all´ıt´asba bekapcsol´od´o ´eleket ´abr´azoltuk. 1(0) r
5(8) r r P qP 4(10) B@PP PPr B@ NB @ @ I B 6 B 3(6) @ 6 6 r @ r 2(0) Br @ 6 1 I @ r r @r -
6(-9)
7(-15)
3
r r
r r -1 P PP qP 2 2 PPr
10
8 3 6 9 6 6 6 6 6 4 r r r @ @ 2 10 10 I @ I @ r @r @r 4
3
Ezt sz´ all´ıt´ asi probl´em´ anak is szokt´ ak magyar´ıtani. Mi itt ink´ abb sz´ all´ıtm´ anyoz´ asi probl´emak´ent emlegetj¨ uk, hogy ne keveredjen o ¨ssze egy speci´ alis esettel, a Hitchcock-f´ele sz´ all´ıt´ asi feladattal.
24
A transshipment probl´ema fel´ırhat´o LP feladatk´ent, ahol A a G gr´af incidencia m´ atrixa, az x vektor xij komponense az (i, j) ´elen sz´all´ıtott ´aru mennyis´ege, cij az egys´egnyi sz´all´ıt´as k¨olts´ege, a b vektor pedig az egyes pontokban jelentkez˝ o kereslet/k´ın´alat. min
P
cij xij = cx
(i,j)∈E(G)
(∗)
Ax = b x≥0
A p´eld´ ankban az A m´ atrix a k¨ovetkez˝o: 1 2 3 4 5 6 7
1,3 -1 0 1 0 0 0 0
1,4 -1 0 0 1 0 0 0
1,5 -1 0 0 0 1 0 0
2,1 1 -1 0 0 0 0 0
2,3 0 -1 1 0 0 0 0
2,4 0 -1 0 1 0 0 0
2,5 0 -1 0 0 1 0 0
5,4 0 0 0 1 -1 0 0
6,1 1 0 0 0 0 -1 0
6,2 0 1 0 0 0 -1 0
6,3 0 0 1 0 0 -1 0
6,7 0 0 0 0 0 -1 1
7,2 0 1 0 0 0 0 -1
7,5 0 0 0 1 1 0 1
xT = [x13 , x14 , x15 , x21 , x23 , x24 , x25 , x54 , x61 , x62 , x63 , x67 , x72 , x75 ] ´es bT = [0, 0, 6, 10, 8, −9, −15]. Vegy¨ uk ´eszre, hogy a (∗) probl´ema m´atrix´ab´ol t¨or¨olhetj¨ uk az utols´o (de tulajdonk´eppen b´ armely) sort ´es a b vektor utols´o koordin´at´aj´at a line´aris f¨ ugg˝ os´eg miatt. A transshipment probl´ema megold´as´ara k¨ ul¨onb¨oz˝o lehet˝os´egek ad´odnak. Ha a G gr´ af, ir´ any´ıt´ ast´ ol eltekintve ¨osszef¨ ugg˝o, akkor a (∗) LP egy tetsz˝oleges b´ azis megold´ as´ anak a b´ azisban l´ev˝o v´altoz´okhoz tartoz´o ´elei egy f´at alkotnak. Ezeknek a f´ aknak a megfelel˝o transzform´aci´oival fogalmazhat´o meg az u ´n. network szimplex algoritmus. Ez a j´ol ismert szimplex algoritmus egy, a gyakorlatban rendk´ıv¨ ul hat´ekony v´altozata. M´as elj´ar´asok enn´el is direktebb m´ odon haszn´ alj´ ak ki a feladat speci´alis szerkezet´et, ´es, legal´abbis elm´eleti vonatkoz´ asban, fel¨ ulm´ ulj´ak a network szimplex algoritmust. Egy egyszer˝ ubb feladat, a maxim´ alis folyam probl´ema vizsg´alat´aban betekint´est adunk ezekbe a m´ odszerekbe. Itt megel´egsz¨ unk az u ´n. integralit´ as t´etel bizony´ıt´ as´ aval. T´ etel 7 (integralit´ as) Tegy¨ uk fel, hogy a fenti transshipment probl´ema b vektor´ anak minden koordin´ at´ aja eg´esz sz´ am. Ha a feladatnak van lehets´eges megold´ asa, akkor van eg´esz megold´ asa is. Ha van optim´ alis megold´ asa, akkor van optim´ alis eg´esz megold´ asa is. 25
Bizony´ıt´ as. A lehets´eges megold´as l´etez´es´eb˝ol k¨ovetkezik (az LP alapt´etel´eb˝ ol), hogy van lehets´eges b´azis megold´as. Kor´abbi t´eteleink szerint az A m´ atrix tot´ alisan unimodul´aris, ´es ´ıgy a probl´ema b´armelyik lehets´eges b´ azis megold´ asa eg´esz. Ism´et az LP alapt´etel´et haszn´alva, ha van optim´alis megold´ as, akkor van optim´alis b´azismegold´as, amely az el˝oz˝o pont miatt sz¨ uks´egk´eppen eg´esz. 2 A transshipment probl´ema formalizmusa ´es az integralit´as t´etel az oper´ aci´ okutat´ as ´es a kombinatorika szerencs´es kever´eke. Val´oj´aban t¨om´erdek kor´ abbi probl´ema/modell k¨ oz¨os ´altal´anos´ıt´asa. Mi a ford´ıtott utat k¨ovetj¨ uk: az ´ altal´ anos probl´ema speci´ alis eseteik´ent mutatunk be n´eh´anyat ezek k¨oz¨ ul. El˝ osz¨ or azonban l´ assunk egy nem trivi´alis alkalmaz´ast. Az ´ etkeztet˝ o (caterer) probl´ ema4 Adott egy ´etkeztet˝ o, akinek n napon ´at tiszta szalv´et´ara van sz¨ uks´ege, a j-edik napon egy el˝ ore ismert dj darabra. Ezt r´eszint u ´j szalv´et´ak v´as´arl´as´aval (a cent darabja), r´eszint a haszn´altak mosat´as´aval fedezheti. Az ut´obbiban v´ alaszthat a gyors (q nap alatt, darabonk´ent b cent´ert) ´es a lass´ u (p nap alatt, c cent´ert) aj´ anlott szolg´altat´asok k¨oz¨ott. Term´eszetesen p > q ´es a > b > c, a minim´ alis k¨ olts´eg pedig a c´el. P´ elda: Legyen egy ´etkezet˝ o feladatban n=10, d1 =50, d2 =60, d3 =80, d4 =70, d5 =50, d6 =60, d7 =90, d8 =80, d9 =50, d10 =100; m´ıg p=4, q=2, a=200, b=75, c=25. Az al´ abbi t´ abl´ azatban ¨osszefoglalunk egy lehets´eges ´es egy optim´alis (a z´ ar´ ojelben l´ev˝ o sz´ amok) strat´egi´at. Az ut´obbi egy a feladathoz rendelt transshipment probl´ema optim´alis b´azis megold´asa. A feladat gr´afj´aban a hozz´ atartoz´ o f´ at szint´en ´ abr´azoljuk majd. 4
A modell eredetileg egy u ¨temez´esi probl´ema, amellyel a l´egier˝ o rep¨ ul˝ og´ep motorjainak karbantart´ as´ at tervezt´ek. K´es˝ obb a megalkot´ oi (Jacobs, Gaddum, Hoffman, Sokolowsky ´es Prager) a demilitariz´ alt caterer (´etkeztet´esi) probl´ema n´even publik´ alt´ ak.
26
Nap 1 2 3 4 5 6 7 8 9 10
Mosott 0 (0) 0 (0) 50 (0) 60 (0) 50 (50) 60 (60) 90 (90) 60 (80) 50 (50) 100 (100)
V´ as´ arolt 50 (50) 60 (60) 30 (80) 10 (70) 0 (0) 0 (0) 0 (0) 20 (0) 0 (0) 0 (0)
Gyors mos´as 50 (0) 60 (0) 50 (0) 60 (0) 60 (10) 60 (10) 50 (50) 100 (10) 0 (0) 0 (0)
Lass´ u mos´as 0 (50) 0 (60) 30 (80) 0 (70) 0 (0) 0 (90) 0 (0) 0 (0) 0 (0) 0 (0)
T´arol´as 0 (0) 0 (0) 0 (0) 10 (0) 0 (40) 0 (0) 40 (40) 20 (110) 70 (160) 170 (260)
A transshipment modell ´es az optim´alis megold´as f´aja a k¨ovetkez˝o: b
b
b
b
-50 b
-b
b
-b
-60 b?
-b
b?
-b
-80 b?
~ -b
b?
~ -b
-70 b?
~ -b
b?
~ -b
-50 b?
~ -b
b?
~ -b
-60 b?
~ -b
b?
~ -b
-90 b?
~ -b
b?
~ -b
-80 b?
~ -b
b?
~ -b
-50 b?
~ -b
b?
~ -b
b
-100 b? -100 b?
b
b? -? b
b?
27
-? b
Az baloldali ´ abra ´ertelmez´ese: A baloldali pontokban, mint t´arol´okban jelenik meg a naponk´ent elhaszn´ alt szalv´eta. Ezekb˝ ol a forr´asokb´ol tov´abb k¨ uldhet˝ok gyors mos´assal a k´et nappal k´es˝ obbi felhaszn´al´asra (v´ızszintes ´elek, b k¨olts´eg), lass´ u mos´assal (ferde ´elek, c k¨ olts´eg), vagy t´arolhat´ok a k¨ovetkez˝o napig (f¨ ugg˝oleges ´elek, 0 k¨ olts´eg). A j-dik napon ig´enyelt dj darab szalv´eta beszerezhet˝o a j − q t´ arol´ ob´ ol gyors, a j − p-b˝ ol lass´ u mosat´assal, vagy a boltb´ol a k¨olts´eg˝ u ´elen. C´elszer˝ u feltenni, hogy a boltban elegend˝o szalv´eta van, ´es ak´ar az eg´esz sz¨ uks´eglet fedezhet˝ o v´as´arl´as u ´tj´an. Az utols´o napon a t´arol´oban l´ev˝o szalv´et´ akat egy (k´epzeletbeli) gy˝ ujt˝obe ir´any´ıtjuk z´er´o k¨olts´eg ´ar´an csak´ ugy, mint az n-edik nap ut´ an a boltban maradtakat. (Ez ut´obbi szint´en z´er´o k¨ olts´eggel tehet˝ o meg.) Ezek seg´ıts´eg´evel az ´etkeztet´esi probl´em´at ´at´ırtuk egy transshipment probl´em´ ara. A jobboldali ´ abra ´ertelmez´ese: Az optim´ alis b´ azis megold´as b´azis´aban l´ev˝o v´altoz´oknak megfelel˝o ´eleket ´abr´ azoltuk. Az ´elekre ´ırt sz´amok a v´altoz´ok ´ert´ekei. Vegy¨ uk ´eszre, hogy n´emelyik b´ azisv´ altoz´ o nulla ´ert´eket kap, azaz a megold´as degener´alt. Ez a h´ al´ ozati probl´em´ ak megold´ as´an´al igen gyakori jelens´eg. Az integralit´as t´etel garant´ alja, hogy van eg´esz optim´alis megold´as, ´es ´ıgy a kapott u ¨temez´esi terv kerek´ıt´esek n´elk¨ ul alkalmazhat´o. A legr¨ ovidebb u ´ t probl´ ema A legr¨ ovidebb utak keres´es´ere m´ar adtunk kiel´eg´ıt˝o algoritmust. Most az u ´j modell¨ unk erej´et illusztr´ aljuk. Tegy¨ uk fel, hogy egy ir´any´ıtott, s´ ulyozott G gr´ afban egy legr¨ ovidebb s − t utat keres¨ unk. Rendelj¨ unk s-hez −1, m´ıg t-hez 1 keresletet. Tekints¨ uk a s´ ulyokat k¨olts´egeknek ´es vegy¨ uk az ´ıgy ad´od´o transshipment probl´ema egy eg´esz optimum´at, ha az l´etezik. Ha G-ben nincs negat´ıv k¨ or, k¨ onnyen l´ athat´o, hogy az ´elekhez rendelt v´altoz´ok csak 0 ´es 1 ´ert´eket vesznek majd fel, ´es az 1 ´ert´ekhez tartoz´o ´eleken eljuthatunk s-b˝ol t-be. (Parci´ alisan a megford´ıt´as is igaz: a legr¨ovidebb utak keres´ese fontos r´eszfeladat a transshipment probl´ema megold´as´ara adott n´emely algoritmusban.) Sz´ all´ıt´ asi (transportation) probl´ ema A probl´em´ at 1941-ben F. I. Hitchcock tanulm´anyozta, ´ıgy n´eha Hitchcockf´ele sz´ all´ıt´ asi feladatk´ent is emlegetik. a probl´em´at:
28
min
m P n P
cij xij
i=1 j=1 n P
xij
= ri , (i = 1, 2, . . . , m)
xij
= sj , (j = 1, 2, . . . , n)
j=1 m P i=1
xij
≥
0
K¨ onnyen l´ athat´ o, hogy ez egy kett˝o kromatikus sz´am´ u gr´afban (vagy m´ as sz´ oval p´ aros gr´ afon) defini´alt transshipment probl´ema. Defini´aljuk G u ´gy, hogy V (G) = U ∩ V , ahol U = {u1 , u2 , . . . , um } a forr´asok, V = {v1 , v2 , . . . , vm } a nyel˝ ok halmaza, ´es E(G) = {ui vj : ui ∈ U, vj ∈ V }. Legyen tov´ abb´ a a k´ın´ alat ri az ui pontn´al (i = 1, . . . , m), a kereslet pedig sj a vj pontn´ al (j = 1, . . . , n). A sz´all´ıt´asi feladat ezek ut´an megoldhat´o az integralit´ as t´etel alapj´ an. A sz´all´ıt´asi feladatnak a nyilv´anval´oan l´atsz´o felhaszn´ alhat´ os´ agon k´ıv¨ ul sok m´ely alkalmaz´asa van, melyre itt nem t´erhet¨ unk ki. Hozz´ arendel´ esi (assignment) probl´ ema Egy p´eld´ an kereszt¨ ul vezetj¨ uk be a feladatot. Tegy¨ uk fel, hogy van 5 ember, 5 k¨ ul¨ onb¨ oz˝ o feladat, ´es egy sz´ammal le´ırhatjuk az i-edik ember teljes´ıtm´eny´et a j-edik feladaton (0 ≤ i, j ≤ 5). Adjunk minden embernek pontosan egy feladatot u ´gy, hogy a teljes´ıtm´enyek ¨osszege a lehet˝o legnagyobb legyen. A teljes´ıtm´enyek le´ırhat´ok egy m´atrix-szal: 1 2 3 4 5 1 7 5 4 4 5 2 7 9 7 9 4 3 4 6 5 8 5 4 5 4 5 7 4 5 4 5 5 8 9 A feladatra eg´esz ´ert´ek˝ u programoz´asi modellt c´elszer˝ u fel´all´ıtani. Legyen xij = 1, ha az i-edik ember a j-edik feladatot kapja, xij = 0 k¨ ul¨onben. Ezzel P a felt´etelek 5j=1 xij = 1 (i = 1, . . . , 5) (minden ember pontosan egy feladaP tot kap) ´es 5i=1 xij = 1 (j=1, . . ., 5) (minden feladatot pontosan egy ember P P v´egez el), a c´elf¨ uggv´eny pedig a m´atrix egy¨ utthat´okb´ol ´all: i j cij xij .
29
´ Altal´ aban a hozz´ arendel´esi probl´ema: max
n P n P
cij xij
i=1 j=1 n P
(∗)
xij
=
1 (i = 1, . . . , n)
xij
=
1 (j = 1, . . . , n)
xij
∈ {0, 1} (1 ≤ i, j ≤ n).
j=1 n P i=1
Vegy¨ uk ´eszre, hogy a (∗) probl´em´anak mindig van pontosan n! lehets´eges, ´es ebb˝ ol k¨ ovetkez˝ oen legal´ abb egy optim´alis megold´asa is, ´es az integralit´asi t´etel miatt az al´ abbi sz´ all´ıt´ asi feladat optim´alis b´azismegold´asa a (∗)-nak is optim´ alis megold´ asa: min
n P n P
(−cij )xij
i=1 j=1 n P
xij
= 1 (i = 1, . . . , n)
xij
= 1 (j = 1, . . . , n)
xij
≤ 0 (1 ≤ i, j ≤ n).
j=1 n P i=1
Megjegyezz¨ uk, hogy a (∗) feladatnak 1950-ben P. R. Halmos ´es H. Vaughon egy meglehet˝ osen abszurd “alkalmaz´as´at” publik´alta. Ebben n h´azasulni k´ıv´ an´ o f´erfi, illetve n˝ o egym´ashoz rendel´es´et ´ırj´ak le olyan m´odon, hogy a cij sz´ am a j-edik n˝ o ´ altal az i-edik f´erfinak adott pontsz´am (n a legjobb P P esetben, 1 a legrosszabban), m´ıg az “¨osszboldogs´ag” ar´anyos i j cij -vel. Ez sz´ amunkra csak annyiban ´erdekes, hogy a k´es˝obbiekben egy valamivel re´ alisabb felt´etel mellett megvizsg´aljuk ´es megold´ast adunk az u ´n. stabil h´ azas´ıt´ asi probl´em´ ara. A probl´ema ´es a r´a vonatkoz´o integralit´as t´etel j´ ol haszn´ alhat´ o a p´ aros gr´ afok p´ aros´ıt´ asi probl´em´ ainak tanulm´anyoz´as´aban. Egy G gr´ af p´ aros, ha V (G) = A ∪ B, ahol A ∩ B = ∅, ´es minden ´el A ´es B k¨ oz¨ ott h´ uz´ odik (jelben χ(G) ≤ 2). K¨onnyen bel´athat´o, hogy egy G p´aros 30
gr´ af maxim´ alis M p´ aros´ıt´ asa az al´abbi LP megold´as´aval megkaphat´o: max
P P
xij
j∈B i∈A
P
xij
≤ 1 (i ∈ A)
xij
≤ 1 (j ∈ B)
xij
≤ 0 (i ∈ A, j ∈ B),
j:(i,j)∈E(G)
P i:(i,j)∈E(G)
ahol M azon (i, j) ´elekb˝ ol a´ll, melyekre x∗ij = 1 az optim´alis megold´asban. Hasonl´ o k¨ onnyeds´eggel kaphatjuk meg K¨onig D´enes h´ıres t´etel´et: T´ etel 8 tegy¨ uk fel, hogy G olyan p´ aros gr´ af, melyre |A| = |B| = n ´es minden v ∈ V (G) pont foksz´ ama d(v) = k ≥ 1. Ekkor G-ben van teljes p´ aros´ıt´ as. Bizony´ıt´ as. K´esz´ıts¨ unk egy transshipment probl´em´at a G gr´afhoz u ´gy, hogy A pontjaihoz -1-et, B pontjaihoz 1-et rendel¨ unk ´es az ´eleket A-b´ol B-be ir´ any´ıtjuk. (Az ´elek k¨ olts´eg´evel nem t¨or˝od¨ unk.) A keletkez˝o probl´em´anak van lehets´eges x megold´ asa: egyszer˝ uen legyen xe = 1/k minden e ´elre. ´Igy az integralit´ as t´etel miatt van x∗ lehets´eges eg´esz megold´as, amelyben x∗e ∈ {0, 1} minden e ´elre. Val´oj´aban A minden pontj´ab´ol pontosan egy ´el vezet ki, melyekhez tartoz´ o v´altoz´o ´ert´eke 1, ´es ezek az ´elek egy M teljes p´ aros´ıt´ ast adnak. 2
31
5. el˝oad´as
2
A maxim´ alis folyam probl´ ema
A maxim´ alis folyam probl´ema felfoghat´o egy olyan transshipment probl´emak´ent, amelyben a v´ altoz´ok ´ert´ekeire fels˝o korl´atokat k¨ot¨ unk ki. Ezt a kapcsolatot felhaszn´ alva elm´eleti k¨ovetkeztet´eseket vonhatunk le, illetve a feladatot megold´ o algoritmusokhoz juthatunk. A ter¨ ulet fejl˝od´ese nem ezt az ir´ anyt k¨ ovette ´es mi sem fogjuk ezt tenni, ugyanis k¨ozvetlen, a szimplex algoritmusra nem hivatkoz´o eszk¨oz¨okkel t´argyalhat´o a probl´ema. Mi t¨ obb, az ad´ od´ o bizony´ıt´ asok egyszer˝ ubbek, az algoritmusok hat´ekonyabbak, mintha ´ altal´ anos elm´eleten kereszt¨ ul ´ern´enk el c´eljainkat. P´ elda: Kezdj¨ uk egy klasszikus p´eld´aval, amelyben San Franciscob´ol New Yorkba igyekszik egy rep¨ ul˝ot´arsas´ag maxim´alis sz´am´ u embert utaztatni. ´ Utk¨ ozben t¨ obb ´ atsz´ all´ asi lehet˝os´eg van ´es az egyes v´arosok k¨oz¨ott sz´all´ıthat´o utasok sz´ am´ at egy t´ abl´ azatban foglaljuk ¨ossze. Honnan San Francisco San Francisco Denver Denver Houston Atlanta Chicago
Hov´a Denver Houston Atlanta Chicago Atlanta New York New York
Helyek sz´ama 5 6 4 2 5 7 4
C b 4s
2 D b
4s
5 SF b
b
7
A
6s
b NYC
b
5
H
A t´ abl´ azat ´ at´ırhat´ o egy ir´any´ıtott gr´af seg´ıts´eg´evel; az ´elek s´ ulyoz´asa az elsz´ all´ıthat´ o utasok maxim´ alis sz´am a k´et pontnak megfelel˝o v´aros k¨oz¨ott. A k¨ ovetkez˝ oket szeretn´enk formaliz´alni egy sz´all´ıt´asi tervben: 1. Ha (v, w) u ´ton k ember megy az ugyanaz, mint a (w, v) u ´ton −k ember. 2. A egy u ´ton k¨ uld¨ ott emberek sz´ama nem haladhatja meg az u ´t korl´atj´at. 3. SF ´es NYC kiv´etel´evel a be´erkez˝o ´es t´avoz´o utasok sz´ama egyenl˝o, azaz az 1. pont miatt az ¨osszeg nulla. Legyen G egy ir´ any´ıtott gr´af k´et kit¨ untetett ponttal, s (forr´ as) ´es t (nyel˝ o). Jel¨ olje c(v, w) a (v, w) ´el kapacit´ as´ at, azaz az ´elhez tartoz´o v´altoz´o maxim´ alis ´ert´ek´et, tov´ abb´ a legyen c(v, w) = 0, ha (v, w) nem ´el G-ben. Az 32
f : V (G) × V (G) → R f¨ uggv´eny folyam, ha az al´abbi h´arom felt´etelnek eleget tesz: (1) Ferde szimmetria. Minden v, w pontra f (v, w) = −f (w, v). Ha f (v, w) > 0, akkor azt mondjuk, van folyam v-b˝ol w-be. (2) Kapacit´ as korl´ at. Minden v, w pontra f (v, w) ≤ c(v, w). Ha (v, w) olyan, hogy f (v, w) = c(v, w), azt mondjuk a folyam tel´ıti (v, w)-t. (3) A folyam megmarad´ as elve. Minden s ´es t-t˝ol k¨ ul¨onb¨oz˝o v pontra P f (v, w) = 0. w∈V (G) A folyam ´ert´eke, |f | := w∈V (G) f (s, w), azaz a forr´asb´ol kifoly´o mennyis´eg. A maxim´ alis folyam probl´ema a maxim´alis ´ert´ek˝ u folyam megkeres´ese. Vizsg´ alataink k¨ ozponti fogalma a v´ ag´ as. Egy X, X v´ ag´ as a V (G) ponthalmaz olyan part´ıci´ oja, hogy s ∈ X ´es t ∈ X = V (G)\X. Az X, X P u v´ ag´ as kapacit´ asa c(X, X) := v∈X,w∈X c(v, w). Egy minim´alis kapacit´as´ v´ ag´ ast minim´ alis v´ ag´ asnak nevez¨ unk. Ha f egy folyam, X, X egy v´ag´as, P akkor a v´ ag´ ason ´ atmen˝ o folyam f (X, X) := v∈X,w∈X f (v, w). P
Lemma 1 B´ armely f folyam ´es X, X v´ ag´ as eset´en a v´ ag´ ason ´ atmen˝ o folyam egyenl˝ o a folyam ´ert´ek´evel. Bizony´ıt´ as. f (X, X) =
X
X
f (v, w) =
f (v, w) −
f (v, w) = |f |,
v∈X,w∈X
v∈X,w∈V (G)
v∈X,w∈X
X
mert v∈X,w∈V (G) f (v, w) = |f | a folyam megmarad´as, pedig nulla a ferde szimmetria t¨orv´enye miatt. P
P
v∈X,w∈X
f (v, w) 2
A lemma szeml´eletes jelent´ese az, hogy a folyam ´ert´eke egyenl˝o az X-et elhagy´ o nett´ o mennyis´eggel. Mivel f (v, w) ≤ c(v, w), |f | =
X
f (v, w) ≤
v∈X,w∈X
X
c(v, w)
v∈X,w∈X
minden f folyam ´es X, X v´ag´as eset´en. ´Igy a maxim´alis folyam ´ert´eke nem haladja meg a minim´ alis v´ag´as ´ert´ek´et. A meglep˝o az, hogy ez a k´et ´ert´ek egyenl˝ o. Ez igaz´ ab´ ol az LP dualit´as t´etel egy speci´alis esete, melyet n´eh´eny fogalom bevezet´es´evel k¨ozvetlen¨ ul is bel´athatunk. A marad´ek kapacit´ as egy f folyamra v ´es w pontok k¨oz¨ott r(v, w) := c(v, w) − f (v, w). Szeml´eletesen r(v, w) egys´eggel n¨ovelhetj¨ uk a folyamot 33
v-b˝ ol w-be (ha ugyanennyivel cs¨okkentj¨ uk f (w, v) ´ert´ek´et). Az R marad´ek gr´ af egy folyamra G pontjaib´ol ´es azon (v, w) p´arokb´ol, mint ´elekb˝ol ´all, amelyekre r(v, w) > 0: lehetnek olyan ´elei, melyek nincsenek G-ben. Egy p n¨ ovel˝ ou ´t az f folyamra egy s-b˝ol t-be vezet˝o u ´t R-ben. A p u ´t marad´ek kapacit´ asa, r(p) a p-ben l´ev˝o ´elek marad´ek kapacit´asainak minimuma. A p n¨ ovel˝ o u ´t szerepe nyilv´ anval´o: a p ´elei ment´en r(p)-vel n¨ovelve az f folyamot, a folyam ´ert´eke r(p)-vel n¨ovelhet˝o. (Ha f (v, w)-t v´altoztatjuk, v´ altozik f (w, v) is!) Lemma 2 Legyen f egy tetsz˝ oleges, f ∗ pedig egy maxim´ alis folyam G-n. Ha R az f -hez tartoz´ o marad´ek gr´ af, akkor R-en a maxim´ alis folyam ´ert´eke |f ∗ | − |f |. Bizony´ıt´ as. Legyen f 0 tetsz˝oleges folyam R-en ´es defini´aljuk az f + f 0 folyamot az (f + f 0 )(v, w) := f (v, w) + f 0 (v, w) egyenl˝os´eggel. Ekkor f + f 0 folyam G-en, ´ert´eke |f | + |f 0 | ≤ |f ∗ |, amib˝ol |f 0 | ≤ |f ∗ | − |f | ad´odik. A hasonl´ oan defini´ alt f ∗ − f , (f ∗ − f )(v, w) := f ∗ (v, w) − f (v, w) folyam ∗ R-en, ´ert´eke |f | − |f |, azaz az el˝oz˝oek miatt maxim´alis folyam R-en. 2 T´ etel 9 (maxim´ alis folyam - minim´ alis v´ ag´ as t´etel) A k¨ ovetkez˝ o felt´etelek ekvivalensek: (i) Az f folyam maxim´ alis. (ii) Nincs n¨ ovel˝ ou ´t f -re. (iii) Valamely X, X v´ ag´ asra az |f | = c(X, X). Bizony´ıt´ as. (i)⇒ (ii) Ha van egy p n¨ovel˝o u ´t f -re, akkor n¨ovelhetj¨ uk a folyam ´ert´ek´et a p-ben l´ev˝ o ´eleken megv´altoztatva a folyamot. (ii)⇒ (iii) Tegy¨ uk fel, hogy f -re nincs n¨ovel˝o u ´t. Legyen X azon pontok halmaza, melyek el´erhet˝ ok s-b˝ ol az R ´eleit haszn´alva, ´es legyen X = V (G)\X. ekkor X, X egy v´ ag´ as (s ∈ X, t ∈ X), ´es |f | =
X v∈X,w∈X
X
f (v, w) =
c(v, w) = c(X, X),
v∈X,w∈X
mert v ∈ X, w ∈ X-b˝ ol k¨ovetkezik, hogy (v, w) nem ´ele R-nek, azaz f (v, w) = c(v, w) (iii)⇒ (i) Mivel |f | ≤ c(X, X) b´armely f folyam ´es X, X v´ ag´ as eset´en, az |f | = c(X, X) egyenl˝os´egb˝ol k¨ovetkezik, hogy f maxim´alis folyam ´es X, X minim´ alis v´ag´as. 2
34
Az el˝ oz˝ o t´etel az alapja Ford ´es Fulkerson u ´n. n¨ ovel˝ ou ´ t m´ odszer´ enek: Induljunk ki a z´erus folyamb´ol (f (v, w) = 0 minden (v, w) ´elre), majd ism´etelj¨ uk meg a n¨ ovel˝ o l´ep´est am´ıg olyan folyamhoz jutunk, amiben nincs n¨ ovel˝ o u ´t. N¨ ovel˝ o l´ ep´ es: Tal´aljunk egy p n¨ovel˝o utat a pillanatnyi f folyamra. N¨ ovelj¨ uk f ´ert´ek´et r(p) egys´eggel a p-ben l´ev˝o ´eleken. T´ etel 10 (integralit´ as t´etel) Ha egy folyam probl´em´ aban a kapacit´ asok eg´eszek, akkor van egy eg´esz ´ert´ek˝ u maxim´ alis folyam. Bizony´ıt´ as. Tegy¨ uk fel, hogy a kapacit´asok eg´eszek. Ekkor a n¨ovel˝o u ´t m´ odszer legal´ abb egy egys´eggel n¨oveli a folyam ´ert´ek´et minden iter´aci´oban, ´ıgy f ∗ maxim´ alis folyamot legfeljebb |f ∗ | l´ep´esben megkapja. Masr´eszt a kezdeti eg´esz ´ert´ekeket minden l´ep´esben eg´esz sz´ammal v´altoztattuk, ´ıgy f ∗ (v, w) eg´esz minden (v, w) ´elre. 2 A p´eld´ ankban az al´ abbi l´ep´esekkel kaphatunk maxim´alis folyamot. Baloldalon a folyam ´ert´ekeket, mellette a hozz´atartoz´o marad´ek gr´afot a n¨ovel˝o u ´ttal egy¨ utt ´ abr´ azoljuk. Inicializ´ al´ as. A n¨ ovel˝ ou ´t: SF-H-A-NYC, r(p) = 5 b
b 0s
0
b
b
b
0
0s
b 0s
0
b
b
0
4s
2
b
4s
5
b
b
7
6s
b
5
1. l´ep´es. A n¨ ovel˝ ou ´t: SF-D-C-NYC, r(p) = 2 b
b 0s
0
b 0
0s
b 5s
5
b
b
b
4s
2
b
5
4s
5
b 5 jY b 1
2. l´ep´es. A n¨ ovel˝ ou ´t: SF-D-A-NYC, r(p) = 2
35
2
5
b
5
b
b 2
b b
0s
2
b 5s
b
2s 5
3 2 5
b 2 j Y b 2 2 2 b s 4 b 5
b
5 b
jY b
5
1
¯ a teli ill. u 3. l´ep´es. Nincs n¨ ovel˝ ou ´t, |f ∗ = 9|, X, X ¨res pontok az ´abr´an. b 2
b 2s
4
b 5s
b
b
d 2 j Y d 2 2 td 2 j Y td 7
b
2s 7
1 2 4 td 5 Y 5 j td
5
1
Megjegyz´ es: A n¨ ovel˝ ou ´t m´odszer nem sz¨ uks´egk´eppen konverg´al, ´es eg´esz sz´ amok eset´en is lehet nagyon hossz´ u. Edmonds ´es Karp viszont megmutatta 1969-ben, hogy a legkevesebb ´elb˝ ol ´all´o n¨ovel˝o u ´t v´alaszt´as´aval az algoritmus cnm2 m˝ uveletet ig´enyel, ahol c konstans, n a pontok, m pedig az ´elek sz´ama G-ben. P´ elda: Az els˝ o rajzon a kapacit´asok, a t¨obbin a k¨ozel´ıt´esek, ha a n¨ovel˝o u ´t ´ athalad a f¨ ugg˝ oleges ´elen. (Csak a folyamot ´abr´azoltuk, a marad´ekgr´afot nem.) Ekkor algoritmus l´ep´essz´ama k. Ha a legr¨ovidebb n¨ovel˝o utakat v´ alasztjuk, akkor k´et l´epesben eljutunk az optimumhoz. b k @ R @ @ b s 1 ? bt @ R k @ k @b k
b 0 @ R @ @ b s 1 ? bt @ R 1 @ 0 @b 1
b 1 @ R @ @ b s 0 ? bt @ R 1 @ 1 @b 1
b 1 @ R @ @ b s s 1 ? bt @ ... R @ 1 2 @ b 2
b k @ R @ b0 ?@ bt @ R k @ k @b k
A k¨ ulsz´ıni fejt´ es probl´ ema A maxim´ alis folyam probl´ema egy v´aratlan ´es m´ely alkalmaz´asa f˝ uz˝odik Balinsky, Rhys ´es Picard nev´ehez, amit k¨ ulsz´ıni fejt´es (vagy open pit) probl´em´ anak h´ıvnak. Tegy¨ uk fel, hogy egy adott ter¨ uleten valamely m´elys´egig felosztottuk a talajt, ´es ismerj¨ uk egy-egy r´eszben l´ev˝o ´asv´any ´ert´ek´et, illetve az adott r´esz kitermel´esi k¨ olts´eg´et. Az egyszer˝ us´eg kedv´e´ert t´eglatest alak´ u
36
darabokkal sz´ amolunk ´es az i-edik darab ´ert´eke wi a benne lev˝o ´asv´any ´ert´ek´enek ´es a kitermel´esi k¨olts´eg k¨ ul¨onbs´ege. P Feladatunk azon P halmaz megtal´al´asa, amelyre a i∈P wi maxim´alis. A neh´ezs´eg abban rejlik, hogy P nem lehet ak´armilyen halmaz; meg kell felelnie egy lehets´eges kitermel´esnek. Ez alatt azt ´ertj¨ uk, ha egy t´egl´at kitermel¨ unk, akkor nemcsak a felette l´ev˝o t´egl´at, de m´eg annak szomsz´edait is ki kell termeln¨ unk, m´egha negat´ıv is az ´ert´ek¨ uk.5 P´ elda: -1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-2
-1
1
5
3
1
-5
4
-1
-1
1
1
0
10
5
1
1
1
1
0
´ Altal´ aban ha az i-edik elem hozz´av´etele a P halmazhoz kik´enyszer´ıti a j-edik elem hozz´ av´etel´et azt egy (i, j) ir´any´ıtott ´ellel jel¨olj¨ uk majd a G gr´ afban, melynek a pontjai az elemek. Legyen ennek a gr´afnak egy X ⊂ V (G) ponthalmaza z´ art, ha i ∈ X ´es (i, j) ∈ E(G) eset´en j ∈ X. ´ Ujrafogalmazva a probl´em´ at egy olyan X z´art r´eszhalmaz´at keress¨ uk a ponP toknak, hogy a i∈X maxim´alis. Ezt a k¨ ovetkez˝ o ej´ ar´ assal visszavezethetj¨ uk egy minim´alis v´ag´as, vagy ami ezzel ekvivalens, egy maxim´alis folyam probl´em´ara. Osszuk fel G pontjait k´et r´eszre; i ∈ A, ha wi ≥ 0 illetve i ∈ B, ha wi < 0. Vegy¨ unk hozz´a G-hez k´et u ´j pontot, egy s forr´ ast ´es egy t nyel˝ ot, valamint egy (s, i) ´elt minden i ∈ A-ra, ´es egy (j, t) ´elt minden j ∈ B-re. legyen az u ´j ´elek kapacit´asa c(s, i) := wi minden i ∈ A-ra, c(j, t) := −wj minden j ∈ B-re, m´ıg G eredeti ´elenek kapacit´ asa v´egtelen. K¨ onnyen l´ athat´ o, hogy egy X ponthalmaz akkor ´es csak akkor z´art, ha az X ∪ {s}, X ∪ {t} v´ ag´ as kapacit´asa v´eges. '$ bi wi : s b X A
&%
'$ B
b t : −wj j b &%
Tov´ abb´ a ha az el˝ obbi v´ ag´as kapacit´asa v´eges, akkor az ´eppen c(X ∪ {s}, X ∪ {t}) =
X i∈A\X
5
c(s, i) +
X
c(i, t) =
i∈B∩X
Ez b´ anyatechnikai el˝ o´ır´ as, ugyanis bizonyos sz¨ ogn´el meredekebb lejt˝ ot nem szabad l´etrehozni k¨ ulsz´ıni fejt´esn´el.
37
=
X i∈A\X
wi +
X
(−wi ) =
i∈B∩X
X i∈A
P
wi −
X
wi .
i∈X
Mivel a i∈A wi konstans, a fenti v´ag´as kapacit´as´anak minimaliz´al´asa a i∈X wi maximaliz´ al´ as´ at jelenti. Azaz a minim´alis v´ag´as megtal´al´asa egyben megadja a keresett maxim´alis s´ uly´ u z´art ponthalmazt. P
38
6. el˝oad´as Moh´ o algoritmusok Mint kor´ abban l´ athattuk, sz´amos iter´aci´on alapul´o algoritmusnak van moh´ o aspektusa: az algoritmus az adott pillanatban a legkedvez˝obbnek t˝ un˝o lehet˝ os´eget v´ alasztja. Ez a megk¨ozel´ıt´es n´eha kiv´al´o, n´eha katasztrof´alis eredm´ennyel j´ ar; mindenesetre egy u ´jonnan felmer¨ ul˝o probl´em´an´al c´elszer˝ u szerencs´et pr´ ob´ alni vele. Ha pontos megold´ast nem is, hasznos inform´aci´okat nyerhet¨ unk ´ altala. A moh´ o algoritmusok ´altal´aban nagyon gyorsak ´es egyszer˝ uek, ´ıgy ha egy feladatot pontosan oldanak meg, akkor nemigen lehet jobbat tal´ alni n´ aluk. A k¨ ovetkez˝o n´eh´any probl´em´aban ez az eset ´all fenn. P´ elda: Maxim´ alis s´ uly´ u fesz´ıt˝ ofa Tegy¨ uk fel, hogy adott egy ir´any´ıtatlan, ¨osszef¨ ugg˝o G gr´af, melynek ´eleihez nem negat´ıv s´ ulyokat rendel¨ unk; w(e) ≥ 0, ha e ∈ E(G). C´elunk egy olyan X ⊆ E(G) ´elhalmaz megad´asa, mely X nem tartalmaz k¨ort ´es a P alis. (A szumma jel¨olhet˝o w(X)-szel ´es ez X s´ ulya.) e∈X w(e) maxim´ Megjegyz´ es: Mivel w(e) ≥ 0 minden e ´elre, feltehet˝o, hogy X maxim´alis k¨ ormentes halmaz, azaz fesz´ıt˝ ofa G-ben. K¨onnyebben motiv´alhat´o lenne egy minim´ alis s´ uly´ u fesz´ıt˝ ofa keres´ese, ami p´eld´aul egy minim´alis k¨olts´eg˝ u ¨osszef¨ ugg˝ o kommunik´ aci´ os h´al´ozatot modellezhet. A probl´ema val´oban ´ıgy vet˝ od¨ ott fel el˝ osz¨ or (Bor˚ uvka 1926, illetve Kruskal 1956), nem neh´ez viszont bel´ atni az ekvivalenci´ ajukat. Az al´ abbi moh´ o algoritmus t˝ unik k´ezenfekv˝onek: Rendezz¨ uk az ´elhalmaz e1 , e2 , . . . , em elemeit u ´gy, hogy w(e1 ) ≥ w(e2 ) ≥ . . . w(em ). Legyen X1 = {e1 }, majd az Xi−1 halmazhoz pr´ob´aljuk hozz´avenni az ei ´elt; ha Xi−1 ∪{ei } k¨ ormentes, akkor Xi := Xi−1 ∪ {ei }, ellenkez˝o esetben Xi := Xi−1 . Legyen v´eg¨ ul X := Xm , illetve tulajdonk´eppen X := Xi , ahol i a legkisebb sz´am, amelyre |Xi | = n − 1. Az algoritmus helyess´eg´et sokkal ´altal´anosabb k¨or¨ ulm´enyek k¨oz¨ott is bel´ athatjuk; csup´ an a k¨ ormentes ´elhalmazok n´eh´any tulajdons´ag´ara van sz¨ uks´eg. Nyilv´ anval´ o, hogy a ∅, azaz az u ¨res halmaz k¨ormentes, illetve ha X ⊆ E(G) k¨ ormentes, akkor b´armely Y ⊆ X is az. Sz¨ uks´eg¨ unk van tov´ abb´ a az al´ abbira ´ all´ıt´ asra: Lemma 3 Ha X ´es Y egy G gr´ af k¨ ormentes ´elhalmazai ´es |Y | < |X|, akkor van olyan e ∈ X\Y , hogy Y ∪ {e} is k¨ ormentes.
39
Bizony´ıt´ as. A G gr´ af pontjain az Y ´elek ´altal alkotott komponensek r´eszf´ ak. Egy-egy ilyen komponensben az X ´elhalmaznak sem lehet t¨obb ´ele, mint Y -nak, hiszen k¨ ul¨onben tartalmazna k¨ort. Mivel |X| > |Y |, van olyan e ∈ X, mely az Y k´et komponens´et k¨oti ¨ossze. Ezzel az e ´ellel az Y ∪ {e} halmaz k¨ ormentes. 2 Matroidok Ha adott egy S v´eges halmaz ´es az S r´eszhalmazainak egy I halmaza u ´gy, hogy (I1 ) ∅ ∈ I; (I2 ) Ha X ∈ I ´es Y ⊆ X, akkor Y ∈ I; (I3 ) Ha X ∈ I ´es Y ∈ I; tov´abb´a |X| > |Y |, akkor van olyan x ∈ X\Y u ´gy, hogy Y ∪ {x} ∈ I, akkor az M = (S, I) p´ ar matroid. Az I-be tartoz´o halmazokat a matroid f¨ uggetlen halmazainak nevezz¨ uk. Egy halmazrendszer, amely az (I1 ) ´es (I2 ) axi´ om´ akat kiel´eg´ıti f¨ uggetlens´egi rendszer. P´ eld´ ak: 1. Az el˝ obbiek szerint egy G ir´any´ıtatlan gr´af E(G) ´elhalmaz´anak k¨ormentes r´eszhalmazai matroidot alkotnak. Ez a G gr´af k¨ ormatroidja. 2. Vektormatroidok. Legyen S v´eges sok vektorb´ol ´all´o halmaz, I pedig a line´ arisan f¨ uggetlen r´eszhalmazainak halmaza. Erre (I1 ) ´es (I2 ) nyilv´anval´oan k¨ ovetkezik, (I3 ) pedig a j´ ol ismert Steinitz-f´ele kicser´el´esi t´etel. Megjegyz´ es: (I3 )-b´ ol k¨ ovetkezik, hogy a maxim´alis f¨ uggetlen f¨ uggetlen halmazok egyforma elemsz´ am´ uak. Ezek az M matroid b´ azisai. C´elunk egy M = (S, I) matroid ´es w : S → R+ eset´en annak az X ∈ I P halmaz megtal´ al´ asa, amelyre a x∈X w(x) maxim´alis. (Feltehet˝o, hogy ez a halmaz maxim´ alis, azaz b´azis.) A moh´ o algoritmus a k¨ovetkez˝o: Rendezz¨ uk S = {x1 , . . . , xm }-et u ´gy, hogy w(xi ) ≥ w(j), 1 ≤ i < j ≤ m. Legyen X1 := {x1 }, Xi := Xi−1 ∪ {xi }, ha Xi−1 ∪ {xi } ∈ I, Xi := Xi−1 k¨ ul¨onben. V´eg¨ ul pedig X := Xm . T´ etel 11 Tetsz˝ oleges M = (S, I) matroid ´es w nem negat´ıv s´ ulyf¨ uggv´eny eset´en a moh´ o algoritmus egy maxim´ alis s´ uly´ u f¨ uggetlen X halmazt tal´ al.
40
Bizony´ıt´ as. Tegy¨ uk fel, hogy a moh´o algoritmus az X = {x1 , x2 , . . . , xn } P P b´ azist adta, de egy Y = {y1 , y2 , . . . , yn } b´azisra ni=1 w(xi ) < ni=1 w(yi ). Feltessz¨ uk, hogy az X ´es Y elemei cs¨okken˝o s´ uly szerint vannak rendezve, azaz w(xi ) ≥ w(xj ) ´es w(yi ) ≥ w(yj ), 1 ≤ i < j ≤ n. P P Mivel w(xi ) < w(yi ), lennie kell egy olyan legkisebb k sz´amnak, amelyre w(xk ) < w(yk ). Legyen A = {x1 , . . . , xk−1 } ´es B = {y1 , . . . , yk }. (Ha k = 1, akkor A = ∅.) Az (I2 ) miatt A, B ∈ I ´es |A| < |B|, ´ıgy (I3 ) miatt van olyan yj ∈ B, melyre A ∪ {yj } ∈ I. Ekkor viszont w(yj ) ≥ w(yk ) > w(xk ) ´es ´ıgy a moh´ o algoritmus nem az xk , hanem az yj elemet v´alasztotta volna. 2 A fenti t´etel r´eszlegesen megford´ıthat´o ´es ez mutatja a matroidok ´es a moh´ o algoritmus szoros kapcsolat´at. T´ etel 12 (Edmonds) Legyen S egy v´eges halmaz, I pedig S r´eszhalmazainak egy (I1 )-et ´es (I2 )-¨ ot kiel´eg´ıt˝ o halmaza, amely nem matroid. Ekkor van olyan w : S → R+ s´ ulyf¨ uggv´eny, amelyre a moh´ o algoritmus nem tal´ alja meg I maxim´ alis s´ uly´ u elem´et. Bizony´ıt´ as. Mivel az (S, I) p´ar nem matroid ((I3 ) nem mindig teljes¨ ul), van olyan X, Y ∈ I, hogy |X| > |Y |, de b´armely x ∈ X\Y eset´en az Y ∪ {x} 6∈ I. Legyen w(y) = 1 minden y ∈ Y -ra, w(x) = 1 − , ha x ∈ X\Y , ahol > 0, ´es w(z) = 0 k¨ ul¨onben. Ekkor a moh´o algoritmus az Y halmazt P szolg´ altatja; ennek s´ ulya y∈Y w(y) = |Y |. M´asr´eszt X ∈ I, a s´ ulya pedig X
w(x) =
X
w(x) +
x∈X∩Y
x∈X
X
w(x) =
x∈X\Y
= |X ∩ Y | + (1 − )|X\Y | ≥ (1 − )|X| ≥ (1 − )(|Y | + 1). Ha 0 < < 1, akkor az (1 − )(|Y | + 1) > |Y |, ´es ´ıgy w(X) > w(Y ). ' $ '$ '$ 1 0
1
1− 0
&% &% X & Y %
2 Megjegyz´ es: Amennyiben minim´alis s´ uly´ u b´azist szeretn´enk tal´alni, alkalmazhatunk egy egy transzform´aci´ot: Vegy¨ uk a s´ ulyok −1-szeres´et, majd adjunk hozz´ a egy elegend˝ oen nagy konstanst. (w(x) ˆ = −w(x) + K, ahol 41
K ≥ w(x) minden x ∈ S-re.) Mivel a b´azisok azonos elemsz´am´ uak, az u ´j s´ ulyok mellett maxim´ alis X ∈ I minim´alis az eredeti s´ ulyf¨ uggv´ennyel. Ugyanezen transzform´ aci´ o szerint m´odos´ıthatjuk a moh´o algoritmust ´es a s´ ulyok szerint n¨ ovekv˝ o sorrendbe ´all´ıtott elemeken v´egrehajtva egyb˝ol a minimumot kapjuk. P´ elda: Balra a s´ ulyozott G gr´af, jobbra a minim´alis fesz´ıt˝ofa; a z´ar´ojelben az adott ´el megold´ asba ker¨ ul´es ideje (l´ep´ese) l´athat´o. 1(3) r r @ @ 4(5) 1(2) @ @@r 1(4) r @ @ @ 0(1) @ @r @r
1 r r @ 4 @ 1 1 @ @ r 2 2 @r @ @ 0 5 3 @ @ @r @r 2
w(X) = 7
Felmer¨ ulhet a k´erd´es, van-e egy´altal´an m´as matroid, mint a k¨ormatroidok. Vegy¨ unk egy n elem˝ u S halmazt, ´es legyen I az ¨osszes k-n´al (k ≤ n) nem nagyobb elemsz´ am´ u r´eszhalmaz´anak halmaza. Ez az u ´n. Un,k uniform matroid. K¨ onny˝ u bel´ atni, hogy p´eld´aul az U4,2 nem lehet semmilyen G gr´af k¨ ormatroidja. (Szint´en nem neh´ez megmutatni, hogy az Un,k , 0 ≤ k ≤ n felfoghat´ o, mint vektormatroid.) Term´eszetesen m´ as k¨ or¨ ulm´enyek k¨oz¨ott a moh´o algoritmus sikeres lehet an´elk¨ ul, hogy egy matroid strukt´ ura garant´aln´a az algoritmus el´er´es´et. Egy egyszer˝ u p´elda erre a legr¨ ovidebb utak probl´em´aj´anak egy speci´alis esete. Dijkstra algoritmusa Tegy¨ uk fel, hogy egy G ir´any´ıtott gr´afban minden ´el l(v, w) s´ ulya nem negat´ıv. A G gr´ afban nincs negat´ıv s´ uly´ u k¨or, ´ıgy b´armely s ´es v pontokra l´etezik az s-b˝ ol v-be vezet˝o utak hossz´anak a minimuma (ez v´egtelen, ha nincs s − v u ´t). Az s-b˝ol kiindul´o legr¨ovidebb utak hossz´at, illetve ezen utakat le´ır´ o fesz´ıt˝ of´ at egy egyszer˝ u ´es gyors algoritmussal, n = |V (G)| iter´ aci´ oban megkaphatjuk. Az elj´ar´ast 1956-ban publik´alta Edsgar Dijkstra. • 1. l´ ep´ es: Legyen X1 := {s}, d(s) = 0, d(v) = ∞ ha v 6= s ´es T1 := {s}, egypont´ u fa. • k. l´ ep´ es: Tegy¨ uk fel, hogy Xk−1 ´es d(v) (v ∈ Xk−1 ) m´ar defini´altak. V´ alasszunk egy olyan w ∈ V (G)\Xk−1 pontot, amelyre a d(v)+l(v, w) minim´ alis, ahol v ∈ Xk−1 . Legyen Xk := Xk−1 ∪ {w}, d(w) := (v) + l(v, w), Tk pedig az a fa, amelyet Tk−1 -b˝ol a w pont ´es a (v, w) u ´t hozz´ av´etel´evel nyer¨ unk. 42
T´ etel 13 A fentiek mellett az algoritmus n-edik l´ep´ese ut´ an d(v) ´ert´eke a legr¨ ovidebb s − v u ´t hossza minden v ∈ V (G) eset´en. Tov´ abb´ a Tn az s-b˝ ol kiindul´ o legr¨ ovidebb utakat k´ odol´ o fa. Bizony´ıt´ as. A t´etelt a l´ep´esek sz´ama szerinti teljes indukci´oval l´atjuk be. Az indukci´ os felt´etel szerint v ∈ Xk−1 eset´en d(v) a legr¨ovidebb s − v u ´t hossza, ´es tegy¨ uk fel, hogy w ∈ Xk \Xk−1 -re d(w) = minv∈Xk−1 d(v) + l(v, w) nem ezt, azaz a legr¨ ovidebb s − w u ´t hossz´at adja. Ekkor a p legr¨ovidebb s−w u ´t egy u pontb´ ol kil´epve el˝osz¨or hagyja el Xk−1 -et. Legyen a p u ´tban az u ut´ an k¨ ovetkez˝ o pont y (feltehet˝o, hogy y 6= w). Xk−1
'
s
$
v bH jHbw H
b b- b
y
u
&
%
Mivel p hossza kisebb, mint d(w), a p vonal´an halad´o s − y u ´t hossza is kisebb, mint d(w). (Itt haszn´aljuk ki a s´ ulyok nem negativit´as´at.) Ekkor viszont az algoritmus az y pontot v´alasztotta volna a k-adik l´ep´esben, ellentmond´ as. A Tn fa szerep´enek bizony´ıt´asa szint´en indukci´oval t¨ort´enhet; ´ıgy Tk−1 r¨ ogz´ıti a legr¨ ovidebb s − v utakat (v ∈ Xk−1 ) ´es azon (v, w) ´el hozz´ av´etel´evel v´ altoztatjuk Tk−1 -et Tk f´av´a, amelyen kereszt¨ ul a w pont d(w) hossz´ uu ´ton el´erhet˝ o s-b˝ol. 2 P´ elda: Baloldalon egy ir´ any´ıtatlan, s´ ulyozott G gr´af az s kiindul´oponttal. Jobboldalon az s-b˝ ol indul´ o legr¨ovidebb utak f´aj´at; a sz´amoz´as azt mutatja, hanyadik l´ep´esben ker¨ ult be a pont a f´aba.
s r
1
2 r @ 1 2 3 @ @r
r
r
5
0
0
3 1
@ 0
@ @r
4
r
2
r
r @
r @ @@r
r5
r8
6
r7
4
@ @r 2
r
A legr¨ ovidebb utak hossz´ at is k¨onnyen leolvashatjuk. A gy¨ok´erpont, azaz s ¨ onmag´ at´ ol vett t´ avols´ aga nulla, egy x pontra pedig u ´gy kaphatjuk meg d(x)-et, ha ¨ osszeadjuk az f´ aban az s − x u ´t ´elein l´ev˝o s´ ulyokat.
43
1 0
r @
@ @r r 2 @ @ @r 0
r3
r6
4
r6
r
Megjegyz´ es: Dijkstra algoritmusa j´oval egyszer˝ ubb ´es gyorsabb, mint a kor´ abban ismertetett Bellman algoritmus, ugyanakkor csak nemnegat´ıv s´ ulyok eset´en alkalmazhat´ o. P´ elda: Baloldalon a gr´ af, k¨ oz´epen a Bellmann algoritmus ´altal adott (helyes) legr¨ ovidebb utak f´ aja, jobboldalon pedig a Dijkstra algoritmus v´egrehajt´as´ aval kapott f´ at ´ abr´ azoltuk. xr 1
@ R1 @ @ @r t
s r @ R @ 2 @ −2 @r y
xr
xr
s r @ R @ @@r y
rt
@ R @ @ r @r t s @ R @ @ @r y
Azaz a Dijkstra m´ odszer nem tal´alja meg a legr¨ovidebb s − t utat, hisz d(t) = 0, nem kett˝ o ´es a legr¨ovidebb s − t u ´t nem az {s, x, t} hanem az {s, y, t}.
44
@ R @
7. el˝oad´as
3
Stabil P´ aros´ıt´ asok
A stabil p´ aros´ıt´ as vagy stabil h´azass´ag probl´ema kiv´al´o p´elda mind a gyakorlat ´es elm´elet viszony´ anak szeml´eltet´es´ere, mind a moh´o algoritmus egy u ´jabb illussztr´ aci´ oj´ ara. A probl´emak¨ort eredetileg az USA-ban a 40-es ´evek k¨ ozep´en kulmin´ al´ o orvos gyakornok hi´any, illetve eloszt´asi zavar motiv´alta. A v´egz˝ os orvosok ezreit kellett a k´orh´azak ´altal meghirdetett helyekre beosztani; r´ aad´ asul mindk´et f´el (orvos vs. k´orh´az) a saj´at preferenci´ait igyekezett ´erv´enyes´ıteni. Az eredetileg alkalmazott technik´ak teljesen alkalmatlann´a v´ altak 1947-re, mikoris egy radik´alisan u ´j rendszert vezzettek be helyett¨ uk. ´ Erdekes m´ odon ennek elm´eleti vizsg´alat´at csak 1962-ben tette meg D. Gale ´es L. S. Shapley, s igaz´ ab´ ol ˝ok nem tudtak a probl´em´ar´ol: az egyetemi felv´eteli rendszert illetve a h´azass´agok stabilit´as´at akart´ak modellezni.6 Mi az ´ altaluk vizsg´ alt legegyszer˝ ubb modellt ismertetj¨ uk, utalva r´a, hogy igen sok ´ altal´ anos´ıt´ as sz¨ uletett az´ota. A stabil h´azass´ag probl´em´aban adott n f´erfi, n n˝ o ´es mindegyik¨ uk valahogyan rangsorolja az ellent´etes nem tagjait; ez az illet˝ o szem´ely preferencia list´ aja. A f´erfiakat g¨or¨og, a n˝oket latin bet˝ ukkel jel¨ olj¨ uk majd. ´Igy p´eld´aul akkor mondjuk, hogy az α (f´erfi) jobban kedveli vagy prefer´ alja A-t B-hez k´epest, ha α preferencia list´aj´an A el˝or´ebb van, mint B. A szem´elyeket ´es preferenci´aikat le´ırhatjuk (dupl´an) s´ ulyozott p´ aros gr´ afokkal, vagy m´ atrixokkal is az al´abbiaknak megfelel˝oen: P´ elda: α β γ
α
A 1, 3 3, 1 2, 2
B 2, 2 1, 3 3, 1
C 3, 1 2, 2 1, 3
β
γ
3 r rH 1 A 1 @H2 H 2 3@ H H @HH H 2 3@ H 1 3 Hr @ r H B @ 1 2HH H @ H H H@ 3 1 HH @ 2 H r 3 @r C 2 1
A m´ atrix egy elem´enek els˝o koordin´at´aja a megfelel˝o oszlop ´altal reprezent´ alt n˝ o helyez´ese a sorhoz tartoz´o f´erfi ranglist´aj´an, m´ıg a m´asodik 6
N´eh´ any ´eve a magyar fels˝ ooktat´ asi felv´eteli rendszere is hasonl´ o algoritmust haszn´ al.
45
koordin´ ata a ford´ıtott helyez´es. A feladat egy olyan n-elem˝ u M p´aros´ıt´as megad´asa, amely, legal´abbis valamely ´ertelemben, elk´epzelhet˝o. Gyakorlati ´es elm´eleti megfontol´asok alapj´ an az al´ abbi defin´ıci´ o t˝ unik ´esszer˝ unek: Defin´ıci´ o. Egy M p´ aros´ıt´as instabil ha vannak olyan α, β f´erfiak ´es A, B n˝ ok, hogy (α, A) ∈ M , (β, B) ∈ M , de β prefer´alja A-t B-hez k´epest, ´es A prefer´ alja β-t α-hoz k´epest. Egy M p´aros´ıt´as stabil, ha nem instabil. A defin´ıci´ o motiv´ aci´ oja k´ezenfekv˝o: feltehet˝o, hogy az instabil esetben β illetve A felbontja pillanatnyi kapcsolat´at, ´es egym´assal l´ep kapcsolatra. A c´elunk egy stabil M p´aros´ıt´as keres´ese lesz majd, m´ar ha van ilyen egy´ altal´ an. (A kor´ abban eml´ıtett Halmos-Vaughan modell glob´alis optimumra t¨ orekedett, nem v´eve figyelembe a lok´alis ´erdekeket, lehet˝os´egeket. Ez´ert legfeljebb kik´enyszer´ıthet˝o, m´ıg a fenti stabilit´as szerint egy M teljes p´ aros´ıt´ as nem bomlik fel, ha mag´ara hagyjuk a rendszert.) K´erd´es persze, van-e egy´altal´an megold´as? A fenti p´eld´aban h´arom megold´ as van: M1 = {(α, A), (β, B), (γ, C)}, M2 = {(α, C), (β, A), (γ, B)} ´es M3 = {(α, B), (β, C), (γ, A)}.
αr
βr
γr
M1
rA
rB
rC
αr A A
βr
M2
rA
αr @
M3
rA
@ @ @r B
@ @
A A A
rB
A A A A A A
γr
βr @
@ @ @ Ar C
γ r
@ @r C
P´ elda: A stabil h´ azass´ ag mint´aja alapj´an defini´alhatjuk az u ´n. szobat´ ars probl´em´ at. Itt adott 2n ember, akiket k´etszem´elyes szob´akba kell telep´ıteni ´es az el˝ oz˝ oekhez hasonl´ oan preferenci´akkal rendelkeznek. Nyilv´anval´o, ha adott n´egy szem´ely (α, β, γ, δ) u ´gy, hogy α, β ´es γ preferencia list´aj´an δ az utols´ o, α-´en β, β-´en γ ´es γ-´en α az els˝o, akkor nincs stabil p´aros´ıt´as.
46
βr 1 2@ 3 @
2
r γ
1
3
@ @ @ @ @ 1
α
@
2
r
3
@ @r
δ
A p´elda f´eny´eben kellemes meglepet´es az al´abbi t´etel. T´ etel 14 (Gale-Shapley) A stabil h´ azass´ ag probl´em´ anak mindig van megold´ asa. Bizony´ıt´ as. Val´ oj´ aban egy nagyon hat´ekony, moh´o t´ıpus´ u algoritmust adunk, melynek v´egeredm´enye bizonyosan stabil p´aros´ıt´as. Trad´ıcion´alisan, hisz ez igencsak trad´ıcion´ alis elj´ar´as, a megfelel˝o k¨oznapi kifejez´eseket haszn´ aljuk a le´ır´ as sor´ an. A elj´ ar´ as els˝ o l´ep´es´eben minden f´erfi aj´anlatot tesz a kedvenc´enek. Minden n˝ o a legjobb aj´ anlatot fogadja el, de ez csak annyit jelent, hogy “v´arakoz´o list´ ara” helyezi a k´er˝ ot. A m´asodik l´ep´esben az elutas´ıtott k´er˝ok u ´jra aj´anlatot tesznek, ez´ uttal a preferencia list´ajukon 2. helyezett h¨olgynek. A n˝ok ism´et a pillanatnyilag legjobb aj´anlatot fogadj´ak el; esetlegesen lecser´elve a v´ arakoz´ o list´ an l´ev˝ o k´er˝ ot. Hasonl´oan folytat´odik ez a k´es˝obbiekben is: egy elutas´ıtott (vagy egy v´ arakoz´o list´ar´ol leker¨ ult) f´erfi a soron k¨ovetkez˝o jel¨ olttel pr´ ob´ alkozik, m´ıg a n˝ok a lehet˝o legjobb jel¨oltet tartj´ak meg. Legk´es˝ obb n2 − 2n + 2 l´ep´es eltelt´evel minden h¨olgy kap legal´abb egy k´er˝ ot, ´ıgy a v´ arakoz´ o list´ aj´ an is lesz majd valaki. (Ugyanis ha egy l´ep´esben van olyan n˝ o, aki nem kapott m´eg aj´anlatot, akkor lennie kell elutas´ıt´asnak is ebben a l´ep´esben, illetve egy f´erfi csak egyszer tesz aj´anlatot egy n˝onek.) Mikor minden n˝ o kapott aj´anlatot, akkor v´eget vet¨ unk az elj´ar´asnak, ´es a pillanatnyi p´ arokat v´eglegesnek ki´altjuk ki. Megmutatjuk, hogy az ´ıgy kapott M p´ aros´ıt´ as stabil. Tegy¨ uk fel, hogy van olyan α ´es A, melyre (α, A) 6∈ M , de α prefer´ alja a p´arj´ahoz k´epest. Ekkor viszont α valamikor aj´ anlatot tett A-nak ´es A elutas´ıtotta ˝ot, azaz a v´arakoz´o list´aj´an α-n´al “jobb” szem´ely volt, s ha cser´el˝od¨ott is az´ota, csak m´eg jobb lehet k´es˝obb. ´Igy A a p´ arj´ at jobban kedveli, mint α-t, azaz nincs instabilit´as. 2 P´ elda:
47
α β γ δ
A 1, 3 1, 4 2, 2 4, 1
B 2, 3 4, 1 1, 4 2, 2
C 3, 2 3, 3 3, 4 3, 0
D 4, 3 2, 2 4, 1 1, 4
Az algoritmus v´egrehajt´as´at egy t´abl´azaton k¨ovethetj¨ uk. Egy cella baloldali eleme az adott l´ep´esben a sor ´altal k´odolt szem´elyt˝ol aj´anlatot kap´o, a jobboldali elem pedig a sor aj´anlat´at elfogadott szem´ely.
α β γ δ
1. l´ep´es A, A A, ∅ B, B D, D
2. l´ep´es ∅, A D, D ∅, B ∅, ∅
3. l´ep´es ∅, A ∅, D ∅, ∅ B, B
4. l´ep´es ∅, ∅ ∅, D A, A ∅, B
5. l´ep´es B, ∅ ∅, D ∅, A ∅, B
6. l´ep´es C, C ∅, D ∅, A ∅, B
A k¨ ovethet˝ os´eg kedv´e´ert felvett¨ uk a f´erfiak preferencia list´ait, ahol fel¨ ulvon´ assal jelezt¨ uk, ha m´ ar t¨ ort´ent aj´anlat: ¯ B, ¯ C, ¯ D) α(A, ¯ D, ¯ C, B) β(A, ¯ ¯ C, D) γ(B, A, ¯ B, ¯ C, A) δ(D, A megold´ ast az utols´ o oszlop jobboldal´ar´ol olvashatjuk le: M = {(α, C), (β, D), (γ, A), (δ, B)}. Felmer¨ ul a k´erd´es, tudunk-e valami k¨ozelebbit mondani a stabil p´aros´ıt´ asok szerkezet´er˝ ol, ¨ osszehasonl´ıthat´ok-e stb. Vegy¨ unk k´et stabil p´aros´ıt´ast, M1 -et ´es M2 -˝ ot. Az M1 f´erfi szempontb´ ol jobb, mint M2 , ha minden f´erfi legal´ abb olyan j´ o p´ art kap M1 -ben, mint M2 -ben; jel¨ol´esben M1 ≥F M2 . Nem lehet b´ armely k´et stabil p´aros´ıt´ast ¨osszehasonl´ıtani, de az ¨osszes stabil p´ aros´ıt´ as, mint azt J. H. Conway megmutatta, u ´n. disztribut´ıv vagy m´as 7 sz´ oval geometriai h´ al´ ot alkot. Speci´ alisan van legnagyobb ´es legkisebb eleme. (Ha a n˝ok szempontj´ab´ol n´ezz¨ uk, ugyanazt a h´ al´ ot kapjuk, csak megford´ıtva. Azaz ami az egyik nemnek a legjobb, a m´ asiknak a legrosszabb.) Ez ut´obbit egyszer˝ uen bel´athatjuk. 7
Egy L h´ al´ o, ha van k´et k´etv´ altoz´ os m˝ uvelete, ∨ ´es ∧, ´es ezek idempotensek x ∨ x = x, x∧x = x, kommutat´ıtvak, x∨y = y ∨x, x∧y = y ∧x, asszociat´ıvak, x∨(y ∨z) = (x∨y)∨z, x ∧ (y ∧ z) = (x ∧ y) ∧ z ´es elnyel˝ ok, azaz x ∨ (x ∧ y) = x ´es x ∧ (x ∨ y) = x minden x, y, z ∈ L eset´en. Disztribut´ıv a h´ al´ o, ha teljes¨ ul m´eg az x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) egyenl˝ os´eg is.
48
P´ elda: Az els˝ o p´eld´ aban szerepl˝o stabil p´aros´ıt´asok az al´abbi h´al´ot alkotj´ak: M1 r
Az M1 -ben j´ arnak legjobban a f´erfiak.
M3 r
Az M3 a f´erfiaknak jobb, mint M2 ´es a n˝oknek jobb, mint M1 .
M2 r
Az M2 -ben j´ arnak legjobban a n˝ok.
Egy A h¨ olgy lehets´eges az α f´erfi sz´am´ara, ha van olyan M stabil p´aros´ıt´as, amelyre (α, A) ∈ M . T´ etel 15 Az el˝ oz˝ o algoritmus minden f´erfinek a legjobb lehets´eges p´ art adja, m´ıg minden n˝ onek a legrosszabbat. Bizony´ıt´ as. Az els˝ o´ all´ıt´ ast a l´ep´esek szerinti indukci´oval l´atjuk be. Tegy¨ uk fel, hogy a soron k¨ ovetkez˝ o l´ep´esig egyetlen f´erfit sem utas´ıtott el olyan n˝o, aki lehets´eges lett volna sz´ am´ara. Tegy¨ uk fel tov´abb´a, hogy ebben a l´ep´esben A elutas´ıtja α-t. Azt ´ all´ıtjuk, hogy ekkor A nem lehets´eges α sz´am´ara. Val´ oban, ha A pillanatnyi p´arja β, akkor β prefer´alja A-t az ¨osszes n˝oh¨oz k´epest, kiv´eve akik kor´ abban visszautas´ıtott´ak. Ezek azonban, az indukci´os felt´etel miatt, nem lehets´egesek β sz´am´ara. Ha teh´at l´etezne egy olyan M stabil p´ aros´ıt´ as, amelyre (α, A) ∈ M , ebben β a p´arj´at (nevezz¨ uk B-nek) kev´esb´e kedveln´e, mint A-t, hiszen mind A ´es B lehets´eges β sz´am´ara. Ekkor viszont az (α, A), (β, B) instabilit´ast okoz, azaz A nem lehets´eges α sz´am´ara, s ezzel bel´ attuk a t´etel els˝ o fel´et. Legyen M ∗ az algoritmusunk ´altal adott f´erfi optim´ alis megold´asa, M pedig egy tetsz˝ oleges stabil p´aros´ıt´as. Bel´atjuk, hogy b´armely A n˝o eset´en az ˝ o M -beli p´ arja nem rosszabb, mint az M ∗ -beli p´arja. (Igaz´ab´ol pontosan akkor nem rosszabb, ha ugyanaz a p´arja a k´et p´aros´ıt´asban, ´es hat´arozottan jobb, ha nem.) Ha (α, A) ∈ M ∗ , (β, A) ∈ M ´es α 6= β, akkor (α, B) ∈ M valamely B 6= A h¨ olgyre. A t´etel els˝o fele miatt persze α prefer´alja A-t Bhez k´epest. M´ asr´eszt az M p´aros´ıt´as stabil, ´ıgy speci´alisan az (α, B), (β, A) p´ arok stabilit´ asa az jelenti, hogy A prefer´alja β-t α-hoz k´epest; s pont ezt akartuk bizony´ıtani. 2 Megjegyz´ esek: Az algoritmus eredeti felhaszn´al´as´an´al a k´orh´azak tett´ek az aj´ anlatokat, ´es azt hangoztatt´ak (term´eszetesen bizony´ıt´as n´elk¨ ul), hogy ez az orvosok jav´ ara v´ alik. Sz´amos tanuls´ag vonhat´o itt le, s ezekb˝ol csak az 49
egyik, hogy nem ´ art meggondolni nyilv´anval´onak t˝ un˝o (vagy annak be´all´ıtott) ´all´ıt´ asokat, mint azt Gale ´es Shapley tett´ek volt. A m´ asik, hasonl´ oan fontos ´eszrev´etel a d¨ont´esi helyzetek illetve strat´egi´ak buktat´ oira vonatkozik. A modell azt sugallja, “el´ebe kell menni” az esem´enyeknek ´es kishit˝ us´eg n´elk¨ ul megpr´ob´alni a legjobbnak t˝ un˝o megold´asokat a “s¨ ult galambra v´ ar´ as” helyett. A stabil p´ aros´ıt´ as mint mag Kor´ abban defini´ altuk egy ir´any´ıtott G gr´af magj´at; ez egy olyan S ⊂ V (G) halmaz volt, amely f¨ uggetlen ´es domin´al´o egyben. Ez a fogalom k¨ ul¨ on¨ osen fontos a j´ at´ekelm´eletben, hisz a megold´asok stabilit´as´at fogalmazza meg matematikai form´aban. A stabil p´aros´ıt´as motiv´alhatja ezt a defin´ıci´ ot, ugyanis egy r¨ ogz´ıtett probl´ema stabil p´aros´ıt´asai tulajdonk´eppen magok egy megfelel˝ oen alkotott gr´afban. Defini´ aljuk egy G gr´ af vonalgr´ afj´ at, L(G)-t, a k¨ovetkez˝ok´eppen: L(G) pontjai G ´elei lesznek, azaz V (L(G)) := E(G), ´es L(G) k´et pontja, e ´es f , k¨ oz¨ ott van ´el, ha G-ben tekintve az e ´es f ´eleknek van k¨oz¨os pontja. Ha G pontjaihoz preferencia list´ ak vannak rendelve, ir´any´ıtsuk az (e, f ) ´elt L(G)ben u ´gy, hogy az a prefer´ alt pontb´ol indul ´es a kev´esb´e kedvelt pontra mutat k¨ oz¨ os ponthoz tartoz´ o lista szerint. ´ ıt´ All´ as: A fenti defin´ıci´ okkal a G gr´af stabil p´aros´ıt´asai ´eppen az L(G) gr´af magjainak felelnek meg. P´ elda: Az els˝ o p´elda G gr´ afj´ahoz tartoz´o L(G): (α,r B)
(α, A) r
z
j
r(α, C)
9
(γ, C) r
U i
N
r (β, C)
? 6 r
K
W
(γ, B)
z ] r (γ, A)
i
50
r (β, A)
*
r (β, B)
8. el˝oad´as
4
Sztochasztikus Programoz´ as
Az optim´ alis ´es d¨ ont´esi modellekben sz´amos, a v´eletlent˝ol f¨ ugg˝o v´altoz´o szerepelhet. Illusztr´ aci´ ok´eppen n´eh´any p´elda: 1. Di´eta probl´ema A probl´em´ at a min
cx Ax ≥ b x ≥ 0
alakban modellezt¨ uk, ahol az x vektor komponensei a k¨ ul¨onb¨oz˝o t´apl´ al´ekok fogyasztand´ o mennyis´eg´et a c komponensei ezek egys´eg´ar´at, az A m´ atrix aij eleme a j-edik t´apl´al´ek egys´egnyi mennyis´eg´enek iedik t´ ap´ert´eke (energia, feh´erje, k¨ ul¨onb¨oz˝o ´asv´anyi anyag, vitamin, stb.), m´ıg a bi az ig´enyelt t´ap´ert´ek. A val´os´agban az A, b ´es c egyes kompenensei lehetnek val´osz´ın˝ us´egi v´altoz´ok, melyeknek eloszl´as´ar´ol t¨ obb-kevesebb inform´ aci´onk van. 2. Portfoli´ o probl´ema Tegy¨ uk fel, hogy n k¨ ul¨onb¨oz˝o tev´ekenys´egbe/r´eszv´enybe fektethet¨ unk be x1 , x2 , . . . , xn t˝ ok´et, ´es ξ1 , ξ2 , . . . , ξn az egys´egnyi t˝oke v´eletlent˝ol f¨ ugg˝ o hozama az adott befektet´es mellett. Feltehetj¨ uk tov´abb´a, hogy Pn Pn x = 1, x ≥ 0, ´ e s a nyeres´ e g¨ u nk ξ x . i i=1 i i=1 i i 3. G´ atmagas´ıt´ as Egy g´ at x egs´egnyivel t¨ort´en˝o magas´ıt´as´anak a k¨olts´eg´et jel¨olj¨ uk I(x)szel, tov´ abb´ a annak a val´osz´ın˝ us´eg´et, hogy a v´ızszint t´ ull´epi H-t P (H)val. Ha a v´ızszint magasabb, mint a g´at, akkor az ´arad´as k¨ovetkezt´eben V k´ ar keletkezik. ´ ag´ 4. Ujs´ arus probl´ema Ez egy klasszikus beruh´az´asi probl´ema. A kereslet egy u ´js´agra (esetleg kar´ acsonyf´ ara) egy ismert eloszl´as ξ val´osz´ın˝ us´egi v´altoz´o. Az u ´js´agos c egys´eg p´enz´ert veszi ´es (d > c) egys´eg´ert adja el. Ha x darabot vesz, akkor ξ ≤ x eset´en dξ − cx = −c(x − ξ) + (d − c)ξ, 51
m´ıg ξ > x dx − cx = −(d − c)(ξ − x) + (d − c)ξ lesz a haszna. Sz´ and´ekosan nem feszegett¨ uk, mi is a c´el a felsorolt modellekben. L´atni fogjuk, hogy ezt igen alaposan meg kell fontolni ´es nem mindig hat´arozhat´o meg egy´ertelm˝ uen. A di´eta probl´em´ ar´ ol azt l´athatjuk, hogy esetleg b´armekkora r´aford´ıt´as mellett sem el´eg´ıthet˝ o ki egy val´osz´ın˝ us´eggel az Ax ≥ b felt´etel. Szerencs´es esetben meg tudjuk becs¨ ulni a felt´etel s´er¨ ul´es´eb˝ol sz´armaz´o k´art, ´es ezt hozz´ aadva a cx c´elf¨ uggv´enyhez ´athidalhat´o ez a probl´ema. A m´ asik megk¨ ozel´ıt´es, hogy az Ax ≥ b teljes¨ ul´es´et egy el˝ore megadott, lehet˝ oleg nagy p val´ osz´ın˝ us´eggel k¨ovetelj¨ uk meg. Ez a p a rendszer¨ unk megb´ızhat´ os´ agi szintje, amely f¨ ugghet p´eld´aul a m˝ uszaki szabv´anyokt´ol.8 Bizonyos esetekben a val´osz´ın˝ us´egi v´altoz´ok helyettes´ıt´ese a v´arhat´o ´ert´ek¨ ukkel elfogadhat´ o megold´ashoz vezet. Tulajdonk´eppen ´ıgy j´artunk el a kor´ abbiakban. N´ezz¨ uk meg e helyett egy m´as ¨otletet ´es a hollandiai g´ atmagas´ıt´ as probl´em´ aj´ at, amelyet van Dantzig vizsg´alt 1956-ban. G´ atmagas´ıt´ as ´ es a Bernoulli elv A Bernoulli elv szerint egy sztochasztikus rendszerben defini´alunk egy hasznoss´ agi f¨ uggv´enyt ´es ennek v´arhat´o ´ert´ek´et maximaliz´aljuk. (Ekvivalensen kock´ azat f¨ uggv´enyt ´es ennek v´arhat´o ´ert´ek´et minimaliz´aljuk.) Jelen esetben a kock´ azati f¨ uggv´eny nem m´as, mint a k¨olts´eg. Legyen H0 a g´ at jelenlegi, H az elegend˝o magass´aga; ezzel az x magas´ıt´as x = H − H0 . Nincs k´ ar, ha a tengerszint H alatt marad, k¨ ul¨onben az ´arad´as okozta k´ar V . A statisztik´ akb´ ol ismerj¨ uk a tengerszint eloszl´as f¨ uggv´eny´et. Ennek alapj´an annak az esem´enynek a p(H) val´osz´ın˝ us´ege, hogy egy ´even bel¨ ul meghaladja a H magass´ agot p(H) = p0 e−α(H−H0 ) , p0 = e−αH0 , 8
Term´eszetesen a di´eta probl´ema alkalmas lehet er˝ om˝ uvek, energiaszolg´ altat´ o rendszerek, v´ızgazd´ alkod´ asi probl´em´ ak stb. modellez´es´ere. Mindazon´ altal ezek a probl´em´ ak matematikai szempontb´ ol nagyon neh´ezek. B´ ar t¨ obb fontos speci´ alis esetben hat´ekonyan megoldhat´ o, de ezekkel itt nem foglalkozhatunk.
52
ahol p0 a H0 szint meghalad´as´anak val´osz´ın˝ us´ege, α pedig egy pozit´ıv konstans. Legyen I(x) a g´ at x-szel t¨ ort´en˝o emel´es´enek teljes k¨olts´ege, ´es tegy¨ uk fel, hogy ez I(x) = 0 ha x=0, m´ıg, I0 +kx, ha x > 0, ahol I0 ´es k pozit´ıv konstansok. (Az I0 interpret´ alhat´ o felvonul´asi k¨olts´egk´ent, az ´ep´ıt´es k¨olts´ege pedig line´ aris f¨ uggv´enye a magas´ıt´asnak.) A jelenlegi k¨olts´eg v´arhat´o ´ert´ek´enek kisz´ am´ıt´ as´ an´ al k´et dolgot kell figyelembe venn¨ unk: (i) az I(H − H0 ) determinisztikus ´ep´ıt´esi k¨olts´eget (ii) az 1., 2., . . . ´evekben bek¨ovetkez˝o esetleges k´ar ´altal okozott k¨olts´egeknek a jelenre visszavet´ıtett k¨olts´eg´et. Mivel ez ut´obbi a j-edik ´evben p(H)V (1 + 0, 01δ)−j , ahol δ az ´ alland´ onak felt´etelezett kamatl´ab, az ¨osszeg: I(H − H0 ) + p(H)V
∞ X
(1 + 0, 01δ)−j ≈ I(x) + 100p(H)V /δ.
j=1
A minimum meghat´ aroz´as´ahoz vegy¨ uk a d (I(x) + 100p0 e−αx V /δ) = 0 dx egyenlet gy¨ ok´et, amely a x =
1 α
log 100pδk0 V α megold´ast adja.
A portfoli´ o probl´ ema Mint eml´ıtett¨ uk, az x1 + x2 + . . . + xn = 1, xi ≥ 0 felt´etelek mellett keres¨ unk Pn megold´ ast, a nyeres´eg¨ unk pedig a v´eletlent˝ol f¨ ugg˝o i=1 ξi xi ¨osszeg. Ha helyettes´ıten´enk9 a ξi -t a µi = E(ξi ) v´arhat´o ´ert´ek´evel, egy trivi´alis h´atizs´ak feladathoz jutn´ ank: max
n P
µi x i
i=1
n P
xi = 1 (∗)
i=1
xi ≥ 0 9
Ez a Bernoulli elv alkalmaz´ asa lenne jelen esetben.
53
Ha µ1 ≥ µ2 ≥ . . . ≥ µn , akkor a (∗) optim´alis megold´asa x∗1 = 1, x∗i = 0, ha 1 < i ≤ n. K¨ onnyen l´athat´o azonban, hogy ´altal´aban, ha ism´etelj¨ uk ezt a strat´egi´ at, az egy val´ osz´ın˝ us´eggel cs˝odh¨oz vezet. Sokf´ele pr´ob´alkoz´as t¨ ort´ent elfogadhat´ o megold´ as keres´es´ere, amely egyszerre ´ıg´er j´o befektet´est ´es v´edelmet a cs˝ od ellen. Ezekb˝ ol k´et megk¨ ozel´ıt´est v´azolunk. Ha feltehet˝o, hogy a ξ j = (ξ1j , . . . , ξnj ) vektorok f¨ uggetlenek ´es azonos eloszl´as´ uak, ahol ξij az i-edik val´osz´ın˝ us´egi v´ altoz´ o j-edik ´evben felvett ´ert´eke, akkor egy nagyon egyszer˝ u szab´aly ad´odik. P P Nem az E( ni=1 ξi xi ) = nj=1 µj xj v´arhat´o ´ert´eket kell kell maximaliz´alni, P hanem a nyeres´eg logaritmus´anak v´arhat´o ´ert´ek´et, az E(log( ni=1 ξi xi ))-et. (A bizony´ıt´ ast, mely az u ´n. marting´ al konvergencia t´etelen alapul, mell˝ozz¨ uk.) Sajnos amilyen eleg´ ans ez a megold´as, annyira t´amadhat´o is: a befektet´esek nyeres´eg´enek f¨ uggetlens´eg´enek ´es az azonos eloszl´as´anak felt´etelez´ese irre´ alis a gyakorlatban. Valamint a m´odszer nem haszn´alja ki, hogy tov´abbi statisztik´ ak nyerhet˝ ok a ξ1 , . . . , ξn v´altoz´okb´ol. Ezenk´ıv¨ ul csak hat´ar´ert´ekben optim´ alis, ´es nem tudjuk mennyire v´ed a cs˝od ellen. Orvosolhatjuk ezeket a bajokat Markowitz u ´n. hat´ekony portfoli´ oit haszn´ alva.10 Tegy¨ uk fel, hogy nemcsak a ξ1 , . . . , ξn v´altoz´ok µi = E(ξi ) v´arhat´o ´ert´ekei, hanem a v´ altoz´ ok C kovariancia m´atrixa is rendelkez´esre ´all, ahol cij = E[(ξi − µi )(ξj − µj )]. Ennek seg´ıts´eg´evel kifejezhetj¨ uk egy x = (x1 , x2 , . . . , xn ) portfoli´o (megold´as) varianci´ aj´ at n X
V ar(
i=1
n X
ξi xi ) = E[(
(ξi − µi )xi )2 ] = xT Cx.
i=1
P
Egy x portfoli´ o hat´ekony, ha v´arhat´o hozama, E[ i ξi xi ], nem n¨ovelhet˝o a variancia n¨ ovel´ese n´elk¨ ul, ´es varianci´aja nem cs¨okkenthet˝o a v´arhat´o hozam cs¨ okkent´ese n´elk¨ ul. A hat´ekony portfoli´o teh´at egyfajta optimum: adott nyeres´eget felt´etelezve a minim´ alis kock´azattal j´ar, illetve egy r¨ogz´ıtett kock´azati szint mellett maxim´ alis nyeres´eget ig´er. Ha ρ > 1 hozam el´er´ese a c´elunk, 10
Ezeket Markowitz 1952-ben kezdte vizsg´ alni, ´es 1990-ben k¨ ozgazdas´ agi Nobel-d´ıjjal ismert´ek el az eredm´enyeit.
54
akkor a k¨ ovetkez˝ ou ´n. kvadratikus programoz´ asi probl´ema megold´asa a v´alasz. xT Cx
min
n P
µj x j
≥ ρ
j=1
n P
xj
= 1
xj
≥ 0 j = 1, . . . , n.
j=1
A feladat egy x∗ megold´ as´ at optim´ alis portfoli´ onak nevezz¨ uk. Nyilv´anval´oan egy optim´ alis portfoli´ o egyben hat´ekony portfoli´o is. Megjegyz´ esek: A feladat c´elf¨ uggv´enye ebben az esetben az ismeretlenek P Pn u, azaz nem lesz kvadratikus (n´egyzetes) f¨ uggv´enye, m i=1 j=1 cij xj xi alak´ line´ aris. Ezeknek a megold´ as´aval nem foglalkozhatunk, de utalunk r´a, hogy sz´ amos hat´ekony algoritmust fejlesztettek ki, melyek a kvadratikus programoz´ asi feladatok megold´ as´ara is alkalmasak. A m´asik felmer¨ ul˝o neh´ezs´eg a szimmetrikus C m´ atrix n(n + 1)/2 elem´enek kisz´am´ıt´asa. (Ezeket term´eszetesen a kor´ abbi megfigyel´esekb˝ol kell meghat´aroznunk.) Mindk´et neh´ezs´eget ´ athidalhatjuk, ha a kovariancia minimaliz´al´asa helyett megel´egsz¨ unk P az ´ atlagos abszol´ ut elt´er´es E[| j (ξj −µj )xj |] mennyis´eg minimaliz´al´as´aval.11 A Konno-Yamazaki-f´ ele MAD modell Konno ´es Yamazaki 1990-ben javasolt m´odszere ´ıgy j´ar el, valamint a µi v´ arhat´ o ´ert´ekek ´es cij kovariancia egy¨ utthat´ok kisz´am´ıt´as´at elker¨ uli; k¨ ozvetlen¨ ul haszn´ alja a megfigyelt adatokat. (Az ´atlagos abszol´ ut elt´er´es angol neve ut´ an, mean absolute deviation, a modell neve MAD.) Ha T megfigyel´est v´egezt¨ unk a m´ ultban, rjt jel¨oli a j-edik befektet´es hozam´ at a t-edik megfigyel´esn´el ´es rj =
T 1X rjt , ajt = rjt − rj , T t=1
akkor a portfoli´ o optimaliz´ al´as a k¨ovetkez˝o alakban ´ırhat´o fel: 11
Val´ oj´ aban a legfontosabb esetben, a t¨ obbv´ altoz´ os norm´ alis eloszl´ as eset´eben, a k´et m´ odszer ekvivalens.
55
min
1 T
T P P n
|
j=1 ajt xj |
t=1 n P
(∗)
≥ ρ
rj xj
j=1 n P
xj
= 1
i=1
≥ 0 j = 1, . . . , n.
xj
A (∗) probl´ema nem LP, de hasonl´oan a m´atrixj´at´ekokn´al alkalmazott gondolathoz LP feladatra reduk´alhat´o: min
−yt ≤
1 T
T P
yt
t=1
n P
ajt xt ≤ yt t = 1, . . . , T
j=1 n P
rj xj j=1 n P xj i=1
≥
ρ (∗∗)
=
1
xj
≥
0 j = 1, . . . , n.
Ezzel a modellel lehet˝ ov´e v´ alik eg´eszen nagy, val´o ´eletbeli probl´em´ak megold´ asa. Nem szabad elfelejten¨ unk azonban, hogy a kapott megold´as csak egy javaslat: egy t´enyleges portfoli´o kiv´alaszt´as´an´al sz´amtalan egy´eb szempont is figyelembe vehet˝ o. A szemi-MAD modell ´ Erdemes meggondolnunk a MAD modellt, ´es egy kicsit v´altoztatni rajta. P ult) v´arhat´o hozamt´ol Id´ezz¨ uk fel, hogy a nj=1 ajt xj kifejez´es adja a (becs¨ val´ o el˝ ojeles elt´er´est a j-edik id˝opontban. K´ezenfekv˝o, hogy ne ezek abszol´ ut ´ert´ekeinek ¨ osszeg´et minimaliz´aljuk, hanem csak azon tagoknak az abszol´ ut ´ert´ek ¨ osszeg´et, amelyek negat´ıvak. (Val´oban, hiszen ha v´arhat´o hozam becsl´es´en´el jobban teljes´ıt a a j-edik id˝opontban a portf´oli´o, az nem kellemetlen, hanem ´eppen kedvez˝o esem´eny.) Bevezetve az |x|− := x, ha x ≤ 0 ´es |x|− := 0, ha x > 0 jel¨ol´est, a probl´ema a k¨ovetkez˝o alakot ¨olti:
56
max
1 T
T P P n
− j=1 ajt xj |
|
t=1 n P
≥ ρ
rj xj
j=1 n P
xj
= 1
i=1
≥ 0 j = 1, . . . , n.
xj
Ennek a probl´em´ nak az LP alakja k¨onnyen megadhat´o, ´es a MAD modelln´el is egyszer˝ ubb: max
1 T
T P
yt
t=1
n P j=1 n P
ajt xt ≥ yt t = 1, . . . , T
rj xj j=1 n P xj i=1
≥
ρ
=
1
yt ≤ xj ≥
0 t = 1, . . . , T 0 j = 1, . . . , n.
Megjegyz´ es: A MAD ´es a szemi-MAD m´odszerek nagyj´ab´ol ekivivalensek, ha az optim´ alis portf´ oli´ ok hozamainak eloszl´asa megk¨ozel´ıt˝oen szimmetrikus. Ez nem sz¨ uks´egk´eppen ´ all fenn, ´ıgy a jelen vizsg´alatok szerint hasznosabbnak t˝ unik a szemi-MAD modell haszn´alata, hiszen a v´arhat´o sz´am´ıt´asi ideje mindenk´eppen kisebb.
57
9. el˝oad´as A k¨ ovetkez˝ okben n´eh´ any speci´alis optimaliz´al´asi illetve megb´ızhat´os´agi feladatot vizsg´ alunk. K¨ oz¨ os tulajdons´aguk csup´an a v´eletlen esem´enyekt˝ol val´ o f¨ ugg´es lesz majd. Az u ´ js´ ag´ arus probl´ ema Amint m´ ar kor´ abban defini´altuk egy u ´js´agos c egys´eg p´enz´ert veszi ´es (d > c) egys´eg´ert ad el egy u ´js´agot. Ha x darabot vesz, akkor ξ ≤ x eset´en dξ − cx = −c(x − ξ) + (d − c)ξ, m´ıg ha ξ > x dx − cx = −(d − c)(ξ − x) + (d − c)ξ lesz a haszna. Term´eszetesen csak akkor v´arhat´o ´ertelmes v´alasz, ha van valamilyen felt´etelez´es¨ unk a kereslet eloszl´as´ar´ol. Legyen ez az eloszl´as el˝ osz¨ or diszkr´et, ´es jel¨ olj¨ uk a ξ = i esem´eny val´osz´ın˝ us´eg´et pi -vel, azaz P r(ξ = i) = pi . A v´ arhat´ o haszon ´ıgy a k¨ovetkez˝o lesz: (d − c)Eξ −
X
c(x − i)pi −
X
(d − c)(i − x)pi ,
i>x
i<x
amely akkor maxim´ alis, ha a X i<x
c(x − i)pi +
X
(d − c)(i − x)pi
i>x
¨osszeg minim´ alis. Ez ´ertelmezhet˝o u ´gy, mint egy v´arhat´o b¨ untet´es, ha a ξ aktu´ alis ´ert´eke elt´er x-t˝ ol; c egys´eget kell fizetni a ξ < x ´es d − c egys´eget az x < ξ esetben. Az els˝o esetben az eladatlan u ´js´ag ´ara jelenik meg, a m´ asodikban az elszalasztott lehet˝os´eget kell “megfizetni.” Pszichikailag a k´et k¨ olts´eg k¨ oz¨ ott nagy k¨ ul¨onbs´eg lehet, az optimaliz´al´as szempontj´ab´ol ellenben semmi. Ennek megfelel˝oen egy d¨ont´es lehet˝oleg az ut´obbi alapj´an hozand´ o. Ha a v´eletlen ig´eny folytonos eloszl´ast k¨ovet, amelynek s˝ ur˝ us´egf¨ uggv´enye f , akkor az x v´ altoz´ ot is c´elszer˝ u folytonosnak tekinteni. Ekkor, az el˝oz˝ovel anal´ og m´ odon, a minimaliz´ aland´o kifejez´es¨ unk Z x
g(x) = c
(x − z)f (z)dz + (d − c)
−∞
Z ∞ x
A sz´ amol´ as kedv´e´ert ´ at´ırva a g(x) f¨ uggv´enyt
58
(z − x)f (z)dz.
Z x
(x − z)f (z)dz + c
g(x) = c −∞
Z ∞
(x − z)f (z)dz + d
Z ∞
Z ∞
zf (z)dz − dx
−∞
−∞
(z − x)f (z)dz =
x
x
f (z)dz − c
= cx
Z ∞
Z ∞
Z ∞
zf (z)dz.
f (z)dz + d x
x
Ezt x szerint deriv´ alva kapjuk 0
g (x) = c − d
Z ∞
f (z)dz + dxf (x) − dxf (x) = d(F (x) − 1) + c,
x x ahol F (x) = −∞ f (z)dz, a ξ v´altoz´o eloszl´as f¨ uggv´enye. A g f¨ uggv´eny minimum helye a g 0 (x) = 0 egyenlet megold´as´aval kaphat´o meg, mely az x0 = F −1 ((d − c)/d) ´ert´eket adja az el˝obbiek szerint.
R
P´ elda: Legyen egy u ´js´ ag kiskereskedelmi ´ara c = 50, az elad´asi ´ara pedig d = 70. A megfigyel´esek szerint egy el´arus´ıt´o helyen a ξ kereslet egyenletes eloszl´ ast k¨ ovet 40 ´es 60 k¨ oz¨ ott. (Az egyszer˝ us´eg kedv´e´ert folytonos modellel sz´ amolunk, b´ ar k¨ onnyen l´ athat´o, hogy a diszkr´et modell most ugyanezt az ´ert´eket adja.) ´Igy az eloszl´ as f¨ uggv´eny F (z) = P r(ξ < z),
F (z) =
0
ha − ∞ < z ≤ 40 z/20 − 2 ha 40 < z ≤ 60 1 ha 60 < z < ∞.
Az F a (40, 60) intervallumon invert´alhat´o, ´es F −1 (z) = 20z + 40. Ezzel − c)/d) = F −1 (2/7) = 45 eg´esz ´es 5/7, azaz durv´an 46 u ´js´agot c´elszer˝ u rendelni, mellyel a v´arhat´o nyeres´eg
F −1 ((d
(d − c)E − c
Z x
(x − z)f (z)dz − (d − c)
Z ∞
−∞
Z 60
20 40
z/20dz − 50
(z − x)f (z)dz =
x
Z 46
(46 − z)/20dz − 20
Z 60
(z − 46)/20dz =
46
40
= 1000 − 45 − 98 = 857. P´ elda: Legyen most d = 3, c = 2 ´es a ξ kereslet k¨ovessen λ param´eter˝ u 12 Poisson eloszl´ ast. Ekkor az optim´alis x ´ert´ek meghat´aroz´as´an´al minimaliz´ aland´ o 12
A Poisson eloszl´ as nagyon sok v´eletlen folyamatban, pl. bolyong´ asok ill. telefonh´ıv´ asok stb. felbukkan, ´ıgy sokkal term´eszetesebb a felt´etelez´ese ebben az esetben, mint az egyenletes eloszl´ asnak.
59
X
c(x − i)pi +
i<x
X
(d − c)(i − x)pi
i>x
a k¨ ovetkez˝ o alakot ¨ olti f (x) :=
X
2(x − i)
i<x
λi e−λ X λi e−λ + (i − x) . i! i! i>x
Tekints¨ uk x-et folytonos v´ altoz´onak; ekkor f -et “differenci´alva” a X λi e−λ X λi e−λ d f (x) ≈ 2 − =0 dx i! i! i<x i>x
egyenlet gy¨ ok´et kell megkeresn¨ unk. Minden diszkr´et eloszl´asra P∞ i −λ ´ıgy speci´ alisan i=0 λ e /i! = 1, azaz X λi e−λ
2
i<x
i!
=2−2
x −λ λ e
x!
−
X λi e−λ i>x
i!
P
i pi
= 1,
.
Vegy¨ uk ´eszre, hogy i>x λi e−λ /i! sokkal kisebb, mint λx e−λ /x!, ha x nem t´ ul kicsi λ-hoz k´epest, ´ıgy az egyenlet nagyj´ab´ol √ λx e−λ 2πx(eλ)x e−λ 0=1− ≈1− , x! xx √ ahol az n! ≈ ( 2πn)(n/e)n k¨ozel´ıt´est, azaz a Stirling formul´at haszn´altuk. Ezzel x √ eλ = 2πxeλ , x P
amelynek e alap´ u logaritmus´at v´eve x(log λ + 1) − x log x = λ +
1 log(2πx). 2
Ha λ ´es x k¨ ozel van egym´ ashoz, akkor log λ ≈ log x, melyet az el˝oz˝o egyenletbe ´ırva az x∗ = λ + log λ +
1 log(2π) ≈ λ + log λ + 1 2
megold´ as ad´ odik. H´ al´ ozati megb´ızhat´ os´ ag
60
Egy kor´ abban t´ argyalt modellhez hasonl´oan adott egy ir´any´ıtatlan G gr´ af az s ´es t kit¨ untetett pontokkal, tov´abb´a G ´eleihez val´osz´ın˝ us´egeket ren´ del¨ unk. Ertelmez´ es¨ unk szerint egy ´elhez rendelt sz´am az ´el j´arhat´os´ag´anak (tkp. l´etez´es´enek) a val´ osz´ın˝ us´ege, ´es az ´elek l´etez´esei f¨ uggetlen esem´enyek. L´ attuk, hogy ekkor p´eld´ aul a legnagyobb val´osz´ın˝ us´eggel l´etez˝o s − t u ´t keres´ese a legr¨ ovidebb u ´t probl´em´ara vezethet˝o vissza. Sokkal nehezebb probl´ema kisz´amolni azt, milyen val´osz´ın˝ us´eggel juthatunk el s-b˝ ol t-be. Ez olyannyira neh´ez, hogy hat´ekony algoritmus nem ismert r´ a ez id˝ o szerint, mi t¨obb, nem is rem´elt. Ez ann´al ink´abb szomor´ u, mert a probl´ema kezelhet˝ os´ege lenne az el˝ofelt´etele olyan d¨ont´esek vizsg´alat´ ahoz, hogy melyik ´el val´ osz´ın˝ us´eg´et ´erdemes n¨ovelni ´es mennyivel, vagy ´eppen mit okozna a hi´ anya. Nem t´ ul nagy feladatok azonban megoldhat´ok a lehets´eges esetek megfelel˝ o csoportos´ıt´as´aval. A gondolat egy rekurz´ıv algoritmus, amely az adatok sz´ am´anak f¨ uggv´eny´eben exponenci´ alis id˝ot ig´enyel. Legyen G a kiindul´ asi gr´af ´es v´alasszunk ki egy e ∈ E(G) ´elt, melynek val´ osz´ın˝ us´eg´et jel¨ olj¨ uk p(e)-vel. Jel¨olje tov´abb´a G \ e ´es G/e rendre azokat a gr´ afokat amelyekb˝ ol elhagytuk az e ´elt, illetve ahol az e ´el k´et v´egpontj´at egybeejtj¨ uk, azaz ¨ osszeh´ uzzuk e-t. Ekkor P r(G)-vel jel¨olve az s − t el´erhet˝os´eg val´ osz´ın˝ us´eg´et P r(G) = (1 − p(e))P r(G \ e) + p(e)P r(G/e), ´es ´ıgy az eredeti feladatot k´et kisebb probl´em´ara vezett¨ uk vissza. P´ elda:
r 0, 5
s
r
r @ 0, 8 0, 9 @r t
0, 8
0, 8
r
0, 5
0, 5
0, 9×
rH 0, 8 HH
0, 5×
Hr
r 0, 8 r
0, 8
@ 0, 1× @@ R 0, 5 r
0, 8
0, 8
r
r 0, 96
r 0, 864 0, 9
r
0, 5
r @ 0, 8 @r r
@ 0, 5× R @
r 0, 8 HHr 0, 9 r 0, 576 r0, 8
-
0, 501
@
0, 5
Vegy¨ uk ´eszre, hogy egy p´arhuzamos ´elp´ar, melyeknek val´osz´ın˝ us´ege p1 ´es p2 , helyettes´ıthet˝ o egy p1 + p2 − p1 p2 val´osz´ın˝ us´eg˝ u ´ellel. Az als´o ´ag kisz´ amol´ asa hason´ oan megy, illetve ha olyan r´eszgr´afra jutunk, amit m´ar kisz´ amoltunk, az felhaszn´ alhat´o. ´Igy P r(G) = 0, 72 × 0, 9 + 0, 501 × 0, 1 = ¨ 0, 6981. Osszehasonl´ ıtva ezt a legnagyobb val´osz´ın˝ us´eg˝ uu ´ttal l´athat´o, hogy m´ıg az csak 0, 516 val´ osz´ın˝ us´eg˝ u, az ¨osszef¨ ugg˝os´egre enn´el sokkal nagyobb az es´ely. 61
F¨ uggetlen alkatr´ eszek megb´ızhat´ os´ aga Tegy¨ uk fel, hogy egy n alkatr´eszb˝ol ´all´o szerkezet m˝ uk¨od´es´ehez mindnek a m˝ uk¨ od´ese sz¨ uks´eges, ´es ezek egym´ast´ol f¨ uggetlen¨ ul mennek t¨onkre. A szerkezet meg´ep´ıt´es´en´el az i-edik alkatr´eszre k´et k¨ ul¨onb¨oz˝o megb´ızhat´os´ag´ u ´es ´ ar´ u v´ alaszt´ asi lehet˝ os´eg¨ unk van: egy qi val´osz´ın˝ us´eggel m˝ uk¨od˝o, si ´ar´ u ´es egy pi val´ osz´ın˝ us´eggel m˝ uk¨ od˝o, ri ´ar´ u, ahol qi < pi ´es si < ri , 1 ≤ i ≤ n. A m˝ uszaki el˝ o´ır´ as szerint a szerkezetnek p val´osz´ın˝ us´eggel m˝ uk¨odnie kell. A c´el az alkatr´eszek olyan kiv´alaszt´asa, amely a szabv´anynak megfelel ´es minim´ alis k¨ olts´eg˝ u. Haszn´ aljuk az xi ∈ {0, 1} v´altoz´ot a modellben a qi , ekkor xi = 0, illetve a pi , ekkor xi = 1, val´osz´ın˝ us´eggel m˝ uk¨od˝o alkatr´esz alkalmaz´as´anak k´ odol´ as´ ara. Ekkor a m˝ uk¨ od´esi val´osz´ın˝ us´eg pontosan n Y
n xi Y pi
qi
i=1
qi
i=1
lesz, m´ıg a k¨ olts´eg n X
ci xi +
n X
si ,
i=1
i=1
ha ci := ri − si , 1 ≤ i ≤ n eset´en. A c´el teh´at a n X
min
ci xi
i=1 n Y i=1
qi
n xi Y pi i=1
qi
≥p
xi ∈ {0, 1}, 1 ≤ i ≤ n feladat megold´ asa. Bevezetve a b := log(p/ ni=1 qi ) ´es az ai := log(pi /qi ) jel¨ ol´est ez ekvivalens az al´ abbi eg´esz ´ert´ek˝ u LP feladattal: Q
min
n X
ci xi
i=1 n X
ai xi ≥ b
i=1
xi ∈ {0, 1}, 1 ≤ i ≤ n. ez a kor´ abban ismertetett h´atizs´ak probl´em´ahoz hasonl´oan oldhat´o meg; p´eld´ aul a korl´ atoz´ as ´es sz´etv´alaszt´as (branch and bound) m´odszer´evel. 62
10. el˝oad´as Nem z´ erus ¨ osszeg˝ u j´ at´ ekok Az ´eletben el˝ ofordul´ o j´ at´ekoknak csak kis r´esze z´erus ¨osszeg˝ u, a legt¨obb esetben nem ez a helyzet. Ezekkel a j´at´ekokkal hihetetlen¨ ul sokf´ele probl´em´at modellezhet¨ unk. Sajnos ennek ´ara van. A z´erus ¨osszeg˝ u j´at´ekok elm´elet´eben oly hasznosnak bizonyult kevert strat´egi´ak ´altal´aban nem adnak j´o v´alaszt, mi t¨ obb, m´ ar azt sem k¨ onny˝ u megfogalmazni mit ´erts¨ unk optim´alis megold´as alatt. Nem ´ all m´ odunkban az ¨osszes koncepci´o ismertet´ese, m´eg kev´esb´e r´eszletes elemz´ese. Ehelyett v´azolunk n´eh´any l´enyeges ¨otletet, els˝osorban olyanokat, melyek beleillenek az eddigi t´argyal´asm´odunkban. P´ elda 1. K´et ´ asv´ anyvizet forgalmaz´o v´allalat (Appolinaris ´es Perrier) versenyeznek a piacon. A lehets´eges strat´egi´ak egy, illetve k´et doll´ar´ert adni az ´ asv´ anyv´ız palackj´ at. Az egyes strat´egi´ak alkalmaz´asa mellett keletkez˝o hasznot t´ abl´ azatban foglaltuk ¨ossze. A m´atrixba ´ırt sz´amp´ar els˝o eleme a sor-, a m´ asodik az oszlopj´ at´ekos haszna az adott strat´egia p´ar mellett. Perrier
Apollinaris
1$ 2$
1$ 0, 0 -5000, 5000
2$ 5000, -5000 0, 0
K¨ onnyen l´ athat´ o, hogy palackonk´ent 1 doll´ar´ert kell adni az ´asv´anyvizet. Ez ak´ ar a nyeregpont l´etez´es´ere val´o hivatkoz´assal, ak´ar az els˝o sor (oszlop) dominanci´ aj´ anak megmutat´as´aval a m´asodik sor (oszlop) felett t¨ort´enhet. ´ Altal´ aban is kimondhatjuk: a dominancia a z´erus ¨osszeg˝ u j´at´ekokn´al l´ atott m´ odszerrel anal´ og m´odon haszn´alhat´o. (Vegy¨ uk ´eszre, hogy a fenti j´ at´ek igaz´ ab´ ol felfoghat´ o z´erus ¨osszeg˝ u j´at´ekk´ent.) P´ elda 2. Egy hasonl´ o, b´ ar kicsit komplik´altabb esetben k´et v´allalat, a T¨ ok´eletes ´es a Var´ azslatos, m¨ uty¨ ur¨oket ´arulhat 1, 2 vagy 3 doll´aros ´aron. A lehet˝ os´egeket a kor´ abbiak szerint rendezt¨ uk t´abl´azatba; a nyeres´eg/vesztes´eg m´ert´ek´et az elad´ asi ´ ar ´es a piaci r´eszesed´es v´altoz´asai miatt v´altoz´o termel´esi k¨ olts´egek szabj´ ak meg. T¨ok´eletes
Var´ azslatos
1 2 3
1 0, 0 -10, 50 -20, 40
2 50, -10 20, 20 10, 90 63
3 40, -20 90, 10 50, 50
´ Ez a j´ at´ek nem z´erus o¨sszeg˝ u, ´es nincs domin´ans strat´egia sem. Uj 13 gondolatra van sz¨ uks´eg, ez az u ´n. Nash egyens´ uly vagy Nash equilibrium. Defin´ıci´ o. Egy strat´egia p´ar Nash egyens´ ulyi helyzet, ha egyik j´at´ekos sem tudja strat´egia v´ altoztat´ssal n¨ovelni nyerem´eny´et, amennyiben a m´asik nem v´ altoztat a strat´egi´ aj´ an. A p´eld´ ankban a (3,3) strat´egia p´ar nem Nash equilibrium, hisz a Var´ azslatos ´ att´erve a 2 doll´ aros strat´egi´ara n¨ovelheti haszn´at. Hasonl´oan bel´ athatjuk, hogy az (1,1) strat´egi´an k´ıv¨ ul nincs Nash egyens´ ulyi helyzet, ´ıgy a mindk´et c´eg ´ altal felsz´am´ıtott 1 doll´aros ´ar a “re´alis” ´ar. N´emely k¨ ozgazd´ asz u ´gy v´eli, a piacgazdas´ag versenyhelyzet´enek hat´as´at siker¨ ult ´ıgy le´ırni: az alacsony ´ arakat. Ha a verseny nem lehets´eges (pl. nem egy doll´aros m¨ uty¨ ur¨ ok, hanem csak n´eh´ any c´eg ´altal gy´artott harci rep¨ ul˝o a t´et), akkor ez a mechanizmus nem k´epes alacsony ´arakat garant´alni. A Nash egyens´ ulyi helyzet a dominanci´ at haszn´al´o megold´asok kiterjeszt´ese, ´es a bemutatottn´al j´ oval ´ altal´ anosabb felt´etelek mellett is l´etezik. Az al´abbi p´elda szerint nem ad egy´ertelm˝ u megold´ ast. P´ elda 3. K´et r´ adi´ o´ allom´ as (L¨ok¨ott ´es Laza) h´arom profilb´ol v´alaszthat. Sug´ arozhatnak rockot (R), komolyzen´et (K) ´es h´ıreket (H). Az adott programok hallgat´ os´ aga 50, 30 ´es 20 sz´azal´ek. Ha egy ´allom´as egyed¨ ul fed le egy programot, akkor megszerzi annak a hallgat´os´ag´at (´es a vele ar´anyos rekl´ ambev´etelt), ha a m´ asikkal egy¨ utt, akkor fele-fele ar´anyban osztoznak. M´ atrix form´ aban: Laza
L¨ ok¨ ott
R K H
R 25, 25 30, 50 20, 50
K 50, 30 15, 15 20, 30
H 50, 20 30, 20 10, 10
K¨ onnyen ellen˝ orizhet˝ o, hogy csak a (K,R) ´es az (R,K) strat´egiap´ar Nash egyens´ ulyi helyzet. Nehezebb eld¨onteni, mit jelent ez a megold´as. Melyik ´ t˝ val´ osul majd meg, ´es milyen strat´egi´at v´alasszanak a j´at´ekosok ? Ugy unik, a Nash equilibriumok meghat´aroz´asa t´avolr´ol sem ad v´alaszt k´erd´eseinkre. Egy lehets´eges tov´ abbl´ep´esi ir´any annak vizsg´alata, mit hozhat a koordin´ aci´ o 13
A fogalmat ´es a vele kapcsolatos legfontosabb t´eteleket John Forbes Nash alkotta meg az 50-es ´evek elej´en. K´es˝ obb a n´emet Reinhard Selten ´es a magyar Hars´ anyi J´ anos ´ert el jelent˝ os eredm´enyeket ebben az ir´ anyban, amit 1994-ben a h´ arm´ ojuk k¨ oz¨ ott megosztott k¨ ozgazdas´ agi Nobel-d´ıjjal ismertek el.
64
j´ at´ekosok egyes csoportjai k¨ oz¨ott, illetve hogyan oszhat´ o el a k¨oz¨osen szerzett haszon. Ez a motiv´ aci´ oja az u ´n. n-szem´elyes j´ at´ekok tanulm´anyoz´as´anak. Miel˝ ott r´ at´ern´enk erre, megeml´ıt¨ unk m´eg egy p´eld´at, amely azt sugallja, hogy a Nash egyens´ ulyi helyzet valamilyen ´ertelemben j´o megold´as, ´es ha probl´em´ aink is vannak vele az az ´elet ´es nem a modell meghat´arozatlans´ag´ ab´ ol ered. P´ elda 4. “Mely oldal´ an haladjunk az u ´tnak” j´at´ek. K´et aut´o halad egym´assal szemben ´es a tal´ alkoz´ asn´al d¨onteni¨ uk kell az u ´t jobb vagy bal sz´el´ere h´ uz´ odjanak. A kiss´e fikt´ıv 10 ´ert´eket rendelve a biztons´agos tov´abbhalad´ashoz, illetve az ¨ ossze¨ utk¨ oz´eshez az al´abbi m´atrixot kapjuk: Honda
Fiat
Bal Jobb
Bal 1, 1 -10, -10
Jobb -10, -10 1, 1
Mind a (Bal, Bal), mind a (Jobb, Jobb) Nash egyens´ ulyi helyzet, de ez nem sokat seg´ıt rajtunk, ha belek´enyszer¨ ul¨ unk egy ilyen j´at´ekba. A t´ arsadalmi konvenci´ okkal szok´as koordin´alni az eff´ele szitu´aci´okat, s mint tudjuk a konkr´et esetre mindk´et megold´asra van p´elda. ´Igy azt´an nem is baj, hogy a modell¨ unk megold´asa nem egy´ertelm˝ u. Ha az lenne, akkor m´ar nem az ´eletet ´ırn´ a le, hanem az el˝o´ıt´eleteinket. P´ elda 5. Az evol´ uci´ o biol´ ogi´aban nagyon fontos szerepet kaptak egyes nem z´erus¨ osszeg˝ u j´ at´ekok. Az al´abbi p´elda az u ´n. Galamb-H´eja modell, amellyel egy popul´ aci´ o evol´ uci´ osan stabil strat´egi´ ait (ESS) szeml´eltethetj¨ uk. Egy galambfajon bel¨ ul - talalkoz´as eset´en - k´et egyed k¨oz¨ott k´etf´ele viselked´es lehets´eges: kit´ernek egym´ as el˝ol vagy harcba kezdenek. A kit´er´essel esetleg elvesztenek egy er˝ oforr´ ast (p´ar, ´elelem, f´eszkel˝ohely stb), m´ıg a konfliktus s´er¨ ul´essel, energia vagy id˝ o pocs´ekl´assal j´ar. Ha mindk´et galamb kit´erne, akkor az egyik¨ uk megszerzi az er˝oforr´ast, legyen ez egyenl˝o es´ely˝ u. Egy “galamb” azaz b´ek´es egyed tal´alkozik egy “h´ej´aval” azaz egy harcias egyeddel, akkor a “galamb” kit´er, elker¨ uli a s´er¨ ul´est, de elveszti az er˝oforr´ast, ami ´ıgy a “h´eja” zs´ akm´ anya lesz. K´et “h´eja” tal´alkoz´asa mindkett˝ore n´ezve jelent˝ os h´ atr´ annyal j´ ar. Az egyedek vagy egyik, vagy a m´asik viselked´est k¨ovetik; k´erdes, melyik a jobb? K¨ onnyen l´ athat´ o, ak´ ar egyik, ak´ar m´asik viselked´es v´alik kiz´ar´olagoss´a, egy olyan egyed, amely ett˝ ol a norm´at´ol el´er jelent˝os el˝onybe ker¨ ul. Teh´ at a c´el egy olyan stabil helyzet megtal´al´asa, melyben az egyed sz´ am´ ara nincs ok v´ altoztatni a viselked´es´en. Oldjuk meg ezt egy fikt´ıv ki65
fizet´esi m´ atrix eset´en. galamb h´eja
galamb 2, 2 5, -1
h´eja -1, 5 -9, -9
Az “galamb-h´eja” eloszl´as x ´es 1 − x, azaz x val´osz´ın˝ us´eggel b´ek´es egy egyed, 1−x-szel agressz´ıv. Felt´eve, hogy a popul´aci´o el´eg nagy, egy “galamb” v´ arhat´ oan 2x − 1(1 − x) = 3x − 1, egy “h´eja” pedig 5x − 9(1 − x) = 14x − 9 nyeres´eget k¨ onyvelhet el. Egyens´ uly, azaz ESS akkor van, ha 3x0 − 1 = 15x0 −9, vagyis x0 = 2/3. Teh´at a popul´aci´o el˝ore meghat´arozhat´o ar´anyban mutat b´ek´es vagy harcias viselked´est. Nem meglep˝o, ha cs¨okkentj¨ uk az er˝ oforr´ as ´ert´ek´et (ami 3 volt a p´eld´aban) illetve az id˝o´et, akkor a b´ek´es, m´ıg ha a s´er¨ ul´es kock´ azat´ at (8), akkor a harcias viselked´es terjed a popul´aci´oban. Az al´ abbi fel´ all´ asban x0 = 9/10. galamb h´eja
galamb 1, 1 2, 0
h´eja 0, 2 -9, -9
Ezt az apr´ ocska modellt neh´ez t´ ul´ert´ekelni: meglep˝oen sz´eles a jelens´egek k¨ ore, melyre k´epes magyar´ azatot adni. P´ elda 6. Sz´eles k¨ orben ismert az u ´n. Prisoner Paradox, azaz az fogoly dilemma. Ez a v´ adalku lassan n´alunk is meghonosod´o int´ezm´enye ´altal keletkez˝ o “j´ at´ek”, egy klasszikus m´atrixa: vall tagad
vall -5, -5 -10, 0
tagad 0, -10 -1, -1
Ebben a “k¨ oz¨ os optimum” a tagad-tagad, ami nyilv´an nem Nash egyens´ ulyi helyzet, hisz a vall-vall az egyed¨ uli ilyen. n-szem´ elyes j´ at´ ekok Az n-szem´elyes j´ at´ekok vizsg´alat´at Neumann J´anos ´es Oskar Morgenstern kezdte el. Mint kor´ abban utaltunk r´a, nem valamif´ele “h´arom szem´elyes sakk”, vagy a futball le´ır´ asa a c´el, hanem a racion´alis osztozkod´as t¨orv´enyeinek tanulm´ anyoz´ asa abban az esetben, mikor a j´at´ekosok egy tetsz˝oleges csoportj´ anak “ereje” ismert. Defin´ıci´ o. Egy n-szem´elyes j´at´ek alatt a k¨ovetkez˝o rendszert ´ertj¨ uk: Adott az I = {1, 2, . . . , n}, a j´at´ekosok halmaza. Egy S ⊆ I halmazt
66
koal´ıci´ onak nevezz¨ uk, ´es adott egy v : 2I → R (a koal´ıci´okhoz egy val´os sz´ amot rendel˝ o) u ´n. karakterisztikus f¨ uggv´ eny u ´gy, hogy (1.) v(∅) = 0 (2.) v(S ∪ T ) ≥ v(S) + v(T ), ha S, T ⊆ I ´es S ∩ T = ∅. A v(S) jelenti szeml´eletesen azt a hasznot (kifizet´est, hatalmat stb.), amit az S-ben l´ev˝ o j´ at´ekosok egym´assal ¨osszefogva egy¨ uttesen el´erhetnek (ak´ ar a t¨ obbiek ellen´ere is). A v(S ∪ T ) ≥ v(S) + v(T ) az S ∩ T = ∅ eset´en azt fejezi ki, hogy a k´et csoport ¨osszefogva legal´abb annyit el´er, mint a k¨ ul¨on szerzett haszon ¨ osszege.14 Ezt szuperaddit´ıv tulajdons´ agnak h´ıvjuk. P´ elda 1. Ingatlan fejleszt´es (k´et v´ as´ arl´ os piac) Egy f¨ oldm˝ uves ´ altal birtokolt f¨old mez˝ogazdas´agi ´ert´eke 100 ezer doll´ar. K´et vev˝ o p´ aly´ azik r´ a, az egyik lak´as´ep´ıt´essel 200 ezer, a m´asik bev´as´arl´o k¨ ozpont l´etrehoz´ as´ aval 300 ezer doll´ar hasznot ´erhet el a f¨old felhaszn´al´as´aval. Vegy¨ uk ´eszre, hogy m´ıg a f¨oldm˝ uves egymag´aban is k´epes haszn´at venni a f¨ oldj´enek, addig az ´ep´ıt˝ ok nem. Ez a k¨ovetkez˝o 3-szem´elyes j´at´eknak felel meg: I = {1, 2, 3}, ahol 1: f¨ oldm˝ uves, 2, 3 pedig a k´et vev˝ojel¨olt. v(∅) = 0 v({1,2}) = 200000 v({1}) = 100000 v({1,3}) = 300000 v({2}) = v({3}) = 0 v({2,3}) = 0 v({1,2,3}) = 300000 ´ Altal´ aban az ´ert´ek a k¨ ul¨ onb¨oz˝o tulajdonosok felhaszn´al´as´aban a, b ´es c, ahol a < b < c. P´ elda 2. A t¨ obbs´egi j´ at´ekok Ez a klasszikus 50%+1 szavazattal megval´osul´o d¨ont´eseket modellezi. I = {1, . . . , n} (
v(S) =
1 eset´en “S nyer” 0 eset´en “S vesz´ıt” (
v(S) =
1 ha |S| > n/2 0 k¨ ul¨onben.
14
Az o ¨sszefog´ assal ezt el is tudj´ ak ´erni, hisz megtehetn´ek, hogy k¨ ul¨ on-k¨ ul¨ on j´ atszanak v(S) illetve v(T ) nyerem´enyt szerezve, majd ut´ anna egyes´ıten´ek a nyerem´eny¨ uket.
67
P´ elda 3. A s´ ulyozott t¨ obbs´egi j´ at´ekok Az i-edik j´ at´ekosnak wi szavazata van ´es q szavazat kell a gy˝ozelemhez. I = {1, . . . , n} P 1 ha wi ≥ q i∈S v(S) = 0 k¨ ul¨onben Jel¨ olj¨ uk ezt a j´ at´ekot a r¨ovidebb (q; w1 , w2 , . . . , wn ) form´aval. Vegy¨ uk ´eszre, hogy p´eld´ aul a (3; 2, 2, 2, 2) “j´at´ek” nem j´at´ek a defin´ıci´onk szerint, mert a v f¨ uggv´eny nem szuperaddit´ıv. Defin´ıci´ o. Egy n-szem´elyes j´at´ek egyszer˝ u, ha a v karakterisztikus f¨ uggv´eny csak 0 ´es 1 ´ert´eket vesz fel. P´ elda 4. Az ENSZ Biztons´ agi Tan´ acs m˝ uk¨ od´ese. A BT-nek 5 ´ alland´ o ´es 10 ideiglenes tagja van. Egy hat´arozat ´eletbe l´ep, ha mind az ¨ ot ´ alland´ o ´es legal´abb n´egy ideiglenes tag megszavazza. Ez fel´ırhat´ o, mint (39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1) s´ ulyozott t¨obbs´egi j´at´ek. Imput´ aci´ ok (kifizet´ esek) Az n-szem´elyes j´ at´ekokban a j´at´ekosoknak jut´o ´esszer˝ u kifizet´eseket akarjuk meghat´ arozni. Egy kifizet´est egy x = (x1 , x2 , . . . , xn ) n-dimenzi´os val´os vektorral ´ırhatunk le, ahol xi az i-edik j´at´ekos r´esze. Aesophus mes´ej´evel ellent´etben feltessz¨ uk, hogy az osztozkod´ast csak a v karakterisztikus f¨ uggv´eny befoly´ asolja, valamint a j´ at´ekosok tiszt´aban vannak az ´erdekeikkel ´es megv´edik azokat.15 Sz´ oba j¨ on az al´abbi k´et szempont: 1. xi ≥ v({i}), i = 1, . . . , n, sz´oban “Egy´eni racionalit´as” 2.
Pn
i=1 xi
= v(I), avagy “Pareto optimalit´as.”
Az 1. pont azt fejezi ki, hogy az egyik j´at´ekos sem fogad el olyan kifizet´est, amelyn´el jobbat (mindenf´ele koal´ıci´o n´elk¨ ul) egymaga is k´epes el´erni. A Pn x ≤ v(I) annyit tesz: nem oszthat´ o t¨obb, mint amennyi van. Az i i=1 egyenl˝ os´eg viszont megk¨ oveteli, hogy a j´at´ekosok ´altal megszerezhet˝o maxim´ alis ¨ osszeget osszuk sz´et. (Azaz egyfajta kooper´aci´ora “k´enyszer´ıthetj¨ uk” a j´ at´ekosokat.) Defin´ıci´ o. Az olyan x ∈ Rn vektorokat, amelyekre teljes¨ ulnek az 1. ´es 2. felt´etelek, imput´ aci´ oknak h´ıvjuk, az ¨osszes imput´aci´o halmaz´at pedig A(v)-vel jel¨ olj¨ uk. 15
Val´ oj´ an ez el´eg er˝ os ´es az ´eletben ritk´ an teljes¨ ul˝ o felt´etel.
68
P´ elda 4. I = {1, 2, 3}, v(S) = 0, ha |S| < 2, m´ıg v(S) = |S|/3 k¨ ul¨onben. Ekkor az imput´ aci´ ok halmaza A(v) = {x ∈ R3 : xi ≥ 0,
3 X
xi = 1}.
i=1
Az imput´ aci´ ok A(v) halmaza “t´ ul nagy”, ´ıgy ´altal´aban nem tekinthet˝o megold´ asnak. K¨ ul¨ onb¨ oz˝ o, t¨obb´e-kev´esb´e ´esszer˝ u felt´etelekkel szok´as sz˝ uk´ıteni az A(v)-t, ´es a kapott r´eszhalmazt deklar´alni a l´etrej¨ohet˝o megold´asok halmaz´ anak. A sokf´ele megk¨ozel´ıt´es sz´amos vit´ara adott alkalmat ´es a mai napig sem lehet egy´ertelm˝ u gy˝oztest hirdetni. Mi h´arom koncepci´ot fogunk v´ azolni, a mag (core), a stabil halmaz ´es a Shapley ´ert´ek fogalm´at. Ezek mindegyike nagyon tanuls´ agos. Defin´ıci´ o. Ha x, y ∈ A(v), akkor egy ∅ = 6 S ⊆ I hat´ ekonyan prefer´ alja P x-et y-nal szemben, ha xi > yi minden i ∈ S eset´en ´es i∈S xi ≤ v(S). Jelben x S y. Az elnevez´es ´es a motiv´aci´o nyilv´anval´o. Az xi > yi i ∈ S miatt az SP beli j´ at´ekosok jobban kedvelik x-et, mint y-t. A i∈S ≤ v(S) a hat´ekonys´ag, ugyanis az S koal´ıci´ o kik´enyszer´ıtheti az y elvet´es´et ´es a sz´am´ara el˝ony¨osebb xi (i ∈ S) kifizet´est garant´ alhatja tagjainak. P´ elda 5. Vegy¨ uk a 4. p´eld´aban szerepl˝o j´at´ekot ´es az x = (1/3, 5/12, 1/4), y = (1/2, 1/3, 1/6) ´es z = (9/24, 1/3, 7/24) vektorokat. L´athat´o, hogy x, y, z ∈ A(v), tov´ abb´ a x {2,3} y (x2 = 5/12 > 1/3 = y2 , x3 = 1/4 > 1/6 = y3 , ´es x2 + x3 = 5/12 + 1/4 ≤ v({2, 3}) = 2/3). Hasonl´oan bel´athat´o a z {1,3} x rel´ aci´ o; ugyanakkor nincs olyan ∅ 6⊆ {1, 2, 3}, amelyre z S y. (Ez azt jelenti, hogy m´ıg egy r¨ ogz´ıtett S-re a “ S ” rel´aci´o tranzit´ıv. Ezzel szemben ha u ´gy defini´ alunk egy “ ” rel´aci´ot, hogy x y akkor ´es csak akkor, ha l´etezik olyan ∅ 6= S ⊆ I, melyre x S y, akkor ez a “ ” rel´aci´o nem tranzit´ıv.) Defin´ıci´ o. Egy n-szem´elyes j´at´ek magja azon x imput´aci´okb´ol ´all, amelyekkel szemben egyetlen y imput´aci´ot sem prefer´al hat´ekonyan valamely nem u ¨res S koal´ıci´ o. Jelben a mag C(v) := {x ∈ A(v) : nem l´etezik olyan y ∈ A(v) ´es ∅ = 6 S ⊆ I, hogy y S x}. P´ elda 6. Vegy¨ uk a (7; 8, 1, 1) s´ ulyozott t¨obbs´egi j´at´ekot. Itt v(S) = 1, ha 1 ∈ S ´es v(S) = 0, ha 1 6∈ S. Ez´ert A(v) = {x : x1 ≥ 1, x2 ≥ 0, x3 ≥ 0 ´es P3 aci´o van csak, i=1 xi = 1} = {(1, 0, 0)}, azaz |A(v)| = 1. Mivel egy imput´ A(v) = C(v), ´es ´ıgy C(v) = {(1, 0, 0)}. Mint v´arhat´o volt, az 1 “viszi az eg´eszet.”
69
11. el˝oad´as n-szem´ elyes j´ at´ ekok, a mag kisz´ am´ıt´ asa Egy v karakterisztikus f¨ uggv´eny˝ u j´at´ek C(v) magj´aban l´ev˝o vektorok joggal tekinthet˝ ok ´esszer˝ u megold´asoknak. Ezzel azonban nem ´ert¨ unk a probl´em´ ak v´eg´ere. P´ elda 1. Sz´ amoljuk ki a (2; 1, 1, 1) s´ ulyozott t¨obbs´eg˝ u j´at´ek magj´at. Tegy¨ uk fel, hogy y ∈ A(v). Ekkor valamely 1 ≤ i < j ≤ 3 eset´en yi + yj < 1, hisz y1 +y2 +y3 = 1. Megmutatjuk, hogy van olyan z ∈ A(v) ´es ∅ = 6 S ⊆ {1, 2, 3}, amelyre z S y. Az indexek cser´ej´evel feltehetj¨ uk, hogy y1 + y2 < 1, s mintegy a “marad´ekot” (y3 -at) sz´etosztjuk az els˝o ´es m´asodik j´at´ekos k¨oz¨ott: z1 := y1 + y3 /2, z2 := y2 + y3 /2. ´Igy persze z {1,2} y. M´assz´oval b´ armely y ∈ A(v)-re l´etezik olyan z ∈ A(v) ´es nem u ¨res S ⊆ {1, 2, 3} halmaz, hogy z S y. Ez persze azt jelenti, hogy a mag az u ¨res halmaz, vagyis nem tudunk j´ o megold´ ast javasolni. Sz¨ uks´eg¨ unk van teh´ at egyr´eszt a mag szerkezet´enek jobb meg´ert´es´ere a k´enyelmesebb kisz´ am´ıt´ as ´erdek´eben, m´asr´eszt tenn¨ unk kell valamit, ha a mag u ¨res. Az els˝ o probl´em´ara vonatkozik a mag le´ır´asa, mint konvex poli´eder. T´ etel 16 Egy v karakterisztikus f¨ uggv´eny˝ u n-szem´elyes j´ at´ekban az x imput´ aci´ o eleme a magnak akkor ´es csak akkor, ha minden S koal´ıci´ ora a P otlens´eg teljes¨ ul. i∈S xi ≥ v(S) egyenl˝ Bizony´ıt´ as. Vegy¨ unk egy olyan x vektort, amelyre teljes¨ ul az ¨osszes, a felt´etelben lev˝ o egyenl˝ otlens´eg. Tegy¨ uk fel, hogy van olyan y ∈ A(v) ´es nem P u ¨res S ⊂ I, hogy y S x. Ekkor yi > xi minden i ∈ S ´es i∈S yi ≤ v(S) a hat´ekony preferencia miatt, amib˝ol a X i∈S
yi ≤ v(S) ≤
X i∈S
xi <
X
yi
i∈S
ellentmond´ as ad´ odik. A m´ asik ir´ any bizony´ıt´as´ahoz tekints¨ unk egy, a felt´etel valamelyik egyenl˝ otlens´eg´et megs´ert˝ o x ∈ A(v) vektort, ´es legyen ∅ = 6 S ⊂ I, amelyre P s´er¨ ul; azaz i∈S xi < v(S). Tal´alni akarunk egy olyan y ∈ A(v) vektort ´es P ∅= 6 T ⊂ I halmazt, amelyre y T x. Az el˝obbiek miatt v(S) = i∈S xi + , ahol > 0. Az y-t u ´gy ´ all´ıtjuk el˝o, hogy az -t “felosztjuk” az S koal´ıci´o tagjai k¨ oz¨ ott, azaz yi := xi + /|S|, ha i ∈ S. K´erd´es, mi legyen yi , ha i 6∈ S ? Az y vektornak benne kell lennie A(v)-ben, ´ıgy az egy´eni racionalit´as 70
felt´eteleit nem s´ertheti, azaz yi ≥ v({i}) minden i ∈ I. Ezek automatikusan teljes¨ ulnek, ha i ∈ S, hiszen x ∈ A(v) ´es yi > xi ≥ v({i}) ha i ∈ S. P Teljes¨ ulnie kell tov´ abb´ a a Pareto optimalit´asnak, vagyis ni=1 yi = v(I). Keress¨ uk h´ at az yi -ket i 6∈ S-re a k¨ovetkez˝o alakban: yi = v({i}) + δi , ahol δi ≥ 0. Ezzel n X
yi =
i=1
amib˝ ol a
P
i∈S
X
xi + +
v({i}) +
i6∈S
i∈S
xi + = v(S) ´es
X
Pn
i=1 yi
v(I) = v(S) +
X
X
δi ,
i6∈S
= v(I) miatt k¨ovetkezik a v({i}) +
i6∈S
X
δi .
i6∈S
´ Atrendezve a δi -kre az al´ abbi felt´etel ad´odik: X
δi = v(I) − v(S) −
i6∈S
X
v({i}).
i6∈S
Nevezz¨ uk a fenti egyenlet jobboldal´at δ-nak, ´es defin´aljuk majd a δi -ket a δi := δ/(n − |S|) formul´ aval. Ekkor az y imput´aci´o lesz, amennyiben δ ≥ 0. Pn ul δ nem neg(Val´ oban, hisz i=1 yi = v(I) ´es yi ≥ v({i}) i ∈ I-re.) V´eg¨ ativit´ as´ anak megmutat´ as´ ara haszn´aljuk a v f¨ uggv´eny szuperadditivit´as´at; P ´ i6∈S v({i}) ≤ v(I \ S). Igy δ = v(I) − v(S) −
X
v({i}) ≥ v(I) − v(S) − v(I \ S) ≥ v(I) − v(I) = 0,
i6∈S
ahol az utols´ o egyenl˝ otlens´egben (v(I) ≥ v(S) + v(I \ S)) ism´et a szuperadditivit´ ast haszn´ altuk, ´es ezzel k´esz vagyunk. 2 P´ elda 2. A t´etel seg´ıts´eg´evel kisz´am´ıthatjuk a kor´abban ismertetett ingatlan fejleszt´es j´ at´ek magj´ at. v v({1}) = 100000 v({2}) = v({3}) = 0 v({1, 2}) = 20000 v({1, 3}) = 30000 v({2, 3}) = 0 v({1, 2, 3}) = 300000
A(v) x1 ≥ 100000 x2 ≥ 0 x3 ≥ 0 P (ii) 3i=1 xi = 300000
71
C(v) A(v) elemei, melyekre (iii) x1 + x2 ≥ 200000 (i) x1 + x3 ≥ 300000 x2 + x3 ≥ 0
(i) ´es (ii) ⇒ x2 = 0, (iii) ⇒ x1 ≥ 200000, azaz a mag a k¨ovetkez˝o: C(v) = {x : 200000 ≤ x1 ≤ 300000, x2 = 0, x3 = 30000 − x1 }. A v´ arakoz´ asnak megfelel˝ oen a 2. j´at´ekos kiz´ar´odik az u ¨zletb˝ol, ´es a f¨oldet a 3. veszi meg egy 200 ´es 300 ezer doll´ar k¨ozti ¨osszeg´ert. Enn´el t¨obbet nem tudunk mondani, de ez term´eszetes, hiszen a val´os´agban sem d¨onthet˝o el el˝ ore, mi lesz az ´ ar. (Az f¨ ugghet az alkufolyamatt´ol.) Stabil megold´ asok Amennyiben a j´ at´ek magja u ¨res, nem tudunk ´esszer˝ u megold´ast javasolni, ´es ez is hasznos inform´aci´o. Elk´epzelhet˝o m´as, stabilit´ast figyelembe vev˝ o szempont alapj´ an t¨ ort´en˝o v´alaszt´as A(v)-b˝ol. Ez volt Neumann ´es Morgenstern eredeti gondolata. Egy kor´ abbi defin´ıci´ onk egy G ir´any´ıtott gr´afban egy f¨ uggetlen ´es domin´al´o S ⊆ V ponthalmaz mag vagy stabil halmaz. (Sajnos a magyar terminol´ ogia k¨ onnyen zavart okozhat, mivel ez a mag az angolban kernel, m´ıg az el˝ oz˝ o t´etellel karakteriz´alt mag az core.) Egy n-szem´elyes j´at´ek imput´ aci´ oinak A(v) halmaza felfoghat´o egy Gv gr´afk´ent; V (Gv ) = A(v), ´es (x, y) ∈ E(Gv ) ⇔ x S y valamely S ⊆ I-re. Defin´ıci´ o. Egy B ⊆ A(v) halmaz stabil megold´ as a v karakterisztikus f¨ uggv´ennyel meghat´ arozott j´at´ekban, ha B mag (kernel, stabil halmaz) a Gv gr´ afban. Megjegyz´ es: A “m´ asik” mag (core) is le´ırhat´o a Gv gr´af seg´ıts´eg´evel: C(v) azon pontok halmaza A(v)-ben, amelyekbe nem fut be ´el, ha mint Gv -beli pontk´ent tekintj¨ uk ˝ oket. Az els˝ o pillant´ asra nem nyilv´anval´o, mi ´ertelme van a stabil halmazokat megold´ asnak tekinteni. Az egyik motiv´aci´o lehet a stabil p´aros´ıt´asi probl´ema, amelynek a megold´asai ´eppen egy gr´af stabil halmazai. Tov´abb´a stabil halmaz l´etezhet akkor is, ha a mag (core) u ¨res. P´ elda 3. A (2; 1, 1, 1) s´ ulyozott t¨obbs´egi j´at´ekra l´attuk, hogy C(v) = ∅. Legyen B = {(1/2, 1/2, 0), (1/2, 0, 1/2), (0, 1/2, 1/2)}, ekkor B stabil halmaz. B f¨ uggetlen halmaz: Ha pl. (1/2, 1/2, 0) S (1/2, 0, 1/2) ⇒ S = {2}, de 1/2 ≤ v({2}) = 0 nem teljes¨ ul; ellentmond´as. A t¨obbi eset bizony´ıt´asa teljesen hasonl´ o m´ odon t¨ ort´enhet. B domin´ al´ o halmaz: Legyen x ∈ A(v), x = (x1 , x2 , x3 ). Ha x1 > 1/2, akkor x2 , x3 < 1/2, de ekkor (0, 1/2, 1/2) {2,3} (x1 , x2 , x3 ). A szimmetria miatt feltehet˝ o, hogy x1 ≥ max{x2 , x3 }, ´ıgy az el˝oz˝o megjegyz´es miatt x2 , x3 ≤ 1/2. Ha x2 vagy ´eppen x3 1/2, akkor x ∈ B. Ha viszont 72
mindkett˝ o kisebb, mint 1/2, akkor (0, 1/2, 1/2) {2,3} (x1 , x2 , x3 ). Hasonl´ o megfontol´ assal ad´ odik, hogy kontinuum sok stabil halmaz van: minden c ∈ (0, 1/2) eset´en a Bc := {(x1 , 1 − c − x1 , c) : 0 ≤ x1 ≤ 1 − c} halmaz stabil. P´ elda 4. A 2. p´eld´ aban kisz´amoltuk az ingatlanfejleszt´es j´at´ek magj´at. B´ armely n-szem´elyes j´ at´ekra, ha B egy stabil halmaz, akkor C(v) ⊆ B. Eset¨ unkben egy B stabil halmaz felt´etlen¨ ul b˝ovebb C(v)-n´el (B\C(v) 6= ∅), hiszen az x = (100000, 100000, 100000) ∈ A(v) imput´aci´ora nem l´etezik olyan y ∈ C(v) ´es S ⊆ {1, 2, 3}, amelyre y S x. Megmutatjuk, hogy B := {(x1 , x2 , x3 ) : 100000 ≤ x1 ≤ 300000, x2 = 0, x3 = 300000 − x1 } egy stabil halmaz. B f¨ uggetlen: Legyen x, y ∈ B ´es x S y. Mivel x2 = y2 = 0, az x1 > y1 , akkor ´es csak akkor, ha x3 < y3 , illetve x3 > y3 ⇒ x1 < y1 . Teh´ at S = {1} vagy S = {3}, ami lehetetlen. B domin´ al´ o: Tegy¨ uk fel, hogy egy y ∈ B-re y2 > 0. Legyen ekkor x = (x1 , x2 , x3 ) := (y1 + y2 /2, 0, y3 + y2 /2). Nyilv´anval´oan x ∈ B ´es x {1,3} y. Egy stabil halmaz teh´ at a mag ´altal sugallt´ol elt´er˝o megold´asokat is ´ megenged. Erdekes tulajdons´aga, hogy “osztozkod´ast” ´ırhat el˝o egy j´at´ekban, amelynek u ¨res a magja (l´ asd 3. p´elda). Sajnos nem puszt´an a nehezen kisz´ am´ıthat´ os´ agban hasonl´ıt a magra; 1969-ben Lucas bebizony´ıtotta, van olyan j´ at´ek, melynek nincs stabil halmaza. Egy karakter´eben k¨ ul¨onb¨oz˝o megk¨ ozel´ıt´est jelent a Shapley ´ert´ek, amely a j´at´ekosok “erej´et”, alkupoz´ıci´oj´ at hivatott modellezni. A Shapley ´ ert´ ek A c´el egy olyan Φ f¨ uggv´eny defini´al´asa, amely minden v karakterisztikus f¨ uggv´ennyel le´ırt j´ at´ekhoz hozz´arendel egy Φ(v) ∈ Rn vektort. Az i-edik j´ at´ekos Shapley ´ert´eke Φi (v), ha Φ(v) = (Φ1 (v), . . . , Φn (v)) ´es az al´abbi axi´ om´ ak teljes¨ ulnek Φ-re: 1. Legyen π az I = {1, . . . , n} halmaz egy permut´aci´oja, ´es w(S) = v(π(S)) minden S ⊆ I-re. Ekkor Φi (w) = Φπ(i) (v). 2.
n P
Φi (v) = v(I).
i=1
3. Ha v(S\{i}) = v(S) minden S ⊆ I-re, akkor Φi (v) = 0. 4. Additivit´ as. Ha v ´es v 0 karakterisztikus f¨ uggv´enyek az I halmazon ´es w = v + v 0 , akkor Φ(w) = Φ(v) + Φ(v 0 ).
73
Megjegyz´ es: Az els˝ o axi´ oma azt fejezi ki, hogy a j´at´ekosok ereje f¨ uggetlen az elnevez´es¨ ukt˝ ol. A m´ asodik a Pareto optimalit´as analogonja, a megszerezhet˝ o haszon teljes feloszt´asa. A harmadik szerint nulla az “´ert´eke” annak a j´ at´ekosnak, akinek l´enyeg´eben nincs befoly´asa a j´at´ek menet´ere. V´eg¨ ul a negyedik azt k¨ oveteli meg, ha k´et f¨ uggetlen j´at´ekot j´atszanak ugyanazon j´ at´ekosok, akkor a nyerem´eny¨ uk a k´et j´at´ek ¨osszege lesz. Az igaz´an meglep˝o, hogy van, r´ aad´ asul pontosan egy, Φ f¨ uggv´eny, amely eleget tesz ezeknek a szigor´ u felt´eteleknek. T´ etel 17 (Shapley) A karakterisztikus f¨ uggv´enyek halmaz´ an l´etezik egy egy´ertelm˝ uen meghat´ arozott Φ f¨ uggv´eny, amely eleget tesz az 1-4 axi´ om´ aknak. Tov´ abb´ a X γ(|S|)(v(S) − v(S\{i}), Φi (v) = i∈S⊆I
ahol γ(k) =
(k − 1)!(n − k)! . n!
P´ elda 5. (51; 49, 48, 3)
Φi (v) =
X
γ(|S|)(v(S) − v(S\{i}) =
i∈S⊆I
1 1 1 (1 − 0) = · 2 = , 3! 6 3 i∈S,|S|=2 X
azaz Φ(v) = (1/3, 1/3, 1/3). P´ elda 6. Ingatlanfejleszt´es Φ1 (v) =
2! 1 (v({1}) − v(∅)) + [(v({1, 2}) − v({1})) + (v({1, 3}) − v({1}))]+ 3! 3!
2 2 + (v({1, 2, 3}) − v({2, 3})) = 216666 3! 3 1 2 2 Φ2 (v) = [(v({1, 2}) − v({2})) + (v({1, 2, 3}) − v({1, 3})) = 16666 3! 3! 3 1 2 2 Φ3 (v) = [(v({1, 3}) − v({1})) + (v({1, 2, 3}) − v({1, 2})) = 66666 3! 3! 3 P´ elda 7. ENSZ, Biztons´ agi Tan´acs: (39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1) Egy nem ´ alland´ o i tagra azon S minim´alis koal´ıci´ok eset´en nem nulla a v(S) − v(S\{i}), amelyek mind az ¨ot ´alland´o tagot ´es pontosan h´arom
74
ideiglenes tagot tartalmaznak az i-edik tagon k´ıv¨ ul. Ezek sz´ama γ(9) = 8! 6!/15!, azaz
9 2 ,
m´ıg
!
Φi (v) =
9 8! 6! 4 = ≈ 0, 001865 2 15! 5 · 7 · 11 · 13
Az els˝ o ´es m´ asodik axi´ oma miatt ha j egy ´alland´o tagja a BT-nek, akkor Φj (v) =
8 1 − 7·11·13 1 − 10Φi (v) = ≈ 0, 1963. 5 5
Az ¨ ot ´ alland´ o tag birtokolja teh´at a d¨ont´eshozatal t¨obb, mint 98%-´at, m´ıg az ideiglenes tagok befoly´ asa a 2%-ot sem ´eri el.
75
12. el˝oad´as J´ at´ ekok ´ es d¨ ont´ esek A Shapley t´ etel k¨ ovetkezm´ enyei Az egyszer˝ u j´ at´ekokra (azaz, melyekben a v(S) = 0 vagy 1 minden S koal´ıci´ ora) a Shapley ´ert´ek kisz´am´ıt´asa egyszer˝ us¨odik. Φi (v) =
X
γ(|S|)(v(S) − v(S\{i}),
i∈S⊆I
´es most, v(S) − v(S\{i}) = 1 pontosan akkor, ha v(S) = 1 ´es v(S\{i}) = 0 k¨ ul¨ onben. Legyen Si (i ∈ S ⊆ I) az i-t tartalmaz´o nyer˝o koal´ıci´ok halmaza, melyek az i-t elhagyva m´ ar nem nyer˝ ok. ´Igy Φi (v) =
X
γ(|S|).
i∈S∈Si
P´ elda 1. ENSZ Biztons´ agi Tan´acs Mint l´attuk a d¨ont´eshozatal itt egy (39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1) s´ ulyozott t¨obbs´egi j´at´ek. Ha i egy nem ´alland´o tag ´es S 3 i minim´ alis nyer˝o koal´ıci´o, akkor S pontosan 5 ´alland´o ´es 4 ideiglenes tagb´ ol ´ all. Ezen S halmazok sz´ama 93 , ´ıgy !
Φi (v) =
X i∈S∈Si
γ(|S|) =
X
γ(9) =
i∈S∈Si
9 4 γ(9) = ≈ 0, 001865. 3 3 · 5 · 11 · 13
A szimmetria miatt, ha j egy ´alland´o tag, akkor 1 − 10Φi (v) ≈ 0, 1963, 5 m´ıg az 5 ´ alland´ o tag egyes´ıtett ereje ≈ 0,98153. A p´elda mutatja, hogy egy s´ ulyozott t¨ obbs´egi j´ at´ekban a j´at´ekosok val´odi ereje ´es a szavazataik sz´ ama k¨ oz¨ ott messze nem line´aris a kapcsolat, illetve a gyeng´ebb j´at´ekosok ´erdek´erv´enyes´ıt˝ o k´epess´ege tragikusan kicsi. Elk´epzelhet˝o viszont, hogy 7 ideiglenes tag ¨ osszefog ´es mindig egy¨ utt szavaz. Ekkor egy¨ uttes erej¨ uk 1/6, csak u ´gy, mint az ´ alland´ o tagok´e ebben az esetben, m´ıg a kimarad´o 3 nem ´alland´ o tag ereje nulla! A r´egi tan´acs, divide et impera, matematikailag is al´ at´ amaszthat´ o.16 Φj (v) =
16
Ez´ert is ideiglenesek a tagorsz´ agok, ´ıgy val´ osz´ın˝ utlen az o ¨sszefog´ asuk, illetve k¨ onnyebben befoly´ asolhat´ ok.
76
Egyszer˝ u j´ at´ekok eset´eben eleg´ans val´osz´ın˝ us´egi interpret´aci´oja adhat´o meg a Shapley ´ert´eknek. Egy π permut´aci´oj´ara I-nek egy i elem pivot´ alis, ha az i-t π-ben megel˝ oz˝ o elemek ´altal vesztes, de i-t hozz´av´eve gy˝oztes koal´ıci´ ot alkotnak. Ha egy S nyer˝o, S\ {i} veszt˝o koal´ıci´o, akkor S-re n´ezve (s − 1)!(n − s)! sz´ am´ u permut´aci´oban lesz i pivot´alis, ahol s = |S|. T´ etel 18 Egy v karakterisztikus f¨ uggv´eny˝ u j´ at´ekban Φi (v) egyenl˝ o annak a val´ osz´ın˝ us´eg´evel, hogy i pivot´ alis, amennyiben az I b´ armely permut´ aci´ oj´ at azonos val´ osz´ın˝ us´eggel v´ alasztjuk. P´ elda 2. Az ausztr´ al parlamenti rendszer m˝ uk¨od´ese Az orsz´ ag hat sz¨ ovets´egi ´ allamb´ol ´all, ´es t¨orv´enyeket ezek k´epvisel˝oi, illetve a sz¨ ovets´egi korm´ anyzat hozza. Az elfogad´as felt´etele, hogy legal´abb ¨ot ´allam, vagy k´et ´ allam ´es a sz¨ ovets´egi korm´anyzat t´amogassa az adott t¨orv´enyt. Egy permut´ aci´ oban a sz¨ ovets´egi korm´anyzat pivot´alis, ha a harmadik, a negyedik vagy ¨ ot¨ odik helyen ´ all. Ezek egym´ast kiz´ar´o esem´enyek, val´osz´ın˝ us´eg¨ uk 1/7 + 1/7 + 1/7 = 3/7. Az egyes ´allamok Shapley ´ert´eke egyenl˝o, 4/7 · 1/6 = 2/21, ami a sz¨ ovets´egi korm´anyzat erej´enek k´et kilencede. Felmer¨ ul a k´erd´es, mi a Shapley ´ert´ek ´es az imput´aci´ok kapcsolata. T´ etel 19 Minden n-szem´elyes j´ at´ekra a Φ(v) vektor eleme az imput´ aci´ ok A(v) halmaz´ anak. Bizony´ıt´ as. A 2. axi´ oma szerint ni=1 Φi (v) = v(I), ´ıgy a Pareto optimalit´ as teljes¨ ul. Az egy´eni racionalit´as Φi ≥ v({i}) egyenl˝otlens´egei a k¨ ovetkez˝ ok miatt ´ allnak. El˝osz¨or is a v(S) − v(S \ {i}) ≥ v({i}) a szuperadditivit´ as miatt. Ezzel P
X
Φi (v) ≥
γ(|S|)v({i}) = v({i})
i∈S⊂I
X
γ(|S|) = v({i}),
i∈S⊂I
hiszen X i∈S⊂I
γ(|S|) =
n X n−1 i=1
k−1
!
γ(|k|) =
n X (n − 1)!(k − 1)!(n − k)! i=1
(n − k)!(k − 1)!n!
=
n X 1 i=1
n
= 1.
2 ¨ Osszefoglalva az eddigieket, egy n-szem´elyes j´at´ek elk´epzelhet˝o megold´asai (kifizet´esei) az imput´ aci´ ok A(v) halmaza. Mivel A(v)-t n X
xi = v(I) egyenlet ´es az xi ≥ v({i}) (i ∈ I)
i=1
77
egyenl˝ otlens´egek hat´ arozz´ ak meg, A(v) egy konvex poli´eder. A C(v) meg az A(v)-nek r´esze, ´es szint´en poli´eder, hiszen C(v) = {x ∈ Rn :
X
xi ≥ v(S), S ⊆ I},
i∈S
m´ıg egy stabil B halmazr´ ol tudjuk, hogy C(v) ⊆ B ⊆ A(v). V´eg¨ ul a Shapley ´ert´ek Φ(v) vektora szint´en A(v)-ben van. P´ elda 3. Az ingatlanfejleszt´es “megold´asai” (a koordin´at´akat ezer doll´arban m´erve). 300
x2 6 @ @
@ @ @ A(v) @ Φ(v) = (217, 16, 67) @ @ @ 0 @ b 300 x1 C(v)
x3
300
Csoportok d¨ ont´ eshozatala Az ´eletben gyakran felmer¨ ul, hogy emberek egy csoportj´anak egy probl´ema megold´ as´ anak k¨ ul¨ onb¨ oz˝o alternativ´ait sorba kell rendeznie. P´ elda 1. Egy csal´ ad aut´ ot v´as´arol, ´es a keresked˝o a k¨ovetkez˝o extr´akat aj´ anlja: blokkol´ asg´ atl´ o (ABS), l´egzs´ak (L), l´egkondicion´al´o (AC) ´es sztereo r´ adi´ o (S). Mivel mindet nem engedhetik meg maguknak, mindenki egy fontoss´ agi list´ at ´ all´ıt fel.
78
f´erj
feles´eg
1. gyerek
2. gyerek
ABS AC S L
AC L S ABS
S AC L ABS
AC L ABS-S
A k´erd´es ezek ut´ an: mi legyen a k¨oz¨os sorrend? (Az ABS-S jel¨ol´essel az ´erz´ekeltetj¨ uk, hogy megengedj¨ uk a d¨ontetlent k´et alternat´ıva ¨osszehasonl´ıt´ as´ an´ al.) ´ Altal´ anosan: Adott egy t elem˝ u I halmaz (az egy´enek csoportja) ´es egy A, az alternat´ıv´ ak halmaza. Jel¨olje P az A sorrendjeinek (d¨ontetlent megengedve) a halmaz´ at, ekkor P ×. . .×P = P t a lehets´eges inputok tere, elemei az u ´n. profilok, jel¨ uk (P1 , . . . , Pt ). Egy F : P t → P f¨ uggv´enyt konszenzus f¨ uggv´enynek (social welfare function) h´ıvunk. A c´elunk term´eszetesen a valamely szempontb´ ol ´esszer˝ u konszenzus f¨ uggv´enyek vizsg´alata. P´ elda 1. Az egyszer˝ u t¨ obbs´eg szab´alya Az a, b ∈ A alternat´ıv´ akra a csoport a-t b fel´e helyezi, ha az egy´enek t¨ obbs´ege ezt tette. Sajnos ez a szab´aly nem vezet konszenzus f¨ uggv´enyhez, mint azt az al´ abbi u ´n. szavaz´ oi vagy Condorcet paradoxon mutatja. Legyen I = {1, 2, 3}, A = {a, b, c}. P1 a b c
P2 b c a
P3 c a b
A szab´ aly szerint a megel˝ozi b-t, b megel˝ozi c-t ´es c megel˝ozi a-t, ami a rendez´es tranzitivit´ asa miatt nem lehets´eges. P´ elda 2. Borda ´ert´ek Egy (P1 , . . . , Pt ) ∈ P t -re ´es a ∈ A-ra defini´aljuk a bi (a) ´ert´eket (bi : A → N f¨ uggv´eny) az al´ abbi formul´aval: bi (a) := Pi -ben az a m¨og´e helyezett P alternat´ıv´ ak sz´ ama. A Borda ´ert´ek pedig b(a) := ti=1 bi (a), ´es a csoport xet y el´e helyezi, ha b(x) > b(y). ´Igy val´oban ad´odik egy konszenzus f¨ uggv´eny; tulajdonk´eppen pl. a pontoz´asra alapul´o sport´agakban hasonl´o t¨ort´enik. Egy s´ ulyos ellenvet´es a m´ odszer ellen az al´abbi profil ki´ert´ekel´ese:
79
P1 x
P2 x
y .. .
y .. .
...
Pt−1 x y .. .
Pt y .. .
x Nyilv´ anval´ oan b(y) − b(x) = |A| − 1 − (t − 1) = |A| − t, azaz ha az alternat´ıv´ ak sz´ ama nagyobb, mint a csoport m´erete, akkor az y alternat´ıv´at a csoport x el´e helyezi. ´Igy az ´ert´ekel´es, ha m´as nem, nagyon ´erz´ekeny a hib´ akra, elfogults´ agokra, esetlegesen manipul´aci´okra. P´ elda 3. Lexikografikus rendez´es Helyezz¨ uk x ∈ A-t y ∈ A el´e, ha P1 -ben x megel˝ozi y-t. Ha P1 -ben x ´es y esetleg azonos helyen van, n´ezz¨ uk P2 -t ´es ´ıgy tov´abb. Ez nyilv´anval´oan konszenzus f¨ uggv´eny, s ´ıgy matematikai szempontb´ol semmi baj sincs vele. A sz´ o k¨ oznapi ´ertelm´eben persze sz´o sincs konszenzusr´ol, az egyes j´at´ekos dikt´ ator. Nem k¨ onny˝ u teh´ at minden ig´enynek eleget tev˝o konszenzus f¨ uggv´enyt tal´ alni. Hasonl´ o megk¨ ozel´ıt´est alkalmazunk, mint a Shapley ´ert´ek defin´ıci´oj´ an´ al; megpr´ ob´ alunk axi´ om´akat adni egy megfelel˝o konszenzus f¨ uggv´enyre. Az al´ abbi n´egy axi´ om´ at 1951-ben Arrow fogalmazta meg. Arrow axi´ om´ ak 1. (A konszenzus f¨ uggv´eny ´es az egy´eni ´ert´ekel´esek pozit´ıv asszoci´aci´oja) Ha egy adott profilra a konszenzus f¨ uggv´eny a-t b el´e helyezi, akkor ezt teszi a profil al´ abbi m´odos´ıt´asa ut´an is: (a) Az egy´enek ´ert´ekel´es´eben az alternat´ıv´ak sorrendje a-t kiv´eve nem v´ altozik. (b) Minden ´ert´ekel´esben az a alternat´ıva ´es b´armely m´as alternat´ıva sorrendje v´ altozatlan marad, vagy a jav´ara v´altozik. 2. (F¨ uggetlens´eg az irrevel´ans alternat´ıv´at´ol) Legyen A1 egy tetsz˝oleges r´eszhalmaza az alternat´ıv´aknak. Ha egy profilt u ´gy m´odos´ıtunk, hogy minden egy´en sorrendje az A1 elemei k¨oz¨ott v´altozatlan, akkor a konszenzus f¨ uggv´eny ugyanazt a sorrendet adja A1 elemei k¨oz¨ott az eredeti ´es a m´ odos´ıtott profil eset´eben. 3. (A polg´ arok szuverenit´asa) B´ armely a ´es b alternat´ıv´akra van olyan profil, melyre a konszenzus f¨ uggv´eny a-t b el´e helyezi. 80
4. (Nincs dikt´ ator) Nincs olyan egy´en, aki ha a-t b el´e helyezi, akkor a konszenzus f¨ uggv´eny is ezt teszi, f¨ uggetlen¨ ul a t¨obbi egy´en ´ert´ekel´es´et˝ol. Az Arrow axi´ om´ ak az igazs´agoss´agot ´es az ´esszer˝ us´eget pr´ob´alj´ak megragadni. Ez´ert azt´ an el´egg´e meglep˝o ´es n´emileg tal´an ki´abr´and´ıt´o a k¨ovetkez˝o t´etel. T´ etel 20 (Arrow) Ha t > 1 ´es |A| > 2, akkor nem l´etezik az 1-4 axi´ om´ aknak eleget tev˝ o konszenzus f¨ uggv´eny. Megjegyz´ es: Arrow t´etele r´avil´ag´ıt d¨ont´eshelyzetek bizonyos csapd´aira. Egyik, gyakran megval´ osul´ o megold´as a dikt´ator, egy m´asik v´alaszt´asi lehet˝ os´egek sz˝ uk´ıt´ese kett˝ ore, rossz esetben egyre. A harmadik pedig, hogy felk´esz¨ ul¨ unk a csapd´ akra, ´es megpr´ob´aljuk feloldani a probl´em´at minim´alis igazs´ agtalans´ ag ´ ar´ an.
81
