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

《《对策论习题课》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《对策论习题课》PPT课件.ppt（66页珍藏版）》请在三一办公上搜索。

1、,对策论习题课,？,？,？,齐王赛马 囚犯两难问题 俾斯麦海的海空对抗,1 案例,案例：齐王赛马 战国时期，一天齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次负者付给胜者1000金。已知同等级的马，田忌的马不如齐王的马;而如果田忌的马比齐王的马高一等级，则田忌的马可取胜。田忌在好友、著名的军事谋略家孙膑的指导下，作出以下安排：齐王 上 中 下 田忌 下 上 中最终净胜一局，赢得1000金。,表14-1 齐王赛马中齐王的赢得表,齐王赢二次，输一次，赢得值为2-1=1,表14-1 齐王赛马中齐王的赢得表,齐王赢一次，输二次，赢得值为 1-2=-1,齐王赛马中齐王的赢得矩阵为：,案

2、例：囚犯两难问题 设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干的，则每人各判刑5年；如果两人都不承认，则由于证据不足，两人各判刑2年；如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑9年。因此，对两个囚犯来说，面临着一个“承认”和“不承认”之间两个策略的选择的难题。,案例：俾斯麦海的海空对抗,1943年2月，第二次世界大战中的日本，在太平洋战区已经处于劣势。为扭转局势，日本统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地南太平洋的新不列颠群岛的蜡包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。,当盟军获悉此

3、情报后，盟军统帅麦克阿梭命令太平洋战区空军司令肯尼将军组织空中打击。,日本统帅山本五十六大将心里很明白：在日本舰队穿过俾斯麦海的三天航行中，不可能躲开盟军的空中打击，他要策划的是尽可能减少损失。,日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划。,案例：俾斯麦海的海空对抗,自然条件对于双方 都是已知的。基本情况如下：从蜡包尔出发开往莱城的海上航线有南北两条。通过时间均为3天。,气象预报表明：未来3天中，北线阴雨，能见度差；而南线天气晴好，能见度好。,肯尼将军的轰炸机布置在南线的机场，侦察机全天候进行侦察，但有一定的搜索半径。,案例：俾斯麦海的海空对抗,经测算，双方均可得到如下估计：,局

4、势1：盟军的侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度差，盟军只能实施两天的轰炸。,局势2：盟军的侦察机重点搜索北线，日本舰队走南线。由于发现晚，尽管盟军的轰炸机群在南线，但有效轰炸也只有两天。,案例：俾斯麦海的海空对抗,局势3：盟军的侦察机重点搜索南线，而日本舰队走北线。由于发现晚、盟军的轰炸机群在南线，以及北线气候恶劣，故有效轰炸只有一天。,局势4：盟军的侦察机重点搜索南线，日本舰队也恰好走南线。此时日本舰队迅速被发现，盟军的轰炸机群所需航程很短，加上天气晴好，有效轰炸时间三天。,案例：俾斯麦海的海空对抗,这场海空遭遇与对抗一定会发生，双方的统帅如何决策呢？历史的实际情

5、况是：局势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=

6、1,2,3,4，S2=1,2,3,4，赢得矩阵为,解:在赢得表上计算为,1 2 3 4 min,5-1 50,6 5 7 5,1234 max,*,*,*,*,例4 某单位采购员在秋天要决定冬季取暖用煤的贮量问题。已知在正常的冬季气温条件下要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。假定冬季时的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为10元，15元和20元，又设秋季时煤价为每吨10元在没有关于当年冬季准确的气象预报的条件下，秋季贮煤多少吨能使单位的支出最少?,局中人I：采购员 三个策略：在秋天时买煤 10吨、15吨、20分别记为：1，2，3，

7、局中人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吨),解：该单位冬季取暖用煤实际费用(即秋季购

8、煤时的用费、与冬季不够时再补购的费用总和)作为局中人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 其中,设局

9、中人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)时，他的最少可能的收

10、入为由局中人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对

11、策的图解法,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局中人

12、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

13、(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时所确定的三条直线

14、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)

15、=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

16、,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

17、,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，已知三种设备分别加工三种产品时，单位时间内创造的价值由下表给出。出现负值是由于设备的消耗大于创造出的价值

18、。在上述条件下，求合理的加工方案。,解：此问题可看成是一个矩阵对策问题并易知没有鞍点。设采用设备1、2、3 的概率分别为(x1,x2,x3)T，产品1、2、3接受加工的概率分为(y1,y2,y3)T。,为简化求 解计算，由定 理 7，赢得矩 阵化简为：,为简化求 解计算，由定 理 7，赢得矩 阵化简为：,解 为,求 解 方 程 组,根 据 试 算 求 解,解 为,根 据 试 算 求 解,解 为,解 为,原矩 阵对 策的 解为,例：12 用线性规划的方法求解下列矩阵对策。,解：赢得矩阵为,解：赢得矩阵为,求解矩阵对策时，首先判断是否具有鞍点，鞍点不存在，利用超优原则及定理7、8提供的方法将原对策

19、的赢得矩阵进行化简，然后再利用本节的各种方法进行求解。,矩阵对策解的求解,在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

20、 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.7425,1 22 0.75 0.70 3 0.73 0.76,由于无鞍点，故在纯策略意义下无解。但是对于A来说，1行元素小于 2行元素，即 2优超1，删除1行；同样道理。对于B来说，2列元素小于 3列元素，即 2优超3，删除3。,解：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,利用公式可得：X*=（0，3/8，5/8）（A）Y

21、*=（3/4，1/4，0）（B）对策的值为 V G*=0.7425,1 22 0.75 0.70 3 0.73 0.76,由于无鞍点，故在纯策略意义下无解。但是对于A来说，1行元素小于 2行元素，即 2优超1，删除1行；同样道理。对于B来说，2列元素小于 3列元素，即 2优超3，删除3。,解：A的赢得矩阵为,A的最优策略是将促销资金的3/8用于降低售价，5/8用于售后服务。B的最优策略是将促销资金的3/4用于广告，1/4用于降低售价。这样做的结果是A的市场占有率为 0.7425（74.25%）,例14 订货计划 某厂制造和销售一种新仪器，需要外购一种配件。现有三个厂生产这种配件，牌号为A，B，C。A配件每只10元，但有次品，装配的仪器也是次品，每台损失100元；B配件每只55元，也有次品，但装配的仪器出售后可在保修期内稍加修理就能使用，修理费55元；C配件每只118元，没有次品；问该厂应如何购置各种配件，使总费用（包括损失费和修理费）最少？,