運籌與優(yōu)化-對策論_第1頁
運籌與優(yōu)化-對策論_第2頁
運籌與優(yōu)化-對策論_第3頁
運籌與優(yōu)化-對策論_第4頁
運籌與優(yōu)化-對策論_第5頁
已閱讀5頁,還剩40頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

運籌與優(yōu)化

第十四章對策論

運籌與優(yōu)化--對策論對策論對策論的基本概念對策論的基本定理矩陣對策的解法運籌與優(yōu)化--對策論第一節(jié)對策論的基本概念

對策論亦稱競賽論或博奕論,是研究具有斗爭或競爭性質的數(shù)學理論和方法.

具有競爭或對抗性質的行為稱為對策行為.

對策論是研究對策行為中競爭各方是否存在最合理的行動方案,以及如何找到最合理方案的數(shù)學理論和方法.

具有對策行為的模型稱為對策模型,或對策.運籌與優(yōu)化--對策論

對策三要素局中人:在一個對策行為中,有權決定自己行動方案的對策者.n個局中人的集合I={1,2,…,n}.

理智的決策者:不存在僥幸心理者.策略集:可供局中人i選擇的一個實際可行的完整的行動方案稱為一個策略si,策略集Si.

局勢:在對策中,各局中人所選定的策略構成的策略組s=(s1,s2,…sn).全體局勢S=S1×S2×…×Sn贏得函數(shù):局勢s的函數(shù)Hi(s).矩陣對策:二人有限零和對策.運籌與優(yōu)化--對策論

第二節(jié)對策論的基本定理局中人I的純策略集S1={α1,α2,…αm};局中人Ⅱ的純策略集S2={β1,β2,…βn};對任一純局勢(αi,βj)(共m×n個),局中人I的贏得值為aij,贏得矩陣為A=(aij)m×n.

局中人Ⅱ的贏得矩陣為-A.矩陣對策記為G={Ⅰ,Ⅱ,S1,S2;A}

或G={S1,S2;A}.

運籌與優(yōu)化--對策論

田忌齊王β1(上中下)β2(上下中)β3(中上下)β4(中下上)β5(下中上)β6(下上中)

α1(上中下)α2(上下中)α3(中上下)α4(中下上)α5(下中上)α6(下上中)311-11113-11111131-1111131-11-11131-111113

例1.“齊王賽馬”中,齊王的贏得矩陣為:

運籌與優(yōu)化--對策論最優(yōu)策略:有利于自己獲得最大贏得(或最少損失)的策略.選擇最優(yōu)策略的原則:牢記對方總是以最不利于你的行動方案來對付你.例2.設矩陣對策G={S1,S2;A},其中

S1={α1,α2,α3,α4},S2={β1,β2,β3},試求雙方的最優(yōu)策略和贏得.理智行為:雙方各按最不利于自己的情形中選擇最為利己的結果作為決策的依據(jù).運籌與優(yōu)化--對策論定義1.設矩陣對策G={S1,S2;A

},若等式

(1)成立,記,則稱VG為對策G的值,稱使(1)成立的純局勢為G在純策略下的解(或平衡局勢、雙贏局勢).

定理1.矩陣對策G={S1,S2;A

}在純策略中有解的充要條件是:存在純局勢使得

(2)(i=1,2,…,m,j=1,2,…,n).既是其所在行的最小元素,又是其所在列的最大元素.運籌與優(yōu)化--對策論定義2.設實函數(shù)f(x,y)定義在x∈A,y∈B上,若存在x*∈A,y*∈B,使得對x∈A,y∈B,有

f(x,y*)≤f(x*,y*)≤f(x*,y)(3)則稱(x*,y*)為f(x,y)的一個鞍點.矩陣對策G在純策略意義下有解,且的充要條件是:是矩陣A的一個鞍點.例3.確定p和q的取值范圍,使矩陣A在(α2,β2)處存在鞍點.其中∵q≤a22≤p

,∴p≥5,q≤5運籌與優(yōu)化--對策論例4.設矩陣對策G={S1,S2;A},其中

S1={α1,α2,α3,α4},S2={β1,β2,β3},試求雙方的最優(yōu)策略和贏得.性質1(無差別性).若(αk,βr)和(αp,βq)是對策G的兩個解,則akr=apq.

事實上,由,有

apq≤apr≤akr≤akq≤apq因此akr=apq.運籌與優(yōu)化--對策論性質2(可交換性).若(αk,βr)和(αp,βq)

是對策G的兩個解,則(αk,βq)和(αp,βr)

也是對策G的解.

由aiq≤apq=akr≤akq≤apq=akr≤akj

得aiq≤akq≤akj,即akq是鞍點.

