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

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

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

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

4、rn”對策論與經(jīng)濟行為” （Theory of Games and Economic Behavior）發(fā)展成熟 Nash均衡、經(jīng)濟博奕論、信息不對稱對策和廣義對策,2024/4/2,Operations Research,7,6.2 對策論的基本概念,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、局中人：在一場競爭或斗爭中的決策者稱為該局對策的局中人 通常，一局對策具有兩個或兩個以上---決策者，一般用I表示局中人集合：,,2024/4/2,Operations Research,9,6.2.1 局中人（Player）,,,,,,2、對策分類：依據(jù)局中人的數(shù)量，可將對策分為,有限對策,無限對策(n>2),對策,,無限零和對策,無限非零和對策,有限零和對

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

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

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

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

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

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

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

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

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

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

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

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

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

19、,,,,,,,,,,對局中人Ⅰ來講，各策略的最壞結(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 矩陣對策的純策略解例解過程,,,,,,,,,,,,,,,,,,,,,,,,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、ions Research,64,6.6.1 圖解法,同理，對局中人Ⅱ而言有,V=5y+35(1-y)=35-30y V=20y+10(1-y)=10+10y,最小最大點為:,即,Ⅱ的最優(yōu)解為 ：,對策值為：,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：求解下列矩陣對策，已知贏得矩陣為：,,,,,,2024/4/2,Operations Research,67,,6.6.1 圖解法,例9 已知：,其中,求對策的解和值。,解：顯然無鞍點，作混合擴充：,2024/4/2,Operations Research,68,,6.6.1 圖解法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

43、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,對局中人Ⅰ而言，若Ⅱ選取,,時，Ⅰ的最小可能收入為以下四條直線在x處縱坐標中的最小者,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點坐標即為所求的極值點.,A,B,(2),(3),(1),(4),B點坐標為:,即,Ⅰ的最優(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)勢法,對于一般的矩陣對策,其中,定義3 若對固定的i、k有,若對固定的j和l，有,則稱,優(yōu)超,，記為,則稱,優(yōu)超,，記為,2024/4/2,Operations Research,74,,6.6.2 優(yōu)勢法,,,,,,,,,,,,

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

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

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

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

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

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 簡化計算法,∴原問題的解為：,2024/4/2,Operations Research,85,6.6.4 線性規(guī)劃解法,考慮一般的問題：

53、 其中,其混合擴充為：,2024/4/2,Operations Research,86,6.6.4 線性規(guī)劃解法,當(dāng)局中人選定任一混合策略時便確定了n個數(shù)：,因為局中人Ⅰ的支付期望值為：,2024/4/2,Operations Research,87,6.6.4 線性規(guī)劃解法,若矩陣對策的值為則由定理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)混合策略可以化歸為：,,,,,,Ⅱ,值大于零的矩陣對策的求解可以轉(zhuǎn)化成為求解一對互為對偶的線性規(guī)劃問題(Ⅰ)和(Ⅱ).,2024/4/2,Operations Research,91,6.6.4 線性規(guī)劃解法,例12 設(shè)有一個矩陣對

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

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

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