运筹学教学课件.ppt

1、运筹学教学课件运筹学教学课件 上海理工大学上海理工大学 管理学院管理学院 系统科学研究所系统科学研究所 目 录 第一章 线性规划 第二章 整数规划 第三章 动态规划 第四章 图与网络 第五章 决 策 论 第六章 矩阵对策 第一章 线性规划 数学模型 图解法 可行域的性质 单纯形法 单纯形表 单纯形法的矩阵描述 对偶规划 运输问题 数学模型 线性规划模型的结构 目标函数：max，min max z(min f)=cjxj 约束条件：,=, aijxj (=, ) bi (i=1,2, n) 变量符号：0,unr,0 xj 0 (j=1,2, n) 线性规划的标准形式 目标函数：max max z

2、=cjxj 约束条件 ：= aijxj = bi (i=1,2, n) 变量符号 ：0 xj 0 (j=1,2, n) 典型问题：典型问题： 合理下料问题合理下料问题 典型问题：典型问题： 合理下料问题合理下料问题 运输问题运输问题 典型问题：典型问题： 合理下料问题合理下料问题 运输问题运输问题 生产的组织与计划问题生产的组织与计划问题 典型问题：典型问题： 合理下料问题合理下料问题 运输问题运输问题 生产的组织与计划问题生产的组织与计划问题 投资证券组合问题投资证券组合问题 典型问题：典型问题： 合理下料问题合理下料问题 运输问题运输问题 生产的组织与计划问题生产的组织与计划问题 投资证券

3、组合问题投资证券组合问题 分派问题分派问题 典型问题：典型问题： 合理下料问题合理下料问题 运输问题运输问题 生产的组织与计划问题生产的组织与计划问题 投资证券组合问题投资证券组合问题 分派问题分派问题 生产工艺优化问题生产工艺优化问题 线性规划的图解 x1 x2 目标函数等值线 可行域 最优解 6 6 -8 4 max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20 可行域的性质 线性规划的最优解在极点上 线性规划的可行域是凸集 极点 凸集 不是凸集 凸集 二个重要结论：二个重要结论： 满足约束条件的可行域一般都满足约束条件的可行域一般都 构成凸多边形。这一

4、事实可以构成凸多边形。这一事实可以 推广到更多变量的场合。推广到更多变量的场合。 二个重要结论：二个重要结论： 满足约束条件的可行域一般都满足约束条件的可行域一般都 构成凸多边形。这一事实可以构成凸多边形。这一事实可以 推广到更多变量的场合。推广到更多变量的场合。 最优解必定能在凸多边形的某最优解必定能在凸多边形的某 一个顶点上取得，这一事实也一个顶点上取得，这一事实也 可以推广到更多变量的场合。可以推广到更多变量的场合。 解的讨论：解的讨论： 最优解是唯一解最优解是唯一解； 解的讨论：解的讨论： 最优解是唯一解最优解是唯一解； 无穷多组最优解：无穷多组最优解： 例：例： max z=40x1

5、+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1,x2 0 x2 50 40 30 20 10 10 20 30 40 x1 可行域可行域 目标函数是同约束目标函数是同约束 条件：条件：4x1+3x2 120 平行的直线平行的直线 x2 50 40 30 20 10 10 20 30 40 x1 可行域可行域 当当z z的值增加时，目的值增加时，目 标函数与约束条件：标函数与约束条件： 4x4x1 1+3x+3x2 2 120 120 重合，重合，Q Q1 1与与Q Q2 2之间都之间都 是最优解。是最优解。 Q1（25，0） Q2（15，20） 解的讨论：解的讨论： 无

6、界解：无界解： 例：例：max z=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1,x2 0 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界，目标函该可行域无界，目标函 数值可增加到无穷大，数值可增加到无穷大， 称这种情况为无界解或称这种情况为无界解或 无最优解。无最优解。 解的讨论：解的讨论： 无可行解：无可行解： 例：例：max S=2x1+3x2 s.t. x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0 该问题可行域为该问题可行域为 空集，即无可行空集，即无可行 解，也不存在最解，也不存在最 优解。优解。 解的

