數(shù)學(xué)建模_對(duì)策論

1、2024/4/2,Operations Research,1,11 矩陣對(duì)策,6.1 引言6.2 對(duì)策論的基本概念6.3 矩陣對(duì)策的概念及模型6.4 矩陣對(duì)策的純策略解（鞍點(diǎn)解）6.5 矩陣對(duì)策的混合策略解（mixed strategic solution）6.6 矩陣對(duì)策的解法,2024/4/2,Operations Research,2,6.1.1 何謂對(duì)策論（Game Theory）？6.1.2

2、 對(duì)策的例子6.1.3 對(duì)策論的誕生與發(fā)展簡(jiǎn)況,,,,,,6.1 引 言,2024/4/2,Operations Research,3,6.1.1 何謂對(duì)策論(Game Theory)？,定義：對(duì)策論亦稱競(jìng)賽論或博弈論，是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。,2024/4/2,Operations Research,4,齊王賽馬決斗問題：神雕俠侶中武林盟主大會(huì),6.1.2 對(duì)策的例子,2024/4/2,Ope

3、rations Research,5,6.1.3 對(duì)策論的誕生與發(fā)展簡(jiǎn)況,早期工作1912年E.Zermelo ‘關(guān)于集合論在象棋對(duì)策中的應(yīng)用’ 1921年E.Borel 引入最優(yōu)策略 1928年J.V.Neumann證明了一些猜想,,,,,,2024/4/2,Operations Research,6,6.1.3 對(duì)策論的誕生與發(fā)展簡(jiǎn)況,產(chǎn)生標(biāo)志 1944年J.V.Neumann和O.Morgenste

4、rn”對(duì)策論與經(jīng)濟(jì)行為” （Theory of Games and Economic Behavior）發(fā)展成熟 Nash均衡、經(jīng)濟(jì)博奕論、信息不對(duì)稱對(duì)策和廣義對(duì)策,2024/4/2,Operations Research,7,6.2 對(duì)策論的基本概念,6.2.1 局中人（Player）6.2.2 策略（Strategy）6.2.3 支付與支付函數(shù),2024/4/2,Operations Resea

5、rch,8,6.2.1 局中人（Player）,1、局中人：在一場(chǎng)競(jìng)爭(zhēng)或斗爭(zhēng)中的決策者稱為該局對(duì)策的局中人 通常，一局對(duì)策具有兩個(gè)或兩個(gè)以上---決策者，一般用I表示局中人集合：,,2024/4/2,Operations Research,9,6.2.1 局中人（Player）,,,,,,2、對(duì)策分類：依據(jù)局中人的數(shù)量，可將對(duì)策分為,有限對(duì)策,無(wú)限對(duì)策(n>2),對(duì)策,,無(wú)限零和對(duì)策,無(wú)限非零和對(duì)策,有限零和對(duì)

6、策,有限非零和對(duì)策,,,2024/4/2,Operations Research,10,6.2.2 策略（Strategy）,1、 策略與策略集局中人指導(dǎo)自己自始至終如何行動(dòng)的一個(gè)方案，稱為策略(Strategy)由所有策略構(gòu)成的集合，稱為策略集(Strategy　Set),,,,,,2024/4/2,Operations Research,11,6.2.2 策略（Strategy）,,,,,,2、策略集的元素：對(duì)于局中

7、人i,i∈I，都有自己的策略集Si,通常每一局中人的策略集中至少應(yīng)包括兩個(gè)策略,對(duì)于例4的包、剪、錘游戲。假設(shè)有兩個(gè)局中人I={甲，乙}，甲的策略集為S甲={(包)、(剪)、(錘)}={a1、a2、a3};乙的策略集為S乙={(包)、(剪)、(錘)} ={b1、b2、b3};,2024/4/2,Operations Research,12,6.2.3 支付與支付函數(shù),1、局勢(shì)：各局中人所選定的策略形成的策略組2、策略組 若

