1對(duì)策論的基本概念

1、1 對(duì)策論的基本概念對(duì)策模型的三個(gè)基本要素：1. 局中人：參與對(duì)抗的各方；2. 策略集：局中人選擇對(duì)付其它局中人的行動(dòng)方案稱(chēng)為策略； 某局中 人的所有可能策略全體稱(chēng)為策略集；3. 一局勢(shì)對(duì)策的益損值：局中人各自使用一個(gè)對(duì)策就形成了一個(gè)局 勢(shì)，一個(gè)局勢(shì)決定了各局中人的對(duì)策結(jié)果 （量化） 稱(chēng)為該局勢(shì)對(duì)策 的益損值?！褒R王賽馬 ”齊王在各局勢(shì)中的益損值表（單位：千金）§ 1 對(duì)策論的基本概念其中：齊王的策略集 :S1= 1, 2,3, 4, 5,6 ，田忌的策略集：S2= 1, 2,3, 4, 5,6 。下面矩陣稱(chēng)齊王的贏得矩陣：3 11 1-111 31 11-1A=1-13 1 1 1

2、-1 11 3111 11 -1311 1-1 113§ 1 對(duì)策論的基本概念二人有限零和對(duì)策（又稱(chēng)矩陣對(duì)策）：局中人為 2；每個(gè)局中人的策略集的策略數(shù)目都是有限的；每一 局勢(shì)的對(duì)策均有確定的損益值， 并且對(duì)同一局勢(shì)的兩個(gè)局中人的益損 值之和為零。通常將矩陣對(duì)策記為 : G = S1, S2, ASi：甲的策略集；S2：乙的策略集；A :甲的贏得矩陣?！褒R王賽馬 ”是一個(gè)矩陣策略。§ 2 矩陣對(duì)策的最優(yōu)純策略在甲方的贏得矩陣中：A=aij mxni行代表甲方策略i=1,2,m ； j行代表乙方策略j=1,2,n； aij代表甲方 取策略i，乙方取策略j，這一局勢(shì)下甲方的益損

3、值。此時(shí)乙方的益損值為 -aj （零和性質(zhì)）。在考慮各方采用的策略時(shí)，必須注意一個(gè)前提，就是雙方都是理智的，即 雙方都是從各自可能出現(xiàn)的最不利的情形選擇一種最為有利的情況作為決策的 依據(jù)。§ 2 矩陣對(duì)策的最優(yōu)純策略 例：甲乙乒乓球隊(duì)進(jìn)行團(tuán)體對(duì)抗賽， 每隊(duì)由三名球員組成， 雙方都可排成三種不同 的陣容，每一種陣容可以看作一種策略，雙方各選一種策略參賽。比賽共賽三局，規(guī)定 每局勝者得 1分，輸者得 -1分，可知三賽三勝得 3分，三賽二勝得 1分，三賽一勝得 -1 分， 三賽三負(fù)得 -3 分。甲隊(duì)的策略集為 S1= 1， 2， 3 ，乙隊(duì)的策略集為 S2= 1， 2， 3。 根據(jù)以往比賽

4、的資料，有甲隊(duì)的贏得矩陣為 A，如下所示，請(qǐng)問(wèn)這次比賽各隊(duì)采用哪種陣容上場(chǎng)最為穩(wěn)妥 ?§ 2 矩陣對(duì)策的最優(yōu)純策略矩陣a中每行的最小元素分別為 1，-3，-1 o在這些最少贏得中最好的結(jié)果是 1，故甲隊(duì)會(huì)采取策略 1，無(wú)論對(duì)手采取何策略，甲隊(duì)至少 得1分。對(duì)于乙隊(duì)， 1，2，3可能帶來(lái)的最少贏得，即 A中每列的最大元素，分別為 3，1，3乙隊(duì)會(huì)采取2策略，確保甲隊(duì)不會(huì)超過(guò) 1分。1和2分別稱(chēng)為局中人甲隊(duì)、乙隊(duì)的最優(yōu)策略。由于雙方必然選擇這一種策略，所以，這種 策略又稱(chēng)為最優(yōu)純策略。這種最優(yōu)純策略只有當(dāng)贏得矩陣 A=（aij ）中等式成立時(shí)，雙方才有最優(yōu)純策略，并把（1, 2）稱(chēng)為對(duì)策

