第五章离散模型.ppt
《第五章离散模型.ppt》由会员分享,可在线阅读,更多相关《第五章离散模型.ppt(159页珍藏版)》请在三一文库上搜索。
1、第五章 离散模型 离散模型是 将实际问题直接抽象成离散的数、符号 或图形,然后以离散数学为主要研究工具来解决的数学 模型。连续模型进行离散化所得到的数学模型不在此讨 论。 一、过河问题 问题 有三名商人各带一名随从要乘一条小船过河, 这条船每次最多只能容纳两个人,并且由于某种原因, 商人们总是提防着随从们,预感到一旦在任何地方只要 随从人数多于商人数,就会对商人构成危害。但是由于 商人们控制着如何乘船的指挥权,所以商人们就可以制 定一个过河方案,以确保商人们的安全。试求出这个方 案。 建模 设在渡河过程中,此岸的商人个数为 随从个数为 以 表示此岸的状态向量,即 在 中有一部分对商人是安全的,
2、称为容许状态集合, 记为 即有 在上图中, 实点即表示为容许状态的集合. 乘船的方案称为决策,仍然用向量 来表示, 即 名商人和 名随从同坐一条船. 在这些决策中, 有 是符合条件的,称为容许决策。容许决策的全体组成集 合构成容许决策的集合,记为 在这个问题中,容许决策的集合为 小船从此岸到彼岸的一次航行,会使两岸的状态发生 一次变化,此称为状态的转移。用 表示状态的转移。其中 用 表示在状态 下的决策。当 为奇数时,表示从此岸到 彼岸,当 为偶数时,表示从彼岸到此岸。所以 公式称为状态转移公式。 所以,该问题转变成寻找一系列的决策 使状 态 按由初始状态经过有限次的 转移达到 建立坐标系统,
3、并在坐标平面上建立的刻度单位。做 网格线,网格线上的每一个交点代表一个状态(用实点 表示)。黄色曲线弧表示向彼岸渡人,绿色曲线弧表示 从彼岸返回。容许决策 表现为 从一个实点向另一个实点的转移。 当 为奇数时,容许决策表现的是 向下及向左的移动,当 为偶数时 容许决策表现的是向上及向右的移 解模 动。 整个状态的转移用下面的表格来表示。 序号状态态决策序号状态态决策 17 28 39 410 511 612 分析 从上表中可以看到,该方案是可行的。 二、马氏链及其应用 1.一个简单的例子 我们知道,人寿保险公司最为关心的是投保人的健康 与疾病以及相应的风险。通过下面的例子我们来看保险 公司是如
4、何处理这类问题的。 问题的提出 设 表示年龄的时段,假定在一年中,今 年健康而明年患病的概率是 而今年患病明年转为健 康的概率为 假设一个人在投保时处于健康状态,我 们来研究若干年之后他分别处于这两种状态的概率。 建模 用随机变量 表示第 年的状态, 表示健康, 表示疾病。 以 表示第 年状态为 的概率。即 以 表示今年状态处于 明年状态处于 的概率,即 由全概率公式得到: 即 由假设, 再由于投保人处于健康状态,即 由此得到 若投保人在开始时处于疾病状态,即 则有 从两张表中可以看到,无论投保人在初始时处于什么 状态,当时间趋于无穷大时,该时刻的状态趋于稳定, 且与初始值无关。即 两种状态的
5、转移概率 意义 若将众多投保人处于两种状态的比例,视为投 保人处于两种状态的概率,例如健康人占3/4,病人占 1/4,即 则同样可计算出 由上面的分析可以看出,对于给定的状态转移概率, 时的状态概率, 趋向于稳定值,该 值与初始值无关,这是马氏链的重要性质。 把人的死亡看作第三种状态,用 来表示,相 应的转移概率如下图表示。 三种状态的转移概率 仍以 表示状态 为 时的概率, 表示状态转移概 率,即有 平行于式,有 设投保人在期初处于健康状态,则由可计算出若干 年后他处于各个状态的概率。 表中最后一列数据是通过预测得到的。从表中的数据 又可以看到,无论投保人在期初处于什么状态,当 时,总有 2
6、.马尔可夫链 假设 1.系统是随时间的发展而离散为 2.在任何时刻,系统的状态为有限多个。在时间 时, 系统的状态的 的取值为 3.在时刻 时系统处于各状态的概率只与时刻 时 系统所处的概率与转移概率有关。 满足以上三个假设的系统的随机发展过程称为马尔可 夫过程或马氏链。 设在时刻 时系统处于状态 的概率为 行向量 称为状态概率向量,由概率的意义,向量应该满足 及 设在时刻 处于状态 的系统转移到 时刻处于 的概率为 它应该满足 1. 2. 引如概率转移矩阵 由假设3,再由全概率公式得 用矩阵的方法来表示的话,可以写成 简单地可以写成 由此可得系统在时刻 时的状态向量为 其中 为时刻 时系统的
7、状态概率向量,又称为 状态初始向量。 例 在前两例中,初始向量与概率转移矩阵分别为 我们通过下面的例子具体说明: 上式表明在时刻 时投保人处于患病状态的概率 为: 从上面的例子中可以看出,对于马氏链模型,最重要 的是构造状态 及概率转移矩阵 由此对于给定的初始 状态 由可计算出任意时刻 的状态 正则链 定义 一个有 个状态的马氏链,如果存在正整数 使从任意状态 经 次的转移,能以大于零的概率到 达状态 则称这样的链为正则链. 定理1 设马氏链的转移矩阵为 则该链为正则链的 充分必要条件是存在 使得 定理2 正则链存在唯一的极限状态概率 满足 与初始状态概率 无关,且 及 例1 设 则由此确定的
8、马氏链为正则链。令 满足 式,即有 由此得到方程组 联系则得到 故方程组的解为 这和前面的结果是相吻合的。 例2 设 因 故由此确定的马氏链是正则链。令 由方程,确定方程组 从方程中解出 即 吸收链 定义 如果存在某个状态转移概率 则称状态 是 吸收的. 如果马氏链中含有吸收状态, 并且从每一个非 吸收状态出发都可以达到某个吸收状态,则称这个马氏 链为吸收链。 例如在前面三个状态的转移概率中,转移概率矩阵 为 并且从每个状态最终都转移到第三种状态, 因而这样的 链是吸收链。 注 吸收链的特征是:任一状态一旦进入该状态就 将停留在该状态。 含有 个吸收状态和 非吸收状态的吸收链的 状态转移概率矩
9、阵的标准形式是 其中 是单位矩阵。 定理3 对于具有标准形式的状态转移概率矩阵,有如 下的性质: 矩阵 具有零极限,即 矩阵 可逆且 记 则矩阵的第 行元素之和值是从非 吸收状态出发被某个吸收状态吸收之前的平均转移次 数。 记 则矩阵 的元素 是从非吸收状态 出 发而被状态 吸收的概率。 在前面的例2中,将 改写成 则 则 应用 基因遗传问题 生物的外部特征是由生物体内的基因决定的。基因分 优势与劣势基因两种。分别表示为 对于生物的某 个外部特征,体内有两个基因与之对应。由于体内的每 个基因都可以是两种基因之一,因此体内的基因对类型 可能有三种: 分别被称为优种、混种和劣 种。按基因理论:含优
10、种和混种的基因个体类型,其外 部特征呈优势;而含劣势基因类型的个体,其外部特征 呈劣势。 生物在繁殖时,后代随机地继承父亲和母亲的两个基 因中的各一个而形成自己的基因对。因此后代成为优 种、劣种、混种基因类型的概率是不同的。 下面讨论两种基因繁殖后代的情况 一、永远与混种繁殖后代的情况 假设一个个体是优种,而另一个个体是混种,则它们 的直接后代成为优种 、混种 、劣种 的概率分别为 假设一个个体是混种,而另一个个体是混种,则它们 的直接后代成为优种 、混种 、劣种 的概率分别为 假设一个个体是劣种,而另一个个体是混种,则它们 的直接后代成为优种 、混种 、劣种 的概率分别为 由此得到概率转移矩
11、阵 由前面的例2知该链为正则链,极限状态概率向量为 上式表明,经过长时间的繁殖过程,后代的外部特征 呈优势的概率是优种和混种概率的和,这个量与初始的 个体所含基因的种类无关。 2.近亲繁殖的结果 假设最初的父母可以是优种、混种或劣种,它们有大 量的后代,这些后代又随机地雌雄交配后代,今来分析 它们后代的演变情况。 由于每次繁殖都是随机地配对父亲和母亲,而父亲和 母亲可以是 中的一种,组合后就有 六种状态,分别记为 当父母都是优种 时,后代必然是优种 因此有 同理,当父母都是劣种时,后代只能是劣种,由此得 当父母一方为 而另一方为 时,当前状态可能是 因而再次配对产生的可能结果有 因此,有 当父
12、母方为 对时,其后代只可能是 因而再 次配对之后之可能产生 所以 当父母方为 对时,其后代可能是 甲 乙 因而相应的概率为 所以概率转移矩阵为 从上面中可以看到状态1和状态2是吸收状态。所以该链 为吸收链。 由前面的计算公式得到 的行和 根据矩阵 和 的性质,上式表明从状态3出发经过 代后它们的后代都会变成优种或劣种,从状态3出发其 后代全变为优种的概率为 上面表明:近亲繁殖的后代变成劣种的可能性很大。 三、钢琴销售的存储策略 问题的提出 一家商店根据以往经验, 平均每周只能售出1架钢琴. 现在经理指定的存储策略是: 每周末检查库存量. 仅当 库存量为零时, 才订购3架供下周销售; 否则不订购
13、. 试 估计在这种策略下失去销售机会的可能性有多大? 以及 每周的平均销售量是多少? 问题分析 对钢琴这类比较昂贵的商品, 其销售一般被认为服从 泊松分布. 即设 为每周的销售量, 则 周末的库存可能为 而周初的库存可能为 注意到需求的改变将引起库存的改变. 而当需求大于库 存时又会失去销售的机会. 今来计算这种变化的规律. 模型假设 1.钢琴每周的需求量服从泊松分布,且均值为1. 2存储策略是:当周末库存量为零时, 订购3架, 周初到货, 否则不订购. 3.以每周初的库存为状态变量, 状态转移具有无后效性. 4.在稳定状态下计算该存储策略失去销售机会的概率, 和每周的平均销售量. 模型建立
14、记第 周的需求量为 则 服从均值为1的泊松分 布, 即有 再记第 周初的库存量为 为该系统的状 态变量, 则有 由得 并由此计算概率转移矩阵 * 即 记状态概率为 即有 注意到 即马氏链为正则链. 令 满足 且 解之得 假定初始状态为1架钢琴, 即状态概率为 则 该存储策略在第 周失去销售机会的概率为 当 时可近似认为 则有 即从长期看, 失去销售的机会为 最后计算平均销售量(用数学期望): 但当库存量为 时, 销售量的最大取值为 因而上式为 同样, 当 时, 用稳态概率 来代替 则 即从长期看, 每周的平均销售量为 讨论 在原问题中, 若将订购策略改为: 若当周末的库存量 为零时, 订购量为
15、销售量加2, 否则不订购, 试建立相应 的马氏链. 解 当概率不变时, 则概率分布为 由此得到状态变量 的取值为 概率转移矩阵为 其中 四、合作对策模型 在经济或社会活动中,几个个体相互合作或结成联 盟,常常能或得比他们单独行动能获得的经济效益或社 会效益。怎样来合理分配所获取的效益是合作对策的研 究题目。 1.三人联合经商的利润分配问题 假设有 三人在经商。 若三人都独自经商,则每人每月都只能获得利润1万 圆; 若 和 合作经商, 则他们每月可获得利润7万圆; 若 和 合作经商, 则他们每月可获得利润5万圆; 若 和 合作经商, 则他们每月可获得利润4万圆; 若三人合作经商, 则他们每月可获
16、得利润10万圆; 则问题转变为这10万圆的利润应如何分配给三人。 先给出合作对策的一般模型 记 为有 个人的集合,若对于 的 任一子集合 都有一个实数 与之对应,且满 足下面条件: ; 对 的任意两个子集合 有 则称 为定义在 上的一个特征函数。 所谓合作对策就是要确定已定义有特征函数的 中的 个人合作的结果,它表现为向量 在实际问题中,常把 中各种组合的合作所获得的利 益定义为特征函数,向量 就是 个人合作获利的 分配。 Shapley提出了应该满足的如下几个公理: 公理1 设 是 的一个排列,对于 的任一子集 令 再定义 上的特征函数 : 则对于每 个 有 上式表明:合作获利对每个人的分配
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 离散 模型
链接地址:https://www.31doc.com/p-2625241.html