運籌學（第5版）教學課件第12章對策論

第十二章對策論OperationalResearch(OR)對策論引言矩陣對策的基本理論矩陣對策的解法其他類型對策簡介沖突分析簡介對策現(xiàn)象和對策論一、對策現(xiàn)象和對策論對策論(gametheory)亦稱博弈論或競賽論，是研究具有對抗或競爭性質(zhì)現(xiàn)象的數(shù)學理論和方法。它既是現(xiàn)代數(shù)學的一個新分支，也是運籌學的一個重要學科。對策論發(fā)展的歷史并不長，但由于它所研究的現(xiàn)象與人們的政治、經(jīng)濟、軍事活動乃至一般日常生活等有著密切聯(lián)系，并且處理問題的方法又有明顯特色，所以日益引起廣泛的重視。齊王賽馬二、對策現(xiàn)象的三要素對策現(xiàn)象的三要素1.局中人(players)：參與對抗的各方；2.策略(strategies)：局中人選擇對付其它局中人的行動方案稱為策略；3.贏得函數(shù)(支付函數(shù))(payofffunction)：各局中人各自使用一個對策就形成一個局勢，一個局勢決定了個局眾人的對策結果（量化）?！褒R王賽馬”齊王在各局勢中的對策結果（單位：千金）對策問題舉例及對策的分類三、對策問題舉例及對策的分類例1市場購買力爭奪問題據(jù)預測，某鄉(xiāng)鎮(zhèn)下一年的飲食品購買力將有4000萬元。鄉(xiāng)鎮(zhèn)企業(yè)和中心城市企業(yè)飲食品的生產(chǎn)情況是：鄉(xiāng)鎮(zhèn)企業(yè)有特色飲食品和低檔飲食品兩類，中心城市企業(yè)有高檔飲食品和低檔飲食品兩類產(chǎn)品。它們爭奪這一部分購買力的結局見下表(單位：萬元)。問題是鄉(xiāng)鎮(zhèn)企業(yè)和中心城市企業(yè)應如何選擇對自己最有利的產(chǎn)品策略。鄉(xiāng)鎮(zhèn)策略中心城市企業(yè)的策略出售高檔飲食品出售低檔飲食品出售特色飲食品20003000出售一般飲食品10003000對策問題舉例及對策的分類例2銷售競爭問題假定企業(yè)Ⅰ,Ⅱ均能向市場出售某一產(chǎn)品，不妨假定他們可于時間區(qū)間［0,1］內(nèi)任一時點出售。設企業(yè)Ⅰ在時刻x出售，企業(yè)Ⅱ在時刻y出售，則企業(yè)Ⅰ的收益(贏得)函數(shù)為：若x<y若x=y若x>y問這兩個企業(yè)各選擇什么時機出售對自己最有利?在這個例子中，企業(yè)Ⅰ,Ⅱ可選擇的策略均有無窮多個。對策問題舉例及對策的分類例3費用分攤問題假設沿某一河流有相鄰的3個城市A，B，C，各城市可單獨建立水廠，也可合作興建一個大水廠。經(jīng)估算，合建一個大水廠，加上敷設管道的費用，要比單獨建3個小水廠的總費用少。但合建大廠的方案能否實施，顯然要看總的建設費用分攤得是否合理。如果某個城市分攤到的費用比它單獨建設水廠的費用還多的話，它顯然不會接受合作的方案。問題是應如何合理地分攤費用，使合作興建大水廠的方案得以實現(xiàn)?對策問題舉例及對策的分類例4拍賣問題最常見的一種拍賣形式是先由拍賣商把拍賣品描述一番，然后提出第一個報價。接下來由買者報價，每一次報價都要比前一次高，最后誰出的價最高，拍賣品即歸誰所有。假設有n個買主給出的報價分別為p1,…,pn,且不妨設pn>pn-1>…>p1,則買主n只要報價略高于pn-1，就能買到拍賣品，即拍賣品實際上是在次高價格上賣出的?，F(xiàn)在的問題是，各買主之間可能知道他人的估價，也可能不知道他人的估價，每人應如何報價對自己能以較低的價格得到拍賣品最為有利?最后的結果又會怎樣?對策問題舉例及對策的分類例5囚犯難題設有兩個嫌疑犯因涉嫌某一大案被警官拘留，警官分別對兩人進行審訊。根據(jù)法律，如果兩個人都承認此案是他們干的，則每人各判刑7年；如果兩人都不承認，則由于證據(jù)不足，兩人各判刑1年；如果只有一人承認，則承認者予以寬大釋放，而不承認者將判刑9年。因此，對兩個囚犯來說，面臨著一個在“承認”和“不承認”這兩個策略間進行選擇的難題。對策問題舉例及對策的分類對策論中將問題根據(jù)不同方式進行分類:(1)根據(jù)局中人的個數(shù)，分為二人對策和多人對策；(2)根據(jù)各局中人的贏得函數(shù)的代數(shù)和是否為零，分為零和對策與非零和對策；(3)根據(jù)各局中人間是否允許合作，分為合作對策和非合作對策；(4)根據(jù)局中人的策略集中的策略個數(shù)，分為有限對策和無限對策。此外，還有許多其他的分類方式，例如根據(jù)策略的選擇是否與時間有關，可分為靜態(tài)對策和動態(tài)對策；根據(jù)對策模型的數(shù)學特征，可分為矩陣對策、連續(xù)對策、微分對策、陣地對策、凸對策、隨機對策等。對策論引言矩陣對策的基本理論矩陣對策的解法其他類型對策簡介沖突分析簡介矩陣對策的基本理論二人有限零和對策：（又稱矩陣策略）局中人為2；每局中人的策略集中策略權目有限；在任一局勢下，兩個局中人的贏得之和總等于零，即一個局中人的所得值恰好等于另一局中人的所失值，雙方的利益是完全對抗的。記矩陣對策為:

