《管理科学方法》总复习

1、考试题型考试题型一、模型建立（一、模型建立（15分）分）二、线性规划基本概念（二、线性规划基本概念（10分）分）三、非线性规划求解（三、非线性规划求解（10分）分）四、线性规划求解（图解法和单纯性法）四、线性规划求解（图解法和单纯性法）（25分）分）五、运输问题求解（五、运输问题求解（15分）分）六、指派问题求解（六、指派问题求解（10分）分）七、图论（七、图论（15分）分）运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线性规划模型及求解线性规划模型及求解Linear ProgrammingLinear Programming第二章第二章重点是：基本概念、图解法、单纯型法

2、重点是：基本概念、图解法、单纯型法1、将线性规划模型化为标准型、将线性规划模型化为标准型2、写出标准型规划问题的矩阵表达式、写出标准型规划问题的矩阵表达式3、写出标准型规划问题的技术系数矩、写出标准型规划问题的技术系数矩阵阵A，资源向量，资源向量b，价格系数向量，价格系数向量c，决策变量决策变量X，列出相应的剩余变量和，列出相应的剩余变量和松弛变量松弛变量 不限原非标准型321321321321321, 0, 020040065300432. .423min:xxxxxxxxxxxxtsxxxz 0, 2004006653004432. .0004423max:6543321633215332

3、1433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxZ标准型写出标准型规划问题的矩阵表达式写出标准型规划问题的矩阵表达式. .maxt sZ0XbAXCXX=x1,x2,x3,x3,x4,x5,x6TC=3,2,-4,4,0,0,0b=300,400,200T A=-2 3 4 -4 -1 0 0 -1 5 6 -6 0 1 0-1 1 1 -1 0 0 1 其中：剩余变量是：剩余变量是：x4松弛变量是：松弛变量是：x5,x6例题例题 已知下列线性规划模型，将其化为标准型，写出相应的矩阵表达式，并写出相应的技术系数矩阵A、资源向量b、价格系数向量C、决策变量

4、X、剩余变量和松弛变量 。 minZ=-x1-2x2+x3-x4-4x5+2x6x1+x2+x3+x4+x5+x662x1-x2-2x3+x44x3+x4+2x5+x6 4X1,x2,x3,x4,x5,x60S.t. minZ=-x1-2x2+x3-x4-4x5+2x6x1+x2+x3+x4+x5+x662x1-x2-2x3+x44x3+x4+2x5+x64x1,x2,x3,x4,x5,x60S.t. 解： 令z=-z，则标准型为： maxZ=x1+2x2-x3+x4+4x5-2x6+0 x7+0 x8+0 x9x1+x2+x3+x4+x5+x6+x7=62x1-x2-2x3+x8=4x3+x

5、4+2x5+x6+x9=4x1,x2,x3,x4,x5,x6,x7,x8,x90S.t. maxZ=CXS.t.AX=bX0X=x1,x2,x3,x4,x5,x6,x7,x8,x9TC=-1,-2,1,-1,-4,2,0,0,0b=6,4,4T A=1 1 1 1 1 1 1 0 02 -1 -2 1 0 0 0 1 00 0 1 1 2 1 0 0 1矩阵形式表示为： 其中： maxZ=x1+2x2-x3+x4+4x5-2x6+0 x7+0 x8+0 x9x1+x2+x3+x4+x5+x6+x7=62x1-x2-2x3+x8=4x3+x4+2x5+x6+x9=4x1,x2,x3,x4,x5,

6、x6,x7,x8,x90S.t.剩余变量是：剩余变量是：松弛变量是：松弛变量是：x7,x8,x9302010线性规划的图解法和单纯形法线性规划的图解法和单纯形法3x2 75504030201010203040 x150等值线等值线B课后作业用图解法求解下列各线性规划模型并指出解的类型（1）min Z = 6x1 + 4x2 2x1 + x2 1 s.t. 3x1 + 4x2 3 x1, x2 0（2）max Z= 4x1+8x2 2 x1 +2x2 10 s.t. -x1 +x2 8 x1, x2 0（3）max Z = x1 + x2 8x1 + 6x2 24 s.t. 4x1 + 6x2

