第8章离散模型

1、第八章第八章 离散模型离散模型8.1 层次分析模型层次分析模型8.2 循环比赛的名次循环比赛的名次y离散模型离散模型 离散模型：差分方程（第离散模型：差分方程（第7 7章）、章）、整数规划（第整数规划（第4 4章）、图论、对策章）、图论、对策论、网络流、论、网络流、 分析社会经济系统的有力工具分析社会经济系统的有力工具 只用到代数、集合及图论（少许）只用到代数、集合及图论（少许）的知识的知识8.1 层次分析模型层次分析模型背背景景 日常工作、生活中的决策问题日常工作、生活中的决策问题 涉及经济、社会等方面的因素涉及经济、社会等方面的因素 作比较判断时人的主观选择起相当作比较判断时人的主观选择起

2、相当大的作用，各因素的重要性难以量化大的作用，各因素的重要性难以量化 Saaty于于1970年代提出层次分析法年代提出层次分析法 AHP (Analytic Hierarchy Process) AHP一种一种定性与定量相结合的、定性与定量相结合的、系统化、层次化系统化、层次化的分析方法的分析方法目标层目标层O(选择旅游地选择旅游地)P2黄山黄山P1桂林桂林P3北戴河北戴河准则层准则层方案层方案层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途一一. . 层次分析法的基本步骤层次分析法的基本步骤例例. . 选择旅游地选择旅游地如何在如何在3 3个目的地中按照景色、个目的地中按照景色

3、、费用、居住条件等因素选择费用、居住条件等因素选择. .“选择旅游地选择旅游地”思维过程的归思维过程的归纳纳 将决策问题分为将决策问题分为3个层次：目标层个层次：目标层O，准则层，准则层C，方案层方案层P；每层有若干元素，；每层有若干元素， 各层元素间的关系各层元素间的关系用相连的直线表示。用相连的直线表示。 通过相互比较确定各准则对目标的权重，及各方通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。案对每一准则的权重。 将上述两组权重进行综合，确定各方案对目标的将上述两组权重进行综合，确定各方案对目标的权重。权重。层次分析法将定性分析与定量分析结合起来层次分析法将定性分析与定量分