8、si是第i個(gè)局中人的一個(gè)策略，則n個(gè)局中人的策略組 s=(s1,s2,…,sn) 就是一個(gè)局勢(shì)。,,,,,2024/4/2,Operations Research,13,6.2.3 支付與支付函數(shù),,,,,例如，對(duì)于包、剪、錘游戲。假設(shè)有兩個(gè)局中人I={甲，乙}，甲的策略集為S甲={(包)、(剪)、(錘)}={(a1)、(a2)、(a3)};乙的策略集為S乙={(包)、(剪)、(錘)} ={(b1)、(b2)、(b3)}

9、; 則甲的一個(gè)策略ai，和乙的一個(gè)策略bj就構(gòu)成一個(gè)局勢(shì)sij.,2024/4/2,Operations Research,14,6.2.3 支付與支付函數(shù),3、贏得（支付）：當(dāng)每個(gè)局中人所采取的策略確定后，他們就會(huì)得到相應(yīng)的收益或損失，稱為局中人的支付（Payoff）。 若甲的一個(gè)策略a3(錘)，乙的一個(gè)策略b2(剪)，則構(gòu)成一個(gè)局勢(shì)s32 。在局勢(shì)s32下，甲的支付為：,乙的支付,2024/4/2,Ope

10、rations Research,15,6.2.3 支付與支付函數(shù),,,,4、支付（贏得）函數(shù)：不同的策略會(huì)導(dǎo)致不同的支付，因此，支付是策略(準(zhǔn)確的說應(yīng)該是局勢(shì))的函數(shù)，稱為支付函數(shù)(payoff function)。對(duì)于例4，兩人的支付函數(shù)分別記為：,,,,,和,例如，對(duì)于策略a3, b1,2024/4/2,Operations Research,16,6.2.3 支付與支付函數(shù),5、零和對(duì)策和非零和對(duì)策 根據(jù)

11、各局中人支付的代數(shù)和是否為0，將對(duì)策分為零和對(duì)策和非零和對(duì)策(non-zero-sum games)。 若在任一局對(duì)策中，全體局中人支付的總和為0，則該對(duì)策稱為零和對(duì)策，否則稱為非零和對(duì)策(non-zero-sum games)。 對(duì)于前例，顯然為零和對(duì)策，因?yàn)?,,,,,,,,2024/4/2,Operations Research,17,6.2.3 支付與支付函數(shù),6、對(duì)策分類 根據(jù)局中人的數(shù)

12、目和支付函數(shù)代數(shù)和,,,,,,,,,有限對(duì)策,n人對(duì)策(n>2),對(duì)策,,合作對(duì)策,非合作對(duì)策,,2024/4/2,Operations Research,18,6.3 矩陣對(duì)策的概念及模型,1、定義：兩個(gè)人零和對(duì)策稱為矩陣對(duì)策 例，“包、剪、錘”游戲中，甲、乙雙方各有三種不同的策略，分別為：,,,,,,,,,,,2024/4/2,Operations Research,19,6.3 矩陣對(duì)策的概念及模型,甲的支付

13、情況如下表,表6.1,2024/4/2,Operations Research,20,6.3 矩陣對(duì)策的概念及模型,齊王賽馬,田忌策略,齊王贏得,齊王策略,,,上中下,上下中,中上下,中下上,下中上,下上中,2024/4/2,Operations Research,21,6.3 矩陣對(duì)策的概念及模型,,,,,,,,,,,,表6.1中的數(shù)字用矩陣的形式表示,A稱為甲的支付矩陣。顯然，乙的支付矩陣為-A。因此，該對(duì)策可記為：,,2

