动 态 规 划PPT课件

1动态规划模型 动态规划是解决多阶段决策过程最优化的一种方法。多阶段决策问题，是指一个问题可以分为若干个阶段，每一阶段需要作出决策，而一个阶段的决策，常常会影响下一个阶段的决策。要在各个阶段决定一个最优决策，使整个系统达到最佳的效果。第1页/共75页2 设某一个公司要铺设管道，从下图中的设某一个公司要铺设管道，从下图中的A A点出发，点出发，经过经过B B、C C等处，最后到达等处，最后到达D D点。从点。从A A到到D D有很多路有很多路线可以选择，各点之间的距离如下图中所示，线可以选择，各点之间的距离如下图中所示，问该公司应该选择哪一条路线，使从问该公司应该选择哪一条路线，使从A A到到D D的总的总的铺设管道距离最短。的铺设管道距离最短。A AB1B1B2C1C2C3D2 22 24 44 43 33 33 33 31 11 11 1例1 最短路线问题第2页/共75页3先引入几个概念状态每一阶段的起点位置决策由一个状态变到另一个状态的选择xk第K阶段的状态，称为状态变量uk(xk) 从xk 出发所作出的决策，称为决策变量状态转移方程xxk+1k+1=T=Tk k(x(xk k,u,uk k(x(xk k)d(x(xk k,x,xk+1k+1)从状态x xk k出发，转移到状态x xk+1k+1的效益f(x(xk k)从状态x xk k出发到终点的最优效益第3页/共75页4最短路问题的动态规划最优化原理 假设一条最短路线经过状态xk，那么，这条路线上从xk到终点的一段，是从xk出发到终点的所有路线中最短的。第4页/共75页5逆序法（回溯法） 从后向前逐步求出各点到终点的最佳路线，最后得到由起点到终点的最短路线。0)(1, 2, 1),(min)(NfNijfcifijj最短路问题的动态规划模型，归纳为下述递推公式：第5页/共75页643, 143,243, 34()02.3( 1)()1 01( 2)()303( 3)()404D CD CD CfDkf CrfDf CrfDf CrfD 1.从最后一段开始,k=4第6页/共75页71, 131, 2321, 332, 132, 2322, 333.2( 1)3 1( 1)min( 2)min 3 34( 3)1 4( 1)2 1( 2)min( 2)min 3 33( 3)1 4B CB CB CB CB CB Ckrf CfBrf Crf Crf CfBrf Crf C第7页/共75页81,212,24.1( 1)2 4( ) minmin6( 2)4 3B AB Akrf BfArf B最短路径：AB1C1D最短距离：6第8页/共75页9A AB1B1B2C1C2C3D2 22 24 44 43 33 33 33 31 11 11 1Model:sets:cities/a,b1,b2,c1,c2,c3,d/:f;roads(cities,cities)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/:d;Endsets第9页/共75页10data:d=2 4 3 3 1 2 3 1 1 3 4;f= , , , , , ,0;enddatan=size(cities);for(cities(i)|i#lt#n: f(i)=min(roads(i,j): f(j)+d(i,j););end第10页/共75页11 Feasible solution found at iteration: 0 Variable Value N 7.000000 F( A) 6.000000 F( B1) 4.000000 F( B2) 3.000000 F( C1) 1.000000 F( C2) 3.000000 F( C3) 4.000000 F( D) 0.000000 D( A, B1) 2.000000 D( A, B2) 4.000000 D( B1, C1) 3.000000 D( B1, C2) 3.000000 D( B1, C3) 1.000000 D( B2, C1) 2.000000 D( B2, C2) 3.000000 D( B2, C3) 1.000000 D( C1, D) 1.000000 D( C2, D) 3.000000 D( C3, D) 4.000000第11页/共75页12图论与网络模型第12页/共75页13定义有序二元组G= (V,E )称为一个图.图的定义图的定义第13页/共75页14定义定义若将图 G 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权权，并称图 G 为赋赋权权图图.第14页/共75页15第15页/共75页16第16页/共75页17顶点的度顶点的度4)(4vd5)(3)(2)(444vdvdvd第17页/共75页18例 在一次聚会中，认识奇数个人的人数一定是偶数。第18页/共75页19子图子图(3)设 E1E,且 E1,以 E1为边集,E1的端点集为顶点集的图 G 的子图,称为 G 的由由 E1导导出出的的子子图图,记为 GE1. GGv1,v4,v5Ge1,e2,e3第19页/共75页20关联矩阵关联矩阵对无向图，其关联矩阵)(ijm，其中：不关联与若相关联与若jijiijevevm01对有向图，其关联矩阵)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设图为简单图第20页/共75页21邻接矩阵邻接矩阵注：假设图为简单图A=432143210111101011011010vvvvvvvv第21页/共75页22对有向赋权图，其邻接矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义A=4321432105375083802720vvvvvvvv第22页/共75页23第23页/共75页24第24页/共75页25第25页/共75页26步骤：第26页/共75页27例（设备更新问题）设某公司需使用某种设备一套，设备购买价格及维修费用见表。现设该公司在第一年开始时新购入一套设备，问今后5年的设备更新方案如何，才能使得总费用最省？年12345价格1111121213使用年限0-11-22-33-44-5维修费用5681118第27页/共75页28 结点i表示第i年购买一套设备，结点6为虚设的结点第28页/共75页29第29页/共75页30第30页/共75页31第31页/共75页32Ford算法 动态规划法与Dijkstra算法，都假定弧的长度是非负的，但在某些问题中，有时会出现长度为负值的情况，可采用Ford算法。 称临时标号为未着色标号，永久性标号为着色标号。所以Ford算法，只要对Dijkstra算法做两点改变。第32页/共75页33 1、计算T( j)=minT( j), P(k)+bkj时，不仅对未着色点进行，对着色点也要进行。已着色标号也可以减小。 2、仅在所有顶点都已着色，而且下一步不能使任一顶点的标号减小时，算法才终止。第33页/共75页34最短路问题的数学表达式：假定图有n个顶点，现需要求从顶点1到顶点n 的最短路。,10.ijijijxxx 设决策变量为当，说明弧(i,j)位于顶点1至顶点n的路上，否则( , )11( , )(, )11(1, )min;. .0,1, ;1;0,( , )ijiji jEnnijjijji jEj iEnjjjEijw xs txxinxxi jE 第34页/共75页35例例A AB1B1B2C1C2C3D2 22 24 44 43 33 33 33 31 11 11 1Model:Model:Sets:Sets:Cities/a,b1,b2,c1,c2,c3,d/;Cities/a,b1,b2,c1,c2,c3,d/;Roads(cities,cities)/a,b1 a,b2Roads(cities,cities)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/:w,x; c1,d c2,d c3,d/:w,x;endsetsendsets第35页/共75页36data:data:w=2 4 3 3 1 2 3 1 1 3 4;w=2 4 3 3 1 2 3 1 1 3 4;EnddataEnddatan=size(cities);n=size(cities);min=sum(roads:wmin=sum(roads:w* *x);x);for(cities(i)|i#ne#1 #and# i#ne#n:for(cities(i)|i#ne#1 #and# i#ne#n: sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i); sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);sum(roads(i,j)|i#eq#1:x(i,j)=1;sum(roads(i,j)|i#eq#1:x(i,j)=1;endend第36页/共75页37选择菜单命令选择菜单命令“lingo|solutionlingo|solution”，出现对话，出现对话框框第37页/共75页38 Global optimal solution found at iteration: 3 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000最短距离：最短距离：6 A-B1-C1-D6 A-B1-C1-D第38页/共75页39设备更新问题第39页/共75页40model:sets:cities/1.6/;roads(cities,cities)|&1 #lt# &2: c, x;endsetsdata:c=12 22 30 41 59 16 22 30 41 17 23 31 17 23 18;enddatan=size(cities);min=sum(roads: c*x);for(cities(i)|i #ne# 1 #and# i#ne#n: sum(roads(i,j):x(i,j)=sum(roads(j,i): x(j,i);sum(roads(i,j)|i #eq# 1: x(i,j)=1;end第40页/共75页41 Variable Value Reduced Cost X( 1, 3) 1.000000 0.000000 X( 3, 6) 1.000000 0.000000 Global optimal solution found at iteration: 0 Objective value: 53.00000 Variable Value Reduced Cost N 6.000000 0.000000 C( 1, 2) 12.00000 0.000000 C( 1, 3) 22.00000 0.000000 第41页/共75页42无向图的最短路问题 例 求下图u1到u8的最短路 解：对于无向图，从点u1到ui和点ui到u8 的边都看成有向弧，其它各边均看成有不同方向的双弧。第42页/共75页43model:sets:cities/1.8/;roads(cities,cities): p,w,x;endsetsdata:p=0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0;第43页/共75页44w=0 2 1 8 0 0 0 0 2 0 0 6 1 0 0 0 1 0 0 7 0 0 9 0 8 6 7 0 5 1 2 0 0 1 0 5 0 3 0 9 0 0 0 1 3 0 4 6 0 0 0 2 0 4 0 3 0 0 0 0 9 6 3 0;enddatan=size(cities);min=sum(roads: w*x);for(cities(i)|i #ne# 1 #and# i#ne#n: sum(cities(j):p(i,j)*x(i,j)=sum(cities(j): p(j,i)*x(j,i);sum(roads(i,j)|i #eq# 1: p(i,j)*x(i,j)=1;end第44页/共75页45 Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000 X( 2, 5) 1.000000 0.000000 X( 5, 8) 1.000000 0.000000 Global optimal solution found at iteration: 10 Objective value: 12.00000 Variable Value Reduced Cost N 8.000000 0.000000 P( 1, 1) 0.000000 0.000000 P( 1, 2) 1.000000 0.000000 P( 1, 3) 1.000000 0.000000 第45页/共75页46最大流问题的数学表达式：假定图有n个顶点，现需要求从顶点1到顶点n 的最大流量。.ijf 代表弧从i点到j点的流量( , )( , )(1, )min;. .0,1, ;,();,( , )fijjij Vj Vi jEj iEsjfj VjEijijVs txxinxVsfci jE 表示起点 0第46页/共75页47例例Model:Model:Sets:Sets:nodes/v1,v2,v3,v4,v5,v6/;nodes/v1,v2,v3,v4,v5,v6/;arcs(nodes,nodes):p,c,f;arcs(nodes,nodes):p,c,f;endsetsendsetsv1v1v2v2v3v4v5v68 82 27 710109 99 95 55 56 6第47页/共75页48data:data:p=0 1 1 0 0 0 p=0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0; 0 0 0 0 0 0;第48页/共75页49C=0 8 7 0 0 0 C=0 8 7 0 0 0 0 0 5 9 0 0 0 0 5 9 0 0 0 0 0 0 9 0 0 0 0 0 9 0 0 0 2 0 0 5 0 0 2 0 0 5 0 0 0 6 0 10 0 0 0 6 0 10 0 0 0 0 0 0; 0 0 0 0 0 0;enddataenddatan=size(nodes)n=size(nodes)max=flow;max=flow;第49页/共75页50for(nodes(i)|i#ne#1 #and# i#ne#n:for(nodes(i)|i#ne#1 #and# i#ne#n: sum(arcs(i,j):p(i,j) sum(arcs(i,j):p(i,j)* *f(i,j)=f(i,j)= sum(arcs(j,i):p(j,i) sum(arcs(j,i):p(j,i)* *f(j,i);f(j,i);sum(arcs(i,j)|i#eq#1:p(i,j)sum(arcs(i,j)|i#eq#1:p(i,j)* *f(i,j)=flow;f(i,j)=flow;for(arcs:bnd(0,f,c);for(arcs:bnd(0,f,c);endend第50页/共75页51 Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost F( V1, V2) 7.000000 0.000000 F( V1, V3) 7.000000 0.000000 F( V2, V3) 2.000000 0.000000 F( V2, V4) 5.000000 0.000000 F( V3, V5) 9.000000 -1.000000 F( V4, V6) 5.000000 -1.000000 F( V5, V6) 9.000000 0.000000v1v1v2v2v3v4v5v6(8,7)(8,7)(2,0)(2,0)(7,7)(7,7)(10,9)(10,9)(9,9)(9,9)(9,5)(9,5)(5,5)(5,5)(5,2)(5,2)(6,0)(6,0)最大流量：最大流量：1414第51页/共75页52最小费用最大流问题最小费用最大流问题ijijijifudi 设 为弧(i,j)上的流量，c 为弧(i,j)上的单位运费，弧(i,j)上的容量， 是节点 处的净流量.最小费用最大流问题的数学表达式：( , )( , )( , )( , )min;. .0,;,( , )ijiji jEijjij Vj Vi jEj iEsjfj Vs jEijijc fs tffifVsfui jE起点，终点 为起点 0第52页/共75页53v1v1v2v2v3vsvt(8,1)(8,1)(2,6)(2,6)(7,1)(7,1)(10,4)(10,4)(10,3)(10,3)(4,2)(4,2)(5,2)(5,2)例例 第第1 1个数字是网络的个数字是网络的容量，第容量，第2 2个数字是个数字是网络的单位运费网络的单位运费. .求求流量流量F F为为1010的最小费的最小费用用Model:Model:Sets:Sets:nodes/vs,v1,v2,v3,vt/nodes/vs,v1,v2,v3,vt/：d;d;arcs(nodes,nodes)/vs,v1 vs,v2 v1,v3 v1,vtarcs(nodes,nodes)/vs,v1 vs,v2 v1,v3 v1,vt v2,v1 v2,v3 v3,vt/:c,u,f; v2,v1 v2,v3 v3,vt/:c,u,f;endsetsendsets第53页/共75页54data:data:d=10 0 0 0 -10;d=10 0 0 0 -10;C=4 1 6 1 2 3 2;C=4 1 6 1 2 3 2;u=10 8 2 7 5 10 4;u=10 8 2 7 5 10 4;enddataenddatan=size(nodes);n=size(nodes);min=sum(arcs:cmin=sum(arcs:c* *f);f);第54页/共75页55for(nodes(i)|i#ne#1 #and# i#ne#n:for(nodes(i)|i#ne#1 #and# i#ne#n: sum(arcs(i,j):f(i,j)= sum(arcs(i,j):f(i,j)= sum(arcs(j,i):f(j,i); sum(arcs(j,i):f(j,i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:bnd(0,f,u);for(arcs:bnd(0,f,u);endend第55页/共75页56 Global optimal solution found at iteration: 6 Objective value: 48.00000 Variable Value Reduced Cost F( VS, V1) 2.000000 0.000000 F( VS, V2) 8.000000 0.000000 F( V1, VT) 7.000000 -1.000000 F( V2, V1) 5.000000 -1.000000 F( V2, V3) 3.000000 0.000000 F( V3, VT) 3.000000 0.000000最小费用：最小费用：4848第56页/共75页57最优连线问题（最小生成树） 定义：如果无向图是连通的，且不包含有圈，则称该图为树(tree). 如果有向图中任何一个顶点都可由某一顶点到达，则该顶点称为图的根(root). 如果有向图G有根，且它的基础图是树，则称G为有向树.第57页/共75页58生成树 定义：若F是包含G的全部顶点的子图，它又是树，则称F为生成树或支撑树. 定理：如果无向图是连通的、有限的，则在G中存在生成树. 定义：在一个赋权图中，称具有最小权和的生成树为最优生成树或最小生成树.第58页/共75页59求最小生成树的算法: 避圈法(Kruskal算法) 1、选择边e1,使得w(e1)尽可能小； 2、若已选定边e1 e2 ei,则从E e1 e2 ei中选取边e(i+1),使得 Ge1 e2 ei e(i+1)为无圈图； w(e(i+1)是满足的尽可能小的权； 3、当2不能继续执行时停止.第59页/共75页60第60页/共75页61最小生成树的数学表达式：( , )1min;. .1;1,1;()ijiji jAjj Vjij Vd xs txxi 各边不构成圈第61页/共75页62例 假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。 第62页/共75页63第63页/共75页64第64页/共75页65第65页/共75页66第66页/共75页67第67页/共75页68第68页/共75页69第69页/共75页70旅行商问题(货郎担问题) 定义：包含图G的每个顶点的路称为Hamilton路， 包含图G的每个顶点的圈成为Hamilton圈. 一个图若包含Hamilton圈，则称这个图为Hamilton图. 旅行商问题就是求最小距离的Hamilton圈第70页/共75页71第71页/共75页72第72页/共75页73第73页/共75页74旅行商问题的数学表达式niunjixnjinxnuunixnjxtsxcziijijjinjijniijnjijiijij, 3, 2, 0, 2, 1, 1, 02, 1, 2, 1, 1, 2, 1, 1. .min111,第74页/共75页75感谢您的观看！第75页/共75页