對策論運籌學講義

對策論運籌學講義第一頁，共六十五頁，2022年，8月28日對策論或博弈論(GameTheory)是研究具有對抗和競爭性行為問題的數(shù)學理論與方法。是運籌學的重要分支學科經(jīng)濟學領域一般稱博弈論，是經(jīng)濟學領域近幾十年發(fā)展起來一門新興學科對策論從理論上作嚴格的討論卻起始于二十世紀：1912年，德國數(shù)學家E.Zermelo證明了國際象棋的3種著法必定存在一種；1921年，法國數(shù)學家E.Borel引入了“最優(yōu)策略”等概念；1928年，美籍匈牙利人J.VonNeumann證明了對策論的基本定理----最大值最小值定理；1944年，VonNeumann和O.Morgenstern合寫了《對策論與經(jīng)濟行為》一書，建立起對策論的基本理論，奠定了對策論研究的基礎。第二頁，共六十五頁，2022年，8月28日對策問題舉例例1猜單和猜雙的博弈。兩個人同時出一個指頭或兩個指頭，如果兩人出的指頭相同，則局中人1從局中人2處贏得五元；如果出的不一樣，局中人1就要支付給局中人2五元。兩個對手都可以采取兩個策略：出一個手指和出兩個手指，下表是局中人1的贏得矩陣(二指莫拉問題)策略局中人2出1指出2指局中人1出1指5－5出2指－55局中人1從局中人2該如何選擇策略，已獲得利益？第三頁，共六十五頁，2022年，8月28日例2囚徒困境。兩個嫌疑犯作案后被警察抓住，分別被關在不同的屋子里審訊。警察告訴他們：如果兩人都坦白，各判刑8年；如果兩人都抵賴，由于證據(jù)不充分，兩人將各判刑2年；如果其中一人坦白，，另一人抵賴，則坦白者立即釋放，抵賴者判刑10年。在這個例子中兩人嫌疑犯都有兩種策略：坦白或抵賴?？梢杂靡粋€矩陣表示兩個嫌疑犯的策略的損益策略囚徒2坦白抵賴囚徒1坦白(－8,－8)(0,－10)抵賴(－10,0)(－2,－2)囚徒該如何選擇策略？囚徒困境反映了個人理性和集體理性的矛盾。對于雙方，（抵賴，抵賴）的結果是最好的，但因為每個囚徒都是理性人，他們追求自身效應的最大化，結果就變成了（坦白，坦白）。個人理性導致了集體不理性第四頁，共六十五頁，2022年，8月28日例3田忌與齊王賽馬

戰(zhàn)國時期，齊威王與大將田忌賽馬，雙方約定：從各自的上、中、下三個等級的馬中各選一匹馬出場比賽，負者要付給勝者一千金。已知田忌的馬要比齊王同一等級的馬差一些，但比齊王等級較低的馬卻要強一些。因此，如用同等級的馬對抗，田忌必連輸三場，失三千金無疑。田忌的謀士孫臏給田忌出了個主意：每局比賽前先了解齊王參賽馬的等級，再采用下等馬對齊王上等馬、中等馬對齊王下等馬、上等馬對齊王中等馬的策略。比賽結果，田忌二勝一負，反而贏得一千金。由此可見，雙方各采取什么樣的出馬次序對勝負至關重要。第五頁，共六十五頁，2022年，8月28日“齊王賽馬”齊王在各局勢中的益損值表(單位：千金)齊王和田忌可以任意選擇三匹馬出場的順序第六頁，共六十五頁，2022年，8月28日§1

對策論的基本概念對策模型的三個基本要素：1.局中人(Players)：參與對抗的各方；2.策略集(Strategices):局中人選擇對付其它局中人的行動方案稱為策略；某局中人的所有可能策略全體稱為策略集3.一局勢對策的益損值：局中人各自使用一個對策就形成了一個局勢，一個局勢決定了各局中人的對策結果（量化）稱為該局勢對策的益損值。

贏得函數(shù)(payofffunction)：定義在局勢上，取值為相應益損值的函數(shù)4.

