第5讲-非线性规划PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模与数学实验,第,5,讲 非线性规划,数学建模与数学实验第5讲 非线性规划,实验目的,实验内容,2,、掌握用数学软件求解优化问题。,1,、直观了解非线性规划的基本内容。,1,、用,Matlab,求解非线性规划,。,4,、实验作业。,2,、非线性规划模型举例。,3,、钢管订购及运输优化模型,实验目的实验内容2、掌握用数学软件求解优化问题。1、直观了解,1,） 首先建立,M,文件,fun.m,定义目标函数,F,（,X,）,:,function f=fun(X);,f=F(X);,其中,X,为,n,维变元向量，,G(X),与,Ceq(X),均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同,.,用,Matlab,求解上述问题，基本步骤分三步：,一、用,Matlab,解非线性规划,1） 首先建立M文件fun.m,定义目标函数F（X）:,3,） 建立主程序,.,非线性规划求解的函数是,fmincon,，,命令的基本格式如下：,(1),x=,fmincon,(fun,X,0,A,b),(2),x=,fmincon,(fun,X,0,A,b,Aeq,beq),(3),x=,fmincon,(fun,X,0,A,b, Aeq,beq,VLB,VUB),(4),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,nonlcon),(5),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,nonlcon,options),(6) ,x,fval,=,fmincon(.),(7) ,x,fval,exitflag,=,fmincon(.),(8) ,x,fval,exitflag,output,=,fmincon(.),输出极值点,M,文件,迭代的初值,参数说明,变量上下限,3） 建立主程序.非线性规划求解的函数是fmincon，,注意：,1 fmincon,函数提供了大型优化算法和中型优化算法。默认时，若在,fun,函数中提供了梯度（,options,参数的,GradObj,设置为,on,），并且只有上下界存在或只有等式约束，,fmincon,函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。,2 fmincon,函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用,BFGS,法更新拉格朗日,Hessian,矩阵。,3 fmincon,函数可能会给出局部最优解，这与初值,X,0,的选取有关。,注意：,1.,写成标准形式,：,s.t.,2x,1,+3x,2,6,s.t x,1,+4x,2,5,x,1,x,2,0,例,1,1.写成标准形式： 2x1+3x2,2.,先建立,M-,文件,fun1.m:,function f=fun1(x);,f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(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,2.先建立M-文件 fun1.m:MATLAB(youh1),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);,x,1,+x,2,=0,s.t. 1.5+x,1,x,2,- x,1,- x,2,0,-x,1,x,2,10,0,2,再建立,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,1先建立M文件 fun2.m,定义目标函数:,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,3主程序youh2.m为:MATLAB(youh2)4.,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,1先建立M-文件fun3.m定义目标函数:2再建立M文件,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),3. 主程序youh3.m为:MATLAB(youh3(fu,4.,运算结果为,:,x =,4.0000,3.0000,fval =-11.0000,exitflag = 1,output =,iterations: 4,funcCount: 17,stepsize: 1,algorithm: 1x44 char,firstorderopt: ,cgiterations: ,返回,4. 运算结果为: 返回,例,4,供应与选址,某公司有,6,个建筑工地要开工，每个工地的位置（用平面坐标系,a,，,b,表示，距离单位：千米 ）及水泥日用量,d(,吨,),由下表给出。目前有两个临时料场位于,A(5,1),，,B(2,7),，日储量各有,20,吨。假设从料场到工地之间均有直线道路相连。,（,1,）试制定每天的供应计划，即从,A,，,B,两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。,（,2,）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为,20,吨，问应建在何处，节省的吨千米数有多大？,二、非线性规划模型举例,例4 供应与选址 某公司有6个建筑工地要开工，,(,a,1,b,1,), d,1,= 3,(,a,2,b,2,), d,2,=5,(,a,6,b,6,), d,6,= 11,A(,x,1,y,1,),e,1,= 20,B(,x,2,y,2,),e,2,= 20,x,11,x,12,x,16,x,21,x,26,x,22,目标：使得吨公里,min,分析,(a1, b1), d1 = 3(a2, b2), d2 =,模型的假设、符号说明,符号说明,1),第,i,个,建筑工地,的位置为,(,a,i,，,b,i,),，,i,=1,n,;,2),第,i,个,建筑工地,需要,水泥,量为,d,j,，,i,=1,n,;,3),第,j,个,料场,的位置为,(,x,j,，,y,j,),，,j,=1,m,;,4),第,j,个,料场,储备的,水泥,量为,e,j,吨,，,j,=1,2, ,m,；,5),第,i,个,料场,向第,j,个,建筑工地,的运送量为,x,ij,，,i,=1,m,j,=1,n,模型的假设,1,）,本模型只考虑与水泥运输有关的问题，其它,情况不予考虑；,2,）,从料场到使用建筑工地之间均有直线道路相连 。,模型的假设、符号说明符号说明1) 第i个建筑工地的位置为(,(,a,1,b,1,), d,1,= 3,(,a,2,b,2,), d,2,=5,(,a,6,b,6,), d,6,= 11,A(,x,1,y,1,),e,1,= 20,B(,x,2,y,2,),e,2,= 20,x,11,x,12,x,16,x,21,x,26,x,22,目标：使得吨公里,min,分析,(a1, b1), d1 = 3(a2, b2), d2 =,建立模型,1.,目标函数为：,2.,约束条件为,：,需求约束,:,日储量约束,:,非负约束,:,根据假设,2,，所有的吨公里为：,建立模型1.目标函数为：2.约束条件为：需求约束:日储量约束,建立模型,所以问题的模型为：,1,）当用原,料场,时决策变量为：,x,ij,2,）当新建,料场,时决策变量为：,x,ij,，,x,j,，,y,j,模型的特点,建立模型所以问题的模型为：1）当用原料场时决策变量为：xij,模型的求解,使用两个,原,料场,A,(5,1),，,B,(2,7).,求从料场,j,向使用单位,i,的运送量为,x,ij,，在各建筑工地使用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，此时由于,a,i,，,b,i,、,x,j,，,y,j,都是已知的，故这是一个,线性规划,问题,.,此时决策变量为,x,ij,，,令,1.,使用原料场,模型的求解 使用两个原料场A(5,1)，B(2,求解线性规划，,MATLAB,程序,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);,end,end,CC=aa(1,:) aa(2,:);,符号说明,：,1.,编写程序,gying1,求解线性规划，MATLAB程序a=1.25 8.75 0.,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.,计算结果,：,总的吨千米数：,136.23,MATLAB,（,gying1,）,A=1 1 1 1 1 1 0 0 0 0 0 02.计算,2.,改建两个料场,决策变量,为：,x,ij,，,x,i,，,y,j,改建两个新料场，要同时确定料场的位置,(,x,j,y,j,),和运送量,x,ij,，,在同样条件下使总吨千米数最小。此时由于,a,i,，,b,i,已知,，,但,x,j,，,y,j,都是未知的，故这是,非线性规划,问题。,模型,为：,2.改建两个料场决策变量为：xij，xi，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,(x,13,x,14,),到各工地的吨公里数,end,符号说明,：,1),编写程序,liaoch.m,和,gying2,求解非线性规划，MATLAB程序(liaoch.m)func,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),到各工地的吨公里数,end,f=f1+f2; %,总的目标函数,clear,x0=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,f2=0;clear编写主程序gying2.m,3),结论：,总的吨千米 数：,89.9,比使用原料场减少了,45.5.,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.9,gying2,（,liaoch,）,3) 结论：总的吨千米 数：89.9 比使用原料场减少了4,例,6,选址问题,例6 选址问题,1.,建立数学模型,这是一个,最大最小化模型。,1.建立数学模型 这是一个最大最小化模型。,2.,模型求解,2.模型求解,第5讲-非线性规划PPT课件,钢管订购及运输优化模型,2000,年“网易杯”全国大学生数学建模竞赛,B,题,优化模型竞赛题,钢管订购及运输优化模型2000年“网易杯”全国大学生数学建模,一、问题重述,要铺设一条输送天然气的主管道,A1A2,A15,，能生产这种钢管的厂家一共有,:S1,S2,S7,。厂家与管道间的,交通网络,已知。假设沿管道或者原来有公路，或者建有施工公路。,为方便计算，,1km,主管道钢管称为,1,单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产,500,个单位。钢厂,Si,在指定期限内能生产该钢管的最大数量为,si,个单位，钢厂,1,单位钢管的出厂销价为,p,i,万元，如下表：,一、问题重述 要铺设一条输送天然气的主管道A1A2A,1,单位钢管的,铁路运价,如下表，,1000km,以上每增加,1,至,100km,运价增加,5,万元。,公路运输费用,为,1,单位钢管每公里,0.1,万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到主管道结点,A,1,A,2, A,15,而是管道全线）。,1单位钢管的铁路运价如下表，1000km以上每增加1至,（,1,）,请制定一个,主管道钢管,的订购和运输计划，使总费用最小（给出总费用）。,（,2,）,请就（）的模型分析：哪个钢厂钢管的,销价的变化,对,购运计划,和,总费用,影响最大，哪个钢厂钢管的,产量的上限的变化,对购运计划和总费用的影响最大，并给出相应的数字结果。,（,3,）,如果要铺设的管道不是一条线，而是一个,树形图,，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图（）的情形给出模型和结果。,需解决的问题：,（1）请制定一个主管道钢管的订购和运输计划，使总费用最,图,1,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,图一,图1A132580101031201242701088107,二、模型假设,1.,沿铺设的主管道以有公路或者有施工公路。,2.,在主管道上，每公里卸,1,单位的钢管。,3.,公路运输费用为,1,单位钢管每公里,0.1,万元（不足整公里部分按整公里计算）,4.,在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用。,5.,在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂的产量不受限制。,6.,假设钢管在铁路运输路程超过,1000km,时，铁路每增加,1,至,100km,，,1,单位钢管的运价增加,5,万元。,二、模型假设1.沿铺设的主管道以有公路或者有施工公路。,三、符号说明,三、符号说明,四、模型的分析、建立、求解,先看,总费用：总费用,由三部分组成：,1),钢管的订购费,。,支付钢厂订购钢管的费用。因为钢厂生产单位钢管的出厂销价为,常量,，所以在运费相同的情况下，,应从销价低的钢厂订购钢管,。,1.,模型的分析与决策变量的设置,根据题目要求，要制定一个,主管道钢管,的,订购,和,运输,计划，使,总费用,最小。,四、模型的分析、建立、求解 先看总费用：总费用由三部分组成：,2),把钢管从,钢厂运到,主管道结点,所需的,运费,。,要注意运输过程中,既有铁路，也有公路,。,3),从结点,A,i,向两边,铺设管道,的费用,。,要注意每个结点,分别向左右铺设多少,？,再看,订购和运输计划：,所谓,订购计划,：就是向每个钢厂订购多少钢管。,所谓,运输计划,：,就是将每个钢厂订购的钢管运输到,那些节点？运多少？,故可设：向第,i,个钢厂订购,x,i,单位钢管，第,i,个钢厂,运往第,j,个节点,x,ij,单位的钢管。,2) 把钢管从钢厂运到主管道结点所需的运费。 3) 从结点A,故可设：向第,i,个钢厂订购,x,i,单位钢管，第,i,个钢厂,运往第,j,个节点,x,ij,单位的钢管 。,故变量,x,i,可以不要，,少用,7,个变量,！,另外,，要决定每个结点分别向,左右铺设,多少？,第二方案,：也可以考虑在,A,j,左右各设一个变量,！,故可设：向第i个钢厂订购xi单位钢管，第i个钢厂故变量xi可,2.,求单位钢管从钢厂运到运输点的最小费用,方法,：将,图一,转换为一个以单位钢管的运输费,用为权的,赋权图，再求最短路的权。,由于运输过程中既有铁路，也有公路，且,铁路的运费还是分段函数,，与全程运输总距离有关,；各路运费确是,线性函数,。,1,单位钢管的铁路运价如下表：,可考虑将铁路与公路,分开考虑,。,2.求单位钢管从钢厂运到运输点的最小费用方法：将图一转换为一,1),将铁路图转化成费用图（与,A,i,对应编号）,图一,1) 将铁路图转化成费用图（与Ai对应编号）图一,1),将铁路图转化成费用图,(,统一编号,),图一,1) 将铁路图转化成费用图 (统一编号)图一,可利用专业的,图论软件包,或,MATLAB,软件包,求最短路。,计算,S,i,到,b,i,的最小费用（与,Ai,对应编号）,如以,S,1,为,例,：,S,1,到,b,i,的最小费用为,:,可利用专业的图论软件包或MATLAB软件包求最短路。计算Si,可利用专业的,图论软件包,或,MATLAB,软件包,求解,如,S1,到,b,i,的最小费用为,:,计算,S,1,到,b,i,的最小费用,(,统一编号,),可利用专业的图论软件包或MATLAB软件包求解,如S1,利用,MATLAB,软件包,求解,如,S,1,到,b,i,的最小费用为,:,2),合并铁路和公路图得以费用为权的交通网络图,利用MATLAB软件包求解,如S1到bi的最小费用为:,S,1,到结点,A,i,的最小费用图,S1到结点Ai的最小费用图,再用,图论软件包,或,MATLAB,软件包,求解,如,S,1,到,A,i,的最小费用（万元）为,:,3),计算,S,1,到结点,A,i,的最小费用,再用图论软件包或MATLAB软件包求解,如S1到Ai,4),计算单位钢管从,S,1,到,A,i,的订购与运输的最小费用,4) 计算单位钢管从S1到Ai的订购与运输的最小费用,5),从,S,i,购买单位钢管运到结点,A,i,的最小费用,A,ij,：,5) 从Si 购买单位钢管运到结点Ai的最小费用Aij ：,(1),铺设总费用,总费用,=,铺设总费用,+,成本及运输总费用,=C+W,3.,模型的建立,1),目标函数,(1)铺设总费用总费用=铺设总费用+成本及运输总费用=C+W,铺设总费用：,故总的铺设费用为：,铺设总费用：故总的铺设费用为：,（,2),成本及运输总费用：,（2)成本及运输总费用：,目标函数为：,总费用,=,铺设总费用,+,成本及运输总费用,=,C,+,W,目标函数为：总费用=铺设总费用+成本及运输总费用=C+W,2,）约束条件,2）约束条件,非线性规划模型：,综合上述分析，得,非线性规划模型：综合上述分析，得,5.,模型求解,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,利用LINGO软件包编程求解Global optimal s,1,）不让,S7,生产的模型求解,添加一个,S7,生产量为,0,的约束,原模型,不让,S7,生产的模型,1）不让S7生产的模型求解添加一个S7生产量为0的约束原模型,2),要求钢厂,S,7,的产量不小于,500,个单位,原模型,让,S7,生产量不小于,500,的模型,添加,S7,生产量不小于,500,的约束,2) 要求钢厂S7的产量不小于500个单位 原模型让S7生产,模型的最后计算结果：,模型的最后计算结果：,某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货,40,台、,60,台、,80,台每季度的生产费用为,（元），其中,x,是该季生产的台数若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度,c,元已知工厂每季度最大生产能力为,100,台，第一季度开始时无存货，设,a=,50,、,b,=0.2,、,c,=4,，,问工厂应如何安排生产计划，才能既满足合同又使总费用最低讨论,a,、,b,、,c,变化对计划的影响，并作出合理的解释,练习一,某厂向用户提供发动机，合同规定，第一、二、,练习二,练习二,谢 谢！,谢 谢！,