G={S1,S2；A}Ⅰ的策略集Ⅰ的贏得矩陣Ⅱ的策略集“齊王賽馬”即是一個矩陣策略。矩陣對策的純策略矩陣對策的純策略例6設有一矩陣對策G={S1,S2;A}，其中Ⅰ：采取

1至少得益-8

22

3-10

4-3Ⅱ：采取1最多損失9

22

36取大則取2maxminaij=2

ij取小則取2minmaxaij=2

j

i平衡局勢(α2,β2)，這個局勢就是雙方均可接受的，且對雙方來說都是一個最穩(wěn)妥的結果。因此，α2和β2應分別是局中人Ⅰ和Ⅱ的最優(yōu)純策略。矩陣對策的純策略設G={S1,S2;A}為一矩陣對策，其中S1={α1,…,αm}，S2={β1,…,βn}，A=(aij)m×n。若成立，記其值為VG，則稱VG為對策的值，稱使其成立的純局勢(αi*,βj*)為G在純策略意義下的解(或平衡局勢)，稱αi*和βj*分別為局中人Ⅰ和Ⅱ的最優(yōu)純策略。定義1矩陣對策的純策略定理1中式子的對策意義是：一個平衡局勢(αi*,βj*)應具有這樣的性質(zhì)：當局中人Ⅰ選擇了純策略αi*后，局中人Ⅱ為了使其所失最少，只能選擇純策略βj*，否則就可能失的更多；反之，當局中人Ⅱ選擇了純策略βj*后，局中人Ⅰ為了得到最大的贏得也只能選擇純策略αi*，否則就會贏的更少，雙方的競爭在局勢(αi*,βj*)下達到了一個平衡狀態(tài)。矩陣對策G={S1,S2;A}在純策略意義下有解的充要條件是：存在純局勢(αi*,βj*)，使得對任意i和j，有aij*≤ai*j*≤ai*j定理1矩陣對策的純策略例7

設有矩陣對策G={S1,S2;A}，其中解有i*=1,3j*=2,4故(α1,β2)，(α1,β4)，(α3,β2)，(α3,β4)都是對策的解，且VG=8矩陣對策的純策略一般對策的解可以是不惟一的，當解不惟一時，解之間的關系具有下面兩條性質(zhì)：若(αi1,βj1)和(αi2,βj2)是對策G的兩個解，則ai1j1=ai2j2若(αi1,βj1)和(αi2,βj2)是對策G的兩個解，則(αi1,βj2)和(αi2,βj1)也是對策G的解。矩陣對策的值是惟一的，即當一個局中人選擇了最優(yōu)純策略后，他的贏得值不依賴于對方的純策略。性質(zhì)1(無差別性)性質(zhì)2(可交換性)矩陣對策的混合策略設矩陣對策G={S1,S2,A}當maxminaijminmaxaij時，