納什均衡：納什均衡指所有局中人最優(yōu)策略組成的一種局勢，既在給定其他局中人策略的情況下，沒有任何局中人有積極性去選擇其他策略第七頁，共六十五頁，2022年，8月28日對策的分類對策按對策方式合作對策非合作對策完全理性有限理性兩人對策零和對策非零和對策多人對策結盟對策不結盟對策按對策人數(shù)靜態(tài)對策完全信息靜態(tài)對策不完全信息靜態(tài)對策動態(tài)對策完全信息動態(tài)對策不完全信息動態(tài)對策按對策狀態(tài)第八頁，共六十五頁，2022年，8月28日二人有限零和對策（又稱矩陣對策）：局中人為2；每個局中人的策略集的策略數(shù)目都是有限的；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。通常將矩陣對策記為:G={S1,S2,A}局中人甲的策略集：局中人乙的策略集：甲的贏得矩陣：

矩陣對策aij為局中人甲在局勢下的贏得第九頁，共六十五頁，2022年，8月28日其中：齊王的策略集:S1={1,2,3,4,5,6}，田忌的策略集：S2={1,2,3,4,5,6}。下面矩陣稱齊王的贏得矩陣：

3111-1113111-1A=1-13111-111311111-13111-1113“齊王賽馬”是一個矩陣策略。第十頁，共六十五頁，2022年，8月28日§2

矩陣對策的最優(yōu)純策略例4

甲、乙兩隊進行球賽，雙方各可排出三種不同的陣容。設甲隊為局中人Ⅰ，乙隊為局中人Ⅱ，每一種陣容為一個策略，有S1=｛α1,α2,α3｝，S2

=｛β1,β2,β3｝。根據(jù)以往兩隊比賽的記錄，甲隊得分情況的贏得矩陣為問：這次比賽中，雙方應如何對陣？第十一頁，共六十五頁，2022年，8月28日在如此反復對策的過程中，各局中人如果不想冒險，就應該考慮從自身可能出現(xiàn)的最壞情況下著眼，去選擇一種盡可能好的結果，即雙方都是從各自可能出現(xiàn)的最不利的情形選擇一種最為有利的情況作為決策的依據(jù)。這就是所謂“理智行為”。稱為最小最大準則，按照這個各方均避免冒險的觀念，就形成如下的推演過程。解

從A中可以看出，Ⅰ最多可得6分。于是，Ⅰ為得6分而選α2

。但是Ⅱ推測Ⅰ會有此心理，從而選β3來對付，使得Ⅰ非但得不到6分，反而要失去3分。當然Ⅰ也會料到Ⅱ會有此心理，從而改選α3

，以使Ⅱ欲得3分而反失4分。第十二頁，共六十五頁，2022年，8月28日矩陣A中每行的最小元素分別為1，-3，-5。

在這些最少贏得中最好的結果是1，故局中人Ⅰ會采取策略1，無論對手采取何策略，局中人Ⅰ至少得1分。對于局中人Ⅱ，{1，2，3}可能帶來的最少贏得，即A中每列的最大元素，分別為6，1，4。局中人Ⅱ會采取2策略，確保局中人Ⅰ不會超過1分。1和2分別稱為局中人Ⅰ、Ⅱ的最優(yōu)策略。由于雙方必然選擇這一種策略，所以，這種策略又稱為最優(yōu)純策略?！?

矩陣對策的最優(yōu)純策略Min1－3－56Max14123123第十三頁，共六十五頁，2022年，8月28日定義1設有矩陣對策G=｛S1,S2;A｝,其中，

A=[aij]m×n

，若有則局勢

(αi*

，βj*)

稱為G在純策略意義下的解，也稱為G的鞍點；αi*

、βj*分別稱為局中人Ⅰ和Ⅱ的最優(yōu)純策略；v稱為G的值，也稱對策值。

對于例4，G的解(鞍點)為(α1,β2)，α1

、β2分別為Ⅰ、Ⅱ的最優(yōu)策略。對策值v=1>0，反映優(yōu)勢在Ⅰ方(對Ⅰ有利)；若v<0，則優(yōu)勢在Ⅱ方(對Ⅱ有利)

；當v=0時，稱為公平對策。第十四頁，共六十五頁，2022年，8月28日矩陣對策有解的條件現(xiàn)在，討論矩陣對策在純策略意義下有解的充分必要條件。定理1

設G=｛S1,S2

；A｝，其中，，A=[a

ij]m×n

，G在純策略意義下有解的充要條件是：存在純局勢(αi*

，βj*)

