决策与对策问题ppt课件.ppt

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

1、决策与对策,决策问题,西北大学数学系,西北大学数学系,决策：是人类活动的基本组成部分之一，几乎任何工作都离不开决策。凡是根据预定的目标做出的任何行动决定，都可称之为决策。决策问题：对于一个需要处理的事件，面临几种客观条件，又有几种方案可供选择， 这就构成一个决策问题。,一 、基本概念,西北大学数学系,状态：决策者所面临的每一种客观条件称之为一个自然状态，简称状态，也叫状态变量。决策：可供选择的行动方案，也叫决策变量。益损值：指采取某种行动方案在不同状态下所获得的报酬。,确定型决策问题，随机型决策问题，复杂过程的决策问题,西北大学数学系,确定型决策问题随机型决策问题复杂过程的决策问题,二、决策问

2、题的类型,确定型决策问题：决策者确切地知道将发生什么样的自然状态，从而可以在既定的自然状态下选择最佳方案的一类决策问题。,方法：穷举法，规划方法（如线性规划，动态规划等）,西北大学数学系,随机型决策问题：决策者所面临的的各种自然状态是随机出现的一类决策问题。,方法：风险型决策，非确定型决策,复杂系统的决策问题：同时受主观与客观因素影响的决策问题。,方法：层次分析法,风险型决策最大可能法，期望值决策法，树型决策法，效用分析法等。非确定型决策乐观法，悲观法，折衷法，等可能性法，后悔值法。,西北大学数学系,农作物种植问题,某地区种植业生产中，可供选择的农作物有水稻、小麦、大豆、燕麦等四种。该地区每年

3、可能发生的天气类型共有五种，即极旱年、旱年、平年、湿润年、极湿年。根据多年来的气候纪录资料和农业生产统计资料计算得到的各种天气类型发生的概率，以及在最佳投入-产出条件下，每一种天气类型所对应的各种农作物收益（元/亩）如表。请给该地区的生产经营者选择农作物的种植类型。,西北大学数学系,表1：不同天气类型所发生的概率及农作物 收益,西北大学数学系,最大可能法,选择最佳农作物类型是大豆。,西北大学数学系,风险型决策,期望值决策法：,选择最佳农作物类型是大豆。,西北大学数学系,结果结点,树型决策法,V,V1,V2,V3,V4,水稻,小麦,大豆,燕麦,0.1,0.2,0.1,0.2,0.4,100126

4、180200220,0.1,0.2,0.1,0.2,0.4,120176230170110,0.1,0.2,0.1,0.2,0.4,250210170120110,0.1,0.2,0.1,0.2,0.4,118130170190210,决策结点,状态结点,方案分枝,概率分枝,170,167,183,165,=,=,=,183,选择最佳农作物类型是大豆。,西北大学数学系,单级决策，多级决策。,西北大学数学系,注意：灵敏度分析,在求解风险型决策问题时灵敏度分析是重要的环节。,例：某捕鱼队面临下个星期是否出海捕鱼的选择。如果出海后仍是天气好，则可得到5000元的收益；如果出海后，天气变坏，则将损失2

5、000元；如果采取不出海，则无论天气好坏，都要承担1000元的损失费。已知下个星期天气好的概率为0.7，天气变坏的概率为0.3。应如何选择最佳方案？并讨论最佳方案是否具有稳定性。,树型决策法,V,V1,V2,0.7,0.3,0.7,0.3,2900,-1000,=,西北大学数学系,天气好,天气坏,天气好,天气坏,5000,-2000,-1000,-1000,出海,不出海,2900,出海捕鱼是最佳方案，其效益期望值为2900。,在风险决策问题中，各种状态出现的概率及相应于个方案的效益的大小均为预测或估计值，因此应该考虑到这些数据变化时是否影响最佳方案。根据数据在一定范围内的变动，讨论最佳方案是否

6、稳定，称为灵敏度分析。,状态出现的概率变化时,方案不变。,西北大学数学系,方案变化，选择不出海。,转折概率。,当天气好的概率大于1/7时，出海是最佳方案。,当 时，两方案具有相同的效益期望值。,所选方案稳定。,西北大学数学系,各个方案的效益值变化时,设在天气好的状况下出海取得的效益为 ，其余状态的效益值不变。,当大于 时，出海是最佳方案。,当 时，两方案具有相同的效益期望值。,所选方案稳定。,西北大学数学系,一般地说，如果最佳决策方案的稳定性较好，则其可靠性程度就较高，相反，若对某些给定数据稍加变动，则最佳方案必须重新选定，那么所选的方案就过于灵敏，可靠性较差。,西北大学数学系,乐观法（大中取

