运筹学7-9网络计划技术图论方法马尔科分析

1、第七章 网络计划技术复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：网络图；关键路线；网络时间与时差的计算等。7.1 网络图计划评核术：简称PERT，是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。关键路线法：简称CPM,是在错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。一、网络图的分类 1、箭线式网络图：箭线代表活动，结点代表活动的开始或完成。 2、结点式网络图：结点代表活动，箭线表示各活动之间的先后承接关系。二、箭线式网络图的构成 1、活动：指作业或工序，用箭线

2、表示，箭线的方向表示前进的方向。 虚活动：即虚设的活动，不消耗资源，不占用时间。 2、结点：起点或终点、两个活动的交接点，用圆圈表示。只有一个始点和一个终点。 3、线路：从始点出发，顺着箭线的方向，经过互相连接的结点和箭线，直到终点的一条连线。 （1）总作业时间：在一条线路上，把各个活动的作业时间加起来就是该线路的总作业时间，也叫路长。 （2）关键线路：总作业时间最长的线路就是关键线路。三、箭线式网络图的编绘 【例题计算题】某工程工序活动明细如下表所示:工序 紧前工序工作时间（天）A无20B无15CA,B15DA15EA,B10FD,E10GC,F25HD,E15 【答案】【解析】当然若只要求

3、编绘网络图，去掉图中的结点时间即可。注意虚活动没有严格意义上的限制，在表达不出现歧义的基础上，能省则省即可。7.2 网络时间的计算一、符号表示：ESi:结点的最早开始时间EFi:结点的最早完成时间LSi:结点的最迟开始时间LFi:结点的最迟完成时间ESij:活动的最早开始时间EFij:活动的最早完成时间LSij:活动的最迟开始时间LFij:活动的最迟完成时间Tij:作业时间 :结点符号 ：活动的最早开始或最早完成符号 ：活动的最迟开始或最迟完成符号二、网络时间计算Tij （1）作业时间：三种时间估计法 Tij=（a+4m+b）/6 其中：a最乐观时间，即最短时间 b最保守时间，即最长时间 m最

4、可能时间（2）结点时间：ESj=maxESi+Tij LFi=minLFj-Tij（3）活动时间：ESij= ESi；LFij= LFj；EFij=ESij+Tij; LSij=LFij-Tij。【例题计算题】下图是截取网络图的一部分，在图中空白处填入有关活动和结点的网络时间（单位：天）。 37 【答案】37 7【解析】考察基本公式的计算，这里尽可能用数形结合的方法记忆。记住口诀：（1）最早时间：从前往后挨个加，遇到分叉选大的；（2）最迟时间：从后往前挨个减，遇到分叉选小的。7.3 时差和关键线路Tij一、结点时差Si=LFi-ESi结点时差为0的结点叫做关键结点。二、活动时差 总时差： Si

5、j总=LFij-Tij-ESij 专用时差：Sij专=EFij-Tij-LSij 局部时差1：Sij局1=EFij-Tij-ESij 局部时差2：Sij局2=LFij-Tij-LSij上述公式可根据图中相等关系替代，可利用数轴方便记忆。总时差等于0的活动称为关键活动。三、线段时差线段：两个关键结点之间的一个活动，或两个关键结点之间的几个活动连续相接的连线称为线段。注意：2个关键结点之间没有第3个关键结点算一个线段；2个关键结点之间还有第3个结点算2个线段。线段时差等于线段中各个活动的总时差的最长者。四、线路时差线路：从始点出发，经过连续相接的活动，直到终点的一条连线。线路时差等于各线段时差之和

6、。关键线路的线路时差等于0。五、小结：关键线路 1、总作业时间最长的线路就是关键线路。 2、关键线路的线路时差等于0。 3、把所有关键结点按照顺序串联起来的线路叫关键线路。7.4 最优方案的选择优化：所谓优化，就是要制定出最优的计划方案，即该计划方案能最合理地、最有效地利用人力物力财力，达到周期最短，成本最低的目的。网络计划优化的内容主要有：1、时间优化：在人力物力财力等基本上有保证的条件下，寻求最短的工程周期。2、时间与资源优化：合理利用资源的条件下，寻求最短的工程周期。3、时间与成本优化：（1）在保证工期最短的情况下，寻求成本较低的方案；（2）在成本最低的情况下，寻求合理的工程周期。 直接

7、费用增长率=（极限费用-正常费用）/（正常时间-极限时间）本章总结：本章内容选择、填空和名词解释都会涉及（关键结点、关键活动和关键路线需特殊注意）；计算题考察主要有三个知识点：1、网络图的编绘；2、网络时间的计算（记住口诀）；3、7个时差的计算（注意线路与线段的区别）。第八章 图论方法复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：树、最小枝杈树、最短路线、最大流量等。8.1图的基本概念1、图的基本要素：结点、边。2、有向图：所有边都带方向。3、无向图：所有边都没有方向。4、连通图：所有结点

8、都连接起来，没有孤立点的图。5、不连通图：有孤立点的图。6、权：赋给结点或边的信息。7、回路（圈）：从一点出发，还能回到原点的一条路。8.2 树和树的逐步生成法1、树：连通且不含圈（回路）的图称为树。2、树的边数=结点数-1。8.3 最小枝杈树问题1、最小枝杈树问题是关于在一个网络中，从一个起点出发到所有点，找出一条或几条路线，以使在这样一些线路中所采用的全部支线的总长度是最小的。2、常用方法：普莱姆法或克鲁斯喀尔法。教材中介绍的是普莱姆法，在做题过程中不如克鲁斯喀尔法简单，因此我们重点讲解克鲁斯喀尔法。3、最小枝杈树问题主要应用于管道、电话线、电线、网线等线路铺设中。4、克鲁斯喀尔法（又称避