7、情况：解的情况： 有可行解有可行解 有唯一最优解有唯一最优解 有无穷最优解有无穷最优解 无最优解无最优解 无可行解无可行解 单纯形法的引例 例： max z=31x1+22x2 s.t. 6x1+ 2x2180 4x1+10x2400 3x1+5x2210 x1,x20 写成标准型为： max z=31x1+22x2 6x1+2xx+x3 =180 4x1+10x2 +x4 =400 3x1+5x2 +x5=210 xj0 (j=1,2,5) max z=31x1+22x2 6 x1+ 2 x2 + x3 =180 4 x1+10 x2 + x4 =400 3 x1+ 5 x2 + x5=21

8、0 xj0 (j=1,2,5) 基变量XB=(x3 , x4 , x5)T,非基变量XN=(x1 , x2)T,令所有非 基变量为0，则得初始可行解为X(0)=(0,0,180,400,210)T, 对应z(0)=0 取目标函数最大正系数对应的非基变量为入基变量； 取最小比值所对应方程的基变量为出基变量。本例中， 取 x1为入基变量， x3为出基变量。 x1+ 1/3x2 +1/6x3 = 30 26/3x2 -2/3x3 +x4 =280 4x2 -1/2x3 +x5 =120 令非基变量x2=x3=0,z(1)=930,相应的基可行解为 x(1)=(30,0,0,280,120)T 为使目

9、标函数中不出现基变量，消去x1，得 z=31(30-1/3x2-1/6x3)+22x2=930+35/3x2-31/6x3 由于非基变量x2的系数为正，故将x2作为入 基变量，z值仍可变大，即X(1)还不是最优解。 再次迭代得， x1 +5/24x3 1/12x5=20 5/12x3 +x4 13/6x5 =20 x2 1/8x3 +1/4x5 =30 同理，为使目标函数中不出现基变量，消去x2，得 z = 93035/3(301/8x31/4x5)31/6x3 = 128089/24x335/12x5 （*） 令非基变量x3=x5=0,得z(2)=1280,相应的基可 行解为X(2)=(20

10、,30,0,20,0)T. 由于（*）式中，非基变量x3,x5的系数皆为 负，故若将其作为入基变量，均只能使z值 减小而非增大。由此，X （2）已是最优解 X*,z(2)为对应的最优值z*. 单纯形表 写出单纯形表 max z=31x1+22x2 6 x1+ 2 x2 + x3 =180 4 x1+10 x2 + x4 =400 3 x1+ 5 x2 + x5=210 xj0 (j=1,2,5) cj 31 22 0 0 0 i CB XB b x1 x2 x3 x4 x5 0 0 0 X3 X4 X5 180 400 210 6 2 1 0 0 4 10 0 1 0 3 5 0 0 1 18

11、0/6 400/4 210/3 -z 0 31 22 0 0 0 作旋转变幻的新单纯形表 cj 31 22 0 0 0 i CB XB b x1 x2 x3 x4 x5 31 0 0 x1 x4 x5 30 280 120 1 1/3 1/6 0 0 0 26/3 -2/3 1 0 0 4 -1/2 0 1 90 420/1 3 30 -z -930 0 35/3 -31/6 0 得 新 基 可 行 解 X(1)=(30,0,0,280,120)T. 因 唯 有 2=35/30，x2为入基变量，又因比值最小在第 三行，故x5为出基变量。合之，知主元为4。作旋 转变化得下表 cj 31 22 0

12、 0 0 CB XB b x1 x2 x3 x4 x5 31 0 22 x1 x4 x5 20 20 30 1 0 5/24 0 -1/12 0 0 5/12 1 -13/6 0 1 -1/8 0 1/4 -z -1280 0 0 -89/24 0 -35/12 因所有检验数 j0(j=1,2,5),故当 前基可行解X(2)=(20,30,0,20,0)T即为最 优解X*,最优值为z*=1280. 单纯形法的矩阵描述单纯形法的矩阵描述 其矩阵形式为： max z=CBXBCNXN s.t. BXBNXN=b b XB ,XN0 矩阵描述之初始单纯形表 先取初始单位阵I作为初始基阵B，得 初始单