14、024/4/2,Operations Research,22,6.3 矩陣對(duì)策的概念及模型,2、矩陣對(duì)策的模型一般地，若局中人 Ⅰ，Ⅱ的策略集分別為：,為了與后面的概念區(qū)分開來，我們稱αi為Ⅰ的純策略， βj為Ⅱ的純策略，對(duì)于純策略αi, βj構(gòu)成的策略偶(αi, βj)稱為純局勢(shì)。,2024/4/2,Operations Research,23,6.3 矩陣對(duì)策的概念及模型,,,,,,,,,,,,,,,,,,,,,,,,若Ⅰ

15、的支付矩陣為：,αij表示局勢(shì)(αi,βj)下，局中人Ⅰ的支付,則矩陣對(duì)策可記為G={S1,S2,A}：即矩陣對(duì)策模型。,2024/4/2,Operations Research,24,6.4 矩陣對(duì)策的純策略解,,,,,,,,,,,,,,,,,,,,,,,,,,,,6.4.1 矩陣對(duì)策的純策略解例解過程6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)6.4.3 矩陣對(duì)策的純策略解性質(zhì),2024/4/2,Operations Resea

16、rch,25,例5 設(shè)二人零和對(duì)策 G={S1, S2, A}，，其中,6.4.1 矩陣對(duì)策的純策略解例解過程,,,,,,,,,,,,,,,,,,,,,,,,,,,,而且局中Ⅰ的支付矩陣為：,兩位局中人都想自己的支付最大化。,2024/4/2,Operations Research,26,6.4.1 矩陣對(duì)策的純策略解例解過程,,,,,,,,,,,,,,,,,,,,,,,,,,,,這里我們認(rèn)為局中人都是理智的，從矩陣A進(jìn)行邏輯推理

17、可知： 如果局中人Ⅰ采取α3作策略，雖有可能獲得最大支付18，但是,局中人Ⅱ分析到Ⅰ的這種心理，就會(huì)采取β3策略，使Ⅰ不僅得不到最大值18，反而取得很壞的結(jié)果-8； 同樣，局中人Ⅱ?yàn)榱说玫阶畲笾Ц?12(即局中人Ⅰ的支付-12)，會(huì)采取 β2作為策略,但局中人Ⅰ也會(huì)猜到Ⅱ的這種心理,而采取 α2作策略，這樣局中人Ⅱ只能得到-3。,,,,2024/4/2,Operations Research,27,6.4.1 矩陣

18、對(duì)策的純策略解例解過程,,,,,,,,,,,,,,,,,,,,,,,,,,,,從以上的分析可以看出，局中人Ⅰ選取最優(yōu)策略時(shí)應(yīng)該考慮到Ⅱ也是十分理智與精明的，Ⅱ的策略是要以Ⅰ支付最少為目的，所以不能存在任何僥幸心理。局中人Ⅱ也應(yīng)作同樣的考慮。,,,,,對(duì)于局中人來說，應(yīng)該是從最壞處著想向最好處努力。,2024/4/2,Operations Research,28,6.4.1 矩陣對(duì)策的純策略解例解過程,,,,,,,,,,,,,,,,,,

19、,,,,,,,,,,對(duì)局中人Ⅰ來講，各策略的最壞結(jié)果分別為：min{-6,2,-7}=-7 min{5,3,6}=3min{18,0,-8}=-8min{-2,-12,7}=-12這些最壞的情況中，最好的結(jié)果是：max{-7,3,-8,-12}=3,,,,,2024/4/2,Operations Research,29,6.4.1 矩陣對(duì)策的純策略解例解過程,,,,,,,,,,,,,,,,,,,,,,,,

20、,,,,同樣，對(duì)局中人Ⅱ而言，各策略的最壞的結(jié)果分別為：max{-6,5,18,-2}=18max{2,3,0,-12}=3max{-7,6,-18,7}=7在這些最壞的情況中，最好的結(jié)果（損失最?。┦莔in{18,3,7}=3,,,,,2024/4/2,Operations Research,30,6.4.1 矩陣對(duì)策的純策略解例解過程,2024/4/2,Operations Research,31,6.4.1

