第五章离散模型.ppt

《第五章离散模型.ppt》由会员分享，可在线阅读，更多相关《第五章离散模型.ppt（159页珍藏版）》请在三一文库上搜索。

1、第五章 离散模型,离散模型是 将实际问题直接抽象成离散的数、符号 或图形，然后以离散数学为主要研究工具来解决的数学 模型。连续模型进行离散化所得到的数学模型不在此讨 论。,一、过河问题,问题 有三名商人各带一名随从要乘一条小船过河， 这条船每次最多只能容纳两个人，并且由于某种原因， 商人们总是提防着随从们，预感到一旦在任何地方只要 随从人数多于商人数，就会对商人构成危害。但是由于 商人们控制着如何乘船的指挥权，所以商人们就可以制 定一个过河方案，以确保商人们的安全。试求出这个方 案。,建模,设在渡河过程中，此岸的商人个数为 随从个数为 以 表示此岸的状态向量，即,在 中有一部分对商人是安全的，

2、称为容许状态集合， 记为 即有,在上图中, 实点即表示为容许状态的集合.,乘船的方案称为决策，仍然用向量 来表示， 即 名商人和 名随从同坐一条船. 在这些决策中, 有,是符合条件的，称为容许决策。容许决策的全体组成集 合构成容许决策的集合，记为,在这个问题中，容许决策的集合为,小船从此岸到彼岸的一次航行，会使两岸的状态发生 一次变化，此称为状态的转移。用,表示状态的转移。其中 用 表示在状态 下的决策。当 为奇数时，表示从此岸到 彼岸，当 为偶数时，表示从彼岸到此岸。所以,公式称为状态转移公式。,所以，该问题转变成寻找一系列的决策 使状 态 按由初始状态经过有限次的 转移达到,建立坐标系统，

3、并在坐标平面上建立的刻度单位。做 网格线，网格线上的每一个交点代表一个状态（用实点 表示）。黄色曲线弧表示向彼岸渡人，绿色曲线弧表示 从彼岸返回。容许决策 表现为 从一个实点向另一个实点的转移。 当 为奇数时，容许决策表现的是 向下及向左的移动，当 为偶数时 容许决策表现的是向上及向右的移,解模,动。,整个状态的转移用下面的表格来表示。,分析 从上表中可以看到，该方案是可行的。,二、马氏链及其应用,1.一个简单的例子,我们知道，人寿保险公司最为关心的是投保人的健康 与疾病以及相应的风险。通过下面的例子我们来看保险 公司是如何处理这类问题的。,问题的提出,设 表示年龄的时段，假定在一年中，今 年

4、健康而明年患病的概率是 而今年患病明年转为健 康的概率为 假设一个人在投保时处于健康状态，我 们来研究若干年之后他分别处于这两种状态的概率。,建模,用随机变量 表示第 年的状态，,以 表示第 年状态为 的概率。即,以 表示今年状态处于 明年状态处于 的概率，即,由全概率公式得到：,即,由假设，,再由于投保人处于健康状态，即,由此得到,若投保人在开始时处于疾病状态，即 则有,从两张表中可以看到，无论投保人在初始时处于什么 状态，当时间趋于无穷大时，该时刻的状态趋于稳定， 且与初始值无关。即,意义 若将众多投保人处于两种状态的比例，视为投 保人处于两种状态的概率，例如健康人占3/4，病人占 1/4

5、，即 则同样可计算出,由上面的分析可以看出，对于给定的状态转移概率， 时的状态概率， 趋向于稳定值，该 值与初始值无关，这是马氏链的重要性质。,把人的死亡看作第三种状态，用 来表示，相 应的转移概率如下图表示。,仍以 表示状态 为 时的概率， 表示状态转移概 率，即有,平行于式，有,设投保人在期初处于健康状态，则由可计算出若干 年后他处于各个状态的概率。,表中最后一列数据是通过预测得到的。从表中的数据 又可以看到，无论投保人在期初处于什么状态，当 时，总有,2.马尔可夫链,假设 1.系统是随时间的发展而离散为,2.在任何时刻，系统的状态为有限多个。在时间 时， 系统的状态的 的取值为,3.在时

