第四讲 非线性规划

优化建模一、非线性规划问题的提出1、为什么要研究非线性规划？•整个社会日益非线性化；•非线性的问题越来越成为人们关注的焦点;•非线性的问题及研究方法的应用广泛；•更多的非线性问题的数学模型都是非线性规划。2、什么是非线性规划？它与线性规划有何不同？•目标函数或约束条件中含有非线性函数；•二者的可行域不同;•非线性规划不一定有全局最优解；•求解方法有很大的不同。优化建模引例股票的组合投资问题一个投资者拟选择Ａ，Ｂ，Ｃ三支业绩好的股票来进行长期组合投资．通过对这三支股票的市场分析和统计预测得到相关数据如下表1所示．表1股票的相关数据表五年的协方差（％）股票名称五年期望收益率（％）ＡＢＣＡＢＣ9264411803611036120-30110-30140一、非线性规划问题的提出优化建模该投资者请你从两个方面分别给出三支股票的投资比例：（１）希望将投资组合中的股票收益的标准差降到最小，以降低投资风险，并希望五年后的期望收益率不少于65%．（２）希望在标准差最大不超过12%的情况下，获得最大的收益．一、非线性规划问题的提出优化建模二、非线性规划的基本概念1、非线性规划问题的数学模型非线性规划的一般模型为ljxxxgmixxxhxxxfnjnin,,2,1,0),,,(,,2,1,0),,,(),,,(min212121若记nTnExxxX),,,(21是n维欧氏空间中的向量（点），则模型为ljXgmiXhXfji,,2,1,0)(,,2,1,0)()(min优化建模ljXgmiXhXfji,,2,1,0)(,,2,1,0)()(min说明：（1）若目标函数为最大化问题，由)](min[)(maxXfXf，令)()(XfXF，则)(min)(maxXFXf；ljxxxgmixxxhxxxfnjnin,,2,1,0),,,(,,2,1,0),,,(),,,(min212121（2）若约束条件为0)(Xgj，则0)(Xgj；（3）0)(0)(0)(XhandXhXhiii。于是可将非线性规划的一般模型写成如下形式：mjXgXfj,,2,1,0)()(min优化建模2．几种特殊情况（1）无约束的非线性规划当问题无约束条件时，则此问题称为无约束的非线性规划，即多元函数的极值问题。一般模型为0)(minXXfRX（2）凸规划当目标函数)(Xf为凸函数，),,2,1)((ljXgj均为凹函数（即)(Xgj为凸函数），则这样的非线性规划称为凸规划。优化建模（3）二次规划1111min()0,1,2,,..0,,,1,2,,nnnjjjkjkjjknijjijjjkkjfXcxcxxaxbimstxccjkn如果目标函数是X的二次函数，约束条件都是线性的，则称此规划为二次规划。二次规划的一般模型为优化建模三．多元函数的极值设)(Xf在区域nER上有定义，对于RX*，如果存在某个0，使对满足*XX的所有RX都有)()(*XfXf（或)()(*XfXf），则称*X为)(Xf在R上局部极小（或大）点，)(*Xf为局部极小（或大）值。（1）局部极值与全局极值如果对所有满足*XX的RX（*XX）都有)()(*XfXf（或)()(*XfXf），则称*X为)(Xf在R上严格局部极小（或大）点，)(*Xf为严格局部极小（或大）值。优化建模如果对所有RX都有)()(*XfXf（或)()(*XfXf），则称*X为)(Xf在R上的全局极小（或大）点，)(*Xf为全局极小（或大）值。如果对所有的RX（*XX）都有)()(*XfXf（或)()(*XfXf），则称*X为)(Xf在R上严格全局极小（或大）点，)(*Xf为严格全局极小（或大）值。优化建模2020年1月19日10针对带有约束条件的非线性规划模型的一般形式为:ljXgmiXhXfji,,2,1,0)(,,2,1,0)()(min下面给出LINGO模型的基本形式.优化建模2020年1月19日11MODEL:sets:num_i/1..m/;num_j/1..L/;num_k/1..n/:x0,x;endsetsinit:x0=x0(1),x0(2),…,x0(n);endinit[OBJ]min=f(x);!目标函数的表达式@for(num_i(i):hi(x)=0;);!等式约束条件@for(num_j(j):gj(x)=0;);!不等式约束条件@for(num_k(k):x(k)=0;);ENDljXgmiXhXfji,,2,1,0)(,,2,1,0)()(min优化建模2020年1月19日12一个投资者拟选择Ａ，Ｂ，Ｃ三支业绩好的股票来进行长期组合投资．通过对这三支股票的市场分析和统计预测得到相关数据如下表1所示．应用案例1：股票的组合投资问题优化建模2020年1月19日13应用案例1：股票的组合投资问题表1股票的相关数据表五年的协方差（％）股票名称五年期望收益率（％）ＡＢＣＡＢＣ9264411803611036120-30110-30140试从两个方面分别给出三支股票的投资比例：优化建模2020年1月19日14应用案例1：股票的组合投资问题(１)希望将投资组合中的股票收益的标准差降到最小，以降低投资风险，并希望五年后的期望收益率不少于65%．(２)希望在标准差最大不超过12%的情况下，获得最大的收益．优化建模2020年1月19日15应用案例1：股票的组合投资问题解设123,,xxx分别表示Ａ，Ｂ，Ｃ三支股票的投资比例，其五年的期望收益率分别记为123,,rrr，即为随机变量．五年后投资组合的总收益率为112233Rxrxrxr，表1股票的相关数据表五年的协方差（％）股票名称五年期望收益率（％）ＡＢＣＡＢＣ9264411803611036120-30110-30140优化建模2020年1月19日16应用案例1：股票的组合投资问题由概率统计的知识,投资组合的方差为222112233121213132323()()()()2(,)2(,)2(,),VarRxVarrxVarrxVarrxxCovrrxxCovrrxxCovrr根据表1中的数据计算得到222123121323()1801201407222060.VarRxxxxxxxxx投资组合的标准差为12222123121323[1801201407222060].Dxxxxxxxxx优化建模2020年1月19日17应用案例1：股票的组合投资问题问题(１)：根据投资者第(1)项要求，则问题的模型为12222123121323123123123min[1801201407222060];1,s.t.0.920.640.410.65,,,0.Dxxxxxxxxxxxxxxxxxx优化建模2020年1月19日18MODEL:sets:num_i/1,2,3/:r,x;endsetsdata:r=0.92,0.64,0.41;enddata[OBJ]min=(180*x(1)^2+120*x(2)^2+140*x(3)^2+72*x(1)*x(2)+220*x(1)*x(3)-60*x(2)*x(3))^(1/2);x(1)+x(2)+x(3)=1;@sum(num_i(i):r(i)*x(i))=0.65;@for(num_i(i):x(i)=0;);END股票组合投资问题的LINGO模型优化建模2020年1月19日19运行该程序可得到结果10.2350713,x230.5222332,0.2426955xx，其最优值为D=8.043967．在保证风险最小，五年总收益率65％的Ａ，Ｂ，Ｃ三支股票的组合投资比例分别为23.51％，52.22％，24.27％，其最小标准差为8.044％．股票组合投资问题的求解结果优化建模2020年1月19日20根据投资者第（２）项要求，则问题的模型为12312312222123121323123max0.920.640.41;1,s.t.[1801201407222060]12,,,0.Rxxxxxxxxxxxxxxxxxx问题（２）：希望在标准差最大不超过12%的情况下，获得最大的收益．应用案例1：股票的组合投资问题优化建模2020年1月19日21MODEL:sets:num_i/1,2,3/:r,x;endsetsdata:r=0.92,0.64,0.41;enddata[OBJ]max=@sum(num_i(i):r(i)*x(i));x(1)+x(2)+x(3)=1;(180*x(1)^2+120*x(2)^2+140*x(3)^2+72*x(1)*x(2)+220*x(1)*x(3)-60*x(2)*x(3))^(1/2)=12;@for(num_i(i):x(i)=0;);END股票组合投资问题的LINGO模型优化建模MODEL:sets:num_i/1,2,3/:c,x;num_j/1,2,3/;link(num_i,num_j):r;endsetsdata:c=0.920.640.41;r=180,36,110,36,120,-30,220,-30,140;enddata[OBJ]max=@sum(num_i(i):c(i)*x(i));x(1)+x(2)+x(3)=1;@sum(link(i,j):r(i,j)*x(i)*x(j))^(1/2)=12;@for(num_i(i):x(i)=0;);END优化建模2020年1月19日23运行该程序可得到结果:10.8593357x,230.1406643,0.000000xx，其目标函数的最优值为R=0.8806140．在保证标准差不超过12％的条件，五年有最大收益率的Ａ，Ｂ，Ｃ三支股票的组合投资比例分别为85.93％，14.07％，0％，其最高收益率可达到88.06％．股票组合投资问题的求解结果优化建模2020年1月19日24设一个战略轰炸机群奉命携带A、B两种型号的炸弹轰炸敌军的四个重要目标．为完成好此项任务要求飞机的耗油量不超过2700升，炸弹A和Ｂ都不超过4枚．已知飞机携带A型炸弹时每升油料可飞行2km,携带B型炸弹时每升油料可飞行3km，空载时每升油料可飞行4km,每次起降各消耗100升,每架飞机每次只能携带一枚炸弹．优化建模2020年1月19日25有关参数如下表所示．摧毁目标的可能性目标距离（km）ABⅠⅡⅢⅣ640850530720.650.500.560.680.760.700.720.66问题：如何制定轰炸方案，使摧毁所有目标的可能性最大？优化建模2020年1月19日26解设ijx表示飞机将第)2,1(ii种炸弹（A和B）投到第)4,3,2,1(jj个目标的炸弹数量;到四个目标的距离为(1,2,3,4)jsj；炸弹Ａ摧毁四个目标的可能性为(1,2,3,4)jaj；炸弹B摧毁四个目标的可能性为(1,2,3,4)jbj．优化建模2020年1月19日27问题要求摧毁所有四个目标的可能性最大，即每一个目标不被摧毁的可能性最小。问题的目标函数为1241min[(1)(1)]jjxxjjjzab．(1)飞机携带A型炸弹飞行一个来回每公里耗油量434121;优化建模2020年1月19日28(2)飞机携带B型炸弹飞行一个来回每公里耗油量1274131;(3)飞机一次起降需要100升,所以关于耗油量的约束为444121211137100()2700412jjjjjjjjjsxsxxx．优化建模2020年1月19日29(4)两种类型炸弹数量约束为12344(1,2).iii