21、矩陣對(duì)策的純策略解例解過程,課堂練習(xí):求解對(duì)策 G=﹛S1,S2,A﹜已知：,2024/4/2,Operations Research,32,定義1 對(duì)于矩陣對(duì)策G=﹛S1,S2,A﹜,如果存在純局勢(shì),6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,則稱局勢(shì) 為對(duì)策G在純策略中的解。亦稱其為G的鞍點(diǎn)(saddle point):,,(列中最大，行

22、中最小),使得對(duì)任意j=1, …，n,及任意i=1, …m有：,2024/4/2,Operations Research,33,6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ),分別稱為局中人Ⅰ，Ⅱ的最優(yōu)純策略。 稱 為對(duì)策G的值(value)，記為,2024/4/2,Operations Research,34,6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

23、,,,,,,,,,,,定理1 矩陣對(duì)策G={S1,S2,A}存在最優(yōu)純策略的充分必要條件為：,2024/4/2,Operations Research,35,6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ),求對(duì)G的解和值。,例6 已知 G={S1,S2,A}，其中,,2024/4/2,Operations Research,36,6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

24、,,,,,,,,,,,解：根據(jù)A可得,,,,,,,2024/4/2,Operations Research,37,6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ),由于：,四個(gè)局勢(shì)均為G的鞍點(diǎn)，且,故知：,2024/4/2,Operations Research,38,,6.4.3 矩陣對(duì)策的純策略解性質(zhì),從上例可知，對(duì)策的解可以是不唯一的，但對(duì)策的值是唯一的。對(duì)策解不唯一時(shí)，應(yīng)滿足下面兩條性質(zhì)：,是矩陣對(duì)策G的兩個(gè)解，則,即對(duì)策值相等，它們

25、在矩陣中的元素相同。,2024/4/2,Operations Research,39,,6.4.3 矩陣對(duì)策的純策略解性質(zhì),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2. 可交換性：若,與,是矩陣對(duì)策G的兩個(gè)解,則,與,也是對(duì)策的解。,2024/4/2,Operations Research,40,6.4.3 矩陣對(duì)策的純策略解性質(zhì),,,,,,,,,,,,,,,,,,,

26、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,是不是每一個(gè)矩陣對(duì)策都有純策略解（鞍點(diǎn)）？,答案是否定的。,2024/4/2,Operations Research,41,6.5 矩陣對(duì)策的混合策略解,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,6.5.1 混合策略與混合擴(kuò)充（mixed strategic solution）6.5.2 解

27、的基本定理,2024/4/2,Operations Research,42,6.5.1 混合策略與混合擴(kuò)充,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1、問題提出,2024/4/2,Operations Research,43,6.5.1 混合策略與混合擴(kuò)充,該對(duì)策問題表明不存在使對(duì)立雙方達(dá)到平衡的局勢(shì)，因此，局中人采取任何一種純策略，都有一定的風(fēng)險(xiǎn)。所以，在這種情

28、況下，局中人必須隱瞞自己選取策略的意圖。,2024/4/2,Operations Research,44,6.5.1 混合策略與混合擴(kuò)充,2、問題處理方案設(shè)計(jì)這時(shí)我們可以設(shè)想局中人隨機(jī)地選取純策略來進(jìn)行對(duì)策。即在一局對(duì)策中，局中人Ⅰ以概率,來選取純策略,,其中的,滿足,于是得到一個(gè)m維的概率向量,2024/4/2,Operations Research,45,6.5.1 混合策略與混合擴(kuò)充,,,,,,,,,,,,,,,,,,,,,

