運(yùn)籌學(xué)第十一章二人有限零和對(duì)策

運(yùn)籌學(xué)第十一章二人有限零和對(duì)策第一頁(yè)，共四十頁(yè)，編輯于2023年，星期二第11章二人有限零和對(duì)策11.1基本概念11.2二人有限零和對(duì)策的純策略對(duì)策模型

11.3二人有限零和對(duì)策的混合策略對(duì)策模型第二頁(yè)，共四十頁(yè)，編輯于2023年，星期二11.1基本概念一、對(duì)策現(xiàn)象與對(duì)策論對(duì)策和對(duì)策論對(duì)策：就是競(jìng)爭(zhēng)或斗爭(zhēng)中的決策．如：政治方面的階級(jí)斗爭(zhēng)，經(jīng)濟(jì)方面的勞資糾紛，市場(chǎng)競(jìng)爭(zhēng)，原料競(jìng)爭(zhēng)，投標(biāo)競(jìng)爭(zhēng)，外貿(mào)談判，軍備競(jìng)賽，各種體育比賽等．對(duì)策論：把各式各樣的沖突現(xiàn)象抽象成一種數(shù)學(xué)模型，然后給出分析這些問(wèn)題的方法和解。第三頁(yè)，共四十頁(yè)，編輯于2023年，星期二對(duì)策論－數(shù)學(xué)角度博弈論－經(jīng)濟(jì)角度２.對(duì)策論的歷史春秋戰(zhàn)國(guó)時(shí)期－孫子兵法殷代－圍棋19世紀(jì)－西方人把對(duì)策論應(yīng)用于經(jīng)濟(jì)領(lǐng)域第四頁(yè)，共四十頁(yè)，編輯于2023年，星期二40年代中期－對(duì)策論作為一種數(shù)學(xué)理論1944年，美籍匈牙利數(shù)學(xué)家－紐曼（Neuman)經(jīng)濟(jì)學(xué)家－曼格斯特（Morgenstern)

《對(duì)策論及其在經(jīng)濟(jì)管理中的應(yīng)用》在40年代發(fā)展迅速，緣于二戰(zhàn)中軍事的需要，二戰(zhàn)后又應(yīng)用于其他領(lǐng)域。第五頁(yè)，共四十頁(yè)，編輯于2023年，星期二50年代是對(duì)策論發(fā)展的鼎盛時(shí)期，納什和夏普利等提出了討價(jià)還價(jià)模型和合作對(duì)策的“核”的概念。60年代，澤爾騰（1965）引入動(dòng)態(tài)分析，提出“精練納什均衡”概念。海薩尼（1967-1968）則把不完全信息引入對(duì)策論的研究。第六頁(yè)，共四十頁(yè)，編輯于2023年，星期二1-1010-1-110A石頭剪子石頭剪子布布贏B猜手:小孩A與B猜手,若規(guī)定贏得1分，平得0分，輸?shù)?1分，則A的贏得可用右表來(lái)表示。

③齊王賽馬：齊王與大將田忌賽馬，各自的馬都分為三

等，但齊王的同等馬均強(qiáng)于田忌。孫臏給田忌出主意，用下----上，上----中，中----下，結(jié)果田忌勝出。②３.對(duì)策問(wèn)題舉例①下棋、打牌、體育比賽等。第七頁(yè)，共四十頁(yè)，編輯于2023年，星期二4.對(duì)策的分類(lèi)

動(dòng)態(tài)：是連續(xù)時(shí)間的動(dòng)態(tài)對(duì)策，因此從上一狀態(tài)到另一狀態(tài)的轉(zhuǎn)移用微分描述對(duì)策零和：得＋失＝０二人：靜態(tài)：非零和：得＋失≠０零和結(jié)盟：多人在一起交換策略非零和多人零和不結(jié)盟：多人在一起交換策略非零和

