管理運籌學(xué)對策論

1、對策論對策論2021-11-212對策論由“齊王賽馬”引入2021-11-2131.對策論的基本概念 三個基本要素； 1.局中人：參與對抗的各方； 2.策略集：局中人選擇對付其它局中人的行動方案稱為策略。 某局中人的所有可能策略全體稱為策略集；3.局勢對策的益損值：各局中人各自使用一個對策就形成一個局勢，一個局勢決定了個局眾人 的對策結(jié)果（量化）稱為該局勢對策的益損值）2021-11-214“齊王賽馬”齊王在各局勢中的益損值表（單位：千金）2021-11-215 齊王的策略集: S S1 1=1, 2, 3, 4, 5, 6 田忌的策略集： S S2 2=1, 2, 3, 4, 5, 6 下列

2、矩陣稱齊王的贏得矩陣： 3 1 1 1 -1 13 1 1 1 -1 1 1 3 1 1 1 -1 1 3 1 1 1 -1A= 1 -1 3 1 1 1A= 1 -1 3 1 1 1 -1 1 1 3 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 1 -1 3 1 1 1 -1 1 1 3 1 1 -1 1 1 3 2021-11-2161.基本概念（續(xù)）二人有限零和對策：（又稱矩陣策略）局中人為2；每局中人的策略集中策略權(quán)目有限；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。2021-11-2171.基本概念（續(xù)） 記矩陣對策為: G =

3、 SG = S1 1, S, S2 2, A, A 甲的策略集 甲的贏得矩陣 乙的策略集 “齊王賽馬”即是一個矩陣策略.2021-11-2182.矩陣對策的最優(yōu)純策略 在甲方贏得矩陣中： A=aijm*n i行代表甲方策略 i=1,2m j行代表乙方策略 j=1,2n aij代表甲方取策略i,乙方取策略j,這一局勢下甲方的益損值，此時乙方的益損值為-aij（零和性質(zhì)）。 在討論各方采用的策略是必須注意一個前提就是對方是理智的。這就是要從最有把握取得的益損值情況考慮。2021-11-2192.矩陣對策的最優(yōu)純策略(續(xù)) 例：有交易雙方公司甲和乙，甲有三個策略1，2，3；乙有四個策略1，2，3，4

4、，根據(jù)獲利情況建立甲方的益損值 贏得矩陣。 -3 0 -2 0-3 0 -2 0 A= 2 3 0 1 A= 2 3 0 1 -2 -4 -1 3 -2 -4 -1 3 問：甲公司應(yīng)采取什么策略比較適合？2021-11-2110甲：采取1至少得益3(損失 3） 2 0 3 -4(損失 4）乙：采取1甲最多得益2 （乙最少得益-2） 2 3（乙得益-3） 3 0（乙得益 0） 4 3（乙得益-3）取大則取取大則取 2 2 max min amax min aijij= 0= 0 i ji j取小則取取小則取 3 3 min max amin max aijij= 0= 0 j j i i2021

5、-11-2111 甲采取策略2 不管乙采取如何策略，都至少得益。 乙采取策略3 不管甲采取如何策略， 都至少可以得益。（最多損失0） 分別稱甲，乙公司的最優(yōu)策略，由唯一性又稱最優(yōu)純策略。存在前提： max min amax min aijij = min max a= min max aijij = v= v i j j i j j i i又稱（ 2 2 ， 3 3 ）為對策G=G=s s1 1, ,s s2 2,A,A的鞍點。值V為G的值。2021-11-21123.矩陣對策的混合策略 設(shè)矩陣對策 G =SG =S1 1,S,S2 2,A,A 當 max min amax min aij i

6、j min max a min max aij ij i j j i j j i i 時，不存在最優(yōu)純策略 求解混合策略。2021-11-21133.矩陣對策的混合策略例：設(shè)一個贏得矩陣如下: minmin 5 9 5 5 9 5 A = max 6 A = max 6 策略2 8 6 6 8 6 6 i i max 8 9 max 8 9 min 8 min 8 策略1 j2021-11-2114 矛盾：甲取2 ，乙取時1，甲實際贏得8比預(yù)期多2（乙就少2）這對乙講是不滿意的，考慮這一點，乙采取策略2，若甲分析到這一點，取策略1，則贏得更多為9 此時，甲，乙芳沒有一個雙方均可接受的平衡局勢。

7、 一個思路：對甲（乙）給出一個選取不同策略的概率分布，以使甲（乙）在各種情況下的平均贏得（損失）最多（最少）。-即混合策略2021-11-2115 求解方法：線性規(guī)劃法 （其他方法：圖解法，迭代法，線性方程法等略） 例： 5 95 9 設(shè)在最壞的情況下， A=A= 甲贏得的平均值為V V. 8 68 6 （未知） STEP 1STEP 1 1)1)設(shè)甲使用策略 1 1的概率為X X1 1 X X1 1+X+X2 2=1=1 設(shè)甲使用策略 2 2的概率為X X2 2 X X1 1,X,X2 2 0 02021-11-21162)2)無論乙取何策略，甲的平均贏得應(yīng)不少于V V: 對乙取1：5 5X

