第12章运筹学课件 对策论.pptx

第12章运筹学课件 对策论.pptx

《第12章运筹学课件 对策论.pptx》由会员分享，可在线阅读，更多相关《第12章运筹学课件 对策论.pptx（63页珍藏版）》请在冰点文库上搜索。

第十二章对策论OperationalResearch（OR）对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介对策现象和对策论一、对策现象和对策论对策论（gametheory）亦称博弈论或竞赛论，是研究具有对抗或竞争性质现象的数学理论和方法。

它既是现代数学的一个新分支，也是运筹学的一个重要学科。

对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般日常生活等有着密切联系，并且处理问题的方法又有明显特色，所以日益引起广泛的重视。

齐王赛马对策现象的三要素二、对策现象的三要素1.局中人（players）：

参与对抗的各方；2.策略（strategies）：

局中人选择对付其它局中人的行动方案称为策略；3.赢得函数（支付函数）（payofffunction）：

各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人的对策结果（量化）。

“齐王赛马”齐王在各局势中的对策结果（单位：

千金）对策问题举例及对策的分类三、对策问题举例及对策的分类例1市场购买力争夺问题据预测，某乡镇下一年的饮食品购买力将有4000万元。

乡镇企业和中心城市企业饮食品的生产情况是：

乡镇企业有特色饮食品和低档饮食品两类，中心城市企业有高档饮食品和低档饮食品两类产品。

它们争夺这一部分购买力的结局见下表（单位：

万元）。

问题是乡镇企业和中心城市企业应如何选择对自己最有利的产品策略。

乡镇策略中心城市企业的策略出售高档饮食品出售低档饮食品出售特色饮食品20003000出售一般饮食品10003000对策问题举例及对策的分类例2销售竞争问题假定企业,均能向市场出售某一产品，不妨假定他们可于时间区间0,1内任一时点出售。

设企业在时刻x出售，企业在时刻y出售，则企业的收益（赢得）函数为：

若xy问这两个企业各选择什么时机出售对自己最有利?

在这个例子中，企业,可选择的策略均有无穷多个。

对策问题举例及对策的分类例3费用分摊问题假设沿某一河流有相邻的3个城市A，B，C，各城市可单独建立水厂，也可合作兴建一个大水厂。

经估算，合建一个大水厂，加上敷设管道的费用，要比单独建3个小水厂的总费用少。

但合建大厂的方案能否实施，显然要看总的建设费用分摊得是否合理。

如果某个城市分摊到的费用比它单独建设水厂的费用还多的话，它显然不会接受合作的方案。

问题是应如何合理地分摊费用，使合作兴建大水厂的方案得以实现?

对策问题举例及对策的分类例4拍卖问题最常见的一种拍卖形式是先由拍卖商把拍卖品描述一番，然后提出第一个报价。

接下来由买者报价，每一次报价都要比前一次高，最后谁出的价最高，拍卖品即归谁所有。

假设有n个买主给出的报价分别为p1,pn,且不妨设pnpn-1p1,则买主n只要报价略高于pn-1，就能买到拍卖品，即拍卖品实际上是在次高价格上卖出的。

现在的问题是，各买主之间可能知道他人的估价，也可能不知道他人的估价，每人应如何报价对自己能以较低的价格得到拍卖品最为有利?

最后的结果又会怎样?

对策问题举例及对策的分类例5囚犯难题设有两个嫌疑犯因涉嫌某一大案被警官拘留，警官分别对两人进行审讯。

根据法律，如果两个人都承认此案是他们干的，则每人各判刑7年；如果两人都不承认，则由于证据不足，两人各判刑1年；如果只有一人承认，则承认者予以宽大释放，而不承认者将判刑9年。

因此，对两个囚犯来说，面临着一个在“承认”和“不承认”这两个策略间进行选择的难题。

对策问题举例及对策的分类对策论中将问题根据不同方式进行分类:

（1）根据局中人的个数，分为二人对策和多人对策；

（2）根据各局中人的赢得函数的代数和是否为零，分为零和对策与非零和对策；（3）根据各局中人间是否允许合作，分为合作对策和非合作对策；（4）根据局中人的策略集中的策略个数，分为有限对策和无限对策。

此外，还有许多其他的分类方式，例如根据策略的选择是否与时间有关，可分为静态对策和动态对策；根据对策模型的数学特征，可分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策等。

对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介矩阵对策的基本理论二人有限零和对策：

（又称矩阵策略）局中人为2；每局中人的策略集中策略权目有限；在任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。

记矩阵对策为:

G=S1,S2；A的策略集的赢得矩阵的策略集“齐王赛马”即是一个矩阵策略。

矩阵对策的纯策略矩阵对策的纯策略例6设有一矩阵对策G=S1,S2;A，其中：

采取1至少得益-8223-104-31：

采取最多损失9226取大则取2maxminaij=2ij取小则取2minmaxaij=2ji平衡局势（2,2），这个局势就是双方均可接受的，且对双22方来说都是一个最稳3妥的结果。

因此，和应分别是局中人和的最优纯策略。

矩阵对策的纯策略成立，记其值为VG，则称VG为对策的值，称使其成立的ij纯局势（*,*）为G在纯策略意义下的解（或平衡局势），ij称*和*分别为局中人和的最优纯策略。

定义1设G=S1,S2;A为一矩阵对策，其中S1=1,m，S2=1,n，A=（aij）mn。

若矩阵对策的纯策略定理1中式子的对策意义是：

一个平衡局势（i,j）应具有这*样的性质：

当局中人选择了纯策略*后，局中人为了使其i所失最少，只能选择纯策略*，否则就可能失的更多；反之，j当局中人选择了纯策略*后，局中人为了得到最大的赢得*j也只能选择纯策略i，否则就会赢的更少，双方的竞争在局势（i,j）下达到了一个平衡状态。

*矩阵对策G=S1,S2;A在纯策略意义下有解的充要条件是：

存在纯局势（i,j），使得对任意i和j，有aijaij*aij定理1矩阵对策的纯策略例7设有矩阵对策G=S1,S2;A，其中解有i*=1,3j*=2,4故（1,2），（1,4），（3,2），（3,4）都是对策的解，且VG=8矩阵对策的纯策略aij=aij1122若（i1,j1）和（i2,j2）是对策G的两个解，则（i1,j2）和（i2,j1）也是对策G的解。

矩阵对策的值是惟一的，即当一个局中人选择了最优纯策略后，他的赢得值不依赖于对方的纯策略。

一般对策的解可以是不惟一的，当解不惟一时，解之间的关系具有下面两条性质：

性质1（无差别性）若（i1,j1）和（i2,j2）是对策G的两个解，则性质2（可交换性）矩阵对策的混合策略设矩阵对策G=S1,S2,A当maxminaijminmaxaij时，ijji不存在最优纯策略求解混合策略。

二、矩阵对策的混合策略矩阵对策的混合策略记则分别称S1和S2为局中人和的混合策略集（或策略集）；*12对xS*和yS*，称x和y为混合策略（或策略），（x,y）为混合局势（或局势）。

局中人的赢得函数记成称G*=S1,S2;E为对策G的混合扩充。

*定义2设有矩阵对策G=S1,S2;A，其中矩阵对策的混合策略记其值为VG，则称VG为对策G的值，称使上式成立的混合局势（x*,y*）为G在混合策略意义下的解（或平衡局势），称x*和y*分别为局中人和的最优混合策略。

定义3设G*=S1,S2;E是矩阵对策G=S1,S2;A的混合扩充。

如果*定理2矩阵对策G在混合策略意义下有解的充要条件是：

存在x*S1,yS2，使得对任意xS1和yS2，有*E（x,y*）E（x*,y*）E（x*,y）矩阵对策的混合策略例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）分别为局中人和的最优策略，对策的值（局中人的赢得的期望值）为VG=9/2。

矩阵对策的基本定理12设x*S*,y*S*,则（x*,y*）为对策G的解的充要条件是：

12设x*S*,yS*，则（x*,y*）为G的解的充要条件是：

存在数v,使得x*和y*分别是下列不等式组的解，且v=VG。

j=1,2,.,ni=1,2,.,mi=1,2,.,mj=1,2,.,n三、矩阵对策的基本定理定理3对任意i=1,m和j=1,n，有E（i,y*）E（x*,y*）E（x*,j）定理4矩阵对策的基本定理设（x*,y*）是矩阵对策G的解，v=VG，则*

（1）若xi0,则*

（2）若yj0,则（3）若*,则xi=0（4）若,则y*j=0定理5对任一矩阵对策G=S1,S2;A，一定存在混合策略意义下的解。

定理6矩阵对策的基本定理设G1=S1,S2,A为一矩阵对策，且A=-AT为斜对称矩阵（亦称这种对策为对称对策），则

（1）VG=0

（2）T1（G）=T2（G）其中，T1（G）和T2（G）分别为局中人和的最优策略集。