，使得對一切i(i＝1,…,m)和j(j＝1,…,n)有證先證充分性設對任意i和j，均有又因為i*行最小元，j*列中最大元i*行最小元1

行最小元第十五頁，共六十五頁，2022年，8月28日另一方面(P209引理)，對于任意i和j有

故

綜合(1)和(2)式，有所以，G在純策略意義下有解i行中最小元j列中最大元

所以有從每列最大元中取最小元第十六頁，共六十五頁，2022年，8月28日證明必要性設G在純策略意義下有解，即成立因在i=i*

時達到最大，即

在j=j*

時達到最小，即同樣定理1說明了G在純策略意義下有解的充分必要條件是：A中存在這樣一個元素，既是所在行的最小元素，也是所在列的最大元素。換言之，有純策略解與存在鞍點等價，這正是VonNeumann當年所證明的。這個著名結論所體現(xiàn)的基本理性思想，就是：“做最壞的打算，尋求最好的結果”。第十七頁，共六十五頁，2022年，8月28日例5已知矩陣對策G,其中：問：G是否存在鞍點？解因不符合鞍點條件，故G的鞍點不存在。但是否每個矩陣對策一定存在鞍點呢？回答是否定的?，F(xiàn)在考察下例。例6

求解矩陣對策，其中：解容易得到由此可見，G的解可以不唯一，但G的值必是唯一的。第十八頁，共六十五頁，2022年，8月28日定義2

設有矩陣對策G={S1,S2;A},其中:

A=[aij]m×n

,概率向量當矩陣對策G在純策略意義下無解時，由于不存在鞍點，即不存在平衡局勢，各局中人的決策總有一定的風險。因此，無理由只取某個策略而舍棄其余策略，也就是局中人應考慮，按照預先確定的一組概率來選取其所有可能采用的策略?！?矩陣對策的混合策略分別稱X,Y為局中人Ⅰ和Ⅱ的“混合策略”。向量組

(X,Y)

稱為混合局勢。數(shù)學期望稱為局中人Ⅰ的贏得。(4)第十九頁，共六十五頁，2022年，8月28日X、Y的全體分別構成Ⅰ、Ⅱ的混合策略集，記作稱

為G的混合擴充。純策略對策是混合策略對策的特例，此時，概率向量為單位向量。一個混合策略可理解為：如果進行多次對策G的話，局中人Ⅰ分別選取純策略α1,α2,…,αm采的頻率。如果只進行一次對策，則反映局中人Ⅰ對各種純策略的偏好程度。第二十頁，共六十五頁，2022年，8月28日例7擲硬幣投注的對策兩個局中人之間開展有裁判的擲硬幣游戲，無論出現(xiàn)正面還是反面，裁判將結果告訴局中人甲，局中人甲看完結果后，有兩種選擇：(1)放棄投注并支付給局中人乙5美元。如果局中人甲放棄，游戲就結束了。但如果局中人甲投注(beton),游戲繼續(xù)，這時局中人乙也有兩種選擇：(1)放棄投注并支付5美元給局中人甲；(2)跟著下注。如果局中人乙選擇下注，裁判將投幣結果展示給乙看，如果是正面，局中人乙支付10美元給局中人甲；如果是反面，則局中人甲支付給局中人乙10美元。（1）試寫出對策中各局中人的策略集（2）建立局中人甲的贏得矩陣（3）判斷對策是否存在鞍點（4）求解此矩陣對策第二十一頁，共六十五頁，2022年，8月28日解（1）分析對策雙方可能采取的策略情況，投幣的情況有兩種可能，甲根據(jù)看到情況做出反映，乙根據(jù)甲的的選擇做出反映。對于局中人甲，可能的策略有4個，每個都是他對裁判給他看的硬幣出現(xiàn)正、反面兩種結果后分別做出的反映：（1）局中人甲在任何情況下放棄投注；（2）局中人甲在任何情況下均投注；（3）硬幣出現(xiàn)正面時投注，出現(xiàn)反面時放棄投注；（4）硬幣出現(xiàn)反面時投注，出現(xiàn)正面時放棄投注，分別將四種策略記為：α1,α2,α3,α4。局中人乙有兩個策略：(1)放棄投注和(2)跟著下注，分別記為β1,β2（2）當局中人甲選擇α1時，他的贏得均為－5。

