管理运筹学第六—第八章

1、第六章矩阵对策,6.1 对策问题 6.2 对策论的基本概念 6.3 矩阵对策的概念及模型 6.4 矩阵对策的纯策略解(鞍点解) 6.5 矩阵对策的混合策略解 6.6 矩阵对策的解,第六章矩阵对策 61对策问题 62对策论的基本概念 621局中人 一场竞争或斗争称为一局对策，一局对策中的决策者 称为该局对策的局中人（只有两个局中人，称为两人 对策；两人以上称为多人对策）。 622策略与策略集合 指导局中人自始至终如何行动的一个实际可行的完 整的行动方案称为策略。 局中人所有策略构成的集合称为策略集合。 有限策略 有限对策 无限策略 无限对策,局中人策略集合: S1=1，2，m 局中人策略集合:

2、S2=1，2，n i，j称为局势 6.2.3支付与支付函数 当局中人选定某一策略后,得到的收益或损失称为 局中人的支付;不同的策略导致不同的支付,因此支付 是策略的函数. 6.2.4零和对策 若在一局对策中,全体局中人的支付总和为0,则将 该对策称为零和对策,否则称为非零和对策. 6.2.5对策分类,零和对策 二人对策 非零和对策 有限对策 零和对策 n人对策 非零和对策 对策 零和对策 二人对策 非零和对策 无限对策 零和对策 n人对策 非零和对策,有限二人零和对策也称为矩阵对策.,63矩阵对策的概念及模型 一般形式： 局中人策略集合: S1=1，2，m 局中人策略集合: S2=1，2，n

3、其中i，j 分别为局中人、的纯策略，策略偶i，j称为纯局势； 若局中人在i，j下的支付为aij则,a11 a12 a1n A = a21 a22 a2n . am1 am2 amn,称为局中人的支付矩阵，矩阵对策模型可记为： G= S1，S2，A 局中人的支付矩阵为：-A,例1：包、剪、锤游戏中 矩阵对策模型：G= S1，S2，A 其中 甲：S1=1（包），2（剪），3（锤） 乙：S2=1（包），2（剪），3（锤）,乙的支付矩阵： -A 6.4 矩阵对策的纯策略解(鞍点解) 模型确定以后,各局中人面临的问题就是如何选取对自 己最为有利的纯策略,以谋求最大的赢得(或最少的损失). 例2:设矩阵对

4、策G= S1，S2，A， 其中: S1=1，2，3，4 ;S2=1，2，3,1 2 3,1 2 3,A =,甲的支付矩阵：,0,-1,1,1,0,-1,-1,1,0,1 2 3 1 -6 2 -7 A = 2 5 3 6 3 18 0 -8 4 -2 -12 7,局中人 1 min-6，2，-7 = -7 2 min 5，3，6 = 3 3 min18，0，-8 = -8 4 min-2，-12，7=-12 最好结果： max min -7，3，-8，-12=3,局中人： 1 max-6，5，18，-2=18 2 max2，3，0，-12 = 3 3 max-7，6，-8，7 = 7 最好结果

5、： min max 18，3，7=3,2，2分别为局中人、的最优策略； 2，2为对策解 （鞍点）,而 a22=3称为对策值。,定义1 矩阵对策 G= S1，S2，A，如果存在纯局势 i*，j*使得对于任意j=1,2,n;i=1,2,m有： aij*ai*j*ai*j 列 行,j* a11 a1j* a1n . A= i*， ai*1 ai*j* ai*n . am1 amj* amn,则称纯局势i*，j*为G在纯策略中的解(鞍点解)； 而i*，j*分别为局中人、的最优纯策略；ai*j*称 为矩阵对策G的值（对策值）。,定理1:矩阵对策G= S1，S2，A存在最优纯策略的充分必要条件为： max

6、 min aij = min max aij 例3：已知矩阵对策G= S1，S2，A,1 2 3 4 1 8 6 8 6 A = 2 1 3 4 -3 3 9 6 7 6 4 -3 1 10 3,局中人最好结果： max min aij =max 6，-3，6，-3=6 局中人最好结果： min max aij = min 9，6，10，6=6,min 6 -3 6 -3,max,9,6,10,6,max min aij = min max aij=6 对策值： ai*j*=a12= a14= a32= a34= 6 对策解（鞍点）： （i*，j*）=（1，2）=（1，4） =（3，2）=（3

