第9讲 非线性规划模型.pdf

《第9讲 非线性规划模型.pdf》由会员分享，可在线阅读，更多相关《第9讲 非线性规划模型.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.非线性规划非线性规划非线性规划建模非线性规划建模引例非线性规划模型、基本概念、性质非线性规划重要算法用引例非线性规划模型、基本概念、性质非线性规划重要算法用MATLAB解无约束规划解无约束规划引例：供应与选址引例：供应与选址某公司有某公司有6个建筑工地要开工，每个工地的位置个建筑工地要开工，每个工地的位置(用平面坐标系用平面坐标系a，b表示，距离单位：千米表示，距离单位：千米)及水泥日用量及水泥日用量w(吨吨)由下表给出。目前有两个临时料场位于由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有，日储量各有20吨。假设从料场到工地之间均有直线道路相连。吨。假设从料场到工

2、地之间均有直线道路相连。(1)试制定每天的供应计划，即从试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的两料场分别向各工地运送多少吨水泥，使总的吨千米吨千米数最小。数最小。(2)为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？吨，问应建在何处，节省的吨千米数有多大？1167453w(吨吨)7.756.554.750.751.25b7.2535.750.58.751.25a654321需点需点工地位置工地位置(a，b)及水泥日用量及水泥日

3、用量w(1)的求解：的求解：记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为wi,i=1,6;料场位置为料场位置为(cj，dj),日储量为日储量为ej，j=1,2;从料场从料场j向工地向工地i的运送量为的运送量为xij.目标函数为：目标函数为：=+=+=216122)()(minjiijijijbdacxf约束条件为：约束条件为：.2,1;6,2,1,02,1 ,6,2,1 ,6121=jixjexiwxijjiijijijLL这是一个线性规划这是一个线性规划,代入已知数据可方便求解代入已知数据可方便求解问题问题(1);这也是一个运输问题这也是一个运输问题,也可计算运费之

4、后列出运输表来求解也可计算运费之后列出运输表来求解问题问题(1);(2)的模型的模型记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为wi,i=1,6;料场位置为料场位置为(cj，dj),日储量为日储量为ej，j=1,2;从料场从料场j向工地向工地i的运送量为的运送量为xij.此时未知变量为此时未知变量为xij和和c1,c2,d1,d2!目标函数为：目标函数为：=+=+=216122)()(minjiijijijbdacxf约束条件为：约束条件为：.2,1;6,2,1,02,1 ,6,2,1 ,6121=jixjexiwxijjiijijijLL这是一个非线性规划问题这是一

5、个非线性规划问题线性约束的非线性规划问题！线性约束的非线性规划问题！定义定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题非线性规划的基本概念非线性规划的基本概念一般形式一般形式:()XfnRX min ()()()=.,.,2,1 0;1,2,.,0.ljXhmiXgtsji()(),21nTnRxxxX=L其中其中满足函数满足函数jihgf,R:RR,h:RR,gf:Rnjnin其它情况其它情况:求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式

6、求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式()()njiRXXhXgXD=,0,0|()XfDX min定义定义1 把满足问题把满足问题(1)中条件的解中条件的解XRn称为称为可行解可行解(或可行或可行点点)，所有可行点的集合称为，所有可行点的集合称为可行集可行集(或或可行域可行域)记为记为D即即:问题问题(1)可简记为可简记为定义2定义2 局部极小值点局部极小值点(局部最优解局部最优解);严格局部极小值点严格局部极小值点(严格局部最优解严格局部最优解).全局极小值点全局极小值点(全局最优解全局最优解)严格全局极小值点严格全局极小值点(严格全局最优解严格

7、全局最优解).注记：注记：当当f，gi是凸函数而是凸函数而hj是线性函数时，局部最优为是线性函数时，局部最优为全局最优。关键字：全局最优。关键字：Lagrange函数，函数，KT条件条件特殊非线性规划:特殊非线性规划:二次规划二次规划UxVbeqxAeqbxAtsxcHxx =+=+.21min 二次规划有成熟的求解算法，特别当二次规划有成熟的求解算法，特别当H正定或半正定时正定或半正定时(这时目标函数为凸函数这时目标函数为凸函数)，可得到全局最优解！二次规划有着非常广泛的应用，可得到全局最优解！二次规划有着非常广泛的应用!基本求解方法：基本求解方法：(1)罚函数法罚函数法内点法/外点法内点法

8、/外点法(2)序列线性规划法序列线性规划法(3)序列二次规划法序列二次规划法(4)信赖域算法信赖域算法()()()()()()()()()()=+=+=ljjkmiikkXhMXgMXfMXT1212,0min,()()()()()()()()=+=+=miikkmiikkXgrXfrXIXgrXfrXI111)(),(or ln,()()()()()()=0 0.min XhXgtsXfji)!10(1kkkMMM=+如的数列为单调递增趋于对没有等式约束的问题，可采用内点法：外点法如的数列为单调递增趋于对没有等式约束的问题，可采用内点法：外点法迭代求解如下无约束规划：缺点：每次迭代得到的解往

9、往是不可行的！缺点迭代求解如下无约束规划：缺点：每次迭代得到的解往往是不可行的！缺点:1)不适用与等式约束问题不适用与等式约束问题;2)必须从一个内点出发！必须从一个内点出发！)!10,(01 =+kkkrrr如单调递减趋于如单调递减趋于基本求解方法：基本求解方法：(1)罚函数法罚函数法内点法/外点法内点法/外点法(2)序列线性规划法序列线性规划法(3)序列二次规划法序列二次规划法(4)信赖域算法信赖域算法()()()()()kTkkXXXfXfXf+min()()()()()miXXXgXgXgkTkikii,1 0L=+=+()()()()()()ljXXXhXhXhkTkjkjj,1 0

10、L=+=+()()()()()()=0 0.min XhXgtsXfji序列线性规划法序列线性规划法每次求解一个近似线性规划：每次求解一个近似线性规划：kkXX)(需进行适当更新步长限制需进行适当更新步长限制k 基本求解方法：基本求解方法：(1)罚函数法罚函数法内点法/外点法内点法/外点法(2)序列线性规划法序列线性规划法(3)序列二次规划法序列二次规划法(4)信赖域算法信赖域算法()()()()()()dBddXfXfXfkTTkk21min+()()()()midXgXgXgTkikii,1 0L=+=+()()()()ljdXhXhXhTkjkjj,1 0L=+=+()()()()()(

11、)=0 0.min XhXgtsXfji序列二次规划法序列二次规划法每次求解一个近似二次规划：每次求解一个近似二次规划：下一次的搜索方向 下一次的搜索方向d新！用类似拟牛顿法迭代更矩阵近似，函数的当前点新！用类似拟牛顿法迭代更矩阵近似，函数的当前点HessenLagragekB基本求解方法：基本求解方法：(1)罚函数法罚函数法内点法/外点法内点法/外点法(2)序列线性规划法序列线性规划法(3)序列二次规划法序列二次规划法(4)信赖域算法信赖域算法()()()()()()dBddXfXfXfkTTkk21min+()()()()midXgXgXgTkikii,1 0L=+=+()()()()lj

12、dXhXhXhTkjkjj,1 0L=+=+()()()()()()=0 0.min XhXgtsXfji序列二次规划法序列二次规划法每次求解一个近似二次规划：每次求解一个近似二次规划：)(需要适当更新信赖域半径需要适当更新信赖域半径k 新！用类似拟牛顿法迭代更矩阵近似，函数的当前点新！用类似拟牛顿法迭代更矩阵近似，函数的当前点HessenLagragekBkd *1dXXkk+=+=+迭代：迭代：用用MATLAB软件求解软件求解,其输入格式如下其输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=quadprog(H,

13、C,A,b,Aeq,beq,VLB,VUB);4.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,fval,exitflag,output=quaprog(.);1、二次规划、二次规划标准型为：标准型为：Min Z=XTHX+cTXs.t.AX=bAeqX=beqVLBXVUB用用Matlab解非线性规划问题解非线性规划问题用Matlab解无约束优化问题用Matlab解无约束优化问题标准形式标准形式：输入命令：输入命令：H=2-2;-2 4;c=-2;-6;A

14、=1 1;-1 2;b=2;2;VLB=0;0;x,z=quadprog(H,c,A,b,VLB)运算结果为：运算结果为：x=(0.8000 1.2000);z=-7.2000XCHXXzT+=+=21minXbAX 0=62,4 22-2 CH=22,2 11 1 bA例例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x22-x1+2x22x10,x201.首先建立首先建立M文件文件fun.m,定义目标函数定义目标函数F(X):function f=fun(X);f=F(X);return2、一般非线性规划、一般非线性规划其中其中X为为n维变元向量

15、维变元向量,G(X)与与Ceq(X)均为非线性函数组成的向量均为非线性函数组成的向量,其它变量的含义与线性规划、二次规划中相同其它变量的含义与线性规划、二次规划中相同.用用Matlab求解上述问题求解上述问题,基本步骤分基本步骤分3步步:标准型为：标准型为：min F(X)s.tAXn x=x;endf=sqrt(x(13)-a).2+(x(14)-b).2)*x(1:6)+sqrt(x(15)-a).2+(x(16)-b).2)*x(7:12);return(2)取初值为线性规划的计算结果及临时料场的坐标取初值为线性规划的计算结果及临时料场的坐标,编写主程序编写主程序mymain.m.A=1

