生活中的预测与决策

生活中的预测与决策任课教师：薛焕斌E-mail:QQ:51054616预测和决策的意义“凡事预则立，不预则废.”这表明预测的重要性。事实上只有以预测为依据的决策，才是有远见卓识的决策。下面是几个有关的例子：1.美国克莱斯勒汽车公司，在20世纪70年代石油危机的冲击中深受其害，1979年9个月内损失7亿多美元；与此相反，日本丰田汽车公司，却在此次经济浪潮中发展壮大。究其原因是市场预见与经营决策的差异。2.第二次世界大战期间，盟军基于对气候的可靠预测，抓住暴风雨的空隙，于1944年6月6日执行诺曼底登陆计划，获得大捷；而希特勒由于对气候作了错误的判断，损失惨重，大败而终。3.1980年，我国有两艘远洋轮，同时从太子港返航。其中一艘船对航线分析预测不当，决策失误，一路上台风侵袭耗时29天；另一艘船预测与决策妥当，返航时间缩短为16天。第一章灰预测与灰决策概论一、灰色系统理论产生的科学背景现代科学技术在高度分化的基础上高度综合的大趋势，导致了具有方法论意义的系统科学学科群出现。系统科学揭示了事物之间更为深刻、更具有本质性的内在联系，大大促进了科学技术的整体化进程；许多科学领域中长期难以解决的复杂问题随着系统科学的出现迎刃而解；人们对自然界和客观事物演化规律的认识也由于系统科学的出现逐步深化。二、灰色系统的基本原理在灰色系统理论创立和发展过程中，邓聚龙教授发现并提炼出灰色系统的基本原理。这些基本原理具有十分深刻的哲学内涵。（1）差异信息原理——“差异”是信息，凡信息必有差异；（2）解的非唯一性原理——信息不完全、不确定的解是非唯一的；（3）最少信息原理——灰色系统理论的特点是充分开发利用已占有的“最少信息”；（4）认知根据原理——信息是认知的根据；（5）最新信息优先原理——新信息对认知的作用大于老信息；（6）灰性不灭原理——“信息不完全”（灰）是绝对的。三、灰色系统理论的主要内容灰色系统理论进过20多年的发展，现已基本建立起一门新兴学科的结构体系。其基本内容包括以灰色代数系统、灰色方程、灰色矩阵等为基础的理论体系，以灰色序列生成为基础的方法体系，以灰色关联空间为依托的分析体系，以灰色模型（GM）为核心的模型体系，以系统分析、评估、建模、预测、决策、控制、优化为主体的技术体系。

我们这门课只要学习的是：灰数、建模、预测、决策(4)连续灰数与离散灰数在某一区间内取有限个值或可数个值的灰数称为离散灰数，取值连续地充满某一区间的灰数称为连续灰数。(5)黑数与白数当时，即当的上、下皆为无穷时，称为黑数；当且时，称为白数。为了讨论方便，我们将黑数与白数看成特殊的灰数。(6)本征灰数与非本征灰数本征灰数是指不能或暂时还不能找到一个白数作为其“代表”的灰数，比如一般的事前预测值、宇宙的总能量、准确到秒或微秒的“年龄”等都是本征灰数。非本征灰数是指凭先验信息或某种手段，可以找到一个白数作为其“代表”的灰数。我们称此白数为相应灰数的白化值，记为，并用表示以a为白化值的灰数。如估计某人的托福考试成绩可能在600分左右，可将600作为该考生托福考试成绩的白化数，记为第二章问题分析一、决策与我们的关系：“事事有决策、时时要决策”（一）决策的风险是决策就会有风险，不同的决策需要承担的风险完全不一样。