ijji不存在最優(yōu)純策略求解混合策略。二、矩陣對策的混合策略矩陣對策的混合策略設有矩陣對策G={S1,S2;A}，其中記則分別稱S1*和S2*為局中人Ⅰ和Ⅱ的混合策略集(或策略集)；對x∈S1*和y∈S2*，稱x和y為混合策略(或策略)，(x,y)為混合局勢(或局勢)。局中人Ⅰ的贏得函數(shù)記成稱G*={S1*,S2*;E}為對策G的混合擴充。定義2矩陣對策的混合策略設G*={S1*,S2*;E}是矩陣對策G={S1,S2;A}的混合擴充。如果記其值為VG，則稱VG為對策G的值，稱使上式成立的混合局勢(x*,y*)為G在混合策略意義下的解(或平衡局勢)，稱x*和y*分別為局中人Ⅰ和Ⅱ的最優(yōu)混合策略。矩陣對策G在混合策略意義下有解的充要條件是：存在x*∈S1*,y*∈S2*，使得對任意x∈S1*和y∈S2*，有E(x,y*)≤E(x*,y*)≤E(x*,y)定義3定理2矩陣對策的混合策略例8

考慮矩陣對策G={S1,S2;A}，其中已知G在純策略意義下無解，故設x=(x1,x2)和y=(y1,y2)分別為局中人Ⅰ和Ⅱ的混合策略，則局中人Ⅰ的贏得的期望是矩陣對策的混合策略取x*=(1/4,3/4)，y*=(1/2,1/2)，則E(x*,y*)=9/2，E(x*,y)=E(x,y*)=9/2，即有E(x,y*)≤E(x*,y*)≤E(x*,y)

故x*=(1/4,3/4)和y*=(1/2,1/2)分別為局中人Ⅰ和Ⅱ的最優(yōu)策略，對策的值(局中人Ⅰ的贏得的期望值)為VG=9/2。矩陣對策的基本定理三、矩陣對策的基本定理設x*∈S1*,y*∈S2*,則(x*,y*)為對策G的解的充要條件是：對任意i=1,…,m和j=1,…,n，有E(i,y*)≤E(x*,y*)≤E(x*,j)設x*∈S1*,y∈S2*，則(x*,y*)為G的解的充要條件是：存在數(shù)v,使得x*和y*分別是下列不等式組的解，且v=VG。j=1,2,...,ni=1,2,...,mi=1,2,...,mj=1,2,...,n定理3定理4對任一矩陣對策G={S1,S2;A}，一定存在混合策略意義下的解。矩陣對策的基本定理設(x*,y*)是矩陣對策G的解，v=VG，則(1)若xi*>0,則(2)若yj*>0,則(3)若,則xi*=0(4)若,則y*j=0定理5定理6矩陣對策的基本定理設有兩個矩陣對策G1={S1,S2,A1}，G2={S1,S2,A2},其中A1=(aij),A2=(aij+L)，L為一任意常數(shù)，則(1)VG2=VG1+L(2)T(G1)=T(G2)設有兩個矩陣對策G1={S1,S2,A}，G2={S1,S2,αA},其中α>0，為一任意常數(shù)，則(1)VG2=αVG1(2)T(G1)=T(G2)設G1={S1,S2,A}為一矩陣對策，且A=-AT為斜對稱矩陣(亦稱這種對策為對稱對策)，則(1)VG=0(2)T1(G)=T2(G)其中，T1(G)和T2(G)分別為局中人Ⅰ和Ⅱ的最優(yōu)策略集。定理7定理8定理9對策論引言矩陣對策的基本理論矩陣對策的解法其他類型對策簡介沖突分析簡介矩陣對策的解法一、圖解法例9

