




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
運籌與優(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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二年級上數(shù)學教案 課件-除法的的初步認識第二課時-西師大版
- 幾倍(教案)二年級上冊數(shù)學滬教版
- 2025年分手費補償協(xié)議模板
- 第二章第一節(jié)地形地勢教學設計2023-2024學年人教版初中地理八年級上冊
- 2025年學習雷鋒精神62周年主題活動方案
- 2025年河南女子職業(yè)學院單招職業(yè)傾向性測試題庫匯編
- 第四單元口語交際:請你支持我 教學設計-2024-2025學年六年級上冊語文統(tǒng)編版
- 2025年懷化師范高等??茖W校單招職業(yè)適應性測試題庫完美版
- 2025年河北美術學院單招職業(yè)技能測試題庫一套
- 二零二五年度診所與醫(yī)療培訓學校合作協(xié)議
- 八年級數(shù)學下冊-全一冊-教學課件-(新版)浙教版
- 農產品電子商務培訓資料課件
- 傳熱學課后習題答案
- 酒店員工獎懲管理規(guī)章制度
- 視頻號精細化運營培訓課件
- 雅馬哈便攜式電子琴KB-100說明書
- 固定財產清查登記匯總表
- DB12-T 1153-2022城市軌道交通運營設備設施大修和更新改造技術規(guī)范
- ava標準錄播教室應用解決方案
- 粗粒土和巨粒土最大干密度試驗檢測記錄表
- 青島版五四制三年級下冊數(shù)學課件 小數(shù)的認識
評論
0/150
提交評論