6、刻 时系统处于各状态的概率只与时刻 时 系统所处的概率与转移概率有关。,满足以上三个假设的系统的随机发展过程称为马尔可 夫过程或马氏链。,设在时刻 时系统处于状态 的概率为,行向量,称为状态概率向量，由概率的意义，向量应该满足,及,设在时刻 处于状态 的系统转移到 时刻处于 的概率为 它应该满足,1.,引如概率转移矩阵,由假设3，再由全概率公式得,用矩阵的方法来表示的话，可以写成,简单地可以写成,由此可得系统在时刻 时的状态向量为,其中 为时刻 时系统的状态概率向量，又称为 状态初始向量。,例 在前两例中，初始向量与概率转移矩阵分别为,我们通过下面的例子具体说明：,上式表明在时刻 时投保人处于

7、患病状态的概率 为：,从上面的例子中可以看出，对于马氏链模型，最重要 的是构造状态 及概率转移矩阵 由此对于给定的初始 状态 由可计算出任意时刻 的状态,正则链,定义 一个有 个状态的马氏链，如果存在正整数 使从任意状态 经 次的转移，能以大于零的概率到 达状态 则称这样的链为正则链.,定理1 设马氏链的转移矩阵为 则该链为正则链的 充分必要条件是存在 使得,定理2 正则链存在唯一的极限状态概率,满足 与初始状态概率 无关，且,及,例1 设,则由此确定的马氏链为正则链。令 满足 式，即有,由此得到方程组,联系则得到,故方程组的解为,这和前面的结果是相吻合的。,例2 设,因,故由此确定的马氏链是

8、正则链。令,由方程，确定方程组,从方程中解出 即,吸收链,定义 如果存在某个状态转移概率 则称状态 是 吸收的. 如果马氏链中含有吸收状态, 并且从每一个非 吸收状态出发都可以达到某个吸收状态，则称这个马氏 链为吸收链。,例如在前面三个状态的转移概率中，转移概率矩阵 为,并且从每个状态最终都转移到第三种状态, 因而这样的 链是吸收链。,注 吸收链的特征是：任一状态一旦进入该状态就 将停留在该状态。,含有 个吸收状态和 非吸收状态的吸收链的 状态转移概率矩阵的标准形式是,其中 是单位矩阵。,定理3 对于具有标准形式的状态转移概率矩阵，有如 下的性质：,矩阵 具有零极限，即,矩阵 可逆且,记 则矩

9、阵的第 行元素之和值是从非 吸收状态出发被某个吸收状态吸收之前的平均转移次 数。,记 则矩阵 的元素 是从非吸收状态 出 发而被状态 吸收的概率。,在前面的例2中,将 改写成,则,则,应用 基因遗传问题,生物的外部特征是由生物体内的基因决定的。基因分 优势与劣势基因两种。分别表示为 对于生物的某 个外部特征，体内有两个基因与之对应。由于体内的每 个基因都可以是两种基因之一，因此体内的基因对类型 可能有三种： 分别被称为优种、混种和劣 种。按基因理论：含优种和混种的基因个体类型，其外 部特征呈优势；而含劣势基因类型的个体，其外部特征 呈劣势。,生物在繁殖时，后代随机地继承父亲和母亲的两个基 因中

10、的各一个而形成自己的基因对。因此后代成为优 种、劣种、混种基因类型的概率是不同的。,下面讨论两种基因繁殖后代的情况,一、永远与混种繁殖后代的情况,假设一个个体是优种，而另一个个体是混种，则它们 的直接后代成为优种 、混种 、劣种 的概率分别为,假设一个个体是混种，而另一个个体是混种，则它们 的直接后代成为优种 、混种 、劣种 的概率分别为,假设一个个体是劣种，而另一个个体是混种，则它们 的直接后代成为优种 、混种 、劣种 的概率分别为,由此得到概率转移矩阵,由前面的例2知该链为正则链，极限状态概率向量为,上式表明，经过长时间的繁殖过程，后代的外部特征 呈优势的概率是优种和混种概率的和，这个量与