定理7设有两个矩阵对策G1=S1,S2,A1，G2=S1,S2,A2,其中A1=（aij）,A2=（aij+L），L为一任意常数，则

（1）VG2=VG1+L

（2）T（G1）=T（G2）定理8设有两个矩阵对策G1=S1,S2,A，G2=S1,S2,A,其中0，为一任意常数，则

（1）VG2=VG1

（2）T（G1）=T（G2）定理9对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介矩阵对策的解法一、图解法例9用图解法求解矩阵对策G=S1,S2,A，其中解设局中人的混合策略为（x,1-x）T，x0,1。

02571x132ABB1B2B3图解法解得x=3/11,VG=49/11。

所以，局中人的最优策略为x*=（3/11,8/11）T下面求局中人的最优策略：

局中人的最优混合策略只由2和3组成设y*=（y1,y2,y3）T为局中人的最优混合策略，则由*E（x*,1）=23/11+78/11=62/1149/11=VG，根据定理6，112必有y*=0。

又因x*=3/110,x*=8/110，再根据定理6，可由求得y2=9/11,y3=2/11。

所以，局中人的最优混合策略*为y*=0,9/11,2/11T方程组法二、方程组法例10求解矩阵对策G=S1,S2;A，其中A为12345方程组法123454严格优于1，所以划去1同理，划去第二行，第三列，第四列和第五列剩下的矩阵中第一行优于第三行，所以划去第三行易知A1没有鞍点，由定理12.6求出方程组和的非负解方程组法于是，以矩阵A为赢得矩阵的对策的一个解就是：

线性规划法三、线性规划法例11利用线性规划方法求解下述矩阵对策，其赢得矩阵为：

由定理5可知，可将其化成两个互为对偶的线性规划解问题：

线性规划法解上述线性规划，得因此对策问题的解为：

对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介二人无限零和对策一、二人无限零和对策表示方法：

G=S1,S2;H其中S1和S2中至少有一个是无限集合，H为局中人的赢得函数。

局中人的至少赢得：

局中人的至多所失：

二人无限零和对策ij设G=S1,S2;H为二人无限零和对策。

若存在*S1,*S2,使得*记其值为VG，则称VG为对策G的值，称使该式成立的（i,jij*）为G在纯策略意义下的解，*,*分别称为局中人和的最优纯策略。

ij12（*,*）为G=S,S;H在纯策略意义下的解的充要条件是：

对任意iS1,jS2,有H（i,j）H（i,j）H（i,j）*定义4定理10二人无限零和对策例12设局中人、互相独立地从0,1中分别选择一个实数x和y，局中人的赢得函数为H（x,y）=2x2-y2。

对策中，局中人希望H越大越好，局中人则希望H越小越好。

图中给出了H（x,y）的等值线，通过对该图的分析，不难看出双方竞争的平衡局势为（1，1），即i=1,j=1分别为局中人和的最*ij优纯策略，VG=1。

可以验证，对（*,*）=（1,1），定理10的等式是成立的。

二人无限零和对策无限对策的混合策略：

局中人和的混合策略X和Y分别为策略集S1和S2上的概率分布（或分布函数），混合策略集记为和。

若用x,y表示纯策略，FX（x）,FY（y）表示混合策略X，Y的分布，则局中人的赢得函数可以有以下4种形式：

H（x,y）以及二人无限零和对策（X*,Y*）为对策G=S1,S2;H的解的充要条件是：

对任意X,Y，有H（X,Y*）H（X*,Y*）H（X*,Y）当S1=S2=0,1，且H（x,y）为连续函数时，称这样的对策为连续对策。

定义5如果有则称VG为对策G的值，称使上式成立的（X*,Y*）为对策G的解，X*和Y*分别为局中人和的最优策略。

定理11对任何连续对策，一定有v1=v2。

例13（生产能力分配问题）某公司下属甲、乙两个工厂，分别位于A，B两市。

设两厂总生产能力为1个单位，两市对工厂产品的总需求也是1个单位。

如果A市的需求量为x,则B市的需求量为1-x，这时只要安排A厂的生产能力为x，就能使供需平衡。

但现在不知道A市的确切需求量x是多少，如果安排A厂的生产能力为y，则将产生供需上的不平衡。

不平衡的程度可用数值表示为：

二人无限零和对策公司的目标是选择y，使得达到极小。

定理12二人无限零和对策如果以市场需求为一方，公司为另一方，则以上问题可转化为一个连续对策问题，其中S1=S2=0,1这个对策求解的结果为：