當甲選擇α2時，如果乙選擇β1，由于出現(xiàn)正面和反面的概率均為1/2，則甲贏得：1/2×5＋1/2×5＝

5；▲甲選α2而乙選擇β2，這時出現(xiàn)正面，甲贏得10，如果反面，則甲贏得－10，出現(xiàn)正面和反面的概率均為1/2，所以甲的贏得為:1/2×10＋1/2×(－10)＝0第二十二頁，共六十五頁，2022年，8月28日（2）當甲選擇α3時，如果乙選擇β1

。甲出現(xiàn)反面時放棄投注,收益為－5，甲出現(xiàn)正面時投注，甲獲得5，出現(xiàn)正反面的概率均為1/2，故甲贏得為

1/2×5＋1/2×(－5)＝0

▲當甲選擇α3時，如果乙選擇β2，甲放棄時，贏得－5；甲投注時，硬幣正面，甲贏得10，甲贏得為：

1/2×10＋1/2×(－5)＝2.5

當甲選擇α4時，如果乙選擇β1，甲放棄時，贏得－5；

甲投注時，贏得5，出現(xiàn)正反面的概率均為1/2，故甲贏得為1/2×(－5)＋1/2×5＝0

▲甲選擇α4時，如果乙選擇β2，甲放棄時，贏得－5；甲投注時，贏得－10，出現(xiàn)正面和反面的概率均為1/2，所以甲1/2××(－5)＋1/2×(－10)＝－7.5第二十三頁，共六十五頁，2022年，8月28日局中人甲局中人乙β1,β2α1－5－5α250α302.5α40－7.5甲的贏得矩陣為Min－500－7.5Max52.5（3）不存在鞍點（4）后面介紹求解第二十四頁，共六十五頁，2022年，8月28日定義3

設是矩陣對策G={S1,S2;A}的混合擴充，如果則稱vG為對策G*的值，使上式成立的(X*,Y*)為G在混合意義下的解（納什均衡），稱X*和Y*分別為局中人Ⅰ和Ⅱ的最優(yōu)混合策略。當局中人Ⅰ取混合策略X，局中人Ⅱ將選用混合策略，使得故Ⅰ應選取X*，使贏得至少為同理當Ⅱ取混合策略Y，局中人將選用混合策略，使得故Ⅱ應選取Y*，使支付至多為(5)第二十五頁，共六十五頁，2022年，8月28日定理2

矩陣對策G={S1,S2;A}在混合策略意義下有解的充分必要條件為：存在混合局勢(X*,Y*)，使得對一切X∈S1*

和Y∈S2*，有E(X,Y*)≤E(X*,Y*)≤E(X*,Y)

(X*,Y*)

即為對策G解，且vG=E(X*,Y*)。定理2的證明與定理1相似，只需把aij

換成E(X,Y)例8考慮例5的矩陣對策G={S1,S2;A}在混合意義下的解解，設和分別為局中人Ⅰ和Ⅱ的混合策略則(6)第二十六頁，共六十五頁，2022年，8月28日

矩陣對策的基本定理先給出兩個記號:當局中人Ⅰ取純策略αi

時的贏得值為

(矩陣A第i行乘以Y)

當局中人Ⅱ取純策略βj

時的贏得值為

(X乘以矩陣A第j列)

取時，E(X*,Y*)＝E(X,Y*)＝E(X*,Y)＝。E(X,Y*)≤E(X*,Y*)≤E(X*,Y)。根據(jù)定理2

和分別局中人Ⅰ和Ⅱ的最優(yōu)策略，對策值vG＝E(X*,Y*)＝ij第二十七頁，共六十五頁，2022年，8月28日則有定理3

設X*∈S1*，Y*∈S2*，則(X*,Y*)是對策G在混合意義下解的充要條件是：對任意i＝1,…,m和j＝1,…,n，有

E(i,Y*)≤E(X*,Y*)≤E(X*,j)

證明設(X*,Y*)是對策G的解，則由定理2,(6)式成立，由于純策略是混合策略的特例，故(8)式成立。反之，設(8)式成立，由(7)(8)(6)式成立，由定理2，(X*,Y*)是對策G的解第二十八頁，共六十五頁，2022年，8月28日定理4

