运筹学-6(图与网络分析)

1、运筹学基础教程运筹学基础教程6黄桐城黄桐城 主编主编 赵弘志赵弘志 改编改编 主讲主讲 第六章第六章 图与网络分析图与网络分析l主要内容主要内容我们的教材我们的教材p-116 图论的基本概念图论的基本概念 最短路问题最短路问题 不重要内容不重要内容 最大流问题最大流问题 不重要内容不重要内容 网络计划网络计划6.1 6.1 图论的基本概念图论的基本概念 .1 引论引论 哥尼斯堡七桥问题哥尼斯堡七桥问题ABD CABCD简捷表示事物之间的简捷表示事物之间的本质联系，归纳事物本质联系，归纳事物之间的一般规律之间的一般规律引论引论 图的用处图的用处l A、B、C、D、E 某公司的某公

2、司的五支球队进行循环赛五支球队进行循环赛 组织机构设置图组织机构设置图ABCDE总公司总公司分公司分公司工厂或工厂或办事处办事处6.1.2 6.1.2 图的基本概念图的基本概念l 图 是 由图 是 由 点点 和和 线线 构 成 的 。构 成 的 。l 点 的 集 合点 的 集 合 V 表 示 ，表 示 ， V = v i l 不 带 箭 头 的 连 线 叫 做不 带 箭 头 的 连 线 叫 做 边边 ( e d g e ) ， 边， 边的 集 合 记 为的 集 合 记 为 E = e j ， 一 条 边 可 以， 一 条 边 可 以用 两 点用 两 点 v i , v j 表 示表 示 , e

3、 j = v i , v j .l 带 箭 头 的 连 线 叫 做带 箭 头 的 连 线 叫 做 弧弧 ( a r c ) , 弧 的 集 合弧 的 集 合记 为记 为 A ， A = a k , 一 条 弧 也 是 用 两一 条 弧 也 是 用 两点 表 示 ，点 表 示 ， a k = v i , v j , 弧 有 方 向 ：弧 有 方 向 ：v i 为 始 点 ，为 始 点 ， v j 为 终 点为 终 点图的基本概念图的基本概念( (续续) )l 由点和边组成的图叫做由点和边组成的图叫做无向图无向图，记为，记为G=（V，E）l 由点和弧组成的图叫做由点和弧组成的图叫做有向图有向图，记

4、为，记为D=（V，A）l 例例1.v1v2v3v4v1v2v3v4v5v6v7e1e2e3e4e5e6e7a1a2a8a4a3a5a6a9a7a10a11无向图：点集、边集无向图：点集、边集有向图：点集、弧集有向图：点集、弧集图的基本概念图的基本概念( (续续) )l 以点以点u u为端点的边的条数，叫做点为端点的边的条数，叫做点u u的的次次l 次为次为1 1的点叫做的点叫做悬挂点悬挂点；次为；次为0 0的点叫做的点叫做孤立点孤立点；次为奇数则称次为奇数则称奇奇点；次为偶数则称点；次为偶数则称偶偶点。点。l 点弧交替序列称为点弧交替序列称为链链；闭合的链称为；闭合的链称为圈圈l 首尾相接的链

5、称为首尾相接的链称为路路；闭合的路称回路；闭合的路称回路l 任意两点之间都有边相连，称为任意两点之间都有边相连，称为连通图连通图节点与（有向）边节点与（有向）边 每一条边和两个节点关联，一条每一条边和两个节点关联，一条边可以用两个节点的标号表示（边可以用两个节点的标号表示（i，j）ji路径（路径（Path） 前后相继并且方向相同的边序列前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4)42314231网络由节点和边组成网络由节点和边组成图的基本概念图的基本概念( (续续) )回路（回路（Circuit） 起点和终点重合的路径称为起点和终点重合的路径称为回路回路 =(1,2),