故(αk,βq)是解.同理,(αp,βr)是解.性質1、2表明,矩陣對策的值是唯一的.例5.P385例題.運籌與優(yōu)化--對策論定義3.設矩陣對策G={S1,S2;A},A=(aij)m×n.若局中人I以概率xi≥0取純策略αi,局中人Ⅱ以概率yj≥0取純策略βj,且.記

則S1*,S2*分別稱為局中人I和Ⅱ的混合策略集.稱x∈S1*,y∈S2*為局中人I和Ⅱ的混合策略,(x,y)為混合局勢,局中人I的贏得函數(shù)為稱G*={S1*,S2*,E}為對策G的混合擴充.運籌與優(yōu)化--對策論設則有定義4.設G*={S1*,S2*;E}是矩陣對策G={S1,S2;A}的混合擴充,若

記其值為VG,則稱VG為對策G*的值,使(3)成立的混合局勢(x*,y*)為G在混合策略意義下的解.運籌與優(yōu)化--對策論定理2.矩陣對策G={S1,S2;A

}在混合策略中有解的充要條件是:(x*,y*)為E(x,y)的一個鞍點,即對一切x∈S1*,y∈S2*,有

E(x,y*)≤E(x*,y*)≤E(x*,y)(4)注意:G在純策略下解存在時,定義4中的

;G在混合策略意義下的解(x*,y*)存在時,VG=E(x*,y*).例4.解矩陣對策G={S1,S2;A

},其中運籌與優(yōu)化--對策論局中人I取純策略αi時,其贏得函數(shù)為

E(i,y)=∑aijyj,

局中人Ⅱ取純策略βj時,其贏得函數(shù)為

E(x,j)=∑aijxi.

由上兩式得

E(x,y)=∑E(i,y)xi(5)E(x,y)=∑E(x,j)yj.(6)定理3.設x∈S1*,y∈S2*,則(x*,y*)是G的解的充要條件是:對任意i=1,2,…,m和j=1,2,…,n,有E(i,y*)≤E(x*,y*)≤E(x*,j)(7)

運籌與優(yōu)化--對策論定理3.設x∈S1*,y∈S2*,則(x*,y*)是G的解的充要條件是:對任意i=1,2,…,m和j=1,2,…,n,有E(i,y*)≤E(x*,y*)≤E(x*,j)(7)

證明:設(x*,y*)是G的解,則由定理2,有

E(x,y*)≤E(x*,y*)≤E(x*,y)(4)

由于純策略是混合策略的特例,故(7)式成立.

反之,設(7)式成立,由(5)、(6)有

E(x,y*)=∑E(i,y*)xi≤E(x*,y*)∑xi=E(x*,y*)E(x*,y)=∑E(x*,j)yj≥E(x*,y*)∑yj=E(x*,y*)可知(4)式成立,故(x*,y*)是G的解運籌與優(yōu)化--對策論定理4.設x*∈S1*,y*∈S2*,則(x*,y*)是G的解的充要條件是:存在數(shù)v,使得x*,y*分別是不等式組

(8)(9)的解,且v=VG.運籌與優(yōu)化--對策論定理4.證明:“”因G有解,(7)式成立.取v=E(x*,y*)就有(8),(9).“”因對任意x∈S1*,y∈S2*,有

E(x,y*)=∑E(i,y*)xi≤∑vxi=vE(x*,y)=∑E(x*,j)yj≥∑vyj=v于是E(x,y*)≤v≤E(x*,y).

特別有E(x*,y*)≤v≤E(x*,y*).故v=E(x*,y*)=VG.運籌與優(yōu)化--對策論定理5.任意矩陣對策G={S1,S2;A}一定存在混合策略意義下的解.

證明:由定理4,只要證明存在數(shù)v*和x*∈S1*,y*∈S2*,使得

(10)為此,考慮下列兩個線性規(guī)劃問題:運籌與優(yōu)化--對策論

易知(P)和(D)互為對偶,x=(1,0,…,0)T∈Em,w=min

a1j是(P)的可行解,y=(1,0,…,0)T∈En,v=maxai1是(D)的可行解.

因此(P)和(D)皆存在最優(yōu)解x*∈S1*,y*∈S2*,且最優(yōu)值v*=w*.故(10)式成立.運籌與優(yōu)化--對策論定理6.設(x*,y*)是矩陣對策G的解,v=VG,那么

(1).若xi*>0,則;(2).若yj*>0,則;(3).若,則xi*=0;(4).若,則yj*=0.證明:由定義有v=maxE(x,y*),x∈S1*,故

運籌與優(yōu)化--對策論又因所以,當xi*>0,必有;當,必有xi*=0.