7、，4） 1，3为局中人的最优纯策略 2，4为局中人的最优纯策略 由此可见对策解不是唯一的，但对策值是唯一的。 两条重要性质： （1）无差别性：若（i1 ，j1 ）与（i2 ，j2 ） 是G的两个解，则ai1 j1 = ai2 j2 （2）可交换性：若（i1 ，j1 ）与（i2 ，j2 ） 是G的两个解，则（i1 ，j2 ）与（i2 ，j1 ） 也是G的两个解。,65矩阵对策的混合策略解 651混合策略与混合扩充 6511混合策略 局中人以概率xi(i=1,2,m)选取纯策略i 局中人以概率yj(j=1,2,n)选取纯策略j 其中：,m xi =1 (0 xi1) i=1 n yj =1 (0y

8、j1) j=1,则向量X=(x1,x2,xm),Y=（y1,y2,yn)分别称为局中人、混合策略；（X，Y）称为一个混合局势 显然：纯策略是混合策略的特例。,6512 混合扩充 在混合策略中,局势（i ，j ）出现的概率为xiyj ，因此局中人的支付期望为： n m E（X，Y）= aijxiyj j=1 i=1 令： 局中人的混合策略集合为 S*1=X=(x1,x2,xm)| 0 xi1，xi=1 局中人的混合策略集合为 S*2=Y=(y1,y2,yn)| 0yj1，yj=1 则称：G*= S*1，S*2，E（X，Y）为对策G的混合扩充。 以下定义一套与纯策略解完全平行的混合策略的解。,定义

9、2：如果存在X*S*1，Y*S*2；对任意的XS*1， 及YS*2均满足： E（X，Y*）E（X*，Y*）E（X*，Y） 则称混合局势（X*，Y*）为G在混合策略中的解(混合 解)；而X*，Y*分别为局中人、的最优混合策略 ；E（X*，Y*）称为矩阵对策G的对策值，通常记为: VG*= E（X*，Y*） 652 解基本定理 定理2：任意一个矩阵对策G= S1，S2，A， 其中：S1=12，m S2=12，n A = （aij）mn 一定有解（混合策略解），且如果G的对策值是V，则 以下两组不等式的解就是局中人、的最优混合策 略：,m m aijxiV (j=1,2,n) xi=1 i=1 i=

10、1 xi0 (i=1,2,m),定理3：若（X*，Y*）是对策G的最优混合策略，则对某一个i或j来说： (1)若yj*0 则 aijxi*=V (2)若xi*0 则 aijyj*=V (3)若aijxi* V 则yj*=0 (4)若aijyj* V 则xi*=0 这两个基本定理为求解矩阵对策奠定了理论基础。,y1 yj yn x1 a11 a1j a1n . A= xi ai1 aij ain . xm am1 amj amn,n n aijyjV (i=1,2,m) yj=1 j=1 j=1 yj0 (j=1,2,n),yj,xi,66 矩阵对策的解 661图解法 适用于：至少有一个局中人，

11、只有两种可供选择的策略的矩阵对策。即： A2n、Am2、A22 例4：矩阵对策G= S1，S2，A 其中:,S1=1，2，S2=1，2,5 35 A = 20 10,解：作混合扩充： S*1=x1 ，1-x1，S*2=y1 ，1-y1,对于局中人而言，若局中人选取1，2，则局中人的支付期望值分别为 1 5x1+20（1-x1）=20-15x1V 2 35x1+10（1-x1）=25x1+10V,局中人用“最大最小”原则选取自己的策略，即 max min (20-15x1 ,25x1+10) 0 x11 从图中可知： min (20-15x1 ,25x1+10) 0 x11 为折线EDF，D为所

12、求的极值点， 其坐标:（1/4,161/4） 所以 X*=(x1* ,1-x1*)=(1/4,3/4) VG*=161/4,35,10,20,5,X1,V,1,0,F,D,E,1/4,对于局中人而言，若局中人选取1，2，则局中 人的支付期望值分别为 1 5y1+35（1-y1）=35-30y1 V 2 20y1+10（1-y1）=10+10y1 V,局中人用“最小最大”原则选取自 己的策略，即 min max (35-30y1 , 10+10y1) 0y11 从图中可知 max (35-30y1 , 10+10y1) 0y11 为折线FGH，G为所求的极值点 其坐标:（5/8,161/4） 所

