非线性规划多目标规划课件.ppt

1、 由于非线性规划问题在计算上常是困难的，由于非线性规划问题在计算上常是困难的，理论上的讨论也不能像线性规划那样给出简洁的理论上的讨论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论结果形式和全面透彻的结论.这点又限制了非这点又限制了非线性规划的应用，所以，在数学建模时，要进行线性规划的应用，所以，在数学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划时，则考虑用非线性规划.问题问题1 抽水费用最小问题抽水费用最小问题 某地区有某地

2、区有3个泵站个泵站:第第 个泵站的抽水费用为个泵站的抽水费用为 其中其中 为抽水流量为抽水流量.泵站与各灌溉地块泵站与各灌溉地块用渠道连接用渠道连接.在一个灌溉周期中在一个灌溉周期中,地块地块 需流量需流量 立方立方米米/小时小时.泵站泵站 的最大抽水能力为的最大抽水能力为 由于渗透和蒸发由于渗透和蒸发,从从 泵站到泵站到 地块的水量要打一折扣地块的水量要打一折扣,即乘上系数即乘上系数 称称为水的实用系数为水的实用系数.问应如何确定每一泵站的输水量问应如何确定每一泵站的输水量,才才能使总的抽水费用为最小能使总的抽水费用为最小?试建立相应的数学模型试建立相应的数学模型.123,.A A Ai,i

3、fxx1234,B B B BjBjbiA,iQij.ijc 3411min iijijzf xfx4131,1,2,3,1,2,3,4 0.ijijijijjiijxQic xbjx.st 设从泵站设从泵站 到地块到地块 的输水量为的输水量为ij,ijx 分析分析 问题的关键是确立决策变量和目标函数问题的关键是确立决策变量和目标函数.注注:在上面的问题中在上面的问题中,输水费用函数输水费用函数 一般不是一般不是的线性函数的线性函数.因而相应的规划不是线性规划因而相应的规划不是线性规划.f xx 问题问题2 砂石运输问题砂石运输问题 设有设有 立方米的砂石立方米的砂石,要由甲地运到乙地要由甲地

4、运到乙地,运输前需运输前需先装入一个有底无盖并在底部装有滑行器的木箱中先装入一个有底无盖并在底部装有滑行器的木箱中.砂砂石运到乙地后石运到乙地后,从箱中倒出从箱中倒出,在继续用空箱装运在继续用空箱装运.不论箱不论箱子大小子大小,每装运一箱每装运一箱,需需0.1元元,箱底和两端的材料费为箱底和两端的材料费为20元元/米米2,箱子两侧的材料费为箱子两侧的材料费为5元元/米米2,箱底的两个滑箱底的两个滑行器与箱子同长行器与箱子同长,材料费为材料费为2.5元元/米米.问木箱的长宽高各问木箱的长宽高各为多少米为多少米,才能使运费与箱子的成本费的总和为最小才能使运费与箱子的成本费的总和为最小.V 建模建模

5、 设木箱的长宽高分别为设木箱的长宽高分别为 运费与成本费的总运费与成本费的总和为和为 则目标函数为则目标函数为123,x x x,W123121 3231min 0.1/20 10405,WVx x xx xx xx xx 0.ix 若在上述问题中若在上述问题中,箱子的底与两侧使用废料来做箱子的底与两侧使用废料来做,而而废料只有废料只有4平方米平方米,则问题为则问题为:123231min 0.1/405,WVx x xx xx1 312.24.stx xx x 0.ix 在上面问题中在上面问题中,目标函数与约束条件中的每一项可表达目标函数与约束条件中的每一项可表达成成 的形式（其中的的形式（其

