M´atrixj´at´ekok megold´as´ar´ol (ism´etl´es) M´atrixj´at´ekok ism´etl´es: Legyen adott k´et j´at´ekos, A e´ s B . A k´et j´at´ekos v´eges strat´egia halmazb´ol v´alaszt. Jel¨olje A strat´egia vektor´at u ∈ U , m´ıg B strat´egia vektor´at v ∈ V . A P kifizet´esi m´atrix pij eleme azt mondja meg, hogy ha az A j´at´ekos az i. a B j´at´ekos pedig a j. strat´egi´at v´alasztja, akkor B mennyit fizet A-nak. Adott strat´egi´ak eset´en ekkor w = uT P v
a j´at´ek v´arhat´o e´ rt´eke. A c´elja: lehet˝o legnagyobb nyeres´eg, vagyis maximaliz´alja w-t B c´elja: lehet˝o legkisebb vesztes´eg, vagyis minimaliz´alja w-t
A tiszta strat´egi´aval a biztosan el´erhet˝o nyeres´eg: A eset´en α = maxi minj pij B eset´en β = minj maxi pij
Ha α = β , akkor nyilv´an van tiszta egyens´ulyi strat´egia. Ha α < β (a ≤ nyilv´anval´o) akkor Neumann t´etele alapj´an l´etezik v´arhat´o e´ rt´ekben egyens´ulyi strat´egia.
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Domin´an´alt strat´egi´ak Minden esetben e´ rdemes elhagyni a domin´ans strat´egi´akat. Ez els˝osorban hat´ekonys´agi k´erd´es, ha benn maradnak akkor az optim´alis megold´asban nulla s´ullyal fognak szerepelni. ¨ Osszetett dominanci´at (mikor kever strat´egia egy¨uttesek domin´alnak m´as strat´egi´akat) m´ar nem e´ rdemes keresni, hiszen a´ ltal´anosan az ugyanolyan k¨olts´eges mint maga az egyens´uly megkeres´ese. Tekints¨uk p´eldak´ent a
2 1 3 -1 3 0 1 1 4 strat´egia m´atrixot. Ebben a 3. oszlop domin´alt. Elhagyva viszont a 3. sor v´alik azz´a, ´ıgy a reduk´alt feladat egyszer˝uen
2 1 -1 3
alakban ´ırhat´o. ´ Erdekess´ egk´eppen megjegyezz¨uk, hogy 2 × 2-es feladatokra egzakt k´eplet adhat´o (mivel a strat´egi´ak fel´ırhat´ok (λ, 1 − λ) alakban).
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
´ strat´egia megfogalmaz´asa line´aris programoz´asi Az egyensulyi feladatk´ent Neumann t´etel´enek bizony´ıt´asakor l´attuk, hogy b´armely u ∈ U strat´egia, e´ s optim´alis u∗ ∈ U e´ s v∗ ∈ V strat´egi´ak eset´en uT P v∗ ≤ u∗T P v∗ = w∗
A fenti o¨ sszef¨ugg´es pontosan akkor a´ ll fenn minden u kevert strat´egi´ara, ha az egys´eg vektorokra fenn´all. Vagyis ha P v∗ ≤ w ∗ 1
A B j´at´ekos olyan optim´alis v ∗ strat´egi´at keres, melyre w∗ minim´alis (hiszen ennyit fizet A-nak). Tudjuk, hogy a kevert strat´egi´akat olyan nemnegat´ıv vektorok, melyek koordin´at´ainak o¨ sszege 1. A B j´at´ekos optim´alis (egyens´ulyi) strat´egi´aj´at a k¨ovetkez˝o line´aris programoz´asi feladat adja meg: min w∗ P v∗ ≤ w ∗ 1 1T v∗ = 1 v∗ ≥ 0
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A feladat a´ tfogalmaz´asa Tegy¨uk fel egy pillanatra hogy w∗ > 0. Ekkor az x = 1T x = w1∗ , a k¨ovetkez˝o rendszert kapjuk. min w∗ P v∗ ≤ w ∗ 1 1T v∗ = 1 v∗ ≥ 0
1 ∗ w∗ u
≥ u´ j ismeretlent haszn´alva, mivel
max 1T x Px ≤ 1 x≥0
Hasonl´oan j´arhatunk el az A j´at´ekos egyens´ulyi strat´egi´aj´anak keres´esekor. A k¨ovetkez˝o rendszer ad´odik, az anal´og a´ t´ır´as ut´an: max w∗ u∗T P ≥ w∗ 1 1T u∗ = 1 u∗ ≥ 0
min 1T y yT P ≥ 1T y≥0
Az optim´alis strat´egi´at nyilv´an a w∗ -al val´o vissza szorz´as ut´an kapjuk. Vegy¨uk e´ szre azonban, hogy a k´et fenti a´ tsk´al´azott feladat egym´asnak prim´al-du´al p´arja, ´ıgy el´eg az egyik feladatot megoldani, abb´ol mindk´et j´at´ekos strat´egi´aj´at megkapjuk (mint prim´al megold´as, e´ s mint du´al v´altoz´ok).
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A sk´al´az´asr´ol e´ s az elj´ar´as o¨ sszefoglal´asa Az a´ t´ır´asn´al felhaszn´altuk hogy w∗ > 0. Ha α = β teljes¨ult, vagyis volt tiszta strat´egia, akkor term´eszetesen nem e´ rdemes fel´ırni a line´aris programoz´asi feladatot, ´ıgy α < w∗ < β feltehet˝o. Ha α ≥ 0 k´eszen vagyunk. Ha α < 0 akkor P minden elem´ehez ugyanazt a kell˝oen nagy pozit´ıv c konstansot adva egy olyan feladatot nyer¨unk, melynek egyens´ulyi megold´asai megegyeznek az eredeti feladat´eval, azonban α ≥ 0 teljes¨ul. Vegy¨uk e´ szre, hogy ugyanezen elj´ar´assal tetsz˝oleges m´atrix j´at´ekot igazs´agoss´a lehet tenni. A m´atrix j´at´ekok megold´as´at teh´at az al´abbiakban foglalhatjuk o¨ ssze: 1. Megkeress¨uk e´ s elhagyjuk a domin´alt strat´egi´akat. 2. Kisz´am´ıtjuk az α e´ s a β e´ rt´ekeket. 3. Ha α = β akkor van tiszta strat´egia, melyeket a min max formula megold´asa egyben meg is hat´arozott. 4. Ha nem, konstans eltol´assal el´erj¨uk hogy w∗ > 0 teljes¨ulj¨on. 5. Fel´ırjuk a megfelel˝o line´aris programoz´asi feladatot, melynek optim´alis prim´al-du´al megold´as p´arja megadja az optim´alis strat´egi´ak szerkezet´et. 6. Visszask´al´azunk w∗ -val. Ne feledj¨uk, hogy a fel´ırt line´aris programoz´asi feladatnak mind´ıg van optim´alis megold´asa. Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A k´et ujjas malom j´at´ek megold´asa (ism´etl´es) Eml´ekezz¨unk vissza, hogy a k´etujjas malomj´at´ek kifizet´es m´atrixa ferd´en szimmetrikus, teh´at a j´at´ek e´ rt´eke w∗ = 0, ez´ert, ha a j´at´ekot line´aris programoz´asi modell seg´ıts´eg´evel szeretn´enk megoldani, akkor a kifizet´esi m´atrix elemeit n¨ovelni kell. Legyen
1 3 −2 1 −1 1 1 4 Pˆ = P + E = 4 1 1 −3 1 −2 5 1
a m´odos´ıtott m´atrix (minden elem´ehez 1-et adtunk hozz´a). Ekkor a j´at´ek e´ rt´eke 1 lesz. MATLAB Fel´ırva a line´aris programoz´asi feladatot a l´atott m´odon, majd megoldva azt az ∗
∗
x =y =
3 2 0, , , 0 5 5
optim´alis strat´egi´akat kapjuk. Mivel a j´at´ek szimmetrikus volt, nem meglep˝o hogy a strat´egi´ak is azonosak. Megjegyezz¨uk, hogy term´eszetesen lehetn´enek alternat´ıv optim´alis strat´egi´ak is, ´ıgy ez a jelens´eg nem t¨orv´enyszer˝u. Val´oban a jelenlegi feladatnak is van alternat´ıv optimuma: x∗2
=
y2∗
=
4 3 0, , , 0 7 7
Ezen strat´egi´ak tetsz˝oleges konvex kombin´aci´oja optim´alis. Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A Blotto j´at´ek megold´asa Eml´ekezz¨unk vissza a Blotto j´at´ekra: Blotto gener´alisnak m, az ellens´egnek n hadoszt´alya van, r sz´am´u (k¨ul¨onb¨oz˝o vagy azonos e´ rt´ek˝u) c´elpont elfoglal´as´ara (legyen m ≥ n). A hadoszt´alyok tov´abb nem oszthat´ok e´ s a c´elpontok b´armely t´uler˝ovel elfoglalhat´ok. Egyenl˝o er˝ok eset´en a c´elpont egyik f´el birtok´aba sem ker¨ul. Hogyan ossza meg Blotto (´es az ellens´eg) az er˝oit, ha a j´at´ekosok a´ ltal elfoglalt c´elpont-egy¨uttesek e´ rt´ek¨osszeg´et tekintve a k¨ul¨onbs´eg maximaliz´al´asa (illetve az ellens´eg r´esz´er˝ol a minimaliz´al´asa) a c´el? Legyen c1 , c2 , . . . , cr a c´elpontok e´ rt´eke, melyekre fenn´all a c1 > c2 > · · · > cr rel´aci´o. Ekkor ha Blotto a B j´at´ekos, akkor strat´egi´ait a {m1 , . . . , mr }, m1 , . . . , mr ∈ N, m1 + · · · + mr = m
alak´u sorozatok hat´arozz´ak meg, ahol mi azt adja meg, hogy az i. c´elponthoz h´any hadoszt´alyt k¨uld. Hasonl´oan az ellens´eg (A j´at´ekos) strat´egi´ai ekkor {n1 , . . . , nr }, n1 , . . . , nr ∈ N, N1 + · · · + nr = n
alak´uak. K¨onnyen l´athat´o, hogy B strat´egi´ainak a sz´ama
„
m+r−1 m
«
, m´ıg A eset´en
„
n+r−1 n
«
.
(i) (j) (j) Legyen B e´ s A strat´egia v´alaszt´asai Ai = m(i) 1 , . . . , mr illetve Bj = n1 , . . . , nr . Ekkor a kifizet´esi m´atrix megfelel˝o eleme
pij =
X (i)
ck − (j)
mk >nk
X (i)
ck = (j)
mk
X
(i) (j) ck ∗ mk − nk
k
hiszen az egyes c´elpontok elfoglal´asa csak a t´uler˝o megl´et´en vagy hi´any´an m´ulik. Ill´es Tibor
E¨o•tv¨ os•Lor´ Tudom´ nyegyetem •First •Prev Next Last a•nd Go Back •FullaScreen •Close •Quit
Blotto: m = 2, n = 3, r = 2, c1 = 2, c2 = 1. (volt 1-es HF) A l´atott k´eplet seg´ıts´eg´evel az optim´alis strat´egi´akat k¨onnyen meghat´arozhatjuk. B1 B2 B3 B4 B5
= {4, 0} = {3, 1} = {2, 2} = {1, 3} = {1, 4}
A1 = {3, 0} A2 = {2, 1} A3 = {1, 2} A4 = {0, 3} 2 1 1 1 1 2 1 1 −1 1 2 1 −1 −1 1 2 −1 −1 −1 1
Mivel β = max{1, 1, −1, −1, −1} = 1, α = min{2, 2, 2, 2} = 2
vagyis a j´at´eknak nincs tiszta egyens´ulyi strat´egi´aja, ´ıgy megoldjuk a j´at´ekhoz tartoz´o line´aris programoz´asi feladatot (miut´an elhagyjuk utols´o sort, mely domin´alt strat´egia). MATLAB Az optim´alis megold´as (u Blotto eset´en e´ s v az ellens´eg eset´en). A j´at´ek e´ rt´eke 1.1. u=
5 3 1 1 1 1 3 5 . , , , ,0 , v = , , , 10 10 10 10 10 10 10 10
Vagyis nem meglep˝o m´odon, Blottonak els˝osorban a leg´ert´ekesebb c´elpontot kell t´amadnia (hiszen az esetek fel´eben erej´enek megoszt´asa n´elk¨ul azt t´amadja). Figyelj¨uk meg tov´abb´a, hogy a tiszta strat´egia 1 egys´eg nyeres´eget garant´alt volna, m´ıg a kevert strat´egia v´arhat´o e´ rt´ekben enn´el 10%-al nagyobb nyeres´eget eredm´enyez. Ill´es Tibor
E¨o•tv¨ os Lor´and Tudom´anyegyetem •First •Prev Next •Last •Go Back •Full Screen •Close •Quit
P´arbaj j´at´ekok A j´at´ek sor´an a k´et j´at´ekos s sz´am´u poz´ıci´ot foglalhat el egym´assal szemben. Az els˝o, kezd˝o poz´ıci´oban vannak egym´ast´ol a legt´avolabb, ebben a poz´ıci´oban a legkisebb a tal´alati val´osz´ın˝us´eg. A j´at´ekosok b´armely poz´ıci´oban kil˝ohetnek egy goly´ot ellenfel¨ukre. Ha valamely poz´ıci´oban nincsen l¨ov´es, vagy van l¨ov´es, de nincsen tal´alat, akkor a j´at´ek a k¨ovetkez˝o poz´ıci´oban - egym´ashoz k¨ozeledv´en - folytat´odik eg´eszen addig, am´ıg tal´alat nem esik, vagy m´ar egyik j´at´ekosnak sem marad goly´oja. A kifizet´esek: +1, ha csak a J1 j´at´ekos tal´al, e´ s -1, ha csak a J2 j´at´ekos tal´al, egy´ebk´ent (egyik sem, vagy mindkett˝o tal´al) z´erus. A l¨ov´esek optim´alis id˝oz´ıt´ese a k´erd´es: magasabb sorsz´am´u poz´ıci´oban (kisebb t´avols´agr´ol) n˝o a tal´alati val´osz´ın˝us´eg, viszont n˝o annak a val´osz´ın˝us´ege is, hogy az ellenf´el tal´al. Legyen az A j´at´ekos tal´alati val´osz´ın˝us´ege: 0 < p1 < p2 < . . . < ps ≤ 1 m´ıg a B j´at´ekos tal´alati val´osz´ın˝us´ege: 0 < q1 < q2 < . . . < qs ≤ 1. csendes p´arbaj: a j´at´ekosnak nincsen tudom´asuk arr´ol, hogy az ellenf´el l˝ott, de c´elt t´evesztett hangos p´arbaj: a j´at´ekosnak tudom´asuk van arr´ol, hogy az ellenf´el l˝ott, de c´elt t´evesztet A hangos p´arbajok a´ ltal´aban nyeregpontos j´at´ekok (gondoljunk arra, hogy ha az ellenf´el l¨ov´es´et hallottuk de mi m´eg nem l˝ott¨unk, akkor nyilv´an mi k¨ozvetlen k¨ozelr˝ol ki fogjuk v´egezni ellenfel¨unk). A p´arbaj ”j´at´eknak” ismert t¨obb goly´os v´altozata is, mikor a j´at´ekosok adott sz´am´u goly´oval gazd´alkodhatnak. ´ Erdemes elgondolkodni hogy mit is jelent egy kevert strat´egia egy p´arbaj eset´en, ahol j´o es´ellyel csak 1 fordul´o van. Gondoljunk arra, hogy ellenfel¨unk lehet gyakorlott p´arbajoz´o, aki m´ar kitapasztalta az a´ ldozataira jellemz˝o viselked´est! Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A p´arbaj kifizet´esi m´atrixa Tekints¨uk az 1 − 1 goly´os csendes p´arbajt (az o¨ sszes t¨obbi eset hasonl´oan kezelhet˝o, csup´an t¨obb goly´os esetben a k´epletek bonyolultabbak). 1. Ha i < j akkor el˝obb az A j´at´ekos l˝o. A tal´alat val´osz´ın˝us´ege pi , a c´elt´eveszt´es´e 1 − pi . Nyilv´an, a B j´at´ekos m´ar csak akkor l˝ohet, e´ s tal´alhat qj val´osz´ın˝us´eggel, ha t´ul´elte A l¨ov´es´et. ´Igy a kifizet´es pij = pi − (1 − pj )qj .
2. Ha i > j eset´en hasonl´o gondolatmenettel pij = −qj + (1 − qj )pi .
3. Ha i = j akkor a k´et f´el egyszerre l˝o. Mivel a kifizet´es csak akkor nem z´erus ha csak az egyik f´el tal´al, ´ıgy pij = pi (1 − qi ) − qi (1 − pj ) = pi − qi .
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Egy konkr´et csendes, 1 − 1 goly´os p´arbaj Tegy¨uk fel hogy k´et p´arbajoz´o A e´ s B k¨oz¨ul A jobban c´eloz. Mi lehet ekkor B legjobb es´elye? A tal´alati val´osz´ın˝us´egek legyenek PA =
1 1 3 1 1 1 , , ,1 PB = , , ,1 4 2 4 4 3 2
A kifizet´es m´atrix
0
0
P =
1 8 5 16 1 2
1 6 1 6 1 3
− 12 1 0 4 1 1 4 2 0 0
− 81
Mivel 1 1 1 α = max − , 0, , 0 = , 2 6 6
β = min
1 1 1 1 , , , 2 3 4 2
1 = , 4
´ıgy itt sincs tiszta strat´egia. Megfigyelhetj¨uk, hogy az els˝o e´ s a m´asodik sor domin´alt. A megmarad´o kifizet´esi m´atrix els˝o e´ s negyedik oszlopa szint´en domin´alt, ´ıgy el´eg lenne egy 2 × 2-es m´atrix´u feladatot megoldanunk, azonban pr´ob´aljuk most ki mi t¨ort´enik ha ezeket a feladatban hagyjuk. MATLAB Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A p´arbaj folytat´asa A j´at´ek e´ rt´eke 0.2, vagyis ahogy azt gondolhattuk, a k´et f´el nem azonos es´elyekkel indul. Az optim´alis strat´egi´ak (u A eset´en e´ s v az ellenf´el eset´en) u=
4 1 0, 0, , 5 5
, v=
3 2 0, , , 0 . 5 5
Vagyis a gyeng´ebben c´elz´o j´at´ekosnak, ahogy azt v´artuk k¨ozelebb kell mennie, vagyis a 2-es vagy 3-as poz´ıci´or´ol l˝onie, m´ıg a jobban c´elz´o j´at´ekos 14 es´ellyel m´ar a kezd˝o 4. poz´ıci´or´ol megpr´ob´alhatja eltal´alni ellenfel´et. Megfigyelhetj¨uk, hogy a domin´alt strat´egi´ak e´ rt´eke a kapott megold´asban term´eszetesen nulla e´ rt´ek˝uek.
A k¨ovetkez˝okben r¨oviden ismertet¨unk (´atism´etl¨unk?) n´eh´any egyszer˝u, klasszikus elj´ar´ast line´aris programoz´asi feladatok megold´as´ara. Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
START
A (prim´al) szimplex m´odszer
El˜ofeldolgoz´as
bemen˝o adatok: a kanonikus (P) feladat AB prim´al megengedett b´azis´ahoz tartoz´o TB (r¨ovid) b´azis t´abla begin I− := {i ∈ IN |ci < 0}; while (I− 6= ∅) do legyen q ∈ I− tetsz˝oleges; if(tq ≤ 0) then STOP: a feladat nem korl´atos; else o n bi legyen ϑ := min tiq : i ∈ IB , tiq > 0 bp tpq
legyen p ∈ IB tetsz˝oleges, melyre = ϑ; endif pivot´al´as: IB := IB ∪ {q} \ {p}; az I− indexhalmaz meghat´aroz´asa; endwhile I− = ∅ akkor optim´alis megold´asn´al vagyunk; end
Kezdõbázis meghatározása
I− meghat´aroz´asa
I− 6= ∅
igaz
ciklusmag
hamis I− = ∅
optimális megoldás
STOP
ciklusmag:
q ∈ I− tetsz˜oleges igaz tq ≤ 0
STOP: A feladat nem korl´atos
hamis prim´al h´anyadosteszt min{ tbiqi : i ∈ IB tiq > 0} Pivot´al´as a tqs elemen i ∈ IB , tiq > 0
I− meghat´aroz´asa
1. ´abra. Szimplex m´odszer.
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
P´elda a szimplex algoritmusra Oldjuk meg a k¨ovetkez˝o feladatot (El˝obb a´ t kell alak´ıtanunk a fenti feladatot kanonikus LPfeladatt´a): min(−x1 − 2x2 − 4x3 − x4 ) x1 + x3 + x4 ≤ 5 x1 + x2 + x4 ≤ 6 x3 ≤ 7 x1 , x2 , x3 , x4 ≥ 0
min(−x1 − 2x2 − 4x3 − x4 ) x1 + x3 + x4 + u1 = 5 x1 + x2 + x4 + u2 = 6 x3 + u3 = 7 x1 , x2 , x3 , x4 , u1 , u2 , u3 ≥ 0
(1)
Megold´as a Szimplex-algoritmussal (balr´ol-jobbra, fentr˝ol-lefele): u1 u2 u3
c
x1
x2
x3
x4
u1
u2
u3
b
1 1 0 -1
0 1 0 -2
1 0 1 -4
1 1 0 -1
1 0 0 0
0 1 0 0
0 0 1 0
5 6 7 0
x1
x2
x3
x4
u1
u2
u3
b
x1 u2 u3
c
x1
x2
x3
x4
u1
u2
u3
b
1 0 0 0
0 1 0 -2
1 -1 1 -3
1 0 0 0
1 -1 0 1
0 1 0 0
0 0 1 0
5 1 7 5
x1
x2
x3
x4
u1
u2
u3
b
1 0 1 1 1 0 0 5 x3 1 0 1 1 1 0 0 5 x2 1 1 0 1 0 0 1 -1 0 -1 1 0 1 1 0 6 0 0 1 0 0 0 1 7 u3 -1 0 0 -1 -1 0 1 2 c 0 0 -5 0 -1 2 0 7 c 5 0 0 5 4 2 0 32 Teh´at a keresett megold´as az x1 = 0, x2 = 6 e´ s x3 = 5. A minim´alis c´elf¨uggv´eny e´ rt´ek 32. Ha a c´elf¨uggv´eny(c) sor´aban pozit´ıv sz´am szerepel e´ s nincs f¨ol¨otte pozit´ıv, akkor nincs megold´asa a feladatnak. x1 x2 u3
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Az MBU szimplex m´odszer START
bemen˝o adatok: a kanonikus (P) feladat AB prim´al megengedett b´azis´ahoz tartoz´o TB (r¨ovid) b´azis t´abla begin I− := {i ∈ IN |ci < 0}; while(I− 6= ∅)do legyen s ∈ I− tetsz˝oleges vezet˝o v´altoz´o; while(s ∈ I− )do legyen Ks = {i ∈ IB |tis > 0}; if(Ks = ∅) then STOP: a D = ∅; else legyen ϑ := min{ txisi |i ∈ Ks }; r ∈ IB tetsz˝oleges, melyre tbrsr = ϑ e´ s θ1 := |ctrss | ; J = {i ∈ I|ci ≥ 0}, e´ s q ∈ IN : θ2 = |tcrqq | if (J = ∅) θ2 := ∞ else θ1 := min{ |tcrii | |i ∈ J }, q ∈ IN : θ2 = |tcrsq | ; endif if(θ1 ≤ θ2 ) then pivot´al´as a trs elemen else pivot´al´as a trq elemen endif hat´arozzuk meg az I− halmazt; endif endwhile endwhile I− = ∅ akkor optim´alis megold´asn´al vagyunk; end
El˜ofeldolgoz´as
Kezdõbázis meghatározása
I− meghat´aroz´asa
I− 6= ∅
igaz
ciklusmag
hamis I− = ∅
optimális megoldás
STOP
ciklusmag: s ∈ I− vez´erv´altoz´o kiv´alaszt´asa
s ∈ I−
igaz
Ks = {i ∈ IB |tis > 0} meghat´aroz´asa
hamis Ks = ∅
igaz
STOP: D = ∅ Du´al nem megengedett feladat
hamis θ1 := |ctrss | θ2 = |tcrqq | J = {i ∈ I|ci ≥ 0} igaz
J =∅
θ2 := ∞
hamis θ1 := min{ |tcrii | |i ∈ J } cq θ2 = |trs | θ1 ≤ θ 2
igaz
pivot´al´as a trs elemen
hamis pivot´al´as a trq elemen I− meghat´aroz´asa
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
P´elda az MBU szimplex algritmusra A simplex algoritmusn´al l´atott p´eld´ab´ol indulunk, ugyanazon a´ talak´ıt´as ut´an. Megold´as az MBUszimplex algoritmussal: min(−x1 − 2x2 − 4x3 − x4 ) x1 + x3 + x4 ≤ 5 x1 + x2 + x4 ≤ 6 x3 ≤ 7 x1 , x2 , x3 , x4 ≥ 0
u1 u2 u3
c
x1
x2
x3
x4
u1
u2
u3
b
1 1 0 -1
0 1 0 -2
1 0 1 -4
1 1 0 -1
1 0 0 0
0 1 0 0
0 0 1 0
5 6 7 0
Folytat´as az MBU Szimplex-algoritmussal (balr´ol-jobbra, fentr˝ol-lefele): x1 u2 u3
c
x1
x2
x3
x4
u1
u2
u3
b
1 0 0 0
0 1 0 -2
1 -1 1 -3
1 0 0 0
1 -1 0 1
0 1 0 0
0 0 1 0
5 1 7 5
x1
x2
x3
x4
u1
u2
u3
b
1 1 0 1
1 0 0 0
0 1 1 -4
1 1 0 1
0 1 0 0
1 0 0 2
0 0 1 0
6 5 7 c 12 Teh´at a megold´as x2 = 6 e´ s x3 = 5. ´Igy a algoritmusn´al is megkaptuk. x2 u1 u3
Ill´es Tibor
x1 u1 u3
c x2 u1 u3
c
x1
x2
x3
x4
u1
u2
u3
b
1 0 0 0
1 -1 0 -1
0 1 1 -4
1 0 0 0
0 1 0 0
1 -1 0 1
0 0 1 0
6 -1 7 6
x1
x2
x3
x4
u1
u2
u3
b
1 1 -1 5
1 0 0 0
0 1 0 0
1 1 -1 5
0 1 -1 4
1 0 0 2
0 0 1 0
6 5 2 32
minim´alis e´ rt´ek 32, ahogy ezt m´ar a SzimplexE¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Megengedett indul´o b´azis el˝oa´ ll´ıt´asa Tegy¨uk fel, hogy a megoldand´o feladatunk Ax = b, x, b ≥ 0 alak´u. Ha kezdetben nem ilyen a feladat, akkor u´ n. slack v´altoz´ok bevezet´es´evel (hozz´aad´as´aval, kivon´as´aval) ilyen alakra hozzuk. A megengedett megold´as az al´abbi feladat megold´as´aval kereshet˝o: max 1T Ax, Ax + Iu = b, x, u ≥ 0,
ahol u jel¨oli a bevezetett mesters´eges slack v´altoz´okat. Ennek a feladatnak l´etezik optim´alis megold´asa, ugyanis (1T A)x ≤ 1T b. A min(1T A)x = 1T b akkor e´ s csak akkor, ha l´etezik olyan x vektor, hogy Ax = b, x ≥ 0. Ekkor a be´agyazott feladatnak az (x, u) optim´alis megold´asa, akkor e´ s csak akkor ha u = 0. Ilyen esetekben l´ep¨unk a´ t a prim´al szimplex m´odszerben a m´asodik f´azisba, e´ s ekkor elhagyjuk a slack v´altoz´ok oszlop´at, illetve a m´asodlagos c´elf¨uggv´eny sor´at. A k¨ovetkez˝okben megismerked¨unk a criss-cross algoritmussal, hol nincs sz¨uks´eg els˝o f´azis feladatra. Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
A Criss-Cross m´odszer bemen˝o adatok: egy (P) feladat r¨ovid (b´azis) t´abl´aja, nem megengedett v´altoz´ok I− indexhalmaza begin while (I− 6= ∅) do
START
El˜ofeldolgoz´as
Bázis meghatározása
I− meghat´aroz´asa
p := min{i ∈ IB : bi < 0}; q := min{j ∈ IN : cj < 0}; r := min{p, q};
if(r = p) then if (t(p) ≥ 0) then STOP: a P = ∅; else legyen q := min{j ∈ IN : tpj < 0}; endif else if(trq ≤ 0) then STOP: a D = ∅; else legyen p := min{i ∈ IB : tiq > 0}; endif endif pivot´al´as a (p,q) poz´ıci´on; IB := IB ∪ {q} \ {p}; hat´arozzuk meg az I− halmazt; endwhile STOP: optim´alis megold´asn´al vagyunk; end
igaz
I− 6= ∅
ciklusmag
hamis I− = ∅
optimális megoldás
STOP
ciklusmag: p := min{i ∈ IB : bi < 0} q := min{j ∈ IN : cj < 0} r := min{p, q} r=p
igaz
hamis STOP: D = ∅ igaz du´al nem megengedett a feladat
trq ≤ 0
t(p) ≥ 0
igaz
hamis
STOP: P = ∅ prim´al nem megengedett a feladat
q := min{j ∈ IN : tpj < 0} meghat´aroz´asa
hamis
p := min{i ∈ IB : tiq > 0} meghat´aroz´asa pivot´al´as a (p,q) poz´ıci´on
I− meghat´aroz´asa
1. ´abra. Criss-Cross-m´odszer.
Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
P´elda a Criss-Cross algoritmusra A m´ar j´ol ismert p´eld´ankat oldjuk meg ez alkalommal a Criss-Cross algoritmussal.
min(−x1 − 2x2 − 4x3 − x4 ) x1 + x3 + x4 ≤ 5 x1 + x2 + x4 ≤ 6 x3 ≤ 7 x1 , x2 , x3 , x4 ≥ 0
Megold´as (balr´ol-jobbra, fentr˝ol-lefele): x1
x2
x3
x4
u1
u2
u3
b
1 0 0 0
0 1 0 -2
1 -1 1 -3
1 0 0 0
1 -1 0 1
0 1 0 0
0 0 1 0
5 1 7 5
x1
x2
x3
x4
u1
u2
u3
b
1 0 1 1 1 0 0 5 x3 1 0 1 -1 0 -1 1 0 1 x2 1 0 0 1 0 0 0 1 7 u3 -1 0 0 -5 0 -1 2 0 7 5 A megold´as az x2 = 6 e´ s x3 = 5 e´ s a minim´alis e´ rt´ek 32.
0 1 0 0
1 0 0 0
1 1 -1 5
1 0 -1 4
0 1 0 2
0 5 0 6 -1 2 0 32
u1 u2 u3
x1
x2
x3
x4
u1
u2
u3
b
1 1 0 -1
0 1 0 -2
1 0 1 -4
1 1 0 -1
1 0 0 0
0 1 0 0
0 0 1 0
5 6 7 0
x1
x2
x3
x4
u1
u2
u3
b
x1 x2 u3
Ill´es Tibor
x1 u2 u3
E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Bim´atrix j´at´ekok Egy bim´atrix j´at´ekban a k´et j´at´ekos A e´ s B hasonl´oan mint eddig, v´eges strat´egia halmazb´ol v´alaszt, azonban a kifizet´esek nem szimmetrikusak, hanem egy A e´ s B kifizet´esi m´atrix ´ırja le azokat a k´et j´at´ekos saj´at szemsz¨og´eb˝ol. Tipikus ilyen feladat volt a fogoly dilemma: • gyan´us´ıtottak J1 e´ s J2 • nincsen elegend˝o bizony´ıt´ek • a gyan´us´ıtottak elk¨ul¨on´ıtik e´ s kihallgatj´ak • ha valamelyik¨uk vall (´es a m´asik tagad), akkor az, aki vallott, enyh´ebb b¨untet´est kap, esetleg
szabadl´abra ker¨ul, s˝ot jutalmat is kaphat az egy¨uttm˝uk¨od´es´ert • a j´at´ekosok lehets´eges strat´egia halmazai S1 = {V, T } e´ s S2 = {V, T } T´abl´azatban rendszerezve a hasznoss´agf¨uggv´eny eredm´eny´et kifizet´esi m´atrixot kapunk. Q 2. 1.Q
V T V (-2,-2) (3,-3) T (-3,3) (2,2)
Megmutatjuk, hogyan lehet a bim´atrix j´at´ekokat a´ t´ırni line´aris komplementarit´asi feladatt´a. Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Szok´as szerint jel¨olje x e´ s y j´at´ekosaink kevert strat´egi´aj´at. K¨onny˝u l´atni, hogy a v´arhat´o nyeres´eg a j´at´ekosok ezen strat´egi´aja mellett e´ ppen az xT Ay illetve az xT By. Hasonl´oan mint kor´abban, az x∗T Ay∗ ≥ xT Ay∗ minden x ∈ ∆n eset´en felt´etel ekvivalens az x∗T Ay∗ ≥ Ai y,
minden i ∈ {1, . . . , n} eset´en,
ahol Ai az A m´atrix i. sora. A felt´eteleket o¨ sszevonva: (x∗T Ay∗ )em ≥ Ay∗
ahol em = (1, . . . , 1)T ∈ Rm . Hasonl´o gondolatmenettel ad´odik, hogy (x∗ ,y∗ ) ∈ ∆n × ∆m egyens´ulyi p´ar, akkor e´ s csak akkor, ha (x∗T Ay∗ )en ≥ Ay∗ (x∗T By∗ )em ≥ (x∗T B)T = B T x¯
L´attuk, feltehet˝o hogy A e´ s B minden eleme pozit´ıv (+c). Emiatt (xT Ay∗ ) > 0 e´ s (x∗T By∗ ) > 0 is feltehet˝o. Bevezetve a ξ = x∗ /(x∗T By∗ ), illetve η = y∗ /(xT Ay∗ ) v´altoz´okat, illetve az u, v elt´er´es v´altoz´okat, a k¨ovetkez˝o rendszert kapjuk: u 0 + BT v
Megmutathat´o, hogy az x∗ = ξ/ feladatnak.
Pn
i=1 ξ i
ξ en A = 0 η em ξ u · = 0 v η u ξ , ≥ 0 v η
, illetve az y = η/
Pm
i=1 η i
egyens´ulyi pontja az eredeti
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
Megjegyz´esek A bim´atrix j´at´ekokat szokt´ak kvadratikus feladatt´a a´ t´ırni. Ennek el˝onye, hogy a (konvex) kvadratikus feladatokat kezelni k´epes megold´ok l´enyegesen elterjedtebbek mint a line´aris komplementarit´asi feladatok´e. Az el˝obbiekben levezetett line´aris komplementarit´asi feladatot p´eld´aul a h´ıres Lemke algoritmussal lehet megoldani. A bemutatott pivot elj´ar´asok kis m´eretben nagyt´abl´as megval´os´ıt´as esetben is k´epesek megoldani a feladatokat. Nagyobb m´eretben azonban fejlettebb technik´akra van sz¨uks´eg, mint amilyen a m´odos´ıtott szimplex algoritmus, vagy a numerikus kerek´ıt´esi hiba korl´atok finom o¨ sszehangol´asa. Ill´es Tibor
E¨otv¨os Lor´and Tudom´anyegyetem
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit
