数学建模知识课件最优化

动态规划教学要求熟悉动态规划的概念；了解动态规划模型求解的算法设计特点了解掌握将线性规划化为动态规划模型的方法。动态规划方法介绍基本介绍见ppt文件例子1：背包问题有一个徒步旅行者，已知他能承受的旅行背包的重量不a（kg。设有n种物品可供他选择装入背包n种物品分别编号为1，2，…，n。其中i种物品每件的重量为a（kg，其使用价值（指一件第i种物品对旅行者来说所带来的好处的一种数量指标）为c（i＝1，2，…，n。问这位旅行者应如何选择携带这n种物品的件数，使得总价值最大？分析：这是一个组合最优化问题，易将此问题归结为一个线性整数规划问题。建立线性规划模型【建立线性规划模型】设旅行者选择携i种物品的xi，不难看出，背nmaxzciin aixiixi0且整，i1, 建立动态规划模型【建立动态规划模型】设把可装入背包的物品种类分为n个阶段。在第i阶段先装i种物品（i＝12n。在第i阶段开始时，把旅行者背包中允许装入前i种物品的总重量作为状态变量，设y。装入每种物品的件数xi（i＝1，2，…，n）为各阶段变量说明：设fk(y)等于当背包中允许装入物品的总重量不超过y和只允许装入前k种物品采用最优策略时的最大使用价值（k＝1，2，…，n则kf(y) kkaixi

cikik