29、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,同樣對(duì)于局中人Ⅱ,有相應(yīng)的一個(gè)n維的概率向量,,滿足,yj表示局中人Ⅱ選取純策略βj的概率。,2024/4/2,Operations Research,46,6.5.1 混合策略與混合擴(kuò)充,3、混合策略概念引入定義:若給定一個(gè)矩陣對(duì)策G={S1,S2,A} ,其中,則我們把純策略集對(duì)應(yīng)的概率向量：,與,分別稱作局中人Ⅰ、Ⅱ的混合策略，(X,Y)稱為一個(gè)

30、混合局勢(shì)。,2024/4/2,Operations Research,47,6.5.1 混合策略與混合擴(kuò)充,如果局中人Ⅰ選取的策略為,局中人Ⅱ選取,由于兩局中人分別選取策略,的事件可以看成使相互獨(dú)立,4、混合策略的局中人支付 如果局中人Ⅰ選取的策略為,2024/4/2,Operations Research,48,6.5.1 混合策略與混合擴(kuò)充,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

31、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,就是局中人Ⅰ的支付值。,所以局勢(shì)(αi，βj)出現(xiàn)的概率是xiyj。從而知局中人Ⅰ支付αij的概率是xiyj。于是，數(shù)學(xué)期望值：,2024/4/2,Operations Research,49,,6.5.1 混合策略與混合擴(kuò)充,令：,5、混合擴(kuò)充,2024/4/2,Operations Research,50,,,,6.5.1 混合策略與混合擴(kuò)

32、充,分別稱為局中人Ⅰ、Ⅱ的最優(yōu)(混合)策略.,稱為對(duì)策G（在混合意義下的）值，記為,2024/4/2,Operations Research,51,6.5.1 混合策略與混合擴(kuò)充,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,解：顯然該問題無(wú)鞍點(diǎn)解。設(shè)局中人Ⅰ、Ⅱ 的混合策略分別為：

33、 X=(x1,x2),Y=(y1,y2).則,,,,2024/4/2,Operations Research,52,,6.5.1 混合策略與混合擴(kuò)充,則局中人Ⅰ支付的數(shù)學(xué)期望為：,2024/4/2,Operations Research,53,,6.5.1 混合策略與混合擴(kuò)充,,,,,,,,,,,,,可見:當(dāng),2024/4/2,Operations Research,54,,6.5.1 混合策略與混合擴(kuò)充,顯然,2024/4/

34、2,Operations Research,55,6.5.1 混合策略與混合擴(kuò)充,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,由定義1知：,分別是局中人Ⅰ、Ⅱ的的最優(yōu)策略，且,,2024/4/2,Operations Research,56,6.5.2 解的基本定理,,,

35、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,定理2 (基本定理) 任意一個(gè)矩陣對(duì)策,,其中,,,,一定有解(在混合策略意義下),且如果G的值是V,則以下兩組不等式的解是局中人Ⅰ,Ⅱ的最優(yōu)策略:,,,,2024/4/2,Operations Research,57,,,6.5.2 解的

36、基本定理,2024/4/2,Operations Research,58,6.5.2 解的基本定理,可用例7驗(yàn)證,定理3 若 是對(duì)策G(同前)的最優(yōu)混合局勢(shì),則對(duì)某一個(gè)i或j來說：,2024/4/2,Operations Research,59,6.5.2 解的基本定理,≤V,≥V,2024/4/2,Operations Research,60,6.6 矩陣對(duì)策的解法,,,,,,,,,,,,,,,,,,,

37、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,6.6.1 圖解法6.6.2 優(yōu)勢(shì)法6.6.3 簡(jiǎn)化計(jì)算法6.6.4 線性規(guī)劃解法,2024/4/2,Operations Research,61,,6.6.1 圖解法,,,,,,,,,,,,,,,,,,,,,,,,,

38、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,例8 已知：,,其中,,,,求矩陣對(duì)策的解和值。,,,2024/4/2,Operations Research,62,解: 設(shè)局中人Ⅰ 的混合策略為 (x,1-x)T,x∈[0,1]。對(duì)局中人Ⅰ而言，他的最少可能收入為局中人Ⅱ選取β1

