非线性规划模型

《非线性规划模型》由会员分享，可在线阅读，更多相关《非线性规划模型（10页珍藏版）》请在金锄头文库上搜索。

1、2.72.7 非线性规划模型非线性规划模型在现实问题中，大量的问题是非线性的。因此，除线性规划外，应用更多的是非 线性规划。本节简单介绍非线性规划的有关概念。 一一. . 引例引例 例例 1如图 2-68，预建一猪舍， 围墙与隔墙的总长不能超过 40 米，问长、 宽各多少时，面积最大？设长、宽分别是米、米时，问1x2x题即为下述优化问题：求 0,4052max212121xxxxstxx易知，本问题的最优解是. 4,1021xx例例 2某企业生产一种产品，其生产要素（可以是某种原材料，也可以是劳力、资本等）编号为. 已知该产品的生产函数为(第n, 2 , 1L),(21nxxxgL种生产要素的

2、投入量为时的产品产出量)一般为非线性函数,设给定产品的总产量为iix,第 种生产要素的单位生产费用为,问如何安排生产成本最低?aiic数学模型为: 0),(min21iniixaxxxgstxc L例例 3最优国民经济计划模型国民经济由个部门所组成, 编号为,各部门间直接消耗的系数矩阵为nn, 2 , 1L,为第 个部门生产价值一个单位的产品直接消耗部门产品的价值 n jiijaA1, ijaij单位, 部门的生产函数其中为第 部门总产品的价值.j),(iiiiKLfx ixi44444434444442111x2x 图 2-68为投入 部门的资金数为投入 部门的劳力数.问在总劳动力,资金给定

3、的前iKiiLiLK提下,如何安排各部门的资金数及劳力投入,可使国民收入最大?设表示第 部门最终产品的总价值,则数学模型为iyi0,),(maxiiiiiiiiiiijijiiKLyxLKfxKKLLyxaxsty例例 4确定经验公式非线性回归分析设(, ) ()为实际问题中的一组数据,且与有关系itiyni, 2, 1Liyit,现求系数使得与数据组“最接近”。化为数学问ctbeaycba,ctbeay题,即求0,)(min21cbabeayictkii一般地，称min ),(1nxxfLs.t. mixxgni，LL, 1, 0),(1ljxxhnj, 1, 0),(1LL为规划问题规划问

4、题(或称为条件极值问题)。特别特别 1. 当为线性函数，为二次函数，称上述问题为二次规划；jihg ,f2. 当均为线性函数，称上述问题为线性规划。fhgji,称为约束条件，称为目标函数。0, 0jihgf二二. . 二变量非线性规划问题的图解法二变量非线性规划问题的图解法 考虑规划问题min ),(21xxfs.t. 0),(21xxgi0),(21xxhj可以用图解法求出.先给出若干概念. 1.约束集合约束集合 首先我们知道,在平面上,一个不等式可确定一个区域。如：，表示上方部分；，02 yx2xy 122 yx表示内部部分等.122 yx一个等式可确定一条曲线。 将所有不等式、等式确定的

5、区域的公共部分称为约约 束集合束集合。 2.等高线等高线对于目标函数，=取定值时，),(21xxf),(21xxfz确定平面上一条曲线，而，取不同值为平面上一条曲线。对应于该曲),(21xxfz z线上的点，其函数值相同，称这些曲线为等高线等高线。例例 5. 的等高线为一族以2 22 121),(xxxxfz原点为圆心的同心圆，时，这些同心圆半径cz 为。随着圆的半径增大，圆上的函数值增大c（如图 2-69） 。例例 6. 的等高线也为一2 22 1211),(xxxxfz族以原点为圆心的同心圆，半径为。随着圆c1图 2-69图 2-70的半径扩大，圆上的函数值变小。 （见图 2-70） 。3

6、.几何意义及图解法几何意义及图解法 例例 7. 非线性规划问题min 2 22 1)2()2(xx12 22 1 xxst0ix的可行域（约束集合）如图 2-71 阴影部分，最 优解为（0，0）. 解“猪舍问题” （例 1）04052. .max2121ixxxtsxx可行域即图 2-72 阴影部分，做出等高线，取，cxx2130,40,50,60c易知最优解为与4021xx的交点405221 xx).4 ,10(三三. 函数的梯度及最速下降法函数的梯度及最速下降法 约束问题转化为无约束问题(如 Lagrange 乘数法)后可用最速下降法求解。 1.求解无约束极值多元函数极值求解无约束极值多元

7、函数极值min ),()(1nxxfxfL经典数学方法：令 ，解得驻点，是否极值点？看矩阵nif ix, 2 , 1, 0L的正定性即可，从)( jixxf0)()(),(010 1100 1x nnnnfxxxxxxxxffLL5 5 2468 图 2-72 2 12图 2-71)()()(22010 110ix nnnxofxxxxxxL)()()(,(),(200 11 000 1100 1 innnnxxnnnxoxxxxxfxxxxxxf jiMLL当矩阵正定时，在取极小；nnxxxf ji)(0 )(xf0x当矩阵负定时，在取极大。nnxxxf ji)(0 )(xf0x这种做法的困

8、难是这种做法的困难是要解方程组；判定正定性。122.规划方法规划方法 首先回顾梯度的性质：在给定点的负梯度即是函数1)(xf0x)(,()(0021xfffxf nxxxxL在点下降最快的方向；)(xf0x时，梯度方向为曲线在的法向。22n),(),(0 20 121xxfxxf 0 20 1 xx最速下降法最速下降法：我们假设稳定点又是最优点。给定初始点，若，T nxxx),(00 10L0)(0xfx则即为最优点；0x否则，则按梯度意义，为下降最快的方向，沿0)(0 1xfx)(0xfxf方向，求，使（其中)(00xfzx0)()(min0 000 00zxfzxf 是的一元函数） 。)(

9、0 0zxf令，则0 001zxx)()(01xfxf（，特别取，有）)()(, 0000 00zxfzxfQ0)()(01xfxf从依次迭代即可得到最优解。1x步骤：1.取初始点；0,0x2.若，止；222)()()()( 21k xk xk xk xxfxfxfxf nL3.计算，求极值；)(k xxf)()(mink kkkkzxfzxf4.令，转 2。k kkkzxx11: kk例例 9. 求无约束问题。2 22 1) 1(4) 1(minxx解：1. 取；4)(10)0, 1 (020xfxT2. ；)8, 0() 1(8),1(2021xxxxf3. ； 8 xf4. ；8/1,)

10、 18(4)8, 1 (min)8 . 0(min20fxf5. 。0)(,) 1, 1 ()8, 0(81101xfxxxTT故 。Txf) 1, 1 (, 0* min四四. 罚函数法罚函数法 考虑非线性规划问题)(minxfst 0)(0)(xhxgji引入函数 0,0, 0)2(), 0(min)(222ttttttt tttt, 0min20,20, 0 用构造函数)(t22112)()(, 0(min)()()()(),(xhxgMxfxhxgMxfMxTjimiljji其中是一个很大的数。M由的定义，及约束条件的集合为，故0)(, 0)(xhxgxRji， RxxfRxxfMxT

11、),(),(),(由于时，Rx0)()(, 0min(22xhxgji及为很大的正数，故也是一个很大的正数。于是，当时，MMRx也是很大的数。MxfMxT)(),(我们称函数为罚函数罚函数，称为罚款项罚款项，称为罚因子罚因子。),(MxTM对于固定的，为的函数。下面求无条件约束问题的最优解。 （可用M),(MxTx最速下降法）设其最优解为。由于为很大的数，故无约束问题的最优x ),(MxT),(minMxT解应满足条件。x Rx 可以证明：的最优解为规划问题),(minMxTx 图 2-73 0)(0)()(minxhxgstxfji的最优解。这里取多大合适，我们事先不知道。但从上述结论，若对

12、，M1MM 的最优解，则为原规划问题的最优解。),(min1MxTRx x否则，则说明不够大。从而取，再求解Rx 1M1210MMM。),(min2MxT依次下去，若求得的最优解，则为原问题的最优解。),(minkMxTRxkkx或与足够接近，如：，迭代停止。否则，kxR)(,)(kjk ixhxg令，继续上述步骤。kkMMM101这个方法称为罚函数方法罚函数方法。 罚函数方法的实际意义：考虑我们购买中货物，对每种货物的采购量分别为，则我n, 2, 1Lnxx,1L们把目标函数),()(1nxxfxfL看成采购量分别为时，所需总钱数。nxx,1L约束集合，理解为某种“规定” 。因此，非线性规划

13、问题 0)(0)()(minxhxgstxfji的经济意义为：在“规定”的范围内购物，使花钱最少。对于罚函数，的意义是：),(kMxT相对“规定”制定一种“罚款”政策。若符合规定（即） ，则罚款为 0。若Rx 违反规定，则需交纳一笔正罚款（即罚款项）2121)()(, 0(min ljjkmii kkxhMxgM于是，罚函数即为采购的总代价。),(kMxT不难理解，当很大时，相当于对违反“规定”的采购规定了苛刻的罚款，这kM当然不合算。于是迫使我们在考虑总代价为最小时，要符合规定。在数学上表现为：当很大时，无约束极值问题的最优解应满足约束条件，kMkx即。Rxk例例 10. 利用罚函数法求解0

14、min xstx解解： ), 0(min),(2xMxMxT2)2(xxMx0,210, 1),(2xxMxMxTkkx若为极值，则。故无约束问题的最优解满足，即x0),(kxMxT021xMk。kMx21当时，得。k021limkMx例例 11. 解非线性规划问题解非线性规划问题 01min3212 32 22 1 xxxstxxx解： 2 3212 32 22 1) 1(),(xxxMxxxMxTk0) 1(22) 1(22) 1(22),(321332123211 xxxMxxxxMxxxxMxMxTkkkkx得0) 1(220) 1(220) 1(22321332123211xxxMxxxxMxxxxMxkkk解得03)(3)(321321kkMxxxMxxx得kk MMxxx313321kkkk kMM MMMxxx31)1313(321，有。k