設X*∈S1*，Y*∈S2*，則(X*,Y*)是對策G在混合意義解的充要條件是：存在數(shù)v，使得X*和Y*分別是不等式組Ⅱ取任意純策略βj

時的贏得值E(X,j)Ⅰ取任意純策略αi

時的贏得值E(i,Y)第二十九頁，共六十五頁，2022年，8月28日定理4證明略其實必要性顯然，取v＝E(X*,Y*)即可充分性考慮可推出E(i,Y*)≤E(X*,Y*)≤E(X*,j)

第三十頁，共六十五頁，2022年，8月28日定理5

任對一矩陣對策G＝{S1,S2;A}，一定存在混合策略意義下的解。證明可見胡運權《運籌學教程》P396在證明過程中，構造兩個對偶的線性規(guī)劃，兩個線性規(guī)劃的最優(yōu)解為(X*,w*)和(Y*,v*)，且滿足w*＝v*，則可推出(X*,Y*)為對策G的解，

w*＝v*＝E(X*,Y*)為對策的值第三十一頁，共六十五頁，2022年，8月28日定理6

設(X*,Y*)是矩陣對策G的解，v

＝vG，則記T(G)為矩陣對策G的解集定理7設有兩個矩陣對策G1＝{S1,S2;A1},G2＝{S1,S2;A2},其中A1=(aij),A2=(aij+L),L為一常數(shù)。則

(1)(2)T(G1)=T(G2)Ⅱ取純策略βj

時的贏得值E(X*,j)Ⅰ取純策略αi

時的贏得值E(i,Y*

)第三十二頁，共六十五頁，2022年，8月28日定理8設有兩個矩陣對策G1＝{S1,S2;A},G2＝{S1,S2;αA},其中α>0,為任一常數(shù)。則

(1)(2)T(G1)=T(G2)定理9設G＝{S1,S2;A}為一矩陣對策，且A=－AT為斜對稱矩陣，稱這樣的對策為對稱對策，則

(1)vG=0(2)T1(G)=T2(G)其中T1(G)和T2(G)分別為局中人Ⅰ和Ⅱ的最優(yōu)策略集定理7和8可以用來簡化矩陣中的元素數(shù)字，使得以后的求解更為方便。第三十三頁，共六十五頁，2022年，8月28日矩陣對策的解法

1優(yōu)超原則法

設有矩陣對策G={S1,S2;A},其中:

A=[aij]m×n

,如果對一切j=1,…,n,都有即矩陣的第行元素均不小于行的元素，則稱局中人Ⅰ的純策略優(yōu)超于純策略；同樣，若對于一切i=1,…,m,有，即矩陣的第列均不大于列的元素，則稱局中人Ⅱ的純策略優(yōu)超于純策略第三十四頁，共六十五頁，2022年，8月28日當局中人Ⅰ的純策略優(yōu)超于純策略時，局中人Ⅰ采用策略超過采用策略；當稱局中人Ⅱ的純策略優(yōu)超于純策時，局中人Ⅱ采用純策略超過采用純策略。在求解矩陣對策時，如果出現(xiàn)上述優(yōu)超情況，可將矩陣A的第行刪除；當Ⅱ的純策略優(yōu)超于純策時，可以將矩陣A第列刪除。優(yōu)超原則可以縮小了A的規(guī)模，使計算簡化。一般情況下，優(yōu)超原理只是一種降階技術，但如精簡之后，A中的剩余元素僅有一個，則意味著已求得了對策的鞍點。第三十五頁，共六十五頁，2022年，8月28日

例9

求解矩陣對策，其中：解查視各列，發(fā)現(xiàn)可劃去第1列，得查視各行，發(fā)現(xiàn)可劃去第3行，得查視各行列，知已無法繼續(xù)優(yōu)超，故原矩陣A被簡化為2×2規(guī)模。第三十六頁，共六十五頁，2022年，8月28日二、2×2公式解法設矩陣對策中的A為若無鞍點，則X*與Y*中各分量必不為零(否則，假定，則，局中人Ⅰ選擇純策略α1，局中人Ⅱ選擇中最小元素對應的策略，即對策存在有鞍點)。由定理6的(3)、(4)，得第三十七頁，共六十五頁，2022年，8月28日二、2×2公式解法求解后，得：(11)第三十八頁，共六十五頁，2022年，8月28日用2×2求解例5已知矩陣對策G,其中：解G是不存在鞍點用2×2求解例9第三十九頁，共六十五頁，2022年，8月28日求解例7已知矩陣對策G,其中：解利用優(yōu)超原理得用公式計算得：矩陣對策的解：X*=(0，1/3,2/3，0)T,Y*=(1/3,2/3)T