13、以 Y*=(y1* ,1-y1*)=(5/8,3/8) VG*=161/4,解：作混合扩充： S*1=x1 ，1-x1，S*2=y1 ，y2 ，y3，y4 对于局中人而言，若局中人选取1，2，3， 4则局中人的支付期望值分别为： 1 2x1+4（1-x1）=4-2x1 V （1） 2 3x1+（1-x1）=1+2x1 V （2） 3 x1+6（1-x1）=6-5x1 V （3） 4 5x1 =5x1 V （4） 局中人用“最大最小”原则选取自己的策略，即 max min (4-2x1，1+2x1，6-5x1，5x1) 0 x11,例5：矩阵对策G= S1，S2，A 其中: S1=1，2， S2

14、=1，2，3，4,2 3 1 5 A = 4 1 6 0,1 2x1+4（1-x1）=4-2x1 V （1） 2 3x1+（1-x1）=1+2x1 V （2） 3 x1+6（1-x1）=6-5x1 V （3） 4 5x1 =5x1 V （4）,为折线OABC，B为所求的极值点 其坐标: （5/7，17/7）, 所以 X*=(x1* ,1-x1*) =(5/7,2/7) VG*=17/7,从图中可知：min (4-2x1，1+2x1，6-5x1，5x1) 0 x11,A,C,B,5/7,对于局中人而言，若局中人选取1，2，则的支 付期望值分别为 1 2y1+3y2+y3+5y4 V 2 4y1+

15、y2+6y3 V 无法作图，应用定理3求出局中人的最优混合策略， x1* =5/7 2y1*+3y2*+y3*+5y4* =V x2* =2/7 4y1*+y2*+6y3* =V 将x1* =5/7，x2* =2/7 ，V=17/7 代入下列约束：,2x1+4（1-x1）=4-2x1 V 3x1+（1-x1） =1+2x1 V x1+6（1-x1）=6-5x1 V 5x1 =5x1 V,推出：,4-2x1* =18/7 V=17/7 y1*=0 1+2x1* =17/7 = V=17/7 y2*0 6-5x1* =17/7 = V=17/7 y3*0 5x1* =25/7 V=17/7 y4*

16、=0,代入下列方程组： 2y1*+3y2*+y3*+5y4* = V 4y1*+y2*+6y3* = V,662 优势法 矩阵对策G= S1，S2，A，其中: S1=1，2，m S2=1，2，3 A=（aij）mn,得方程组： 3y2*+y3*=17/7 y2*+6y3*=17/7,Y*=(y1*, y2*, y3*, y4*)=(0,5/7，2/7，0) VG*=17/7,定义3: 若对固定的i,k有aijakj i： ai1 aij ain k： akj akj akn （j=1,2,n） 则称i优超于k 记为i k,若对固定的j,L有 aijaiL j： a1j a2j amj L： a

17、1L a2L amL (i=1,2,m) 则称j优超于L 记为j L,例6：矩阵对策G= S1，S2，A，其中：,y1 y2 y3 y4 y5 l2345 x1 1 3 4 0 3 0 x2 2 5 0 2 5 9 A = x3 3 7 3 9 5 9 x4 4 4 6 8 7 6 x5 5 6 0 8 8 3,根据优超原理： 3 优超于2 x2*=0,4 优超于1 x1*=0 于是矩阵对策转化为,1 2 3 4 5 3 7 3 9 5 9 A1=4 3 6 8 7 6 5 6 0 8 8 3,2优超于3， 所以y3*=0，,1 2 3 7 3 A2=4 3 6 5 6 0,求解得： x3*