第八頁(yè)，共四十頁(yè)，編輯于2023年，星期二二.對(duì)策問(wèn)題的組成（幾個(gè)基本要素）1.局中人：一局對(duì)策的參加者。2.策略：局中人在一局對(duì)策中對(duì)付對(duì)手的一個(gè)行動(dòng)方案。策略全體稱(chēng)為策論集。S={s1,s2,……,sm}—局中人甲的策略集D={d1,d2,……,dn}—局中人乙的策略集3.局勢(shì)：在一局對(duì)策中，每個(gè)局中人都選定一個(gè)策略后的各策略的組合。表示為（Si,Dj).4.得失值（贏得函數(shù)）：局中人選定某策略后相應(yīng)的收益值。表示為R甲（si,dj)—甲的收益

R乙（si,dj)—乙的收益第九頁(yè)，共四十頁(yè)，編輯于2023年，星期二11.2二人有限零和對(duì)策的純策略對(duì)策模型

二人：指參加對(duì)策的局中人有２個(gè)。有限：指每個(gè)局中人的策略集為有限集。零和：指在任一局勢(shì)下，雙方收益之和為０。第十頁(yè)，共四十頁(yè)，編輯于2023年，星期二M一、純策略對(duì)策模型－矩陣對(duì)策第十一頁(yè)，共四十頁(yè)，編輯于2023年，星期二二、純策略對(duì)策的解1、純策略分析例１：今有甲、乙兩廠生產(chǎn)同一種產(chǎn)品，它們都想通過(guò)內(nèi)部改革挖掘，獲得更多得市場(chǎng)份額。已知兩廠分別都有三個(gè)策略措施。據(jù)預(yù)測(cè)，當(dāng)雙方采取不同的策略措施后兩廠的市場(chǎng)占有份額變動(dòng)情況如下所示。

第十二頁(yè)，共四十頁(yè)，編輯于2023年，星期二

d1d2d3S110

-13Ａ＝S21210-5S3685請(qǐng)你分析，理智情況下，甲、乙兩廠最可能出現(xiàn)什么策略，最大收益是多少？第十三頁(yè)，共四十頁(yè)，編輯于2023年，星期二

d1d2d3S110-13-1

A=S2

1210-5

-5S3685*5*

12105*(s3,d3)即為雙方的最優(yōu)策略，此時(shí)甲得5，乙失5。有唯一最優(yōu)策略。對(duì)甲而言，先想最壞，再想最好．則s*=s3,V甲＝５=maxminaij

對(duì)乙而言，先想最壞，再想最好．則d*=d3,V乙＝５=minmaxaij第十四頁(yè)，共四十頁(yè)，編輯于2023年，星期二２、純策略對(duì)策的解第十五頁(yè)，共四十頁(yè)，編輯于2023年，星期二定理1：第十六頁(yè)，共四十頁(yè)，編輯于2023年，星期二第十七頁(yè)，共四十頁(yè)，編輯于2023年，星期二例２

只有一個(gè)鞍點(diǎn)例３-2-3-4-23-68387第十八頁(yè)，共四十頁(yè)，編輯于2023年，星期二例４第十九頁(yè)，共四十頁(yè)，編輯于2023年，星期二(3)優(yōu)超原理第二十頁(yè)，共四十頁(yè)，編輯于2023年，星期二例5：用優(yōu)超原理求解下列對(duì)策s1s2s3s4d1d2d3d4d1d2d3d4s1s2s3s4s3s4d1d2s1s2s3s4d1d2s3s4d1s3d1故鞍點(diǎn)為（s3,d1)對(duì)策值為ＶＧ＊＝２第二十一頁(yè)，共四十頁(yè)，編輯于2023年，星期二練習(xí)先用優(yōu)超原理簡(jiǎn)化矩陣，再求解。第二十二頁(yè)，共四十頁(yè)，編輯于2023年，星期二11.3二人有限零和對(duì)策的混合策略對(duì)策模型一、基本概念例：已知對(duì)策Ｇ＝｛Ｓ，Ｄ；Ａ｝

A=744*36376*易知，Ｇ在純策略意義下無(wú)解。第二十三頁(yè)，共四十頁(yè)，編輯于2023年，星期二

d1d2xis17

4x1s23

6yjy1y2x2

第二十四頁(yè)，共四十頁(yè)，編輯于2023年，星期二當(dāng)甲取s1時(shí)，最少收益為:min{7x1y1,4x1y2}當(dāng)乙取d1時(shí)，最大損失為:max{7x1y1,3x2y1}則(x*,y*)－混合策略下的最優(yōu)解

