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

第11章二人有限零和對策第11章二人有限零和對策11.1基本概念11.2二人有限零和對策的純策略對策模型

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

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

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

等，但齊王的同等馬均強(qiáng)于田忌。孫臏給田忌出主意，用下----上，上----中，中----下，結(jié)果田忌勝出。②３.對策問題舉例①下棋、打牌、體育比賽等。4.對策的分類

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

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

R乙（si,dj)—乙的收益11.2二人有限零和對策的純策略對策模型

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

d1d2d3S110

-13Ａ＝S212

10-5S3685請你分析，理智情況下，甲、乙兩廠最可能出現(xiàn)什么策略，最大收益是多少？

d1d2d3S110

-13-1

A=S2

12

10-5

-5S3685*5*

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

對乙而言，先想最壞，再想最好．則d*=d3,V乙＝５=minmaxaij２、純策略對策的解定理1：例２

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

A=744*36376*易知，Ｇ在純策略意義下無解。

d1d2xis17

4x1s23

6

yjy1y2x2

當(dāng)甲取s1時(shí)，最少收益為:min{7x1y1,4x1y2}當(dāng)乙取d1時(shí)，最大損失為:max{7x1y1,3x2y1}則(x*,y*)－混合策略下的最優(yōu)解

E(x*,y*)－混合策略下的最優(yōu)值二人有限零和對策的混合策略對策模型：

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

－甲的期望收益－乙的期望損失二、混合策略對策的解１、定義：如果混合策略對策

G*={S*,D*;E}滿足：２、定理：設(shè)G*=(S*,D*;E)為混合對策，則例６：求解下列對策例７：求解矩陣

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

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

日美雙方的指揮官及參謀人員都進(jìn)行了冷靜與全面的謀劃。自然條件對于雙方來說是已知的。基本情況是：

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

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

局勢2：盟軍偵察機(jī)重點(diǎn)搜索北線，而日本艦隊(duì)走南線。由于發(fā)現(xiàn)晚，盡管盟軍轟炸機(jī)群在南線，但有效轟炸也只有兩天。

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

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

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

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

2策略：美日雙方各有兩個(gè)策略：南線、北線3支付與支付函數(shù)：日軍北線南線盟軍北線22

南線13=A

日軍北線南線盟軍北線-2-2

南線-1-3=B五、求解分析（1）局中人1（盟軍）希望獲得的支付（贏得轟炸天數(shù)）盡可能多，但同時(shí)，他們也深知：局中人2（日軍）必然想方設(shè)法使自己的付出（被轟炸天數(shù)）盡可能少。

（2）因此，盟軍參謀部或肯尼將軍在作選擇時(shí)，首先要考慮：選擇每個(gè)策略時(shí)至少能贏得多少，然后從中選取最有利的策略。具體來說：先對支付矩陣A各列求極?。ㄖ辽仝A得），然后，在對矩陣各列極小組成的集合中取極大（爭取最佳）。于是有：

maxmin{aij}＝max{2,1}＝2（3）對于日軍參謀部或山本五十六大將，因居于被動地位，故首先考慮在對方每個(gè)策略中最多最多損失多少，在此前提下爭取損失最小。具體來說：對同一支付矩陣A各行求極大（最多損失），然后，對矩陣各行極大組成的集合中取極?。幦∽罴眩Ｓ谑怯校?/p>

minmax{aij}＝min{2,3}＝2

上述求解思想可概括為：“從最壞處著想，去爭取最好的結(jié)果”。這是理性思考的表現(xiàn)。此例中，恰有：

maxmin{aij}＝minmax{aij}＝2

這是實(shí)際對局的結(jié)果。［案例3］中美貿(mào)易問題——對策問題一、相關(guān)背景資料

1996年5月15日，美國政府借口中國對知識產(chǎn)權(quán)保護(hù)不力，單方面宣布：對中國出口到