6、中的 为整数）为整数）,数学上将其成为广义多项式数学上将其成为广义多项式,相应的规划称为几何规划相应的规划称为几何规划.当系数为正数时当系数为正数时,规划称为正项几何规划规划称为正项几何规划.312123nnax x xxi非线性规划问题的标准形式为：非线性规划问题的标准形式为：min ()()0,1,2,.()0,1,2,ijfxgxims thxjr非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类：无约束非线性规划模型：无约束非线性规划模型：等式约束非线性规划模型：等式约束非线性规划模型：min()nf xxRmin().()0,1,2,jf xst h xj

7、r 不等式约束非线性规划模型：不等式约束非线性规划模型：min().()0,1,2,if xst g xim针对上述三类非线性规划模型，其常用求解的基针对上述三类非线性规划模型，其常用求解的基本思路可归纳如下：本思路可归纳如下：1)无约束的非线性规划问题无约束的非线性规划问题 无约束非线性规划一般可写成无约束非线性规划一般可写成 min,f x其中其中 112,.Tnxx xxfC解法解法 1.求求 的梯度的梯度 f x,f2.令梯度令梯度 解出解出 的驻点的驻点0,f f x*12,Tnx xx3.验证验证 在该点的在该点的Hessian矩阵是否为正（负）定的矩阵是否为正（负）定的,若成立若

8、成立,则该点为函数的极小（大）值点则该点为函数的极小（大）值点.f x例例7 求函数求函数 的极小点的极小点.221212244412f xxxx xx解解 的梯度为的梯度为 f x122184,8412,fxxxx 令令 则驻点为则驻点为 函数的函数的Hessian阵为阵为0,f 1,2.T 2122 284.48fG xx x 注意到该矩阵为正定阵注意到该矩阵为正定阵,因而该点为极小值点因而该点为极小值点.注意到此方法只有对一些特殊的函数才有效注意到此方法只有对一些特殊的函数才有效.一般情一般情况下况下,要求出函数的驻点是比较困难的要求出函数的驻点是比较困难的.下面我们简单下面我们简单介绍

9、求解该类问题的数值解法介绍求解该类问题的数值解法.f x1.给出给出 的极小点的极小点 的一个初始估计值的一个初始估计值 称为初称为初始点始点;*x 0,x2.如果如果 已求得已求得,并且不是极小点并且不是极小点,设法选取一个方向设法选取一个方向 （该方向称为搜索方向）（该方向称为搜索方向）,使目标函数使目标函数 沿该方沿该方向是下降的（一般取梯度方向）向是下降的（一般取梯度方向）;,kx ks f x3.在射线在射线 取适当的步长取适当的步长,记记 0kkxs,k ,kkkkf xsf x由此确定点由此确定点 其中的其中的 一般取使得一般取使得上式取到极小值的值上式取到极小值的值.1,kkk

10、kxxsk4.检验检验 是否为函数是否为函数 的极小值的极小值,或者满足或者满足精度的要求精度的要求,若不是若不是,再回到第二步再回到第二步.1kf x f x2)2)只有等式约束的非线性规划问题通常可用消只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为元法、拉格朗日乘子法或反函数法，将其化为无约束问题求解无约束问题求解.3)3)具有不等式约束的非线性规划问题解起来很具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为复杂，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，等式约束，再将约束问题化为无约束问题，用线性逼近

11、的方法将非线性规划问题化为线用线性逼近的方法将非线性规划问题化为线性规划问题性规划问题.下面介绍一个简单的非线性规划问题的下面介绍一个简单的非线性规划问题的例子，其中的一些约束条件是等式，这类非线例子，其中的一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解性规划问题可用拉格朗日方法求解.例8（石油最优储存方法）有一石油运输公司，（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间为了减少开支，希望作了节省石油的存储空间.但要求存储的石油能满足客户的要求但要求存储的石油能满足客户的要求.为简化问为简化问题，假设只经营两种油，各种符号表示的意义题，假设只经营两种