13、纯形表： cj CA CI CB XB b XA XI CI XI b A I -z -CIb CACII-1A CICII-1A 矩阵描述之迭代单纯形表 cj CA CI CB XB b XA XI CB XB B-1b B-1A B-1I -z -CBB-1b CACBB-1A CICBB-1I 再选某一基阵B进行迭代，得 迭代单纯形表： 对偶规划 DUAL 定义： 设有原规划： max z = CX AXb X0 其对偶规划为： min f =Yb YAC Y0 原规划与对偶规划的线性关系 原（对偶）规划 对偶（原）规划 目标 max z min f 目标 变量 n个 0 0 自由 n个

14、 = 约束 约束 m个 = m个 0 0 自由 变量 限制向量 价值向量 价值向量 限制向量 运输问题运输问题 运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 最小元素法、差值法 判别最优方案 位势法 2 3 2 1 3 4 1 运输问题网络图 s2=27 s3=19 d1=22 d2=13 d3=12 d4=13 s1=14 供 应 量 供应地 运价 需 求 量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 运输问题线性规划模型 0xxxxxxxxxxxx 13xxx 12xxx 13xxx 22xxx 19xxxx 27xxxx 14xxxxs.t. x6x10x

15、9x5x7x2x4x8x3x5x7x6zmin 343332312423222114131211 342414 332313 322212 312111 34333231 24232221 14131211 343332312423222114131211 供 应 地 约 束 需 求 地 约 束 运输问题的表格表示 1 2 3 4 6 7 5 3 1 x11 x12 x13 x14 14 8 4 2 7 2 x21 x22 x23 x24 27 5 9 10 6 3 x31 x32 x33 x34 19 22 13 12 13 最小元素法（1） 1234 6753 114 8427 2 12

16、2715 59106 319 22131213 0 最小元素法（2） 1234 6753 1 13 141 8427 2 12 2715 59106 319 22131213 00 最小元素法（3） 1234 6753 1 13 141 8427 2 1312 272 59106 319 22131213 000 最小元素法（4） 1 2 3 4 6 7 5 3 1 13 14 1 8 4 2 7 2 13 12 27 2 5 9 10 6 3 19 19 0 22 13 12 13 3 0 0 0 最小元素法（5） 1234 6753 1 113 140 8427 2 1312 272 59

17、106 3 19 190 22131213 2000 最小元素法（6） 1234 6753 1 113 140 8427 2 21312 270 59106 3 19 190 22131213 0000 表上作业法差值法(1) 1 2 3 4 hi 6 7 5 3 1 14 2 8 4 2 7 2 27 2 5 9 10 6 3 19 1 22 13 12 13 kj 1 3 3 3 计算各行各列中最小两个运价之差值 差值法(2) 1 2 3 4 hi 6 7 5 3 1 14 2 8 4 2 7 2 13 14 5 5 9 10 6 3 19 1 22 0 12 13 kj 1 3 3 除第

18、二列外重新计算差值 1 2 3 4 hi 6 7 5 3 1 14 3 8 4 2 7 2 13 12 2 1 5 9 10 6 3 19 1 22 0 0 13 kj 1 3 差值法(3) 1 2 3 4 hi 6 7 5 3 1 13 1 6 8 4 2 7 2 13 12 2 8 5 9 10 6 3 19 5 22 0 0 0 kj 1 差值法(4) 1 2 3 4 hi 6 7 5 3 1 13 1 6 8 4 2 7 2 2 13 12 0 5 9 10 6 3 19 5 20 0 0 0 kj 1 差值法(5) 1 2 3 4 hi 6 7 5 3 1 1 13 0 8 4 2

19、7 2 2 13 12 0 5 9 10 6 3 19 5 19 0 0 0 kj 5 差值法(6) 1 2 3 4 hi 6 7 5 3 1 1 13 0 8 4 2 7 2 2 13 12 0 5 9 10 6 3 19 0 0 0 0 0 kj 差值法(7) 判别最优方案位势法 1 2 3 4 ai ui 6 7 5 5 5 3 1 1 13 14 0 8 4 2 7 2 2 2 13 12 27 2 5 9 8 10 11 6 4 3 19 19 -1 bj 22 13 12 13 vj 6 2 0 3 本例中，每个含格所对应的 ijij=c =cij ij- -u ui i- -v