（三）正确决策的关键正确决策的关键是：对问题的正确判断。你能不能正确地判断问题？要清楚地知道自己到底想要什么。对环境的客观评估。你到底处于什么样的环境之中？你对这个环境的了解到底有多少？对资源的有效评价。你要想解决问题，要想做出一个决策，你手上有什么资源？对困难的理性分析。这里面强调的一个词就是“理性”，而不是感性。对风险的充分准备。我们对一个决策所可能产生的风险要有充分的准备，准备得充分与否直接决定决策的成败。决策的支持体系三要素：要有相关的数据要掌握一种推理的方法推理要符合逻辑二、中华传统文化与决策思维模式（一）中华传统文化对决策的影响要“高深莫测”，还要“大智若愚”即使内心“五内如焚”，但外表还要“不动声色”三、决策价值观的差异注重“过程”的决策观，尽量把问题放在决策的前面；注重“结果”的决策观，总习惯于把问题放在决策的前面；四、决策的模型及分析工具（一）可使用的模型可使用的模型包括一些简单的方法还有一些比较复杂的模型。比如：柱状图、树形图、扇形图、曲线图等分析工具；和SWOT分析法、麦肯锡7S模型、EVA分析法等模型。（二）需建立的模型关注关键结果领域——进行因果分析柏拉图法柏拉图法又称排列图法或主次因素分析图法，由19世纪意大利学者柏拉图在分析意大利社会财富分布状况时首先提出。他在研究中发现，少数人占有社会上的大量财富，而绝大多数人处于贫困状况，即发现了“关键的少数和次要的多数”的关系。鱼骨图分析法鱼骨图分析法是一种因果分析方式，指明问题发生的区域，并找出该区域的因素五、分析和解决问题的逻辑思维逻辑有时也指逻辑学，其实就是研究主观思维的客观形式及其规律的科学。第三章序列算子与灰色序列生成事实上，研究系统的行为特征，得到的数据往往是一串确定的白数，我们把它看成是某个随机过程的一条轨道或实现，或是看成灰色过程的白化值，这并没有本质上的区别。如何通过系统行为特征数据研究其发展规律，不同的方法思路也不一样。随机过程是以先验概率为出发点，研究数据的统计规律。这种方法是建立在大量数据的基础上的。但有的时候，即使有了大量的数据也未必一定能找到统计规律。因为概论论或随机过程中研究的典型分布十分有限，对于非典型的分布过程（如第四章一个有效的问题

分析与决策模型1.状况评估查明具体难题排出轻重缓急计划行动步骤准备采取行动2.问题分析描述面临问题识别可能原因评估可能原因确认真正原因3.方案决策明确决策目的评估选择方案评估决策方案作出最终决策4.应变措施识别潜在问题找出可能原因采取预防措施计划应变措施状况评估案例模拟——X公司的一次部门经理会议X公司的起重机销售额下降，成本不断增加，为此公司总裁召集各个部门经理开会，要求大家找到问题并采取行动。生产部门认为——是采购和运输问题。具体说来就是采购的零配件质量不好，而且在运输上又经常中断，使得他们的生产时断时续，十分不稳定。市场部门认为——是经济形势的影响。总体来说，他们认为这没什么大不了，主要是整体经济形势下滑，造成整个行业出现了问题，而不是公司内部的问题。销售部认为——对竞争对手不了解。他们认为竞争对手越来越强大，而公司对此熟视无睹，没有对策，甚至根本不知道竞争对手在干什么。开发部认为——是技术优势不明显。主要是因为公司部给钱，研发经费减少，结果很多技术问题都解决不了。因此，我们需要一个系统的程序来帮助解决难题，它就是状况评估法。什么是“难题”——“难题”就是那些需要关注，并且采取行动解决的事件。而且难题不仅指困难，也需要涉及事件改进的可能。状况评估法的作用：找出难题并且分解和控制问题；体统分析资料后排出轻重缓急；解决难题的计划和采取的方法。一、查明具体的难题1、列出难题想要查明具体的原因是什么、首先要做的就是列出一些问题。一般来说，我们可以提出下面一些常见的问题：到底发生了什么偏差？应实施什么样的计划？应该做出怎么的决定？预计将来有什么变化？会存在什么样的机会？X公司的难题1销售额在不断地下降2产品的成本增加很快3分销商有压货的现象4关键零部件存量偏低5市场竞争压力在增加6公司缺乏先进的技术

