浙大运筹学PPT参考课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学演示课件,2.0版,浙江大学管理学院,蒋绍忠 制作,2001年8月,1,目 录,第一章线性规划,第二章对偶,第三章整数规划,第四章运输问题,第五章网络优化,第六章动态规划,第七章排 队 论,2,第一章 线性规划,线性规划模型,线性规划的图解,可行域的性质,线性规划的基本概念,基础解、基础可行解,单纯形表,线性规划的矩阵表示,3,线性规划模型,线性规划模型的结构,目标函数：,max,，min,约束条件：,=,变量符号：0,unr,0,线性规划的标准形式,目标函数：,min,约束条件：=,变量符号：0,4,线性规划的图解,max z=x,1,+3x,2,s.t.x,1,+x,2,6,-x,1,+2x,2,8,x,1,0,x,2,0,可行域,目标函数等值线,最优解,6,4,-8,6,0,x,1,x,2,5,可行域的性质,线性规划的可行域是凸集,线性规划的最优解在极点上,凸集,凸集,不是凸集,极点,6,线性规划的基本概念,线性规划的,基矩阵,、,基变量,、,非基变量,=,=,目标函数,约束条件,行列式0,基矩阵,右边常数,7,8,基变量,x,1,、,x,2,、,x,3,，,非基变量,x,4,、,x,5,、,x,6,基础解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）5，3，1，0，0，0）,是基础可行解，表示可行域的一个极点。,目标函数值为：,z=20,9,基变量,x,1,、,x,2,、,x,4,，,非基变量,x,3,、,x,5,、,x,6,基础解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）=（27/5，12/5，0，2/5，0，0）,是基础可行解，表示可行域的一个极点。,目标函数值为：,z=18,10,基变量,x,1,、,x,2,、,x,5,，,非基变量,x,3,、,x,4,、,x,6,基础解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）=（6，3，0，0，-3，0）,是基础解，但不是可行解，不是一个极点。,11,基变量,x,1,、,x,2,、,x,6,，,非基变量,x,3,、,x,4,、,x,5,基础解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）=（3，4，0，0，0，4）,是基础可行解，表示可行域的一个极点。,目标函数值为：,z=18,12,基变量,x,2,、,x,3,、,x,4,，,非基变量,x,1,、,x,5,、,x,6,基础解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）=（0，21/2，27/2，-30，0，0）,是基础解，但不是可行解。,13,基变量,x,1,、,x,2,、,x,3,，,非基变量,x,4,、,x,5,、,x,6,基础解为（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）=（0，3，6，0，15，0）,是基础可行解，表示可行域的一个极点。,目标函数值为：,z=15,14,基变量,x,1,、,x,2,、,x,3,，,非基变量,x,4,、,x,5,、,x,6,基础解为,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,）=（0，11/2，-3/2，0，0，10）,是基础解但不是可行解。,15,=,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,=,基变量,16,=,进基变量,离基变量,目标函数,约束条件,右边常数17,=,目标函数,约束条件,新的基矩阵,右边常数,=,18,=,进基变量,离基变量,目标函数,约束条件,基矩阵,=,19,=,目标函数,约束条件,新的基矩阵,右边常数,=,20,基础解、基础可行解,max z=x,1,+3x,2,D,s.t.x,1,+x,2,+x,3,=6 B,-x,1,+2x,2,+x,4,=8 x,4,=0 C x,3,=0,x,1,x,2,x,3,x,4,0 x,1,=0,E O x,2,=0 A,21,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：,凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值线：,一组平行线,目标函数值等于一个常数的解,22,单纯形表,23,求解线性规划问题,写成标准化形式,24,写出单纯形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/,1/2,1,x,5,1/2,1,0,1/2,18/,1/2,0,7,18,1,1/2,1/2,x,2,0,x,6,离基，,x,2,进基，,x,5,离基，,x,1,进基，,25,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x,1,0,1,-1,1,0,14,11,0,1,0,x,2,0,得到最优解，最优解为：,（,x,1,，x,2,，x,3,，x,4,，x,5,，x,6,）=（14，11，0，0，0，0）,min z=-86，max z=86,26,27,28,29,30,线性规划的矩阵表示,=,=,31,=,=,=,32,33,34,C,B,T,B,-1,a,j,-c,j,=z,j,-c,j,称为非基变量的检验数（,Reduced Cost,）,B,-1,a,j,=Y,j,，B,-1,b=，C,B,T,B,-1,b=z,0,35,36,第二章 对偶线性规划,对偶的定义,对偶问题的性质,原始对偶关系,目标函数值之间的关系,最优解之间的关系互补松弛关系,最优解的,Kuhn-Tucher,条件,对偶可行基对偶单纯形法,对偶的经济解释,DUAL,37,一、对偶的定义,原始问题,min z=C,T,X,s.t.AXb,X 0,对偶问题,max y=b,T,W,s.t.A,T,WC,W,0,min,b,A,C,T,C,A,T,b,T,max,m,n,m,n,38,二、对偶问题的性质,1、对偶的对偶就是原始问题,max z=-C,T,X,s.t.-AX,-b,X 0,min y=-b,T,W,s.t.-A,T,W,-C,W,0,max y=b,T,W,s.t.A,T,WC,W,0,min z=C,T,X,s.t.AXb,X 0,对偶的定义,对偶的定义,39,min z=C,T,X,s.t.AX,b,X 0,max y=b,T,W,s.t.A,T,WC,W,0,2、其他形式问题的对偶,min z=C,T,X,s.t.AX,b,X 0,max y=b,T,W,s.t.A,T,WC,W,0,min z=C,T,X,s.t.AX,=,b,X 0,max y=b,T,W,s.t.A,T,WC,W：,unr,40,三、原始对偶关系,1、可行解的目标函数值之间的关系,设,X,F,、W,F,分别是原始问题和对偶问题的可行解,z=C,T,X,F,W,T,AX,F,W,T,b=y,2、,最优解的目标函数值之间的关系,设,X,o,、W,o,分别是原始问题和对偶问题的最优解,z=C,T,X,o,=W,oT,AX,o,=W,oT,b=y,41,3、原始问题和对偶问题最优解之间的互补松弛关系,min z=C,T,X,s.t.AX-X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W+W,S,=C,W,W,S,0,min z=C,T,X,s.t.AXb,X 0,max y=b,T,W,s.t.A,T,WC,W0,对偶,引进松弛变量,引进松弛变量,X,T,W,S,=0 W,T,X,S,=0,互补松弛关系,X，Xs,W，Ws,42,min z=C,T,X,s.t.AX-X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W+W,S,=C,W,W,S,0,X,T,W,S,=0,W,T,X,S,=0,m,n,=,W,W,S,A,T,I,C,n,=,A,X,S,-,I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,43,w,1,w,i,w,m,w,m+1,w,m+j,w,n+m,x,1,x,j,x,n,x,n+1,x,n+i,x,n+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,x,j,w,m+j,=0w,i,x,n+i,=0(i=1,2,m;j=1,2,n),在一对变量中，其中一个大于0，另一个一定等于0,44,Kuhn-Tucher,条件,3、原始问题和对偶问题最优解的充分必要条件,(1)原始可行条件（,PFC）,AX-X,Sb,X,X,S,0,(2),对偶可行条件（DFC）,A,T,W+W,S,=C,W,W,S,0,(3),互补松弛条件（,CSC）,X,T,W,S,=0,W,T,X,S,=0,45,四、对偶单纯形法,1、用单纯形表求解原始问题的四种形式,min,z=C,T,X,s.t.AX,b,X 0,min,z=C,T,X,s.t.AX,b,X 0,max,z=C,T,X,s.t.AX,b,X 0,max,z=C,T,X,s.t.AX,b,X 0,（2）,（3）,（4）,（1）,46,单纯形表和对偶(1),min z=C,T,X,s.t.AX-X,S,=b,X,X,S,0,max y=b,T,W,s.t.AT,W+W,S,=C,W,W,S,0,min z=C,T,X,s.t.AXb,X 0,max y=b,T,W,s.t.A,T,WC,W0,对偶问题,原始问题,引进松弛变量,引进松弛变量,47,min z=C,T,X,s.t.AX-X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W+W,S,=C,W,W,S,0,W,T,=C,B,T,B,-1,W,S,T,=C,T,-W,T,A,48,min z=C,T,X,s.t.AX,+,X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W+W,S,=C,W,0,W,S,0,min z=C,T,X,s.t.AX,bX 0,max y=b,T,W,s.t.A,T,WC,W,0,单纯形表和对偶(2),对偶问题,原始问题,引进松弛变量,引进松弛变量,49,min z=C,T,X,s.t.AX+X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W+W,S,=C,W 0,W,S,0,W,T,=C,B,T,B,-1,W,S,T,=C,T,-W,T,A,50,max z=C,T,X,s.t.AX-X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W-W,S,=C,W,0,W,S,0,max z=C,T,X,s.t.AX b,X 0,min y=b,T,W,s.t.A,T,W C,W,0,单纯形表和对偶(3),对偶问题,原始问题,引进松弛变量,引进松弛变量,51,max z=C,T,X,s.t.AX-X,S,=b,X,X,S,0,min y=b,T,W,s.t.A,T,W-W,S,=C,W 0,W,S,0,W,T,=C,B,T,B,-1,W,S,T,=W,T,A-C,T,52,max z=C,T,X,s.t.AX+X,S,=b,X,X,S,0,max y=b,T,W,s.t.A,T,W-W,S,=C,W,W,S,0,max z=C,T,X,s.t.AX b,X 0,min y=b,T,W,s.t.A,T,W C,W 0,单纯形表和对偶(4),对偶问题,原始问题,引进松弛变量,引进松弛变量,53,max z=C,T,X,s.t.AX+X,S,=b,X,X,S,0,min y=b,T,W,s.t.A,T,W-W,S,=C,W,W,S,0,W,T,=C,B,T,B,-1,W,S,T,=W,T,A-C,T,54,2、对偶单纯形法（初始解原始不可行的问题）,55,56,57,已获得最优解：,（,x,1,x,2,x,3,x,4,x,5,x,6,）=（5,7,6,0,0,0）min z=35,对偶问题的最优解为：,（,w,1,w,2,w,3,w,4,w,5,w,6,）=（-1,5,7,0,0,0）max y=35,58,3、初始解原始、对偶都不可行的问题,59,解法1先解决原始可行性,60,61,在得到原始可行解时同时得到对偶可行解，已获得最优解：,（,x,1,x,2,x,3,x,4,x,5,x,6,）=（5,7,6,0,0,0）min z=17,对偶问题的最优解为：,（,w,1,w,2,w,3,w,4,w,5,w,6,）=（-7,5,10,0,0,0）max y=17,62,解法2：先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,63,64,得到原始可行解，已获得最优解：,（,x,1,x,2,x,3,x,4,x,5,x,6,）=（5,7,6,0,0,0）min z=17,对偶问题的最优解为：,（,w,1,w,2,w,3,w,4,w,5,w,67,5,10,0,0,0）max y=17,65,五、对偶的经济解释,1、,原始问题是利润最大化的生产计划问题,单位产品的利润（,元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（,吨）,消耗的资源（吨）,66,2、,对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解,w,1,、,w,2,、.、,w,m,称为,m,种资源的,影子价格（,Shadow Price,）,原始和对偶问题都取得最优解时，,最大利润,max z=min y,67,3、,资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺,影子价格越小，说明这种资源相对不紧缺,如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,68,w,1,w,2,w,m,4、产品的机会成本,机会成本,表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,69,机会成本,利润,差额成本,5、产品的差额成本（,Reduced Cost,）,差额成本=机会成本-利润,70,5、互补松弛关系的经济解释,在利润最大化的生产计划中,（1）边际利润大于0的资源没有剩余,（2）有剩余的资源边际利润等于0,（3）安排生产的产品机会成本等于利润,（4）机会成本大于利润的产品不安排生产,71,第四章 运输问题,运输问题的表示,网络图、线性规划模型、运输表,初始基础可行解,西北角法、最小元素法,非基变量的检验数,闭回路法、对偶变量法,确定进基变量，调整运量，确定离基变量,72,2,3,2,1,3,4,1,运输问题网络图,s,2,=27,s,3,=19,d,1,=22,d,2,=13,d,3,=12,d,4,=13,s,1,=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,73,运输问题线性规划模型,供应地约束,需求地约束,74,运输问题的表格表示,75,初始基础可行解西北角法,8,13,13,14,6,6,76,初始基础可行解最小元素法（1）,77,最小元素法（2）,78,最小元素法（3）,79,最小元素法（4）,80,最小元素法（5）,81,最小元素法（6）,82,-5,非基变量,x,ij,的检验数,z,ij,-c,ij,闭回路法(1),z,12,-c,12,=(c,11,-c,21,+c,22,)-c,12,=6-8+4-7=-5,83,-5,闭回路法,(2),z,13,-c,13,=(c,11,-c,21,+c,23,)-c,13,=6-8+2-5=-5,-5,84,-5,闭回路法,(3),z,14,-c,14,=(c,11,-c,21,+c,21,-c,23,+c,33,-c,14,)-c,13,=(6-8+2-10+6)-3=-7,-7,-5,85,-5,闭回路法,(4),z,24,-c,24,=(c,23,-c,33,+c,34,)-c,24,=(2-10+6)-7=-9,-9,-5,-7,86,-5,闭回路法,(5),z,31,-c,31,=(c,21,-c,23,+c,33,)-c,31,=(8-2+10)-5=+11,+11,-5,-7,-9,87,-5,闭回路法,(6),z,32,-c,32,=(c,22,-c,23,+c,33,)-c,32,=(4-2+10)-9=+3,+3,-5,-7,-9,+11,88,非基变量,x,ij,的检验数,z,ij,-c,ij,对偶变量法,(1),v,4,=0,89,对偶变量法,(2),u,3,+v,4,=c,34,u,3,=6,90,对偶变量法,(3),u,3,+v,3,=c,33,v,3,=4,91,对偶变量法,(4),u,2,+v,3,=c,23,u,2,=-2,92,对偶变量法,(5),u,2,+v,2,=c,22,v,2,=6,93,对偶变量法,(6),u,2,+v,1,=c,21,v,1,=10,94,对偶变量法,(7),u,1,+v,1,=c,11,u,1,=-4,95,对偶变量法,(8),z,12,-c,12,=u,1,+v,2,-c,12,=(-4)+6-7=-5,-5,96,对偶变量法,(9),z,13,-c,13,=u,1,+v3,-c,13,=(-4)+4-5=-5,-5,-5,97,对偶变量法,(10),z,14,-c,14,=u,1,+v,4,-c,14,=(-4)+0-3=-7,-7,-5,-5,98,对偶变量法,(11),z,24,-c,24,=u,2,+v,4,-c,24,=(-2)+0-7=-9,-9,-5,-5,-7,99,对偶变量法,(12),z,31,-c,31,=u,3,+v,1,-c,31,=6+10-5=11,11,-5,-5,-7,-9,100,对偶变量法,(13),z,32,-c,32,=u,3,+v,2,-c,32,=6+6-9=+3,+3,-5,-5,-7,-9,11,101,选择进基变量,确定离基变量,x,31,进基,minx,21,x,33,=min8,6=6,x,33,离基,+3,-5,-5,-7,-9,11,102,调整运量,重新计算检验数,确定进基、离基变量,x,14,进基,minx,11,x,34,=min14,13=13,x,34,离基,-11,-5,-5,+4,+2,-8,103,调整运量,重新计算检验数,所有,z,ij,-c,ij,0,得到最优解。,Min z=61+3 13+8 2+4 13+2 12+5 19=142,-11,-5,-5,-4,-8,-2,104,第五章 网络优化,网络的基本概念,网络最小费用流问题,网络最大流问题,最短路径问题,105,网络的基本概念,节点与（有向）边,每一条边和两个节点关联，一条边可以用两个节点的标号表示（,i，,j,）,j,i,路径（,Path,）,前后相继并且方向相同的边序列,P=(1,2),(2,3),(3,4),4,2,3,1,4,2,3,1,网络由节点和边组成,106,回路（,Circuit,）,起点和终点重合的路径称为,回路,=,(1,2),(2,4),(4,1),回路中各条边方向相同,4,2,3,1,链（,Chain,）,前后相继并且方向不一定相同的边序列称为,链,C=(1,2),(3,2),(3,4),4,2,3,1,107,连通图,任意两个节点之间至少有一条链的图称为,连通图,2,43,5,1,圈(,Cycle),起点和终点重合的链称为,圈,=(1,2),(2,4),(3,4),(1,3),圈中各条边方向不一定相同,4,2,3,1,树(,Tree),无圈的连通图称为,树,树中只与一条边关联的节点称为,悬挂节点,108,树的性质,任何树至少有一个悬挂节点,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树的节点个数为,m，,则边的个数为,m-1,树中任意两个节点之间只有唯一的一条链,在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈,109,网络的生成树,由网络的所有节点（,m,个）和网络的,m-1,条边组成的树称为网络的,生成树,，网络中不属于生成树的边称为生成树的,弦,4,2,3,1,4,2,3,1,4,2,3,1,4,2,3,1,4,2,3,1,4,2,3,1,4,2,3,1,110,网络的生成树的变换,4,2,3,1,网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树,4,2,3,1,4,2,3,1,4,2,3,1,生成树2,生成树3,生成树1,/,/,111,网络的生成树和线性规划的关系,网络的一个生成树对应于线性规划的一个基,生成树上的边对应于线性规划的基变量,生成树的弦对应于线性规划的非基变量,生成树的变换对应于线性规划单纯形法的进基和离基变换,112,网络最小费用流问题,b,2,=-2b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,c,24,=5,c,46,=1,c,13,=3,c,35,=2,c,56,=4,c,34,=4,c,12,=6,2,3,4,5,6,1,需求节点,供应节点,c,ij,单位流量的费用,113,初始基础可行解生成树,b,6,=-5,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,1,=5,x,13,=3,x,46,=3,x,35,=8,x,56,=2,x,12,=2,2,3,4,5,6,1,114,确定非基变量,x,24,和,x,34,b,2,=-2,b,6,=-5,b,3,=5,b,5,=-6,b,1,=5,c,24,=5,c,46,=1,c,13,=3,c,35,=2,c,56,=4,c,34,=4,c,12,=6,2,3,4,5,6,1,b,4,=3,115,求,x,24,的检验数,z,24,-c,24,闭回路法,z,24,-c,24,=(-c,46,+c,56,+c,35,+c,13,-c,12,)-c,24,=(-1+4+2+3-6)-5=-3,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,c,24,=5,c,46,=1,c,13,=3,c,35,=2,c,56,=4,c,12,=6,2,3,4,5,6,1,116,求,x,34,的检验数,z34,-,c,34,闭回路法,z,34,-c,34,=(-c,46,+c,56,+c,35,)-c,34,=(-1+4+2)-4=+1，x,34,进基,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,c,46,=1,c,13,=3,c,35,=2,c,56,=4,c,34,=4,c,12,=6,2,3,4,5,6,1,117,变量,x,34,进基，确定离基变量,minx,56,x,35,=min2,8=2,x,56,离基，调整流量，进行基变换,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,x,46,=3,x13,=3,x,35,=8,x,56,=2,x,34,=0,x,12,=2,2,3,4,5,6,1,118,确定非基变量,x,24,和,x,56,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,x,46,=5,x,13,=3,x,35,=6,x,34,=2,x,12,=2,2,3,4,5,6,1,119,计算,x,24,和,x,56,的检验数,z,24,-,c,24,、z,56,-c,56,z,24,-c,24,=(c,34,+c,13,-c,12,)-c,24,=(4+3-6)-5=-4,z,56,-c,56,=(c,46,+c,34,-c,35,)-c,56,=(1+4-2)-4=-1，,获得最优解,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,c,24,=5,c,46,=1,c,13,=3,c,35,=2,c,56,=4,c,34,=4,c,12,=6,2,3,4,5,6,1,120,最优解,最优解的目标函数值为：,min,z=6,2+33+42+26+15=46,b,2,=-2,b,4,=3,b,3,=5,b,5,=-6,b,6,=-5,b,1,=5,x,46,=5,x,13,=3,x,35,=6,x,34,=2,x,12,=2,2,3,4,5,6,1,121,网络最大流问题,2,3,54,6,7,1,f,f,u,25,=6,u,42,=2,u,45,=4,u,23,=3,u,13,=7,u,34,=4,u,46,=3,u,36,=1,u,65,=7,u,57,=9,u,67,=8,u,12,=8,122,边的容量和流量,容量,u,ij,，,流量,x,ij,可行流,满足以下条件的流称为可行流：,1、每一个节点流量平衡,2、0,x,ij,u,ij,边的容量和流量、可行流,123,2,1,x,ij,=5,u,ij,=5,2,1,x,ij,=3,u,ij,=5,饱和边、不饱和边、流量的间隙,（1，2）是饱和的,2、如果,x,ij,0，,边从,j,到,i,的方向是不饱和的；,（2，1）是不饱和的,间隙为,12,=,x,12,=5,125,给出一个初始的可行流,x,ij,=0,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,126,找到所有的不饱和边，以及各边可以调整流量的方向,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,127,找到一条从1到7的不饱和链,链的间隙为：,=,min8,3,1,8=1,调整链的流量：,x,ij,=x,ij,+,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,=3,=1,=8,=8,x=0,128,调整流量，,f=1。,继续求出网络的不饱和边,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,129,求出一条从1到7的不饱和链,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,=1,=6,=9,=7,=,min 7,1,6,9=1,调整流量,x,ij,=x,ij,+1,f=f+1=2,130,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=2,f=2,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=1,x=0,x=0,x=1,x=0,x=0,x=0,x=1,x=1,x=1,x=1,x=0,131,求出一条从1到7的不饱和链,2,3,5,4,6,7,1,f=2,f=2,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=1,x=0,x=0,x=1,x=0,x=0,x=0,x=1,x=1,x=1,x=1,x=0,=5,=8,=7,=,min 7,5,8=5,调整流量,x,ij,=x,ij,+5,f=f+5=2+5=7,132,调整流量，继续求出网络的不饱和边,2,3,5,4,6,71,f=7,f=7,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=0,x=1,x=0,x=0,x=0,x=6,x=1,x=1,x=6,x=0,133,2,3,5,4,6,7,1,f=7,f=7,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=0,x=1,x=0,x=0,x=0,x=6,x=1,x=1,x=6,x=0,求出一条从1到7的不饱和链,=,min 6,7,4,3=3,调整流量,x,ij,=x,ij,+3,f=f+3=7+3=10,=4,=4,=3,6,134,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=10,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,135,求出一条从1到7的不饱和链,2,3,5,4,6,7,1,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,f=10,=1,=3,=7,=3,=,min 3,1,3,7=1,调整流量,x,ij,=x,ij,+1,f=f+1=10+1=11,136,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=11,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3,137,已求得最大流,2,3,5,4,6,7,1,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,f=11,最大流,f=11，,最小割集为（2,5）（3,4）（3,5）,u,25,+u,34,+u,35,=6+4+1=11,138,最短路径问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,139,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,w,1,=0,min c,12,c,14,c,16,=min 0+2,0+1,0+3=min 2,1,3=1,X=1,4,w,4,=1,w,1,=0,w,1,=0,140,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,4,min c,12,c,16,c,42,c,47,=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2,X=1,2,4,w,2,=2,w,1,=0,w,4,=1,w,2,=2,141,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,min c,13,c,23,c,25,c,47,=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3,X=1,2,4,6,w,6,=3,w,2,=2,w,4,=1,w,1,=0,w,6,=3,142,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,min c,23,c,25,c,47,c,67,=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,X=1,2,4,6,7,w,7,=3,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,143,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,25,c,75,c,78,=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6,X=1,2,4,5,6,7,w,5,=6,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,144,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,53,c,58,c,78,=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8,X=1,2,3,4,5,6,7,w,3,=8,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,w,3,=8,145,2,37,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,min c,38,c,58,c,78,=min 8+6,6+4,3+7=min 14,10,11=10,X=1,2,3,4,5,6,7,8,w,8,=10,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,w,3,=8,w,8,=10,146,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,8,1,到10的最短路径为1，4，7，5，8，长度为10。,w,2,=2,w,41,w,1,=0,w,6,=3,w,7,=3,w,5,=6,w,3,=8,w,8,=10,147,第六章 动态规划,最短路径问题,资源分配问题,背包问题,机器负荷分配问题,148,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,一、最短路径问题,求从,A,到,E,的最短路径,149,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,5,(E)=0,150,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,1,)=5,f,5,(E)=0,151,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,4,(D,1,)=5,152,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,1,)=8,f,4,(D,1,)=5,153,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,2,)=7,f,4,(D,1,)=5,f,3,(C,1,)=8,154,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,