18、=1/3，x4*=2/3； y1*=1/2，y2*=1/2 X*=(0,0,1/3,2/3 0) Y*=(1/2,1/2,0,0,0) VG*=5,2优超于4， 所以y4*=0，,2优超于5， 所以y5*=0，,1 2 A3 = 3 7 3 4 3 6,3优超于5， 所以x5*=0，,663 简化计算法 定理4：矩阵对策G1=S1，S2，A1=（aij）mn ，G2=S1，S2，A2=（aij+d）mn，其中d为常数，则G1 ，G2具有相同的解，且对策值差一个常数d，即 VG2= VG1+ d 推论：矩阵对策G1=S1，S2，A1=（aij）mn ，G2=S1，S2，A2=（kaij）mn，其

19、中k0常数，则G1， G2具有相同的解，且对策值差一个常数d，即 VG2= kVG1 例7：矩阵对策G=S1，S2，A 3600 1200 A1= 1200 1800 解：用推论取k=1/600,再取d=2则可得同解矩阵,6 2 A2= 2 3,矩阵对策G3的解 X3*=（1/5，4/5） Y3*=（1/5，4/5）VG3=4/5 根据定理4与推论： X1*=X3*=（1/5，4/5） Y1*=Y3*=（1/5，4/5） VG1 =600VG2=600（2+VG3） =600（2+4/5）=1680,4 0 A3= 0 1,664特殊的矩阵（方阵）对策 (1)各行各列均为相同元素的不同排列。

20、例：包、剪、锤游戏中的矩阵,y1 y2 y3 1 2 3 x1 1 0 -1 1 A= x2 2 1 0 -1 x3 3 -1 1 0,各个策略被选取的机会是均等的，所以 X* =（x1*，x2*，x3*） =（1/3，1/3，1/3） Y* =（y1*，y2*，y3*） =（1/3，1/3，1/3） VG = 0,例8：齐王賽马i= i(i=1,2,3,4,5,6) 1 2 3 4 5 6 （上中下）1 3 1 1 1 -1 1 （上下中）2 1 3 1 1 1 -1 A= （中上下）3 1 -1 3 1 1 1 （中下上）4 -1 1 1 3 1 1 （下上中）5 1 1 1 -1 3 1

21、 （下中上）6 1 1 -1 1 1 3,X*=（x1*，x2*，x3*，x4*，x5*，x6*） =（1/6，1/6，1/6，1/6，1/6，1/6） Y*=（y1*，y2*，y3*，y4*，y5*，y6*） =（1/6，1/6，1/6，1/6，1/6，1/6） VG=1 (2)Amm中每行、每列仅有一个非零且非负的元素。,例 y1 y2 y3 1 2 3 x1 1 0 2 0 A= x2 2 1 0 0 x3 3 0 0 3,665线性规划的解法 线性规划的解法对于所有的矩阵对策问题都是有效的。 例：矩阵对策G= S1，S2，A， 其中：S1=12，m S2=12，n A = （aij）m

22、n,n aijyjV (i=1,2,m) j=1,y1 yj yn x1 a11 a1j a1n . A= xi ai1 aij ain . xm am1 amj amn,根据矩阵基本定理：,xi0 (i=1,2,m) (1),yj0 (j=1,2,n)(2),m xi=1 i=1,n yj=1 j=1,m aijxi V (j=1,2,n) i=1,m m aijxiV (j=1,2,n) xi=1 i=1 i=1,n n aijyjV (i=1,2,m) yj=1 j=1 j=1,xi0 (i=1,2,m) (1),yj0 (j=1,2,n) (2),设:V0,令xi/ =xi/V yj/

23、=yj/V 分别代入（1）、（2）,m m aijxi/ 1 (j=1,2,n) xi/ =1/V i=1 i=1 xi/ 0 (i=1,2,m) (3),n n aijyj/ 1 (i=1,2,m) yj/ =1/V j=1 j=1 yj/ 0 (j=1,2,n) (4),得,得,m m aijxi/ 1 (j=1,2,n) xi/ =1/V i=1 i=1 xi/ 0 (i=1,2,m) (3),又知： E（X，Y*）E（X*，Y*）=V E（X*，Y）,n n aijyj/ 1 (i=1,2,m) yj/ =1/V j=1 j=1 yj/ 0 (j=1,2,n) (4),Max E（X，