用圖解法求解矩陣對策G={S1,S2,A}，其中解設局中人Ⅰ的混合策略為(x,1-x)T，x∈［0,1］。01x257ⅠⅠⅡⅡβ1β3β2ABB1B2B3圖解法解得x=3/11,VG=49/11。所以，局中人Ⅰ的最優(yōu)策略為x*=(3/11,8/11)T下面求局中人Ⅱ的最優(yōu)策略：局中人Ⅱ的最優(yōu)混合策略只由β2和β3組成設y*=(y1*,y2*,y3*)T為局中人Ⅱ的最優(yōu)混合策略，則由E(x*,1)=2×3/11+7×8/11=62/11>49/11=VG，根據(jù)定理6，必有y1*=0。又因x1*=3/11>0,x2*=8/11>0，再根據(jù)定理6，可由求得y2*=9/11,y3*=2/11。所以，局中人Ⅱ的最優(yōu)混合策略為y*=[0,9/11,2/11]T方程組法二、方程組法例10

求解矩陣對策G={S1,S2;A}，其中A為β1β2β3β4β5方程組法β1β2β3β4β5α4嚴格優(yōu)于α1，所以劃去α1同理，劃去第二行，第三列，第四列和第五列剩下的矩陣中第一行優(yōu)于第三行，所以劃去第三行方程組法易知A1沒有鞍點，由定理12.6求出方程組和的非負解于是，以矩陣A為贏得矩陣的對策的一個解就是：線性規(guī)劃法例11

利用線性規(guī)劃方法求解下述矩陣對策，其贏得矩陣為：三、線性規(guī)劃法解由定理5可知，可將其化成兩個互為對偶的線性規(guī)劃問題：線性規(guī)劃法解上述線性規(guī)劃，得因此對策問題的解為：對策論引言矩陣對策的基本理論矩陣對策的解法其他類型對策簡介沖突分析簡介二人無限零和對策一、二人無限零和對策表示方法：G={S1,S2;H}其中S1和S2中至少有一個是無限集合，H為局中人Ⅰ的贏得函數(shù)。局中人Ⅰ的至少贏得：局中人Ⅱ的至多所失：二人無限零和對策設G={S1,S2;H}為二人無限零和對策。若存在αi*∈S1,βj*∈S2,使得記其值為VG，則稱VG為對策G的值，稱使該式成立的(αi*,βj*)為G在純策略意義下的解，αi*,βj*分別稱為局中人Ⅰ和Ⅱ的最優(yōu)純策略。(αi*,βj*)為G={S1,S2;H}在純策略意義下的解的充要條件是：對任意αi∈S1,βj∈S2,有H(αi,βj*)≤H(αi*,βj*)≤H(αi*,βj)定義4定理10二人無限零和對策例12