vG=5／3第四十頁，共六十五頁，2022年，8月28日三、2×n和m×2圖解法

當對策雙方中的某一方策略個數(shù)為2，而另一方策略個數(shù)大于2時，可以采用圖解法來方便地求解這類對策問題。下面通過例子來介紹這種直觀的幾何方法。用一個例子來看解法例10求解矩陣對策，其中:解顯然，G無鞍點且無優(yōu)超關系。設局中人Ⅰ的混合策略為X=(x1,x2)T=(x,1－x)T，則按“理智行為”，Ⅰ期望的贏得為1.考慮2×n階矩陣第四十一頁，共六十五頁，2022年，8月28日在Oxv平面直角坐標系中，x∈[0,1]

畫直線段（圖10-1）：L1

：v

=-8x+9L2

：v=7xL3

：v=15x-2圖10-1xvO2468101Cx*DEFL1L2L3第四十二頁，共六十五頁，2022年，8月28日于是，v=f(x)

的圖形就是折線CDEF。因為E點是折線的最高點，所以v=f(x*)。注意到E點是L1與L2的交點，求解得x*=3／5，vG=21／5，Ⅰ的最優(yōu)混合策略為X*=(3/5,2/5)T。圖10-1xvO2468101Cx*DEFL1L2L3設局中人Ⅱ的最優(yōu)混合策略為Y*=(y1*，y2*，y3*)T，則由定理6知第四十三頁，共六十五頁，2022年，8月28日圖10-1xvO2468101Cx*DEFL1L2L3根據(jù)定理6得y3*=0。也可根據(jù)E點只與L1、L2有關且此處L3高于E點，即只與β1,β2有關且β3不必考慮,所以,y3*=0，代入上式，可解得

y1*

=7／15，y2*=8／15。于是，Ⅱ的最優(yōu)混合策略為

Y*=(7/15,8/15,0)T。矩陣對策的解

X*=(3/5,2/5)T,Y*=(7/15,8/15,0)TvG=21／5注意：第四十四頁，共六十五頁，2022年，8月28日例11求解矩陣對策，其中:解顯然，G無鞍點使用優(yōu)超原理，α1優(yōu)超α4，刪去第4行，將A簡化為設局中人Ⅱ的混合策略為Y=(y1,y2)T=(y,1－y)T，則按“理智行為”，Ⅱ期望的贏得為2.考慮m×2階矩陣第四十五頁，共六十五頁，2022年，8月28日在Oxv平面直角坐標系中，y∈[0,1]

畫直線段（圖10-2）：L1

：v

=6y－5L2

：v=－8y＋4L3

：v=－5y＋3圖10-2yvO24－61Fy*DECL1L2L3－4－2v=g(y)

的圖形就是折線CDEF。因為E點是折線的最低點，所以

v=g(y*)。注意到E點是L1與L3的交點，求解第四十六頁，共六十五頁，2022年，8月28日圖10-2yvO24－61Fy*DECL1L2L3－4－2求解得y*=8／11，v=－7／11，Ⅱ的最優(yōu)混合策略為Y*=(8/11,3/11)T。設局中人Ⅰ的最優(yōu)混合策略為:X*=(x1*，x2*，x3*，0)T，y1*＞0,y2*＞0則由定理6知第四十七頁，共六十五頁，2022年，8月28日圖10-2yvO24－61Fy*DECL1L2L3－4－2矩陣對策的解：

X*=(5/11,0,6/11,0)T

，Y*=(8/11,3/11)T。v

G=－7／11根據(jù)定理6得x2*=0。也可根據(jù)由于E點只與L1、L3相關,且此處L2低于E點，即只與α1、α3相關且α2不必考慮，所以x2*=0，代入上式，可解得x1*=5／11，x3*=6／11。于是，Ⅰ的最優(yōu)混合策略為X*=(5/11,0,6/11,0)T。第四十八頁，共六十五頁，2022年，8月28日