24、Y*）=E（X*，Y*）=V XS*1,Min1/ E（X，Y*）=1/ V,Min E（X*，Y）=E（X*，Y*）=V YS*2,m Min 1/V = xi/ i=1 m aijxi/ 1(j=1,2,n) i=1 xi/ 0 (i=1,2,m),n Max 1/V = yj / j=1 n aijyj/ 1(i=1,2,m) j=1 yj/ 0 (j=1,2,n),Max1/ E（X*，Y）=1/ V,E（X，Y*）E（X*，Y*）=V E（X*，Y）,结合（3）、（4）问题归结为,不难看出（）、（）是一对互为对偶的线性规 划问题，由对偶理论知，只须求解其中之一。,不难看出（）、（）是

25、一对互为对偶的线性规 划问题，由对偶理论知，只须求解其中之一。,3 2 3 A= 2 3 4 5 4 2,解：混合策略为 X=（x1，x2，x3）;Y=（y1，y2，y 3） 令：xi/ =xi/V； yj/ =yj/V 相应的线性规划问题为：,MinZ（X）=x1/ +x2/ +x3/ 3x1/ + 2x2/ + 5x3/ 1 2x1/ + 3x2/ + 4x3/ 1 3x1/ + 4x2/ + 2x3/ 1 x1/，x2/，x3/ 0,MaxZ（Y）=y1/ +y2/ +y3/ 3y1/ +2y2/ +3y3/1 2y1/ +3y2/ +4y3/1 5y1/ +4y2/ +2y3/ 1 y

26、1/，y2/，y3/ 0,例9：一矩阵对策的支付矩阵为,最终单纯形表：,Y/ =（1/8，0，3/16）；,1/V=5/16 V=16/5 Y*=（2/5，0，3/5）；,注意：矩阵对策化为线性规划求解时，对策值V0，如 果不满足这一点，将得到错误的结论。见P157例,X/ =（0，3/16，1/8）,X*=（0，3/5，2/5）；,定理5：若支付矩阵A中的所有元素aij0(j=1,2,n；i=1,2,m)，则对策值一定大于零。 根据此定理可将任意支付矩阵化为各元素均大于或等于零的同解支付矩阵。,y1 y2 y3 1 2 3 x1 1 0 -1 1 A= x2 2 1 0 -1 x3 3 -1

27、 1 0,y1 y2 y3 1 2 3 x1 1 1 0 2 A1= x2 2 2 1 0 x3 3 0 2 1,A1中的所有元素均0，其对策值一定大于零。,y1 y2 y3 1 2 3 x1 1 0 -6 1 A= x2 2 2 0 -6 x3 3 -6 3 0,y1 y2 y3 1 2 3 x1 1 6 0 7 A1= x2 2 8 6 0 x3 3 0 9 6,A1中的所有元素均0，其对策值一定大于零。,第七章 图与网络,7.1图的基本概念,第七章 图与网络 7.1图的基本概念 7.1 .1图与有向图 图是一个由表示具体事物的点（图论中称为顶点）的集合 和表示具体事物间的联系的边的集合组

28、成的集合。 若 V=v1 ,v2 ,vn 表示全体顶点的集合， E=e1 ,e2 ,em 表示全体边的集合 则图就可形式地写成G=V , E 注意；这里定义的图G有别与几何学中的图。在几何学中，图中点的位置、线的长短和斜率等都十分重要，而运筹学中的图，只关心图中有多少点以及那些点之间有线相连。如果给图中的点和边赋予具体的含义和权数，如距离、费用、容量等，则把这样的图称为网络图。,无向图：若E中任意一条边e= vi, vj= vj, vi则 称 e为无向边，图 G=V , E 称为无向图。 其中e的端点 vi, 及vj相关联， vi与vj相邻。 子图：由图G =V , E 的部分顶点和边构成的图

29、称为子图。 例：设有： G =V , E ，其中V=v1 ,v2 ,v5，E=e1 ,e2 ,e7 ，边与顶的关联情况由下表所示：,e,e1,e2,e3,e4,e5,e6,e7,e=u ,v,e1 ,e2,e1 ,e5,e2 ,e4,e1 ,e4,e4 ,e3,e5 ,e4,e1 ,e5,e7,e6,e5,e4,e3,e2,e1,v5,v4,v3,v2,v1,平行边：无向图中，若两条不的边ei，ej具有相同的端点，则称ei与ej为G的平行边. 简单图：若无向图中无平行边则称G为简单图. 完备图：若简单图中任意两点之间仅有一边相连，则称为完备图。 有向图：若图G=V , E ，中任意一条边e是V