12、油，各种符号表示的意义如表如表4 4所示所示.其中供给率指石油公司供给客户的其中供给率指石油公司供给客户的速度速度.表表4 4 各种符号表示意义表各种符号表示意义表第第i i种油的存储量种油的存储量第第i i种油的价格种油的价格第第i i种油的供给率种油的供给率第第i i种油的每单位的存储费用种油的每单位的存储费用第第i i种油的每单位的存储空间种油的每单位的存储空间总存储公式总存储公式iaibihitTix由历史数据得到的经验公式为由历史数据得到的经验公式为 :且提供数据如表且提供数据如表5 5所示：所示：1 11 12 2221212121 122min(,)22.(,)abh xa bh

13、 xf x xxxst g x xt xt xT表表5 5 数据表数据表已知总存储空间已知总存储空间24T 代入数据后得到的模型为：代入数据后得到的模型为：模型求解：模型求解：拉格朗日函数的形式为：拉格朗日函数的形式为：121212122720min(,)0.250.10.2424f x xxxxxstxx 121212(,)(,)(,)L x xf x xg x xT即即:121212122720(,)0.250.102424L x xxxxxxx21122212270.2520200.104024240LxxLxxLxx 对对 求各个变量的偏导数，并令它们等求各个变量的偏导数，并令它们等于

14、零，得于零，得:12(,)L x x解这个线性方程组得：解这个线性方程组得：12125.0968,3.4516,0.3947,(,)12.71xxf x x从而可得最小值是从而可得最小值是 .12.71 非线性规划解法非线性规划解法例例9 求解非线性规划求解非线性规划2212min (1.5)zxx221212121,21,0.xxxxx x.st解解1 图解法图解法1x2x3.25f 0.25f 1,0解解2 用用Lingo软件求解软件求解min=(x1-1.5)2+x22;x12+x22=1;Local optimal solution found.Objective value:0.25

15、00004 Extended solver steps:5 Total solver iterations:25 Variable Value Reduced Cost X1 0.9999996 0.000000 X2 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.2500004 -1.000000 2 0.8162711E-06 0.5000006 3 0.9999992 0.0000006 6、多目标规划模型、多目标规划模型 在许多实际问题中，衡量一个方案的好坏标在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个

16、导弹，既要射程准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高最远，又要燃料最省，还要精度最高.这一类问题这一类问题统称为多目标最优化问题或多目标规划问题统称为多目标最优化问题或多目标规划问题.我们我们先来看一个生产计划的例子先来看一个生产计划的例子.123,x xx我们希望购买我们希望购买DVDDVD的总数量最小，即的总数量最小，即:1001minjjzy由此，可以得到问题三的双目标整数线性规划模型由此，可以得到问题三的双目标整数线性规划模型如下：如下：10011000 100111000 10011100011001min1max27000100030.951.6

17、1,100301,1000.1,10001,100011,10001,jjijijijijijijjiijijijijijzywc xxxyjxzis txcijxij 或 100011,10001,100ijziyj或取整 10011000 100111000110011000 10011min100030.951.61,100301,1000.1270001,10001,100011,10001,1jjijijijjiijijijijijijijijzyxxyjxzis tc xxcijxij 或 00011,10001,100ijziyj或 取整表表6 6 当当 时最小购买量的时最小购买

18、量的 值值(1,2,.,100)jyj DVDDVD编编号号D0D01 1D0D02 2D0D03 3D0D04 4D0D05 5D0D06 6D0D07 7D0D08 8D0D09 9D1D10 0最少购最少购买买量量1414212117172424121217171919212122221414DVDDVD编编号号D1D11 1D1D12 2D1D13 3D1D14 4D1D15 5D1D16 6D1D17 7D1D18 8D1D19 9D2D20 0最少购最少购买买量量1818181817171717171724241818161618182323DVDDVD编编号号D2D21 1D2D