6、(2,4),(4,1) 回路中各条边方向相同回路中各条边方向相同4231链（链（Chain） 前后相继并且方向不一定相同的边前后相继并且方向不一定相同的边序列称为序列称为链链 C=(1,2),(3,2),(3,4)4231连通图连通图 任意两个节点之间至少有一条任意两个节点之间至少有一条链的图称为链的图称为连通图连通图24351圈圈(Cycle) 起点和终点重合的链称为起点和终点重合的链称为圈圈 =(1,2),(2,4),(3,4),(1,3) 圈中各条边方向不一定相同圈中各条边方向不一定相同4231树树(Tree) 无圈的连通图称为无圈的连通图称为树树 树中只与一条边关联的节点称树中只与一条

7、边关联的节点称为为悬挂节点悬挂节点图上作业法图上作业法l已知如图所示：三个工厂向四个市场配已知如图所示：三个工厂向四个市场配送，请确定最佳配送路线。送，请确定最佳配送路线。 4B223A33B157B412131A1334B34A2先去掉两个圈内路线最长的线，得到下列流量图先去掉两个圈内路线最长的线，得到下列流量图B2(1)(2)A3(1)B1（3）B41213A13(1)B34A2135432374验证：第一圈内总长：验证：第一圈内总长：3+4+5+4+7=233+4+5+4+7=23第一圈逆时针内配送路长：第一圈逆时针内配送路长：3+4+5=1211.53+4+5=1211.5，则不是最优

8、方案，则不是最优方案第二圈内配送路长：第二圈内配送路长：4+2+3+4=134+2+3+4=13第二圈逆时针内配送路长：第二圈逆时针内配送路长：26.526.5，则是最优方案。，则是最优方案。第二圈顺时针内配送路长：第二圈顺时针内配送路长：36.536.5，则是最优方案。，则是最优方案。 修正第一圈内方案，取逆时针方向最小值修正第一圈内方案，取逆时针方向最小值1 1，然后逆时针方向配送路线，然后逆时针方向配送路线减去减去1 1，顺时针方向配送及未走路线加上，顺时针方向配送及未走路线加上1 1，则得到第一圈内配送路长：，则得到第一圈内配送路长：55总长一半，则是最优方案。如图所示：总长一半，则是

9、最优方案。如图所示：验证：验证：第一圈顺时针内配送路长：第一圈顺时针内配送路长：7+4=1111.57+4=1111.5，则是最优方案；，则是最优方案；第一圈逆时针内配送路长：第一圈逆时针内配送路长：511.5511.5，则是最优方案。，则是最优方案。第二圈顺时针内配送路长：第二圈顺时针内配送路长：36.536.5，则是最优方案。，则是最优方案。第二圈逆时针内配送路长：第二圈逆时针内配送路长：4+2=66.54+2=66.5，则是最优方案。，则是最优方案。计算运费：计算运费：1 1* *7+27+2* *5+15+1* *4+24+2* *3+13+1* *2=292=29A2(1)(2)A3

10、B1(2)(1)B412131A133B3(1)54323474案例案例通俗思路解题通俗思路解题起点和终点不同的单一路线选择起点和终点不同的单一路线选择 例例1： 如图如图55所示，所示，A是一煤矿所在地，是一煤矿所在地，I是是煤炭需求地，煤炭需求地，B，C，D，E，F，G，H，I是由是由A到到J的可经过的城镇。每两节点之间的距离已经标的可经过的城镇。每两节点之间的距离已经标 出，现在要找出从出，现在要找出从A到到J之间的最短路线。这就是一之间的最短路线。这就是一个最短路问题。个最短路问题。步步骤骤已解点已解点候选点候选点相关相关成本成本第第n个个最近最近节点节点最小最小成本成本最新最新连接连

11、接A到各到各N节点节点最短最短路径路径1ABCD90,138,348B90AB AB2ABCDCE138,348156,174C138ACAC3ABCDEDF348174291,228E174BEABE步步骤骤已解点已解点候选点候选点相关相关成本成本第第n个个最近最近节点节点最小最小成本成本最新最新连接连接A到各到各N节点节点最短最短路径路径4ACEDD, FF, I348291, 228294, 258F228CFACF5ACEFDDIH, G348291258288, 360I258EIABEI6ACFIDDH, GH, J348291288, 360390, 384H288FHACFH步