30、的一个有序元素对， vi，vj,则称G为有向图, vi 为有向图边e的起点， vj为终点。,e,e1,e2,e3,e4,e5,e6,e=u ,v,v2 , v1,v1 , v2,v3 , v2,v3 , v2,v2 , v4,v3 , v4,例：设有： G =V , E ，其中V=v1 ,v2 , v3 ,v4，E=e1 ,e2 ,e76， 边与顶的关联情况由下表所示：,根据表可以化出其图：,e,e1,e2,e3,e4,e5,e6,e=u ,v,v2 , v1,v1 , v2,v3 , v2,v3 , v2,v2 , v4,v3 , v4,平行边：有向图中G ，若两条不的边ei与ej具有相同的

31、端点，则称ei与ej为G的平行边. 简单图：若有向图中无平行边则称G为简单图.,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,完备图：若简单图中任意两点之间恰有两条边有向边vi , vj 与 vj , vi相连，则称该有向图为完备图。 基本图：,同构：若若图G=V , E ，和图G/=V/ , E /的顶点集V 与V/，边 集E 与E / 之间在保持关联性质的条件下一、一对应，则G与G/ 称为同构。（见P163） 由于同构图被认为是相同的，给我们研究和建立网络模型带来 了许多方便。,v6,v4,v5,v3,v2,v1,v/1,v/2,v/3,v/4,v/6,v/5,7.1.2图的

32、矩阵表示 设无向图G =V , E ，V=v1 ,v2 ,vn，E=e1 ,e2 ,em ， 用矩阵的行标号i表示图G的顶点下标；用列标号j表示图G边的 下标，于是可构造一个n*m矩阵A(G)=(aij)与该图对应，其中,0 vi 与 ej 不关联 1 vi 与 ej 关联,aij=,称矩阵A为G关联矩阵,写出关联矩阵,e1 , e2 , e3 , e4, e5 , e6,v1 v2 v3 v4,1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1,第八章网络计划技术,8.1 网络计划技术的基本概念 8.2 网络图时间参数 8.3 网络图时间参数计算

33、8.4 网络计划的时间-费用优化,第八章网络计划技术（统筹法） 81网络计划技术的基本概念 811网络图 一种表示一项工程或一个计划中各项工作或各道工 序的先后顺序、衔接关系以及所需时间的图解模型称 为网络图。它主要由结点“ i ” 和箭线“ ”构成。,8111事项（结点） 指某项工程开始或结束时刻，它是相邻两工序在时 间上的分界点。事项（结点）不消耗资源也不占用时 间，只是表示开始或结束的符号。 8112工序（箭线） “ ”表示工程或计划中的各项工作或活动。工,序要消耗资源和时间。网络图中箭线的长短与工序所 需时间无关。它不是矢量，不必按比例画，可长、可 短、也可弯曲，但不可中断。,例：,8

34、113路和关键路 路指从始点沿着箭头所指的方向连续不断地到达终点 的一条通路。其中最长的一条路称为关键路。 812网络图绘制规则 （1）每一道工序用两个结点和一个箭线组成，箭杆上（下）通常标出活动代号，一条箭线只能代表一道工序. （2）每一道工序完工所需时间以数字标于箭下（上）.,（3）箭头方向表示工程进行的方向，通常按从左向 右，从上向下的方向编号。 （4）每一道工序的先后连接关系根据工程的实际情况而定。 （5）一道或几道工序结束之后，紧接着又开始一道或 几道工序，则分别称为紧前工序、紧后工序。如图,和为的紧后工序,和为的紧前工序,（6）引用虚工序 网络图中“ ”称为虚工序，引用虚工序可以,