事实上，我们提出问题的最终目的，就是要列明存在的各种难题，这样才能在后面的步骤中做到有的放矢。通过上面的示例，我们就可以列出X公司的难题一览表2、澄清难题的方法——做出有效提问列出问题之后还需要进一步澄清问题，把一些复杂的问题分解成简单的、一目了然的和具体的难点，让原本笼统的、复杂的难题变得具体和现实。如何来澄清难题呢？提问你的实际意思是指？你具体讲的问题是？是否还有其他问题？你有什么具体证据？什么偏差造成问题？X公司难题的澄清笼统的难题：生成成本在不断增加。具体的难题：成本增加具体原因是什么？提供证据：某些原材料成本上升并多变。3、问题的分解X公司的问题分解：液压件的成本增加了20%；公司产品在最近只中了3个标；必须重新部署产品的竞争策略；特种钢材价格在不断上升；在少占用资金的前提下提高库存量。案例某位女生遇到了以下几个问题：第一，男朋友经常不陪她一起吃饭。第二，男朋友对她态度不好。第三，晚上经常有人找他出去。在查明具体难题这个环节里，我们要做到：第一，列出难题；第二，通过有效提问的方式澄清难题。二、把握难题的轻重缓急X公司的难题1销售额在不断地下降2产品的成本增加很快3分销商有压货的现象4关键零部件存量偏低5市场竞争压力在增加6公司缺乏先进的技术1、制定缓急程度的标准一般来说，我们对问题的缓急程度很难达成共识，往往是仁者见仁、智者见智。所以，为了让我们能对问题轻重缓急程度作出有效的判断，就要设法找到一种合适的方法。制定标准：必须易于掌握和使用；又有很明显的灵活性；基于问题的各个方面。2、严重性、紧急性和发展性衡量问题缓急程度的标准：问题分类第一类，严重性；第二类，紧急性；第三类，发展性判断“三性”的提问1影响我们的因素是什么？2具体会影响到哪些人？3采取行动的最后期限到底是什么时候？4什么时候开始行动是最好的？5发展的趋势如何？6如果什么都不做，会有什么后果？3、问题级别评估并得出结论列出难题事项澄清难题严重性紧急性发展性1最近男朋友经常不一起吃饭次数不断增加低低中2男朋友对她态度不好男朋友工作太忙低低中男朋友开始讨厌她中中高3晚上经常有人找他出去男朋友的公司太忙低低高找他出去的是个女人高高高4、问题的变化与解决我们做好了问题的级别评估，接下来还要防止问题发生变化。这是因为：难题越临近到最后期限，越会增加它的紧急性；如果一旦出现新的难题，问题的缓急程度就需要重新做出判断。三、解决问题的计划与步骤当我们知道了存在什么问题、明确了问题的轻重缓急，也就知道了哪件事情是第一重要的，哪件次之。接下来就需要按照它们的轻重缓急去解决问题，那就需要知道解决问题的计划和步骤是什么。（一）第一轮提问是否需要知道偏差的原因？是否需要去做出一个选择？是否需要采取行动或计划？是否需要进一步澄清问题？实际和预计之间有没有偏差？这种偏差的原因是明确的，还是不明确？我们采取行动之前，需不需要做出进一步分析？（二）进一步提出问题能不能确定我们需要采取行动？能不能确定我们需要实施的计划？其他方面的改变会不会影响我的计划？（三）潜在问题分析【案例】行军问题问题分析还是决策分析列出难题事项澄清难题严重性紧急性发展性问题分析决策分析1最近男朋友经常不一起吃饭次数不断增加低低中√2男朋友对她态度不好男朋友工作太忙低低中√男朋友开始讨厌她中中高√3晚上经常有人找他出去男朋友的公司太忙低低高√找他出去的是个女人高高高√重点提示：如果能下结论，我们就要做决策分析；如果不能下结论，那就要进一步做问题分析。四、准备采取行动在前面的内容中，我们讲述了再状况评估中，不但要知道问题，要澄清问题，要分析问题的紧急性、严重性、和发展性，我们还需要再对它做出一个评估，明确这些问题中的哪些是我们需要做进一步的问题分析，哪些需要做决策分析。（一）计划的内容我们到底需要做什么？我们什么时候做？谁来参与做？（二）计划行动的程序计划行动的程序主要包含：收集信息分析创造性（如何解决问题）承诺批准执行培训奖励激励【案例】问题分析决策分析结果状况分析谁来做做什么啥时候男朋友确实不对劲抓现形证据确凿，铁证如山姐妹团抓现场就今天正中下怀，拱手相送晓厉害义正词严，最后通牒全家上跪搓板定明天屡教不改，死猪一个唤内疚患难与共，良心何在靠自己烛光餐星期六往事如烟，不堪回首去整容脱胎换骨，再比高低美容院全系列下星期投资太大，风险太高换环境搬家旅游，斩断情丝旅行社东南亚马上走藕断丝连，徒劳一场小结环节提出问题列出难题发生了什么偏差？应该做什么决定？应实施什么计划？预计会有何变化？会存在什么机会？澄清难题你的意思是指…？具体的讲问题是…？是否有其它问题？你有什么证据？什么偏差造成问题？严重性、紧急性、发展性影响是什么？会影响哪么人？采取行动的最后期限？何时开始行动？发展趋势如何？如果什么都不做会怎样？注意：如果能下结论，我们就要做决策分析；如果不能下结论，那就要进一步做问题分析。计划行动需要做什么？何时做？谁来参与？信息？分析？创造性？承诺？批准？执行？培训？奖励？问题分析识别可能的原因评估可能的原因描述面临的问题确认真正的原因解决问题的三大常见误区1.妄下结论2.错误定义问题3.盲目行动1.妄下结论第一，信息不够，却认为自己已经把握 问题； 第二，只用支持自己观点的信息来论证 自己的结论； 第三，故意忽略和自己的假设不相符的 信息，甚至去攻击和否定它们。2.错误的定义问题第一，信息过多，我们看到很多信息 视乎都跟问题有关；第二，我们没有办法去分辨哪些信息是 真正重要的；第三，面对复杂的信息，我们很难判断 这些信息到底有没有利用价值。3.盲目行动第一，因为时间、事件的紧迫，往往会 同时采取多种行动；第二，总是希望侥幸碰到解决问题的方 法；第三，没有核查、确认行动是否对解决 问题真正有利，马上就采取行动第四，即使偶尔问题得到了解决，也往 往不知道怎么解决的。决策分析评估选择方案评估决策风险明确决策目的作出最终决策【案例】她该嫁给谁 某女孩有四个男朋友可以选择，第一个叫李酷毙；第二个叫张帅呆；第三个叫罗老实；第四个叫王大款。因为她一个人不能同时嫁给四个人，所以只能去挑选其中的一个。决策目标的分类：1、必须要求目标；2、愿望要求目标；必须目标的判断第一，年龄20岁到50岁；第二，有固定的工作和收入；第三，一年之内可以和她结婚。愿望目标评估第一，英俊潇洒；第二，有楼有车；第三，收入丰厚；第四，存款大把；第五，嫁过去要当家作主；第六，财产共享。评估选择方案决策明示：方案1方案2方案3方案4选择结婚对象李酷毙张帅呆罗老实王大款目标分类：必须要求目标20~50岁，男性19223048有固定工作收入游荡有工作有工作大老板一年之内结婚可以可以可以可以愿望要求分/分值分/分值分/分值张帅呆罗老实王大款英俊潇洒9帅呆了1090相貌平平654大腹便便218有楼有车7无楼、自行车214祖楼、桑塔纳535别墅、奔驰963收入丰厚5月入1千210月入5千52510万以上945存款大把6存款1万16存款10万318存款千万954当家作主8父母做主00自己做主540毫无疑问972财产共享10只有遗憾00可惜太少330分你一半10100总分120202352评估风险【案例】生产手机的公司，要在销售旺季到来前向市场推出新型手机K。公司给出50万的投资资金并下达任务销售额要比去年同期提升两个百分点。选择方案1选择方案2广告新包装找出不利后果：评估威胁找出不利后果：评估威胁可能性、严重性可能性、严重性若广告公司未能按时准备好，会错过销售旺季。如不能实现销售预测，则两个百分点的增长就实现不了。如市场不像预期一样接受广告宣传，则反馈就会缺乏评判。如新包装不能按时准备好，就会错过销售旺季。如广告公司评判不准确，业绩增长的目标就难以实现。如包装盒达不到质量要求，我们就会错过销售时机。如竞争者的改进更优越，我们便不会增加市场份额。如成本预测过低，我们便会超出预算。如需要持续广告宣传一支持销售，利润就变得很小。应变措施找出可能原因采取预防措施识别潜在问题计划应变措施潜在问题分析一个系统化的过程，可以确保计划和方案的成功辨识潜在问题称述行动制定计划列出潜在问题评估风险性最后达到的结果是什么？为达到最后结果，准备采取什么行动？关键步骤有哪些？导致错误的原因是什么？潜在问题发生的可能性是什么？如问题真的发生，严重性事什么？找出可能原因考虑潜在问题产生的原因是什么？这些潜在问题发生的原因是什么？是否还有其他原因？采取预防措施针对可能原因找出行动方案针对每个原因采取什么方案？要减少潜在问题发生的可能，应采取什么方案？计划应急措施制定方案，减少可能的影响如问题真的发生，采取什么方案可减少影响？为应急措施设定“预警信号”要减少潜在问题影响的严重性，应采取什么方案？使应急措施发生效应的动力是什么？第五章灰色关联分析数理统计中的回归分析、方差分析、主成分分析等都是用来进行系统分析的方法。这些方法都有下来不足之处：（1）要求有大量数据，数据少量就难以找出统 计规律；（2）要求原本服从某个典型的概率分布，要求 各因素数据与系统特征数据之间呈线性关系 且各因素之间彼此无关。这种要求往往难以 满足。（3）计算量大，一般靠计算机帮助。（4）可能出现量化结果与定性分析结果不符的 现象，导致系统的关系和规律遭到歪曲和颠 倒。灰色关联因素和关联算子集进行系统分析，选准体统行为特征的映射量后，还需进一步明确影响系统主行为的有效因素。如要作量化研究分析，则需对系统行为特征映射量和各有效因素进行恰当处理，通过算子作用，使之化为数量级大体相近的无量纲数据，并将负相关因素转化为正相关因素。命题5.1初值化算子、均值化算子和区间化算子皆可使系统行为序列无量纲化，且在数量上归一。一般地，初值化算子、均值化算子和区间化算子不宜混合、重叠作用，在进行系统因素分析时，可根据实际情况选用其中一个。命题5.2任意行为序列的区间值像有逆化像按照定理5.1定义的算式可得灰色关联度的计算步骤如下：例某市工业、农业、运输业、商业各部门的行为数据如下：工业：X1=(x1(1),x1(2),x1(3),x1(4))=(45.8,43.4,42.3,41.9)农业：X2=(x2(1),x2(2),x2(3),x2(4))=(39.1,41.6,43.9,44.9)运输业：X3=(x3(1),x3(2),x3(3),x3(4))=(3.4,3.3,3.5,3.5)商业：X4=(x4(1),x4(2),x4(3),x4(4))=(6.7,6.8,5.4,4.7)分别以X1，X2为系统特征序列，计算灰色关联度xy案例:根据某地区10年农民人均收入年纯收入的资料，和该地区相应年份的销售额资料，预测该地区市场销售额。观察期资料见表1根据表1中x与y观察期十年资料绘制散点图散点图表明，x与y存在相关关系，且散点基本集中在一条直线上，说明相关程度较高，农民年人均纯收入（x）与销售额（y）表现较高程度的直线正相关。可以采用一元线性相关回归分析预测模型2.