11、初始的 个体所含基因的种类无关。,2.近亲繁殖的结果,假设最初的父母可以是优种、混种或劣种，它们有大 量的后代，这些后代又随机地雌雄交配后代，今来分析 它们后代的演变情况。,由于每次繁殖都是随机地配对父亲和母亲，而父亲和 母亲可以是 中的一种，组合后就有 六种状态，分别记为 当父母都是优种 时，后代必然是优种 因此有,同理，当父母都是劣种时，后代只能是劣种，由此得,当父母一方为 而另一方为 时，当前状态可能是 因而再次配对产生的可能结果有,因此，有,当父母方为 对时，其后代只可能是 因而再 次配对之后之可能产生 所以,当父母方为 对时，其后代可能是,甲 乙,因而相应的概率为,所以概率转移矩阵为

12、,从上面中可以看到状态1和状态2是吸收状态。所以该链 为吸收链。,由前面的计算公式得到,的行和,根据矩阵 和 的性质，上式表明从状态3出发经过,代后它们的后代都会变成优种或劣种，从状态3出发其 后代全变为优种的概率为,上面表明：近亲繁殖的后代变成劣种的可能性很大。,三、钢琴销售的存储策略,问题的提出,一家商店根据以往经验, 平均每周只能售出1架钢琴. 现在经理指定的存储策略是: 每周末检查库存量. 仅当 库存量为零时, 才订购3架供下周销售; 否则不订购. 试 估计在这种策略下失去销售机会的可能性有多大? 以及 每周的平均销售量是多少?,问题分析,对钢琴这类比较昂贵的商品, 其销售一般被认为服

13、从 泊松分布. 即设 为每周的销售量, 则,周末的库存可能为 而周初的库存可能为 注意到需求的改变将引起库存的改变. 而当需求大于库 存时又会失去销售的机会. 今来计算这种变化的规律.,模型假设,1.钢琴每周的需求量服从泊松分布,且均值为1.,2存储策略是:当周末库存量为零时, 订购3架, 周初到货, 否则不订购.,3.以每周初的库存为状态变量, 状态转移具有无后效性.,4.在稳定状态下计算该存储策略失去销售机会的概率, 和每周的平均销售量.,模型建立,记第 周的需求量为 则 服从均值为1的泊松分 布, 即有,再记第 周初的库存量为 为该系统的状 态变量, 则有,由得,并由此计算概率转移矩阵,

14、*,即,记状态概率为,即有,注意到 即马氏链为正则链. 令 满足 且 解之得,假定初始状态为1架钢琴, 即状态概率为,则,该存储策略在第 周失去销售机会的概率为,当 时可近似认为 则有,即从长期看, 失去销售的机会为,最后计算平均销售量（用数学期望）:,但当库存量为 时, 销售量的最大取值为 因而上式为,同样, 当 时, 用稳态概率 来代替 则,即从长期看, 每周的平均销售量为,讨论,在原问题中, 若将订购策略改为: 若当周末的库存量 为零时, 订购量为销售量加2, 否则不订购, 试建立相应 的马氏链.,解 当概率不变时, 则概率分布为,由此得到状态变量 的取值为,概率转移矩阵为 其中,四、合

15、作对策模型,在经济或社会活动中，几个个体相互合作或结成联 盟，常常能或得比他们单独行动能获得的经济效益或社 会效益。怎样来合理分配所获取的效益是合作对策的研 究题目。,1.三人联合经商的利润分配问题,假设有 三人在经商。,若三人都独自经商，则每人每月都只能获得利润1万 圆；,若 和 合作经商, 则他们每月可获得利润7万圆；,若 和 合作经商, 则他们每月可获得利润5万圆；,若 和 合作经商, 则他们每月可获得利润4万圆；,若三人合作经商, 则他们每月可获得利润10万圆；,则问题转变为这10万圆的利润应如何分配给三人。,先给出合作对策的一般模型,记 为有 个人的集合，若对于 的 任一子集合 都有

