第八章对策与决策模型.ppt

《第八章对策与决策模型.ppt》由会员分享，可在线阅读，更多相关《第八章对策与决策模型.ppt（102页珍藏版）》请在三一文库上搜索。

1、第八章 对策与决策模型,浙江大学数学建模基地,第八章 对策与决策模型,对策与决策是人们生活和工作中经常会遇到的择优活动。人们在处理一个问题时，往往会面临几种情况，同时又存在几种可行方案可供选择，要求根据自己的行动目的选定一种方案，以期获得最佳的结果。 有时，人们面临的问题具有竞争性质，如商业上的竞争、体育中的比赛和军事行动、政治派别的斗争等等。这时竞争双方或各方都要发挥自己的优势，使己方获得最好结果。因而双方或各方都要根据不同情况、不同对手做出自己的决择，此时的决策称为对策。在有些情况下，如果我们把可能出现的若干种情况也看作是竞争对手可采取的几种策略，那么也可以把决策问题当作对策问题来求解。,

2、8.1 对策问题,对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。,先考察几个实际例子。,例8.1 （田忌赛马）,田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。,例8.2 （石头剪子布）,这是一个大多数人小时候都玩过的游戏。游戏双方只能选石头、剪子、布中的一种

3、，石头赢剪子，剪子赢布，而布又赢石头，赢者得一分，输者失一分，双方相同时不得分，见下表。,表8.1,例8.3 （囚犯的困惑）,警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将各被判刑3年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列表如下：,表8.2,表中每对数字表示嫌疑犯A、B被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保

4、险的办法自然是承认制造了伪币。,一、对策的基本要素,（1）局中人。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例8.3中，局中人是A、B两名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他们各自采取的态度，警方不能为他们做出选择。,从这些简单实例中可以看出对策现象中包含的几个基本要素。,（2）策略集合。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着

5、一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。,记局中人i的策略集合为Si。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量S表示，称之为一个纯局势（简称局势）。,例如，若一对策中包含A、

6、B两名局中人，其策略集合分别为SA = 1, m，SB = 1, n。若A选择策略 i而B选策略 j，则（ i, j）就构成此对策的一个纯局势。显然，SA与SB一共可构成mn个纯局势，它们构成表8.3。对策问题的全体纯局势构成的集合S称为此对策问题的局势集合。,（3）赢得函数（或称支付函数）。对策的结果用矢量表示，称之为赢得函数。赢得函数F为定义在局势集合S上的矢值函数，对于S中的每一纯局势S，F（S）指出了每一局中人在此对策结果下应赢得（或支付）的值。综上所述，一个对策模型由局中人、策略集合和赢得函数三部分组成。记局中人集合为I = 1,k，对每一iI，有一策略集合Si，当I中每一局中人i选