7、大）,选择最佳农作物类型是小麦。,西北大学数学系,非确定型决策,悲观法（小中取大）,选择最佳农作物类型是燕麦。,西北大学数学系,折衷法,选择最佳农作物类型是大豆。,西北大学数学系,等可能性法：,选择最佳农作物类型是小麦。,西北大学数学系,后悔值法：,1、求出每个状态下各个方案的最大收益值,西北大学数学系,2、求出每个状态下的各个方案的后悔值,西北大学数学系,3、求出每个方案的最大后悔值,西北大学数学系,4、求出每个方案的最大后悔值的最小后悔值,选择最佳农作物类型是大豆。,西北大学数学系,风险决策的进一步思考,为了降低风险决策带来的损失，采取分散风险的办法。,西北大学数学系,如：可按一定比例选种

8、水稻、小麦、大豆、燕麦的种植方案，可能降低风险，或是的收益达到比较满意的程度。,是否存在恰当的比例，使收益达到最大？这就是投资组合问题。见1998年A题。,练习：最佳投资问题,某地要新建一个工厂，以满足市场对某种产品的需求，有三个方案可供选择：V1：建大厂，需投资350万。据估计，产品销路好时，每年可获利100万元，销路差时，亏损25万元，服务期限10年。V2：建小厂，需投资145万。产品销路好时，每年可获利40万元，销路差时，可获利30万元，服务期限10年。V3：先建小厂，若销路好时，三年后扩建，需追加投资200万元。扩建后，每年可获利95万元，服务期限7年（扩建后的期限）。据市场预测，该厂

9、产品投产后10年内销路好的概率为0.7，销路不好的概率为0.3。试选定最佳决策方案，并对销路好坏的概率作灵敏度分析。,西北大学数学系,对策问题,西北大学数学系,一 问题的提出,对策论（game theory）又称博弈论，运筹学的一个分支，是关于两个或多个局中的人按一定规则处于竞争状态下的决策行为的数学理论。 对策论起源于关于室内游戏(象棋、扑克等)局中人的行为与得失的研究。 产生于上世纪三十年代。,西北大学数学系,1921年法国的包瑞尔首先做出对策论的研究。 美籍数学家冯诺伊曼在1928年提出的“最大最小原则”奠定了对策论的理论基础，特别是在1944年发表的对策论与经济行为一书，引起了广泛的注

10、意，对策论也由最初对于桥牌、棋艺的研究转到对经济、军事、心理等领域的广泛应用。 现在，对策论与线性规划、统计判决、管理科学、运筹学和军事计划等领域都有着密切关系。 对策论也是安全管理学的理论基础。现代化生产中的安全问题是极复杂的问题，运用对策论解决这些复杂的问题，提出新模型具有重要意义。,西北大学数学系,田忌赛马,西北大学数学系,第一次赛马,田 忌,齐威王,上 中 下,上 中 下,败,胜,田忌赛马,西北大学数学系,第二次赛马,田 忌,齐威王,上 中 下,上 中 下,败,胜,警察同时逮捕了两个人，逮捕的证据是他们持有大量的伪钞。在警察局里，他们被关在不同处。负责调查这一案件的检察官怀疑，他们不仅

11、持有大量的伪钞，而且还是伪钞的制造者，但是没有充分的证据，警察希望犯人能自己供认。,例子,警察对两名犯人分别进行审问。犯人知道：如果两个人都不承认是伪造者，则将以持有伪钞罪被判刑18个月；如果两个人都承认是伪造者，则被判刑3 年；如果只有一人供认，而另一人拒不承认，那么坦白者可以免刑，而隐瞒者将被判刑7年。 请分析两个犯人该怎么做？,把犯人A，B被判刑的几种可能列表如下,两犯人都希望受到最轻的处罚，但又担心对方的供认，最保险的办法是承认制造伪钞，这样可避免最坏的情况。检察官成功地获得了口供。,（1）局中人（players）：,二 基本要素,如犯人A和犯人B是局中人，警察不是。在象棋比赛中，参加