5、G在純策略下的解，又稱(chēng)（ 1, 2）為對(duì)策G的鞍點(diǎn)。把其值 V稱(chēng)之為對(duì)策G=S1，S2，A的值。§ 2 矩陣對(duì)策的最優(yōu)純策略已知在正常的冬季氣溫條例 某單位采購(gòu)員在秋天決定冬季取暖用煤的儲(chǔ)量問(wèn)題，件下要消耗 15噸煤，在較暖和較冷的天氣下要消耗 10噸和 20噸。假定冬天的煤價(jià)隨天氣 寒冷程度而有所變化，在較暖和、正常、較冷的氣候條件下每噸煤價(jià)分別為10元、 15元、20元。又設(shè)冬季時(shí)煤炭?jī)r(jià)格為每噸 10元。在沒(méi)有關(guān)于當(dāng)年冬季準(zhǔn)確的氣象預(yù)報(bào)的條 件下，秋天儲(chǔ)煤多少?lài)嵞苁沟脝挝坏闹С鲎钌?？解：局中?I 為采購(gòu)員，局中人 II 為大自然，采購(gòu)員有三個(gè)策略，買(mǎi) 10噸、 15噸、 20噸

6、。分別記為 1， 2， 3。大自然也有三個(gè)策略：暖、正常、冷，分別記為1， 2，3。§ 2 矩陣對(duì)策的最優(yōu)純策略贏得矩陣如下：在此表上計(jì)算，有故（3, 3）為對(duì)策G的解，VG=-200設(shè)矩陣對(duì)策 G = S1, S2, A 。當(dāng)max min aij min max aiji j j i 時(shí)，不存在最優(yōu)純策略。例：設(shè)一個(gè)贏得矩陣如下 :min5 9 5A =max 6策略 28 6 6 imax 8 9策略 1min 8j當(dāng)甲取策略 2 ，乙取策略 1時(shí)，甲實(shí)際贏得 8比預(yù)期的多 2，乙當(dāng)然不滿(mǎn)意?？紤] 到甲可能取策略 2這一點(diǎn)，乙采取策略 2 。若甲也分析到乙可能采取策略 2這一點(diǎn)

7、，取 策略i，則贏得更多為9。此時(shí)，對(duì)兩個(gè)局中人甲、乙來(lái)說(shuō)，沒(méi)有一個(gè)雙方均可接受 的平衡局勢(shì)， 其主要原因是甲和乙沒(méi)有執(zhí)行上述原則的共同基礎(chǔ)， 即 max min aij minmax aij 。一個(gè)自然的想法：對(duì)甲（乙）給出一個(gè)選取不同策略的概率分布，以使甲（乙）在 各種情況下的平均贏得（損失）最多（最少） 即混合策略。求解混合策略的問(wèn)題有圖解法、 迭代法、 線(xiàn)性方程法和線(xiàn)性規(guī)劃法等， 我們這里只 介紹線(xiàn)性規(guī)劃法，其他方法略。例：設(shè)甲使用策略1的概率為Xi',使用策略2的概率為X2 ,并設(shè)在最壞的情況下， 甲贏得的平均值為 V （未知）。59A=STEP 1861)X1' +

8、X2' =1X1' , X2'02）無(wú)論乙取何策略，甲的平均贏得應(yīng)不少于 V:對(duì)乙取 1： 5X 1'+ 8X2' V 對(duì)乙取 2： 9X 1'+ 6X2' V 注意V>0,因?yàn)锳各元素為正。STEP 2 作變換： X1= X1'/V ; X2= X2'/V得到上述關(guān)系式變?yōu)椋篨 1+ X 2=1/V （V 愈大愈好）待定5X 1+ 8X2 19X 1+ 6X2 1X 1, X 2 0建立線(xiàn)性模型：min X1+X2s.t. 5X1+8X2 1X1= 1/219X1+6X2 1X2= 2/21X1, X 2 01/V

