运筹学讲义 1.给顶点①以标号t(1)=0 2按照统筹图中各顶点的编号顺序,依次给顶点回,…,回以标号1(2)…,(n) 其中()=max{t(k)+w(k,i)},i=2,3,…,n,w(k,是弧(k,i)的长度,并 将取最大值的弧(k,)改为粗线 3.当顶点○被标号时,即得一条关键路线,且其长度为r(n) 注:顶点O的标号(i)恰是以顶点①为开工事项的工序的最早可能开工时间特别地,t(m)是生 产过程的完工期. 求统筹图的关键路线的标号法与求解最短路问题的 Di jkstra算法既有所类似,又有根本区别 (1)标号法是求最长路,而 Di jkstra算法是求最短路;(2)对标号法,下一个待标号的顶点是在计 算前按照各顶点的编号顺序依次确定下来的,而对 Dijkstra算法,下一个待标号的顶点是在上一个 顶点被标号后,对尚未被标号的顶点通过搜索确定的 例1求下面统筹图的一个关键路 解:利用标号法,得 0(1 关键路线有两条,分别为①→③→④→>⑥→⑦和①→③→⑥→⑦,其长度均为20.L 统筹图中有关参数的计算:运 筹 学 讲 义 2 1.给顶点○1 以标号 t(1) = 0. 2.按照统筹图中各顶点的编号顺序，依次给顶点○2 ，…，○n 以标号 t(2), ,t(n) ， 其中 t(i) max{t(k) w(k,i)} k i = +  ，i = 2,3,  ,n，w(k,i) 是弧 (k,i) 的长度，并 将取最大值的弧 (k,i) 改为粗线. 3.当顶点○n 被标号时，即得一条关键路线，且其长度为 t(n) . 注：顶点○i 的标号 t(i) 恰是以顶点○i 为开工事项的工序的最早可能开工时间.特别地， t(n) 是生 产过程的完工期. 求统筹图的关键路线的标号法与求解最短路问题的 Dijkstra 算法既有所类似，又有根本区别： （1）标号法是求最长路，而 Dijkstra 算法是求最短路；（2）对标号法，下一个待标号的顶点是在计 算前按照各顶点的编号顺序依次确定下来的，而对 Dijkstra 算法，下一个待标号的顶点是在上一个 顶点被标号后，对尚未被标号的顶点通过搜索确定的. 例 1 求下面统筹图的一个关键路线： 解：利用标号法，得  关键路线有两条，分别为○1 → ○3 → ○4 → ○6 → ○7 和○1 → ○3 → ○6 → ○7 ，其长度均为 20.▍ 统筹图中有关参数的计算：