第5讲-非线性规划PPT课件.ppt
数学建模与数学实验数学建模与数学实验第第5讲讲 非线性规划非线性规划 实验目的实验目的实验内容实验内容2、掌握用数学软件求解优化问题。、掌握用数学软件求解优化问题。1、直观了解非线性规划的基本内容。、直观了解非线性规划的基本内容。1、用用Matlab求解非线性规划求解非线性规划。4、实验作业。、实验作业。2、非线性规划模型举例。、非线性规划模型举例。3、钢管订购及运输优化模型、钢管订购及运输优化模型 1）首先建立首先建立M文件文件fun.m,定义目标函数定义目标函数F（X）:function f=fun(X);f=F(X);其中其中X为为n维变元向量，维变元向量，G(X)与与Ceq(X)均为非线性函数组成的均为非线性函数组成的向量，其它变量的含义与线性向量，其它变量的含义与线性规划、二次规划中相同规划、二次规划中相同.用用Matlab求解上述问题，基本步求解上述问题，基本步骤分三步：骤分三步：一、用一、用MatlabMatlab解非线性规划解非线性规划 3）建立主程序建立主程序.非线性规划求解的函数是非线性规划求解的函数是fmincon，命令的基本格式如下：命令的基本格式如下：(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,output=fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限 注意：注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认函数提供了大型优化算法和中型优化算法。默认时，若在时，若在fun函数中提供了梯度（函数中提供了梯度（options参数的参数的GradObj设置设置为为on），并且只有上下界存在或只有等式约束，），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日法更新拉格朗日Hessian矩阵。矩阵。3 fmincon函数可能会给出局部最优解，这与初值函数可能会给出局部最优解，这与初值X0的选取的选取有关。有关。1.写成标准形式写成标准形式：s.t.2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例1 2.先建立先建立M-文件文件 fun1.m:function f=fun1(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2MATLAB(youh1)3.再建立主程序再建立主程序youh1.m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun1,x0,A,b,Aeq,beq,VLB,VUB)4.运算结果为：运算结果为：x=0.7647 1.0588 fval=-2.0294 1先建立先建立M文件文件 fun2.m,定义目标函数定义目标函数:function f=fun2(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 02再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;ceq=;例例2 3主程序主程序youh2.m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun2,x0,A,b,Aeq,beq,vlb,vub,mycon2)MATLAB(youh2)4.运算结果为运算结果为：x=-1.2250 1.2250 fval=1.8951 1先建立先建立M-文件文件fun3.m定义目标函数定义目标函数:function f=fun3(x);f=-2*x(1)-x(2);2再建立再建立M文件文件mycon3.m定义非线性约束：定义非线性约束：function g,ceq=mycon3(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;ceq=;例例3 3.主程序主程序youh3.m为为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output =fmincon(fun3,x0,VLB,VUB,mycon3)MATLAB(youh3(fun3)4.运算结果为运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:返回返回 例例4 供应与选址供应与选址 某公司有某公司有6个建筑工地要开工，每个工地的位置（用平面坐标个建筑工地要开工，每个工地的位置（用平面坐标系系a，b表示，距离单位：千米表示，距离单位：千米）及水泥日用量）及水泥日用量d(吨吨)由下表给出。由下表给出。目前有两个临时料场位于目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有，日储量各有20吨。假吨。假设从料场到工地之间均有直线道路相连。设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从）试制定每天的供应计划，即从A，B两料场分别向各工地两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有吨，问应建在何处，节省的吨千米数有多大？多大？二、非线性规划模型举例二、非线性规划模型举例 (a1,b1),d1=3(a2,b2),d2=5(a6,b6),d6=11A(x1,y1)e1=20B(x2,y2)e2=20 x11x12x16x21x26x22目标：使得吨公里目标：使得吨公里min分析分析 模型的假设、符号说明模型的假设、符号说明符号说明符号说明1)第i个建筑工地的位置为(ai，bi)，i=1,n;2)第i个建筑工地需要水泥量为dj，i=1,n;3)第 j个料场的位置为(xj，yj)，j=1,m;4)第j个料场储备的水泥量为ej吨，j=1,2,m；5)第i个料场向第 j个建筑工地的运送量为xij，i=1,m j=1,n模型的假设模型的假设1 1）本模型只考虑与水泥运输有关的问题，其它 情况不予考虑；2 2）从料场到使用建筑工地之间均有直线道路相连。(a1,b1),d1=3(a2,b2),d2=5(a6,b6),d6=11A(x1,y1)e1=20B(x2,y2)e2=20 x11x12x16x21x26x22目标：使得吨公里目标：使得吨公里min分析分析 建立模型建立模型1.1.目标函数为：目标函数为：2.2.约束条件为约束条件为：需求约束需求约束:日储量约束日储量约束:非负约束非负约束:根据假设2，所有的吨公里为：建立模型建立模型所以问题的模型为：所以问题的模型为：1 1）当用原）当用原料场料场时决策变量为：时决策变量为：xij2 2）当新建）当新建料场料场时决策变量为：时决策变量为：xij，xj，yj模型的特点模型的特点 模型的求解模型的求解 使用两个使用两个原原料场料场A(5,1)，B(2,7).求从料场求从料场j 向使用向使用单位单位i 的运送量为的运送量为xij，在各建筑工地使用量必须满足和，在各建筑工地使用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米各料场运送量不超过日储量的条件下，使总的吨千米数最小，此时由于数最小，此时由于ai，bi、xj，yj都是已知的，故这是都是已知的，故这是一个一个线性规划线性规划问题问题.此时决策变量为此时决策变量为xij，令令1.1.使用原料场使用原料场 求解线性规划，求解线性规划，MATLABMATLAB程序程序a=1.25 8.75 0.5 5.75 3 7.25;b=1.25 0.75 4.75 5 6.5 7.75;d=3 5 4 7 6 11;x=5 2;y=1 7;e=20 20;for i=1:2 for j=1:6 aa(i,j)=sqrt(x(i)-a(j)2+(y(i)-b(j)2);endendCC=aa(1,:)aa(2,:);符号说明符号说明：1.1.编写程序编写程序gying1 A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1;B=20;20;Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1;beq=d(1);d(2);d(3);d(4);d(5);d(6);VLB=0 0 0 0 0 0 0 0 0 0 0 0;VUB=;x0=1 2 3 0 1 0 0 1 0 1 0 1;x,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0)2.2.计算结果计算结果：总的吨千米数：总的吨千米数：136.23j123456x1j(料场A)350701x2j(料场B)0040610MATLAB（gying1）2.改建两个料场改建两个料场决策变量决策变量为：为：xij，xi，yj 改建两个新料场，要同时确定料场的位置改建两个新料场，要同时确定料场的位置(xj,yj)和运送量和运送量xij，在同样条件下使总吨千米数最小。此时在同样条件下使总吨千米数最小。此时由于由于ai，bi 已知已知，但但xj，yj都是未知的，故这是都是未知的，故这是非线性非线性规划规划问题。问题。模型模型为：为：求解非线性规划，求解非线性规划，MATLAB程序程序(liaoch.m)function f,g=liaoch(x)a=1.25 8.75 0.5 5.75 3 7.25;b=1.25 0.75 4.75 5 6.5 7.75;d=3 5 4 7 6 11;e=20 20;f1=0;for j=1:6 s(j)=sqrt(x(13)-a(j)2+(x(14)-b(j)2);f1=f1+s(j)*x(j);%A(x13,x14)到各工地的吨公里数end符号说明符号说明：1)1)编写程序编写程序liaoch.m和和gying2 f2=0;for i=7:12 s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2);f2=f2+s(i)*x(i);%B(x15,x16)到各工地的吨公里数endf=f1+f2;%总的目标函数clearx0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0;B=20;20;Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0;编写主程序编写主程序gying2.m 3)3)结论：结论：总的吨千米总的吨千米 数：数：89.9 89.9 比使用原料场减少了比使用原料场减少了45.5.45.5.2)2)计算结果计算结果beq=3 5 4 7 6 11;vlb=zeros(12,1);-inf;-inf;-inf;-inf;vub=;x,fval,exitflag=fmincon(liaoch,x0,A,B,Aeq,beq,vlb,vub)总的吨千米总的吨千米 数：数：89.9gying2（liaoch）例例6 选址问题选址问题 1.建立数学模型建立数学模型 这是一个最大最小化模型。最大最小化模型。2.模型求解模型求解 钢管订购及运输优化模型钢管订购及运输优化模型20002000年年“网易杯网易杯”全国大学生数学建模竞赛全国大学生数学建模竞赛B B题题优化模型竞赛题优化模型竞赛题 一、问题重述一、问题重述 要铺设一条输送天然气的主管道A1A2A15，能生产这种钢管的厂家一共有:S1,S2,S7。厂家与管道间的交通网络交通网络已知。假设沿管道或者原来有公路，或者建有施工公路。为方便计算，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si 个单位，钢厂1单位钢管的出厂销价为pi万元，如下表：I1 2 3 4 5 6 7 SI800 800 1000 2000 2000 2000 3000 Pi160 155 155 160 155 150 160 1单位钢管的铁路运价铁路运价如下表，1000km以上每增加1至100km运价增加5万元。公路运输费用公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到主管道结点A1,A2,A15,而是管道全线）。里程（km）300 301350 351400 401450 451500 运价（万元）20 23 26 29 32 里程（km）501600 601700 701800 801900 9011000 运价（万元）37 44 50 55 60 （1 1）请制定一个主管道钢管主管道钢管的订购和运输计划，使总费用最小（给出总费用）。（2 2）请就（）的模型分析：哪个钢厂钢管的销销价的变化价的变化对购运计划购运计划和总费用总费用影响最大，哪个钢厂钢管的产量的上限的变化产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3 3）如果要铺设的管道不是一条线，而是一个树树形图形图，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图（）的情形给出模型和结果。需解决的问题：需解决的问题：图1A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7图一 二、模型假设二、模型假设1.沿铺设的主管道以有公路或者有施工公路。2.在主管道上，每公里卸1单位的钢管。3.公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）4.在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用。5.在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂的产量不受限制。6.假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管的运价增加5万元。三、符号说明三、符号说明 四、模型的分析、建立、求解四、模型的分析、建立、求解 先看总费用：总费用总费用：总费用由三部分组成：1)1)钢管的订购费钢管的订购费。支付钢厂订购钢管的费用。因为钢厂生产单位钢管的出厂销价为常量常量，所以在运费相同的情况下，应从销价低的钢厂订购钢管应从销价低的钢厂订购钢管。1.模型的分析与决策变量的设置模型的分析与决策变量的设置 根据题目要求，要制定一个主管道钢管主管道钢管的订购订购和运输运输计划，使总费用总费用最小。2)2)把钢管从钢厂运到钢厂运到主管道结点主管道结点所需的运费运费。要注意运输过程中既有铁路，也有公路既有铁路，也有公路。3)3)从结点Ai向两边铺设管道铺设管道的费用的费用。要注意每个结点分别向左右铺设多少分别向左右铺设多少？再看订购和运输计划：订购和运输计划：所谓所谓订购计划订购计划：就是向每个钢厂订购多少钢管。所谓所谓运输计划运输计划：就是将每个钢厂订购的钢管运输到 那些节点？运多少？故可设：向第i个钢厂订购xi单位钢管，第i个钢厂 运往第j个节点xij单位的钢管。故可设：向第i个钢厂订购xi单位钢管，第i个钢厂 运往第j个节点xij单位的钢管 。故变量xi可以不要，少用少用7 7个变量个变量！另外另外，要决定每个结点分别向左右铺设多少？第二方案第二方案：也可以考虑在Aj左右各设一个变量左右各设一个变量！2.求单位钢管从钢厂运到运输点的最小费用求单位钢管从钢厂运到运输点的最小费用方法方法：将图一转换为一个以单位钢管的运输费 用为权的赋权图，再求最短路的权。赋权图，再求最短路的权。由于运输过程中既有铁路，也有公路，且铁路铁路的运费还是分段函数的运费还是分段函数，与全程运输总距离有关；各路运费确是线性函数线性函数。1单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)3744505560可考虑将铁路与公路分开考虑分开考虑。1)将铁路图转化成费用图（与将铁路图转化成费用图（与Ai对应编号）对应编号）图一图一 b2b3b4b5b6b71b8b9b10b11b12b13b141b142b151b1521601408037202020608595105115125130140140可利用专业的图论软件包图论软件包或MATLABMATLAB软件包软件包求最短路。计算计算Si 到到bi 的最小费用（与的最小费用（与Ai对应编号）对应编号）如以S1 为例例：S1到bi的最小费用为:b2b3b4b5b6b71b8b9b10b11b12b13b141b142b151b1521601408037202020608595105115125130140140 利用MATLABMATLAB软件包软件包求解,如S1到bi的最小费用为:2)合并铁路和公路图得以费用为权的交通网络图合并铁路和公路图得以费用为权的交通网络图 S1到结点到结点Ai的最小费用图的最小费用图 再用图论软件包图论软件包或MATLAB软件包软件包求解,如S1到Ai的最小费用（万元）为:A2A3A4A5A6A7A8160.3140.298.63820.53.121.2A9A10A11A12A13A14A1564.29296106121.21281423)计算计算S1到结点到结点Ai的最小费用的最小费用 A2A3A4A5A6A7A8160.3140.298.63820.53.121.2A9A10A11A12A13A14A1564.29296106121.21281424)计算单位钢管从计算单位钢管从S1到到Ai的订购与运输的最小费用的订购与运输的最小费用A2A3A4A5A6A7A8320.3300.2258.6198180.5163.1181.2A9A10A11A12A13A14A15224.2252256266281.2288302 5)从从Si 购买单位钢管运到结点购买单位钢管运到结点Ai的最小费用的最小费用Aij：A2A3A4A5A6A7A8A9A10A11A12A13A14A15s1320.3300.2258.6198180.5163.1181.2224.2252256266281.2288302s2360.3345.2326.6266250.5241226.2269.2297301311326.2333347s3375.3355.2336.6276260.5251241.2203.2237241251266.2273287s4410.3395.2376.6316300.5291276.2244.2222211221236.2243257s5400.3380.2361.6301285.5276266.2234.2212188206226.2228242s6405.3385.2366.6306290.5281271.2234.2212201195176.2161178s7425.3405.2386.6326310.5301291.2259.2237226216198.2186162 (1)(1)铺设总费用铺设总费用总费用总费用=铺设总费用铺设总费用+成本及运输总费用成本及运输总费用=C+W=C+W3.模型的建立模型的建立1)1)目标函数目标函数 铺设总费用：铺设总费用：故故总总的的铺设费铺设费用用为为：（2)成本及运输总费用：成本及运输总费用：目标函数为：目标函数为：总费用总费用=铺设总费用铺设总费用+成本及运输总费用成本及运输总费用=C+W 2）约束条件）约束条件 非线性规划模型：非线性规划模型：综合上述分析，得 5.模型求解模型求解 利用利用LINGO软件包编程求解软件包编程求解Global optimal solution found.Objective value:1275352.Objective bound:1275352.Infeasibilities:0.000000 Extended solver steps:1 Total solver iterations:381 Model Title:问题一的模型求解：分三种情况分别求解问题一的模型求解：分三种情况分别求解 Variable Value S1DINGGOULIANG 800.0000 S2DINGGOULIANG 800.0000 S3DINGGOULIANG 1000.000 S4DINGGOULIANG 0.000000 S5DINGGOULIANG 1155.824 S6DINGGOULIANG 1170.176 S7DINGGOULIANG 245.0000 1）不让）不让S7生产的模型求解生产的模型求解添加一个S7生产量为0的约束原模型原模型不让不让S7生产的模型生产的模型 2)要求钢厂要求钢厂S7的产量不小于的产量不小于500个单位个单位 原模型原模型让让S7生产量不小于生产量不小于500的模型的模型添加S7生产量不小于500的约束 模型的最后计算结果：模型的最后计算结果：订购量订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S5101503582420000004150000S6155600000000035186333621165S7000000000000000 某厂向用户提供发动机，合同规定，第一、二、某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货三季度末分别交货4040台、台、6060台、台、8080台每季度的生台每季度的生产费用为产费用为 （元），其中（元），其中x是该季生产的台数是该季生产的台数若交货后有剩余，可用于下季度交货，但需支付若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度存储费，每台每季度c元已知工厂每季度最大生产元已知工厂每季度最大生产能力为能力为100100台，第一季度开始时无存货，设台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满问工厂应如何安排生产计划，才能既满足合同又使总费用最低讨论足合同又使总费用最低讨论a、b、c变化对计划的变化对计划的影响，并作出合理的解释影响，并作出合理的解释练习一练习一 练习二练习二 谢谢 谢！谢！