9、= X1+X2=1/7所以， V=7返回原問(wèn)題：X 1'=X 1V= 1/3X2'=X 2V= 2/3于是甲的最優(yōu)混合策略為：以1/3的概率選 1， 以2/3的概率選 2，最優(yōu)值 V=7。例：求解“齊王賽馬”問(wèn)題。 已知齊王的贏得矩陣 A求得故不存在純策略問(wèn)題下的解，可求其混合策略。A中有負(fù)元素，可以取k=2,在A的每個(gè)元素上加2得到A'如下:建立對(duì)G =Si, S2, A 中求甲方最佳策略的線(xiàn)性規(guī)劃如下：Min x1+x2+x3+x4 +x5+x6約束條件：5x 1+3x2 +3x3 +X4 +3x5 +3x6 > 13x 1+5x2 +X3+3x4 +3x5

10、+3x6 > 13x 汁3x2 +5x3 +3x4+3x 5+X6 > 13x 1+3X2+3X3+5X4+X5+3X6 A 1x 1+3X2+3X3+3X4+5X5+3X6 A 13x 1+x2+3x3+3x4+3x5+5x6 A 1x i A 0,i=1,2,6可解得解為：X1=X4=X5=0, X 2=X3=X6=0.111, V =3, X 1 =X4 =X5 = 0 ,X2 ' =X3 =X6 =1/3,即X *=(0,1/3,1/3,0,0,1/3) T，所以甲的最優(yōu)策略為作出策略2、3、6的概率都為0.333,而作出 1、4、5 的概率為 0,此時(shí) V G=V

11、 =3。同樣可以建立對(duì)策 G =S1, S2, A 中求乙方最佳策略的線(xiàn)性規(guī)劃如下： Min y1+y2+y3+y4+y5+y6約束條件：5y 1+3y2+3y3+3y4+y5+3y6 w 13y 1+5y2 +3y3 +3y4+3y 5+y 6 w 13y 1+y2+5y3+3y4 +3y5 +3y6 w 1y 1+3y2+3y3+5y4+3y5+3y6 w 13y 1+3y2+3y3+y4+5y5+3y6 w 13y 1+3y2+y3+3y4+3y5+5y6 w 1y iA0,i=1,2,6可解得解為：y 1=y4=y5=0.111, y 2=y3=y6=0, v =3, y 1 =y4

12、=y5 = 1/3 ，y 2' =y3 =y'=0,即 Y' * =(1/3,0,0,1/3,1/3,0)T。所以田忌的最優(yōu)混合策略為作出策略1、4、5的概率都為1/3,而作出2,3,6的概率為0,此時(shí)VG=Vg-k=1 。*T 齊王賽馬問(wèn)題的對(duì)策最優(yōu)解可簡(jiǎn)記為 X*=(0,1/3,1/3,0,0,1/3)T,Y*=(1/3,0,0,1/3,1/3,0)丁，對(duì)策值 Vg=1o例 兩個(gè)局中人進(jìn)行對(duì)策,規(guī)則是兩人互相獨(dú)立的各自從 1、 2 、 3這三個(gè)數(shù)字中任意選寫(xiě)一個(gè)數(shù) 字。如果兩人所寫(xiě)的數(shù)字之和為偶數(shù)，則局中人乙支付給局中人甲以數(shù)量為此和數(shù)的報(bào)酬；女口 果兩人所寫(xiě)數(shù)字之