公司方的最优策略（为纯策略）是y*=1/2，即两个厂各生产一半；市场需求方的最优策略（为混合策略）是：

分别以0.5的概率取0和1，即要么全部需求都集中在A市，要么都集中在B市，且两种情况发生的概率相等。

该对策的值为VG=2，即当公司和市场均选择各自的最优策略时，两市中需求大于供给的平均程度为2。

多人非合作对策二、多人非合作对策所谓非合作对策，就是指局中人之间互不合作，对策略的选择不允许事先有任何交换信息的行为，不允许订立任何约定，矩阵对策就是一种非合作对策。

一般非合作对策模型可描述为：

（1）局中人集合：

I=1,2,n;

（2）每个局中人的策略集：

S1,S2,Sn（均为有限集）；（3）局势：

s=（s1,sn）S1Sn；（4）每个局中人i的赢得函数记为Hi（s）,一般说来，一个非合作n人对策一般用符号G=I,Si,Hi表示。

多人非合作对策它的含义是：

在局势s=（s1,sn）中，局中人i将自己的策略由si换成si,其他局中人的策略不变而得到的一个新局0势。

如果存在一个局势s,使得对任意siSi,有0iHi（s）Hi（ss0）则称局势s对局中人i有利，也就是说，若局势s对局中人i有利，则不论局中人i将自己的策略如何置换，都不会得到比在局势s下更多的赢得。

显然，在非合作的条件下，每个局中人都力图选择对自己最有利的局势。

多人非合作对策iHi（s）Hi（ss0）则称s为非合作对策G的一个平衡局势（或平衡点）。

ij当G为二人零和对策时，（*,*）为平衡局势的充要条件是：

对任意i,j,有aij*ai*j*ai*ji若对任意iI,ziS*，有Ei（xzi）Ei（x）则称x为非合作n人对策G的一个平衡局势（或平衡点）。

定义6如果局势s对所有的局中人都有利，即对任意iI,siSi,有0定义7多人非合作对策x*TAy*xTAy*xS*21x*TBy*x*TByyS*定理13（Nash定理）非合作n人对策在混合策略意义下的平衡局势一定存在。

对于二人有限非零和对策（亦称为双矩阵对策），Nash定理的结论可表述为：

一定存在x*S1,yS2，使得*多人非合作对策例14求解22阶双矩阵对策，其中解已知Q=a11+a22-a21-a12=5,q=a22-a12=2,=q/Q=2/5R=b11+b22-b21-b12=5,r=b22-b21=3,=r/R=3/5代入双矩阵对策解的公式，得y2/5y=2/5y2/5y=00y1y=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,E2（0,0）=2,E1（1,1）=2E2（1,1）=1三、合作对策合作对策的基本特征是参加对策的局中人可以进行充分的合作，即可以事先商定好，把各自的策略协调起来；可以在对策后对所得到的支付进行重新分配。

合作的形式是所有局中人可以形成若干联盟，每个局中人仅参加一个联盟，联盟的所得要在联盟的所有成员中进行重新分配。

在合作对策中，每个局中人如何选择自己的策略不是主要研究的问题，应当强调的是如何形成联盟，以及联盟的所得如何被合理分配（即如何维持联盟）的问题。

合作对策合作对策合作对策的可行解是一个满足下列条件的n维向量x=（x1,x2,xn）:

满足上式的向量x称为一个分配。

合作对策的两个基本要素是：

局中人集合I特征函数v（S）其中I=1，2，n，S为I的任一子集，也就是任何一个可能形成的联盟，v（S）表示的是联盟S在对策中的所得。

例15（产品定价问题）设有两家厂商（厂商1，厂商2）为同一市场生产同样产品，可选择的竞争策略是价格，目的是赚得最多的利润。

已知两个厂商的需求函数为Q1=12-2P1+P2Q2=12-2P2+P1其中，P1，P2分别为两个厂商的价格，Q1，Q2分别为市场对两个厂商产品的需求量（实际销售量）；又知，两家厂商的固定成本均为20元。

合作对策

（1）厂商1的利润函数为：

1=P1Q1-20=12P1-2P1+P1P2-202利润最大化时的P1:

同理可得：

厂商1对厂商2的价格的反应函数厂商2对厂商1的价格的反应函数厂商1定价4元定价6元厂商2定价4元定价6元12，1220，44，2016，16不合作：

（12，12）（Nash均衡）合作：

（16，16）（双赢）合作对策对策论引言矩阵对策的基本理论矩阵对策的解法其他类型对策简介冲突分析简介一、冲突分析的理论基础和发展冲突是具有不同目标的两个或更多的个人或团体为了利益、资源等进行抗争所造成的一种对立状态。