39、，β2所確定的兩條直線(定理3知):,6.6.1 圖解法,V1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10,因?yàn)閤1和x2一定大于0,在x處的縱坐標(biāo)中的最小者. 局中人Ⅰ用“最大最小”原則選取自己的策略,即:,2024/4/2,Operations Research,63,,D點(diǎn)為極值點(diǎn),D點(diǎn)坐標(biāo)為：,即,Ⅰ的最優(yōu)混合策略為：,從上圖可以看出：,就是折線EDF.,2024/4/2,Operat

40、ions Research,64,6.6.1 圖解法,同理，對(duì)局中人Ⅱ而言有,V=5y+35(1-y)=35-30y V=20y+10(1-y)=10+10y,最小最大點(diǎn)為:,即,Ⅱ的最優(yōu)解為 ：,對(duì)策值為：,2024/4/2,Operations Research,65,6.6.1 圖解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

41、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/4/2,Operations Research,66,6.6.1 圖解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

42、,,,,,,,,,,,,課堂練習(xí)p145-10.4-3：求解下列矩陣對(duì)策，已知贏得矩陣為：,,,,,,2024/4/2,Operations Research,67,,6.6.1 圖解法,例9 已知：,其中,求對(duì)策的解和值。,解：顯然無(wú)鞍點(diǎn)，作混合擴(kuò)充：,2024/4/2,Operations Research,68,,6.6.1 圖解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

43、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,對(duì)局中人Ⅰ而言，若Ⅱ選取,,時(shí)，Ⅰ的最小可能收入為以下四條直線在x處縱坐標(biāo)中的最小者,v=2x+4(1-x)=4-2x (1)v=3x+(1-x)=2x+1 (2)v=x+6(1-x)=-5x+6

44、 (3)v=5x (4),2024/4/2,Operations Research,69,,6.6.1 圖解法,從圖上可以看出 B點(diǎn)坐標(biāo)即為所求的極值點(diǎn).,A,B,(2),(3),(1),(4),B點(diǎn)坐標(biāo)為:,即,Ⅰ的最優(yōu)解為,2024/4/2,Operations Research,70,6.6.1 圖解法,同理可得：

45、 v=2y1+3y2+y3+5y4 (5) v=4y1+y2+6y3 (6)由上節(jié)的定理3求出Ⅱ的最優(yōu)解 將 分別代入方程(1)～(4)得：,2024/4/2,Operations Research,71,6.6.1 圖解法,,,定理3的(4),定理3的(2),定理3的(2),定理3的(4),2024/4/2,Opera

46、tions Research,72,6.6.1 圖解法,代入(5)、(6)得：,,解之得：,故Ⅱ的最優(yōu)策略為,2024/4/2,Operations Research,73,,6.6.2 優(yōu)勢(shì)法,對(duì)于一般的矩陣對(duì)策,其中,定義3 若對(duì)固定的i、k有,若對(duì)固定的j和l，有,則稱,優(yōu)超,，記為,則稱,優(yōu)超,，記為,2024/4/2,Operations Research,74,,6.6.2 優(yōu)勢(shì)法,,,,,,,,,,,,

47、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(1),,,,定理4 設(shè)G中的某個(gè),被其余的,之一優(yōu)超,,由G可得,，其中,于是有,(2),中局中人Ⅱ的最優(yōu)策略就是G中Ⅱ的,最優(yōu)策略；,2024/4/2,Op

48、erations Research,75,,6.6.2 優(yōu)勢(shì)法,若,是Ⅰ在,中的最優(yōu)解，則,為Ⅰ在G中的最優(yōu)解.,(3),2024/4/2,Operations Research,76,6.6.2 優(yōu)勢(shì)法,例10 已知某矩陣對(duì)策G的支付矩陣為：,求解這個(gè)矩陣對(duì)策。,2024/4/2,Operations Research,77,,,6.6.2 優(yōu)勢(shì)法,解：顯然無(wú)鞍點(diǎn)，由于A的階數(shù)為,圖解法失效。由定義可知,由定理1可