应用最小平方法求回归方程中的参数，建立预测模型求参数a、b的标准方程为：

∑y＝na＋b∑x∑xy＝a∑x＋b∑x2解得方程为：求解a、b值：则回归方程为：ŷ＝99.121＋0.1x＝99.121＝0.1灰色预测模型——GM(1,1)模型第六章图与网络模型1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1所示。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。第六章图与网络模型§1图与网络的基本概念§2最短路问题§3最小生成树问题§4最大流问题§5最小费用最大流问题§1图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图6-1就是一个表示这种关系的图。(v1)赵(v2)钱(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图6-1当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图6-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图6-2如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图6-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。思考：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。ABCDEF分析：点表示项目，边表示两个项目有同一名运动员参加目的：在图中找出点序列，使得依次排列的两个点不相邻，就找到了每名运动员不连续参加两项比赛的安排方案A、C、B、F、E、D§2最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。最短路问题引例下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从v1到v8：P1=（v1，v2，v5，v8）费用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用3+2+10+2+4=21P3=……从v1到v8的旅行路线从v1到v8的路。旅行路线总费用路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363几个概念路：设p是D中一个首尾相连的弧的集合，如果vs是它的第一条弧的始点，vt是它的最后一条弧的终点，则称它是以点vs为始点，以点vt为终点的一条路。路长：路p中所有弧的权值的和称为路p的长，记为设图D=（V，A）是一有向网络

v2v523464v3v1V4v6121061210v8v9v72363设P是以点vs为始点，以点vt为终点的所有路的集合，如果,且，则称p0是以点vs

为始点，以点vt为终点的最短路。而称其路长为点

vi到点vj的距离，记为。注意：在有向网络中,一般最短路及一点到另一点的距离最短路问题是重要的最优化问题之一，可以直接应用于解决生产实际的许多问题:管道铺设、线路安排、厂区布局等。而且经常被作为一个基本工具来解决其他的优化问题。最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法求解最短路问题的Dijkstra算法条件：当所有

wij

≥0时，用来求给定点vs到任一个点vj最短路的公认的最好方法。事实：如果P是D中从vs到vj的最短路，vi是P中的一基解个点，那么，从vs沿P到vi的路是从vs到vi的最基解短路。Dijkstra算法是Dijkstra在1959年提出的，可用于求解指定两点间的最短路问题，或从指定点到其余各点的最短路问题。由于其以标号为主要特征，又称为标号法。v1v2v3v4v5最短路的子路是最短路Dijkstra算法基本思想

从始点vs出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)