設局中人Ⅰ、Ⅱ互相獨立地從［0,1］中分別選擇一個實數(shù)x和y，局中人Ⅰ的贏得函數(shù)為H(x,y)=2x2-y2。對策中，局中人Ⅰ希望H越大越好，局中人Ⅱ則希望H越小越好。圖中給出了H(x,y)的等值線，通過對該圖的分析，不難看出雙方競爭的平衡局勢為(1，1)，即αi*=1,βj*=1分別為局中人Ⅰ和Ⅱ的最優(yōu)純策略，VG=1。可以驗證，對(αi*,βj*)=(1,1)，定理10的等式是成立的。二人無限零和對策無限對策的混合策略：局中人Ⅰ和Ⅱ的混合策略X和Y分別為策略集S1和S2上的概率分布(或分布函數(shù))，混合策略集記為和。若用x,y表示純策略，F(xiàn)X(x),FY(y)表示混合策略X，Y的分布，則局中人Ⅰ的贏得函數(shù)可以有以下4種形式：H(x,y)以及二人無限零和對策如果有則稱VG為對策G的值，稱使上式成立的(X*,Y*)為對策G的解，X*和Y*分別為局中人Ⅰ和Ⅱ的最優(yōu)策略。(X*,Y*)為對策G={S1,S2;H}的解的充要條件是：對任意X∈,Y∈，有H(X,Y*)≤H(X*,Y*)≤H(X*,Y)當S1=S2=［0,1］，且H(x,y)為連續(xù)函數(shù)時，稱這樣的對策為連續(xù)對策。定義5定理11二人無限零和對策對任何連續(xù)對策，一定有v1=v2。例13(生產(chǎn)能力分配問題)某公司下屬甲、乙兩個工廠，分別位于A，B兩市。設兩廠總生產(chǎn)能力為1個單位，兩市對工廠產(chǎn)品的總需求也是1個單位。如果A市的需求量為x,則B市的需求量為1-x，這時只要安排A廠的生產(chǎn)能力為x，就能使供需平衡。但現(xiàn)在不知道A市的確切需求量x是多少，如果安排A廠的生產(chǎn)能力為y，則將產(chǎn)生供需上的不平衡。不平衡的程度可用數(shù)值表示為：公司的目標是選擇y，使得達到極小。定理12二人無限零和對策如果以市場需求為一方，公司為另一方，則以上問題可轉化為一個連續(xù)對策問題，其中S1=S2=[0,1]這個對策求解的結果為：公司方的最優(yōu)策略(為純策略)是y*=1/2，即兩個廠各生產(chǎn)一半；市場需求方的最優(yōu)策略(為混合策略)是：分別以0.5的概率取0和1，即要么全部需求都集中在A市，要么都集中在B市，且兩種情況發(fā)生的概率相等。該對策的值為VG=2，即當公司和市場均選擇各自的最優(yōu)策略時，兩市中需求大于供給的平均程度為2。多人非合作對策二、多人非合作對策所謂非合作對策，就是指局中人之間互不合作，對策略的選擇不允許事先有任何交換信息的行為，不允許訂立任何約定，矩陣對策就是一種非合作對策。一般非合作對策模型可描述為：(1)局中人集合：I={1,2,…,n};(2)每個局中人的策略集：S1,S2,…,Sn(均為有限集)；(3)局勢：s=(s1,…,sn)∈S1×…×Sn；(4)每個局中人i的贏得函數(shù)記為Hi(s),一般說來，一個非合作n人對策一般用符號G={I,{Si},{Hi}}表示。多人非合作對策它的含義是：在局勢s=(s1,…,sn)中，局中人i將自己的策略由si換成si0,其他局中人的策略不變而得到的一個新局勢。如果存在一個局勢s,使得對任意si0∈Si,有Hi(s)≥Hi(s‖si0)則稱局勢s對局中人i有利，也就是說，若局勢s對局中人i有利，則不論局中人i將自己的策略如何置換，都不會得到比在局勢s下更多的贏得。顯然，在非合作的條件下，每個局中人都力圖選擇對自己最有利的局勢。多人非合作對策如果局勢s對所有的局中人都有利，即對任意i∈I,si0∈Si,有Hi(s)≥Hi(s‖si0)則稱s為非合作對策G的一個平衡局勢(或平衡點)。當G為二人零和對策時，(αi*,βj*)為平衡局勢的充要條件是：對任意i,j,有aij*≤ai*j*≤ai*j若對任意i∈I,zi∈Si*，有Ei(x‖zi)≤Ei(x)則稱x為非合作n人對策G的一個平衡局勢(或平衡點)。定義6定義7多人非合作對策非合作n人對策在混合策略意義下的平衡局勢一定存在。對于二人有限非零和對策(亦稱為雙矩陣對策)，Nash定理的結論可表述為：一定存在x*∈S1*,y*∈S2*，使得x*TAy*≥xTAy*x∈S1*

x*TBy*≥x*TByy∈S2*定理13(Nash定理)多人非合作對策例14

求解2×2階雙矩陣對策，其中解已知Q=a11+a22-a21-a12=5,q=a22-a12=2,α=q/Q=2/5

