第9讲 非线性规划模型.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第9讲 非线性规划模型 非线性 规划 模型
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内