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

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

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

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

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

矩陣對(duì)策aij為局中人甲在局勢(shì)下的贏得第九頁(yè)，共六十五頁(yè)，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“齊王賽馬”是一個(gè)矩陣策略。第十頁(yè)，共六十五頁(yè)，2022年，8月28日§2

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

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

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

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

。但是Ⅱ推測(cè)Ⅰ會(huì)有此心理，從而選β3來(lái)對(duì)付，使得Ⅰ非但得不到6分，反而要失去3分。當(dāng)然Ⅰ也會(huì)料到Ⅱ會(huì)有此心理，從而改選α3

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

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

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

A=[aij]m×n

，若有則局勢(shì)

(αi*

，βj*)

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

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

對(duì)于例4，G的解(鞍點(diǎn))為(α1,β2)，α1

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

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

設(shè)G=｛S1,S2

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

ij]m×n

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

，βj*)

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

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

故

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

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

時(shí)達(dá)到最大，即

在j=j*

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

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

設(shè)有矩陣對(duì)策G={S1,S2;A},其中:

A=[aij]m×n

,概率向量當(dāng)矩陣對(duì)策G在純策略意義下無(wú)解時(shí)，由于不存在鞍點(diǎn)，即不存在平衡局勢(shì)，各局中人的決策總有一定的風(fēng)險(xiǎn)。因此，無(wú)理由只取某個(gè)策略而舍棄其余策略，也就是局中人應(yīng)考慮，按照預(yù)先確定的一組概率來(lái)選取其所有可能采用的策略?！?矩陣對(duì)策的混合策略分別稱X,Y為局中人Ⅰ和Ⅱ的“混合策略”。向量組

(X,Y)

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

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

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

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

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

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

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

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

當(dāng)甲選擇α4時(shí)，如果乙選擇β1，甲放棄時(shí)，贏得－5；

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

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

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

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

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

(X*,Y*)

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

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

矩陣對(duì)策的基本定理先給出兩個(gè)記號(hào):當(dāng)局中人Ⅰ取純策略αi

時(shí)的贏得值為

(矩陣A第i行乘以Y)

當(dāng)局中人Ⅱ取純策略βj

時(shí)的贏得值為

(X乘以矩陣A第j列)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

時(shí)的贏得值E(i,Y*

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

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

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

1優(yōu)超原則法

設(shè)有矩陣對(duì)策G={S1,S2;A},其中:

A=[aij]m×n

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

例9

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

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

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

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

：v

=-8x+9L2

：v=7xL3

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

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

y1*

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

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

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

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

：v

=6y－5L2

：v=－8y＋4L3

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

的圖形就是折線CDEF。因?yàn)镋點(diǎn)是折線的最低點(diǎn)，所以

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

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

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

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

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

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

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

問題()和()是互為對(duì)偶的線性規(guī)劃，可用單純形或?qū)ε紗渭冃畏ㄇ蠼猓儆勺儞Q(12)和(13)，即可得到原問題的解和對(duì)策值A(chǔ)第i行列乘以第五十頁(yè)，共六十五頁(yè)，2022年，8月28日例12

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

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

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

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

建立對(duì)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，此時(shí)V′G=V′－2=1。第五十三頁(yè)，共六十五頁(yè)，2022年，8月28日

同樣可以建立對(duì)策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，此時(shí)VG=VG′-k=1?！?矩陣對(duì)策的混合策略第五十四頁(yè)，共六十五頁(yè)，2022年，8月28日

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

可知無(wú)純策略意義的解，下面求其在混合策略下的解。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矩陣對(duì)策的混合策略第五十六頁(yè)，共六十五頁(yè)，2022年，8月28日得到x1′=0.25,x2′=0.50,x3′=0.25；y1′=0.25,y2′=0.50,y3′=0.25。即此對(duì)策的解為X*=(0.25,0.50,0.25)T，Y*=(0.25,0.50,0.25)T。VG=VG′-k=0?！?矩陣對(duì)策的混合策略第五十七頁(yè)，共六十五頁(yè)，2022年，8月28日例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)總份額一定，由于各自采取的措施不同，通過預(yù)測(cè)今后兩個(gè)企業(yè)的市場(chǎng)占有份額變動(dòng)情況如下表，試求出這兩個(gè)企業(yè)各自的最優(yōu)策略。3-58-6510108-121（措施1）2（措施2）3（措施3）3（措施3）2（措施2）1（措施1）§4矩陣對(duì)策的混合策略甲的贏得甲的策略乙的策略第五十八頁(yè)，共六十五頁(yè)，2022年，8月28日解：易知此對(duì)策無(wú)純策略意義下的解。把A的每一個(gè)元素加上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。即此對(duì)策的解為X*=(0.3858,0.2858,0.3286)T,Y*=(0.3215,0.3215,0.3572)T。VG=VG′-k=2.29?！?矩陣對(duì)策的混合策略第五十九頁(yè)，共六十五頁(yè)，2022年，8月28日

§5其他類型的對(duì)策論簡(jiǎn)介

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

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