二次_动态规划-图论

§1二次规划模型数学模型：ubxlbbeqxAeqbxAxfHxxTTx21min其中H为二次型矩阵，A、Aeq分别为不等式约束与等式约束系数矩阵，f,b,beq,lb,ub,x为向量。求解二次规划问题函数为quadprog()调用格式：X=quadprog(H,f,A,b)X=quadprog(H,f,A,b,Aeq,beq)X=quadprog(H,f,A,b,Aeq,beq,lb,ub)X=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)X=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=quadprog(…)[x,fval,exitflag]=quadprog(…)[x,fval,exitflag,output]=quadprog(…)[x,fval,exitflag,output,lambda]=quadprog(…)说明：输入参数中，x0为初始点；若无等式约束或无不等式约束，就将相应的矩阵和向量设置为空；options为指定优化参数。输出参数中，x是返回最优解；fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛；output是返回包含优化信息的结构。Lambda是返回解x入包含拉格朗日乘子的参数。例1：求解：二次规划问题minf(x)=x1-3x2+3x12+4x22-2x1x2s.t2x1+x2≤2-x1+4x2≤3程序：f=[1;-3];H=[6-2;-28];A=[21;-14];b=[2;3];[X,fval,exitflag]=quadprog(H,f,A,b)结果：X=-0.04550.3636fval=-0.5682exitflag=1例2：求解：二次规划问题minx12+2x22-2x1x2-4x1-12x2s.tx1+x2≤2-x1+2x2≤22x1+x2≤30≤x1,0≤x2程序：H=[2-2;-24];f=[-4;-12];A=[11;-12;21];b=[2;2;3];lb=zeros(2,1);[x,fval,exitflag]=quadprog(H,f,A,b,[],[],lb)结果：x=0.66671.3333fval=-16.4444exitflag=1练习1求解下面二次规划问题21212221x6x2xxxx21)x(fminsub.to2xx212x2x213xx22121x0,x0解：xfxHx21)x(f则2111H，62f，21xxx在MATLAB中实现如下：H=[1-1;-12];f=[-2;-6];A=[11;-12;21];b=[2;2;3];lb=zeros(2,1);[x,fval,exitflag,output,lambda]=quadprog(H,f,A,b,[],[],lb)结果为：x=%最优解0.66671.3333fval=%最优值-8.2222exitflag=%收敛1output=iterations:3algorithm:'medium-scale:active-set'firstorderopt:[]cgiterations:[]lambda=lower:[2x1double]upper:[2x1double]eqlin:[0x1double]ineqlin:[3x1double]lambda.ineqlinans=3.11110.44440lambda.lowerans=00说明第1、2个约束条件有效，其余无效。练习2求二次规划的最优解maxf(x1,x2)=x1x2+3sub.tox1+x2-2=0解：化成标准形式：3xx)0,0(xx0110)xx(213xx)xx(fmin2121212121sub.tox1+x2=2在Matlab中实现如下：H=[0,-1;-1,0];f=[0;0];Aeq=[11];beq=2;[x,fval,exitflag,output,lambda]=quadprog(H,f,[],[],Aeq,beq)结果为：x=1.00001.0000fval=-1.0000exitflag=1output=firstorderopt:0iterations:1cgiterations:1algorithm:[1x58char]lambda=eqlin:1.0000ineqlin:[]lower:[]upper:[]§2最大最小化模型基本思想：在对策论中，我们常遇到这样的问题：在最不利的条件下，寻求最有利的策略。在实际问题中也有许多求最大值的最小化问题。例如急救中心选址问题就是要规划其到所有地点最大距离的最小值。在投资规划中要确定最大风险的最低限度等等。为此，对每个x∈R,我们先求诸目标值fi(x)的最大值，然后再求这些最大值中的最小值。最大最小化问题的数学模型：ubxlbbeqxAeqbxAxceqxctsxFiFxi0)(0)(maxmin求解最大最小化问题的函数为fminimax调用格式：x=fminimax(F,x0,)x=fminimax(F,x0,,A,b)x=fminimax(F,x0,,A,b,Aeq,beq)x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub)x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon)x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon,options)x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2)[x,fval]=fminimax(…)[x,fval,maxfval]=fminimax(…)[x,fval,maxfval,exitflag,output]=fminimax(…)[x,fval,maxfval,exitflag,output,lambda]=fminimax(…)说明：F为目标函数；x0为初值；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。x返回最优解；fval返回解x处的目标函数值；maxfval返回解x处的最大函数值；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。例1求解下列最大最小值问题：201294)(6)(745)(351223)()](),(),(),(max[min2122214221322121222114321xxxxxfxxxfxxxxfxxxxfxfxfxfxf其中首先编辑M文件ff14.mfunctionf=ff14(x)f(1)=3*x(1)^2+2*x(2)^2-12*x(1)+35;f(2)=5*x(1)*x(2)-4*x(2)+7;f(3)=x(1)^2+6*x(2);f(4)=4*x(1)^2+9*x(2)^2-12*x(1)*x(2)+20;取初值x0=(1,1)调用优化函数x0=[11];[x,fval,maxfval]=fminimax(@ff14,x0)结果：x=1.76370.5317fval=23.73319.56216.301023.7331例2：选址问题设某城市有某种物品的10个需求点，第i个需求点Pi的坐标为(ai,bi),道路网与坐标轴平行，彼此正交。现打算建一个该物品的供应中心，且由于受到城市某些条件的限制，该供应中心只能设在x界于[5,8]，y界于[5.8]的范围之内。问该中心应建在何处为好?P点的坐标为：ai1435912620178bi2108181451089建立数学模型：设供应中心的位置为(x,y)，要求它到最远需求点的距离尽可能小，此处采用沿道路行走计算距离，可知每个用户点Pi到该中心的距离为|x-ai|+|y-bi|，于是有：8585maxmin,yyxxtsbxaxiiiyx编程：首先编辑M文件：ff15.mfunctionf=ff15(x)a=[1435912620178];b=[2108181451089];f(1)=abs(x(1)-a(1))+abs(x(2)-b(1));f(2)=abs(x(1)-a(2))+abs(x(2)-b(2));f(3)=abs(x(1)-a(3))+abs(x(2)-b(3));f(4)=abs(x(1)-a(4))+abs(x(2)-b(4));f(5)=abs(x(1)-a(5))+abs(x(2)-b(5));f(6)=abs(x(1)-a(6))+abs(x(2)-b(6));f(7)=abs(x(1)-a(7))+abs(x(2)-b(7));f(8)=abs(x(1)-a(8))+abs(x(2)-b(8));f(9)=abs(x(1)-a(9))+abs(x(2)-b(9));f(10)=abs(x(1)-a(10))+abs(x(2)-b(10));然后用以下程序计算：x0=[6;6];AA=[-10100-101];bb=[-5;8;-5;8];[x,fval]=fminimax(@ff15,x0,AA,bb)结果：x=88fval=1365138851491即：在坐标为(8,8)处设置供应中心可以使该点到各需求点的最大距离最小，最小的最大距离为14单位。练习求下列函数最大值的最小化问题])x(f,)x(f,)x(f,)x(f,)x(f[54321其中：304x40x48xx2)x(f212221122222x3x)x(f18x3x)x(f213214xx)x(f8xx)x(f215解：先建立目标函数文件，并保存为ff16.m：functionf=ff16(x)f(1)=2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304;f(2)=-x(1)^2-3*x(2)^2;f(3)=x(1)+3*x(2)-18;f(4)=-x(1)-x(2);f(5)=x(1)+x(2)-8;然后，在命令窗口键入命令：x0=[0.1;0.1];%初始值[x,fval,maxf]=fminimax(@ff16,x0)结果为：x=4.00004.0000fval=0.0000-64.0000-2.0000-8.0000-0.0000maxf=2.2737e-013§3动态规划模型如图所示，给定一个线路网络，两点之间连线上的数字表示两点间距离，试求一条从A到E的路线，使总距离为最短。Mattlab求解：首先利用Excel建立工作表edge存储图的上三角阵。其中edge=999995299999999999999999999999999999999999999999999937999999999999999999999999999999999999999963999999999999999999999999999999999999999999999699999999999999999999999999999999999999993899999999999999999999999999999999999999991999999999999999999999999999999999999999999999399999999999999999999999999999999999999997999999999999999999999999999999999999999999999,然后在Matlab调入以上数据。同时将调用自编的动态规划AB1B