16、一个实数 与之对应，且满 足下面条件：, ；,对 的任意两个子集合 有,则称 为定义在 上的一个特征函数。,所谓合作对策就是要确定已定义有特征函数的 中的 个人合作的结果，它表现为向量,在实际问题中，常把 中各种组合的合作所获得的利 益定义为特征函数，向量 就是 个人合作获利的 分配。,Shapley提出了应该满足的如下几个公理：,公理1 设 是 的一个排列，对于 的任一子集 令,再定义 上的特征函数 ： 则对于每 个 有,上式表明：合作获利对每个人的分配与记号无关。,公理2表明如果有人对他所参加的所有项目都没有贡 献，那么他就不应该从全体的合作中获利。,公理2 若对所有包含 的子集 都有 则

17、,公理3,公理3表明各个人的分配之和等于合作获利。,公理4 若 也是定义在 上的特征函数，且 则,公理4表明，若 个人同时进行两个项目的合作，则获 利的分配为两个独立项目分配之和。,Shapley证明了满足着四条公理的 是唯一的，并 且解的公式为：,其中 是 中所有含 的子集， 是集合 中的人数， 是加权因子，其值为,可看作为成员 对合作 的贡献。,表示对所有含 的子集 求和。,在例1中，将 分别记为 当 时，经计算得下表：,代入得,即 应分得利润4万圆。同理可计算对 时,有相应 的值:,代入，得,最后计算，得,2.三城镇的污水处理方案,沿河有城镇1、2、3，地理位置入图所示，城镇的污 水必须

18、经过处理后才能排入河中，因此三个城镇将单独 或联合建造污水处理厂，用管道将污水集中处理（污水 应从位于河流的上游向位于下游的城镇输送）。,以 表示污水量， 表示管道长 度，由经验公式，建厂费为,（万圆）.,铺管费为,（万圆）.,已知三城镇的污水量分别为 城镇间的距离分别为,试从节约总投资的角度出发,为三个城镇制定一个建造 污水处理厂的方案。如果联合建厂，各城镇应如何分担 费用？,以 代表三城镇，考虑,三城镇污水处理的如下5种方案,分别建厂，投资费用为,总投资,1，2合作在城镇2建立厂，则投资为,总投资为,2，3合作在城镇3建厂，则投资为,总投资为,1，3合作在城镇3建厂，则投资为,该费用超过了

19、1，3分别建厂的费用 故该方案无意义。,三城合作在城镇3建厂，则总费用为,比较结果，,即：选择联合建厂是一个最佳方案。但问题是应该如 何分担费用。,总费用 由三部分构成：联合建厂费,城1至城2的管道费,城2至城3的管道费,城3提出： 由三城镇按 的比例分担， 是 城1、2铺设的管道费用，则由他们承担，城2同意，并 提出 由城1、2按污水量 的比例分担，而 由城 1独自承担，城1不同意。 现计算按上面的想法各城应承 担的费用：,城3： 城2：,城1：,上面结果表明：城2、3的分担费用比单独建厂的费用 要低，而城1的费用要比单独建厂所花费的费用要高， 因而城1不能赞同这种方案。,为了促成三城联合建

20、厂，应当寻找合理分担费用的方 案。三城的合作节约了投资，产生了效益，可以将其看 作是一个 个人的合作问题。联合建厂比单独建厂节约 的投资定义为特征函数，于是有,三城联合建厂的效益为 由Shapley值作为这个效益 的分配，则有表,得,得 最后得,结果分析：,三城镇联合投资建厂的分担费用为：,城镇1,城镇2,城镇3,与按比例分担比较： 城镇1收益最大， 而城镇3“吃亏”。,3.股东在公司中的权重,某股份公司有4个股东分别持有 的股份，公司的决策必须经持有半数以上股份的股东同 意才可通过，问这 个股东在公司决策中的权重各多大？,该问题可看作为 个人的合作对策，记 其中 分别代表持有 股份 的股东。