13、和為奇數(shù)，則局中人甲付給局中人乙以數(shù)量為此和數(shù)的報(bào)酬。試求岀其最優(yōu) 策略。解：首先計(jì)算局中人甲的贏得矩陣如下表：即甲的贏得矩陣為 A：可知無(wú)純策略意義的解，下面求其在混合策略下的解。A的各元素都加上6,得到建立線(xiàn)性規(guī)劃模型如下：Min x1+x2+x3Max y1+y2+y3S.T.8x1+3x2+10x3 > 18y1+3y2+10y3 冬 13x1+10X2+X3 > 13y1+10y2+y3 W110x1 +x?+12x3 A110y1+y2+12y3 冬 1x1,x 2,x 3 >0y1,y 2,y 3 > 0得到X1 =0.25, x 2 =0.50, x 3

14、 =0.25;y1 =0.25, y 2 =0.50, y 3 =0.25o即此對(duì)策的解為*TX* =(0.25,0.50,0.25) T，*TY* =(0.25,0.50,0.25) T。Vg=Vg -k=0 o例4 甲乙兩個(gè)企業(yè)生產(chǎn)同一種電子產(chǎn)品， 甲企業(yè)可以采取的策略措施有 :（1） 降低產(chǎn)品價(jià)格； （2） 提高產(chǎn)品質(zhì)量；（3）推岀新產(chǎn)品。乙企業(yè)考慮采取的策略措施有（1）增加廣告費(fèi)用；（2）增設(shè)維修網(wǎng)點(diǎn)，加強(qiáng)售后服務(wù)；（3）改進(jìn)產(chǎn)品性能。由于甲乙兩個(gè)企業(yè)財(cái)力有限，都只能采取一個(gè)措施。假定這兩個(gè)企業(yè)所占有的市場(chǎng)總份額一定，由于各自采取的措施不同，通過(guò)預(yù)測(cè)今后兩個(gè)企業(yè)的市場(chǎng)占有份額變動(dòng)情況如

15、下表，試求岀這兩個(gè)企業(yè)各自的最優(yōu)策略。解：易知此對(duì)策無(wú)純策略意義下的解。把A的每一個(gè)元素加上12,得到A建立線(xiàn)性規(guī)劃模型如下：Max y1+y2+y3Min x1+x2+x3S.T.22X i+20X2> 16x 1+17x2+22x3 > 115x1+7x2+20x3122y1+6y2+15y3 < 120y1+17y2+7y3 < 122y2+20y3 < 1x1,x 2,x 3 0y1,y 2,y 3 0得到：x1=0.027,x 2=0.020,x 3=0.023；y1=0.0225,y 2=0.0225,y 3=0.025 oV=14.29o X1

16、9; =0.3858, x 2 =0.2858, x 3' =0.3286 ; y =0.3215,y 2' =0.3215,y 3' =0.3572即此對(duì)策的解為 X* =(0.3858,0.2858,0.3286) T ,Y* =(0.3215,0.3215,0.3572) 仏=乂 -k=2.29 o優(yōu)超原則： 稱(chēng)甲方策略s優(yōu)超于t （ s優(yōu)超于t）。假設(shè)矩陣對(duì)策甲方贏得矩陣若存在兩行（列），G = S 1, S 2, A A=aij ms 行（列）的各元素均優(yōu)于as a© j=1,2n ( a ist 行（列）的元素，即ait i=1,2 m ）優(yōu)超原則：當(dāng)局中人甲方的策略t被其它策略所優(yōu)超時(shí)，可在其贏得矩陣 A中劃去第t行（同理，當(dāng)局中人乙方的策略t被其它策略所優(yōu)超時(shí)，可在矩陣 A中劃去第t列）.如此得到階數(shù)較小的贏得矩陣 A',其對(duì)應(yīng)的矩陣對(duì)策G'= S1, S2, A' 與 G = S1, S2, A 等價(jià)，即解相同。例.設(shè)甲方的益損值，贏得矩陣為3 203 0被第 3、 4行所優(yōu)超5 025 9被第 3行所優(yōu)超A= 73 9 594 687 5.56 088 3得到73