12、步骤骤已解点已解点候选点候选点相关相关成本成本第第n个个最近最近节点节点最小最小成本成本最新最新连接连接A到各到各N节点节点最短最短路径路径7ACFIHDDGJG, J348291360384336, 414D291CDACD8FIHDGJJG360384414396J384IJABEIJ6.2 6.2 网络计划网络计划.1 基本概念基本概念p130网络计划网络计划是用网络分析的方法编制的计划是用网络分析的方法编制的计划杜邦公司杜邦公司关键路线法关键路线法CPMCPM美国海军武器局美国海军武器局计划评审技术计划评审技术PERTPERT网络图网络图（有向赋权图）的构成（有向赋权图

13、）的构成结点结点，也称事项，一道工序的开始或结束，也称事项，一道工序的开始或结束工序工序（弧），相对独立的活动，消耗资源（弧），相对独立的活动，消耗资源虚工序虚工序，只表示衔接关系，不消耗资源，只表示衔接关系，不消耗资源工序时间工序时间（权），完成工序的时间消耗（权），完成工序的时间消耗.2 网络图的绘制原则网络图的绘制原则l 只 能 有 一 个 始 点 事 项 和 一 个 终 点只 能 有 一 个 始 点 事 项 和 一 个 终 点 事 项事 项l 不 允 许 出 现 编 号 相 同 的不 允 许 出 现 编 号 相 同 的 箭 线箭 线l 不 允 许 出 现不 允 许 出

14、现 循 环 线 路循 环 线 路l 作 业 要 始 于 结 点 终 于作 业 要 始 于 结 点 终 于 结 点结 点网网 络络 规规 则（则（2 2）l 1 1、避免循环、不留缺口、避免循环、不留缺口l 2 2、一一对应：一道工序用两个事项表示、一一对应：一道工序用两个事项表示l 3 3 、从左向右依次展开、从左向右依次展开例：例：工工 序序ABCDEFGHI紧前工序紧前工序-ABBC、D C、DE、F G工序时间工序时间466 7 5 9748A, 4B, 6C, 6D, 7E, 5G, 7F, 9H,4I,8网络图的绘制网络图的绘制l 任务的分析与分解任务的分析与分解l 判定作业之间的逻

15、辑关系判定作业之间的逻辑关系l 依逻辑关系绘制网络图依逻辑关系绘制网络图作业作业A AB BC CD DE EF FGG紧前作业紧前作业A AA AC CBDBDD DEFEF.3 关键路线法关键路线法 CPM一、时间参数运算一、时间参数运算 什么是关键路线？什么是关键路线？1、作业时间作业时间t t（i，j），经验数据、统计数据），经验数据、统计数据2 2、事项最早时间事项最早时间 TE(j)max TE(i)+ t（i，j） 到齐上课，最后到者决定最早开课时间到齐上课，最后到者决定最早开课时间3 3、事项最迟时间事项最迟时间 TL(i)min TL(j)- t（i，j） 保

16、证保证1212点吃饭，路最远者决定最迟下课时间点吃饭，路最远者决定最迟下课时间4 4、工序最早可能开工时间、工序最早可能开工时间 TES(i,j) TE(i) = max TES(h,i)+ t（h,i ）5 5、工序最早可能完工时间、工序最早可能完工时间 TEF(i,j) TES(i,j)+ t（i，j）hij.6、工序最迟必须开工时间工序最迟必须开工时间 TLS（i,j) TL(j) t（i,j) minTLs(j,k)- t（i，j）7 7、工序最迟必须完工时间、工序最迟必须完工时间 TLF（i,j) TL(j) TLS（i,j)+ t（i,j)8 8、工序总时差：、工序总时差：在不影响

