【正文】 策 ——“齊王賽馬” 解 已知齊王的贏得矩陣為 3 1 1 1 1 11 3 1 1 1 11 1 3 1 1 11 1 1 3 1 11 1 1 1 3 11 1 1 1 1 3A???????????????????* * * * * * * T1 2 3 4 5 6( , , , , , )x x x x x x x? * * * * * * * T1 2 3 4 5 6( , , , , , )y y y y y y y?* 0,ix ? * 0jy ?易知， A沒有鞍點，即對齊王和田忌來說都不存在最優(yōu)純策略。設齊王和田忌的最優(yōu)混合策略為 于是，可用線性方程組法求解。 清華大學出版社 75 1 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 63333331x x x x x x vx x x x x x vx x x x x x vx x x x x x vx x x x x x vx x x x x x vx x x x x x? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? ? ??? ? ? ? ? ??1 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 63333331y y y y y y vy y y y y y vy y y y y y vy y y y y y vy y y y y y vy y y y y y vy y y y y y? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ??1 / 6 , 1 , ,6 。 1 / 6 , 1 , ,6 。 1ijx i y j v? ? ? ? ?*T( 1 / 6 , 1 / 6 , 1 / 6 , 1 / 6 , 1 / 6 , 1 / 6)x ? *T( 1 / 6 , 1 / 6 , 1 / 6 , 1 / 6 , 1 / 6 , 1 / 6)y ?故齊王和田忌的最優(yōu)混合策略為 ?通過求解方程組 ?得到 和 清華大學出版社 76 ?該對策的值 (即齊王的期望贏得值 )為 VG=1。這與我們的設想相符，即雙方都以 1/6的概率選取每個純策略，或者說每個純策略被選取的機會應是均等的，則總的結局應該是：齊王有 5/6的機會贏田忌，贏得的期望值是 1千金。 ?但如果齊王在每出一匹馬前將自己的選擇告訴了對方，這實際上等于公開了自己的策略，如齊王選取出馬次序為 (上，中，下 )，則田忌根據(jù)謀士的建議便以 (下，上，中 )對之，結果田忌反而可得千金。 ?因此，在矩陣對策不存在鞍點時，競爭的雙方在開局前均應對自己的策略 (實際上是純策略 )加以保密，否則不保密的一方是要吃虧的。 清華大學出版社 77 由定理 5已知，任一矩陣對策 的求解均等價于一對互為對偶的線性規(guī)劃問題，而定理 4表明，對策 G的解等價于下面兩個不等式組的解。 線性規(guī)劃方法 ? ?12, 。 G S S A?, 1 , , 1 , , ( I ) 1 ( I I ) 10 , 1 , , 0 , 1 , ,ij jij ijiiji ja y v i ma x v j nxyx i m y j n? ??? ?????????????? ??? ?????****2211m a x m in ( , ) m in m a x ( , ) ( 1 0 4 0 )y S y Sx S x Sv E x y E x y????? ? ?其中 就是對策的值 VG 清華大學出版社 78 ，則 ? ?12, 。 G S S A?** 21 1 1m a x m in ( , ) m in m a x ( , ) ( 1 0 4 1 )G jn imySxSV E x j E i y?? ????? ? ?****2211m a x m in ( , ) m in m a x ( , ) ( 1 0 4 1 )G y S y Sx S x SV E x y E x y????? ? ?*1xS?*21m in ( , ) m in ( , ) ( 1 0 4 3 )jn ySE x j E x y?? ???*** 2111m a x m in ( , ) m a x m in ( , ) ( 1 0 4 4 )jn ySx S x SE x j E x y?? ??? ??定理 11 設矩陣對策 的值為 VG 證明：因 VG是對策的值，故 一方面，任給 ，有 故 清華大學出版社 79 **12,x S y S??11( , ) ( , ) m in ( , )nj jnjE x y E x j y E x j???? ? ??*2***21111m i n ( , ) m i n ( , ) ( 10 45 )m a x m i n ( , ) m a x m i n ( , ) ( 10 46)jnySjnySx S x SE x y E x jE x y E x j????????????*1 1m a x m in ( , )G jnxSV E x j????*2 1m in m a x ( , )G imySV E i y????另一方面，任給 ，有 故 由 (1044)式和 (1046)式得 同理可證 清華大學出版社 80 / , 1 , , ( 1 0 4 7 )iix 39。 x v i m? ? ?1 , 1 , ,( I ) 1 / ( 10 48 )0 , 1 , , )ij iiiiia x 39。 j nx 39。 vx 39。 i m? ????????? ?????*1 1m a x m in ij ijnxS iv a x???? ?m i n ( ) 1 , 1 , , ( 10 49)0iiij iiiz x 39。P a x 39。 j nx39。? ???? ? ???? ????下面給出求解矩陣對策的線性規(guī)劃方法。 作變換 (根據(jù)定理 7，不妨設 v0) 則不等式組 (1038)變?yōu)? 根據(jù)定理 11， 這樣，不等式組 (Ⅰ )即等價于線性規(guī)劃問題： 清華大學出版社 81 / , 1 , , ( 1 0 5 0 )jjy 39。 y v j n? ? ?1 , 1 , ,( I I ) 1 / ( 10 51 )0 , 1 , ,ij jjjjja y 39。 i my 39。 vy 39。 j n? ????????? ?????*2 1m in m a x i j jimyS jv a y???? ?m a x ( D ) 1 , 1 , , ( 10 52)0 , 1 , ,jji j jjjw y 39。a y 39。 i my 39。 j n? ???? ? ???? ?????同理，作變換 則不等式組 (1039)變?yōu)?11 其中 與之等價的線性規(guī)劃問題是： 清華大學出版社 82 顯然，問題 (P)和 (D)是互為對偶的線性規(guī)劃，故可利用單純形或?qū)ε紗渭冃畏椒ㄇ蠼?。在求解時，一般先求問題 (D)的解，因為這樣容易在迭代的第一步就找到第一個基可行解，而問題 (P)的解從問題 (D)的最后一個單純形表上即可得到。當求得問題 (P)和 (D)的解后，再利用變換 (1447)式和 (1450)式即可求出原對策問題的解及對策的值。 清華大學出版社 83 7 2 92 9 09 0 1 1A?????????1 2 31 2 312131 2 31 2 31 2 312131 2 3m i n( )7 2 9 12 9 1 ( 10 53 )9 11 1, , 0m a x( )7 2 9 12 9 1 ( 10 54)9 11 1, , 0x x xx x xxxxxx x xy y yy y yyyyyy y y??? ? ???????????? ????? ? ???????????? ??例 18 利用線性規(guī)劃方法求解贏得矩陣為 A的矩陣對策。 解： 求解問題可化成兩個互為對偶的線性規(guī)劃問題： 清華大學出版社 84 TT( 1 / 2 0 , 1 / 1 0 , 4 / 8 0 ) ( 1 / 2 0 , 1 / 1 0 , 1 / 2 0 )1 6 / 8 0yw? ?????TT( 4 / 8 0 , 8 / 8 0 , 4 / 8 0 ) ( 1 / 2 0 , 1 / 1 0 , 1 / 2 0 )1 6 / 8 0xz? ?????* T T* T T80 / 16 5( 1 / 20 ,1 / 10 ,1 / 20 ) ( 1 / 4 , 2 / 4 , 1 / 4)( 1 / 20 ,1 / 10 ,1 / 20 ) ( 1 / 4 , 2 / 4 , 1 / 4)GVx V Gy V G??? ? ?? ? ?利用單純形方法求解問題 (D)，迭代過程如表 104所示，從表144中可得到問題 (D)的解為 由表 104中最后一個單純形表可得問題（ P）的解為： 于是 清華大學出版社 85 cj 1 1 1 0 0 0 w cB xB b y1 y2 y3 u1 u2 u3 0 u1 1 7 2 9 1 0 0 0 u2 1 2 9 0 0 1 0 0 u3 1 [9] 0 11 0 0 1 cj－ zj 1 1 1 0 0 0 0 0 u1 2/9 0 2 4/9 1 0 － 7/9 0 u2 7/9 0 [9] － 22/9 0 1 － 2/9 1 y1 1/9 1 0 11/9 0 0 1/9 cj－ zj 0 1 － 2/9 0 0 － 1/9 1/9 0 u1 4/81 0 0 [80/81] 1 － 2/9 － 59/81 1 y2 7/81 0 1 － 22/81 0 1/9 1/9 1 y1 1/9 1 0 11/9 0 0 1/9 cj－ zj 0 0 4/81 0 － 1/9 － 7/81 16/81 1 y3 4/80 0 0 1 81/80 － 18/80 － 59/80 1 y2 1/10 0 1 0 22/80 4/80 － 18/80 1 y1 1/20 1 0 0 － 99/80 22/80 81/80 cj－ zj 0 0 0 － 4/80 － 8/80 － 4/80 16/80