四、線性規(guī)劃解法(最通用、應用最廣的方法)對于前述各種方法全都失效的一般形式的矩陣對策，線性規(guī)劃解法是最通用的方法，可以求解任一矩陣對策。由定理5知，求解矩陣對策可等價地轉化為求解互為對偶的線性規(guī)劃（P）和（D），故在問題（P）中，令。則問題(P)的約束條件變?yōu)椋簡栴}(P)等價與線性規(guī)劃問題()(12)

乘以A第j列第四十九頁，共六十五頁，2022年，8月28日

四、線性規(guī)劃解法(最通用、應用最廣的方法)同理在問題（D）中，令可知問題(D)等價于線性規(guī)劃問題()(13)

問題()和()是互為對偶的線性規(guī)劃，可用單純形或對偶單純形法求解，再由變換(12)和(13)，即可得到原問題的解和對策值A第i行列乘以第五十頁，共六十五頁，2022年，8月28日例12

求解矩陣對策，其中：解易知，G無鞍點且無法優(yōu)超。求解問題可化成線性規(guī)劃問題迭代后，得規(guī)劃最優(yōu)解：

=(1/14,11/196,5/49)T，對偶規(guī)劃最優(yōu)解

=(5/49,11/196,1/14)T，最優(yōu)值z*=45／196，vG

=1／z*=196／45，X*=v=(20/45,11/45,14/45)TY*=v=(14/45,11/45,20/45)T第五十一頁，共六十五頁，2022年，8月28日例：求解“齊王賽馬”問題。已知齊王的贏得矩陣A求得故不存在純策略問題下的解，可求其混合策略。A中有負元素，可以取k=2,在A的每個元素上加2得到A’如下：§4矩陣對策的混合策略第五十二頁，共六十五頁，2022年，8月28日

建立對G′={S1，S2，A′}中求甲方最佳策略的線性規(guī)劃如下：

Minx1+x2+x3+x4+x5+x6s.t.5x1+3x2+3x3+x4+3x5+3x6≥13x1+5x2+x3+3x4+3x5+3x6≥13x1+3x2+5x3+3x4+3x5+x6≥13x1+3x2+3x3+5x4+x5+3x6≥1x1+3x2+3x3+3x4+5x5+3x6≥13x1+x2+3x3+3x4+3x5+5x6≥1

xi≥0,i=1,2,…,6

可解得解為：x1=x4=x5=0,x2=x3=x6=0.111,v′=3,x1′=x4′=x5′=0，x2′=v′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，此時V′G=V′－2=1。第五十三頁，共六十五頁，2022年，8月28日

同樣可以建立對策G′={S1，S2，A′}中求乙方最佳策略的線性規(guī)劃如下：

Miny1+y2+y3+y4+y5+y6

約束條件：

5y1+3y2+3y3+3y4+y5+3y6≤13y1+5y2+3y3+3y4+3y5+y6≤13y1+y2+5y3+3y4+3y5+3y6≤1y1+3y2+3y3+5y4+3y5+3y6≤13y1+3y2+3y3+y4+5y5+3y6≤13y1+3y2+y3+3y4+3y5+5y6≤1yi≥0,i=1,2,…,6

可解得解為：

y1=y4=y5=0.111,y2=y3=y6=0,v′=3,y1′=y4′=y5′=1/3，

y2′=y3′=y6′=0，即Y′*=(1/3,0,0,1/3,1/3,0)T。所以田忌的最優(yōu)混合策略為作出策略1、4、5的概率都為1/3,而作出2，3，6的概率為0，此時VG=VG′-k=1?！?矩陣對策的混合策略第五十四頁，共六十五頁，2022年，8月28日

齊王賽馬問題的對策最優(yōu)解可簡記為X*=(0,1/3,1/3,0,0,1/3)T，Y*=(1/3,0,0,1/3,1/3,0)T，對策值VG=1。例兩個局中人進行對策，規(guī)則是兩人互相獨立的各自從1、2、3這三個數(shù)字中任意選寫一個數(shù)字。如果兩人所寫的數(shù)字之和為偶數(shù)，則局中人乙支付給局中人甲以數(shù)量為此和數(shù)的報酬；如果兩人所寫數(shù)字之和為奇數(shù)，則局中人甲付給局中人乙以數(shù)量為此和數(shù)的報酬。試求出其最優(yōu)策略。解：首先計算局中人甲的贏得矩陣如下表：4-56-34-52-341（出1）2（出2）3（出3）3（出3）2（出2）1（出1）甲的贏得甲的策略乙的策略第五十五頁，共六十五頁，2022年，8月28日即甲的贏得矩陣為A：

