大学数学建模电子教案.ppt

《大学数学建模电子教案.ppt》由会员分享，可在线阅读，更多相关《大学数学建模电子教案.ppt（185页珍藏版）》请在三一文库上搜索。

1、数学建模电子教案,重庆邮电大学 数理学院 沈世云,第二篇 规划论模型,第二章 线性规划 第三章 整数规划 第四章 无约束非线性规划 第五章 约束非线性规划 第六章 规划模型的MATLAB解法 第七章 动态规划,第五章 约束非线性规划,5.1 最优性条件,5.2 非线性规划案例,本章主要考察带有约束条件的非线性规划问题。,称问题(MP)为数学规划（Mathematical Programming）。,（MP）,称 为不等式约束， 为等式约束。,称集合 为问题(MP)的可行域。,若问题(MP)中的 是凸函数， 是线性函数，则称问题(MP)为凸规划。,5.1.1 不等式约束问题的最优性条件,5.1

2、最优性条件,定义5.1.1 设 ，若对某个 有 ，称 为点 处的起作用约束，也称为有效约束，积极约束(Active Constraint)。,记 为起作用约束下标集，简记为 。,5.1 最优性条件,若 ，则称 为点 处的不起作用约束。其几何意义如图所示。在 处， 是起作用约束， 是不起作用约束。在 处 均是不起作用约束。,5.1 最优性条件,例5.1 用图解法求下列问题的最优解，指出最优解处的起作用约束及目标函数的最优值。,(1),(2),解： (1)原问题可以化为：,5.1 最优性条件,最优解 ，最优值 。 在 处是起作用约束。,如图所示。,5.1 最优性条件,(2)原问题可化为,最优解 ，

3、最优值 。 在 处是起作用约束。,5.1 最优性条件,定理5.1.1（Fritz-John必要条件） 设 在 处可微， 在 处连续，若 是不等式约束问题(1)的最优解，则存在不全为零的数 使,5.1 最优性条件,解：在 处 是起作用约束，即,且,取 ，便有Fritz-John条件成立。,5.1 最优性条件,在Fritz-John必要条件中，若 则Fritz-John条件中就没有目标函数的信息了，这样的Fritz-John条件就没有多大的价值，为了保证 ，需对约束条件加以适当的限制条件，称之为约束规格（Constraint qualification）。在非线性规划的研究中，有着各种不同的约束规

4、格，如果增加起作用约束的梯度向量线性无关的约束规格，就得出著名Kuhn-Tucker条件。它是Kuhn和Tucker在1951年提出的，简称为K-T条件。,5.1 最优性条件,定理5.1.2（Kuhn-Tucker必要条件） 设 在 处可微， 在处连续， 线性无关，若 是不等式约束问题(5.1.1)的局部最优解，则存在 使,5.1 最优性条件,解：经验证 是可行点,由于在 处只有 是起作用约束，此时有,5.1 最优性条件,在 处， 均是起作用约束，且 是线性无关，由,有方程组,解之有,故 是K-T点。,5.1 最优性条件,证明：由定理的条件，显然可行域是凸集，由是凸函数，再由定理1.3.2，有

5、,又由K-T条件，存在 ，使,5.1 最优性条件,由 是凸函数有,即,即 是（5.1.1）的全局最优解。,5.1 最优性条件,5.1.2 等式约束问题的最优性条件,(5.1.1)的结论可平移到(5.1.3)中来，并得到(5.1.2)的相应结论。(5.1.2)也可采用Lagrange乘数法来求解。,5.1 最优性条件,定义5.1.3 对等式约束问题(5.1.2)，设存在数 称,为等式约束问题(5.1.2)的Lagrange函数。其中 称为Lagrange乘子， ；记,5.1 最优性条件,称 为的Jacobi矩阵。,5.1 最优性条件,定义5.1.4 若 满足： ,则 称为等式约束问题(5.3)的