20、vj j均为非负， 故所得方案已是最优方案 1 2 3 4 ai 6 9 12 7 1 8 7 45 60 1 3 6 1 2 42 42 5 1 3 4 3 30 18 48 bj 50 30 25 45 位势法(2) 例：已知初始方案如下表所示，检验并改 进至最优方案。 6 9 -1 12 7 1 8 7 45 60 0 1 3 -2 6 -1 1 -1 2 42 42 -5 5 8 1 3 4 6 3 30 18 48 -9 bj 50 30 25 45 vj 6 10 12 7 位势法(3) 1 2 5 4 3 6 位势法(4) 6 9 1 12 2 7 1 15 45 60 0 1

21、3 6 1 1 -1 2 35 7 42 -5 5 6 1 3 4 4 3 23 25 48 -7 bj 50 30 25 45 vj 6 8 10 7 1 2 3 4 6 9 0 12 1 7 1 50 10 60 0 1 1 3 6 1 1 2 7 35 42 -6 5 7 1 3 4 5 3 23 25 48 -8 bj 50 30 25 45 vj 6 9 11 7 位势法(5) 第二章 整数规划 分枝定界法 0-1型整数规划 分配问题 例1：讨论纯整数规划 max z=x1+2x2 s.t. 2x1+5x215 2x12x25 x1 , x20且为整数 分枝定界法 不考虑x1,x2为