19、22 2D2D23 3D2D24 4D2D25 5D2D26 6D2D27 7D2D28 8D2D29 9D3D30 0最少购最少购买买量量2020181822221414181817171515121216162424DVDDVD编编号号D3D31 1D3D32 2D3D33 3D3D34 4D3D35 5D3D36 6D3D37 7D3D38 8D3D39 9D4D40 0最少购最少购买买量量19192222202019192222222213131717171717170.95续上表DVDDVD编编号号D5D51 1D5D52 2D5D53 3D5D54 4D5D55 5D5D56 6D

20、5D57 7D5D58 8D5D59 9D6D60 0最少购最少购买买量量2424171719191717191918181919171720202121DVDDVD编编号号D6D61 1D6D62 2D6D63 3D6D64 4D6D65 5D6D66 6D6D67 7D6D68 8D6D69 9D7D70 0最少购最少购买买量量1616191919192020171719191717212120201919DVDDVD编编号号D7D71 1D7D72 2D7D73 3D7D74 4D7D75 5D7D76 6D7D77 7D7D78 8D7D79 9D8D80 0最少购最少购买买量量212

21、1222215152020151514141212171719191717DVDDVD编编号号D8D81 1D8D82 2D8D83 3D8D84 4D8D85 5D8D86 6D8D87 7D8D88 8D8D89 9D9D90 0最少购最少购买买量量1818101014141212212113132222151513131717 我们利用规划模型求得每种我们利用规划模型求得每种DVDDVD的购买量后，需要的购买量后，需要对其进行可行性校验，测试此结果是否可以满足对其进行可行性校验，测试此结果是否可以满足一个月内比例为一个月内比例为95%95%的会员得到他想看的的会员得到他想看的DVDDVD

22、，且，且具有尽可能大的总体满意度具有尽可能大的总体满意度.校验方法：校验方法：（一）根据订单和求得的（一）根据订单和求得的DVDDVD购买数量，利用购买数量，利用问题二的规划模型进行第一次分配，对分配情况：问题二的规划模型进行第一次分配，对分配情况：租赁的会员，租赁的会员，DVDDVD的分配情况，剩余的各种的分配情况，剩余的各种DVDDVD数数量作记录；同时将已租赁的会员在满意指数矩阵量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为的指数全变为0 0，即不考虑对其进行第二次分配，即不考虑对其进行第二次分配.（二）随机从第一次得到（二）随机从第一次得到DVDDVD的会员中抽取的会员中抽取6

23、0%60%，将这部分人所还回的将这部分人所还回的DVDDVD与第一次分配余下的与第一次分配余下的DVDDVD合合在一起，作为第二次分配时各种在一起，作为第二次分配时各种DVDDVD的现有量的现有量.然后，然后，利用问题二的利用问题二的0-10-1线性规划模型对第一次未分配到线性规划模型对第一次未分配到DVDDVD的会员进行第二次分配；的会员进行第二次分配；（三）统计出经过两次分配后，得到（三）统计出经过两次分配后，得到DVDDVD的会的会员的比例，若大于员的比例，若大于95%95%，则此次分配成功，则此次分配成功.利用这利用这种算法进行多次随机模拟，若大多数情况下可以种算法进行多次随机模拟，若

24、大多数情况下可以使得到使得到DVDDVD的会员大于的会员大于95%95%，则认为模型三是合理，则认为模型三是合理的的.校验结果：校验结果：因为每次检验需时约因为每次检验需时约1 1小时，我们只对问题小时，我们只对问题三求得的结果进行了三求得的结果进行了7 7次模拟，其中次模拟，其中6 6次符合要求次符合要求（观看比例大于（观看比例大于95%95%）.下面给出下面给出7 7次模拟得到的次模拟得到的观看比例（表观看比例（表7 7）：）：表表7 77 7次模拟结果每次的观看比例列表次模拟结果每次的观看比例列表验证次数验证次数1 12 23 34 45 56 67 7观看比例观看比例95.895.896.696.693.493.495.395.395.995.996.196.195.795.7