9、圈法） （1）每次选择剩余边中长度最小的 （2）后选的边与已经选好的边不能构成回路，若构成则舍弃 （3）重复（1）（2），直到把所有边选完。【例题计算题】某自来水公司欲在某地区各高层住宅楼间敷设自来水管道并与主管道相连。其位置如下图，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离（单位：百米）。如何敷设才能使所用管道最少？【答案】【解析】按照克鲁斯喀尔的算法很轻松得出答案。8.4 最短路线问题最短路线问题为当通过网络的各边所需要的时间、距离或费用已知时，寻求两点间的距离最短或费用最少的路性问题。采用的方法为逆向推算法。【例题计算题】某城市东到西的交通道路如下图所示，线上标注的数字为两点

10、间距离(单位：千米)。某公司现需从市东紧急运送一批货物到市西。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。【答案】【解析】从终点逆向标到起点即可说明：方框中的数字代表改点到终点最短距离；方框上的标示从改点到终点最短路线的走法。8.5 最大流量问题最大流量问题，就是在一定条件下，要求流过网络的流量为最大的问题。【例题计算题】某网络如图，线上标注的数字是单位时间通过两节点的流量。试求单位时间由网络始点到网络终点的最大流量（单位：吨）。 【答案】第一条路：1246 流量为5吨 第二条路：1346 流量为2吨 第三条路：1356 流量为6吨 所以最大流量为5+2+6=13吨。【解析】路线的

11、选择顺序不唯一，但不管哪种选择最终的总流量是相等的。小结：三种求解问题方法在实际中的应用1、最小枝杈树问题主要应用于管道、电话线、电线、网线等线路铺设中（总路线最短）。2、短路线问题为当通过网络的各边所需要的时间、距离或费用已知时，寻求两点间的距离最短或费用最少的路性问题（两点间距离最短）。3、最大流量问题，就是在一定条件下，要求流过网络的流量为最大的问题。本章总结：本章内容选择、填空和名词解释都会涉及（图和树中关于边数和点数的关系需特殊注意）；计算题考察主要有三个知识点：1、最小枝杈树；2、最短路径；3、最大流量，考试从中选一个。第九章 马尔科夫分析9.1 马尔科夫分析的数学原理在20世纪初

12、（1907年）俄国数学家马尔科夫发现：在某些事物的概率转换过程中，第N次试验的结果，常常由第N-1次的试验结果所决定。1、 概率向量：任意一个向量u=(u1,u2,un),如果它内部的各个元素为非负数，且总和等于1，则称此向量为概率向量。2、概率矩阵：一方阵每一行都是概率向量，则称为概率矩阵。3、平衡概率矩阵（或固定概率矩阵）： 设有概率矩阵， 当，必有：，称作平衡（固定）概率矩阵。9.2 马尔科夫分析问题的要求1、马尔科夫问题的阶：一阶马尔科夫过程在确定事件周期的选择概率时，只考虑前一周期的选择情况，二阶马尔科夫过程在确定事件周期的选择概率时，考虑前两 周期的选择情况。2、转移概率：某个销售

13、者保持、获得或失去消费者的概率。3、转移概率矩阵：把转移概率排列成矩阵。4、未来市场份额的确定设第一周期的市场份额为T1,转移概率矩阵为P,则第二周期的市场份额为T2=T1*P,以此类推可以得出任意周期的市场份额。【例题计算题】甲、乙两家啤酒厂同时向市场投放一种啤酒，初时，它们所占市场份额相等。第二年，两啤酒厂为吸引顾客，都改换了各自的产品包装，其结果是：甲保持其顾客的70%，丧失30%给乙；乙保持其顾客的60%，丧失40%给甲。第三年，假设顾客的购买倾向与第二年末相同，但甲、乙都为自己的产品大做广告，其结果是：甲保持其顾客的90%，丧失10%给乙；乙保持其顾客的80%，丧失20%给甲。 问：

14、第二年末，两家啤酒厂各占多少市场份额?【答案】由已知得第一年市场份额=(0.5,0.5),第二年对应的概率矩阵为 P=所以第二年末的市场份额为= P=(0.5,0.5) =（0.55,0.45）【解析】预测未来一个周期的市场份额为现在市场份额与转移概率的乘积。5、最终（平衡）市场份额的确定不同销售者在销售过程中的市场份额每个周期都在改变，若消费者的选择概率不变，那么市场份额在经过一个较长时期的转换后会一直不变，我们称为最终（平衡）的市场份额。 计算方法：最终平衡时，可推导出公式T=TP,利用该公式列出线性方程组，在加上概率向量T本身的特点即非负且之和为1，解出未知数来即可。【例题计算题】 某商

15、场对甲,乙,丙三种品牌服装的顾客作调查：原穿甲牌仍然继续穿甲牌的人占75%，改穿乙牌的人占10%，改穿丙牌的人占15%。原穿乙牌仍然继续穿乙牌的人占60%，改穿丙牌的人占20%，改穿甲牌的人占20%。原穿丙牌仍然继续穿丙牌的人占90%，改穿乙牌的人占5%，改穿甲牌的人占5%。试问：最终这三种品牌服装的市场占有率分别为多少(保留三位有效数字)？【答案】由已知的该问题的转移概率矩阵为： 设最终这三种品牌服装的市场占有率分别为X1,X2,X3 由 （X1,X2,X3）=（X1,X2,X3）得方程组为 0.75X1+0.20X2+0.05X3=X1 0.10X1+0.60X2+0.05X3=X2 0.15X1+0.20X2+0.90X3=X3且由题意得X1+X2+X3=1 解方程组得：X1=0.236，X2=0.137，X3=0.627 即三种品牌的服装最终市场占有率分别为