生活中的预测与决策.ppt

生活中的预测与决策,任课教师：薛 焕 斌 E-mail: QQ:51054616,预测和决策的意义,“凡事预则立，不预则废.”这表明预测的重要性。事实上只有以预测为依据的决策，才是有远见卓识的决策。下面是几个有关的例子： 1. 美国克莱斯勒汽车公司，在20世纪70年代石油危机的冲击中深受其害，1979年9个月内损失7亿多美元；与此相反，日本丰田汽车公司，却在此次经济浪潮中发展壮大。究其原因是市场预见与经营决策的差异。 2. 第二次世界大战期间，盟军基于对气候的可靠预测，抓住暴风雨的空隙，于1944年6月6日执行诺曼底登陆计划，获得大捷；而希特勒由于对气候作了错误的判断，损失惨重，大败而终。 3. 1980年，我国有两艘远洋轮，同时从太子港返航。其中一艘船对航线分析预测不当，决策失误，一路上台风侵袭耗时29天；另一艘船预测与决策妥当，返航时间缩短为16天。,第一章 灰预测与灰决策概论,一、灰色系统理论产生的科学背景 现代科学技术在高度分化的基础上高度综合的大趋势，导致了具有方法论意义的系统科学学科群出现。系统科学揭示了事物之间更为深刻、更具有本质性的内在联系，大大促进了科学技术的整体化进程；许多科学领域中长期难以解决的复杂问题随着系统科学的出现迎刃而解；人们对自然界和客观事物演化规律的认识也由于系统科学的出现逐步深化。,灰色系统理论(简称灰理论或灰论，Grey Theory)，是在1982年由中国学者邓聚龙教授创立的，灰理论是一种研究少数据、贫信息不确定性问题的新方法。它以“部分信息已知，部分信息未知”的“小样本”，“贫信息”不确定性系统为研究对象，主要通过对“部分”已知信息的生成、开发，提取有价值的信息，实现对系统运行行为、演化规律的正确描述和有效监控。灰色系统模型对实验数据没有什么特殊的要求和限制，因此应用领域十分宽广。,二、灰色系统的基本原理 在灰色系统理论创立和发展过程中，邓聚龙教授发现并提炼出灰色系统的基本原理。这些基本原理具有十分深刻的哲学内涵。 （1）差异信息原理“差异”是信息，凡 信息必有差异； （2）解的非唯一性原理信息不完全、不确定的解是非唯一的； （3）最少信息原理灰色系统理论的特点是充分开发利用已占有的“最少信息”；,（4）认知根据原理信息是认知的根据； （5）最新信息优先原理新信息对认知的作用大于老信息； （6）灰性不灭原理“信息不完全”（灰）是绝对的。 三、灰色系统理论的主要内容 灰色系统理论进过20多年的发展，现已基本建立起一门新兴学科的结构体系。其基本内容包括以灰色代数系统、灰色方程、灰色矩阵等为基础的理论体系，以灰色序列生成为基础的方法体系，以灰色关联空间为依托的分析体系，以灰色模型（GM）为核心的模型体系，以系统分析、评估、建模、预测、决策、控制、优化为主体的技术体系。 我们这门课只要学习的是：灰数、建模、预测、决策,(4)连续灰数与离散灰数 在某一区间内取有限个值或可数个值的灰数称为离散灰数，取值连续地充满某一区间的灰数称为连续灰数。 (5)黑数与白数 当 时，即当 的上、下皆为无穷时，称 为黑数； 当 且 时，称 为白数。 为了讨论方便，我们将黑数与白数看成特殊的灰数。,(6)本征灰数与非本征灰数 本征灰数是指不能或暂时还不能找到一个白数作为其“代表”的灰数，比如一般的事前预测值、宇宙的总能量、准确到秒或微秒的“年龄”等都是本征灰数。 非本征灰数是指凭先验信息或某种手段，可以找到一个白数作为其“代表”的灰数。我们称此白数为相应灰数的白化值，记为 ，并用 表示以a为白化值的灰数。如估计某人的托福考试成绩可能在600分左右，可将600作为该考生托福考试成绩 的白化数，记为,第二章 问题分析,一、决策与我们的关系： “事事有决策、时时要决策” （一）决策的风险 是决策就会有风险，不同的决策需要承担的风险完全不一样。,（二）如何规避决策风险 第一，如何降低因决策失误造成的风险 第二，怎样增强承受风险的能力 如何才能有效地降低决策失误造成的风险？如何增强我们承受风险的能力呢？ 要想有效地降低决策失误风险和增强抵抗风险的能力，就必须建立一个决策模型，使用分析的工具。,（三）正确决策的关键 正确决策的关键是： 对问题的正确判断。你能不能正确地判断问题？要清楚地知道自己到底想要什么。 对环境的客观评估。你到底处于什么样的环境之中？你对这个环境的了解到底有多少？,对资源的有效评价。你要想解决问题，要想做出一个决策，你手上有什么资源？ 对困难的理性分析。这里面强调的一个词就是“理性”，而不是感性。 对风险的充分准备。我们对一个决策所可能产生的风险要有充分的准备，准备得充分与否直接决定决策的成败。,决策的支持体系三要素： 要有相关的数据 要掌握一种推理的方法 推理要符合逻辑 二、中华传统文化与决策思维模式 （一）中华传统文化对决策的影响 要“高深莫测”，还要“大智若愚” 即使内心“五内如焚”，但外表还要“不动声色”,逢事要“自己明白”，但不能“说透”； 说话要“面面俱到”，并“留有余地”； 做人要“圆滑”、“世故”、“中庸” 因此，我们的传统文化是以模糊为最高境界的，而模糊的最高境界则是一个“悟” （二）传统决策思维模式,三、决策价值观的差异 注重“过程”的决策观，尽量把问题放在决策的前面； 注重“结果”的决策观，总习惯于把问题放在决策的前面；,四、决策的模型及分析工具 （一）可使用的模型 可使用的模型包括一些简单的方法还有一些比较复杂的模型。比如：柱状图、树形图、扇形图、曲线图等分析工具；和SWOT分析法、麦肯锡7S模型、EVA分析法等模型。 （二）需建立的模型 关注关键结果领域进行因果分析,柏拉图法 柏拉图法又称排列图法或主次因素分析图法，由19世纪意大利学者柏拉图在分析意大利社会财富分布状况时首先提出。他在研究中发现，少数人占有社会上的大量财富，而绝大多数人处于贫困状况，即发现了“关键的少数和次要的多数”的关系。 鱼骨图分析法 鱼骨图分析法是一种因果分析方式，指明问题发生的区域，并找出该区域的因素,利用鱼骨图结构来分析问题，可以辨识并列出与任一资源相关的潜在问题，并排列优先级。换而言之，该分析法是一种层层剥茧、透过现象看本质的分析方法。 （三）靠个人的模型 以人的感觉、直觉、靠人对问题的判断，靠人的经验和悟性去进行决策。,五、分析和解决问题的逻辑思维 逻辑有时也指逻辑学，其实就是研究主观思维的客观形式及其规律的科学。,第三章 序列算子与灰色序列生成,事实上，研究系统的行为特征，得到的数据往往是一串确定的白数，我们把它看成是某个随机过程的一条轨道或实现，或是看成灰色过程的白化值，这并没有本质上的区别。如何通过系统行为特征数据研究其发展规律，不同的方法思路也不一样。 随机过程是以先验概率为出发点，研究数据的统计规律。这种方法是建立在大量数据的基础上的。但有的时候，即使有了大量的数据也未必一定能找到统计规律。因为概论论或随机过程中研究的典型分布十分有限，对于非典型的分布过程（如,平稳过程、高斯过程、马尔可夫过程或白噪声过程等以外的分布过程), 往往难以处理。 灰色系统是通过对原始数据的挖掘、整理来寻求其变化规律的，这是一种就数据寻找数据的现实规律的途径，我们称为灰色序列生成。灰色系统理论认为，尽管客观系统表象复杂，数据离乱，但它总是有整体功能，因此必然蕴含某种内在规律。关键在于如何选择适当的方式去挖掘它和利用它。一切灰色序列都能通过某种生成弱化其随机性，显现其规律。 例如，已知原始数据数列X(0)=1,2,1.5,3 它没有明显的规律性。如何使其显现出规律呢？,一、冲击扰动系统与序列算子 冲击扰动系统预测是一个历来令预测专家棘手的问题。对于冲击扰动系统预测，模型选择理论也将失去其应有的功效。因为问题的症结不在模型的优劣，而是由于系统行为数据因系统本身受到某种冲击波的干扰而失真。这时，系统行为数据已不能正确地反映系统的真实变化规律。,第四章 一个有效的问题 分析与决策模型,状况评估,案例模拟X公司的一次部门经理会议 X公司的起重机销售额下降，成本不断增加，为此公司总裁召集各个部门经理开会，要求大家找到问题并采取行动。 生产部门认为是采购和运输问题。具体说来就是采购的零配件质量不好，而且在运输上又经常中断，使得他们的生产时断时续，十分不稳定。,市场部门认为是经济形势的影响。总体来说，他们认为这没什么大不了，主要是整体经济形势下滑，造成整个行业出现了问题，而不是公司内部的问题。 销售部认为对竞争对手不了解。他们认为竞争对手越来越强大，而公司对此熟视无睹，没有对策，甚至根本不知道竞争对手在干什么。 开发部认为是技术优势不明显。主要是因为公司部给钱，研发经费减少，结果很多技术问题都解决不了。,因此，我们需要一个系统的程序来帮助解决难题，它就是状况评估法。 什么是“难题”“难题”就是那些需要关注，并且采取行动解决的事件。而且难题不仅指困难，也需要涉及事件改进的可能。 状况评估法的作用： 找出难题并且分解和控制问题； 体统分析资料后排出轻重缓急； 解决难题的计划和采取的方法。,一、查明具体的难题 1、列出难题 想要查明具体的原因是什么、首先要做的就是列出一些问题。一般来说，我们可以提出下面一些常见的问题： 到底发生了什么偏差？ 应实施什么样的计划？ 应该做出怎么的决定？ 预计将来有什么变化？ 会存在什么样的机会？,事实上，我们提出问题的最终目的，就是要列明存在的各种难题，这样才能在后面的步骤中做到有的放矢。 通过上面的示例，我们就可以列出X公司的难题一览表,2、澄清难题的方法做出有效提问 列出问题之后还需要进一步澄清问题，把一些复杂的问题分解成简单的、一目了然的和具体的难点，让原本笼统的、复杂的难题变得具体和现实。 如何来澄清难题呢？ 提问 你的实际意思是指？ 你具体讲的问题是？,是否还有其他问题？ 你有什么具体证据？ 什么偏差造成问题？ X公司难题的澄清 笼统的难题：生成成本在不断增加。 具体的难题：成本增加具体原因是什么？ 提供证据：某些原材料成本上升并多变。,3、问题的分解 X公司的问题分解： 液压件的成本增加了20%； 公司产品在最近只中了3个标； 必须重新部署产品的竞争策略； 特种钢材价格在不断上升； 在少占用资金的前提下提高库存量。,案例 某位女生遇到了以下几个问题： 第一，男朋友经常不陪她一起吃饭。 第二，男朋友对她态度不好。 第三，晚上经常有人找他出去。 在查明具体难题这个环节里，我们要做到： 第一，列出难题； 第二，通过有效提问的方式澄清难题。,二、把握难题的轻重缓急,1、制定缓急程度的标准 一般来说，我们对问题的缓急程度很难达成共识，往往是仁者见仁、智者见智。所以，为了让我们能对问题轻重缓急程度作出有效的判断，就要设法找到一种合适的方法。 制定标准： 必须易于掌握和使用； 又有很明显的灵活性； 基于问题的各个方面。,2、严重性、紧急性和发展性 衡量问题缓急程度的标准：问题分类 第一类，严重性；第二类，紧急性； 第三类，发展性,3、问题级别评估并得出结论,4、问题的变化与解决 我们做好了问题的级别评估，接下来还要防止问题发生变化。这是因为： 难题越临近到最后期限，越会增加它的紧急性； 如果一旦出现新的难题，问题的缓急程度就需要重新做出判断。,三、解决问题的计划与步骤 当我们知道了存在什么问题、明确了问题的轻重缓急，也就知道了哪件事情是第一重要的，哪件次之。接下来就需要按照它们的轻重缓急去解决问题，那就需要知道解决问题的计划和步骤是什么。 （一）第一轮提问 是否需要知道偏差的原因？ 是否需要去做出一个选择？ 是否需要采取行动或计划？,是否需要进一步澄清问题？ 实际和预计之间有没有偏差？ 这种偏差的原因是明确的，还是不明确？ 我们采取行动之前，需不需要做出进一步分析？ （二）进一步提出问题 能不能确定我们需要采取行动？ 能不能确定我们需要实施的计划？ 其他方面的改变会不会影响我的计划？,（三）潜在问题分析 【案例】行军问题 问题分析还是决策分析,重点提示：如果能下结论，我们就要做决策分析；如果不能下结论，那就要进一步做问题分析。,四、准备采取行动 在前面的内容中，我们讲述了再状况评估中，不但要知道问题，要澄清问题，要分析问题的紧急性、严重性、和发展性，我们还需要再对它做出一个评估，明确这些问题中的哪些是我们需要做进一步的问题分析，哪些需要做决策分析。 （一）计划的内容 我们到底需要做什么？ 我们什么时候做？ 谁来参与做？,（二）计划行动的程序 计划行动的程序主要包含： 收集信息 分析 创造性（如何解决问题） 承诺 批准 执行 培训 奖励激励,【案例】,小结,问题分析,识别可能的原因,评估可能的原因,描述面临的问题,确认真正的原因,解决问题的三大常见误区,1.妄下结论 第一，信息不够，却认为自己已经把握 问题； 第二，只用支持自己观点的信息来论证 自己的结论； 第三，故意忽略和自己的假设不相符的 信息，甚至去攻击和否定它们。 2.错误的定义问题 第一，信息过多，我们看到很多信息 视乎都跟问题有关 ；,第二，我们没有办法去分辨哪些信息是 真正重要的； 第三，面对复杂的信息，我们很难判断 这些信息到底有没有利用价值。 3.盲目行动 第一，因为时间、事件的紧迫，往往会 同时采取多种行动； 第二，总是希望侥幸碰到解决问题的方 法； 第三，没有核查、确认行动是否对解决 问题真正有利，马上就采取行动,第四，即使偶尔问题得到了解决，也往 往不知道怎么解决的。,决策分析,评估选择方案,评估决策风险,明确决策目的,作出最终决策,【案例】她该嫁给谁 某女孩有四个男朋友可以选择，第一个叫李酷毙；第二个叫张帅呆；第三个叫罗老实；第四个叫王大款。因为她一个人不能同时嫁给四个人，所以只能去挑选其中的一个。 决策目标的分类： 1、必须要求目标； 2、愿望要求目标；,必须目标的判断 第一，年龄20岁到50岁； 第二，有固定的工作和收入； 第三，一年之内可以和她结婚。 愿望目标评估 第一，英俊潇洒； 第二，有楼有车； 第三，收入丰厚； 第四，存款大把； 第五，嫁过去要当家作主； 第六，财产共享。,评估风险 【案例】生产手机的公司，要在销售旺季到来前向市场推出新型手机K。公司给出50万的投资资金并下达任务销售额要比去年同期提升两个百分点。,应变措施,找出可能原因,采取预防措施,识别潜在问题,计划应变措施,第五章 灰色关联分析,数理统计中的回归分析、方差分析、主成分分析等都是用来进行系统分析的方法。这些方法都有下来不足之处： （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为系统特征序列，计算灰色关联度,案例: 根据某地区10年农民人均收入年纯收入的资料，和该地区相应年份的销售额资料，预测该地区市场销售额。观察期资料见表1,根据表1中x与y观察期十年资料绘制散点图 散点图表明，x与y存在相关关系，且散点基本集中在一条直线上，说明相关程度较高，农民年人均纯收入（x）与销售额（y）表现较高程度的直线正相关。可以采用一元线性相关回归分析预测模型,2. 应用最小平方法求回归方程中的参数，建立预测模型 求参数a、b的标准方程为： ynabx xyaxbx2 解得方程为：,求解a、b值： 则回归方程为： 99.1210.1x,99.121,0.1,灰色预测模型GM(1,1)模型,第六章 图与网络模型,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1所示。,欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,第六章 图与网络模型,1 图与网络的基本概念 2 最短路问题 3 最小生成树问题 4 最大流问题 5 最小费用最大流问题,1 图与网络的基本概念 图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图6-1就是一个表示这种关系的图。,当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图6-2来表示，可见图论中的图与几何图、工程图是不一样的。,如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图6-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六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。,A,B,C,D,E,F,分析：点表示项目，边表示两个项目有同一名运动员参加,目的：在图中找出点序列，使得依次排列的两个点不相邻，就找到了每名运动员不连续参加两项比赛的安排方案,A、C、B、F、E、D,2 最短路问题 最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。,最短路问题引例,下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。,从v1到v8： P1=（v1，v2，v5，v8） 费用 6+1+6=13 P2=（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21 P3= ,最短路问题中，不考虑有向环、并行弧。,几个概念,路：设p是D中一个首尾相连的弧的集合，如果vs是它的第一条弧的始点，vt是它的最后一条弧的终点，则称它是以点vs为始点，以点vt为终点的一条路。 路长：路p中所有弧的权值的和称为路p的长，记为,设图D=（V，A）是一有向网络,设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年提出的，可用于求解指定两点间的最短路问题，或从指定点到其余各点的最短路问题。由于其以标号为主要特征，又称为标号法。,v5,最短路的子路是最短路,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,图上标号法,0,0,M, ,M, ,v1,3,M, ,M, ,M, ,v1,1,v1,1,永久标号,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,v1,6,图上标号法,0,0,M, ,M, ,v1,3,M, ,M, ,M, ,0,0,v1,1,v4,11,v1,3,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,0,0,M, ,v1,1,M, ,M,M, ,1,3,图上标号法,v4,11,v1,3,v1,6,v3,5,v3,5,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,0,0,M, ,v4,11,v1,1,M, ,M, ,M, ,v1,3,图上标号法,v3,5,v2, 6,v2, 6,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,0,0,M, ,v4,11,v1,1,M, ,M, ,v1,3,v5,12,v5,9,v5,9,图上标号法,v3,5,v2, 6,永久标号,临时标号,v5,10,v1出发到v8去，使总费用最小的旅行路线,0,0,v5,10,v1,1,M, ,v5, 12,v1,3,v5,9,v5, 12,v3,5,v2, 6,图上标号法,永久标号,临时标号,v5,10,v1出发到v8去，使总费用最小的旅行路线,0,0,v5,10,v1,1,M, ,v1,3,v5, 12,v3,5,v2, 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算法，可解得最短路径为 v1v3v4v6,无向网络:,负权弧时。,无向网络中，最短路最短链。,多个点对之间最短路？,Dijkstra算法失效,Dijkstra算法注意的问题,逐步逼近算法,路矩阵算法,5,7,2,7,4,6,1,2,6,3,2,0,2,6,5,7,7,10,v3,v1,v2,v4,v5,v6,v7,练习：求如下无向网络中v1到v7的最短链,Dijkstra算法求最短链,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,逐次逼近算法思想,该公式表明， P(1)1j中的第j个分量等于P(0)1j的分量与基本表(权矩阵)中的第j列相应元素路长的最小值，它相当于在v1与vj之间插入一个转接点(v1,v2,vn中的任一个，含点v1与vj)后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而P(k)1j中的每一个分量则随着k的增加而呈不增的趋势！,用于计算带有负权弧指定点v1到其余各点的最短路,逐次逼近算法基本步骤,例 计算从点v1到所有其它顶点的最短路,解：初始条件为,以后按照公式 进行迭代。,直到得到 ，迭代停止。,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下标追踪路径,空格为无穷大,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下标追踪路径,空格为无穷大,已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人,问小学应建在哪一个村子，使学生上学最方便（原则所有人走的总路程最短；尽可能公平。）。,最短路问题算例1(选址问题),最短路问题求解方法,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的最短路记为 ,则一定有,Floyd算法(路矩阵法)思想,再在D1中加入v2及D中与vi，vj，v1， v2相关联的弧，得D2，D2中vi到vj的最短路长记为 ，则有,Floyd算法(路矩阵法)思想,Floyd算法(路矩阵法)步骤,设有有向网络D=（V，A），其权矩阵为A=(aij)nn，,如下构造路矩阵序列：,则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。,令权矩阵A为初始路矩阵D（0），即令D（0）=A,2. 依次计算K阶路矩阵D（K）=（d(k)ij）nn, 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算法(路矩阵法)算例,例 求如下交通网络中各对点间最短路路长。,Floyd算法(路矩阵法)算例,利用公式,发现第一行，第一列元素不变,利用公式,发现第二行，第二列元素不变,利用公式,发现第三行，第三列元素不变,利用公式,发现第四行，第四列元素不变,D(5)中的元素给出相应两点间 的最短路，其下标给出最短路 个顶点下标,比如：,6254,已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人,问小学应建在哪一个村子，使学生上学最方便（原则所有人走的总路程最短；尽可能公平。）。,最短路问题算例1(选址问题),最短路问题算例1(选址问题),最短路问题算例1(选址问题),A处30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人.,0 200 50 140 350 360 600,150 0 175 40 250 240 480,60 280 0 120 250 240 480,210 80 150 0 150 120 360,210 200 125 60 0 60 180,180 160 100 40 50 0 240,300 320 200 120 250 240 0,1700 1335 1430 1070 835 770 1330,A B C D E F G,A B C D E F G,某工厂使用一台设备，每年年初工厂都要作出决定：如果继续使用旧的，要付维修费；如果买新的，要付购置费。试制定一个五年更新计划，使工厂总支出最少？,若该设备在各年的购置费、不同役龄的残值及维修费如下表：,最短路问题算例2(设备更新问题),最短路问题算例2(设备更新问题),弧（vi，vj）的权: 表示第i年初购买的设备一直使用到第j年年初所需支付的总费用，即第i年初的购置费加上第一年、第二年、第（j-i）年的维修费，再减去（j-i）年役龄残值。,解：为将该问题化为最短路问题，用点vi表示第i年初购买一台新设备，并虚设点v6表示第五年年底。,弧（vi，vj）：表示第i年初购买的设备一直使用到第j年年初（即第j-1年年底）；,这样一来，设备更新问题可归结为如下基本表中的求v1到v6的最短路问题。,用逐次逼近法较为简便,答：第一年初购买一台新设备一直用到第三年年初处理，再购买一台新设备一直用到第五年底可使支付的总费用最少。,7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许中转)，并且电话线根数最少？,引例,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,分析：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求：,连通图 图中有圈的话，从圈中任去掉一条边，余下的图仍连通,树,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,如果G=（V，E）是一个无圈的连通图，则称G为树。,树中必存在次为1的点（悬挂点） 树中任两点必有一条链且仅有一条链； 在树的两个不相邻的点之间添加一条边，就得到一个圈； 反之，去掉树的任一条边，树就成为不连通图； n个顶点的树有（n-1）条边。,树是无圈连通图中边数最多的，也是最脆弱的连通图！,图的部分树（支撑树）,如果图G=（V，E）的部分图G=（V，E）是树， 则称G是G的部分树（或支撑树）。,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最小部分树（最小支撑树）。,点保留 边可去 仍是树 不唯一,思考：如何铺设电话线，使得电话线长度最少？,最小部分树的求法,定理：图中任一个点i，若j是与相邻点中距离最近的， 则边i,j一定必含在该图的最小部分树内。,推论：把图的所有点分成 和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,避圈法,破圈法,2,2,7,5,4,1,4,3,5,1,7,5,求解最小生成树的避圈算法,S,A,B,C,D,E,S,T,2,2,1,3,1,5,求解最小生成树的破圈算法,算法的步骤： 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.72000.3(-60)=122（万元） 中型扩建：E(d2)=0.71500.320=111（万元） 小型扩建：E(d1)=0.71000.360=88（万元） （2）选择决策方案。根据计算结果，大型扩建方案获利期望值是122万，中型扩建方案获利期望值是111万元、小型扩建方案获利期望值是88万元。因此，选择大型扩建方案是最优方案。,第一节 风险决策的期望值准则及其应用,例3-2 某冷饮厂拟定今年夏天(七、八两月)某种冷饮的日计划产量。该种冷饮每箱成本为100元，售价为200元，每箱销售后可获利100元。如果当天销售不出去，过剩一箱就要由于冷藏费及其它原因而亏损60元。通过统计分析和市场预测，确认当年市场销售情况如表3-2所示。 表3-2 冷饮日销售量概率表,第一节 风险决策的期望值准则及其应用,问：该厂今年夏天每日生产量应定为多少才能使利润最大? 解：,第一节 风险决策的期望值准则及其应用,三、期望损益决策法中的几个问题 （一）期望损益值相同方案的选择 在一项决策中，如果期望收益值最大（或期望损失值最小）的方案不止一个时，就要选取离差最小的方案为最优方案。 按决策技术定义的离差为：,第一节 风险决策的期望值准则及其应用,例3-3 设有一个四种状态、三个方案的决策问题。各状态发生的概率及每一方案在各个状态下收益值如表3-4所示。 表3-4 收益值表,值,益,率,第一节 风险决策的期望值准则及其应用,E(d1)=300.1+100.2+450.3+200.4=26.5 E(d2)=150.1+250.2+250.3+350.4=28 E(d3)=330.1+210.2+350.3+250.4=28 E(d2)= E(d3) E(d1) 2= E(d2)-min15,25,25,35=13 3= E(d3)-min33,21,35,25=7 因2 3,故应选方案d3为最优方案。,第一节 风险决策的期望值准则及其应用,（二）风险型决策中完整情报的价值 如果知道状态j发生，则选择状态j下对应的最优方案。记 ，Ep是完整情报的最大利润。显然， EpmaxE(di)=E(d)。 故完整情报的价值为Ev=Ep - E(d), 表示了花钱搞情报所能得到的最大的期望利润。决策时，所花人力、物力去获得完整情报的费用不超过Ev ，则获取完整情报的工作是合算的，否则得不偿失。,第一节 风险决策的期望值准则及其应用,例3-4 计算例3-2的完整情报的价值 。根据已提供的资料，计算具有完整情报下各方案的最大利润