8运筹学基础第四章对策论2

运筹学基础1第四章对策论矩阵对策的数学模型矩阵对策的解矩阵对策的混合策略矩阵对策的基本定理运筹学基础2第四章对策论矩阵对策的数学模型矩阵对策的解矩阵对策的混合策略矩阵对策的基本定理运筹学基础34.1矩阵对策的数学模型1﹒二人有限零和对策：是指有两个参加对策的局中人，每个局中人都只有有限个策略可供选择，在任一局势下，两个局中人的赢得之和总等于零。2﹒矩阵对策：就是二人有限零和对策。3﹒矩阵对策模型：设Ⅰ﹑Ⅱ分别表示两个局中人，且它们的纯策略集分别为S1={α1,α2,…,αm}和S2={β1,β2,…,βn}。记局中人Ⅰ对任一纯局势(αi,βj)的赢得值为aij,并称a11a12…a1n..….am1am2…amnA＝为局中人Ⅰ的赢得矩阵。由于假定对策为零和,所以局中人Ⅱ的赢得矩阵为﹣A。运筹学基础44.1矩阵对策的数学模型当局中人Ⅰ﹑Ⅱ和策略集S1﹑S2及局中人Ⅰ的赢得矩阵A确定后，一个矩阵对策就确定了。通常，将矩阵对策记成G={Ⅰ,Ⅱ;S1,S2;A}或G={S1,S2;A}。3﹒矩阵对策模型：设Ⅰ﹑Ⅱ分别表示两个局中人，且它们的纯策略集分别为S1={α1,α2,…,αm}和S2={β1,β2,…,βn}。记局中人Ⅰ对任一纯局势(αi,βj)的赢得值为aij,并称a11a12…a1n..….am1am2…amnA＝为局中人Ⅰ的赢得矩阵。由于假定对策为零和,所以局中人Ⅱ的赢得矩阵为﹣A。运筹学基础54.1矩阵对策的数学模型4﹒局中人如何选取对自己最有利的纯策略？①局中人的“理智行为”：双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最小，从各自可能出现的最不利的情形中选择一种最为有利的情形作为决策的依据。②选择原则：局中人Ⅰ按最大最小原则，局中人Ⅱ按最小最大原则。即局中人Ⅰ从所有最小的赢得中选择最大的赢得的策略，局中人Ⅱ从所有最大的损失中选择最小的损失的策略。运筹学基础6例1设有一矩阵G={S1,S2;A}，其中S1={α1,α2,α2,α4}和S2={β1,β2,β3}局中人Ⅰ的赢得矩阵为﹣61﹣83249﹣2﹣10A=﹣306求出局中人Ⅰ﹑Ⅱ的最优策略。解：根据选择的原则，分析局中人的选择策略⑴局中人Ⅰ的策略：纯策略α1,α2,α3,α4可能带来的最小赢得分别﹣8，2，﹣10，﹣3所以，最小赢得中最大的值为2。因此局中人Ⅰ的策略应为α2。⑵局中人Ⅱ的策略：纯策略β1,β2,β3可能带来的最大损失分别9，2，6。所以，最大损失中最小的值为2。因此局中人Ⅱ的策略应为β2。总之，局中人Ⅰ﹑Ⅱ的最优纯策略分别为α2，β2。运筹学基础7第四章对策论矩阵对策的数学模型矩阵对策的解矩阵对策的混合策略矩阵对策的基本定理运筹学基础84.2矩阵对策的解定义1设G={S1,S2;A}为矩阵对策,其中S1={α1,α2,…,αm}，S2={β1,β2,…,βn}，A=(aij)m×n。若等式成立，记VG=ai*j*。则称VG为对策G的值，称上述等式成立的纯局势(αi*,βj*)为G在纯策略下的解(或平衡局势)，αi*与βj*分别称为局中人Ⅰ、Ⅱ的最优纯策略。根据定义1可知，例1中(α2,β2)是在纯策略下的解。对策值VG=a22=2，i*=2，j*=2。**maxminminmaxijijijjjiiaaa运筹学基础9所以又因所以又因为，对任给i,j有所以于是(1.1)(1.2)由(1,1,)和(1.2）有且VG=ai*j*。定理1矩阵对策G={S1,S2;A}在纯策略意义下有解的充要条件是:存在纯局势(αi*,βj*)使得对一切i=1,2,…,m,j=1,2,…,n,均有aij*≤ai*j*≤ai*j。证：充分条件因为对任意i，j均有aij*≤ai*j*≤ai*j****maxminijijijjiaaa*minmaxmaxijijjiiaa*minmaxminijijjjiaa**minmaxmaxminijijijjjiiaaaminmaxijijijjiaaamaxminmaxijijjiiaamaxminminmaxijijjjiiaa**minmaxmaxminijijijjjiiaaa运筹学基础104.2矩阵对策的解必要性设(αi*,βj*)是在纯策略意义下的解，则于是有显然有因此对任意i，j有aij*≤ai*j*≤ai*j证毕。定理的直观解释：如果ai*j*既是矩阵A=(aij)m×n中第i*行的最小值，又是第j*列的最大值，则ai*j*是对策的值，且(αi*,βj*)是在纯策略意义下的解。定理的对策意义：一个平衡局势(αi*,βj*)具有这样的性质，当局中人Ⅰ选择了纯策略αi*后，局中人Ⅱ为了其所失最小，只能选择βj*，否则就可能失去更多；反之，当局中人Ⅱ选择了纯策略βj*后，局中人Ⅰ为了得到最大的赢得，只能选择αi*，否则就会赢得更少。双方在局势(αi*,βj*)下达到一个平衡状态。**minmaxmaxminijijijjjiiaaa****maxminijijijjiaaa**maxijijiaa**minijijjaa运筹学基础114.2矩阵对策的解定理1的等价命题：矩阵对策G在纯策略意义下有解，且VG=ai*j*的充要条件是：ai*j*是矩阵A的一个鞍点(也称为对策的鞍点)。定理1的一个等价命题：定义2设f(x,y)为一个定义在x∈A,y∈B上的实值函数，如果存在x*∈A,y*∈B,使得对一切x∈A,y∈B，有f(x,y*)≤f(x*,y*)≤f(x*,y),则称(x*,y*)为函数f(x,y)的一个鞍点。运筹学基础124.2矩阵对策的解例2设有一矩阵G={S1，S2；A}，其中S1={α1,α2,α2,α4}和S2={β1,β2,β3,β4}局中人Ⅰ的赢得矩阵为6565142﹣18575A=0262求出局中人Ⅰ﹑Ⅱ的最优策略。解：计算列的最大和行的最小6565142﹣18575α1α2α2α40262β1β2β3β4minmax5﹣1508575其中i*=1,3j*=2,4故(α1,β2),(α1,β4),(α3,β2),(α3,β4)都是对策解，且VG=5**maxminminmax5ijijijjjiiaaa运筹学基础134.2矩阵对策的解性质1无差别性即若,是对策G的两个解，则证：因,是对策G的两个解。所以1122maxminminmaxijijijijjjiiaaaa11,ij22,ij1122ijijaa11,ij22,ij运筹学基础144.2矩阵对策的解性质2可交换性即若,是对策G的两个解，则,也是解。证：因为所以于是有因此,也是解。11,ij22,ij12,ij21,ij1122maxminminmaxijijijijjjiiaaaa221211122minijijijijijjaaaaa112121122minijijijijijjaaaaa12211122ijijijijaaaa12,ij21,ij运筹学基础154.2矩阵对策的解例4某单位采购员在秋天要决定冬季取暖用煤的贮存量问题。已知在正常的冬季气温条件下要消耗15吨煤，在较暖与较冷的气候条件下要消耗10吨和20吨。假定冬季时的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为10元、15元和20元，又设秋季时煤价为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋季贮煤多少吨能使单位的支出最少？分析：这一贮量问题可以看成是一个对策问题，两个局中人：Ⅰ是采购员﹑Ⅱ是大自然运筹学基础164.2矩阵对策的解这一贮量问题可以看成是一个对策问题，两个局中人：Ⅰ是采购员﹑Ⅱ是大自然－100－175－300－150－150－250－200－200－200α1(10吨)α2(15吨)α3(20吨)β1(较暖)β2(正常)β3(较冷)－300－250－200minmax－100－150－200故对策的解为(α3,β3)，即秋季贮煤20吨合理。33maxminminmax200ijijjjiiaaa运筹学基础174.2矩阵对策的解然而，一般情形不总是如此，实际中出现的更多情形是v1v2这样根据定义1,对策不存在纯策略意义下的解。由前面的讨论可知，对矩阵策略G={S1，S2；A}来说，局中人Ⅰ有把握的至少赢得是局中人Ⅱ有把握的至多损失是当v1＝v2时，矩阵对策G存在纯策略意义下的解，且VG＝v1＝v21maxminijjiva2minmaxijjiva运筹学基础184.2矩阵对策的解例如对于赢得矩阵为3654A=的对策来说v2＝a21＝54＝v1于是，当双方各根据从最不利情形中选取最有利的原则选择纯策略时，应分别选取α2和β1,此时局中人Ⅰ将赢得5,比其预期赢得4还多，原因就在于局中人Ⅱ选择了β1，使他当对手多得了原来不该得的赢得，故β1对局中人Ⅱ来说并不是最优的。1maxmin4*2ijjivai2minmax5*1ijjivaj运筹学基础194.2矩阵对策的解3654A=v2＝54＝v1ⅠⅡα2β1局中人策略赢得值5－5大于预期赢得值4α1β2策略赢得值6－6β1对局中人Ⅱ来说并不是最优的β1α2策略运筹学基础204.2矩阵对策的解这样时局中人Ⅰ出α1和α2的可能性以及局中人Ⅱ出β1和β2的可能性都不能排除。对两个局中人来说，不存在一个双方均可接受的平衡局势，或者说当v1v2时，矩阵对策G不存在纯策略意义下的解。在这种情况下，一个比较自然且合乎实际的想法是：既然各局中人没有最优纯策略可出，是否可以给出一个选取不同策略的概率分布。如上例中，局中人Ⅰ可以制定如下一种策略：分别以概率1/4和3/4选取纯策略α1和α2这种策略是局中人Ⅰ当策略集{α1,α2}上的一个概率分布，称之为混合策略。运筹学基础21第四章对策论矩阵对策的数学模型矩阵对策的解矩阵对策的混合策略矩阵对策的基本定理运筹学基础224.3矩阵对策的混合策略定义3设G={S1，S2；A}为矩阵对策，其中S1={α1,α2,…,αm}，S2={β1,β2,…,βn}，A=（aij）m×n。记则S1*和S2*分别称局中人Ⅰ和Ⅱ的混合策略集（或策略集）；x∈S1*，y∈S2*分别称为局中人Ⅰ和Ⅱ的混合策略；对x∈S1*，y∈S2*，称(x,y)为一个混合局势(或局势),局中人Ⅰ的赢得函数记成这样得到的一个新的对策记成G*={S1*,S2*,E},称G*为对策G的混合扩充。1﹑混合策略的定义*110,1,2,,,1mmiiiSxEximx*210,1,2,,,1nnjjjSyEyiny11,mnTijijijExyxAyaxy运筹学基础232﹒纯策略与混合策略的关系①纯策略是混合策略的特例。局中人Ⅰ的纯策略αk等价于混合策略x=(x1﹐x2﹐…﹐xm)T∈S1*,其中当i=k时，xi=1，当i≠k时，xi=0。②混合策略x=(x1﹐x2﹐…﹐xm)T∈S1*,可设想成当两个局中人多次重复进行对策G时，局中人Ⅰ分别采取纯策略α1,α2,…,αm的频率。3﹒矩阵对策G在混合策略意义下解的定义局中人Ⅰ赢得的期望值至少局中人Ⅱ损失的期望值至多**211maxmin,2.1ySxSvExy**212minmax,2.2ySxSvExy运筹学基础244.3矩阵对策的混合策略定义4﹒设G*={S1*,S2*;E}是矩阵对策G={S1,S2;A}的混合扩充，如果记其值为VG。则称VG为G*的值，称满足上述等式的混合局势(x*,y*)为G在混合策略意义下的解(或简称解)，x*和y*分别称为局中人Ⅰ和Ⅱ的最优混合策略(或简称最优解)。约定：对G={S1,S2;A}及其混合扩充G*={S1*,S2*;E}一般不加区别。通常都用G={S1,S2;A