6、Lagrange点。,定理5.1.4（必要条件） 设等式约束问题(5.1.2)中 在 处的某个邻域内可微， 的Jacobi矩阵在 处的秩为 ，若 是(5.1.2)的局部最优解，则存在 使,5.1 最优性条件,定理5.1.5（充分条件） 设等式约束问题(5.1.2)中 二阶连续可微，若存在 使得,其中 ; 则 是等式约束问题(5.1.2)的严格局部最优解。,5.1 最优性条件,例5.1.4 求解,解：原问题可化为：,有,5.1 最优性条件,令 有,设向量 满足 , 则有,而此时,由定理4.5知是问题的严格局部最优解。,4.1 最优性条件,5.1.3 混合约束问题的最优性条件,记,5.1 最优性条

7、件,5.1 最优性条件,在定理4.1.6中，若还有条件， 在点 处可微，则Fritz-John条件可改写为,4.1 最优性条件,定理5.1.7 （Kuhn-Tucker必要条件） 设混合约束问题中的 在点 处可微， 在点 处连续， 在点 处连续可微，且 线性无关，若 是 的局部最优解，则存在 使,5.1 最优性条件,在定理5.1.7中若还有条件 在点 处可微，则K-T条件可改写为：,5.1 最优性条件,定理5.1.8（充分条件） 设混合约束问题(5.1.4)中的 在点 处可微，若 满足(5.1.4)的K-T条件，并且 是凸函数， 是线性函数，则 是(5.1.4)的全局最优解。,5.1 最优性条

8、件,例4.5 求解,解：,4.1 最优性条件,由K-T条件有：,5.1 最优性条件,解此方程组有解,由于 是凸函数， 是线性函数，而且 是K-T点，故由定理4.1.8知 是问题的全局最优解。,5.1 最优性条件,5.2 非线性规划建模实例,飞行管理问题,1、问题提出,在约10000m高空的某边长为160km的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假

9、定条件如下：（1）不碰撞的标准为任意两架飞机的距离大于8km；（2）飞机飞行方向角调整的幅度不应超过 ；（3）所有飞机飞行速度均为800km每小时；（4）进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在60km以上；（5）最多需考虑6架飞机；（6）不必考虑飞机立刻此区域后的状况。,5、计算结果,第六章 规划模型的 MATLAB求解,6.1 用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式： 存在，则令A= ，b= .,命令：1 x=linprog（c，A，b

10、，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0）,注意：1 若没有等式约束: , 则令Aeq= , beq= . 2其中X0表示初始点,4、命令：x,fval=linprog() 返回最优解及处的目标函数值fval.,解 编写M文件xxgh1.m如下： c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;9

11、00; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh1),解: 编写M文件xxgh2.m如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh2),例3,编写M文件xxgh3.m如下: f = 13 9 10 11 12 8; A = 0.4 1.1 1 0 0 0 0 0 0 0

12、.5 1.2 1.3; b = 800; 900; Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1; beq=400 600 500; vlb = zeros(6,1); vub=; x,fval = linprog(f,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh3),结果: x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为138

13、00。,6.2 用Matlab解无约束优化问题,其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,常用格式如下： （1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）x，fval= fminbnd（.） （4）x，fval，exitflag= fminbnd（.） （5）x，fval，exitflag，output= fminbnd（.）,To Matlab(wliti1),主程序为wliti

14、1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作图语句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8),例2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解,先编写M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).2*x;,主程序为wliti2.m: x,fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval,运算结果为: xma

15、x = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.,To Matlab(wliti2),命令格式为: （1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ） （2）x= fminunc（fun,X0 ，options）； 或x=fminsearch（fun,X0 ，options） （3）x，fval= fminunc（.）； 或x，fval= fminsearch（.） （4）x，fval，exitflag= fminunc（.）； 或x，fval，exitflag= fminsearch

16、（5）x，fval，exitflag，output= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.）,2、多元函数无约束优化问题,标准型为：min F(X),3 fminunc为中型优化算法的步长一维搜索提供了两种算法， 由options中参数LineSearchType控制： LineSearchType=quadcubic(缺省值)，混合的二次和三 次多项式插值； LineSearchType=cubicpoly，三次多项式插,使用fminunc和 fminsearch可能会得到局部最优解.,说明:,fminsearch是用单纯形法寻优