17、其紧后工序在不影响其紧后工序最迟必须最迟必须开工时间的前提开工时间的前提下，本工序可以推迟的时间下，本工序可以推迟的时间 R（i,j） TLS(i,j) TES(i,j) TLF(i,j) TEF(i,j) minTLS(j,k) TEF（i,j）9 9、工序单时差：、工序单时差：在不影响其紧后工序在不影响其紧后工序最早可能最早可能开工时间的前提开工时间的前提下，本工序可以推迟的时间下，本工序可以推迟的时间 r （i,j） minTES(j,k) TEF（i,j） kk.4时间参数图解时间参数图解.解上例：解上例：计算事项计算事项 时间参数时间参数 TESTLSTEFTLFTE

18、STLSTEFTLSr(i,j)R（i,j）A4B 6C6G7D7E5F9H4I 80047613222028282024136关键路线关键路线：由总时差为零的工序构成：由总时差为零的工序构成 B D G It（i,j)t（j,k).l 解上例解上例 计算工序时间参数计算工序时间参数 工序工序ijt(i,j) ESEFLSLFRrA4043730B6060600C641071333D761361300E561119241311F91322152420G71320132000H42226242822I82028202800.5计划评审技术计划评审技术PERTl PERT的产生的产

19、生 关键路线法中，工序时间是确定值，而对研究性的工关键路线法中，工序时间是确定值，而对研究性的工序来说，序来说， t（i，j）是随机的。）是随机的。1958年美国海军武器局年美国海军武器局研制北极星导弹时提出，重点在于计划的评审。研制北极星导弹时提出，重点在于计划的评审。l PERT的时间估计的时间估计 采用三种时间估计法采用三种时间估计法a最最乐观时间，乐观时间，b最悲观时间，最悲观时间，m最可能时间，则最可能时间，则 工序期望时间工序期望时间 te 方差方差 e2（ ）2a+4m+b 6ba6时时 间间 优优 化化 网 络 图网 络 图 P E R T 技 术 的 优 化技 术 的 优 化

20、 , , 分 多 种 ：分 多 种 ： 有有时 间 优 化 、 时 间时 间 优 化 、 时 间 费 用 优 化 和 时 间 费 用 费 用 优 化 和 时 间 费 用 资 源 利 用 优 化资 源 利 用 优 化 等 。等 。 我 们 在我 们 在 这 里 简 单 介 绍这 里 简 单 介 绍 时 间时 间优 化优 化 和 时 间和 时 间 费 用 优 化 费 用 优 化 。 时 间。 时 间 优 化 主 要优 化 主 要 是是 在在以 下以 下 两 方 面 进 行两 方 面 进 行 工 作工 作 ： 向 关 键 线 路 要 时 间 ： 尽 可 能 节 省 时 间 ；向 关 键 线 路 要

21、时 间 ： 尽 可 能 节 省 时 间 ； 向 非 关 键 线 路 要 资 源 ： 在 非 关 键 线 路向 非 关 键 线 路 要 资 源 ： 在 非 关 键 线 路 调调整 人 员 、 资 金整 人 员 、 资 金 、 物 资 等 ， 集 中 到 关 键 线 路、 物 资 等 ， 集 中 到 关 键 线 路 ，使 得 关 键 线 路使 得 关 键 线 路 有 所有 所 突 破突 破 。时时 间间 费费 用用 优优 化化l 时间和费用双目标优化时间和费用双目标优化，一般来讲二者是矛盾的。通过，一般来讲二者是矛盾的。通过仔细分析，寻找既省时又省钱的方案，即最低成本日程仔细分析，寻找既省时又省钱

22、的方案，即最低成本日程。l 费用费用：直接费用和间接费用：直接费用和间接费用l 直接费用直接费用：建造工程本身所需材料、人工：建造工程本身所需材料、人工l 间接费用间接费用：工程所需管理费用、设备租金：工程所需管理费用、设备租金ct间接费用间接费用总费用总费用直接费用直接费用赶工赶工：直接费用增加，间接：直接费用增加，间接费用减少。间接费用是常量费用减少。间接费用是常量直接费用简化为常量处理。直接费用简化为常量处理。则：则：赶工直接费用率赶工直接费用率费用差费用差时间差时间差课课 后后 作作 业业 请请 同学们根据网络关键路线法求出下面网络计划图的关同学们根据网络关键路线法求出下面网络计划图的

