二次_动态规划-图论

1、§1 二次规划模型数学模型：其中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= qua

2、dprog()x,fval,exitflag,output= quadprog()x,fval,exitflag,output,lambda= quadprog()说明：输入参数中，x0为初始点；若无等式约束或无不等式约束，就将相应的矩阵和向量设置为空；options为指定优化参数。输出参数中，x是返回最优解；fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛；output是返回包含优化信息的结构。Lambda是返回解x入包含拉格朗日乘子的参数。例1：求解：二次规划问题min f(x)= x1-3x2+3x12+4x22-2x1x2s.t 2x1+x22 -x1+4x23程

3、序：f=1;-3;H=6 -2;-2 8;A=2 1;-1 4;b=2;3;X,fval,exitflag=quadprog(H,f,A,b)结果：X = -0.0455 0.3636fval = -0.5682exitflag = 1例2：求解：二次规划问题min x12+2x22-2x1x2-4x1-12x2s.t x1+x22 -x1+2x22 2x1+x230x1, 0x2程序：H=2 -2;-2 4;f=-4;-12;A=1 1;-1 2;2 1;b=2;2;3;lb=zeros(2,1);x,fval,exitflag=quadprog(H,f,A,b,lb)结果：x = 0.66

4、67 1.3333fval = -16.4444exitflag = 1练习1 求解下面二次规划问题sub.to 解：则，在MATLAB中实现如下：>>H = 1 -1; -1 2 ;>>f = -2; -6;>>A = 1 1; -1 2; 2 1;>>b = 2; 2; 3;>>lb = zeros(2,1);>>x,fval,exitflag,output,lambda = quadprog(H,f,A,b, , ,lb)结果为：x = %最优解 0.6667 1.3333fval = %最优值 -8.2222exi

5、tflag = %收敛 1output = iterations: 3 algorithm: 'medium-scale: active-set' firstorderopt: cgiterations: lambda = lower: 2x1 double upper: 2x1 double eqlin: 0x1 double ineqlin: 3x1 double>> lambda.ineqlinans = 3.1111 0.4444 0>> lambda.lowerans = 0 0说明 第1、2个约束条件有效，其余无效。练习2 求二次规划的最优解

6、max f (x1, x2)=x1x2+3sub.to x1+x2-2=0解：化成标准形式： sub.to x1+x2=2在Matlab中实现如下：>>H=0,-1;-1,0;>>f=0;0;>>Aeq=1 1;>>beq=2;>>x,fval,exitflag,output,lambda = quadprog(H,f, , ,Aeq,beq)结果为：x = 1.0000 1.0000fval = -1.0000exitflag = 1output = firstorderopt: 0 iterations: 1 cgiteratio

7、ns: 1 algorithm: 1x58 charlambda = eqlin: 1.0000 ineqlin: lower: upper: §2最大最小化模型基本思想：在对策论中，我们常遇到这样的问题：在最不利的条件下，寻求最有利的策略。在实际问题中也有许多求最大值的最小化问题。例如急救中心选址问题就是要规划其到所有地点最大距离的最小值。在投资规划中要确定最大风险的最低限度等等。为此，对每个xR,我们先求诸目标值fi(x)的最大值，然后再求这些最大值中的最小值。最大最小化问题的数学模型：求解最大最小化问题的函数为 fminimax调用格式：x=fminimax(F,x0,)x=f

8、minimax(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=

9、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 求解下列最大最小值问题： 首先

10、编辑M文件ff14.mfunction f=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=1 1;x,fval,maxfval=fminimax(ff14,x0)结果：x = 1.7637 0.5317fval = 23.7331 9.5621 6.3010 23.7331例2：选址问题设某城市有某种物品的10个需求点，第i个需求点Pi的坐标为(ai,bi),道路

11、网与坐标轴平行，彼此正交。现打算建一个该物品的供应中心，且由于受到城市某些条件的限制，该供应中心只能设在x界于5,8，y界于5.8的范围之内。问该中心应建在何处为好?P点的坐标为：ai1435912620178bi2108181451089建立数学模型：设供应中心的位置为(x,y)，要求它到最远需求点的距离尽可能小，此处采用沿道路行走计算距离，可知每个用户点Pi到该中心的距离为 |x-ai|+|y-bi|，于是有： 编程：首先编辑M文件：ff15.mfunction f = ff15(x)a=1 4 3 5 9 12 6 20 17 8;b=2 10 8 18 1 4 5 10 8 9;f(1

12、) = 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)+ab