12、对弈的两位棋手就是两个局中人。在人与大自然作斗争时，人与大自然是两个局中人。局中人可以是一个人，也可以是代表共同利益的一个集团。,参加对策的每一方称为局中人。,（2）策略（strategies）：,全部策略构成策略集。,局中人A有m个策略（或称为纯策略），策略集,局中人B有n个策略，策略集,就构成一个纯局势。,和 中的策略可构成,个纯局势。,局中人能采取的可行方案称为策略。,对应于纯局势 ，A的赢得记为,(3)赢得矩阵（支付矩阵）(payoff matrix) ：,B的赢得记为,三 对策问题的分类,当纯局势 已确定时，A的赢得恰是B的所失，双方得失之和为零。这种对策称为零和对策。,在构造赢得矩

13、阵时，可略去,四 零和对策,在零和对策中，,有的赢得表没有明显的给出A的所得正是B的所失，但A、B双方的赢得数之和为一定数。,A与B赢得数之和为10,表中每个元素减去5为零和对策,把一个对策记为,最优策略与鞍点,设有对策 ，其中,局中人A采取策略 时，所应得的最坏的结果分别是：,对策双方在选择对策时受到对方的影响，为了稳妥，考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。,其中最好的结果是,最优策略为 。,局中人B采取策略 时，要考虑最大损失。B采取个各方案的最大损失为,B认为最优策略为 。,在这个对策中A的最小获得值恰是B的最大损失值，记为,称之为对策值。,称之为对策的鞍点。

14、,（1）设有矩阵对策 ，若,则 称为对策 G 的值。,（2）若纯局势,使得,则 称为对策G的鞍点。,对策矩阵中与 相对应的元素 ，称为矩阵的鞍点。,分别称为局中人A与B的最优策略。,（3）对策G的鞍点，称为纯策略中的稳定解。,引理,设有零和对策 ，记,则,定理1 一个零和对策有稳定解的充要条件是,1. 稳定解的存在性（极大极小值原理 ）,对策的稳定解可能不唯一。有下面性质：,五 基本定理及性质,对策 G 的解 ，那么,（1）无差别性：若 与 同为,（2）可交换性：若 与 是对策,G 的解 ，那么 与,也是G 的解 。,例1：设局中人I的赢得矩阵为,可见存在4个鞍点，(1,2), (1,4),

15、(3,2), (3,4) 最优值都是4 。,（不同的鞍点, 最优值相同）,这时，需考虑混合策略，即就是局中人为了防备对方识破自己的行动，按一定概率分布选择各纯策略。如 ，局中人A以,2. 混合局势及其存在性,的概率分别选取 记为,也称概率向量 为局中人A的策略,例,在纯策略意义下无解。,称为一个混合局势。,一般地,则定义局中人 A 的赢得函数的期望值为,设有矩阵对策,分别称为局中人A,B的混合策略。,分别称为局中人A,B的混合策略集。,如果存在概率向量,则称 (x*,y*)为混合局势的最优解。也称为函数 E 的鞍点。,即,定理2 是函数 的鞍点的充要条件为:,使得,，,定理 3 混合局势 是矩

16、阵对策G的解的充要条件是,分别是以下不等式组的解,定理 4 混合局势的最优解 的策略 必存在， 且分别是以下两个线性规划问题的解,，,注：实际上这两个线性规划问题是互为对偶的，每用对偶单纯性法求出第一个线性规划问题的解后就得到第二个问题的解。,六 举例,例1 A ，B 两方作战，A方要派出两架轰炸机 I 和轰炸B方的指挥部，轰炸机 I 在前面飞行，随其后。两个轰炸机中仅有一架装有炸弹，而另一架仅是护航。轰炸机飞至B方占领地区的上空，受到B方战斗机的阻击。当战斗机阻击在后面飞行的轰炸机时，战斗机仅受到的射击，战斗机被击中的概率为0.3，如果战斗机阻击轰炸机 I 时，那么它将同时受到两架轰炸机的射