8、 X1 1+ 8X+ 8X2 2 V V 對乙取2：9 9X X1 1+ 6X+ 6X2 2 V V 注意 V0,V0,因為A A各元素為正。STEP 2 STEP 2 作變換： X X1 1= X= X1 1/V ; X/V ; X2 2= X= X2 2/V/V 得到上述關(guān)系式變?yōu)椋?X X1 1+ X+ X2 2=1/V (V=1/V (V愈大愈好）待定愈大愈好）待定 5X5X1 1+ 8X+ 8X2 2 1 1 9X 9X1 1+ 6X+ 6X2 2 1 1 X X1 1, X, X2 2 0 02021-11-2117 建立線性模型： min Xmin X1 1+X+X2 2 s.t

9、. 5Xs.t. 5X1 1+8X+8X2 2 1 1 X X1 1= 1/21= 1/21 9 9X X1 1+6X+6X2 2 1 1 X X2 2= 2/21= 2/21 X X1 1, X, X2 2 0 1/V= 0 1/V= X X1 1+X+X2 2=1/7=1/7 所以：V=7V=7 返回原問題： X X1 1= = X X1 1V= 1/3V= 1/3 X X2 2= = X X2 2V= 2/3V= 2/3 于是甲的最優(yōu)混合策略為： 以1/31/3的概率選 1 1；以2/32/3的概率選 2 2 最優(yōu)值V=7V=7.2021-11-2118 同樣可求乙的最優(yōu)混合策略： 設(shè)乙

10、使用策略1 1的概率為Y1 1 Y Y1 1+Y+Y2 2=1=1 設(shè)乙使用策略2 2的概率為Y2 2 Y Y1 1,Y,Y2 2 0 0 設(shè)在最壞的情況下，甲贏得的平均值為V V. 這也是乙損失的平均值，越小越好 作變換： Y Y1 1= Y= Y1 1/V ; Y/V ; Y2 2= Y= Y2 2/V/V 建立線性模型： max Ymax Y1 1+Y+Y2 2 s.t. 5Ys.t. 5Y1 1+9Y+9Y2 2 1 1 Y Y1 1= 1/14= 1/14 8 8Y Y1 1+6Y+6Y2 2 1 1 Y Y2 2= 1/14= 1/14 Y Y1 1, Y, Y2 2 0 1/V=

11、 0 1/V= Y Y1 1+Y+Y2 2=1/7=1/7 所以：V=7V=7 2021-11-2119 返回原問題： Y Y1 1= = Y Y1 1V= 1/2V= 1/2 Y Y2 2= = Y Y2 2V= 1/2V= 1/2 于是乙的最優(yōu)混合策略為： 以1/21/2的概率選1 1；以1/21/2的概率選2 2 最優(yōu)值V=7V=7. 當贏得矩陣中有非正元素時，V0的條件不一定成立，可以作下列變換： 選一正數(shù)k，令矩陣中每一元素加上k得到新的正矩陣A，其對應(yīng)的矩陣對策 G G= S= S1 1,S,S2 2,A,A 與與 G = SG = S1 1,S,S2 2,A ,A 解相同，但解相

12、同，但V VG G = V = VG G - k - k2021-11-2120再討論“齊王賽馬” “齊王賽馬”的贏得矩陣A有 max min amax min aijij1 1 min max a min max aijij3 3 i j i j j i j i 故需求混合策略，由于A中有非正元素，可選k2，令矩陣中每一元素加上k得到新的正矩陣A： 5 3 3 3 1 35 3 3 3 1 3 3 5 3 3 3 1 3 5 3 3 3 1 A = 3 1 5 3 3 3 A = 3 1 5 3 3 3 1 3 3 5 3 3 1 3 3 5 3 3 3 3 3 1 5 3 3 3 3 1

13、5 3 3 3 1 3 3 5 3 3 1 3 3 52021-11-2121再討論“齊王賽馬”(續(xù)) 求甲方(齊王)最優(yōu)策略的線性規(guī)劃模型： min Xmin X1 1+X+X2 2 +X+X3 3 +X+X4 4 +X+X5 5 +X+X6 6 s.t. 5Xs.t. 5X1 1+3X+3X2 2 +3X+3X3 3 + X+ X4 4 +3X+3X5 5 +3X+3X6 6 1 1 3X 3X1 1+5X+5X2 2 + X+ X3 3 +3X+3X4 4 +3X+3X5 5 +3X+3X6 6 1 1 3X 3X1 1+3X+3X2 2 +5X+5X3 3 +3X+3X4 4 +3X+

14、3X5 5 + X+ X6 6 1 1 3X 3X1 1+3X+3X2 2 +3X+3X3 3 +5X+5X4 4 + X+ X5 5 +3X+3X6 6 1 1 X X1 1+3X+3X2 2 +3X+3X3 3 +3X+3X4 4 +5X+5X5 5 +3X+3X6 6 1 1 3X 3X1 1+ X+ X2 2 +3X+3X3 3 +3X+3X4 4 +3X+3X5 5 +5X+5X6 6 1 1 X X1 1，X X2 2，X X3 3，X X4 4，X X5 5，X X6 6 0 0 可得兩組解：可得兩組解：(0,1/9,1/9,0,0,1/9)(0,1/9,1/9,0,0,1/9)

15、T T, , (1/18,1/18,1/18,1/18,1/18,1/18) (1/18,1/18,1/18,1/18,1/18,1/18)T T ,V=3,V=3于是，于是，XX(0,1/3,1/3,0,0,1/3)(0,1/3,1/3,0,0,1/3)T T, , XX(1/6,1/6,1/6,1/6,1/6,1/6)(1/6,1/6,1/6,1/6,1/6,1/6)T T V = V-2 V = V-2 = = 1 1即齊王的最優(yōu)混合策略值是贏即齊王的最優(yōu)混合策略值是贏1 1千金千金2021-11-2122再討論“齊王賽馬”(續(xù)) 求乙方(田忌)最優(yōu)策略的線性規(guī)劃模型： min Ymin

16、 Y1 1+Y+Y2 2 +Y+Y3 3 +Y+Y4 4 +Y+Y5 5 +Y+Y6 6 s.t. 5Ys.t. 5Y1 1+3Y+3Y2 2 +3Y+3Y3 3 +3Y+3Y4 4 + Y+ Y5 5 +3Y+3Y6 6 1 1 3Y 3Y1 1+5Y+5Y2 2 +3Y+3Y3 3 +3Y+3Y4 4 +3Y+3Y5 5 + Y+ Y6 6 1 1 3Y 3Y1 1+ Y+ Y2 2 +5Y+5Y3 3 +3Y+3Y4 4 +3Y+3Y5 5 +3Y+3Y6 6 1 1 Y Y1 1+3Y+3Y2 2 +3Y+3Y3 3 +5Y+5Y4 4 +3Y+3Y5 5 +3Y+3Y6 6 1 1

17、3Y 3Y1 1+3Y+3Y2 2 +3Y+3Y3 3 + Y+ Y4 4 +5Y+5Y5 5 +3Y+3Y6 6 1 1 3Y 3Y1 1+3Y+3Y2 2 + Y+ Y3 3 +3Y+3Y4 4 +3Y+3Y5 5 +5Y+5Y6 6 1 1 Y Y1 1，Y Y2 2，Y Y3 3，Y Y4 4，Y Y5 5，Y Y6 6 0 0 可得兩組解：可得兩組解：(1/9,0,0,1/9,1/9,0)(1/9,0,0,1/9,1/9,0)T T, , (1/18,1/18,1/18,1/18,1/18,1/18) (1/18,1/18,1/18,1/18,1/18,1/18)T T ,V=3,V

18、=3于是，于是，YY(1/3,0,0,1/3,1/3,0)(1/3,0,0,1/3,1/3,0)T T, , YY(1/6,1/6,1/6,1/6,1/6,1/6)(1/6,1/6,1/6,1/6,1/6,1/6)T T V = V-2 V = V-2 = = 1 1即田忌的最優(yōu)混合策略值是輸即田忌的最優(yōu)混合策略值是輸1 1千金千金2021-11-2123 優(yōu)超原則：優(yōu)超原則： 假設(shè)矩陣對策 G = SG = S1 1,S,S2 2,A ,A 甲方贏得矩陣 A=aijmn- 若存在兩行，s 行的各元素均優(yōu)于 t 行的元素，即 asjatj j=1,2n 稱甲方策略s優(yōu)超于t - 若存在兩列，s

19、 列的各元素均優(yōu)于 t 列的元素，即 ais ait i=1,2,m 稱乙方策略 s優(yōu)超于t3.3.矩陣對策的混合策略矩陣對策的混合策略( (續(xù)續(xù)) )2021-11-2124- 優(yōu)超原則：當局中人甲方的策略t被其它策略所優(yōu)超時，可在其贏得矩陣A中劃去第t行（同理，當局中人乙方的策略t被其它策略所優(yōu)超時，可在矩陣A中劃去第t列）。 如此得到階數(shù)較小的贏得矩陣A，其對應(yīng)的矩陣對策 G= SG= S1 1,S,S2 2,A,A 與與 G = SG = S1 1,S,S2 2,A ,A 等價，即解相同。3.3.矩陣對策的混合策略矩陣對策的混合策略( (續(xù)續(xù)) )2021-11-2125 例 設(shè)甲方的益損值 贏得矩陣。 3 2 0 3 03 2 0 3 0 被第3、4行所優(yōu)超 5 0 2 5 95 0 2 5 9 被第3行所優(yōu)超 A= 7 3 9 5 9A= 7 3 9 5 9 4 6 8 7 5.5 4 6 8 7 5.5 6 0 8 8 3 6 0 8 8 3得到得到 7 3 7 3 9 59 5 9 9 被第1列所優(yōu)超 A A1 1= 4 6 = 4 6 8 78 7 5.5 5.5 被第2列所優(yōu)超 6 0 6 0 8 88 8 3 33.3.矩陣對