4、析结合起来完成以上步骤，给出决策问题的定量结果。完成以上步骤，给出决策问题的定量结果。1135/13/11125/13/13/12/117/14/1557123342/11AijjiijnnijaaaaA1, 0,)(层次分析法的基本步骤层次分析法的基本步骤一一.计算成对比计算成对比较阵和权向量较阵和权向量 元素之间两两对比，对比采用相对尺度元素之间两两对比，对比采用相对尺度 设要比较各准则设要比较各准则C1,C2, , Cn对目标对目标O的重要性的重要性ijjiaCC:A成对比较阵成对比较阵A是正互反阵是正互反阵要由要由A确定确定C1, , Cn对对O的权向量的权向量选选择择旅旅游游地地nn

5、nnnnwwwwwwwwwwwwwwwwwwA21222121211171242/11A成对比较的不一致情况成对比较的不一致情况):(2/ 12112CCa ):(43113CCa ):(83223CCa 一致比较一致比较不一致不一致允许不一致，但要确定不一致的允许范围允许不一致，但要确定不一致的允许范围考察完全一致的情况考察完全一致的情况nwwwW,) 1(21jiijwwa/令权向量),(21TnwwwwwAwnnnnnnwwwwwwwwwwwwwwwwwwA212221212111成对比较完全一致的情况成对比较完全一致的情况nkjiaaaikjkij, 2 , 1,满足满足的正互反阵的正

6、互反阵A称称一致阵一致阵，如，如 A的秩为的秩为1，A的唯一非零特征根为的唯一非零特征根为n A的任一列向量是对应于的任一列向量是对应于n 的特征向量的特征向量 A的归一化特征向量可作为权向量的归一化特征向量可作为权向量对于不一致对于不一致( (但在允许范围内但在允许范围内) )的成对的成对比较阵比较阵A，建议用对应于最大特征根，建议用对应于最大特征根 的特征向量作为权向量的特征向量作为权向量w ，即，即一致阵一致阵性质性质2 4 6 8比较尺度比较尺度aij Saaty等人提出等人提出19尺度尺度aij 取值取值1,2, , 9及其互反数及其互反数1,1/2, , 1/9尺度尺度 1 3 5

7、 7 9 ija相同相同 稍强稍强 强强 明显强明显强 绝对强绝对强的重要性jiCC :jiCC :aij = 1,1/2, ,1/9的重要性与上面相反的重要性与上面相反 心理学家认为成对比较的因素不宜超过心理学家认为成对比较的因素不宜超过9个个 用用13,15,117,1p9p (p=2,3,4,5), d+0.1d+0.9 (d=1,2,3,4)等等27种比较尺度对若干实例构造成对比较阵，种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，算出权向量，与实际对比发现， 19尺度较优。尺度较优。 便于定性到定量的转化：便于定性到定量的转化：二二.一致性检验一致性检验对对A确定不一

8、致的允许范围确定不一致的允许范围已知：已知：n 阶一致阵的唯一非零特征根为阶一致阵的唯一非零特征根为n可证：可证：n 阶正互反阵最大特征根阶正互反阵最大特征根 n, 且且 =n时为一致阵时为一致阵1nnCI定义一致性指标定义一致性指标:CI 越大，不一致越严重越大，不一致越严重RI0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51 n1 234567891110为衡量为衡量CI 的大小，引入的大小，引入随机一致性指标随机一致性指标 RI随机模随机模拟得到拟得到aij , 形成形成A，计算，计算CI 即得即得RI。定义一致性比率定义一致性比率 CR

9、= CI/RI 当当CR0.1时，通过一致性检验时，通过一致性检验Saaty的结果如下的结果如下“选择旅游地选择旅游地”中中准则层对目标的权准则层对目标的权向量及一致性检验向量及一致性检验1135/13/11125/13/13/12/117/14/1557123342/11A准则层对目标的准则层对目标的成对比较阵成对比较阵最大特征根最大特征根 =5.073权向量权向量( (特征向量特征向量) )w =(0.263,0.475,0.055,0.090,0.110)T018.0155073.5CI一致性指标一致性指标随机一致性指标随机一致性指标 RI=1.12 (查表查表)一致性比率一致性比率CR

10、=0.018/1.12=0.0163)个顶点的双向连通竞赛图，存在个顶点的双向连通竞赛图，存在正整数正整数r，使邻接矩阵，使邻接矩阵A 满足满足Ar 0，A称称素阵素阵seAkkklim 素阵素阵A的最大特征根为正单的最大特征根为正单根根 ，对应正特征向量，对应正特征向量s，且，且eAAsskkk ) 1()(0001100011000110A排名为排名为1，2，4，3sskk)(,)(归一化后Ts)230. 0 ,167. 0 ,280. 0 ,323. 0(, 4 . 1用用s排名排名1234(4)1, 2, 3, 4?00010010010011000000101011100011101

11、0ATTTTssss)16,25,21,32,28,38(,)9 ,12,7 ,16,10,15()3 , 4, 3 , 9 , 5 , 8(,)1 , 2, 2, 3 , 3 , 4()4()3()2()1(1234566支球队比赛结果支球队比赛结果Ts)104. 0 ,150. 0 ,113. 0 ,231. 0 ,164. 0 ,238. 0(,232. 2排名次序为排名次序为1，3， 2，5，4，6第九章第九章 概率模型概率模型9.1 传送系统的效率传送系统的效率9.2 报童的诀窍报童的诀窍9.3 随机存贮策略随机存贮策略确定性因素和随机性因素确定性因素和随机性因素随机因素可以忽略随机

12、因素可以忽略随机因素影响可以简单随机因素影响可以简单地以平均值的作用出现地以平均值的作用出现随机因素影响必须考虑随机因素影响必须考虑概率模型概率模型统计回归模型统计回归模型马氏链模型马氏链模型随机模型随机模型确定性模型确定性模型随机性模型随机性模型传送带传送带挂钩挂钩产品产品工作台工作台工人将生产出的产品挂在经过他上方的空钩上运走，若工工人将生产出的产品挂在经过他上方的空钩上运走，若工作台数固定，挂钩数量越多，传送带运走的产品越多。作台数固定，挂钩数量越多，传送带运走的产品越多。背背景景在生产进入稳态后，给出衡量传送带效在生产进入稳态后，给出衡量传送带效率的指标，研究提高率的指标，研究提高传送

13、带效率传送带效率的途径的途径9.1 传送系统的效率传送系统的效率问题分析问题分析 进入稳态后为保证生产系统的周期性运转，应进入稳态后为保证生产系统的周期性运转，应假定工人们的假定工人们的生产周期相同生产周期相同，即生产一件产品的，即生产一件产品的时间相同。假设每人作完一件产品后，要么恰有时间相同。假设每人作完一件产品后，要么恰有空钩经过他的工作台，使他可将产品挂上运走，空钩经过他的工作台，使他可将产品挂上运走，要么没有空钩经过，迫使他放下这件产品并立即要么没有空钩经过，迫使他放下这件产品并立即投入下件产品的生产。投入下件产品的生产。 可以用一个周期内传送带运走的产品数占产品可以用一个周期内传送

14、带运走的产品数占产品总数的总数的比例比例，作为衡量传送带效率的数量指标。，作为衡量传送带效率的数量指标。 工人们生产周期虽然相同，但稳态下每人生产工人们生产周期虽然相同，但稳态下每人生产完一件产品的时刻不会一致，可以认为是随机的，完一件产品的时刻不会一致，可以认为是随机的，并且在一个周期内并且在一个周期内任一时刻的可能性相同任一时刻的可能性相同。模型假设模型假设1）n个工作台个工作台均匀排列，均匀排列，n个工人生产相互独立，个工人生产相互独立，生产周期是常数；生产周期是常数；2）生产进入稳态，每人生产完一件产品的时刻在）生产进入稳态，每人生产完一件产品的时刻在一个周期内是一个周期内是等可能等可

15、能的；的；3）一周期内）一周期内m个均匀排列的挂钩个均匀排列的挂钩通过每一工作台通过每一工作台的上方，到达第一个工作台的挂钩都是空的；的上方，到达第一个工作台的挂钩都是空的；4）每人在生产完一件产品时都）每人在生产完一件产品时都能且只能触到一只能且只能触到一只挂钩挂钩，若这只挂钩是空的，则可将产品挂上运走；，若这只挂钩是空的，则可将产品挂上运走；若该钩非空，则这件产品被放下，退出运送系统。若该钩非空，则这件产品被放下，退出运送系统。模型建立模型建立 定义定义传送带效率传送带效率为一周期内运走的产品数（记作为一周期内运走的产品数（记作s,待定）与生产总数待定）与生产总数 n（已知）之比，记作（已

16、知）之比，记作 D=s /n 若求出一周期内每只挂钩非空的概率若求出一周期内每只挂钩非空的概率p，则，则 s=mp为确定为确定s s，从，从工人工人考虑还是从考虑还是从挂钩挂钩考虑，哪个方便？考虑，哪个方便？ 设每只挂钩为空的概率为设每只挂钩为空的概率为q，则，则 p=1-q如如何何求求概概率率 设每只挂钩不被一工人触到的概率为设每只挂钩不被一工人触到的概率为r，则，则 q=rn 设每只挂钩被一工人触到的概率为设每只挂钩被一工人触到的概率为u，则，则 r=1-uu=1/mp=1-(1-1/m)nD=m1-(1-1/m)n/n一周期内有一周期内有m个挂钩通过每一工作台的上方个挂钩通过每一工作台的

17、上方模型解释模型解释若若(一周期运行的一周期运行的)挂钩数挂钩数m远大于工作台数远大于工作台数n, 则则)2)1(1(12mnnmnnmD 传送带效率传送带效率(一周期内运走一周期内运走产品数与生产总数之比）产品数与生产总数之比）)11(1nmnmD定义定义E=1-D (一周期内未运走产品数与生产总数之比）一周期内未运走产品数与生产总数之比）提高效率提高效率的途径：的途径： 增加增加m 习题习题1当当n远大于远大于1时时, E n/2m E与与n成正比，与成正比，与m成反比成反比若若n=10, m=40, D 87.5% (89.4%)mn2119.2 报童的诀窍报童的诀窍问问题题报童售报：报

18、童售报： a (零售价零售价) b(购进价购进价) c(退回价退回价)售出一份赚售出一份赚 a-b；退回一份赔；退回一份赔 b-c 每天购进多少份可使收入最大？每天购进多少份可使收入最大？分分析析购进太多购进太多卖不完退回卖不完退回赔钱赔钱购进太少购进太少不够销售不够销售赚钱少赚钱少应根据需求确定购进量应根据需求确定购进量每天需求量是随机的每天需求量是随机的优化问题的目标函数应是长期的日平均收入优化问题的目标函数应是长期的日平均收入每天收入是随机的每天收入是随机的存在一个合存在一个合适的购进量适的购进量等于每天收入的期望等于每天收入的期望建建模模 设每天购进设每天购进 n 份，份，日平均收入为

19、日平均收入为 G(n)调查需求量的随机规律调查需求量的随机规律每天每天需求量为需求量为 r 的概率的概率 f(r), r=0,1,2准准备备)()(rncbrnrbarnr赔退回赚售出nbannr)( 赚售出nrnrrnfbarfrncbrbanG01)()()()()()(求求 n 使使 G(n) 最大最大 已知售出一份赚已知售出一份赚 a-b；退回一份赔；退回一份赔 b-cnndrrnpbadrrprncbrbanG0)()()()()()(dndG求解求解将将r视为连续变量视为连续变量概率密度）()()(rprf0dndGcbbadrrpdrrpnn)()(0nndrrpbadrrpcb

20、0)()()()(ndrrpbannpba)()()()(ndrrpcbnnpba0)()()()(cbbadrrpdrrpnn)()(0结果解释结果解释nnPdrrpPdrrp201)(,)(nP1P2cbbaPP21取取n使使 a-b 售出一份赚的钱售出一份赚的钱 b-c 退回一份赔的钱退回一份赔的钱ncbnba)(,)(0rp9.3 随机存贮策略随机存贮策略问问题题以周为时间单位；一周的商品销售量为随机；以周为时间单位；一周的商品销售量为随机；周末根据库存决定是否订货，供下周销售。周末根据库存决定是否订货，供下周销售。（s, S) 存贮策略存贮策略制订下界制订下界s, 上界上界S，当周末

21、库存小于，当周末库存小于s 时订货，时订货，使下周初的库存达到使下周初的库存达到S; 否则，不订货。否则，不订货。考虑订货费、存贮费、缺货费、购进费，制订考虑订货费、存贮费、缺货费、购进费，制订（s, S) 存贮策略存贮策略, ,使使( (平均意义下平均意义下) )总费用最小总费用最小模型假设模型假设 每次订货费每次订货费c0, 每件商品购进价每件商品购进价c1,每件商品每件商品一周贮存费一周贮存费c2,每件商品缺货损失费每件商品缺货损失费c3 ,c3 相当相当于售出价，所以于售出价，所以c1c3 每周销售量每周销售量 r 随机、连续，概率密度随机、连续，概率密度 p(r) 周末库存量周末库存

22、量x, 订货量订货量 u, 周初库存量周初库存量 x+u 一周的销售是集中在周初进行的，即每周一周的销售是集中在周初进行的，即每周贮存量按贮存量按 x+u-r 计计 ，一周内不随时间而改变。，一周内不随时间而改变。（可考虑修改此假设）（可考虑修改此假设）建模与求解建模与求解（s, S) 存贮策略存贮策略0usx确定确定(s, S), 使目标函数使目标函数每周总费用的期望值最每周总费用的期望值最小，即长期经营中每周总费用的平均值小，即长期经营中每周总费用的平均值Suxusx , 0s 订货点，订货点， S 订货值订货值0)(0),()(10uxLuuxLuccuJxxdrrpxrcdrrprxcxL032)()()()()(平均平均费用费用 订货费订货费c0,