(k1, ,并且当k＝n，y＝a时，有nf(a)nnaixi

ncii显然fn(a)也就是上述线性规划模型的最优解。把上式转化为递归方程： （属于前向算法）f1(y)

0xyai a1

f(y) c (yax y k a0xk ak例子2：运载问题【例子】0t货物编号123单位重量345单位价值456件问题分析：此装载问题类似与背包问题。此问题是一个典型的最优化问题，优化目标是卡车装载的总价值最大；装载当然越多越好，但又受到卡车本身的最大货运量的限制；所以此问题可以归结为如下的线性规划问题： f(x)4x15x26 3x14x25x3xi0且为整数其中xi（i＝1，2，3）分别表示装载第i种货物的件数。wi（i＝1，2，3：第i种货物的单位重量（单位：吨）ci（i＝123：i种货物的单位价值yk（k＝1，2，3）分别表示装载前i种货物的货运量fkyk)fk(yk)当背包中允许装入物品的总重量不超过和只允许装入前k种物品采用最优策略时的最大使用价值。（k＝1，2，3前向算法建立动态规划模型可归结为动态规划问题，此问题的递归方程为fk1(yk1)

0

k

{ck1xk1

fk(yk1wk1xk1k1 wk1初始条件：

f(y) 4x4y1 y 30x3

3状态转移方程：

1 yk具体如下：

yk1wk1xk1(k1, yf(y)max4x110xy11 13

f(y)max{5xf(y4x0xy 24

35

f2(y5x3要求得总价值最大，即求f3(10求解线性规划模型的Lindo程序 4x1+5x2+6x33x1+4x2+5x3<=x1x2x3x1x2x3GIN下面是部分输出窗口的内容：OBJECTIVEFUNCTION ---求解线性规划模型的Lingo程序max=4*x1+5*x2+6*x3;3*x1+4*x2+5*x3<=10;x1>=0;x2x3x1x2x3输出结果：Globaloptimalsolutionfoundat Objective --SlackorDual12345678求解动态规划模型的程function%动态规划模型求解程序示例%以【背包问题】为例（一维背包问题%P212~215，《组合数学》（修订本），电子科技大学globalM M=[345;%第一行：单位重量456];%第二行：单位价值valuegetmaxvalue(3,10);%下面是一个子函数（属于递归函数globalMvalue=-inf;ifk==1whichfix(y/M(1,1));f%d(%8.2f)=%8.2f=%d(单)*%d(fornum=0:fix(y/M(1,k))curvalue=M(2,k)*num+ifcurvalue>valuevalue=end%ifend%forf%d(%8.2f)=%8.2f=%d(单)*%d(策k,k,y,value,M(2,k),which,k-1,y-程序运行结在命令行输运行结果：1阶112.00=4(单)*3(决策8.00=4(单)*2(决策0.00=4(单)*0(决策2阶段113.00=5(单)*1(决策4.00=4(单)*1(决策10.00=4(单)*0(决策2阶段5.00=5(单)*1(决策10.00=4(单)*0(决策2阶段0.00=5(单)*0(决策3阶段13.00=6(单)*0(决策ans可知总价值最13，根据以上结果分析依次可得此时决策变量x3＝0，x2＝1，x1＝2；（结果）说明：可见对这个问题建立线性整数规划模型与动态规划模型求解结果一致。思考：自动给出？后向算法建立动态规划模型可归结为动态规划问题，此问题的递归方程为 yf(y)

max630x35

f(y)max{5xf(y4x0xy 24

1

f2(y3x1要求得总价值最大即求f1(10求解动态规划模型的程function%动态规划模型求解程序示例%%这是一个采用【后向算法】的动态规划建模方法globalM M=[345;%第一行：单位重量456];%第二行：单位价valuegetmaxvalue(1,10);%后向算法模型，这个就globalMvalueinf;ek=3;%结束阶段ifk==ek（只包含第一个决策变量which=策fornum=0:fix(y/M(1,k))curvalue=M(2,k)*num+ifcurvalue>valuevalue=end%ifend%forf%d(%8.2f)=%8.2f=%d(单)*%d(策程序运行结在命令行输入：运行结果：312.00=6(单)*2(决策6.00=6(单)*1(决策0.00=6(单)*0(决策第2阶段12.00=5(单)*0(决策36.00=6(单)*1(决策30.00=6(单)*0(决策第2阶段6.00=5(单)*0(决策3阶0.00=6(单)*0(决策3阶0.00=6(单)*0(决策第2阶段5.00=5(单)*1(决策30.00=6(单)*0(决策第2阶段0.00=5(单)*0(决策第1阶段13.00=4(单)*2(决策可知总价值最大为13，根据以上结果分析依次可得此时决策解结果一致。（^_^）：前向算法与后向算法结果一致求解方法结果对比分析思考：动态规划结果更加全面，得到全局最优解。动态规划模型的基本方程后向动态规划的基本方程：fk(xk) [vk(xk,uk)fk1(xk1ukUk(xkkn,n ,或者可以表示为f(x)v(x,u*) (T(x,u* k kn,n ,状态转移方程：xk初始条件是：

Tk(xk,uk),xkfn1(xn1)(xn1前向动态规划基本方程：fk1(xk1) [vk1(xk1,uk1)fk(xkuk1Uk1(xk1k1, ,n1,状态转移方程：xkTk1(xk1,uk1),xkXkk1, ,初始条件是：f1(x1)(x1例3机器负荷分配问题（先练习某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷情况下，设年初投入的完好机器u，年终的完好机器数为0.7u，称0.7为机器的完好率。记年产量为p＝8u。在低负荷下设年初投入的完好机器数为v，完好率为0.9，年产量为q＝5v。假设开始时拥1000台完好机器。要制定五年计划，每年年初决定重新分配在两种负荷下生产的完好机器数，使五年内的总产量最大。(动态规划附加例子讲解动态规划务必考虑状态的无后效性。参考书《动态规划》，理工大学变量说明xk：第k年年初的完好机器数uk：第k年初投入高负荷生产的完好机器数。vkk年初投入低负荷生产的完好机器vkxkuk。fk(xk)k年初投入xk的完好机器数后k年到第5年建立后向动态规划模型fkxk实际上，则

max8uk5vkfk1xk1,k1,2,3,40uk +0.9(xk-=0.9xk-0.2fxmax8u5v 0.9x0.2u,k 0uk k k＝5

fxmax8u55v5 0u5max8u55x5u50u5此时u*x 求精确解：手工推算（解析求解略，详见计算机求解：求精确解可能很费时间.穷举可以得到全局最优解。难点：.解空间较大；故可考虑近似求解；.p10：得f1100023700，年初投入高负荷生成的机器数依次为：0，0，810，567，397.（前2年全部投入低负荷生产，后三年年初全部完好机器投入高负荷生产）.5年末完好机器数为0.7397278。结果分析计算机求解的结果不如手工推导的结果由于计算机采用了近似求解策略，所以得不到全局最优解。如果不近似，则计算机求解得时间复杂度很高，运行时间难以预料。进一步问题如果要考虑第五年后的完整机器数，则怎样决策？例4整数规划转化为动态规划用动态规划求解下面的最优化问题min3x25x3x23x2x27x 2x13x22x316,x1,x2,x3x1x2x3均为整数建立后向动态规划模型：2x13x22x3S1，模型归结为求fkSk其

0xk

gkxkfk1Sk1,k1,2,3gx3x25 gx3x23 3g3x32x273实际上，

Sk1SkCkxk,k其中C12,C23,C32则fkSk max(0,Sk)Ck

gkxkfk1SkCkxk,kk＝3时fS 2x27x max(0,S3)C3 Lingo求解程序：min3*x1*x1-5*x1+3*x2*x2-3*x2+2*x3*x3-Lingo求解结果输出： 2Vars= 3Negervars=Nonlinear Nonlinear 7Constraint No.<:0No.=:0No.>:1,Single Optimalsolutionfoundat Objective Branch ReducedSlackorSurplusDual 然后回溯。留作思考题：如何转换为动态规划模型？求解程序function%《动态规划》，理工大学 P54,1-%globalans_mat1以下矩阵用于最优列以便提供功能得到最策略（）ans_mat1=zeros(1,5);%y>0实际上满足最y为正整数% 阶段状态 决策值优化值下阶段状态globalans_mat1ans_mat2a=[23ifx=ceil(y/a(k));%max(0,ceil(y/a(k)));ifx<=2,obj=2*x^2-disp(sprintf('第%2d阶段ify>0end%iflow=opt_x=0;fori=0:50,x=i;switchk,case1,cur_obj=3*x^2-5*x+casecur_obj=3*x^2-3*x+casecur_obj=2*x^2-7*x+