1.标号P（固定标号或永久性标号）——从始点vs到该标号点vj的最短路权P(vj)

。2.标号T（临时性标号）——从始点vs到该标号点vj的最短路权上界T(vj)

。j

,P(vj)j,T(vj)该方法的每一步就是去修改T标号，并且把某一个具T标号的点改变为具有P标号的点，从而使D中具P标号的顶点数多一个，至多经过n-1步，就可以求出始点vs到各点的最短路。前点标号j

——表示始点vs到vj的最短路上vj的前一点。Dijkstra算法步骤：

第二步：考虑满足条件①的所有点；②vi具有P标号;vj具有T标号;修改vj的T标号为，并将结果仍记为T(vj)第一步：始点标上固定标号,其余各点标临时性标号

T(vj)=,j1;第三步：若网络图中已无T标号点，停止计算。否则,令，s为T标号点集,然后将的T标号改成P标号，转入第二步。v1,6图上标号法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

∞v1,3M,∞M,∞M,∞v1,1v1,1永久标号永久标号临时标号v1出发到v8去，使总费用最小的旅行路线v1,6图上标号法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,∞v1,3M,∞M,∞M,∞0,0v1,1v4,11v1,3永久标号临时标号v1出发到v8去，使总费用最小的旅行路线v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v1,1M,∞M,∞M,∞1,3图上标号法v4,11v1,3v1,6v3,5v3,5永久标号临时标号v1出发到v8去，使总费用最小的旅行路线v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞M,∞v1,3图上标号法v3,5v2,6v2,6永久标号临时标号v1出发到v8去，使总费用最小的旅行路线v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞v1,3v5,12v5,9v5,9图上标号法v3,5v2,6永久标号临时标号v5,10v1出发到v8去，使总费用最小的旅行路线v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v5,12v1,3v5,9v5,12v3,5v2,6图上标号法永久标号临时标号v5,10v1出发到v8去，使总费用最小的旅行路线v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v1,3v5,12v3,5v2,6图上标号法v5,9永久标号临时标号标号结束反向追踪v1出发到v8去，使总费用最小的旅行路线Dijkstra算法步骤：