49、將該問題簡(jiǎn)化為:,2024/4/2,Operations Research,78,,,,6.6.2 優(yōu)勢(shì)法,可用圖解法求得最優(yōu)解和值分別為：,由,又可看出：,從,又可看出：,，因此得：,2024/4/2,Operations Research,79,,6.6.2 優(yōu)勢(shì)法,即可得到對(duì)策G的解為：,值為,V=5。,2024/4/2,Operations Research,80,6.6.3 簡(jiǎn)化計(jì)算法,,,,,,,,,,,,,

50、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,定理5 若矩陣對(duì)策,,,,,其中d為常數(shù)，則G1與G2有相同的解，且對(duì)策的值相差一個(gè)常數(shù)d，即：,,,2024/4/2,Operati

51、ons Research,81,6.6.3 簡(jiǎn)化計(jì)算法,推論1 若矩陣對(duì)策,其中k>0為常數(shù)，則G1與G2有相同的解,且,2024/4/2,Operations Research,82,6.6.3 簡(jiǎn)化計(jì)算法,例11 已知某矩陣對(duì)策G的支付矩陣如下：,解：由推論1可取,得同解矩陣：,2024/4/2,Operations Research,83,,,6.6.3 簡(jiǎn)化計(jì)算法,由定理1可取d=-2，簡(jiǎn)化為：,由

52、v=4x+0(1-x) =4x v=0x+1(1-x)=1-x,則,由 v=4y+0(1-y) =4y v=0y+1(1-y)=1-y,則,2024/4/2,Operations Research,84,6.6.3 簡(jiǎn)化計(jì)算法,∴原問題的解為：,2024/4/2,Operations Research,85,6.6.4 線性規(guī)劃解法,考慮一般的問題：

53、 其中,其混合擴(kuò)充為：,2024/4/2,Operations Research,86,6.6.4 線性規(guī)劃解法,當(dāng)局中人選定任一混合策略時(shí)便確定了n個(gè)數(shù)：,因?yàn)榫种腥刷竦闹Ц镀谕禐椋?2024/4/2,Operations Research,87,6.6.4 線性規(guī)劃解法,若矩陣對(duì)策的值為則由定理2可知(參見309的陳述),2024/4/2,Operations Research,88,,6.6.4 線性規(guī)劃

54、解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,不失一般，假設(shè)V>0,令,,,,,,,定

55、理 2的第一組不等式,2024/4/2,Operations Research,89,6.6.4 線性規(guī)劃解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

56、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Ⅰ,,,,,2024/4/2,Operations Research,90,6.6.4 線性規(guī)劃解法,同理Ⅱ的最優(yōu)混合策略可以化歸為：,,,,,,Ⅱ,值大于零的矩陣對(duì)策的求解可以轉(zhuǎn)化成為求解一對(duì)互為對(duì)偶的線性規(guī)劃問題(Ⅰ)和(Ⅱ).,2024/4/2,Operations Research,91,6.6.4 線性規(guī)劃解法,例12 設(shè)有一個(gè)矩陣對(duì)

57、策，其局中人Ⅰ的 支付矩陣為,求最優(yōu)解及值。,2024/4/2,Operations Research,92,6.6.4 線性規(guī)劃解法,解：顯然無(wú)鞍點(diǎn)解，求解問題可化成兩個(gè)互為對(duì)偶的線性規(guī)劃問題：,,,2024/4/2,Operations Research,93,6.6.4 線性規(guī)劃解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

58、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/4/2,Operations Research,94,6.6.4 線性規(guī)劃解法,,,,,,,,,,,,,,,,

59、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,通過線性規(guī)劃(Ⅰ’)或(Ⅱ’)可得：,