故(1),(3)得證.同理可證(2),(4).定理7.設矩陣對策G1={S1,S2;A1}的解集T(G1),G2={S1,S2;A2}的解集為T(G2).其中A1=(aij),A2=(aij+p),p∈R.則

(1).VG2=VG1+p;(2).T(G1)=T(G2).運籌與優(yōu)化--對策論定理8.設矩陣對策G1={S1,S2;A}的解集為T(G1),G2={S1,S2;αA}(α∈R+)的解集為T(G2).則

(1).VG2=αVG1;(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—定理9的證明:

利用鞍點的概念和定理3.運籌與優(yōu)化--對策論定義5.設矩陣對策G={S1,S2;A},其中A=(aij),S1={α1,α2,…αm},S2={β1,β2,…βn}

若對j=1~n,都有akj≥atj,則稱局中人I的純策略αk優(yōu)超于αt;若對i=1~m,都有aip≤aiq,則稱局中人Ⅱ的純策略βp優(yōu)超于βq.定理10.設矩陣對策G={S1,S2;A},如果純策略α1被純策略α2,…,

αm中之一所優(yōu)超,由G可得新的矩陣對策G’={S1’,S2’;A’},于是有

(1).VG’=VG;(2).T2(G’)包含于T2(G)中;(3).若(x2,…,xm)T∈T1(G’),則

(0,x2,…,xm)T∈T1(G).運籌與優(yōu)化--對策論推論.如果純策略α1被純策略α2,…αm的凸線性組合所優(yōu)超,則定理10的結論仍成立.類似地,對局中人Ⅱ,如果純策略β1被純策略β2,…,

βn的凸線性組合所優(yōu)超,于是有(1).VG’=VG;(2).T1(G’)包含于T1(G)中;(3).若(y2,…,ym)T∈T2(G’),則

(0,y2,…,ym)T∈T2(G).優(yōu)超原則:可在贏得矩陣A中劃去被其它行(列)或其它行(列)的凸線性組合所優(yōu)超的那些行(列).運籌與優(yōu)化--對策論例5.設贏得矩陣A如下,求解矩陣對策G.解:

由于矩陣A中行r4≥r1,r3≥r2,故可從A中劃去第1行和第2行,得到新矩陣A1.

對于A1,列c1≤c3,c2≤c4,(1/3)c1+(2/3)c3≤c5,可從A1中劃去第3列、第4列、第5列,得到新矩陣A2.運籌與優(yōu)化--對策論

對于A2,r1≥r3,從A2中劃去第3行,得到新矩陣A3.對于A3,由于故A3無鞍點.應用定理4,求解不等式組:

7x3+4x4≥v7y1+3y2≤v3x3+6x4≥v(I);4y1+6y2≤v(Ⅱ)x3+x4=1y1+y2=1x3,x4≥0

y1,y2≥0運籌與優(yōu)化--對策論

首先求解下列等式組的非負解:

7x3+4x4=v7y1+4y2=v3x3+6x4=v(I’)4y1+6y2=v(Ⅱ’)x3+x4=1y1+y2=1求得x3*=1/3,x4*=2/3,v=5,y1*=1/2,y2*=1/2.

于是,原對策G的解是

x*=(0,0,1/3,2/3,0)T,y*=(1/2,1/2,0,0,0)T,VG=5.運籌與優(yōu)化--對策論第三節(jié)矩陣對策論的解法

一、2×2對策的公式法設,當A無鞍點時,可以證明G有嚴格非負解:x1*=(a22-a21)/[(a11+a22)-(a12+a21)],x2*=(a11-a12)/[(a11+a22)-(a12+a21)];y1*=(a22-a12)/[(a11+a22)-(a12+a21)],y2*=(a11-a21)/[(a11+a22)-(a12+a21)];VG=(a11a22-a12a21)/[(a11+a22)-(a12+a21)].例1.設矩陣對策G={S1,S2;A},其中

則對策的最優(yōu)解為:x*=(1/2,1/2),y*=(1/4,3/4),VG=5/2運籌與優(yōu)化--對策論

二、圖解法例2.設矩陣對策G={S1,S2;A},其中S1={α1,α2},S2={β1,β2,β3}.試用圖解法求解.解:設局中人I的混合策略為(x1,1-x1)T,x1∈[0,1].做兩條垂線P0(x1=0)和P1(x1=1),P0

P1

表示局中人I分別取純策略β3

11α2和α1.垂線P0上的值表

7

β1

示局中人I取α2時,局中人5B

β2Ⅱ取各βj時的贏得值.同理,

2

S

23垂線P1上的值表示局中人I取

0A1

α1時,局中人Ⅱ取各βj時的贏得值.圖1

運籌與優(yōu)化--對策論

P0

圖1P1

β3

11

7

5

β1

B

β2

3

2S2

0A1

如圖1,當局中人I選擇策略(x1,1-x1)T時,其最少可能的收入是局中人Ⅱ選擇β1,β2,β3時所確定的三條直線

2x1+7(1-x1)=v3x1+5(1-x1)=v11x1+2(1-x1)=v在x1處的縱坐標中之最小者.所以局中人I按maxmin原則,應選擇x1=OA,而AB即為對策值.運籌與優(yōu)化--對策論聯(lián)立過點B的兩條線段β2和β3所確定的方程:3x1+5(1-x1)=VG,11x1+2(1-x1)=VG解得x1=3/11,VG=49/11.

故局中人I的最優(yōu)策略為x*=(3/11,8/11)T.

由于B點是β2和β3的交點,局中人Ⅱ的最優(yōu)混合策略必由β2和β3組成.由定理6,聯(lián)立方程:3y2+11y3=49/11,5y2+2y3=49/11,y2+y3=1

求得y2*=9/11,y3*=2/11.

故局中人Ⅱ的最優(yōu)策略為y*=(0,9/11,2/11)T運籌與優(yōu)化--對策論例3.用圖解法求解對策G={S1,S2;A},其中

S1={α1,α2,α3},S2={β1,β2},解:設局中人Ⅱ的混合策略為(y1,1-y1)T中,由圖2可知,三條直線α1,α2,α3

P0

P1

在任一點y1∈[0,1]處

圖211

的縱坐標分別是局中

7

S

α3

人Ⅱ取(y1,1-y1)T時的

6B1B2

α26

支付.根據(jù)最不利中選取最利己的原則,局中人Ⅱ按minmax原則,

2

α1

2

0

A1

A2

1運籌與優(yōu)化--對策論局中人Ⅱ應選OA1≤y1≤OA2,則對策值為6.由

2y1+7(1-y1)=6,11y1+2(1-y1)=6解得OA1=1/5,OA2=4/9.

故局中人Ⅱ的最優(yōu)策略為

y*=(y1,1-y1)T(1/5≤y1≤4/9).

由于B1是α1和α2的交點,B2是α3和α2的交點,根據(jù)定理6,可由

11(1/5)+2(1-1/5)<6,得x3=0;2(4/9)+7(5/9)<6,得x1=0.于是得x1*=x3*=0,x2*=1.故局中人I取純策略α2.運籌與優(yōu)化--對策論例4.求贏得矩陣A的矩陣對策G.解法1.優(yōu)超法:

因列c2≤c3,故可劃去第3列;

又因(2/3)c4+(1/3)c1=c2,故可劃去第2列.

于是,求贏得矩陣A’的矩陣對策G’.其中從而求得原對策G的一個解為

x*=(3/4,1/4)T,y*=(5/8,0,0,3/8)T,VG=13/4.解法2.圖解法:

由圖可見,局中人I的最優(yōu)策略為x*=(3/4,1/4)T.

若局中人Ⅱ的最優(yōu)策略為y*=(y1*,y2*,y3*,y4*)T,運籌與優(yōu)化--對策論

有y3*=0(∵4x1+5(1-x1)>v),而y1*,y2*,y4*由方程:4y1+(8/3)y2+2y4=13/4y1+5y2+7y4=13/4y1+y2+y4=17β4

易知具有無窮多解5β3

故局中人Ⅱ有無窮4

多個最優(yōu)混合策略.13/4β2

例4說明,優(yōu)超法β1

8/3

可能劃去原矩陣1

對策的一些解.S03/41P0

圖3P1

運籌與優(yōu)化--對策論線性方程組方法:

設xi*、yj*均不為零,先求解等式組

的非負解.

若(Ⅰ),(Ⅱ)的解有負分量,就將(Ⅰ),(Ⅱ)的某些等式改為不等式.

三、線性方程組方法運籌與優(yōu)化--對策論

定理11.設矩陣對策G={S1,S2;A1}的值為VG,

則證明:因VG是對策的值,故一方面,

求解矩陣對策的線性規(guī)劃方法:運籌與優(yōu)化--對策論

另一方面,有

故得

同理有

運籌與優(yōu)化--對策論

根據(jù)定理7,可設v>0.作變換xi’=xi/v,i=1,2,…m,則由定理4有

(1)

根據(jù)定理11,

于是(1)等價于線性規(guī)劃(P):

運籌與優(yōu)化--對策論

同理,作變換yj’=y/v,則定理4的另一不等組等價于線性規(guī)劃(D):(2)(3)注:一般先求解問題(D),再代回變換即可求出原對策解.運籌與優(yōu)化--對策論例5.利用線性規(guī)劃求解對策G,其中A:解:為使對策值V≥0,由定理7,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論