第二步：考虑满足条件①的所有点；②vi具有P标号;vj具有T标号;修改vj的T标号为，并将结果仍记为T(vj)第一步：始点标上固定标号,其余各点标临时性标号

T(vj)=,j1;第三步：若网络图中已无T标号点，停止计算。否则,令，s为T标号点集,然后将的T标号改成P标号，转入第二步。例1求下图中v1到v6的最短路采用Dijkstra算法，可解得最短路径为 v1→v3→v4→v6v23527531512v1v6v5v3v4无向网络:负权弧时。wijvivjwijwijvjvi无向网络中，最短路→最短链。

多个点对之间最短路？v1v2v312-3Dijkstra算法失效Dijkstra算法注意的问题逐步逼近算法路矩阵算法5727461263202657710v3v1v2v4v5v6v7练习：求如下无向网络中v1到v7的最短链Dijkstra算法求最短链最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法逐次逼近算法思想

该公式表明，P(1)1j中的第j个分量等于P(0)1j的分量与基本表(权矩阵)中的第j列相应元素路长的最小值，它相当于在v1与vj之间插入一个转接点(v1,v2,…,vn中的任一个，含点v1与vj)后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而P(k)1j中的每一个分量则随着k的增加而呈不增的趋势！v1v2v312-3用于计算带有负权弧指定点v1到其余各点的最短路j=1,2,…,n.k=1,2,…,t≤n.2.计算逐次逼近算法基本步骤

j=1,2,…,n.1.令其元素即是v1到vj的最短路长。3.当出现时，v1v2v312-3例计算从点v1到所有其它顶点的最短路解：初始条件为以后按照公式进行迭代。

直到得到，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下标追踪路径基本表空格为无穷大v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下标追踪路径基本表空格为无穷大v2v523464v3v1v4v6121061210v8v9v72363已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人，G处60人,问小学应建在哪一个村子，使学生上学最方便（原则①所有人走的总路程最短；②尽可能公平。）。最短路问题算例1(选址问题)AGFECB522747163D26最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法

某些问题需要求网络上任意两点间的最短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。这里介绍Floyd在1962年提出的路矩阵法，它可直接求出网络中任意两点间的最短路。Floyd算法(路矩阵法)思想

考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络D0，记wij为弧（vi，vj）的权。

在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路记为,则一定有vivjv1wijFloyd算法(路矩阵法)思想

网络D=（V，A，W），令U=(dij)nn，表示D中vi到vj的最短路的长度。dij

再在D1中加入v2及D中与vi，vj，v1，

v2相关联的弧，得D2，D2中vi到vj的最短路长记为，则有Floyd算法(路矩阵法)思想Floyd算法(路矩阵法)步骤设有有向网络D=（V，A），其权矩阵为A=(aij)n╳n，如下构造路矩阵序列：则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。

