《对策论习题课》PPT课件.ppt

,对策论习题课,？,？,？,齐王赛马 囚犯两难问题 俾斯麦海的海空对抗,1 案例,案例：齐王赛马 战国时期，一天齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次负者付给胜者1000金。已知同等级的马，田忌的马不如齐王的马;而如果田忌的马比齐王的马高一等级，则田忌的马可取胜。田忌在好友、著名的军事谋略家孙膑的指导下，作出以下安排： 齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得1000金。,表14-1 齐王赛马中齐王的赢得表,齐王赢二次，输一次，赢得值为2 - 1 = 1,表14-1 齐王赛马中齐王的赢得表,齐王赢一次，输二次，赢得值为 1 - 2 = -1,齐王赛马中齐王的赢得矩阵为：,案例：囚犯两难问题 设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干的，则每人各判刑5年；如果两人都不承认，则由于证据不足，两人各判刑2年； 如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑9年。因此，对两个囚犯来说，面临着一个“承认”和“不承认”之间两个策略的选择的难题。,案例：俾斯麦海的海空对抗,1943年2月，第二次世界大战中的日本，在太平洋战区已经处于劣势。为扭转局势，日本统帅山本五十六大将统率下的一支舰队策划了一次军事行动： 由集结地南太平洋的新不列颠群岛的蜡包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。,当盟军获悉此情报后，盟军统帅麦克阿梭命令太平洋战区空军司令肯尼将军组织空中打击。,日本统帅山本五十六大将心里很明白： 在日本舰队穿过俾斯麦海的三天航行中，不可能躲开盟军的空中打击，他要策划的是尽可能减少损失。,日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划。,案例：俾斯麦海的海空对抗,自然条件对于双方 都是已知的。基本情况如下：从蜡包尔出发开往莱城的海上航线有南北两条。通过时间均为3天。,气象预报表明：未来3天中，北线阴雨，能见度差；而南线天气晴好，能见度好。,肯尼将军的轰炸机布置在南线的机场，侦察机全天候进行侦察，但有一定的搜索半径。,案例：俾斯麦海的海空对抗,经测算，双方均可得到如下估计：,局势1： 盟军的侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度差，盟军只能实施两天的轰炸。,局势2：盟军的侦察机重点搜索北线，日本舰队走南线。由于发现晚，尽管盟军的轰炸机群在南线，但有效轰炸也只有两天。,案例：俾斯麦海的海空对抗,局势3：盟军的侦察机重点搜索南线，而日本舰队走北线。由于发现晚、盟军的轰炸机群在南线，以及北线气候恶劣，故有效轰炸只有一天。,局势4：盟军的侦察机重点搜索南线，日本舰队也恰好走南线。此时日本舰队迅速被发现，盟军的轰炸机群所需航程很短，加上天气晴好，有效轰炸时间三天。,案例：俾斯麦海的海空对抗,这场海空遭遇与对抗一定会发生，双方的统帅如何决策呢？历史的实际情况是：局势1成为现实。肯尼将军命令盟军的侦察机重点搜索北线；而山本五十六大将命令日本舰队取道北线航行。由于气候恶劣，能见度差，盟军飞机在一天后发现了日本舰队，基地在南线的盟军轰炸机群远程航行，实施了两天的有效轰炸，重创了日本舰队，但未能全歼。,案例：俾斯麦海的海空对抗,例1 设有一矩阵对策G=S1,S2,A，其中 S1 = 1, 2, 3, 4 ， S2 = 1, 2, 3，,2 例题,例2 求解矩阵对策 G=S1,S2;A，其中,-8,2,-3,-3,16,2,5,解：根据赢得矩阵，有,G 的解为(2,2)， VG=2 , 2 与2分别是局中人I和II的最优纯策略。,例3 求解矩阵对策 G =S1, S2; A，其中 S1 = 1, 2, 3, 4， S2 = 1, 2, 3, 4 ， 赢得矩阵为,解: 在赢得表上计算为,1 2 3 4 min,5 -1 5 0,6 5 7 5,1 2 3 4 max,*,*,*,*,例4 某单位采购员在秋天要决定冬季取暖用煤的贮量问题。已知在正常的冬季气温条件下要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。假定冬季时的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为10元，15元和20元，又设秋季时煤价为每吨10元在没有关于当年冬季准确的气象预报的条件下，秋季贮煤多少吨能使单位的支出最少?,局中人I：采购员 三个策略：在秋天时买煤 10吨、 15吨、 20分别记为：1，2，3， 局中人II：大自然 三种策略：冬季出现 较暖、 正常、 较冷 分别记为：1，2，3，,局中人I的赢得矩阵,1(10吨) 2(15吨) 3(20吨),1 2 3 (较暖) (正常) (较冷),不同策略下买煤的总费用：,(1，2): 1010 + 515=175,(1，1): 1010 = 100,(1，3): 1010 + 1020 =300,(2，1): 1510 = 150,(2，2): 1510 = 150,(2，3): 1510 + 520 = 250,(3，1): 2010 = 200,(3，2): 2010 = 200,(3，3): 2010 = 200,(10元) (15元) (20元) (10吨) (15吨) (20吨),解：该单位冬季取暖用煤实际费用(即秋季购煤时的用费、与冬季不够时再补购的费用总和)作为局中人I的赢得，得赢得矩阵如下：,1 2 3 (较暖) (正常) (较冷),1(10吨) 2(15吨) 3(20吨),-300 -250 -200,-100 -150 -200,min,max,*,*,*,*,故对策的解为(3, 3)，即秋季购煤20吨合理。,优超原则,优超原则,例5：求解下列矩阵对策。,解：利用优超原则化简,得新的赢得矩阵,解新的赢得矩阵，对于A2，无鞍点，即x30, x40，y1 0, y2 0，应用定理6得下列求方程组,得新的赢得矩阵,求得解为,原矩阵对策的解为,例6 求解矩阵对策GS1,S2,A 其中,例7 求解矩阵对策GS1,S2,A 其中,设局中人I的混合策略为(x, 1-x)， x0,1 过数轴上坐标为0和1的两点 分别做两条垂线I-I和II-II，垂线上 点的纵坐标值分别表示局中人I 采取 纯策略1和2时，局中人II采取各纯 策略时的赢得值。,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,当局中人I选择每一策略(x，1-x)时，他的最少可能的收入为由局中人II选择1、2、3时所确定的三条直线 2x十7(1-x)=V， 3x十5(1-x)=V， 11x十2(1-x)=V 在 x 处的纵坐标中之最小者。即如折线 B1BB2B3 所示。,x1,x2,x3,x4,x5,x6,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,3,2,1,局中人I的最优选择就是确定x使他的收入尽可能地多，按最小最大原则应选择 x* OA、而AB即为对策值VG。,A,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,3,2,1,解过B点的两条线段和3所确定的方程： 3x十5(1-x)=V 11x十2(1-x)=V 得 x = 311， VG = 4911， 所以，局中人I的最优策略为 x*(311，811)T。,A,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,3,2,1,另外， E(x*,1) = 23/11+78/11 = 62/11 49/11 = VG E(x*,2) = E(x*,3) = VG 由定理6知，必有y1* = 0 局中人II的最优混合策略只由2和3组成。,A,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,3,2,1,局中人II的最优混合策 略只由2和3组成。解下列 方程组： 3y2+11y3 = 49/11， 5y2+ 2y3 = 49/11 y2+y3 = 1 解得 y2 = 911 y3 = 211 所以，局中人II的最优策略 为 y*(911，211 ),A,2,11,3,1,0,7,5,2,3,2,1,II,II,I,I,图14-2 2n对策的图解法,2x+7(1-x)=V,3x+5(1-x)=V,11x+2(1-x)=V,3,2,1,A,VG,=VG,=VG,=VG,=VG,= 0,例8 求解矩阵对策GS1,S2,A 其中,设局中人II的混合策略为(y,1-y) y0,1, 过数轴上坐标为0和1的两点 分别做两条垂线I-I和II-II，垂线上点的纵坐标值分别表示局中人I采取纯策略1、2和3时，局中人II采取各纯策略时的支付值。,2,11,6,1,0,7,6,2,1,II,II,I,I,2y+7(1-y)=V,图14-3 m 2对策的图解法, 3, 2,6y+6(1-y)=V,11y+2(1-y)=V,当局中人II选择每一策略(y，1-y)时，他的最大可能的损失为由局中人I选择1、2、3时所确定的三条直线 2y+7(1-y)=V， 6y+6(1-y)=V， 11y+2(1-y)=V 在 y 处的纵坐标中之最大者。如图所示。,2,11,6,1,0,7,6,2,1,II,II,I,I,2y+7(1-y)=V,图14-3 m 2对策的图解法, 3, 2,6y+6(1-y)=V,11y+2(1-y)=V,2,1,局中人II的最优选择就是确定 y 使他的损失尽可能地少，按最大最小原则应选择 OA1 y* OA2 而A1B1与A2B2为对策值,A2,A1,2,11,6,1,0,7,6,2,1,II,II,I,I,2y+7(1-y)=V,图14-3 m 2对策的图解法, 3, 2,6y+6(1-y)=V,11y+2(1-y)=V,2,1,由方程： 2y十7(1-y)=6， 11y十2(1-y)=6， 解得 OA1 = 1/5， OA2 = 4/9， 所以，局中人II的最优策略为 ( y*, 1- y*)T 其中 1/5 y* 4/9。 而局中人I的最优策略为 (0,1,0)T，即为 2,A2,A1,例9 求解矩阵对策GS1,S2,A 其中,划 去 第 2 列,2/3第4列+ 1/3第1列 第2列,例9 求解矩阵对策GS1,S2,A 其中,解：利用优超原则划减赢得矩阵,例9 求解矩阵对策GS1,S2,A 其中,解：利用优超原则划减赢得矩阵,1,4,8/3,1,0,7,5,2,1,2,4,II,II,I,I,图14-4 2n对策的图解法,3,13/4,3/4,局中人I的最优混合策略为： x*(3/4，1/4)T 1 、2、 4两线的交点。,从图形中看出y3* = 0，局中人II的最优混合策略由 下列方程组解得： 4y1 + 3/8y2 + 2y4 = 13/4 y1 + 5y2 + 7y4 = 13/4 y1 + y2 + y4 = 1 满足上面方程的解有无穷多个故局中人II有无穷多个最优混合策略。,超优原则解法的缺陷,例10 求解矩阵对策“齐王赛马”,每个局中人选取每种策略都是可能的，假设齐王与田忌的的最优混合策略的所有分量大于0，即 x*0, y*0。求解下面两个线性方程组。,解 赢得矩阵为,解之得到 v = 1 xi = 1/6 i = 1,2, ,6 故齐王的最优混合策略为 x* = (1/6, 1/6, 1/6, 1/6, 1/6, l/6)T 对策的值(齐王的期望赢得)为VG1。,解之得到 v = 1 yi = 1/6 i = 1,2, ,6 故田忌的最优混合策略为 y* = (1/6, 1/6, 1/6, 1/6,1 /6, l/6)T 对策的值(齐王的期望赢得)为VG1。,故齐王和田忌的最优混合策略为 x* = (1/6, 1/6, 1/6,1 /6, 1/6, l/6)T y* = (1/6,1 /6, 1/6, 1/6, 1/6, l/6)T 对策的值(齐王的期望赢得)为VG1。,例11 某厂用三种不同的设备1、2、3加工三种不同的产品1、2、3，已知三种设备分别加工三种产品时，单位时间内创造的价值由下表给出。 出现负值是由于设备的消耗大于创造出的价值。在上述条件下，求合理的加工方案。,解：此问题可看成是一个矩阵对策问题并易知没有鞍点。设采用设备1、2、3 的概率分别为(x1, x2, x3)T，产品1、2、3接受加工的概率分为( y1, y2, y3 )T。,为简化求 解计算，由定 理 7，赢得矩 阵化简为：,为简化求 解计算，由定 理 7，赢得矩 阵化简为：,解 为,求 解 方 程 组,根 据 试 算 求 解,解 为,根 据 试 算 求 解,解 为,解 为,原矩 阵对 策的 解为,例：12 用线性规划的方法求解下列矩阵对策。,解：赢得矩阵为,解：赢得矩阵为,求解矩阵对策时，首先判 断是否具有鞍点，鞍点不存在 ，利用超优原则及定理7、8提 供的方法将原对策的赢得矩阵 进行化简，然后再利用本节的 各种方法进行求解。,矩阵对策解的求解,在W城的冰箱市场上，以往的市场份额由本市生产的A牌冰箱占有绝大部分。本年初，一个全国知名的B牌冰箱进入W城的市场。在这场竞争中假设双方考虑可采用的市场策略均为三种：广告、降价、完善售后服务，且双方用于营销的资金相同。根据市场预测，A的市场占有率为：,广告1 降价2 服务3 广 告1 0.60 0.62 0.65 降价2 0.75 0.70 0.72 服务3 0.73 0.76 0.78 试确定双方的最优策略。,例13 营销策略的确定,广告1 降价2 服务3 广 告1 0.60 0.62 0.65 降价2 0.75 0.70 0.72 服务3 0.73 0.76 0.78,利用公式可得： X*= （0，3/8，5/8） （A） Y*= （3/4，1/4，0） （B） 对策的值为 V G*= 0 . 74