35、虚工序的引入 明确地表示在 之后。和 均为的紧 前工序。,（7）相邻两个结点之间只 能有一条箭线。如不可以 表示为：,明确各项工序间的相互关系，以消除模棱两可、含 糊不清的现象。虚工序不消耗资源和时间。,（8）网络图中不能有回路，即不能表示为：,（9）网络图中不能有缺口，即只有一个始点和一个终点。,813两种缩短工期的作业法 8131平行作业 为了缩短工期，在条件允许的情况下可以采用将某 一工序分解成若干道子工序同时进行，这种方法称为 平行作业法，如,8132交叉作业 为了缩短工期还经常采用几道工序交叉进行施工的方 式,例如修建某段铁路，有3道工序，（a）修路基；（b）铺路面；（c）铺钢轨。,

36、可将各道工序分为3段： a = a1 +a2+ a3 b = b1 +b2+ b 3 c = c1+ c2+ c3 交叉进行,11,3,6,8,6,5,10,9,4,2,1,c3,c2,c1,b3,b2,b1,a3,a2,a1,判断下面网络图是否正确。,a1,a2,a3,b1,b2,b3,c1,c2,c3,82网络图时间参数 821工序时间的确定 在一定条件下，完成某一工序所需要的时间称为工序时间 ，通常用t(i,j)表示，其单位可视具体情况而定。确定工序 时间有两种方法 8211一点时间估计法 在具备工时定额或劳动定额资料的条件下，或者在具有 类似工序作业时间的统计资料时，可以根据这些资料，

37、 用分析、对比、计算的方法直接估算工序的作业时间。 8212三点时间估计法 在不具备工时定额或类似工序作业时间的统计资料，且 作业时间较长，未知的和难以估计的因素较多的情况下， 对完成工序所用时间可用3点时间估计，然后计算它们的 平均值，将其作为工序时间。 三种时间为：,(1)最乐观时间：指在顺利情况下完成工序所需要的时间 ， 用a表示。 (2)最可能时间：指在正常情况下完成工序所需要的时间 ， 用m表示。 (3)最保守时间：指在不利情况下完成工序所需要的时间 ，用b表示。 工序时间按下列公式计算 t(i,j)=(ai+4mi+bi)/6 其标准差： ij=(bi-ai)/6 整个工程所需要的

38、时间为关键路线上各道工序时间之和 ，若关键路线上有n道工序，则工程的完工时间渐近于一个 正态分布，其均值、方差分别为：,n TE= (ai+4mi+bi)/6 i=1,n 2= (bi-ai)/62 i=1,记为：N（TE，2）,在TE ，2为已知的情况下，可以计算出： （1）工程某一时间完工的概率； （2）具有一定概率值的完工时间。 如工程完工时间（目标时间）为TK 的概率，通过线性变换，可将TK 化为标准的正态分布：N（0，1）。 即 = （ TK - TE ）/ 服从于标准正态分布 N（0，1）. 例：已知某项工程关键路线由4道工序组成，有关数据如下：,6,7,5,2,(1)工程21天、

39、19天完工的概率？ (2)概率不小于0.9的完工时间？,解：（1） TK=21,4 TE = (ai+4mi+bi)/6 i=1,=2+5+7+6=20,4 =(bi-ai)/62 1/2 i=1,=(1/9 + 16/9 + 16/9 + 9/9)1/2 =(42/9)1/2 =2.16,于是: =（ TK - TE ）/= (21-20)/2.16=0.46 查正态分布表得:P(0.46)=0.68, TK=19时 =（TE - TK）/ = (19-20)/2.16 = -0.46 查正态分布表得: P(-0.46)=0.32 试问20天完工的概率?,(2)由P(*)=0.9 查表得:

40、*=1.3 从而可得: TK = TE +* =20+1.32.16 = 22.8(天) 即23天完工的概率不小于90%.,822事项的时间参数 8.2.2.1事项最早开始时间tE(j) 指从始点事项到本事项的最长路线上各工序的时间之 和。若令始点事项的最早开始时间tE(1)=0，则按公式 tE(j)=max tE(i)+t(i,j) j=2,3,n 从始点事项开始，由左向右依此计算。 例：已知某工程网络图如下,解：tE(1)=0 tE(2)= tE(1)+ t(1，2)=2 tE(3)= tE(1)+ t(1，3)=3 tE(4) = maxtE(2)+ t(2，4)；tE(3)+ t(3，

41、4) = max2+5；3+2=7 tE(5) = maxtE(3)+ t(3，5)；tE(4)+ t(4，5) = max3+4；7+3=10,8.2.2.2事项最迟结束时间tL(i) 若该事项在某时刻不完成，就要影响它紧后工序的按 时开工，从而影响整个工程进度，则这个时间就称为事 项的最迟结束时间。 根据定义：tL(n) =tE(n)=总工期 则：tL(i)= mintL(j) - t(i,j) i=n-1,n-2,1 从终点事项开始，由右向左依此计算。,例： tL(5) = tE(5)=10 tL (4)= tL(5)- t(4,5)=10-3=7,tL (3)= min tL(5)-