令权矩阵A为初始路矩阵D（0），即令D（0）=A2.依次计算K阶路矩阵D（K）=（d(k)ij）n╳n,k=1,2,…,n，这里路矩阵序列的含义K阶路矩阵D（K）其中的元素表示相应两点间可能以点v1、v2、…、vk为转接点的所有路中路长最短的路的路长。D（0）其中的任一元素表示相应两点间无转接点时最短路路长。一阶路矩阵D（1）其中的元素表示相应两点间可能以点v1为转接点的所有路中路长最短的路的路长；……；为使计算程序化，转接点按顶点下标的顺序依次加入n阶路矩阵D(n)其中的元素d(n)ij就是vi到vj的可能以点v1、v2、…、vn为转接点的所有路中路长最短的路的路长。既是vi到vj的最短路的路长。例求如下交通网络中各对点间最短路路长。该图的权矩阵为：Floyd算法(路矩阵法)算例31025v4v1v2v5v312262448例求如下交通网络中各对点间最短路路长。Floyd算法(路矩阵法)算例31025v4v1v2v5v312262448利用公式发现第一行，第一列元素不变31025v4v1v2v5v312262448利用公式发现第二行，第二列元素不变31025v4v1v2v5v312262448利用公式发现第三行，第三列元素不变31025v4v1v2v5v312262448利用公式发现第四行，第四列元素不变31025v4v1v2v5v31226244831025v4v1v2v5v312262448D(5)中的元素给出相应两点间的最短路，其下标给出最短路个顶点下标,比如：6254已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人，G处60人,问小学应建在哪一个村子，使学生上学最方便（原则①所有人走的总路程最短；②尽可能公平。）。最短路问题算例1(选址问题)AGFECB522747163D26最短路问题算例1(选址问题)AGFECB522747163D26最短路问题算例1(选址问题)A处30人，B处40人，C处25人，D处20人，E处50人，F处60人，G处60人.0200501403503606001500175402502404806028001202502404802108015001501203602102001256006018018016010040500240300320200120250240017001335143010708357701330ABCDEFGABCDEFG某工厂使用一台设备，每年年初工厂都要作出决定：如果继续使用旧的，要付维修费；如果买新的，要付购置费。试制定一个五年更新计划，使工厂总支出最少？若该设备在各年的购置费、不同役龄的残值及维修费如下表：项目购置费设备役龄维修费残值第一年第二年第三年第四年第五年110-154121-263132-382143-4111154-5180最短路问题算例2(设备更新问题)最短路问题算例2(设备更新问题)项目购置费设备役龄维修费残值第一年第二年第三年第四年第五年110-154120-263132-382143-4111154-5180弧（vi，vj）的权:

表示第i年初购买的设备一直使用到第j年年初所需支付的总费用，即第i年初的购置费加上第一年、第二年、…、第（j-i）年的维修费，再减去（j-i）年役龄残值。解：为将该问题化为最短路问题，用点vi表示第i年初购买一台新设备，并虚设点v6表示第五年年底。弧（vi，vj）：表示第i年初购买的设备一直使用到第j年年初（即第j-1年年底）；这样一来，设备更新问题可归结为如下基本表中的求v1到v6的最短路问题。用逐次逼近法较为简便项目购置费设备役龄维修费残值第一年第二年第三年第四年第五年110-154120-263132-382143-4111154-5180答：第一年初购买一台新设备一直用到第三年年初处理，再购买一台新设备一直用到第五年底可使支付的总费用最少。7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许中转)，并且电话线根数最少？引例村庄1村庄4村庄3村庄6村庄2村庄5村庄7分析：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求：连通图图中有圈的话，从圈中任去掉一条边，余下的图仍连通树村庄1村庄4村庄3村庄6村庄2村庄5村庄7如果G=（V，E）是一个无圈的连通图，则称G为树。

树中必存在次为1的点（悬挂点）树中任两点必有一条链且仅有一条链；在树的两个不相邻的点之间添加一条边，就得到一个圈；反之，去掉树的任一条边，树就成为不连通图；n个顶点的树有（n-1）条边。树是无圈连通图中边数最多的，也是最脆弱的连通图！145241575237图的部分树（支撑树）如果图G=（V，E）的部分图G’=（V，E’）是树，则称G’是G的部分树（或支撑树）。村庄1村庄4村庄3村庄6村庄2村庄5村庄7部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最小部分树（最小支撑树）。点保留边可去仍是树不唯一思考：如何铺设电话线，使得电话线长度最少？ijkml最小部分树的求法定理：图中任一个点i，若j是与相邻点中距离最近的，则边[i,j]一定必含在该图的最小部分树内。推论：把图的所有点分成和两个集合，则两集合之间连线的最短边一定包含在最小部分树内。避圈法破圈法227541435175ABCDEST算法的步骤：1、在给定的赋权的连通图上任选一点vi∈,其余点在中。2、从与的连线中找出权数最小的边[vi,vj]，这条边一定包含在最小部分树内，做以标记。3、令vi，；

