第3章运筹学.ppt

第3章运筹学,运筹帷幄之中，决胜千里之外。,本章目的,掌握多目标决策、对策论、系统可靠性、专家系统、层次分析法的原理及它们解决问题步骤;学会运用运筹学的观点来解决采矿实际问题。,3.1多目标决策3.2对策论3.3系统可靠性3.4专家系统3.5层次分析,3.1多目标决策,又称Delphi法，又称专家意思法，就是聘请一批专家各自写出判断意见，然后请另一批专家对这些意见进行评价，也分别写出自己的意见，再反馈给第一批专家，以此往复。这种方法能避免集体判断法的主观误差。,3.1.1原理多目标决策的基础概率论独立观测次数n→∞,得到的参数n,x,δ将趋于“公平”模糊数学得出一种“趋势”“方向”，“综合”评价系统动力学动态、相互抑制,专家集中“专家”的集体智慧进行决策，防止个人主观片面，将各项指标换算成综合可比指标并进行对比，选取较好指标的的一种方法。“权”系数由专家集体决定某些指标的“权”系数，以此为基础计算各方案的综合权系数，以此决定方案的选取。,3.1.2多目标决策的过程,3.1.3多目标决策问题的五要素,决策单元一集目标一集属性决策情况决策规则,（1）决策单元和决策人,决策人（是最小决策单元）分析人（决策人之外的参与者）机器（计算机、绘图仪等）,作用接受输入信息；在内部产生信息；把信息转换为知识；作出决定；,（2）目标和属性,一集意义明确的目标，通常可表示为一递阶结构，如下图所示。,属性代用属性某些场合，有的目标找不到一个或若干个明显属性去直接测量它所达到的程度，但是仍然存在一个或若干个既便于测量又能间接地反映目标达到程度的属性。这种属性称代用属性。例如，论文工作量可用从事论文工作的时间及内容作为代用属性。,,,,目标的属性必须满足可理解性和可测性可理解性其值能标定相应目标达到的程度可测性对给定方案能按某种标度给属性赋值（3）决策情况决策问题的结构和决策环境（4）决策规则最优规则和满意规则,3.1.4多目标决策步骤,1.准备工作题目定目标定指标定专家,,2.定权系数分组取值法重要性序列法累加相对重要性序列,3.方案优选加权相对偏离值最小法,3.1.5多目标决策实例,见书P66。,3.2对策论,对策论又称博奕论，就是从策略的观点出发，研究竞争性、对抗性活动如何取胜的一种方法，它主要应用于与竞争有关的诸多领域。参加斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目的，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最合理的方案。对策论是20世纪20年代产生的，1944年J.冯诺伊曼与O.莫根施特恩合著的竞赛论与经济行为是一部奠基性著作。,3.2.1例子,齐王与田忌赛马，每人出三匹马上、中、下，共比三次，每次败者输四金，当时，同级马中，齐王的优于田忌的如果按上－上、中－中、下－下，田忌必输三千，实际上田忌采用上－下、中－上、下－中，结果赢一千。,齐王上中下胜1田忌下上中胜2共有多少种可能的结果，列成表,3.2.2对策的数学模型及分类,1.数学模型对于只有两方简称二人对策得失之和为零胜者所得等于负者所失的对策，可以列出它们的策略集为Sα{α1，α2，，αm}Sβ{β1，β2，，βn}即α、β分别有m个、n个策略，任一αi，βj构成一个对局。例如α的收入为aij，则β的收入为-aij列表为,可用G{SαSβ,A}表示矩阵策略。,将а的支付表列为矩阵,a支付表,总之，具有对策行为的模型称为对策，它一般具有3个基本要素①局中人，在一局对策中有权决定自己行动方案的参加各方。②策略，在一局对策中可供局中人选择的一个实际可行的完整行动方案。③支付函数，在一局对策中，各局中人所选取的策略形成的策略组称为一个局势，当局势给定后，对策结果也确定了。这时每个局中人都有所得失，“得失”是“局势”的函数，称之为支付函数。,2.对策分类鞍点型非鞍点型“方案状态型”,3.2.3鞍点对策,（1）简单的例子假定G{SαSβ,A}其中A为第一步α的最大收入为8，必先出α2；第二步β的最大收入为5，必先出β1使α损失5；第三步如果β出β1，α必出α3使β损失3；第四步如果α出α3，β必出β4使β损失1α2β1α3β4结束。,（2）思路如果对局双方都是有智谋的话，必然都不敢冒险，而是考虑对方总要使自己处于最不利的地位。为此，双方都应当从坏处着想，力争好的结果。对于上例中的α最坏的结果是支付表中每一行最小之元素即0，-5，1这些最坏的结果中能争取到的最好结果是1。所以，不论β出什么策略，α只要出α3就会使自己至少赢1，否则就有可能吃亏。同理对于β最坏的结果就是支付表中每列最大元素，即3，8，4，1最好的结果是输1。所以，不管α如何出，β出β4能使自己亏得最少。因为当对局双方的最坏情况下的最好结果的绝对值相等时等于1，称此时的对局α3，β4为对策G{Sα,Sβ,A}的最优局势或鞍点。,（3）数学表示对策G{Sα,Sβ,A}Sα{α1，α2，，αm}Sβ{β1，β2，，βn}如果maxminaijminmaxaijai*j*Uijji,则称αi*,βj*为局中α和β的最优策略。式αi*,βj*为对策的鞍点。讨论当U0时，α有利于不败之地的策略，他必不冒险而采取αi*，β也不敢存侥幸心理。当Ut1Ft式中Ft为系统在[0，t时刻内失效（故障）的概率，又称不可靠度或失效函数。,一般地，Rt服从指数分布，如图所示Rte-λte-λ/mλ平均故障率，次/minm平均故障间隔时间，min/次,m1/λ,即平均工作时间。,Rt具有以下特征1R01，系统开始时处于良好状态。2Rt是t的单调减函数，Rt随时间的增加而减小，系统的可靠度在下降。3当时间无限增大时，可靠度逐渐减小，其极限为0。40≤Rt≤1，即系统可靠度的值在0，1之间。5特别地，对于Rte-λte-λ/m，,系统可靠性基本术语（4）有效度At对于可修复系统，系统或元件包括维护的效用在内，保持正常状态的概率称之为有效度。,例如有效度At比可靠度Rt的要求低（或宽）。比如有效度A1200.96表示的是100台设备在规定120小时的工作时间内，当达到120小时那一瞬间，平均有96台设备处于正常工作状态。而不管a．出故障的是哪一台；b．什么时间出的故障；c．中途是否经过修理等等。,但可靠度R1200.96则要求100台设备中有96台设备能无故障地工作120小时，显然可靠度要求是高的。,有效度计算,平均有效度Aμ/μλ1/1λ/μ式中μ平均修复率，次/minλ平均故障时间，min/次,,上式又可写为式中MTBF平均无故障工作时间平均寿命MTTR平均修理时间采矿中常用“有效度”的概念完好率。,,系统可靠性基本术语（5）串、并联系统可靠性参数计算①串联,,②并联Rt1∏1RiA1∏1Ai,③串并联复合系统一般原则是，先算出局部的并联参数，再按串联算出复合系统参数。如下图。先算1、2的并联参数，再算1、2共同与3的串联参数。即A[1-1-A11-A2]A3,3.3.3可靠性在煤矿中的应用,1大型矿井主要运、提设备采用两套。2重要设备采用“备用”。通风系统、供电系统的备用电源线路。主扇风机、主排水泵、排水管路均为两套。备用工作面机、炮采，由于综采折旧费、大修理费高，一般不用）。3设置煤仓。“缓冲”高峰生产，提高后级设备的可靠性。,4尽量减少不必要的生产环节，提高矿井生产的可靠性。1）条件合适改走向长壁为倾斜长壁（少一道运输环节）。国内外已有整阶段整个水平布置一个大功率综采面的设想，这样将使运输环节最少。2）用长距离胶带运输机代替多台短距离刮板运输机。3）一台可弯曲运输机代替两台串联运输机。5尽管采用质量好，效率高的设备及零、配件，提高“元件”可靠性。如用“多绳摩擦提升机”代替单绳普通提升机。,3.4专家系统,Expertsystem,3.4.1专家系统概述,所谓专家系统，实际上是一种以知识为基础的计算机程序系统，具有大量的专门知识，能应用人工智能的理论和技术，根据人类专家的知识和经验进行推理，模拟人类专家进行决策，解决需要专家才能解决的复杂问题。,1历史背景,从原始人的工具、石块、树枝到刀斧是四肢的延伸;从蒸汽机、机床等是肌体的延伸;从无线电、电视是感官的延伸;计算机是人脑的延伸;专家系统是人脑思维的延伸;专家系统是人工智能的一部分;人工智能（ArtificalIntelligenceAI）与空间技术和原子能的应用可称为二十世纪人类杰出的发明。,2什么是专家系统（Expertsystem）ES,ES是一个（或一组）能在某一特定领域内，以人类专家水平去解决该领域中困难问题的计算机程序。,3专家系统的特征,1）专门知识的启发性专家自己的经验很难表达或证明;2）专门知识的专有性好多知识不写到书本里，专家自己所有;3）专门知识的不稳定性实践是衡量真理的标准，专家有的知识也是错误的;4）抽取专门知识的困难性要保证二者的合作也是困难的。,专家系统的主要特点①具有知识信息的处理能力。它用符号描述知识，并用符号按照一定的规则进行逻辑推理。②具有根据不精确知识进行推理的能力。专家有些经验性的知识往往是不很精确的，要解决的问题本身所提供的信息往往也是不确定的，专家系统能综合利用这些模糊的信息和知识进行推理。③具有咨询解释的能力。它能对用户提出的问题和答案的推理过程给出解释，对答案的可信度作出估计。④具有灵活的系统扩充能力。它的知识存储于知识库中，与推理机分离，便于不断扩充知识，随之不断地提高系统的性能。⑤具有从错误中学习的能力。它所具有的解释能力使它易于发现和修改错误。,3.4.2专家系统设计原理,,1专家系统的结构,1）基本结构,最简单的基本结构为,2）流行结构,专家系统通常由5部分组成数据库知识库推理机解释程序知识获取部分人机接口为用户与专家提供方便,专家系统的体系结构,专家、开发人员,用户,知识获取与学习系统,解释程序,用户接口,推理机,工作区间,知识库管理系统,知识库,,,,,,,,,,,,,,数据库,,2知识库知识的表示RULES,1）逻辑表示法如x学习好用Sx表示x工作好用Wx表示x学习工作都好Sx∧Wx若x学习好则x工作好Sx→Wx又如x学习不好则x工作不好╕Sx→╕Wx又如没有人不犯错误先设Mx表示x是人F（x）表示x犯错误则╕XMX∧╕FX其中╕表示否定，表示存在,2）语义网络表示法,所谓语义是指语言学的符号和表达式同它所描述的对象之间的关系。语义网络是一种以网络格式表示人类知识构造的一种形式。语义网络既可作为人类联想记忆的心理学模型，又可作为计算机内部表达知识的一种格式。,语义网络的基本特点是由节点和连接街点的弧组成。如“一切教师都是教职员”这一事实，可以用两个节点和连接该节点的弧表示。,而“一切教职员都是学校的工作人员”、“一切教师都是教职员”和“A是一位教师”这三个事实可用下图表示。,3）基于规划的表示法（产生式表示法）,IFTHEN如IF动物会飞THEN动物是鸟IF物质PH7THEN物质是酸性的,4）其他表示法,①框架表示法兄弟二人玩哥哥打弟弟一下弟弟反应有情况一情况二情况三回打哭不在乎类型打主动者哥被动者弟可能结果情况一框架情况二框架情况三框架另外，表示墙，有门，有窗②特征表示法性别（档案）年龄③剧本表示法④过程表示法,数据库（FACTS）,存放所有的原始数据资料，求解过程中的中间数据、动态数据查询表、最后结果及推进记录。如动物识别，动物是肉食动物，有爪,,4推理机,1）匹配IFxzThenyz则称A与z匹配IFAzThenyz又如IF小李是老李的儿子X是老李的儿子THEN小李是X,2）回溯正向推理从事实推出结论反向推理假设结论再找事实（1）正向推理用户提供事实存放在数据库FACTS中，然后a.推理机用这些事实与知识库里的规则的前提进行匹配，b.如匹配成功将知识库中这一规则的结论放入FACTS中，否则进一条规则匹配，c.再用修改后的FACTS重复a，b直到得出结论或事实加入FACTS中。如下图所示,取RULEI的前提,令I1,取RuleI的结论,新事物加入FACTS,BEGIN,在FACTS中,,,,,是否新的,,,IK,,II1,,,,,END,,,,N,N,N,Y,正向推理框图,（2）逆向推理用户提出一个（一组）假设a.验证假设是否在数据库FACTS中，若在，则假设成立，推理结果或验证其它假设，b.判断假设是否是论据节点，若是，向用户提问，若不是，进行下一步，c.找出结论部分包含这个事实的那些规则，把这些规则的前提作为新的假设，d.重复a，b，c，直到某一假设成立或所有假设不成立。如下图所示,逆向推理框图,3.5层次分析法,AnalyticHierarchyProcess,3.5.1概述,问题的提出日常生活中有许多决策问题。决策是指在面临多种方案时需要依据一定的标准选择某一种方案。例1购物买钢笔，一般要依据质量、颜色、实用性、价格、外形等方面的因素选择某一支钢笔。买饭，则要依据色、香、味、价格等方面的因素选择某种饭菜。例2旅游假期旅游，是去风光秀丽的苏州，还是去迷人的北戴河，或者是去山水甲天下的桂林，一般会依据景色、费用、食宿条件、旅途等因素选择去哪个地方。,例3择业面临毕业，可能有高校、科研单位、企业等单位可以去选择，一般依据工作环境、工资待遇、发展前途、住房条件等因素择业。例4科研课题的选择由于经费等因素，有时不能同时开展几个课题，一般依据课题的可行性、应用价值、理论价值、被培养人才等因素进行选题。,面临各种各样的方案，要进行比较、判断、评价、最后作出决策。这个过程主观因素占有相当的比重给用数学方法解决问题带来不便。T.L.saaty等人20世纪在七十年代提出了一种能有效处理这类问题的实用方法。,层次分析法（AnalyticHierarchyProcess,AHP这是一种定性和定量相结合的、系统化的、层次化的分析方法。过去研究自然和社会现象主要有机理分析法和统计分析法两种方法，前者用经典的数学工具分析现象的因果关系，后者以随机数学为工具，通过大量的观察数据寻求统计规律。近年发展的系统分析是又一种方法，而层次分析法是系统分析的数学工具之一。,层次分析法的基本思路,与人们对某一复杂决策问题的思维、判断过程大体一致。,选择钢笔,质量、颜色、价格、外形、实用,钢笔1、钢笔2、钢笔3、钢笔4,质量、颜色、价格、外形、实用进行排序将各个钢笔的质量、颜色、价格、外形、实用进行排序经综合分析决定买哪支钢笔,,3.5.23层次分析法的基本原理、步骤,一般分为三层，最上面为目标层，最下面为方案层，中间是准则层或指标层。例1的层次结构模型,准则层,方案层,目标层,,,,,,1建立层次结构模型,,例2层次结构模型,,,,准则层A,方案层B,目标层Z,若上层的每个因素都支配着下一层的所有因素，或被下一层所有因素影响，称为完全层次结构，否则称为不完全层次结构。,,要比较它们对上一层某一准则（或目标）的影响程度，确定在该层中相对于某一准则所占的比重。（即把个因素对上层某一目标的影响程度排序）,用表示第个因素相对于第个因素的比较结果，则,设某层有个因素，,则称为成对比较矩阵。,上述比较是两两因素之间进行的比较，比较时取19尺度。,2构造成对比较矩阵,尺度,第个因素与第个因素的影响相同,,第个因素比第个因素的影响稍强,第个因素比第个因素的影响强,第个因素比第个因素的影响明强,第个因素比第个因素的影响绝对地强,含义,比较尺度（19尺度的含义）,2,4,6,8表示第个因素相对于第个因素的影响介于上述两个相邻等级之间。不难定义以上各尺度倒数的含义，根据。,由上述定义知，成对比较矩阵,则称为正互反阵。比如，例2的旅游问题中，第二层A的各因素对目标层Z的影响两两比较结果如下,满足一下性质,1,1/2,4,3,3,2,1,7,5,5,1/4,1/7,1,1/2,1/3,1/3,1/5,2,1,1,1/3,1/5,3,1,1,分别表示景色、费用、居住、饮食、旅途。,由上表，可得成对比较矩阵,旅游问题的成对比较矩阵共有6个（一个5阶，5个3阶）。,问题两两进行比较后，怎样才能知道，下层各因素对上层某因素的影响程度的排序结果呢,层次单排序确定下层各因素对上层某因素影响程度的过程。用权值表示影响程度，先从一个简单的例子看如何确定权值。例如一块石头重量记为1，打碎分成各小块，各块的重量,分别记为,则可得成对比较矩阵,由右面矩阵可以看出，,3层次单排序及一致性检验,5.的任一列行都是对应于特征根的特征向量。,在正互反矩阵中，若,则称为一致阵。,即，,但在例2的成对比较矩阵中，,一致阵的性质,表示下层第个因素对上层某因素影响程度的权值。,若成对比较矩阵是一致阵，则我们自然会取对应于最大特征根的归一化特征向量，且,定理阶互反阵的最大特征根，当且仅当时，为一致阵。,若成对比较矩阵不是一致阵，Saaty等人建议用其最大特征根对应的归一化特征向量作为权向量，则,（为什么）,这样确定权向量的方法称为特征根法.,定义一致性指标,其中为的对角线元素之和，也为的特征根之和。,则可得一致性指标,定义随机一致性指标,随机构造500个成对比较矩阵,随机一致性指标RI的数值,的不一致程度在容许范围之内，可用其归一化特征向量作为权向量，否则要重新构造成对比较矩阵，对加以调整。,一致性检验利用一致性指标和一致性比率0.1及随机一致性指标的数值表，对进行检验的过程。,一般，当一致性比率,时，认为,确定某层所有因素对于总目标相对重要性的排序权值过程，称为层次总排序从最高层到最低层逐层进行。设,,,,,,,,,,,,,,,,,,,,对总目标Z的排序为,的层次单排序为,4层次总排序及其一致性检验,即层第个因素对总目标的权值为,层的层次总排序为,,A,B,当时，认为层次总排序通过一致性检验。到此，根据最下层（决策层）的层次总排序做出最后决策。,设层对上层层中因素的层次单排序一致性指标为，随机一致性指为，则层次总排序的一致性比率为,5层次总排序的一致性检验,1.建立层次结构模型该结构图包括目标层，准则层，方案层。,3.计算单排序权向量并做一致性检验,2.构造成对比较矩阵,从第二层开始用成对比较矩阵和19尺度。,对每个成对比较矩阵计算最大特征值及其对应的特征向量，利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通过，特征向量（归一化后）即为权向量；若不通过，需要重新构造成对比较矩阵。,层次分析法的基本步骤归纳如下,进行检验。若通过，则可按照总排序权向量表示的结果进行决策，否则需要重新考虑模型或重新构造那些一致性比率较大的成对比较矩阵。,计算最下层对最上层总排序的权向量。,4.计算总排序权向量并做一致性检验,利用总排序一致性比率,用Excel计算层次分析问题,参考书本P95。,