7、-12 2x2 4 x1, x2 0（4）max Z= 3x1+9x2 x1 + 3x2 22 s.t. -x1 + x2 4 x2 6 2 x1 -5x2 0 x1, x2 021510maxxxz94321 xx82521 xx0,21xx课堂举例课堂举例 用图解法图解法和单纯形法单纯形法分别求解下述线性规划问题由图知： *(1,3/2)35/2;TxZ； 首先化为标准形如下：12123124max105.349528(1,2,3,4)0izxxstxxxxxxx i+0 x3 +0 x4CjiCBXBb检验数检验数 jx1x2x3x4x3x498001050034105201105009

8、/38/5CjiCBXBb检验数检验数 jx1x2x3x4x3x121/501010500014/51-3/512/501/5010-28/5CjiCBXBb检验数检验数 jx1x2x3x4x2x13/251010500015/14-3/1410-1/72/700-5/14-25/1413/28/2*(1,3/2)35/2;TxZ； 原问题具有唯一最优解原问题具有唯一最优解 : 课堂例题课堂例题1用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题 3212maxxxxz603321xxx102321xxx20321xxx)3 , 2 , 1(0jxj1231234123123m ax

9、2.36 021 02 0(1, 2, 3, 4, 5, 6 )0jzxxxstxxxxxxxxxxxxxi56 CjiCBXBb检验数jx1x2x3x4x5x62-11000 x4x5x600060311100101-1201060/310/120/12011-1001 2-11000+0 x4 +0 x5 + 0 x6CjiCBXBb检验数jx1x2x3x4x5x62-11000 x4x1x60203004-51-30101-1201030/4-10/21002-30-11 01-30-20CjiCBXBb检验数jx1x2x3x4x5x62-11000 x4x1x202-1100011-1

10、-215101/201/21/2501-3/20-1/21/2 00-3/20-3/2-1/2*(,);TxZ15 5，0 ；25原问题具有唯一最优解原问题具有唯一最优解 :运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外非线性规划模型非线性规划模型Non-linear ProgrammingNon-linear Programming第第 4 4 章章基本题型基本题型写出一个函数的海赛写出一个函数的海赛Hesse矩阵矩阵判断矩阵是正定、半正定、负定、半负、不定判断矩阵是正定、半正定、负定、半负、不定判断一个函数是（严格）凹函数还是（严格）凸函判断一个函数是（严格）凹函数还

11、是（严格）凸函数数判定一个非线形规划是否是凸规划判定一个非线形规划是否是凸规划判断一个函数是否有极值点判断一个函数是否有极值点求解极值点求解极值点(无约束极值问题和有约束极值问题无约束极值问题和有约束极值问题)1、写出一个函数的海赛矩阵、写出一个函数的海赛矩阵 f(x)=x21+x22-4x1+4f(x)=（2x1-4，2x2）T-梯度2f (x)= -海赛矩阵2 00 2练习题：f(x)=2x21-4x2x1+4x22-6x1-3x2 f(x)=2x21+x22+x23-x1x22、判断矩阵是正定、半正定、负定、判断矩阵是正定、半正定、负定、半负定、不定半负定、不定h11 h12 h13 h

12、1nh21 h22 h23 h2n h31 h32 h33 h3nhn1 hn2 hn3 hnnh110h11 h12 h21 h22 0h11 h12 h13h21 h22 h23 h31 h32 h330h11 h12 h13 h1nh21 h22 h23 h2n h31 h32 h33 h3nhn1 hn2 hn3 hnn0顺序主子式全部大于顺序主子式全部大于0，矩阵是正定，矩阵是正定D1 =D2 =D3 =Dn =h110h11 h12 h21 h22 0h11 h12 h13h21 h22 h23 h31 h32 h33 0h11 h12 h13 h1nh21 h22 h23 h2n

13、 h31 h32 h33 h3nhn1 hn2 hn3 hnn 0顺序主子式全部大于等于顺序主子式全部大于等于0，矩，矩阵是半正定阵是半正定D1 =D2 =D3 =D4 =h11 0h11 h12 h13h21 h22 h23 h31 h32 h330时，时， f(x)存在极小点存在极小点 当当f(x)=0且且f (x)0，所以，所以f(x)具有极小值具有极小值f(x)极小点为极小点为x*=2，极小值为，极小值为f*(x)=48求多维函数求多维函数f(x)存在极小点的条件是：存在极小点的条件是： 必要条件是：必要条件是： f(x)在极值点的梯度在极值点的梯度=0（驻点）（驻点） 充分条件是充分

14、条件是Hesse矩阵正定矩阵正定Tnxxfxxfxxfxf)(,.)(,)()(*2*1*nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf2*22*21*22*222*212*21*221*212*2*2)(,.)(,)(.)(,.)(,)()(,.)(,)()(（2）求多维函数）求多维函数f(x)的极小点和极小值的极小点和极小值3322112822xxfxxfxxf123222132124),(minxxxxxxxf非线性规划问题例如：求解下列无约束2、令以上一阶偏导数、令以上一阶偏导数=0，得：，得：1、求一阶偏导数：、求一阶偏导数：020802233221

15、1xxfxxfxxf0;0;1321xxx求得：求得：3322112822xxfxxfxxf3、求海赛矩阵：、求海赛矩阵：002)(2Xf0802004、判断海赛矩阵的正定性：、判断海赛矩阵的正定性：D1=20D2=160D3=320所以所以Hesse矩阵为正定矩阵矩阵为正定矩阵5、求解、求解f(x)的极小点和极小值：的极小点和极小值：因为因为f(x)存在一阶导数为存在一阶导数为0的点，并且的点，并且Hesse矩阵矩阵为正定矩阵，为正定矩阵，f所以所以(x)存在极小值点存在极小值点0;0;13*2*1*xxx极小值为：极小值为：f*=-1极小点为：极小点为：设有如下非线性函数设有如下非线性函数

16、f(x)=2x21-4x2x1+4x22-6x1-3x2 +900求求f(x)的的Hesse矩阵，并判别是否为矩阵，并判别是否为正定，判别正定，判别 f(x) 是否有极值，若判定是否有极值，若判定 有极值，请求出极值点；若判定有极值，请求出极值点；若判定 f(x)没有极值，请进行说明为什么没有极没有极值，请进行说明为什么没有极值值?退 出前一页后一页求解有不等式和等式约束的非线性规划求解有不等式和等式约束的非线性规划问题的基本步骤如下：问题的基本步骤如下：分别对分别对f(X)、gi(X)和和hj(X)求一阶导数；求一阶导数；对对gi(X)和和hj(X)分别引入拉格朗日乘子分别引入拉格朗日乘子列

17、出列出K-T条件：条件：求解求解如果原规划是凸规划，则利用如果原规划是凸规划，则利用K-T条件计算出的条件计算出的解为原问题的极小点解为原问题的极小点代入目标函数得到最优值代入目标函数得到最优值运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运输问题运输问题找一个初始基可行解找一个初始基可行解;方法方法: 西北角法西北角法/最小元素法最小元素法最优解的判别（求非基变量的检验数）最优解的判别（求非基变量的检验数）;方法方法:闭回路法闭回路法/位势法位势法确定入基变量与出基变量，找出确定入基变量与出基变量，找出新新的基可的基可行解；行解；方法方法:闭回路调整法闭回路调整法1.

18、重复重复2、3直到得到最优解直到得到最优解平衡运输问题的表上作业法基本步骤平衡运输问题的表上作业法基本步骤 已知下列运输问题产销平衡表，应如何调运，已知下列运输问题产销平衡表，应如何调运，使得总运输费用最小？使得总运输费用最小？ 销地销地产地产地B1B1B2B2B3B3B4B4产量产量A1A111115 5222214141616A2A213137 7101022222020A3A35 51616171720204 4销量销量4 4161615155 5 运输问题（1）用最小元素法确定初始基可行解）用最小元素法确定初始基可行解（2）用位势法判断已得的方案是否是最优解，若是，为什么？）用位势法判

19、断已得的方案是否是最优解，若是，为什么？ 若不是，请求出最优运输方案若不是，请求出最优运输方案解：设解：设xij表示表示Ai产地到产地到Bj销售地的运输量，则销售地的运输量，则 产地销地B1B2B3B4产量A1x11x12x13x1416A2x21x22x23x2420A3x31x32x33x344销量416155（1 1）用最小元素法确定初始基可行解）用最小元素法确定初始基可行解产地销地B1B2B3B4产量A1 16 016A2 15520A3 4 04销量416155（2 2）用位势法判断已得的方案是否是最优解）用位势法判断已得的方案是否是最优解产地销地B1B2B3B4Ui A1 （12）

20、 16（20） 00A2 （6） （-6） 1558A34 （5） （9）06Vj-15214因为存在非基变量的检验数小于因为存在非基变量的检验数小于0 0，所以不是原问题的最优方，所以不是原问题的最优方案，采用回路法调整：案，采用回路法调整：产地销地B1B2B3B4Ui A1 （12） 11（16） 50A2 （12） 5 15（6）2A3 4 （5） （3）06Vj-15814因为所有非基变量的检验数都大于因为所有非基变量的检验数都大于0 0，所以是原问题的最优方案，所以是原问题的最优方案最小费用为：最小费用为：4 4* *5+115+11* *5+55+5* *7+157+15* *10

21、+510+5* *14=33014=330课下作业 已知运输问题的供需关系与单位运价如下表，试用表上作业法求最优解。甲乙丙丁产量132765027523603254525销量60402015Linear Integer ProgrammingLinear Integer Programming例、例、 有四个熟练工人，他们都是多面手，有四项任有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下所项任务，而每人完成每项任务的工时耗费如下所示，问如何分配任务使完成四项任务的总工时耗示，问

22、如何分配任务使完成四项任务的总工时耗费最少？费最少？指派问题及匈牙利法指派问题及匈牙利法 2 10 5 05 0 3 90 9 2 90 2 0 2匈牙利法的步骤：匈牙利法的步骤： 第一步第一步：变换效率矩阵变换效率矩阵使每行每列至少有一个零，同时不出现负元素使每行每列至少有一个零，同时不出现负元素 行变换行变换：找出每行最小元素，从该行各元素中减去：找出每行最小元素，从该行各元素中减去之之 列变换列变换：找出每列最小元素，从该列各元素中减去：找出每列最小元素，从该列各元素中减去之之 9 17 16 712 7 14 168 17 14 177 9 11 9-7-7-8-72 10 9 05

23、0 7 90 9 6 90 2 4 2行行变变换换列列变变换换-42 10 5 05 0 3 90 9 2 90 2 0 2第二步：在变换后的系数矩阵中确定第二步：在变换后的系数矩阵中确定独立零元素独立零元素 独立零元素独立零元素-指位于不同行不同列的零元素。指位于不同行不同列的零元素。 确定独立零元素的方法：首先在只有一个零元素的确定独立零元素的方法：首先在只有一个零元素的行（或列）中对零元素加圈，因为这表示此人只能做行（或列）中对零元素加圈，因为这表示此人只能做该事（或此事只能由该人来做）。每圈一个该事（或此事只能由该人来做）。每圈一个0，同时把，同时把位于同行和同列的其他零元素划去，这表

24、示此事已不位于同行和同列的其他零元素划去，这表示此事已不能再由其他人来做（或此人已不能做其他事），如此能再由其他人来做（或此人已不能做其他事），如此反复进行，直到系数矩阵中所有零元素都被圈去或划反复进行，直到系数矩阵中所有零元素都被圈去或划去为止。在此过程中，如遇到在所有的行和列中，零去为止。在此过程中，如遇到在所有的行和列中，零元素都不止一个时，可任选其中一个零元素加圈，同元素都不止一个时，可任选其中一个零元素加圈，同时划去同行和同列中其他零元素。当过程结束时，被时划去同行和同列中其他零元素。当过程结束时，被划圈的零元素即为独立零元素。划圈的零元素即为独立零元素。独立零元素个数为独立零元素个

25、数为4个，而个，而m=42 10 5 05 0 3 90 9 2 90 2 0 22 10 5 05 0 3 90 9 2 90 2 0 20 0 0 10 1 0 01 0 0 00 0 1 0答：最优分配方案为答：最优分配方案为 x14= x22= x31 = x43 =1，其余为，其余为0， 即甲即甲 D ，乙，乙 B ，丙，丙 A ，丁，丁 C ，Z=33最优解为：最优解为： 9 17 16 712 7 14 168 17 14 177 9 11 9 若独立零元素有若独立零元素有m个，则表示已可确定最个，则表示已可确定最优指派方案，此时，令解矩阵中和独立零优指派方案，此时，令解矩阵中和

26、独立零元素对应位置上的元素为元素对应位置上的元素为1，其他元素为，其他元素为0，即得出最优解矩阵；若独立零元素少于即得出最优解矩阵；若独立零元素少于m个，则表示还不能确定最优指派方案。此个，则表示还不能确定最优指派方案。此时需要确定能覆盖所有零元素的最少直线时需要确定能覆盖所有零元素的最少直线数目的直线集合；数目的直线集合；4 10 7 52 7 6 33 3 4 44 6 6 3-4-2-3-30 6 3 10 5 4 10 0 1 11 3 3 0行行变变换换列列变变换换-10 6 2 10 5 3 10 0 0 11 3 2 0独立零元素个数为独立零元素个数为3个，而个，而m=4，继续，

27、继续例题例题确定最少覆盖直线数目的方法：确定最少覆盖直线数目的方法：对没有划圈的行打对没有划圈的行打；（没事情干的人）（没事情干的人）在已打在已打的行中，对的行中，对 所在列打所在列打 ；（该人可干的事）（该人可干的事）在已打在已打的列中，对所在行打的列中，对所在行打 （该事被干的人）该事被干的人）重复重复2 （该人还可干的事）（该人还可干的事）和和3 （该事还被干的人）该事还被干的人） ，直到再也不能找到可以打直到再也不能找到可以打 的行或列为止；的行或列为止；对没有打对没有打的行画一横线，对打的行画一横线，对打的列画一垂线，这样就的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线

28、集合。得到了覆盖所有零元素的最少直线数目的直线集合。 0 6 2 10 5 3 10 0 0 11 3 2 0 提示：最少直线的个数正好等于独立提示：最少直线的个数正好等于独立零元素的个数零元素的个数第三步：继续变换系数矩阵第三步：继续变换系数矩阵 方法是：在未被直线覆盖的元素中找出一个最小元素。对未被直线覆盖的元素所在的行中各元素都减去这一最小元素。对被直线覆盖的元素所在的列中各元素都加上这一最小元素（或列），返回第二步。未被直线覆盖的元素中最小值为未被直线覆盖的元素中最小值为1 0 6 2 10 5 3 10 0 0 11 3 2 0 -1-1+10 5 1 00 4 2 01 0 0 1

29、2 3 2 0 -1-10 4 0 00 3 1 02 0 0 22 2 1 0+1+1-10 5 1 00 4 2 01 0 0 12 3 2 0 0 0 1 01 0 0 00 1 0 00 0 0 1答：最优分配方案为答：最优分配方案为 x13= x21= x32 = x44 =1，其余为，其余为0， 即甲即甲C，乙，乙A，丙，丙B，丁，丁D，Z=15最优解为：最优解为：未被直线覆盖的元素中最小值为未被直线覆盖的元素中最小值为14 10 7 52 7 6 33 3 4 44 6 6 3指派问题举例指派问题举例 某商业公司计划开办五家新商店。为了尽早建某商业公司计划开办五家新商店。为了尽早

30、建成营业，商业公司决定由成营业，商业公司决定由5家建筑公司分别承建。家建筑公司分别承建。已知建筑公司对新商店的建造费用的报价如表，已知建筑公司对新商店的建造费用的报价如表，商业公司应当对商业公司应当对5家建筑公司怎样分配建造任务，家建筑公司怎样分配建造任务，才能使总的建造费用最少？才能使总的建造费用最少？B1B2B3B4A1 48715A2 A3A4A57666997917121412148610B512107106有一份中文说明书有一份中文说明书,需译成英、日、德、俄四种需译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人。他们将中文文字，现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语

31、种的说明书所需时间如表，说明书翻译成不同语种的说明书所需时间如表，问应指派何人去完成何工作，使所需总时间最问应指派何人去完成何工作，使所需总时间最少？少？ 英英 日日 德德 俄俄 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9课堂练习题一课堂练习题一 2 15 13 410 4 14 15 9 14 16 13 7 8 11 90 0 0 10 1 0 01 0 0 00 0 1 0 A B C D E 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 14 6 6 10 戊 4 10 7 10 9课堂练

32、习题二课堂练习题二rxdtdx(Graph and Network Analysis)(Graph and Network Analysis)举例举例v1v2v35322153517v6v5v4求求v1到到v6的最短路的最短路解解: : (1)(1)给起始点给起始点v v1标以标以(0,s)，表示从，表示从v v1到到v v1的距离为的距离为0 0， v v1为为起始点起始点(0,s) (2)(2)这时已标定点集合这时已标定点集合 I =v1 ， 未标定点集合未标定点集合 J=v2，v3，v4 ，v5，v6 弧集合弧集合： A=(vi，vj)|viI, vj J= (v1，v2)，(v1，v3

33、)，(v1，v4) 计算：计算： s12 =l1 +c12=0+3=3 s13 =l1 +c13=0+2=2 s14 =l1 +c14=0+5=5因为因为min(s12, s13, s14) = s13=2所以给弧所以给弧(v1，v3)的终点的终点v3标号标号(2,1)，表示从表示从v v1到到v v3的距离为的距离为2 2， 并且在并且在v v1到到v v3的最的最短路径中短路径中v v3的前面一个点是的前面一个点是v v1(2,1) v1v2v35322153517v6v5v4(0,s) (3)(3)这时已标定点集合这时已标定点集合I =v1 ， v3， 未标定点集合未标定点集合J=v2，

34、v4 ，v5，v6 弧集合弧集合：A= (vi，vj)|viI, vj J= (v1，v2)，(v1，v4)，(v3，v4) 计算：计算： s12 =l1 +c12=0+3=3 s14 =l1 +c14=0+5=5 s34 =l3 +c34=2+1=3 因为因为min(s12, s14, s34) = s12=s34=3所以给弧所以给弧(v1，v2)的终点的终点v2标号标号(3,1)，表示从表示从v v1到到v v2的距离为的距离为3 3， 并且在并且在v v1到到v v2的最短路径中的最短路径中v v2的前面一个点是的前面一个点是v v1 给弧给弧(v3，v4)的终点的终点v4标号标号(3,

35、3)，表示从表示从v v1到到v v4的距离为的距离为3 3， 并且在并且在v v1到到v v4的最短路径中的最短路径中v v4的前面一个点是的前面一个点是v v3(2,1) 前面已经算出(3,1) (3,3) v1v2v35322153517v6v5v4(0,s) (4)(4)这时已标定点集合这时已标定点集合I =v1， v2 ， v3 ，v4 ， 未标定点集合未标定点集合J=v5，v6 弧集合弧集合：A=(vi，vj)|viI, vj J= (v2，v6)， (v4，v6 计算：计算： s26 =l2 +c26=3+7=10 s46 =l4 +c46=3+5=8 因为因为min(s26,

36、s46) = s46=8所以给弧所以给弧(v4，v6)的终点的终点v6标号标号(8,4)，表示从表示从v v1到到v v6的距离为的距离为8 8， 并且在并且在v v1到到v v6的最短路径中的最短路径中v v6的前面一个点是的前面一个点是v v4(2,1) (3,1) (3,3) (8,4) v1v2v35322153517v6v5v4(0,s) (5)(5)这时已标定点集合这时已标定点集合I =v1， v2 ， v3 ，v4 ，v6， 未标定点集合未标定点集合J=v5 弧集合弧集合：A= (vi，vj)|viI, vj J= 计算结束计算结束这时这时J=v5，也即，也即v5还未标号还未标号

37、 ，说明，说明从从v v1到到v v5没有有向路没有有向路(2,1) (3,1) (3,3) (8,4) (6)(6)通过反向追踪得到最优路径通过反向追踪得到最优路径 根据终点根据终点v6的标号（的标号（8 8，4 4）可知道）可知道从从v v1到到v v6的距离是的距离是8 8，其，其最短路径中最短路径中v v6的前面一点是的前面一点是v v4 ， 从从v4的标号（的标号（3 3，3 3）可知）可知v v4的的前面一点是前面一点是v v3 ，从，从v3的标号（的标号（2 2，1 1）可知）可知v v3的前面一点是的前面一点是v v1 ，即此最短路径为即此最短路径为v1 v3 v4 v6 课堂

38、练习课堂练习1 利用利用Dijkstra算法，求出图中，算法，求出图中，v1到到v5的最短路的长度？的最短路的长度？v1V2V3V4V54310 27815 网络计划技术 有向图：弧、节点、权、路有向图：弧、节点、权、路 路表示一种逻辑上或时序上的先后顺序关系（可以表达工程管理问题各个环节之间的关系） 工程：工序、事件、时间工程：工序、事件、时间第五节 关键线路模型12435678工序开始事件工序结束事件A(10)B(12)C(16)D(2)E(3)F(7)H(13)K(18)J(4)工序时间工序代号总开总开工事工事件件总完总完工事工事件件一个工程事事件件工工序序线线路路关键线路（时间和最大的

39、线路），之上的工序叫关键工序关键线路（时间和最大的线路），之上的工序叫关键工序1A(10)紧前工序紧后事件建立关键线路模型：建立关键线路模型：1、将整个工程分解成若干个工序，对每一个工序给予名称、将整个工程分解成若干个工序，对每一个工序给予名称和代号，确定每一个工序的紧前工序和代号，确定每一个工序的紧前工序2、确定每一工序所需的时间，填写、确定每一工序所需的时间，填写“紧前事件表紧前事件表”3、绘制网络图绘制网络图4、计算网络图中的时间参数计算网络图中的时间参数5、确定关键路线确定关键路线6、网路图的调整和优化，从而获得最佳的计划安排方案、网路图的调整和优化，从而获得最佳的计划安排方案序号序号

40、工序名称工序名称工序代号工序代号工序时间工序时间紧前工序紧前工序123绘制网络图的规则绘制网络图的规则有向图有向图，绘制时从左向右延伸，绘制时从左向右延伸不能出现不能出现回路回路两个事件之间只能有一个工序两个事件之间只能有一个工序，若有平行工序，若有平行工序，须引入须引入“虚工序虚工序”虚工序用虚工序用虚线虚线表示，工序表示，工序时间为时间为0图中一般只有图中一般只有一个总开工事件和一个完工事件一个总开工事件和一个完工事件图中事件图中事件统一编号统一编号，编号从左向右进行，每个，编号从左向右进行，每个工序的开始节点编号应小于结束节点的编号。工序的开始节点编号应小于结束节点的编号。AB123AB

41、AB123ABC4C局部工序图和网络图的画法局部工序图和网络图的画法AB123ABC4CD5D123AB4C5D或者或者可以拆分任意一个工序，即共有如上两种形式可以拆分任意一个工序，即共有如上两种形式AB123ABC4CD5D123AB4C5D或者或者AB124ABC5CE6E可以拆分任意两个工序，即还有另外两种形式可以拆分任意两个工序，即还有另外两种形式DD3可以拆分任意一个工序，即共有如上两种形式可以拆分任意一个工序，即共有如上两种形式AB123ABC4CD5D123AB4C5DAB123ABC4CD5DE6EAB123ABC4CD5EE6D或者或者只能拆分只能拆分B工序，因为工序，因为B

42、还有一个紧后工序还有一个紧后工序只能拆分只能拆分C工序，因为工序，因为C还有一个紧后工序还有一个紧后工序可以拆分任意一个工序，即共有如上两种形式可以拆分任意一个工序，即共有如上两种形式ABABC4CDDEEE局部工序图和网络图的画法局部工序图和网络图的画法12356ABABC5CDDEE123684E7F局部工序图和网络图的画法局部工序图和网络图的画法ABABC5CDDE12364F7GE98G10EABABC5CDDEE123684E7作业1、已知下列资料：要求： （1）绘制网络图 （2）计算各项时间参数 （3）确定关键路线工序紧前工序工序时间工序紧前工序工序时间工序紧前工序工序时间AGM3

43、EC5IAL2BH4FAE5KFI1C7GBC2LBC7DL3H5MC3CMGAEHBLDFIK工序紧前工序工序时间工序紧前工序工序时间工序紧前工序工序时间AGM3EC5IAL2BH4FAE5KFI1C7GBC2LBC7DL3H5MC3CMGAEHBLDFIK24135D6710C(7)H(5)B(4)G(2)M(3)E(5)L(7)A(3)D(3)911F(5)I(2)K(1)从左向右逐步计算事件最早时间，如下从左向右逐步计算事件最早时间，如下 :(1)0Et从左向右计算从左向右计算24135D6710C(7)H(5)B(4)G(2)M(3)E(5)L(7)A(3)D(3)911F(5)I(

44、2)K(1)计算网络图中的时间参数计算网络图中的时间参数工序时间工序时间t(i，j)事件最早时间事件最早时间 tE(j)事件最迟时间事件最迟时间 tL(j)工序最早可能开工时间工序最早可能开工时间tES(i，j)工序最迟必须开工时间工序最迟必须开工时间tLS(i，j)工序的总时差工序的总时差R(i，j)工序最早可能完工时间tEF(i，j)工序最迟必须完工时间tLF(i，j)工序的单时差r(i，j)事件最早时间事件最早时间 tE(j)tE(1)=0tE(j)=maxtE(i)+t(i,j)tE(j)是事件最早可能开始的时间，其中总开工事件的tE(1)=0 ，表示工程从0时刻开始 。即一个结束事件

45、结束事件的最早时间等于它所对应的工序的开始事开始事件件的最早时间+该工序时间，若一个事件节点同时是几个工序的结束事件节点，则选择开始事件节点时间+工序时间之和的最大值最大值作为该事件节点的最早时间。 完工事件完工事件节点的最早时间记为tE= tE(n) ，是工程的最早完工时间，称为工程最早完工工期，最早完工工期，也是从总开工事件总开工事件到完完工事件工事件的最长的线路最长的线路 2341A(4)B(7)C(10)F(7)5D(8)678E(12)G(5)H(4)从左向右逐步计算事件最早时间，如下 :(1)0Et(2)(1)(1,2)044EEttt(3)(2)(2,3)4711EEttt(4)(2)(2,4)41014EEttt(3)(3,5)11 0(5)max14(4)(4,5)140EEEttttt(3)(3,6)11 8(6)max(5)(5,6)14 1226(4)(4,6)147EEEEttttttt(7)(6)(6,7)26 531EEttt (8)(7)(7,8)31435EEttt整个工程的最早完工期(8)35EETt从左向右计算从左向右计算事件最迟时间事件最迟时间 tL(j)tL(n)=tE(n)tL(i)=mintL(j)-t(i,j)