4、重复2、3两步，直至所有点都包含在中为止。∪→﹨vi→求解最小生成树的避圈算法S77ABCDEST2254143515求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。第七章风险决策的期望值准则及其应用一、风险型决策分析风险型决策分析是在状态概率已知的条件下进行的，一旦各自然状态的概率经过预测或估算被确定下来，在此基础上的决策分析所得到的最满意方案就具有一定的稳定性。第一节风险决策的期望值准则及其应用风险型决策一般包含以下条件：（1）存在着决策者希望达到的目标（如收益最大或损失最小）；（2）存在着两个或两个以上的方案可供选择；（3）存在着两个或两个以上不以决策者主观意志为转移的自然状态（如不同的天气对市场的影响）；第一节风险决策的期望值准则及其应用（4）可以计算出不同方案在不同自然状态下的损益值；（5）在可能出现的不同自然状态中，决策者不能肯定未来将出现哪种状态，但能确定每种状态出现的概率。第一节风险决策的期望值准则及其应用二、风险型决策分析的期望值准则（一）期望损益决策的基本原理一个决策变量d的期望值，就是它在不同自然状态下的损益值乘上相对应的发生概率之和。式中E(di)－变量di的期望值；dij－变量di在自然状态θj下的损益值；p（θj）－自然状态θj发生的概率。第一节风险决策的期望值准则及其应用决策变量的期望值包括三类：①收益期望值；②损失期望值；③机会期望值。把每个方案的期望值求出来加以比较选优的方法，即为期望值决策准则。（二）案例分析

例3-1某化工厂为扩大生产能力，拟定了三种扩建方案以供决策：①大型扩建；②中型扩建；③小型扩建。如果大型扩建，遇产品销路好，可获利200万元，销路差则亏损60万元；如果中型扩建，遇产品销路好，可获利150万元，销路差可获利20万元；如果小型扩建，产品销路好，可获利100万元，销路差可获利60万元。根据历史资料，未来产品销路好的概率为0.7，销路差的概率为0.3，试做出最佳扩建方案决策。其决策表如表3-1。第一节风险决策的期望值准则及其应用表3-1某化工厂扩建问题决策单位：万元第一节风险决策的期望值准则及其应用应用期望收益决策准则进行决策分析，其步骤是：（1）计算各方案的期望收益值：大型扩建：E(d1)=0.7×200＋0.3×(-60)=122（万元）中型扩建：E(d2)=0.7×150＋0.3×20=111（万元）小型扩建：E(d1)=0.7×100＋0.3×60=88（万元）（2）选择决策方案。根据计算结果，大型扩建方案获利期望值是122万，中型扩建方案获利期望值是111万元、小型扩建方案获利期望值是88万元。因此，选择大型扩建方案是最优方案。

第一节风险决策的期望值准则及其应用例3-2某冷饮厂拟定今年夏天(七、八两月)某种冷饮的日计划产量。该种冷饮每箱成本为100元，售价为200元，每箱销售后可获利100元。如果当天销售不出去，过剩一箱就要由于冷藏费及其它原因而亏损60元。通过统计分析和市场预测，确认当年市场销售情况如表3-2所示。表3-2冷饮日销售量概率表第一节风险决策的期望值准则及其应用问：该厂今年夏天每日生产量应定为多少．才能使利润最大?解：第一节风险决策的期望值准则及其应用三、期望损益决策法中的几个问题

（一）期望损益值相同方案的选择在一项决策中，如果期望收益值最大（或期望损失值最小）的方案不止一个时，就要选取离差最小的方案为最优方案。按决策技术定义的离差为：第一节风险决策的期望值准则及其应用例3-3设有一个四种状态、三个方案的决策问题。各状态发生的概率及每一方案在各个状态下收益值如表3-4所示。表3-4收益值表状态θ1θ2θ3θ4期望收益离差

概收方案0.10.20.30.4E(di)σid1d2d330153310252145253520352526.5282816.5138值益率第一节风险决策的期望值准则及其应用E(d1)=30×0.1+10×0.2+45×0.3+20×0.4=26.5E(d2)=15×0.1+25×0.2+25×0.3+35×0.4=28E(d3)=33×0.1+21×0.2+35×0.3+25×0.4=28E(d2)=E(d3)>E(d1)δ2=E(d2)-min{15,25,25,35}=13δ3=E(d3)-min{33,21,35,25}=7因δ2>δ3,故应选方案d3为最优方案。第一节风险决策的期望值准则及其应用（二）风险型决策中完整情报的价值

如果知道状态θj发生，则选择状态θj下对应的最优方案。记，Ep是完整情报的最大利润。显然，