E(x*,y*)－混合策略下的最優(yōu)值第二十五頁(yè)，共四十頁(yè)，編輯于2023年，星期二二人有限零和對(duì)策的混合策略對(duì)策模型：

G*={S*,D*;E}

其中:S*={X=(x1,x2,…,xm)T

∑xi=1,xi≥0}

－甲的混合策略集D*={y=(y1,y2,…,yn)T∑yj=1,yj≥0}

－乙的混合策略集E=E(X,Y)=∑∑aijxiyj

－甲的期望收益－乙的期望損失第二十六頁(yè)，共四十頁(yè)，編輯于2023年，星期二二、混合策略對(duì)策的解１、定義：如果混合策略對(duì)策

G*={S*,D*;E}滿(mǎn)足：２、定理：設(shè)G*=(S*,D*;E)為混合對(duì)策，則第二十七頁(yè)，共四十頁(yè)，編輯于2023年，星期二例６：求解下列對(duì)策第二十八頁(yè)，共四十頁(yè)，編輯于2023年，星期二例７：求解矩陣

d1d2d3

S110

-13

x1A=S21267x2S3685x3y1y2y3y(1)=0y(2)=0.50000y(3)=0.50000x(1)=0x(2)=0.75000x(3)=0.25000VG*=6.50000

第二十九頁(yè)，共四十頁(yè)，編輯于2023年，星期二［案例１］企業(yè)建廠決策問(wèn)題某企業(yè)生產(chǎn)甲、乙兩種家用電器．據(jù)預(yù)測(cè)，若在某地建新廠則要投資100萬(wàn)元，每年可凈收益14萬(wàn)元．若將此款存入銀行，則有２萬(wàn)元利息．此外，還有以下信息可供決策者參考：（１）在某地建新廠后，原廠房若不能售出，則要維修，每年將花費(fèi)3.2萬(wàn)元．因此，在某地建新廠后的凈收益只能是10.8萬(wàn)元．（２）據(jù)預(yù)測(cè)，今后１０年中，乙產(chǎn)品的需求量將下降５％（與進(jìn)口無(wú)關(guān)）．在此情況下，未被吸收的固定管理費(fèi)用為2.３萬(wàn)元，因此，建新第三十頁(yè)，共四十頁(yè)，編輯于2023年，星期二廠的凈收益只能是11.7萬(wàn)元．（３）在某地建新廠后，可增加銷(xiāo)售額，經(jīng)計(jì)算能多得2.4萬(wàn)元的收益，因此，凈收益為16.4萬(wàn)元．反之，若不建新廠將會(huì)損失2.4萬(wàn)元，扣除利息２萬(wàn)元，凈損失為0.４萬(wàn)元．（４）競(jìng)爭(zhēng)者建廠．若該企業(yè)不在此地建廠，則競(jìng)爭(zhēng)者將在該地建廠，于是該企業(yè)在此地的銷(xiāo)售額將被競(jìng)爭(zhēng)者所占有，將損失3.６萬(wàn)元，扣除利息２萬(wàn)元，凈損失1.６萬(wàn)元．（５）進(jìn)口影響．進(jìn)口產(chǎn)品中對(duì)甲產(chǎn)品影響不大，但對(duì)乙產(chǎn)品銷(xiāo)路的威脅極大．若進(jìn)口產(chǎn)品成功，將會(huì)占去８０％的市場(chǎng)．此時(shí)在該地建新廠不但無(wú)第三十一頁(yè)，共四十頁(yè)，編輯于2023年，星期二收益，反而損失4.5萬(wàn)元．根據(jù)以上信息，該企業(yè)的決策者應(yīng)如何決策？解：原始預(yù)算（d1)原廠房未出售（d2)需求量下降（d3)增加銷(xiāo)售（d4)競(jìng)爭(zhēng)者建廠（d5)進(jìn)口影響（d6)建廠（s1)不建廠(s2)１４２10.8211.7216.4-0.414-1.6-4.52第三十二頁(yè)，共四十頁(yè)，編輯于2023年，星期二X=(0.16,0.84)TY=(0,0,0,0,0.29,0.71)TVG=0.94第三十三頁(yè)，共四十頁(yè)，編輯于2023年，星期二［案例2］俾斯麥海的海空對(duì)抗——對(duì)策問(wèn)題一、相關(guān)背景資料