16、 1 1 1 1 1 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0;B=20;20;Aeq=eye(6)eye(6)zeros(6,4);beq=3 5 4 7 6 11;vlb=zeros(12,1);-inf;-inf;-inf;-inf;x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;x,fval,exitflag=fmincon(myfun,x0,A,B,Aeq,beq,vlb),x0=x;x,fval,exitflag=fmincon(myfun,x0,A,B,Aeq,beq,vlb),x0=x;x,fv

17、al,exitflag=fmincon(myfun,x0,A,B,Aeq,beq,vlb),x0=x;x,fval,exitflag=fmincon(myfun,x0,A,B,Aeq,beq,vlb)设设 X11=x1,X21=x2,X31=x3,X41=x4,X51=x5,X61=x6,X12=x7,X22=x8,X32=x9,X42=x10,X52=x11,X62=x12,c1=x13,d1=x14,c2=x15,d2=x1616个变量问题?向量个变量问题?向量x最终的总运量为最终的总运量为:99.3789,较临时料场节约运量较临时料场节约运量36.85!01234567890123456

18、781(3)2(5)3(4)4(7)5(6)6(11)工地分布及需求量示意图工地分布及需求量示意图分析此分布图，分析此分布图，人工选择初始值人工选择初始值初始料场点应为初始料场点应为6点和点和4点或点或5点中的一个，在人工分配运量可得：点中的一个，在人工分配运量可得：6?4X0=3 5 4 7 1 0 0 0 0 0 5 11 5.75 5 7.25 7.756?5X0=3 0 4 7 6 0 0 5 0 0 0 11 3 6.5 7.25 7.75?89.8902?85.266001234567890123456781(3)2(5)3(4)4(7)5(6)6(11)4 3 6 7 5 11

19、最优选址与供应量示意图最优选址与供应量示意图运量运量85.2660吨千米吨千米选址：选址：(3.2547,5.6522)(7.2500,7.7500)由于非凸非线性规划不能保证总的到全局最优解，要得到本题的全局最优解，需对问题适当处理，注意到当地址选定后本问题是一个线性规划问题，可得到对应的全局最优解，于是采用对料场地址可能坐标进行全搜索由于非凸非线性规划不能保证总的到全局最优解，要得到本题的全局最优解，需对问题适当处理，注意到当地址选定后本问题是一个线性规划问题，可得到对应的全局最优解，于是采用对料场地址可能坐标进行全搜索(只有只有4各变量各变量)，求解相应的线性规划，找出对应的最小解来！，求解相应的线性规划，找出对应的最小解来！全局搜索在一定情况下是很可靠的方法！全局搜索在一定情况下是很可靠的方法！模型检验或最优性的验证模型检验或最优性的验证请大家用这种方法求出本题的绝对最优解请大家用这种方法求出本题的绝对最优解程序运行程序运行时间不限时间不限!