R=b11+b22-b21-b12=5,r=b22-b21=3,β=r/R=3/5代入雙矩陣對策解的公式，得y≤2/5y=2/5y≥2/5y=00<y<1y=1多人非合作對策解不等式組，得到對策的3個平衡點：(x,y)=(0,0),(3/5,2/5),(1,1)由E1(x,y)=5xy-2(x+y)+1E2(x,y)=5xy-3(x+y)+2可得E1(3/5,2/5)=E2(3/5,2/5)=1/5E1(0,0)=1,E1(1,1)=2E2(0,0)=2,E2(1,1)=1合作對策合作對策的基本特征是參加對策的局中人可以進行充分的合作，即可以事先商定好，把各自的策略協(xié)調(diào)起來；可以在對策后對所得到的支付進行重新分配。合作的形式是所有局中人可以形成若干聯(lián)盟，每個局中人僅參加一個聯(lián)盟，聯(lián)盟的所得要在聯(lián)盟的所有成員中進行重新分配。在合作對策中，每個局中人如何選擇自己的策略不是主要研究的問題，應當強調(diào)的是如何形成聯(lián)盟，以及聯(lián)盟的所得如何被合理分配（即如何維持聯(lián)盟）的問題。三、合作對策合作對策局中人集合I特征函數(shù)v（S）其中I={1，2，…，n}，S為I的任一子集，也就是任何一個可能形成的聯(lián)盟，v(S)表示的是聯(lián)盟S在對策中的所得。合作對策的可行解是一個滿足下列條件的n維向量x=(x1,x2,…,xn):滿足上式的向量x稱為一個分配。合作對策的兩個基本要素是：合作對策例15（產(chǎn)品定價問題）設有兩家廠商（廠商1，廠商2）為同一市場生產(chǎn)同樣產(chǎn)品，可選擇的競爭策略是價格，目的是賺得最多的利潤。已知兩個廠商的需求函數(shù)為Q1=12-2P1+P2Q2=12-2P2+P1其中，P1，P2分別為兩個廠商的價格，Q1，Q2分別為市場對兩個廠商產(chǎn)品的需求量（實際銷售量）；又知，兩家廠商的固定成本均為20元。（1）廠商1的利潤函數(shù)為：π1=P1Q1-20=12P1-2P12+P1P2-20利潤最大化時的P1:同理可得：廠商1對廠商2的價格的反應函數(shù)廠商2對廠商1的價格的反應函數(shù)合作對策廠商1定價4元定價6元廠商2定價4元12，1220，4定價6元4，2016，16不合作：（12，12）（Nash均衡）合作：（16，16）（雙贏）對策論引言矩陣對策的基本理論矩陣對策的解法其他類型對策簡介沖突分析簡介沖突分析簡介一、沖突分析的理論基礎和發(fā)展沖突是具有不同目標的兩個或更多的個人或團體為了利益、資源等進行抗爭所造成的一種對立狀態(tài)。Howard的偏對策(metagame)理論Bennett的超對策(supergame,又稱為誤對策)理論Fraser和Hipel在對偏對策進行了改進的基礎上，提出了沖突分析方法。沖突分析的建模與分析二、沖突分析的建模與分析建模：系統(tǒng)分析人員要以系統(tǒng)的方式將所掌握的有關沖突的全面信息描述出來穩(wěn)定性分析：根據(jù)建立的模型和所能獲得的數(shù)據(jù)，確定沖突可能的解決方案（沖突的可能的解必須對參加沖突的各方面都是穩(wěn)定的(即沒有再改進的必要)）選手(player)方案或選擇(option)策略(strategy)結果(outcome)古巴導彈危機的案例分析三、古巴導彈危機的案例分析1.模型的建立時間點：美國剛在古巴發(fā)現(xiàn)蘇制導彈的1962年10月17日附近。選手：美國和蘇聯(lián)方案：美國有兩個方案：對古巴的導彈基地進行空襲(簡稱空襲)或實行軍事封鎖(簡稱封鎖)，美國可任選一個方案，或兩個都選，或都不選(即通過外交等途徑解決沖突)。蘇聯(lián)的方案是撤出部署的導彈(簡稱撤出)或進一步激化局勢(簡稱激化)，如用導彈襲擊美國，或既不撤出也不激化，即維持現(xiàn)狀。古巴導彈危機的案例分析古巴導彈危機中美國和蘇聯(lián)的方案及結果注：“1”表示選擇了一個方案，“0”表示沒有選擇該方案方案美國空襲010101010101封鎖001100110011蘇聯(lián)撤出000011110000激化000000001111十進制數(shù)0123456789