运筹学基最短路松弛互补.ppt

运筹学,目 录,第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划 第七章 排 队 论,第一章 线性规划,线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示,线性规划模型,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, unr, 0 线性规划的标准形式 目标函数：min 约束条件 ：= 变量符号 ：0,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,可行域的性质,线性规划的可行域是凸集 线性规划的最优解在极点上,凸集,凸集,不是凸集,极点,线性规划的基本概念,线性规划的基矩阵、基变量、非基变量,=,=,目标函数,约束条件,行列式0 基矩阵,右边常数,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20,基变量x1、x2、x4，非基变量x3、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18,基变量x1、x2、x5，非基变量x3、x4、x6,基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。,基变量x1、x2、x6，非基变量x3、x4、x5,基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18,基变量x2、x3、x4，非基变量x1、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基础解，但不是可行解。,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=15,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,目标函数,约束条件,新的基矩阵,右边常数,进基变量,离基变量,目标函数,约束条件,基矩阵,目标函数,约束条件,新的基矩阵,右边常数,基础解、基础可行解,max z=x1+3x2 D s.t. x1+ x2+x3 =6 B -x1+2x2 +x4 =8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集： 凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值线： 一组平行线,目标函数值等于一个常数的解,单纯形表,求解线性规划问题,写成标准化形式,写出单纯形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/2,0,7,18,1,1/2,1/2,x2,0,x6离基，,x2进基，,x5离基，,x1进基，,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,0,14,11,0,1,0,x2,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z=-86，max z=86,线性规划的矩阵表示,=,=,CBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost） B-1aj=Yj， B-1b= ，CBTB-1b=z0,第二章 对偶线性规划,对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的Kuhn-Tucher条件 对偶可行基对偶单纯形法 对偶的经济解释,DUAL,一、对偶的定义,原始问题 min z=CTX s.t. AXb X 0,对偶问题 max y=bTW s.t. ATWC W 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,二、对偶问题的性质,1、对偶的对偶就是原始问题,2、其他形式问题的对偶,三、原始对偶关系,1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解 z=CTXF WTAXF WTb=y 2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y,3、原始问题和对偶问题最优解之间的互补松弛关系,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,互补松弛关系,min z=CTX s.t. AX-XS=b X, XS 0,max y=bTW s.t. ATW+WS=C W, WS 0,XTWS=0 WTXS=0,m,n,=,W,WS,AT,I,C,n,=,A,XS,-I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjwm+j=0 wixn+i=0 (i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0,Kuhn-Tucher 条件,3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC） AX-XS=b X, XS 0 (2)对偶可行条件（DFC） ATW+WS=C W, WS 0 (3)互补松弛条件（CSC） XTWS=0 WTXS=0,四、对偶单纯形法,1、用单纯形表求解原始问题的四种形式,min z=CTX s.t. AXb X 0,min z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,（2）,（3）,（4）,（1）,单纯形表和对偶(1),min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,WT=CBTB-1 WST=CT-WTA,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,min z=CTX s.t. AX b X 0,max y=bTW s.t. ATWC W 0,单纯形表和对偶(2),对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,WT=CBTB-1 WST=CT-WTA,max z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW-WS=C W 0, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,单纯形表和对偶(3),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=CTX s.t. AX-XS=b X, XS0,min y=bTW s.t. ATW-WS=C W 0, WS0,WT=CBTB-1 WST=WTA- CT,max z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW-WS=C W, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,单纯形表和对偶(4),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=CTX s.t. AX+XS=b X, XS0,min y=bTW s.t. ATW-WS=C W, WS0,WT=CBTB-1 WST=WTA- CT,2、对偶单纯形法（初始解原始不可行的问题）,已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,3、初始解原始、对偶都不可行的问题,解法1：先解决原始可行性,在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,解法2：先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,得到原始可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,五、对偶的经济解释,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1 w2 wm,4、产品的机会成本,机会成本 表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本,利润,差额成本,5、产品的差额成本（Reduced Cost）,差额成本=机会成本 - 利润,5、互补松弛关系的经济解释,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产,第四章 运输问题,运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、对偶变量法 确定进基变量，调整运量，确定离基 变量,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,运输问题线性规划模型,供应地约束,需求地约束,运输问题的表格表示,初始基础可行解西北角法,8,13,13,14,6,6,初始基础可行解最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,-5,非基变量xij的检验数zij-cij闭回路法(1),z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5,-5,闭回路法(2),z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,-5,闭回路法(3),z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7,-7,-5,-5,闭回路法(4),z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9,-9,-5,-7,-5,闭回路法(5),z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11,+11,-5,-7,-9,-5,闭回路法(6),z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,非基变量xij的检验数zij-cij对偶变量法(1),v4=0,对偶变量法(2),u3+v4=c34 u3=6,对偶变量法(3),u3+v3=c33 v3=4,对偶变量法(4),u2+v3=c23 u2=-2,对偶变量法(5),u2+v2=c22 v2=6,对偶变量法(6),u2+v1=c21 v1=10,对偶变量法(7),u1+v1=c11 u1=-4,对偶变量法(8),z12-c12=u1+v2-c12=(-4)+6-7=-5,-5,对偶变量法(9),z13-c13=u1+v3-c13=(-4)+4-5=-5,-5,-5,对偶变量法(10),z14-c14=u1+v4-c14=(-4)+0-3=-7,-7,-5,-5,对偶变量法(11),z24-c24=u2+v4-c24=(-2)+0-7=-9,-9,-5,-5,-7,对偶变量法(12),z31-c31=u3+v1-c31=6+10-5=11,11,-5,-5,-7,-9,对偶变量法(13),z32-c32=u3+v2-c32=6+6-9=+3,+3,-5,-5,-7,-9,11,选择进基变量,确定离基变量,x31进基, minx21,x33=min8,6=6, x33离基,+3,-5,-5,-7,-9,11,调整运量,重新计算检验数,确定进基、离基变量,x14进基, minx11,x34=min14,13=13, x34离基,-11,-5,-5,+4,+2,-8,调整运量, 重新计算检验数,所有zij-cij0,得到最优解。 Min z=6×1+3 ×13+8 ×2+4 ×13+2 ×12+5 ×19=142,-11,-5,-5,-4,-8,-2,第五章 网络优化,网络的基本概念 网络最小费用流问题 网络最大流问题 最短路径问题,网络的基本概念,节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）,路径（Path） 前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4),4,2,3,1,4,2,3,1,网络由节点和边组成,回路（Circuit） 起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同,4,2,3,1,链（Chain） 前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4),4,2,3,1,连通图 任意两个节点之间至少有一条链的图称为连通图,2,4,3,5,1,圈(Cycle) 起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3) 圈中各条边方向不一定相同,4,2,3,1,树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点,树的性质,任何树至少有一个悬挂节点,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树的节点个数为m，则边的个数为m-1,树中任意两个节点之间只有唯一的一条链,在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈,网络的生成树,由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦,网络的生成树的变换,网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树,生成树2,生成树3,生成树1,/,/,网络的生成树和线性规划的关系,网络的一个生成树对应于线性规划的一个基 生成树上的边对应于线性规划的基变量 生成树的弦对应于线性规划的非基变量 生成树的变换对应于线性规划单纯形法的进基和离基变换,网络最小费用流问题,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,cij 单位流量的费用,初始基础可行解生成树,b6=-5,b2=-2,b4=3,b3=5,b5=-6,b1=5,x13=3,x46=3,x35=8,x56=2,x12=2,2,3,4,5,6,1,确定非基变量x24和x34,b2=-2,b6=-5,b3=5,b5=-6,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2,3,4,5,6,1,b4=3,求x24的检验数z24-c24 闭回路法,z24 -c24 =(-c46+c56+c35+c13-c12)-c24=(-1+4+2+3-6)-5=-3,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c12=6,2,3,4,5,6,1,求x34的检验数z34 -c34 闭回路法,z34 -c34 =(-c46+c56+c35)-c34=(-1+4+2)-4=+1，x34进基,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2,3,4,5,6,1,变量x34进基，确定离基变量,minx56,x35=min2,8=2, x56离基，调整流量，进行基变换,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x46=3,x13=3,x35=8,x56=2,x34=0,x12=2,2,3,4,5,6,1,确定非基变量x24和x56,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x46=5,x13=3,x35=6,x34=2,x12=2,2,3,4,5,6,1,计算x24和x56的检验数z24 -c24 、z56-c56,z24 -c24 =(c34+c13-c12)-c24=(4+3-6)-5= -4 z56 -c56 =(c46+c34-c35)-c56=(1+4-2)-4= -1，获得最优解,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2,3,4,5,6,1,最优解,最优解的目标函数值为：min z=62+33+42+26+15=46,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x46=5,x13=3,x35=6,x34=2,x12=2,2,3,4,5,6,1,网络最大流问题,边的容量和流量 容量uij，流量xij 可行流 满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0xij uij,边的容量和流量、可行流,饱和边、不饱和边、流量的间隙,（1，2）是饱和的,2、如果xijuij，边从i到j的方向是不饱和的；,（1，2）是不饱和的 间隙为12=u12-x12=5-3=2,1、如果xij=uij，边从i到j的方向是饱和的；,3、如果xij=0，边从j到i的方向是饱和的；,（2，1）是饱和的,如果xij0，边从j到i的方向是不饱和的；,（2，1）是不饱和的 间隙为12=x12=5,给出一个初始的可行流xij=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,找到一条从1到7的不饱和链,链的间隙为： = min8,3,1,8=1 调整链的流量：xij=xij+ ,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,调整流量，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,求出一条从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, 调整流量 xij=xij+1, f=f+1=2,调整流量，继续求出网络的不饱和边,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,求出一条从1到7的不饱和链,=5,=8,=7,=min 7,5,8=5, 调整流量 xij=xij+5, f=f+5=2+5=7,调整流量，继续求出网络的不饱和边,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, 调整流量 xij=xij+3, f=f+3=7+3=10,=4,=4,=3,=6,调整流量，继续求出网络的不饱和边,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,求出一条从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, 调整流量 xij=xij+1, f=f+1=10+1=11,调整流量，继续求出网络的不饱和边,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,已求得最大流,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） u25+u34+u35=6+4+1=11,最短路径问题,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的最短路径,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, w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, w4=1,w1=0,w1=0,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 c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, w2=2,w1=0,w4=1,w2=2,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 c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, w6=3,w2=2,w4=1,w1=0,w6=3,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 c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, w7=3,w2=2,w4=1,w1=0,w6=3,w7=3,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 c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, w5=6,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,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 c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, w3=8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,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,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, w8=10,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,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。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,第六章 动态规划,最短路径问题 资源分配问题 背包问题 机器负荷分配问题,一、最短路径问题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=