《线性规划数学模型 p29》由会员分享，可在线阅读，更多相关《线性规划数学模型 p29（29页珍藏版）》请在金锄头文库上搜索。
1、 引例囚徒困境：甲、乙两个人一起携枪准备作案，被警察发现抓了起来。如果两个人都不坦白，警察会以非法携带枪支罪而将二人各判1年；如果其中一人招供而另一人不招，坦白者作为证人将不会被起诉，另一人将会被重判15年；如果两人都招供，则两人都会因罪名各判10年。这两个囚犯该怎么办？斗鸡博弈：两只斗鸡遇到一起，每只斗鸡都有两个行动选择：一是退下来，一是进攻。如果一方退下来，而对方没有退下来，对方获得胜利，这只公鸡则很丢面子；如果对方也退下来，则双方打个平手；如果自己没退下来，而对方退下来，自己则胜利，对方则失败；如果两只公鸡都前进，那么则两败俱伤。这两只公鸡该怎么办？引例在社会生活中，经常碰到各种各样具有
2、竞争或利益相对抗的活动，如下棋、打扑克、为争夺市场开展的广告战、军事斗争中双方兵力的对垒等，竞争的各方总是希望击败对手，取得尽可能好的结果。竞争各方都想用自己最好的战术去取胜，这就是对策现象。对策现象实际上是一类特殊的决策，在不确定型的决策分析中，决策者的对手是“大自然”，它对决策者的各种策略不产生反应，更没有报复行为。但在对策现象中，代替“大自然”的是有理智的人，因而任何一方做出决定时都必须充分考虑其他对手可能作出的反应。我国历史上齐王和田忌赛马的故事，生动的说明研究对策问题的意义。产生与发展 1944年，冯诺依曼与曼彻斯特发表了题为对策论和经济行为。 50年代是对策论发展的鼎盛时期，纳什和
3、夏普利等提出了讨价还价模型和合作对策的“核”的概念。同时，非合作对策也开始创立。 纳什于1950和1951年发表了两篇关于非合作对策的文章，图克于1950年定义了“囚徒困境”问题。 60年代，泽尔腾(1965)引入动态分析，提出“精练纳什均衡”概念。海萨尼(1967-1968)则把不完全信息引入对策论的研究。对策的基本要素局中人：在一个对策行为中，有权决定自己行动方案的对策参加者。它可是一个人，也可以是一个集团局中人必须是有决策权的主体，而不是参谋或从属人员局中人可以有两方，也可以有多方当存在多方的情况下，局中人之间可以有结盟和不结盟之分对策的基本要素策略：在一局对策中，把局中人的一个可行方案
4、称为它的一个策略，把局中人的策略全体叫做策略集。这个方案必须是一个独立的完整的行动，而不能是若干相关行动中的某一步；一个局中人可以拥有多个策略；一个局中人所拥有的策略的总和构成该局中人的策略集。对策的基本要素局势：当每个局中人从自己的策略集中选择了一个策略组 成的策略组就称为一个局势。 支付(赢得)：局势出现后，对策的结果也就确定了，对任 一局势，任一局中人都有一个支付值。显然，支付是局势 的函数，该函数称为支付函数或赢得函数。当各局中人得失的总和为零时，称这类对策为零和对 策，否则称为非零和对策。零和对策中存在两个局中人，其中一个局中人的支出 或损失恰好等于另一局中人的收入或赢得。二人零和对
5、策双方的得失用矩阵形式表示，通常称为 支付矩阵，二人零和对策也被习惯地称为矩阵对策。对策问题举例市场购买力竞争问题销售竞争问题费用分摊问题拍卖问题矩阵对策数学模型矩阵对策就是二人有限零和对策，指的是参加对策的局中人只有两方，每个局中人都只有有限个策略可供选择。在任一局势下，两个局中人的赢得之和总是零，即一方局中人的收入总等于另一方的支付，这表明双方的利益是激烈对抗的。用甲、乙表示局中人双方。假设局中人甲有m个策略(纯策略)，分别以1，2， m表示，局中人乙有n个策略(纯策略) ，分别以表1，2 ， n示，则局中人甲乙的策略集分别为：S甲=1，2，mS乙=1，2 ， ，n 矩阵对策数学模型当局中
6、人甲选定策略m和局中人乙选定策略n后，就形成了一个纯局势(i，j)。对任一纯局势(i，j)，记局中人甲的赢得值为aij ，并称为局中人甲的赢得矩阵(或为局中人乙的支付矩阵)。当局中人甲、乙和策略集S甲、 S乙及局中人的赢得矩阵A确定后，一个矩阵对策也就给定了。通常将一个矩阵对策记成：G=甲，乙； S甲， S乙；A或G=S甲， S乙；A=mnmmnnaaaaaaaaaALMLMMLL212222111211矩阵对策数学模型齐王赛马中齐王的赢得如下表田忌策略 齐王策略1 (上,中,下)2 (上,下,中)3 (中,上, 下)4 (中,下,上)5 (下,中,上)6 (下,上,中) 1(上,中,下)31
7、111-1 2(上,下,中)1311-11 3 (中,上, 下)1-13111 4 (中,下,上)-111311 5 (下,中,上)11-1131 6 (下,上,中)111-113-=311111131111113111111311111131111113A矩阵对策的解与对策值设有一矩阵对策G=S甲，S乙；A，其中S甲=1，2，3，4， S乙=1 ， 2 ， 3 -=6031019423816A矩阵对策的解与对策值1.求对策问题的解是建立在以下假设基础上每个局中人对双方拥有的全部策略及当各自采取某一策略时的相互得失有充分了解；对策的双方是理智的，他们参与对策的目的是力图扩大自己的收益，因而总是
8、采取对自己有利的策略；双方在相互保密的情况下选择自己的策略，并不允许存在任何协议。矩阵对策的解与对策值2.对策问题中，任何一方对对方在下次行动中准备采取的策略可以说是一无所知，双方处于完全对抗的环境中，因而各自都采取保守的态度，从最坏处着眼，并力争较好的结局。3.对策问题的解：对策双方遵循的对局中人A是最大最小准则，对局中人B则是最小最大准则，相应于这种准则下的对策双方各自采取的策略，称为对策问题的解。4.对策值：双方采取上述策略，连续重复进行对策，其输赢的平均值称为相应对策问题的对策值，通常用v表示。最大最小和最小最大准则局中人A策略有:a1,a2,am,局中人B策略有:b1,b2,bn。当
9、A采取策略ai(i=1,2,m)，而B采取策略bj(j=1,2,n)时，A的赢得(或B的损失)值为 cij 。b1b2bna1c11c12c1na2c21c22c2namcm1cm2cmn最大最小和最小最大准则1.最大最小准则:当A依据最大最小准则选择策略时，他总考虑不管选哪一个策略都将得到最坏结局，即选择策略ai时，得到的收入为再从以上各个最坏结局中找出一个最好的ijjcMinajiijjiVccMinMax=112.最小最大准则:当B依据最小最大准则选择策略时，他总考虑不管选哪一个策略都将得到最坏结局，即选择策略bj时，付出的支出为ijicMax 再从以上各个最坏结局中找出一个最好的bji
10、ijijVccMaxMin=22baVVV具有鞍点的对策鞍点：在矩阵对策中，若有ci1j2=ci2j2=cij时，则cij的值既是在同行中最小又是同列中的最大的，就像一个马鞍的骑坐点所处的位置，故称为鞍点。具有鞍点的对策：如果对策问题具有鞍点，称相应对策为具有鞍点的对策。 定义1：设G=S甲，S乙；A为矩阵对策，其中S甲=1，2，m， S乙=1 ，2，n ，A=(aij) mn。若等式*maxminminmaxjiijijijjiaaa=成立，记VG=ai*j*。则称VG为对策G的值，称使上式成立的纯局势(i*, j*)为G在纯策略下的解(或平衡局势)， i*和 j*分别称为局中人甲乙的最优纯
11、策略。矩阵对策数学模型例6-1：求解矩阵对策G=S甲，S乙；A，其中-=5033116423817A-3-32-85216ijiamax50-34-3-11634232-81-71321ijjamin矩阵对策数学模型定理1：矩阵对策G=S甲，S乙；A在纯策略意义下有解的充分必要条件是存在纯局势(i*, j*)，使得对一切i=1,2, ,m， j=1,2, ,n均有jijiijaaa*定义2：设f (x，y)为一个定义在xA及yB上的实值函数，如果存在x*A， y * B，使得对一切xA及yB有：),(),(),(*yxfyxfyxf则称 (x*，y*)为函数的一个鞍点。矩阵对策的混合策略 =4
12、563A12* 1451, 5maxmin22, 4minmaxvavjaviavijijijijji=这时双方若仍使用纯策略，就会出现不稳定状态.出现双方都不能连续不变地使用某种纯策略，都必须考虑如何随机使用自己的策略，使对方捉摸不到自己使用何种策略。这就是使用混合策略的对策。矩阵对策的混合策略定义3：矩阵对策G=S甲，S乙；A，其中S甲=1，2，m， S乙=1 ，2，n ，A=(aij) mn。 =miiimxmixExS1* 甲1,2, 1,0L =njjjnynjyEyS 1, 2 , 1, 0* 乙L则S1*和S2*分别称为局中人甲和乙的混合策略集；xS甲*和yS乙*分 别称为局中人
13、甲和乙的混合策略；对xS甲*，yS乙*，称(x，y)为 一个混合局势，局中人甲的赢得函数记成 =ijjiijTyxaAyxyxE),(这样得到的新的对策记为G*=S甲*,S2*,E,称G*为对策G的混合扩充。矩阵对策的混合策略当局中人甲采取混合策略x时，他只能希望获得(最不利的情形)因此居中人甲应选取xS1*,使得上式取极大值(最不利当中的最有利 情形)，即局中人甲可保证自己的赢得期望值不少于同样局中人乙可保证自己的赢得期望值不多于),(* 2yxEMin Sy),(* 2* 11yxEMinMaxv SySx=),(* 1* 22yxEMaxMinv SxSy=),(),(* 2* 1yxE
14、MinyxEMinMax ySySx= ),(),(* 1* 2yxEMaxyxEMaxMin xSxSy= 2*),(),(),(vyxEMaxyxEyxEMinv xy=矩阵对策的混合策略定义4：设G*=S甲*，S乙*；A是矩阵对策G=S甲，S乙；A 的混合扩充，若定理2：矩阵对策G=S甲，S乙；A在混合策略意义下有解的 充分必要条件是存在x* S甲*和y* S乙*，使(x *, y * )为函数 E(x，y)的一个鞍点，即：记其值为VG。则VG称为对策G*的值，称使上式成立的混合局势(x *, y *)为G在混合策略意义下的解， x *和 y *分别称为局中人甲和乙的最优混合策略。),(
15、),(* 1* 2* 2* 1yxEMaxMinyxEMinMax SxSySySx=),(),(),(*yxEyxEyxE22对策的公式法22对策是指局中人甲的赢得矩阵为22阶的，即： =22211211 aaaaA最优混合策略可通过下列方程求得：=+=+=+=+=+=+1)2( 1) 1 (2122212121211121222112221111yyvyayavyayaxxvxaxavxaxa上述方程组一定有严格非负解：)()()()()()()()()()(2112221121122211211222112111* 2 211222111222* 1211222111211* 2 211222112122* 1aaaaaaaaVaaaaaayaaaaaayaaaaaaxaaaaaaxG+-+-=+-+-=+-+-=+-+-=+-+-=2n或m2对策的图解法 =4563A