21、特征函数定义为：对 中的任一子集 当其持 有的股份超过 时， 其余 于是,的子集为,其余 个子集的,由公式，可计算各个股东的Shapley值,对 经计算可得,由此得到,对 相应的数值为,得,同理可计算,即权重向量为,Shapley值方法的确定及解决方法,Shapley值方法以严格的公理为基础，在处理合作对 策的分配问题时具有公正、合理等优点，但是它需要知 道所有合作者的获利，即要定义 的所有 子集的特征函数，通常情况下这很难办到。例如 个单 位合作治理污染，第 方单独治理的投资 和 方合作治 理的投资 是已知的，还要知道第 方不参加合作时其 余 方所需的投资 特征函数定义为合作的获利，即 节约

22、的投资。为此有,除此之外还要计算其它的 这在计算上有一定的困 难。,以三人经商为例，我们介绍其余的几种方法：,记 无 参加时其余 方合作的获利记作 记,试确定各方对全体合作获利的分配。记作,五、团体决策模型,参加评选优秀运动员、优秀产品，选举代表都要有一 定的办法。该方法能从各位评判人员对评选对象的评价 综合地得出对各个评选对象的总的评价，从而选出优秀 者或排出名次。这样一类问题称为团体决策问题，各种 评选方法构成团体决策模型。,一、团体决策函数,设 是由 位评选人组成的集合；,设 是由 个被评选对象组成的 集合。,假设评选方法如此规定：,要求每位评选人员 对所有在候选对象集合 中的 候选对象

23、给出一个排序,这里序的定义为：,1.对任意的评选对象 必有 和 三种关系之一，且只有一种关系成立；,2.对任意三个评选对象 若 则必有,评选人员的排序组成一个排序组 称为 对 的一个分布，要求以此分布为基础确定整个 评选人员集合 对候选对象 的所有对象的一个排序,这个评选结果是由分布 的一种对应关 系，称为团体一致函数，记作,（一）、简单多数原则,如果在排序 中有关系 成立，则称有 如果在排序 中有关系 成立，则称有,简单多数原则是：当且仅当有 成立的 超 过 的一半时，就认为有 成立。然后根据一系 列对象间的上述形式的关系来排出总序。,例如，取 给出分布,显然，使 成立的 的个数是 故有 使

24、 成立的 的个数为 故有 同理，最后得排序为,简单多数原则的一个缺陷：产生循环。,例,结果： 从而无法给出排序。,（二）、Borda数原则,记 为排序 中劣于 的 的元素的个数，称为 对 的Borda数，而称,为 的Borda数。,Borda数原则是：当且仅当 时就认为有 且两个式中的等号是同时成立的。然后再根据一 系列对象间的上述形式的关系来派出总序。,在排序中，各个对象的Borda数依次为,再由，得,由此得相应的排序为：,此与用简单多数原则所获得的结果是一致的。,但是， Borda也有失效的时候。例如对 分布,相应的Borda数表为,于是有,得出总的排序,但是，按简单多数原则来排序的话，则

25、排序为,此排序似乎更为合理。,二、Arrow公理,设 为选民的集合， 为 候选人的集合。称一个分布 为一次投 票，称 为选民 的投票；称团体决策 为选举结果， 团体一致函数 是从每个选民的投票来确定选举结果的 选举程序。Arrow在1951年提出选举程序应满足的四条 公理：,公理1 对任何一对候选人 和 都可能存在一次投 票，根据选举程序能确定,公理2 如果选举程序根据第一次投票的结果确定了 在第二次投票时每个选民 的投票 中 的次 序与第一次相同，或则是提前了，而其他候选人的次序 不变，则选举程序根据第二次投票也应该有,公理3 设 为 的一个子集，如果在两次投票中每 个选民对在 中的的各候选