23、关键路线。键路线。164325426435404281015151110480（0）（3）（0）（3）（6）（0）（6）关键线路：时差为零的作业连接而成的线路关键线路：时差为零的作业连接而成的线路 答答 案案1.1.建立层次结构模型建立层次结构模型 该结构图包括目标层，准则层，方案层。该结构图包括目标层，准则层，方案层。层次分析法的基本步骤归纳如下层次分析法的基本步骤归纳如下3.3.计算单排序权向量并做一致性检验计算单排序权向量并做一致性检验2.2.构造成对比较矩阵构造成对比较矩阵从第二层开始用成对比较矩阵和从第二层开始用成对比较矩阵和1 19 9尺度。尺度。对每个成对比较矩阵计算最大特征值及

24、其对应的特征向量，对每个成对比较矩阵计算最大特征值及其对应的特征向量，利用一致性指标、随机一致性指标和一致性比率做一致性利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通过，特征向量（归一化后）即为权向量；检验。若检验通过，特征向量（归一化后）即为权向量；若不通过，需要重新构造成对比较矩阵。若不通过，需要重新构造成对比较矩阵。目标层目标层选一领导干部选一领导干部 准则层准则层 1P2P3P 方案层方案层 健康状况健康状况业务知识业务知识口才口才写作能力写作能力工作作风工作作风政策水平政策水平建立层次结构模型建立层次结构模型1132221133/1113/13/115/14/14/

25、12/13512/112/1142112/114111A健康情况健康情况业务知识业务知识写作能力写作能力口才口才政策水平政策水平工作作风工作作风健康情况健康情况业务知识业务知识写作能力写作能力口才口才政策水平政策水平工作作风工作作风A的最大特征值的最大特征值,35. 6max相应的特征向量为：相应的特征向量为：TW)30. 0 ,12. 0 ,05. 0 ,19. 0 ,19. 0 ,16. 0()2(构造成对比较矩阵及构造成对比较矩阵及层次单排序层次单排序07.016635.6CI一致性指标一致性指标随机一致性指标随机一致性指标 RI=1.24 (查表查表)一致性比率一致性比率CR=0.07

26、/1.24=0.05650.1通过一致性检验通过一致性检验假设假设3人关于人关于6个标准的判断矩阵为：个标准的判断矩阵为：13/123142/14/11)3(1B健康情况健康情况1252/1144/14/11)3(2B业务知识业务知识113113/13/131)3(3B写作能力写作能力17/15/171353/11)3(4B口才口才17/17/1711711)3(5B政策水平政策水平15/19/1517/1971)3(6B工作作风工作作风由此可求得各属性的最大特征值和相应的特征向量。由此可求得各属性的最大特征值和相应的特征向量。特征值特征值健康情况健康情况 业务知识业务知识 写作能力写作能力

27、口才口才 政策水平政策水平 工作作工作作风风 3.02 3.02 3.05 3.05 3.00 3.02max各属性的最大特征值各属性的最大特征值05. 007. 007. 046. 057. 024. 017. 047. 065. 022. 033. 063. 077. 047. 028. 032. 010. 014. 0)3(W均通过一致性检验均通过一致性检验从而有从而有30. 012. 005. 019. 019. 016. 005. 007. 007. 046. 057. 024. 017. 047. 065. 022. 033. 063. 077. 047. 028. 032. 010. 014. 0)2()3(WWW26. 034. 040. 0W即在即在3人中应选择人中应选择A担任领导职务。担任领导职务。层次总排序及一致性检验层次总排序及一致性检验怎么样选择对象（项目）怎么样选择对象（项目）期望值期望值= 1A1 +2A2 + 3 A3 + 4 A4 +5 A5+ 6 A6 +7 A7 +8 A8期望值期望值= 1A1 +2A2 + 3 A3 + 4 A4 +5 A5+ 6 A6 +7 A7 +8 A8课堂复习与练习课堂复习与练习1 1、