42、t(3,5);tL (4)- t(3,4) = min 10-4；7- 2=5 tL (2)= tL(4)- t(2,4)=7-5=2 tL (1)= min tL(2)- t(1,2)；tL (3)- t(1,3) = min 2- 2；5- 3=0,8.2.2.3事项的时差s(i) 一个事项的结束可以推迟而又不至于影响整个工程 的完工，这个时间差称为事项时差。 公式： s(i)= tL(i)- tE(i) ;i=1，2, n 时差为零的事项为关键事项,将所有关键事项连接 起来即得到关键路线. 823工序的时间参数 8.2.3.1工序的最早开始时间tES(i,j) 任何一个工序都必须在其紧前

43、工序完工之后才能开 始,各紧前工序最早结束时间即为所求工序的最早开始 时间. 计算方法有两种:,(1)tES (i , j)=tE(i) (2)tES(i , j)= maxtES(h,i)+ t(h,i) 从左向右依此计算。 如: tES(4 , 5) = max tES(2,4)+ t(2,4) tES(3,4)+ t(3,4) =max2+ 5;3+2=7,5,3,4,2,1,2,3,4,3,5,2,8.2.3.2工序的最早结束时间tEF(i,j) 工序最早开始时间加上该工序的作业时间 公式: tEF(i,j)= tES(i,j)+ t(i,j) 8.2.3.3工序的最迟开始时间tLS(

44、i,j) 在不影响工程最早结束时间条件下,工序最迟必须 开始的时间.(若不开始将影响其紧后工序的按时开工, 从而影响整个工程的结束时间). 计算方法有两种:,例 tLS(4,5)=tL(5)-t(4,5)=10-3=7 tLS(3,5)=tL(5)-t(3,5)=10-4=6 tLS(3,4)=tL(4)-t(3,4)= 7-2=5 tLS(1,3)=tL(3)-t(1,3)= 5-3=2 或tLS(1,3) = min tLS(3,4)-t(1,3) tLS(3,5)-t(1,3) = min5-3;6-3=2,5,3,4,2,1,2,3,4,3,5,2,(1)tLS(i,j)=tL(j)-

45、t(i,j) (2)tLS(i,j)=mintLS(j,k)-t(i,j) 从右向左依此计算。,8.2.3.4工序的最迟结束时间tLF(i,j) 在不影响整个工程结束的条件下，工序最迟必须结束的时间。 计算公式： tLF(i,j)= tLS(i,j)+t(i,j) 或 tLF(i,j)=tL(j) 8.2.3.5工序的时差 时差是指在不影响按期完成任务的条件下，工作过程中可以 灵活机动使用的时间，时差越大，可以利用的机动时间也越长 ；计算和利用时差是网络计划技术中一个重要问题，它可以 为计划的进度安排提供可选方案，为确定关键路线提供科 学依据，可以进一步挖掘潜力，求得计划安排和资源配置的 最优

46、方案。 （1）工序的总时差R(i,j) 在不影响整个工程的总工期的前提下，工序的完工期可以 推迟的时间。,（2）工序的单时差r(i,j) 指不影响紧后工序最早开始时间的前提下，工序最早结束可以推迟的时间。 计算公式： r(i,j)= tES(j,k)-tEF(i,j) i j k,单,总,a,b,计算公式： R(i,j)= tLS(i,j) tES(i,j) 或 = tLF(i,j) tEF(i,j),8.3.2表上计算（工序）,列表：,8.3网络图时间参数计算 网络图参数的计算可以程序化，利用计算机进行计算 ，对于一些不太复杂的网络图，则可采用下列方法 8.3.1图上计算,关键路线：,0,0,0,12,6,13,6