22、整数的 限制条件，得规划（0） 对应的最优解与最优值 为 （0） R0 z 2x15x2=15 3 2.5 分枝定界法(1) 14 11 6z ,) 7 3 ,1 14 13 (3X T 考察X的某一分量，不妨选x2= ,因为1x22,为了使x2整数 化,剔除1x22对应的可行域.为此,增加约束条件x21及x22, 于是可行域R0可分解成两个小可行域R1和R2.原规划(0)分解 成规划(1)与规划(2): (1) （2） max z=x1+2x2 max z=x1+2x2 s.t. 2x1+5x215 s.t. 2x1+5x215 2x1-2x25 2x1-2x25 x21 x22 x1,x2

23、0且为整数 x1,x20且为整数 分枝定界法（2） 仿上求解，得规划（1）、 （2）对应的最优解与最优 值为： R2 R1 z 3 x1 2 1 1 2 3 x2 （1） （2） 分枝定界法(3) 2 1 5,) 1 , 2 1 3 (zX T 2 1 6,) 2 , 2 1 2 (zX T 考察(1)、(2)，因规划（2）的z值优于规划（1）的z值， 故先分解规划（2）。仿上，R2分解成R3与R4= 。规 划（2）分解成规划（3）与规划（4）： 分枝定界法(4) (1) （2） max z=x1+2x2 max z=x1+2x2 s.t. 2x1+5x215 s.t. 2x1+5x215 2

24、x1-2x25 2x1-2x25 x22 x22 x1 2 x1 3 x1,x20且为整数 x1,x20且为整数 分枝定界法(5) 仿上求解，得规划（1）、 （2）对应的最优解与最优 值为： （3） （4） R3 R1 z 3 x2 3 2 1 1 2 x1 5 2 6,) 5 1 2 , 2 (zX T无可行解, 剪枝 考察(1)、(3)，因规划（3）的z值优于规划（1）的z值， 故先分解规划（3）。仿上，R3分解成R5与R6。规划 （3）分解成规划（5）与规划（6）： 分枝定界法(6) (5) （6） max z=x1+2x2 max z=x1+2x2 s.t. 2x1+5x215 s.t

25、. 2x1+5x215 2x1-2x25 2x1-2x25 x22 x22 x1 2 x1 2 x22 x23 x1,x20且为整数 x1,x20且为整数 分枝定界法(7) 仿上求解，得规划（1）、 （2）对应的最优解与最 优值为： （5） （6） X=(2,2)T, z=6 X=(0,3)T, z=6 R1 R5 z x2 2 1 1 2 3 x1 01型整数规划(1) 0 1 2 3 4 显枚举法： 例：求解下列01规划 max z=3x12x25x3 s.t. x12x2x32 x14x2x34 x13x2 3 4x23x36 01型整数规划(2) 按二进位制穷举01变量xj（j=1，2

26、，3）构成 的解X=(x1,x2,x3)T,共有8种可能组合。先检查哪 些是可行解，再从中选最优解。 约束条件左端值 z 值 （x1,x2,x3） 1 2 3 4 可行性 0 (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) 0 0 0 0 -1 1 0 3 2 4 3 4 1 5 3 7 1 1 1 0 0 2 1 3 3 5 4 4 2 6 4 7 + + + + + 0 5 -2 3 3 8* 1 6 01型整数规划(3) 分析上述求解过程，对显枚举法作相应的改进 后，其计算见表如下，此即为隐枚举法： z 值

27、约束条件左端值 （x1,x2,x3） 0 1 2 3 4 可行性 (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) 0 5 -2 3 3 8* 1 6 0 0 0 0 -1 1 0 3 0 2 1 3 + + + 分配问题 一般最小分配问题的数学模型为: min f=cijxij s.t. xij=1 (i=1,2,n) xij=1 (j=1,2,n) xij=0或1 (i,j=1,2,n) 目标函数最大的分配问题可化为目标函数最小的分配 问题来求解。可取一个比所有cij都大的整数k，令 cij=kcij即可。以ci

28、j为价值系数求最大分配就等 价于以cij为价值系数求最小分配。 1、缩减矩阵 分配问题解法匈牙利法 2.0 4.2 3.4 4.0 3.5 4.5 1.0 3.6 3.6 1.8 2.5 1.9 3.0 2.1 1.8 3.0 -2.0 -1.0 -1.8 -1.8 0 2.2 1.4 2.0 2.5 3.5 0 2.6 1.8 0 0.7 0.1 1.2 0.3 0 1.2 -0.1 0 2.2 1.4 1.9 2.5 3.5 0 2.5 1.8 0 0.7 0 1.2 0.3 0 1.1 2、初始分配 匈牙利法（2） 0 2.2 1.4 1.9 2.5 3.5 0 2.5 1.8 0 0.

29、7 0 1.2 0.3 0 1.1 3、行列标号 匈牙利法（3） s 0 2.2 1.4 1.9 2.5 3.5 0 2.5 1.8 0 0.7 0 1.2 0.3 0 1.1 4 3 4、继续缩减 匈牙利法（4） s 0 2.2 1.4 1.9 2.5 3.5 0 2.5 1.8 0 0.7 0 1.2 0.3 0 1.1 4 3 =0.3 0 2.2 1.7 1.9 2.2 3.2 0 2.2 1.8 0 1.0 0 0.9 0 0 0.8 s 4 4 2 3 3 0 2.2 1.7 1.9 2.2 3.2 0 2.2 1.8 0 1.0 0 0.9 0 0 0.8 5、调整分配 而今 0

30、 已满4个，故得最优分配，最优解为： 匈牙利法（5） 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 X*= 第三章 动态规划(DP) 不定阶段最短路线问题 资源分配问题 排序问题 求如图所示交通图中点i =1,2,3,4到点5的最短路线 及路长。 一、不定阶段最短路线问题 5 3 2 4 1 2 3 2 6 7 5 5 1 0.5 5 1、迭代运算 m i j 1 2 3 4 5 f(m)(i) u(m)(i) 1 2 3 4 0 6 5 2 2 6 0 0.5 5 7 5 0.5 0 1 5 2 5 1 0 3 2 7 5 3 5 5 5 5 * 5 3 2 4 1 2 3

31、 2 6 7 5 5 1 0.5 5 f(1)=d() =2 5 3 2 4 1 2 3 2 6 7 5 5 1 0.5 m i j 1 2 3 4 5 f (m)(i) u (m)(i) 2 3 4 6+2 0+7 0.5+5 5+3 7+0 5+2 0.5+7 0+5 1+3 5+0 2+2 5+7 1+5 0+3 3+0 5.5 4 3 3 4 5 * f(4)=d()=3 5 3 2 4 1 2 3 2 6 7 5 5 1 0.5 m i j 1 2 3 4 5 f (m)(i) u (m)(i) 2 3 6+2 0+5.5 0.5+4 5+3 7+0 5+2 0.5+5.5 0+4

32、1+3 5+0 4.5 4 3 4 * f(3)=d() +f(4)=1+3=4 5 3 2 4 1 2 3 2 6 7 5 5 1 0.5 m i j 1 2 3 4 5 f (m)(i) u (m)(i) 2 6+2 0+5.5 0.5+4 5+3 7+0 4.5 3 f(2)=d()+f(3)=0.5+4=4.5 * 5 3 2 4 1 2 3 2 6 7 5 5 1 0.5 2、最优方案 i R*(i) r*(i) m*(i) 1 2 3 4 15 2345 345 45 2 4.5 4 3 1 3 2 1 例：工厂有五台设备分配给编号为j=1，2，3的三个 车间。各种可能的分配台数x

33、i及其对应的经济收益 gi(xi)(万元)数据如下表所示： 问：应如何分配给车间设备的台数，才能使总收益 最大？ 二、资源分配问题 gj(xi) j i 1 2 3 0 1 2 3 4 5 0 0 0 3 5 4 7 10 6 9 11 11 12 11 12 13 11 12 ）阶段变量k表示把当前留存的设备以某一台数分配给k号 车间（k=1,2,3）。 ）状态变量yk表示第k阶段开始时留存的设备台数。 ）决策变量xk表示把当前留存的设备分配给k号车间的台数， 对应的决策集合为： xk|xk=0,1,yk k=1,2 Dk(yk)= x3|x3=y3 k=3 )转移方程 yk+1=ykxk