可知無純策略意義的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立線性規(guī)劃模型如下：

Minx1+x2+x3Maxy1+y2+y31+3x2+10x3≥18y1+3y2+10y3≤13x1+10x2+x3≥13y1+10y2+y3≤110x1+x2+12x3≥110y1+y2+12y3≤1x1,x2,x3≥0y1,y2,y3≥0

§4矩陣對策的混合策略第五十六頁，共六十五頁，2022年，8月28日得到x1′=0.25,x2′=0.50,x3′=0.25；y1′=0.25,y2′=0.50,y3′=0.25。即此對策的解為X*=(0.25,0.50,0.25)T，Y*=(0.25,0.50,0.25)T。VG=VG′-k=0?！?矩陣對策的混合策略第五十七頁，共六十五頁，2022年，8月28日例4

甲乙兩個企業(yè)生產(chǎn)同一種電子產(chǎn)品，甲企業(yè)可以采取的策略措施有:(1)降低產(chǎn)品價格；(2)提高產(chǎn)品質量；(3)推出新產(chǎn)品。乙企業(yè)考慮采取的策略措施有(1)增加廣告費用；(2)增設維修網(wǎng)點，加強售后服務；(3)改進產(chǎn)品性能。由于甲乙兩個企業(yè)財力有限，都只能采取一個措施。假定這兩個企業(yè)所占有的市場總份額一定，由于各自采取的措施不同，通過預測今后兩個企業(yè)的市場占有份額變動情況如下表，試求出這兩個企業(yè)各自的最優(yōu)策略。3-58-6510108-121（措施1）2（措施2）3（措施3）3（措施3）2（措施2）1（措施1）§4矩陣對策的混合策略甲的贏得甲的策略乙的策略第五十八頁，共六十五頁，2022年，8月28日解：易知此對策無純策略意義下的解。把A的每一個元素加上12，得到A′建立線性規(guī)劃模型如下：

Minx1+x2+x3Maxy1+y2+y31+20x2≥122y1+6y2+15y3≤16x1+17x2+22x3≥120y1+17y2+7y3≤115x1+7x2+20x3≥122y2+20y3≤1x1,x2,x3≥0y1,y2,y3≥0得到：x1=0.027,x2=0.020,x3=0.023；y1=0.0225,y2=0.0225,y3=0.025。V=14.29。x1′=0.3858,x2′=0.2858,x3′=0.3286；y1′=0.3215,y2′=0.3215,y3′=0.3572。即此對策的解為X*=(0.3858,0.2858,0.3286)T,Y*=(0.3215,0.3215,0.3572)T。VG=VG′-k=2.29?！?矩陣對策的混合策略第五十九頁，共六十五頁，2022年，8月28日

§5其他類型的對策論簡介

在對策論中可以根據(jù)不同方式對對策問題進行分類，通常分類的方式有（1）根據(jù)局中人的個數(shù)，分為二人對策和多人對策；（2）根據(jù)各局中人的贏得函數(shù)的代數(shù)和是否為零，可分為零和對策和非零和對策；（3）根據(jù)局中人是否合作，又可分為合作對策和非合作對策；（4）根據(jù)局中人的策略集中個數(shù)，又分為有限對策和無限對策（或連續(xù)對策）；（5）也可根據(jù)局中人掌握信息的情況及決策選擇是否和時間有關可分為完全信息靜態(tài)對策、完全信息動態(tài)對策、非完全信息靜態(tài)對策及非完全信息動態(tài)對策；也可以根據(jù)對策模型的數(shù)字特征又分為矩陣對策、連續(xù)對策、微分對策、陣地對策、凸對策、隨機對策。本節(jié)只對對策論中非合作對策的完全信息對策、多人非合作對策、非零和對策作一個簡單的敘述性介紹。第六十頁，共六十五頁，2022年，8月28日

§5其他類型的對策論簡介一、完全信息靜態(tài)對策該對策是指掌握了參與人的特征、戰(zhàn)略空間、支付函數(shù)等知識和