17、击，战斗机被击中的概率为0.7。一旦战斗机没有被轰炸机击中，战斗机就以的0. 6的概率击毁A方的轰炸机。 现需要为A ，B 双方选择最优策略：对于A方，应选择哪一架轰炸机装载炸弹？ 对于B方，战斗机应如何阻击轰炸机？,分析,局中人 A ，B,A的策略集,B的策略集,对策矩阵A中的元素 表示A方采取策略 ，B方采取策略 时，A方能炸毁B方的指挥部的期望值，根据题意，计算得,对策矩阵,不存在鞍点，对策应采取混合策略，即,建模,由定理 4 求x*和y*使得,而 满足,y1,y2,o,0.82y1+y2=1,y1+0.58y2=1,1,1/0.82,1/0.58,1,P(7/8.74, 3/8.74)

18、,w=y1+y2,Max w = 10/8.74,图解法,西北大学数学系,E = 0.874,求解,结论,A应以0.7的概率使轰炸机I载有炸弹，取胜的可能性比较大，而B方采取的最优策略是以 0.7的概率阻击轰炸机I 。,图解法,0(A1),1(A2),a11,a12,a22,a21,B1,B1,B2,B2,N,p2,N点的纵坐标表示对策值,N点的横坐标表示p2值，即采取策略A2的概率。,例2 在棒球赛中击球手（局中人1）和投球手（局中人2）之间的较量可用如下击球手的赢得矩阵来表示,其中局中人1的策略集是猜测投球手投向（上区，中区，下区）， 而投球手的策略是投向（上区，中区，下区）数字表示击球手

19、在各种纯局势时打出本垒打的击球率。,可见本问题没有鞍点， 采用计算机编程计算求解,棒球赛中的策略,建模,由定理 4 求 x* 和 y* 使得,而 满足,答案是击球手注意上区概率为0，中区概率为0.8，下区概率为0.2。 投球手注意投向 上区概率为0.4， 中区概率为0，下区概率为0.6。 最优值E=0.24.,计算见以下程序：编写 LINGO 程序如下,sets:row/1.3/;col/1.3/:y;matrix(row,col):A;endsetsmax=sum(col:y);for(row(i):sum(col(j):A(i,j)*y(j)=1);data:A=0.4,0.2,0, 0.

20、3,0.4,0.2, 0,0.3, 0.4;enddata,编写 LINGO 程序如下,Objective value: 4.166667 Variable Value Reduced Cost Y( 1) 1.666667 0.000000 Y( 2) 0.000000 0.6666667 Y( 3) 2.500000 0.000000 Row Slack or Surplus Dual Price 1 4.166667 1.000000 2 0.3333333 0.000000 3 0.000000 3.333333 4 0.000000 0.8333333,运行的结果,七 进一步考虑的问

21、题,例3 现有一对策问题，双方获利情况见下表，试分 析这一问题。,分析：由于双方获利之和不为常数，无法化为零和对策问题。,假设双方考虑问题均较保守,A发现采用策略4时，至少可获利为4，从而采取这一策略。,B发现采用策略1时，至少可获利为2，从而采取这一策略。,此时，局势为（4，1），双方获利之和6。,从整体观点来分析，这一结果并非是最好的，因为总获利本来可以达到10。同时也不难看出，在这里依靠单方的努力不一定能收到良好的效果。,假如B也许会想在对方收益不变的情况下，采取策略2可获利为6。,A就会想，如果B采用策略2，那A肯定会选策略2，获利可增加到9，此时，B可能冒一无所获的风险。,上述过程可

22、无休止的进行下去。,明智的做法，双方互相配合，先取得总体上的最大利益，即使总获利为10 ，然后再按某一原则来“公平”地分享已经获得的最大利益，这样对双方均有利。,例3说明，总获利可以改变的对策问题是存在合作基础的对策问题。但存在一个关键问题：如何分享利益？如果不能达到一个双方都愿意接受的“公平”分配原则，合作仍然不可能实现。,合作对策中研究的主要问题：合理公平的分配原则！,我方布置三种武器A1，A2，A3，敌方有三架飞机B1，B2，B3 。我方目标是要击落飞机，敌方目的是要逃避打击。已知使用武器A1时，飞机 B1，B2，B3 被击落的概率分别为0.9,0.4,0.2,当使用武器A2时，飞机 B1，B2，B3 被击落的概率分别为0.3,0.6,0.8,当使用武器A3时，飞机 B1，B2，B3 被击落的概率分别为0.5,0.7,0.2。构造对策矩阵，并为双方选择最优策略。,八 练习,