34、)目标函数 Vk3=gj(xj) (k=1,2,3) )基本方程 fk(yk)=maxgk(xk)+fk+1(ykxk) f4(y4)=0 (k=3,2,1) 1、动态规划模型 2、逆序计算表 k yk xk yk+1 gk(xk) fk+1(yk+1) gk(xk)+fk+1(yk+1) fk(yk) xk * 0 0 0 0 0 0 0 0 1 1 0 4 0 4 4 1 2 2 0 6 0 6 6 2 3 3 0 11 0 11 11 3 4 4 0 12 0 12 12 4 3 5 5 0 12 0 12 12 5 k yk xk yk+1 gk(xk) fk+1(yk+1) gk(x

35、k)+fk+1(yk+1) fk(yk) xk* 0 0 0 0 0 0 0 0 0 1 0 4 4 1 1 0 5 0 5 5 1 0 2 0 6 6 1 1 5 4 9 2 2 0 10 0 10 10 2 0 3 0 11 11 1 2 5 6 11 2 1 10 4 14 3 3 0 11 0 11 14 2 0 4 0 12 12 1 3 5 11 16 2 2 10 6 16 3 1 11 4 15 4 4 0 12 0 12 16 16 1 2 0 5 0 12 12 1 4 5 12 17 2 3 10 11 21 3 2 11 6 17 4 1 11 4 15 2 5 5 0

36、 11 0 11 21 2 k yk xk yk+1 gk(xk) fk+1(yk+1) gk(xk)+fk+1(yk+1) fk(yk) xk* 0 5 0 21 21 1 4 3 16 19 2 3 7 14 21 3 2 9 10 19 4 1 12 5 17 1 5 5 0 13 0 13 21 21 0 2 3、最优策略 有两个最优策略 P13*=0,2,3或2,2,1 4、最优方案 车间 1 2 3 0 2 3 设备（台） 2 2 1 收益（万元） 21 最优排序方法： 1.求mina1, a2, a3,an;b1,b2, ,bn，此值记作m 2.当m=ai时，则把工件i排在首位，

37、并从初始工件集 w中去掉工件i。工件i不唯一时，可任选一个。 3.当m=bi时，则把工件i排在末位。并从初始工件集 w中去掉工件i，工件i不唯一时，可任选一个。 4、对新得的工件集wi重复步骤1、2、3，直至w成 为空集，停止 三、排序问题 例：设有2*5排序问题，数据如下表所示， 求最优顺序。 解：按最优排序规则，可得如下最优顺序： 2 155 工时 工件 工序 1 2 3 4 5 A B 2 4 8 6 2 5 1 4 8 5 5 1 2 3 3 3 3 4 4 4 4 第四章 图与网络 图的基本概念 树的性质 中国邮递员问题 有向图与最短路问题 最大流问题 A B D C 非空点集V与连