17、. fminunc的算法见以下几点说明：,1 fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制： LargeScale=on(默认值),使用大型算法 LargeScale=off(默认值),使用中型算法,2 fminunc为中型优化算法的搜索方向提供了4种算法，由 options中的参数HessUpdate控制： HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式； HessUpdate=dfp，拟牛顿法的DFP公式； HessUpdate=steepdesc，最速下降法,例3 min f(x)=(4x12+2x22+4x1

18、x2+2x2+1)*exp(x1),To Matlab(wliti3),1、编写M-文件 fun1.m: function f = fun1 (x) f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); 2、输入M文件wliti3.m如下: x0=-1, 1; x=fminunc(fun1,x0) y=fun1(x),3、运行结果: x= 0.5000 -1.0000 y = 1.3028e-10,To Matlab (wliti31),To Matlab (wliti32),1. 为获得直观认识，先画出Rosenbrock 函数的三维图形,

19、 输入以下命令： x,y=meshgrid(-2:0.1:2,-1:0.1:3); z=100*(y-x.2).2+(1-x).2; mesh(x,y,z),2. 画出Rosenbrock 函数的等高线图,输入命令： contour(x,y,z,20) hold on plot(-1.2,2, o ); text(-1.2,2,start point) plot(1,1,o) text(1,1,solution),3.用fminsearch函数求解,To Matlab(wliti41),输入命令: f=100*(x(2)-x(1)2)2+(1-x(1)2; x,fval,exitflag,ou

20、tput=fminsearch(f, -1.2 2),运行结果: x =1.0000 1.0000 fval =1.9151e-010 exitflag = 1 output = iterations: 108 funcCount: 202 algorithm: Nelder-Mead simplex direct search,用MATLAB软件求解,其输入格式如下: 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C

21、,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exitflag,output=quaprog(.);,1、二次规划,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,MATLAB（youh1）,1、写成标准形式：,2、 输入命令： H=1 -1; -1 2; c=-2

22、 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、运算结果为： x =0.6667 1.3333 z = -8.2222,s.t.,1. 首先建立M文件fun.m,定义目标函数F（X）: function f=fun(X); f=F(X);,2、一般非线性规划,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：,3. 建立主程序.非线性规划求解的函数是fminco

23、n,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon) (5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,out

24、put= fmincon(.),输出极值点,M文件,迭代的初值,参数说明,变量上下限,注意： 1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。 2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。 3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,1、写成标准形式： s.t.,2x1+3x2

25、 6 s.t x1+4x2 5 x1,x2 0,例2,2、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(youh2),3、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、运算结果为： x = 0.7647 1.0588 fval = -2.0294,1先建立M文件 fun4.m,定义目标函数: fun

26、ction f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,例3,2再建立M文件mycon.m定义非线性约束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,3主程序youh3.m为: x0=-1;1; A=;b=; Aeq=1 1;beq=0; vlb=;vub=; x,fval=fmincon(fun4,x0,A,b,Ae

27、q,beq,vlb,vub,mycon),MATLAB(youh3),3. 运算结果为： x = -1.2250 1.2250 fval = 1.8951,例4,1先建立M-文件fun.m定义目标函数: function f=fun(x); f=-2*x(1)-x(2);,2再建立M文件my2.m定义非线性约束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,3. 主程序fxx.m为: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag =fmincon(fun,x0,VLB,VUB,my2

28、),MATLAB(fxx(fun),4. 运算结果为: x = 4.0000 3.0000 fval =-11.0000 exitflag = 1 output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: ,返回,牛顿迭代法,例1 用牛顿迭代法求方程 在x=0.5附近的近似根，误差不超过 。 牛顿迭代法的迭代函数为,牛顿迭代法,相应的MATLAB代码为(nddd.m) clear; x=0.5; for i=1:3 x=x-(x3+x2+x-1)/(3*x

29、2+2*x+1) End 可算的迭代数列的前3项0.5455，0.5437，0.5437。经三次迭代，就大大超过了精度要求。,牛顿迭代法,相应的MATLAB代码为 (nddd1.m) clear; x= ; x(1)=0.9; for i=1:6 x(i+1)=x(i)-(x(i)3+x(i)2+x(i)-1)/(3*x(i)2+2*x(i)+1); if abs(x(i+1)-x(i)0.0001 x(i+1) break end end,第7章 动态规划,(Chapter7 Dynamic Programming),7.1 动态规划的基本概念,7.3 动态规划的应用举例,7.2 动态规划的

30、最优性原理与数学模型,1951年美国数学家R. Bellman等人创建了动态规划。,基本思想：将一个复杂问题分解成若干个阶段，每一个阶段作为一个小问题进行处理，从而决定整个过程的决策，,求解过程分两步：先按整体最优化递序地求出各个可能状态的最优化决策，再顺序地求出整个问题的最优策略和最优路线。,7.1 动态规划的基本概念,例7.1 最短路径问题,图7.1表示从A到E之间各点的距离。求A到E的最短路径。,7.1.1 引例,如果用穷举法，A到E：332=18条路径，,求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。,计算每条路径

31、的长度，总共 418=72次加法计算； 对18条路径的长度比较，总共 181=17次比较。,如果从A到C的站点有k个，总共3k-12条路径， 求最短路总共(k+1)3k-12次加法，3k-12-1次比较。,当k值增加，需要进行的加法和比较次数将迅速增加。 例如当k=10时，加法次数为433026次，比较39365次。,记从Bi (i=1, 2, 3) 到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可表示：,计算S(B1)又可归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci) (i=1, 2, 3)，而求S(Ci)又可以归结为求S(D1)和S(D

32、2)这两个子问题。,从图7.1看出，在这个问题中，S(D1)和S(D2)是已知的，它们分别是： S(D1)=5，S(D2)=2 从这两个值开始，逆向递归计算S(A)的值。,计算过程如下：,S(C1)=8 且如果到达C1，则下一站应到达D1；,S(C2)=7 且如果到达C2，则下一站应到达D2；,S(C3)=12 且如果到达C3，则下一站应到达D2；,计算S(Bi)：,S(B1)=20 且如果到达B1，则下一站应到达C1；,计算S(A)：,从A到E的最短路径为： A B2 C1 D1 E,S(B2)=14 且如果到达B2，则下一站应到达C1；,S(B3)=19 且如果到达B3，则下一站应到达C2

33、；,计算过程及结果用下图表示。从图中任一点到E的最短路径。仅用了18次加法，11次比较。,7.1.2 动态规划的基本概念,1阶段,2状态和状态变量,把所要处理的问题合理地划分成若干个相互联系的阶段，通常用 表示阶段变量。,如例7.1中，第3阶段集合可记为,每一个阶段的起点，称为该阶段的状态，描述过程状态的变量，称为状态变量，它可以用一个数、一组数或一个向量来描述。常用 表示第 阶段的某一状态。第 阶段状态的集合,3决策和决策变量,决策就是在某一阶段给定初始状态的情况下，从该状态演变到下一阶段某状态的选择，即确定系统过程发展的方案。,用一个变量来描述决策，称这个变量为决策变量。,设 表示第 阶段

34、初始状态为 的决策变量。 表示初始状态为 的允许决策集合，有,4策略和子策略,由每段的决策 组成的整个过程的决策变量序列称为策略，记为 ，即,从阶段 到阶段 依次进行的阶段决策构成的决策序列称为 子策略，记为 ，即,时的 子策略就是策略。,如例7.1中，选取路径 就是一个子策略。,从允许策略集中选出的具有最佳效果的策略称为最优策略。,5状态转移方程,系统在阶段 处于状态 ，执行决策 的结果是系统状态的转移，即由阶段 的状态 转移到阶段 的状态 适用于动态规划方法求解的是一类具有无后效性的多段决策过程。无后效性又称马尔科夫性，指系统从某个阶段往后的发展，完全由本阶段所处的状态及其往后的决策决定，

35、与系统以前的状态及决策无关，对于具有无后效性的多阶段决策过程，系统由阶段 到阶段 的状态转移方程为,(7.1.3),即 只与 有关，而与前面状态无关。,称为变换函数或算子。,6指标函数和最优指标函数,在多阶段决策中，可用一个数量指标来衡量每一个阶段决策的效果，这个数量指标就是指标函数，为该阶段状态变量及其以后各阶段的决策变量的函数，设为 ，即,最常见的指标函数取各阶段效果之和的形式，即,(7.1.4),指标函数 的最优值，称为相应的最优指标函数，记为,式中opt是最优化之意，根据问题的要求取min或max。,7.2 动态规划的最优性原理与数学模型,7.2.1 最优性原理,多阶段决策过程的特点是

36、每个阶段都要进行决策， 段决策过程的策略是由 个相继进行的阶段决策构成的决策序列。由于前一阶段的终止状态又是后一阶段的初始状态，因此，确定阶段最优决策不能只从本阶段的效应出发。必须通盘考虑，整体规划。,R. Bellman指出：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”。,7.2.2 动态规划的数学模型,设在阶段 的状态 执行了任意选定的决策 后的状态是 。这时 后部子过程就缩小为 后部子过程。根据最优性原理，对 后部子过程采用最优策略，由于无后效性， 后部子过程的目标函数值为,就某个 而言必有,根据条件最优

37、目标函数的定义有,一般表示为,(7.2.1),其中 ，（7.2.1）称为动态规划基本方程，亦称Bellman方程。,当目标函数为阶段效应求和形式时，动态规划的基本方程也可以直接由条件最优目标函数的定义导出，即,其中,动态规划基本方程是最优性原理的体现，即不论初始状态 和初始决策 是什么，余下的决策对于由初始状态及初始决策造成的状态 ，必须构成最优策略，由之得到相应的条件最优目标函数值 。,练习1：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6

38、,6,4,最优路线为：A B1 C2 D1 E2 F2 G 路长18,求从A到G的最短路径,3,k=5，出发点E1、E2、E3,k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3,7 5 9,u5(E2)=F2,u6(F2)=G,最优策略,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,求从A到E的最短路径,路线为AB2C1 D1 E ，最短路径为19,A,B2,B1,B3,C1,C3,D1,D

39、2,E,C2,5,2,14,1,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,练习2：,1,7.3 动态规划应用举例,1. 投资分配问题 2. 背包问题 3. 机器负荷分配问题 4. 设备更新问题,现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元） ；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题是如何确定各工厂的资金数，使得总的利润为最大。,据此，有下式：,一、投资分配问题,令：fk(x) = 以数量为x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求

40、 fn(a) 的问题。,当 k=1 时， f1(x) = g1(x) （因为只给一个工厂）,当1kn 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0y x ），此时还剩 x y（万元）的资金需要分配给前 k-1 个工厂,如果采取最优策略，则得到的最大利润为fk1(xy) ,因此总的利润为： gk(y) fk1(xy),如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，x。上式可变为：,所以，根据动态规划的最优化原理，有下式：,例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。,解：依据题意

41、，是要求 f4(60) 。,按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) g1(x)，得到下表,第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。,最优策略为（40，20），此时最大利润为120万元。,同理可求得其它 f2(x) 的值。,最优策略为（30，20），此时最大利润为105万元。,最优策略为（20，20），此时最大利润为90万元。,最优策略为（20，10），此时最大利润为70万元。,最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。,f2(0) 0。最优策略为（0，0），最大利润为0万元。 得到下表,最优

42、策略为（20，0），此时最大利润为50万元。,第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。,最优策略为（20，10，30），最大利润为155万元。,同理可求得其它 f3(x) 的值。得到下表,第四阶段：求 f4(60)。即问题的最优策略。,最优策略为（20，0，30，10），最大利润为160万元。,练习： 求投资分配问题得最优策略，其中a50 万元，其余资料如表所示。,例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。,x1=2

43、，x2=1，x3=1，f3(4)=47,有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,二、背包问题,设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：,用动态规划方法求解，令 fx(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0， k 1,2, , n 。所以问题就是求 fn(a),其递推关系式为：,当

44、 k=1 时，有：,例题：求下面背包问题的最优解,解：a5 ，问题是求 f3(5),所以，最优解为 X（1 . 1 . 0），最优值为 Z = 13。,练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？,最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260,练习2：求下列问题的最优解,X=(2. 1. 0) 最优值为 Z = 13,三. 机器负荷分配问题 某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。,构造动态规划模型如下：,阶段 ：运行年份（ ），其中 表示第一年初，依次类推； 表示第五年末（即第六年初）；,状态变量 ：第 年初完好的机器数（ ），其中 表示第五年末（即第六年初）的完好机器数；,决策变量 ：第 年投入高负荷运行的机器数；,状态转移方程：,决