Howard的偏对策（metagame）理论Bennett的超对策（supergame,又称为误对策）理论冲突分析简介Fraser和Hipel在对偏对策进行了改进的基础上，提出了冲突分析方法。

二、冲突分析的建模与分析建模：

系统分析人员要以系统的方式将所掌握的有关冲突的全面信息描述出来稳定性分析：

根据建立的模型和所能获得的数据，确定冲突可能的解决方案（冲突的可能的解必须对参加冲突的各方面都是稳定的（即没有再改进的必要））冲突分析的建模与分析选手（player）方案或选择（option）策略（strategy）结果（outcome）古巴导弹危机的案例分析三、古巴导弹危机的案例分析1.模型的建立时间点：

美国刚在古巴发现苏制导弹的1962年10月17日附近。

选手：

美国和苏联方案：

美国有两个方案：

对古巴的导弹基地进行空袭（简称空袭）或实行军事封锁（简称封锁），美国可任选一个方案，或两个都选，或都不选（即通过外交等途径解决冲突）。

苏联的方案是撤出部署的导弹（简称撤出）或进一步激化局势（简称激化），如用导弹袭击美国，或既不撤出也不激化，即维持现状。

古巴导弹危机的案例分析古巴导弹危机中美国和苏联的方案及结果注：

“1”表示选择了一个方案，“0”表示没有选择该方案方案美国空袭010101010101封锁001100110011苏联撤出000011110000激化000000001111十进制数01234567891011古巴导弹危机中美国的偏好序列古巴导弹危机中苏联的偏好序列古巴导弹危机的案例分析古巴导弹危机的案例分析2.稳定性分析偏好序列下面标出的数字表示了由该结果进行单方面改进所得到的结果（称为UI）。

所谓一个单方面改进是指一个选手在当前结果下，假定其他选手的策略不变所能得到的更好的结果。

古巴导弹危机的案例分析对任一给定的可行结果，可以确定以下四种稳定性，

（1）合理稳定如果对一个结果q来说，选手A不存在单方面改进，即该选手所选择的策略已经是另一选手选定策略下的最佳策略，则结果q对选手A来说是合理的，具有合理稳定性，记为“r”。

（2）相继稳定如果对一个结果q来说，选手A的所有单方面改进都会由于选手B所采取的可靠行动而导致一个还不如不改动的结果（所谓可靠行动是指采取行动的选手可以得到比原来更好的结果），这种由于试图有所改进反而得到更差结果的情况，阻止了选手进行单方面的改进所造成的稳定性称为相继稳定，记为“s”。

古巴导弹危机的案例分析（3）不稳定当选手A没有可靠行动来阻止选手B在结果q下的全部单方面改进时，则称结果q对选手B是不稳定的（即还有可能再得到改进），记为“u”。

（4）同时稳定如果两个选手同时从对他们都不稳定的一个结果q出发而改变策略的话，可能会导致一个对他们中的一个或两个都不利的结果，也就是可能受到同时制裁，这时，称结果q是同时稳定的，在“u”上再加一个“/”，这种情形并不普遍，但进行稳定性分析时仍是要考虑的。

古巴导弹危机的案例分析（8）结束如果一个结果对所有选手来说是稳定的，即具有上述三种稳定性之一，则称该结果为一个均衡，它构成了冲突的一个可能解。

在有两个选手A，B的冲突中，对选手A的结果q的稳定性分析可按以下步骤进行：

（1）选手A的结果q有无单方面改进是

（2）对选手A的单方面改进，选手B是否有单方面改进是是是（3）选手B的所有单方面改进对A来说是否比q更好否（4）除了q,选手是否还有单方面改进否否否（7）q对选手A是不稳定的（5）q对选手A是相继稳定的（6）q对选手A是合理的考虑是否进行同时稳定性的检验古巴导弹危机的案例分析3.古巴导弹危机的分析结论该冲突有两个均衡：

结果4和6结果6对苏联是合理的，对美国是相继稳定的，因此它很可能就是冲突的结局。

冲突分析中选手的偏好不需要具有传递性，而且偏好序列也不要求严格有序，允许有同等的偏好；对偏好程度也不必量化，只要求能给出顺序比较。

再有，只有当一个选手的行动会导致对其自身有利的结果时，他才会考虑制裁另一个对手。

这些主要特点都使得冲突分析比经典的对策论、偏对策等更切合实际，更能灵活地适应各种环境，从而更具有优越性。