38、接点的某个线集E之二元组合 称为图 ，记作G=(V,E). 点与有向边 每一条边和两个邻点关联，一条边可以用 两个邻点的标号表示（i，j） j i 路径（Path） 前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4) 4 3 1 2 链（Chain） 前后相继并且方向不一定相同 的边序列称为链 C=(1,2),(3,2),(3,4) 4 1 3 2 回路（Circuit） 起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同 2 3 1 4 圈(Cycle) 起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3) 圈中各

39、条边方向不一定相同 4 2 1 3 连通图 任意两个节点之间至少有一条 链的图称为连通图 树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称 为悬挂节点 2 4 3 5 1 任何树至少有一个悬挂点 p个顶点的树T含p1条边 树T中任意两点之间存在唯一 的一条链 树T中不相邻两点之间连一条 边，则形成唯一的圈 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 当连通图G=(V,E)的部分子图为 树T，则称T为G得支撑树，记作 T=(V,E),其中E包含于E 4 2 3 1 4 2 3 1 4 2 3 1 3 4 2 1 4 2 3 1 4 2 3 1 4 2 3 1 定理

40、设连通非负赋权图，R为蕴含E的圈。R有最小总数 的充分必要条件为 （1）每边最多重复一次； （2）在G的每个圈上，重复边总权不超过圈总权 之半。 如图所示之G是一幅街道图，点v6表示邮局。 求最优投递路线。 1 4 5 2 1 3 2 2 6 3 2 v1 v3 v1 v2 v4 v5 v6 G含两个奇点v2, v4。 取链取链v2, v6, v5, v4,作重复边作重复边，得得Euler图图G(0),有有 Euler圈圈R(0)，总权是总权是40 v3 v1 v2 v4 v5 v6 R(0)满足条件1 检验条件检验条件2。取圈。取圈v1, v5, v4, v1调整的调整的G(1), 有有R(

41、1),总权是总权是39。 v3 v1 v2 v4 v5 v6 取圈取圈v2, v3, v5, v2，调整得调整得G(2),有有R(2)， 总权是总权是37。 v3 v1 v2 v4 v5 v6 逐圈检验逐圈检验。得得G(2) =G*, 其上任一个其上任一个Euler圈皆圈皆 为为R*.例如可取例如可取R*= v6, v2, v3, v4 v1, v2, v3, v5 v1, v6, v3, v5 v1, v4, v5, v6 有向图与最短路问题 1、顺序标号法 例：如图是一个单项道路系统。大批物资集中在出发 地S，要求用车尽快运输到目的地T。A,B,C,D,E是 中间站。图中数字为相邻两站间的

42、路程。 S A B C D E T 2 5 2 7 4 1 4 3 4 5 7 1 S A B C D E T 2 5 2 7 4 1 4 3 4 5 7 1 v5 v2 v3 v4 v1 v6 v7 0 2 4 4 8 7 13 由此而得两条从v1到v7的最短路R7* : v1, v2, v3, v6, v7与v1, v2, v3, v5, v6, v7 2、递推标号法 求如图所示D的从v1到v8的最短路R8*及 路长ri* v1 v2 v4 v3 v5 v6 v7 v8 6 -1 -2 8 3 -1 2 1 -1 2 -3 7 -5 -3 -5 1 1 wij vj vi 1 2 3 4

43、5 6 7 8 rj (k) k vj 0 1 2 3 4 R8 * 1 0 -1 -2 3 1 0 0 0 0 0 * 2 6 0 2 2 -1 -5 -5 -5 -5 3 -3 0 -5 1 3 -2 -2 -2 -2 -2 * 4 0 2 4 3 -7 -7 -7 -7 * 5 -1 0 -3 5 1 -3 -3 -3 6 1 0 1 7 6 -1 -1 -1 -1 7 -1 0 -5 7 5 -5 -5 -5 * 8 0 8 -2 -10 -10 * 得一条最短路 R8*=v1, v3, v4, v7, v8 路长为r8* =-10 无向图求最短路算法 求如图所示之G的从v1到v8的最短路R8*及路长 r8*. v1 v2 v3 v4 v5 v6 v7 v8 4 2 8 1 6 7 1 2 2 9 3 4 9 6 2 v1 v2 v3 v4 v5 v6 v7 v8 4 2 8 1 6 7 1 2 2 9 3 4 9 6 2 ri* tj k vt 0 1 2 3