1943年2月，第二次世界大戰(zhàn)中的日本，在太平洋戰(zhàn)區(qū)已處于明顯的劣勢(shì)。為扭轉(zhuǎn)戰(zhàn)局，日軍統(tǒng)帥山本五十六大將統(tǒng)率下的一支艦隊(duì)策劃了一次軍事行動(dòng)：由集結(jié)地——南太平洋新不列顛群島的拉包爾出發(fā)，穿過(guò)俾斯麥海，開(kāi)往新幾內(nèi)亞的萊城，支援困守在那里的日軍。山本五十六心中非常明白，在日本艦隊(duì)穿過(guò)俾斯麥海的3天航程中，不可能躲開(kāi)盟軍的襲擊，他要謀劃的是盡可能減少損失。當(dāng)盟軍獲悉此情報(bào)以后，盟軍統(tǒng)帥麥克阿瑟即命令他麾下的太平洋戰(zhàn)區(qū)空軍司令肯尼將軍組織空中打擊。

第三十四頁(yè)，共四十頁(yè)，編輯于2023年，星期二日美雙方的指揮官及參謀人員都進(jìn)行了冷靜與全面的謀劃。自然條件對(duì)于雙方來(lái)說(shuō)是已知的?；厩闆r是：

（1）從拉包爾到萊城的海上航線有南線和北線兩條，通過(guò)時(shí)間均為3天。（2）氣象預(yù)報(bào)表明，未來(lái)3天中，北線陰雨，能見(jiàn)度差；而南線則天氣晴好，能見(jiàn)度佳。二、局勢(shì)估計(jì)

局勢(shì)1：盟軍偵察機(jī)重點(diǎn)搜索北線，日本艦隊(duì)也恰好走北線。由于氣候惡劣，能見(jiàn)度低以及轟炸機(jī)群在南線，因而盟軍只能實(shí)施兩天有效的轟炸。

局勢(shì)2：盟軍偵察機(jī)重點(diǎn)搜索北線，而日本艦隊(duì)走南線。由于發(fā)現(xiàn)晚，盡管盟軍轟炸機(jī)群在南第三十五頁(yè)，共四十頁(yè)，編輯于2023年，星期二線，但有效轟炸也只有兩天。

局勢(shì)3：盟軍偵察機(jī)重點(diǎn)搜索南線，而日本艦隊(duì)走北線。由于發(fā)現(xiàn)晚，盟軍轟炸機(jī)群在南線，以及北線天氣惡劣，故有效轟炸只能實(shí)施1天。

局勢(shì)4：盟軍偵察機(jī)重點(diǎn)搜索南線，日本艦隊(duì)也恰好走南線。此時(shí)，日軍艦隊(duì)被迅速發(fā)現(xiàn)，盟軍轟炸機(jī)群所需航程很短，加之天氣晴好，這將使盟軍空軍在3天中皆可實(shí)施有效轟炸。三、歷史情況局勢(shì)1成為事實(shí)。即肯尼將軍命令盟軍偵察機(jī)重點(diǎn)搜索北線；而山本五十六命令日本艦隊(duì)取道北線航行。

第三十六頁(yè)，共四十頁(yè)，編輯于2023年，星期二盟軍飛機(jī)在1天后發(fā)現(xiàn)日本艦隊(duì)，基地在南線的盟軍轟炸機(jī)群遠(yuǎn)程飛行，在惡劣天氣中，實(shí)施了2天有效地轟炸，重創(chuàng)了日本艦隊(duì)，但未能全殲。四、數(shù)學(xué)模型

1局中人：美日雙方?jīng)Q策者

2策略：美日雙方各有兩個(gè)策略：南線、北線第三十七頁(yè)，共四十頁(yè)，編輯于2023年，星期二3支付與支付函數(shù)：日軍北線南線盟軍北線22

南線13=A

日軍北線