Mi a megoldása az n×n-es mátrixjátéknak?
Adott egy X = [ x11 ... x1n ; ...; xn1 ... xnn ] négyzetes mátrix, és keressük az a = [a1, ..., an-1, 1 - (a1 + ... + an-1)] és a b = [b1, ..., bn-1, 1 - (b1 + ... + bn-1)]^T vektorokat, melyekre fennáll minden i-re és j-re, hogy a × X[i,*] = X[*,j] × b = v, ahol v a játék értéke, amit szintén keresünk. 2×n egyenlet és 2×(n-1)+1 változó, tehát pont megoldhatónak kellene lennie.
Elég, ha könnyen implementálható algoritmust adtok rá, de a szép matematikai formulákat is értékelni fogom.
válasza:Az adott probléma megoldható lineáris programozás (LP) segítségével, amely egy olyan matematikai módszer, amelynek célja egy lineáris célfüggvény optimumát találni lineáris korlátok mellett. Az LP megoldása gyorsan elvégezhető, és garantálja az optimális megoldást.
Az első lépés a lineáris korlátok megadása. Az a × X[i,] = X[,j] × b egyenlet azt jelenti, hogy a két oldal egyenlő, így átrendezve és kifejezve az összes változót, a következő lineáris korlátokat kapjuk:
a1x11 + a2x12 + ... + anx1n - x1jb1 - x2jb2 - ... - xnjbn-1 = 0
a1x21 + a2x22 + ... + anx2n - x2jb1 - x3jb2 - ... - xnjbn-1 = 0
...
a1xn1 + a2xn2 + ... + anxnn - xnjb1 - xn-1jb2 - ... - x1jbn-1 = 0
Az összes i és j indexre szükséges lineáris korlátot felírva, egy n x n-es egyenletrendszert kapunk, amelyben (n-1) + (n-1) + 1 = 2n-1 ismeretlen változó van. Az egyenletrendszer mátrix alakja az alábbi lesz:
[ x11 x12 ... x1n -b1 -b2 ... -bn-1 0 ]
[ x21 x22 ... x2n 0 -b1 ... -bn-1 0 ]
[ . . . . . . . . ]
[ xn1 xn2 ... xnn -bn-1 ... -b2 -b1 ]
Az utolsó oszlopban a játék értéke v található, amelyet a célfüggvény segítségével keresünk. A célfüggvény az alábbi lesz:
maximize v
A lineáris korlátok és a célfüggvény megadása után, az LP megoldó algoritmus a leghatékonyabb vektort fogja kiszámítani a megadott korlátok mellett. Az LP megoldása azonban csak egy megoldást ad, és nem garantálja, hogy ez az egyetlen vagy a legjobb megoldás. Azonban ha a korlátok jól vannak megadva, akkor az LP megoldása az optimális megoldás lehet.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!