7、定策略后得一个局势s；将s代入赢得函数F，即得一矢量F(s) = ( F1(s),Fk(s)，其中Fi(s)为在局势s下局中人i的赢得（或支付）。,本节讨论只有两名局中人的对策问题，即两人对策，其结果可以推广到一般的对策模型中去。对于只有两名局中人的对策问题，其局势集合和赢得函数均可用表格表示。例如，表8.2就给出了例8.3的局势集合和赢得函数。,二、零和对策,存在一类特殊的对策问题。在这类对策中，当纯局势确定后，A之所得恰为B之所失，或者A之所失恰为B之所得，即双方所得之和总为零。在零和对策中，因F1(s)= F2(s)，只需指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若A有m

8、种策略，B有n种策略，赢得矩阵,表示若A选取策略i而B选取策略j，则A之所得为aij（当aij0时为支付）。,在有些两人对策的赢得表中，A之所得并非明显为B之所失，但双方赢得数之和为一常数。例如在表8.4中，无论A、B怎样选取策略，双方赢得总和均为10，此时，若将各人赢得数减去两人的平均赢得数，即可将赢得表化为零和赢得表。表8.4中的对策在转化为零和对策后，具有赢得矩阵,表8.4,给定一个两人对策只需给出局中人A、B的策略集合SA、SB及表示双方赢得值的赢得矩阵R。综上所述，当遇到零和对策或可转化为零和对策的问题时，R可用通常意义下的矩阵表示，否则R的元素为一两维矢量。,故两人对策G又可称为矩

9、阵对策并可简记成 G = SA, SB, R ,例8.4 给定G = SA, SB, R，其中SA = 1, 2, 3，SB = 1, 2, 3, 4,从R中可以看出，若A希望获得最大赢利30，需采取策略 1，但此时若B采取策略 4，A非但得不到30，反而会失去22。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人A采取策略 1、 2、 3时，最坏的赢得结果分别为,min 12, 6, 30, 22 = 22,min 14, 2, 18, 10 =2,min 6, 0, 10, 16 = 10,其中最好的可能为max 22,2,10=2。如果A采取策略

10、2，无论B采取什么策略，A的赢得均不会少于2.,B采取各方案的最大损失为max 12,14, 6=14，max 6,2,0=2，max 30,18, 10=30和max 22,10,16 =16。当B采取策略 2时，其损失不会超过2。注意到在赢得矩阵中，2既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定解，（注：也被称为鞍点）,定义8.1 对于两人对策G = SA, SB, R，若有 ，则称G具有稳定解，并称VG为对策G的值。若纯局势（ ）使得 ，则称（ ）为对策G的鞍点或稳定解，赢

11、得矩阵中与（ ）相对应的元素 称为赢得矩阵的鞍点， 与 分别称为局中人A与B的最优策略。,对（8.1）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定一个对策G，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。,定理8.1 设G = SA, SB, R ， 记 ， 则必有+0,证明 : ，,易见为A的最小赢得，为B的最小赢得，,由于G是零和对策，故+0必成立。,定理8.2 零和对策G具有稳定解的充要条件为+= 0。,证明：,（充分性） 由和的定义可知，存在一行（例如p行）为p行中的最小元素且存在一列（例如q列），为q列中的最大元素。故有 apq且apq 又因+= 0

12、，所以=，从而得出apq=，apq为赢得矩阵的鞍点，（ p, q）为G的稳定解。,（必要性）若G具有稳定解（ p , q ），则apq为赢得矩阵的鞍点。故有,从而可得+0，但根据定理8.1，+0必成立，故必有+=0。,上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若,则易见，（ 2, 2），（ 2, 4），（ 4, 2），（ 4, 4）均为此对策问题的解。 一般又可以证明。,定理8.3 对策问题的解具有下列性质：,（1）无差别性。若（ , ）与（ , ）同为对策G的解，则必有 。,（2）可交换性。若（ , j1）、（ , j2）均为对策G的解，

13、则（ , j2）和（ , j1）也必为G的解。,定理8.3的证明非常容易，作为习题留给读者自己去完成。,具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是+0的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（8.1）中的赢得矩阵R。若双方都采取保守的max min原则， 将会出现纯局势 （ 4, 1）或 （ 4, 3）。但如果局中人A适当改换策略，他可以增加收入。例如，如果B采用策略 1，而A改换策略 1，则A可收

14、益 3。但此时若B改换策略 2，又会使A输掉4，。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。,设A方用概率xi选用策略 i，B方用概率yj选用策略 j， ， 且双方每次选用什么策略是随机的，不能让对方看出规律，,记X = (x1, ,xm)T，Y = (y1, ,yn)T，则A的期望赢得为,E ( X,Y) = X

15、TRY,其中，R为A方的赢得矩阵。记,分别称SA与SB为A方和B方的混合策略。,对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。,定义8.2 若存在m维概率向量和n维概率向量，使得对一切m维概率向量X和n 维概率向量y有 则称（ , ）为混合策略对策问题的鞍点。,定理8.4 （Von Neumann）任意混合策略对策问题必存在鞍点，即必存在概率向 量和，使得： （证明从略）。,使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策 问题的特殊情况，相当于以概率1选取其中某一策略，以概率0选取其余策略。,对于双方均只有两种策略的对策问题（即22对策），可按几何

16、方法求解。,例8.5 A、B为作战双方，A方拟派两架轰炸机I和II去轰炸B方的指挥部，轰炸机I在前面飞行，II随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰炸机飞至B方上空，受到B方战斗机的阻击。若战斗机阻击后面的轰炸机II，它仅受II的射击，被击中的概率为0.3（I来不及返回击它）。若战斗机阻击I，它将同时受到两架轰炸机的射击，被击中的概率为0.7。一旦战斗机未被击落，它将以0.6的概率击毁其选中的轰炸机。请为A、B双方各选择一个最优策略，即：对于A方应选择哪一架轰炸机装载炸弹？对于B方战斗机应阻击哪一架轰炸机？,解：双方可选择的策略集分别为,SA = 1, 2, 1：轰炸机 I

17、装炸弹， II 护航 2：轰炸机 II 装炸弹，I 护航,SA = 1, 2, 1：阻击轰炸机 I 2：阻击轰炸机 II,赢得矩阵R=（aij）22，aij为A方采取策略 i而B方采取策略 j 时，轰炸机轰炸B方指挥部的概率，由题意可计算出：,a11= 0.7 + 0.3 (10.6) = 0.82,a12= 1, a21= 1,a22= 0.3 + 0.7 (10.6) = 0.58,即,易求得 ， 。 由于+0，矩阵R不存在鞍点，应当求最佳混合策略。,现设A以概率x1取策略 1、概率x2取策略 2； B以概率y1取策略 1、概率y2取策略 2。,先从B方来考虑问题。B采用 1时，A方轰炸机

18、攻击指挥部的概率的期望值为E（ 1）=0。82x1+x2，而B采用 2时，A方轰炸机攻击指挥部的概率的期望值为E（ 2）=x1+0.58x2。若E（ 1）E（ 2），不妨设E（ 1） E（ 2），则B方必采用 1以减少指挥部被轰炸的概率。故对A方选取的最佳概率x1和x2，必满足：,即,由此解得x1=0.7，x2=0.3。,同样，可从A方考虑问题，得,即,并解得y1=0.7，y2=0.3。B方指挥部轰炸的概率的期望值VG=0.874。,上述方法也可以用几何方式表达。在x轴上取长度为1的线段，左端点为x=0，右端点为x=1。过x=0和x=1各作x轴的垂线，称之为轴I和轴II。在轴I上取B1、B2，

19、它们到x轴的距离分别的a11和a12，表示在A采取策 略 1 即(x2=0）时A方在B方分别采取策略 1 和 2下的赢得，如图8.1所示。,借助几何方法也可以解m2或2n的使用混合策略的对策问题。 但当m2且n2时，采用几何方法求解就变得相当麻烦， 此时通常采用线性规划方法求解。,现设A以概率x2采取策略 2，若B采取策略 2，则A的期望赢得为a11(1x2)+a21x2。对应x2的不同取值（0x21），a11(1x2)+a12x2恰好构成连接两个B1的直线段。类似地，连接两个B2的直线段恰好对应当B取 2而A以概率x2取2时的赢得a12(1x2)+a22x2。设两直线段相交于N，并设N对应于

20、 。若A以小于 的x2取策略 2，则B可以采取 1使A的期望赢得减小；反之，若x2 ，则B又可采取 2而使A的赢得减小。故A的最佳混合策略为以 =1 概率取 1，以概率取 2（注：B的最佳混合策略可类似用几何方法求得）。,A方选择混合策略 的目的是使得,其中ej为只有第j个分量为1而其余分量均为零的向量，Ej = XTRej。 记 ，由于 ， 在yk=1，yj=0 （jk）时达到最大值u，,故 应为线性规划问题,同理， 应为线性规划,由线性规划知识，（8.2）与（8.3）互为对偶线性规划，它们具有相同的最优目标函数值。关于线性规划对偶理论，有兴趣的读者可以参阅有关书籍，例如鲁恩伯杰的“线性与非

21、线性规划引论”。,为了寻找例8.5中A方的最优混合策略，求解线性规划,min u S.t 0.82x1 + x2 u x1 + 0.58x2 u x1 + x2 = 1 x1 , x2 0,可得最优混合策略x1 =0.7, x2 =0.3。类似求解线性规划,max S.t 0.82y1 +y2 y1 +0.58y2 y1 +y2 =1 y1 , y2 0,可得B方最优混合策略：y1 =0.7, y2 =0.3。,三、非零和对策,除了零和对策外，还存在着另一类对策问题，局中人获利之和并非常数。,例8.4 现有一对策问题，双方获利情况见表8.5。,表8.5,假如A、B双方仍采取稳妥的办法，A发现如

22、采取策略4，则至少可获利4，而B发现如采取策略1，则至少可获利2。因而，这种求稳妥的想法将导至出现局势（4，2）。,容易看出，从整体上看，结果并不是最好的，因为双方的总获利有可能达到10。不难看出，依靠单方面的努力不一定能收到良好的效果。看来，对这一对策问题，双方最好还是握手言和，相互配合，先取得总体上的最大获利，然后再按某一双方均认为较为合理的方式来分享这一已经获得的最大获利。,例8.4说明，总获利数并非常数的对策问题（即不能转化为零和对策的问题），是一类存在着合作基础的对策问题。当然，这里还存在着一个留待解决而又十分关键的问题：如何分享总获利，如果不能达到一个双方（或各方）都能接受的“公平

23、”的分配原则，则合作仍然不能实现。怎样建立一个“公平”的分配原则是一个较为困难的问题，将在第九章中介绍。,最后，我们来考察几个对策问题的实例。,例8.6（战例分析）1944年8月，美军第一军和英军占领法国诺曼第不久，立即从海防前线穿过海峡，向Avranches进军。美军第一军和英军的行动直接威胁到德军第九军。美军第三军也开到了Avranches的南部，双方军队所处的地理位置如图8.2所示。,美军方面的指挥官是Bradley将军，德军指挥官是Von Kluge将军。,Von Kluge将军面临的问题是或者向西进攻，加强他的西部防线，切断美军援助；或者撤退到东部，占据塞那河流域的有利地形，并能得到

24、德军第十五军的援助。,Bradley将军的问题是如何调动他的后备军，后备军驻扎在海峡南部。Bradley将军有三种可供选择的策略：他可以命令后备军原地待命，当海峡形势危急时支援第一军或出击东部敌人，以减轻第一军的压力。,双方应如何决策，使自己能有较大的机会赢得战争的胜利呢？,我们将用建立矩阵对策模型的方法，来试图求得双方的最优策略。模型假设：,1、Bradley将军和Von Kluge将军分别为对策问题的局中人A和B。,2、局中人A的策略集合为SA = 1, 2, 3，其中： 1为后备军增援保卫海峡； 2为后备军东征，切断德军后路； 3为后备军待命,3、局中人B的策略集合为SB = 1, 2，

25、其中： 1为德国向西进攻海峡，切断美军援助； 2为德军撤退到东部，占领塞纳河流域有利地形。,4、SA、SB构成六种纯局势，综合双方实力，各种局势估计结果如下。若B采取策略 1，即德军采取攻势，则有,（1）（ 1, 1），估计美军击败德军并占领海峡的可能性（即概率）为,（2）（ 2, 1），估计美军取胜的可能为 。德军很可能打破美军第一军的防线，并切断美军的退路。,（3）（ 3, 1），估计美军可以根据需要增援。如不需增援，后备军可东进绕行到德军后方。这样，美军将占领海峡并彻底歼灭德军第九军。,情况（1）、（2）、（3）如图8.3（1）、（2）、（3）所示。,若B采取策略 2，即德军第九军东撤，

26、占据塞纳河流域有利地形，则有,（4）（ 1, 2），美方扩大了战线，德军虽占据了有利地形，美军仍有击败 德军的可能性。,（5）（ 2, 2），美后备军东进给德军东撤造成压力并挫伤德军，使美军击败 德军的可能性增大到 。,（6）（ 3, 2），美后备军待命。在发现德军撤退后，奉命向东扰乱敌方撤退， 为以后歼灭德第九军创造条件，估计是美军击败德军的可能性 。,情况（4）、（5）、（6）见图8.3（4）、（5）（6）所示。,上述分析估计是由Bradley将军作出的，据此构造出A方赢得矩阵,这是一个32对策矩阵。可以求得 ， ， ，不存在稳定解，需要考虑其他解法。,定义8.3 对于赢得矩阵R，如果对所

27、有j，aijakj均成立，且至少存在一个 使 得 则称i行优于k行（策略ai优于ak）。同样，如对一切i有aijakl， 且至少有一个i0使得 ，则称j列优于l例（局中人B的策略 j优于 l）。,易见，若一个对策矩阵的第i行优于第k行，则无论局中人B选择哪种策略，局中 人A采取策略 i的获利总优于（至少不次于）采取策略 k的获利。,定理8.5 对于矩阵对策G= SA, SB, R，若矩阵R的某行优于第i1,ik行， 则局中人A在选取最优策略时，必取 。 令 ，R为从R中划去第i1行，ik行后剩下的矩 阵，则 的最优策略即原对策G的最优策略，对于R中 列的最优关系也有类似的结果。,利用这一定理，

28、有时对策问题可先进行化简，降低矩阵的阶数。,现在回过来讨论美、德军队对策问题。在Bradleg构造的矩阵中容易发现,a1ja3j, j=1,2,故 3优于 1。 根据上面的定理8.5，可划去该矩阵的第一行，得到22赢得矩阵,这仍然是一个无鞍点的对策矩阵。设Bradley以概率p1取策略 2而以概率p2取略 3，则应有,解得,类似地，设Von Kluge 以概率q1取策略 1而以概率q2取策略 2，则应有,解得 。,由于两军作战并非可以反复进行的对策问题，看来最大的可能是美军采取策略 3而德军采取策略 2，即美方后备军待命而德军第九军东撤。事实上，当时双方指挥官正是这样决策的，如果真能实行，双方

29、胜负还难以料定。但正当德军第九军刚开始东撤时，突然接到了希特勒的命令要他们向西进攻，从而失去了他们有可能取得的最佳结局，走上必然灭亡的道路。Von Kluge将军指挥的德军向西进攻，开始时德军占领了海峡，但随之即被美军包围遭到了全军复灭，Von Kluge本人在失败后自杀。,例8.7 （防坦克地雷场的布设） 实战中，攻方为了增强攻击力，大量使用攻击力强、防御坚固的坦克；守方为了抵御对方攻击，需要大量杀伤敌方的有生力量，有效对策之一是布设防坦克地雷场。,1、分析,评价防坦克地雷场的重要指标是战斗效力，而布雷密度是基本因素之一。只要有足够多的地雷，用较高密度的地雷场对付敌方进攻总是行之有效的。但在

30、实际战斗中，地雷不太可能是足够多的。假设：,（1）防坦克地雷数量有限；,（2）通过侦察、分析，已知敌方可能采用 1、 2、 n种进攻策略之一；,（3）通过敌情分析，确定了防御正面的宽度，并根据我方地雷数量，设计 了 1, 2, m这m种布雷方案。,问采取哪一方案或什么样的混合策略能有效击毁敌方的坦克？,本例在过去一般是凭指挥员的作战经验定性决策的，现用矩阵对策方法进行定量择优。,由于每两辆坦克之间一般要保持50米的间距，因而进攻正面拉得很宽，如一个梯队20辆坦克，进攻正面约为一公里宽。因为只有有限个防御正面，用有限个进攻策略来描述敌方的进攻状态是非常接近实际情况的。对守方来讲，布雷密度通常可分

31、成0.5,1,1.5,2等有限个等级。按常规做法，在防御正面上一般采用同一种技术密度。为了提高杀伤率，现将一个防御正面划分成几段，各段允许采用不同密度。,2、对策决策,要用矩阵对策决策，关键问题是如何列出守方的赢得矩阵。由效率评定试验可得出在各种布雷密度下的杀伤率表，如表8.6所示。,表8.6,根据上表，在确定方案后即可根据各段不同密度针对攻方的进攻策略计算出坦克的杀伤率。为便于理解，作为实例分析下面两种情况：,情况1 设守方只有1500个防坦克地雷，欲布设在攻方必经的2公里攻击正面上。攻方一个坦克梯队的20辆坦克展开成1公里宽的阵面，但既可能从左侧进攻（策略 1）也可能从右侧进攻（策略 2）

32、。守方设计了三种布雷方案 1, 2, 3,（图8.4），试求守方的赢得矩阵和最优策略。,图8.4,情况1求解：容易求得守方的赢得矩阵,这是一个有鞍点的矩阵，鞍点为a22。守方只要按 2方案布雷，则不管攻方从哪一侧进攻，总可毁伤对方47.5%的坦克。,情况2 攻方一梯队20辆坦克可从左侧（ 1）、中路（ 2）或右翼（ 3）进攻，展开成1公里布阵。守方只有2000个防坦克地雷，初步提出三种布雷方案，如图8.5所示，试求守方采用何种布雷方案较好。,图8.5,对情况2，可求得守方的赢得矩阵为,此时，矩阵A中不存在鞍点，对策无稳定解，应采用混合策略。可以求得，此时守方如按照0.166:0.456:0.3

33、78的比例采取策略 1, 2, 3布雷，平均可毁伤对方83.5%的坦克。,由本例可以看出，在决策问题中，策略的设计至关重要，它直接影响到赢得矩阵。策略的设计并没有包含在决策问题的求解中，事实上，仅当策略设计完成后，即策略集合给定后，决策问题才被给定，从而才能被求解，因而，在用对策论方法研究实际课题时，应当特别注意策略的设计。这一部分工作既具有一定的创造性又在很大程度上影响到结果，对它研究也是十分有趣的。,8.2 决策问题,人们在处理问题时，常常会面临几种可能出现的自然情况，同时又存在着几种可供选择的行动方案。此时，需要决策者根据已知信息作决策，即选择出最佳的行动方案，这样的问题称为决策问题。面

34、临的几种自然情况叫做自然状态或简称状态。状态是客观存在的，是不可控因素。可供选择的行动方案叫做策略，这是可控因素，选择哪一方案由决策者决定。,例8.8 在开采石油时，会遇到是否在某处钻井的问题。尽管勘探队已作了大量调研分析，但由于地下结构极为复杂，仍无法准确预测开采的结果，决策者可以决定钻井，也可以决定不钻井。设根据经验和勘探资料，决策者已掌握一定的信息并列出表8.7。,表8.7,问：决策者应如何作出决策？,解：由题意可以看出，决策问题应包含三方面信息：状态集合 Q= 1, n、策略集合A = 1, m及收益R = aij，其中aij表示如果决策者选取策略i而出现的状态为j，则决策者的收益值为

35、aij（当aij为负值时表示损失值）。,决策问题按自然状态的不同情况，常被分为三种类型：确定型、风险型（或随机型）和不确定型。,确定型决策是只存在一种可能自然状态的决策问题。这种决策问题的结构较为简单，决策者只需比较各种方案，确定哪一方案最优即可。值得一提的是策略集也可以是无限集，例如，线性规划就可行看成一个策略集是限集的确定型决策，问题要求决策者从可行解集合（策略集）中挑选出最优解。确定型决策的求解并非全是简单的，但由于这些问题一般均有其自己的专门算法，本节不准备再作介绍。在本节中，我们主要讨论风险型与不确定型决策，并介绍它们的求解方法。,一、风险型决策问题,在风险型决策问题中存在着两种以上

36、可能出现的自然状态。决策者不知道究竟会出现哪一种状态，但知道各种状态出现的概率有多大。例如，例8.8就是一个风险型决策问题。,对于风险型决策问题，最常用的决策方法是期望值法，即根据各方案的期望收益或期望损失来评估各方案的优劣并据此作出决策。如对例1，分别求出方案 1（钻井）和 2（不钻井）的期望收益值：,E（ 1）=0.2（30）+0.520 + 0.340 = 16（万元）,E（ 2）=0,由于E（ 1）E（ 2），选取 1作为最佳策略。,风险型决策也可采用期望后悔值法求解。首先，求出采取方案 i而出现状态 j时的后悔值 。,例如，如果不钻井，但事实上该处可开出一口高产井，则后悔值为40。因

37、为钻井可收益40万元，但决策者作了不钻井的决策，未获得本来可以获得的40万元收益。然后，比较各方案的期望后悔值，选取期望后悔最小的方案作为最佳策略。在例8.8中，如采用期望后悔值法，则E（ 1）=6，E（ 2）=22，取 1为最佳策略。,在选取策略 i而出现状态 j时后悔值为 的理由是在 出现状态 j情况下的最大可能收益为 。,定理8.6 最大期望收益法与最小期望后悔值法等价，即两者选出的最佳 策略相同。,证明：由 得,故,等式（8.4）的右端项为一常数，其左端项为采取策略 i时期后悔值与期望收益值之和，从而，若某策略使期望收益最大，则该策略必使期望后悔值最小，定理得证。,对于较为复杂的决策问

38、题，尤其是需要作多阶段决策的问题，常采用较直观的决策树方法，但从本质上讲，决策树方法仍然是一种期望值法。,例8.9 某工程按正常速度施工时，若无坏天气影响可确保在30天内按期完工。但根据天气预报，15天后天气肯定变坏。有40%的可能会出现阴雨天气而不影响工期，在50%的可能会遇到小风暴而使工期推迟15天，另有10%的可能会遇到大风暴而使工期推迟20天。对于可能出现的情况，考虑两种方案：,（1）提前紧急加班，在15天内完成工程，实施此方案需增加开支18000元。,（2）先按正常速度施工，15天后根据实际出现的天气状况再作决策。,如遇到阴雨天气，则维持正常速度，不必支付额外费用。,如遇到小风暴，有

39、两个备选方案：（i）维持正常速度施工，支付工程延期损失费20000元。（ii）采取应急措施。实施此应急措施有三种可能结果：有50%可能减少误工期1天，支付应急费用和延期损失费共24000元；有30%可能减少误工期2天，支付应急费用和延期损失费共18000元；有20%可能减少误工期3天，支付应急费用和延期损失费共12000元。,如遇大风暴，也有两个方案可供选择：（i）维持正常速度施工，支付工程延期损失费50000元。（ii）采取应急措施。实施此应急措施也有三种可能结果：有70%可能减少误工期2天，支付应急费及误工费共54000元；有20%可能减少误工期3天，支付应急费及误工费共46000元；有1

40、0%可能减少误工期4天，支付应急费和误工费共38000元。,根据上述情况，试作出最佳决策使支付的额外费用最少。,解：由于未来的天气状态未知，但各种天气状况出现的概率已知，本例是一个风险型决策问题，所谓的额外费用应理解为期望值。,本例要求作多次决策，工程初期应决定是按正常速度施工还是提前紧急加班。如按正常速度施工，则15天后还需根据天气状况再作一次决策，以决定是否采取应急措施，故本例为多阶段（两阶段）决策问题。为便于分析和决策，采用决策树方法。,根据题意，作决策树如图8.6,图8.6中，表示决策点，从它分出的分枝称为方案分枝，分枝的数目就是方案的个数。表示机会节点，从它分出的分枝称为概率分枝，一

41、条概率分枝对应一条自然状态并标有相应的发生概率。称为未梢节点，右边的数字表示相应的收益值或损失值。,在决策树上由右向左计算各机会节点处的期望值，并将结果标在节点旁。遇到决策点则比较各方案分枝的效益期望值以决定方案的优劣，并且用双线划去淘汰掉的方案分枝，在决策点旁标上最佳方案的效益期望值，计算步骤如下：,（1）在机会节点E、F处计算它们的效益期望值,E(E) = 0.5（24000）0.3（18000）0.2（12000）=19800 E(F) = 0.7（54000）0.2（46000）0.1（38000）=50800,（2）在第一级决策点C、D处进行比较，在C点处划去正常速度分枝，在D处划去

42、应急分枝。,（3）计算第二级机会节点B处的效益期望值,E(B) = 0.400.5（19800）0.1（50000）=14900,并将14900标在B点旁。,（4）在第二级决策点A处进行方案比较，划去提前紧急加班，将14900标在A点旁。,结论 最佳决策为前15天按正常速度施工，15天后按实际出现的天气状况再作决定。如出现阴雨天气，仍维持正常速度施工；如出现小风暴，则采取应急措施；如出现大风暴，也按正常速度施工，整个方案总损失的期望值为14900元。,根据期望值大小决策是随机型决策问题最常用的办法之一。实际应用时应根据具体情况作出分析，选取期望收益最大或期望损失最小的方案。,二、不确定型决策问

43、题,只知道有几种可能自然状态发生，但各种自然状态发生的概率未知的决策问题称为不确定型决策问题，由于概率未知，期望值方法不能用于这类决策问题。下面结合一个例子，介绍几种处理这类问题的方法。,例8.10 设存在五种可能的自然状态，其发生的概率未知。有四种可供选择的行动方案，相应的收益值见表8.7,表8.8,（1）乐观法（max max原则）,采用乐观法时，决策者意在追求最大可能收益。他先计算每一方案的最大收益值，再比较找出其中的最大者，并采取这一使最大收益最大的方案，在例8.10中，max a1j = 6，max a2j = 8，max a3j = 9，max a4j = 6，而max 6，8，9

44、，6=9， 采取方案 3。,（2）悲观法（max min原则）,采用悲观法时，决策者意在安全保险。他先求每一方案的最小收益,再比较找出其中的最大者，并采取这一使最小收益值最大化的方案。对于例8.10，min a1j = 4，min a2j = 3，min a3j = 1，min a4j = 3。 因为max 4, 3，1，3 = 4, 采取方案 1。,（3）乐观系数法（Hurwicz决策准则）,乐观系数法采用折中的办法，引入一个参数t，0t1，称t为乐观系数。,作决策时，决策者先适当选取一个t的值；再对各方案 1求出 ； 最后再作比较，找出使 最大的方案。在例8.10中，若取t=0.5，采用乐

45、观系数法决策，将选取 方案 2。易见，t=1对应乐观法，而t=0则对应于悲观法。,（4）等可能法（Laplace 准则）,由于不能估计各状态出现的概率，决策者认为它们相差不会过大。此时，决策者采用将各状态的概率取成相同值的办法把问题转化为风险型，并借用风险型问题的期望值法来决策。对于例8.10，如取各状态出现的概率均为0.2，用期望值法决策，将选取策略 2。,不难看出，对于不确定型决策问题，不论采用什么方法决策，最终采用的策略都不能称为最佳策略。事实上，采取什么方法决策与决策者的心理状态有关。而且，即使对同一决策者，在处理不同决策问题时也可能采取不同的方法。例如，在决定购买几元钱一张的对奖券时

46、，决策者也许会采用乐观法。因为几元钱的损失对他来讲是无所谓的事，小额奖金他也许看不上眼，要中就来个大奖。但是，在决策购买何种股票时，因为关系重大，也许他为了保险又会采取悲观法。同而，不确定型问题的决策充其量只能算是在决策者某种心理状态下的选优。要作出较符合实际情况的决策，还需决策者多作些调查研究，以便对未来自然状态的出现作出较符合客观实际的预测，才能收到较好的效果。,例8.11（离散报童模型）设某商品的需求量为离散变量，其取值范围为Q = 1, n， 取值 i的概率为P( i )，=1。记该商品的进货量为 （决策变量），若 ，进货过量，每单位进货过剩将造成k0元过量损失；反之，若 ，进货不足，每单位进货不足将造成ku元的不足损失。试确定该商品的最佳进货量。,解：当 时，将有过量损失k0（ ）；当 时，将有不足损失ku（ ）。故总期望损失为