26、人的排序不变，则在选举,中排序不变，则在选举程序所确定的两次选举结果中， 中的各候选人的排序相同。,公理4 不能存在这样的选民 使得对任一对候选 人 和 只要他的投票 中有 就能确定有,现在的问题是，有没有满足这四条公理的选举程序 呢？下面的情况说明这个问题与候选人数和选民人数有 关。,当 或 时，这样的选举是无意义的；,当 或 时，简单多数原则所确定的选举 程序就是满足四条Arrow公理的选举程序。,当 且 情况时，不存在满足四条Arrow 公理的选举程序。,该结论说明了：如果你认为只有满足Arrow公理的选 举程序才是公平合理的，那么这样的选举程序是不存 在的！,三、联合尺度,对于某种评选

27、对象（例如酒）可以按照某个指标（例 如甜度）在区间 上标记出它的位置；而每位评选者 都按自己的标准认定了在区间 上的某个位置是最理 想的。于是在区间 上就有两个尺度，称它为联合尺 度。,设 为四个候选对象，它们各处于 和 的位置上；有 三位评选者，他们各认定,和 是最佳位置。我们将评判者 所认定的理想位置 也记作,按联合尺度可得到每位评判者的排序：如果对象离 开 近的就排在前面，距离相等的就认为名次相同。 于是按下图所确定的排列为：,再由简单多数原则决定出的排列是,可以看到： 为标准在联合尺度的居中的评判者，而他 的排序正好是与简单多数原则确定的排序 相同。,定理 设候选人集合为 选民集合为

28、且选民的个数为 奇数个，又设按联合尺度得到的投票结果记为,而所有这样的投票结果的全体组成集合,设有 中的一次投票，而 是在联合尺度上 居中的那位选民，则按照简单多数原则所确定的选举结,与 是一致的，并且简单多数原则符合Arrow公理。,六、层次分析模型,层次分析法是T.L.Saaty等人在70年代初提出和广泛应 用的方法。它不仅可用来在工程技术、经济管理、社会 管理、社会生活等方面进行决策，而且可用来进行分析 和预报，它是近年来发展起来的系统分析的重要数学工 具之一。,假设有三个旅游地点 可供选择，要考虑的 的因素有五个：费用 景色 居住条件 饮食条件 和交通条件 旅游者的最后决策为,设每个因

29、素对三个地点的权重都是以知的，它们为,设旅游者在考虑旅游地点时对每个因素的（偏爱）权,重是已知的，它为,设旅游者对地点的权重为,则它可以用下列公式来计算：,这样，旅游者就可选择权重繁荣的地点作为选中的旅游 地点。,然而，权重 和 都是不容易确定的。因此引处了许 多进一步的问题。,（一）、成对比较法，正互反阵和一致阵,要判断 个因素 对目标 的影 响，即确定各个因素在 中的比重是比较困难的。如果 每次取两个因素 和 来比较容易多了。,设 为 和 对 的影响之比，则全部的比较结 果可用矩阵表示为,称为成对比矩阵，显然有性质,满足和的矩阵称为正互反矩阵。对于正互反矩阵， 则有,我们的目标是从正互反矩

30、阵出发，得到比重向量,其中 表示因素 对目标 的影响所占的比重。,若比重向量 已知，则容易得到成对比矩阵,注意到这个矩阵中的每一个列向量都是成比例的，并 且满足关系,若正互反矩阵 满足,则称该矩阵是一致性矩阵，简称为一致阵。,性质1,七、练习,1.某甲（农民）有一块土地，若他在这块土地上从事 农业生产，每年可收入10000元；若他将这块土地出租 给某乙（企业家）用于工业生产，则每年可获得收入 20000元；若租给某丙（旅店老板）用于旅游业，则可 获得收入30000元；若旅店老板请企业家参与经营时每 年收入可达40000元。试用Shapley值方法求分享甲乙丙 三人合作所得的40000元收入。,2.某委员会有100个席位，有三个派别分别拥有34席、 33席和33席。法律规定每一提案需要有超过半数的赞成 票时方能通过。假定每个派别的成员同时头赞成或反对 票，试用合作对策模型求三个派别在表决时各自占的比 重。如果三个派别分别拥有49，48和3席时，结果又如 何？,