13、s(x(2)-b(9);f(10) = abs(x(1)-a(10)+abs(x(2)-b(10);然后 用以下程序计算 ：x0 = 6; 6; AA=-1 0 1 0 0 -1 0 1;bb=-5;8;-5;8;x,fval = fminimax(ff15,x0,AA,bb)结果：x = 8 8fval = 13 6 5 13 8 8 5 14 9 1即：在坐标为(8,8)处设置供应中心可以使该点到各需求点的最大距离最小，最小的最大距离为14单位。练习 求下列函数最大值的最小化问题其中：解：先建立目标函数文件，并保存为ff16.m：function f = ff16(x)f(1)= 2*x(

14、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.0000 4.0000fval = 0.0000 -64.0000 -2.0000 -8.0000 -0.0000 maxf = 2.2737e-013§3动态规划模型AB1B2C1C2C3D1D

15、2E536337263871如图所示，给定一个线路网络，两点之间连线上的数字表示两点间距离，试求一条从A到E的路线，使总距离为最短。Mattlab求解：首先利用Excel建立工作表edge存储图的上三角阵。其中edge=9999952999999999999999999999999999999999999999999999379999999999999999999999999999999999999999639999999999999999999999999999999999999999999996999999999999999999999999999999999999999938999999

16、99999999999999999999999999999999991999999999999999999999999999999999999999999999399999999999999999999999999999999999999997999999999999999999999999999999999999999999999,然后在Matlab调入以上数据。同时将调用自编的动态规划程序函数“dongtaigh.m”，即在Matlab命令窗口输入n=9;distance,path=dongtaigh(edge,n),回车后则在窗口显示出路径Path和距离distance§4最小

17、生成树725314650604565524050703042例1 某工厂要架设局域网联通工厂各个部门。已知工厂有7个部门，各个部门间铺设网线的距离如上图所示，计算出铺设网线的最短距离。Matlab的算法： 首先，将上图的邻接矩阵存储为G；即：G=999995060999999999999999999995099999999996540999999999960999999999952999999999945999996552999995030429999940999995099999709999999999999999999930709999999999999999999945429999999

18、99999999,然后调入到Matlab命令窗口中，另外将调用自编程序shengcs.m，即:n=7;result=shengcs(G,n)即可看见最小生成树的连接方式。 例2 某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。v5v6v2v4627535441V1v3 §5最短路例3 如下图所示的交通网络，边上的权重代表城市之间的距离，求城市1到其他城市的最短路径。12354101003010502060Matlab的算法： 首先，将上图的邻接矩阵存储为H；即：H=99999109999930100999999999950999

19、9999999999999999999999999991099999999992099999999999999999999999996099999然后调入到Matlab命令窗口中，另外将调用自编程序zuiduanlu.m,即：n=5;path=zuiduanlu(H,n)即可看见最最短路的连接方式。例4: 如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。v6v4v2v8v7v963623410231262410V1V3v5§6网络最大流VsV2V3VtV1V4(3,x1)(1,x3)(4,x4

20、)(5,x7)(5,x2)(2,x6)(1,x5)(2,x8)如上图所示，每条弧相关的括号中，第一个数据表示该条弧的容量，第二个表示该弧流量，最大流量必须满足以下条件的限制：1. 可行性条件：xi>=0, x1<=3, x2<=5, x3<=1, x4<=4, x5<=1,x6<=2, x7<=5, x8<=22. 始点Vs和收点Vt容量的要求：x1+x2<=8, x7+x8<=73. 流量平衡要求总流入量和总流出量相同：x1+x2-x7-x8=04. 内节点流入量和流出量相同：x1+x5-x3-x4=0x2+x3-x6=0x6

21、-x5-x8=0x4-x7=0目标函数为：max z=x1+x2软件求解：Matlab函数：linprog(线性规划), ip（整数规划） Lindo软件求解结果如下： OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.000000 0.000000 X3 0.000000 1.000000 X4 3.000000 0.000000 X5 0.000000 0.000000 X6 2.000000 0.000000 X7 3.000000 0.000000 X8 2.000000 0.000000例5.如下图所示为一城市水管网络流量图，试求一条从始点Vs到收点Vt的最大流v3v1vtv2v4vs1735108611453 §6最小费用最大流问题网络最大流只考虑了流量的问题，实际在运用时还有“费用”因素存在。人们总是希望在得到最大流的同时，使费用最少，这就是最小费用最大流问题VsV2V3VtV1V4(3,2，x1)(1,1，x3)(4,，5，