非线性规划多目标规划

1、5.5.非线性规划模型非线性规划模型 前面介绍了线性规划问题，即目标函数和约前面介绍了线性规划问题，即目标函数和约 束条件都是线性函数的规划问题，但在实际工作束条件都是线性函数的规划问题，但在实际工作 中，还常常会遇到另一类更一般的规划问题，即中，还常常会遇到另一类更一般的规划问题，即 目标函数和约束条件中至少有一个是非线性函数目标函数和约束条件中至少有一个是非线性函数 的规划问题，即非线性规划问题的规划问题，即非线性规划问题. . 由于非线性规划问题在计算上常是困难的，由于非线性规划问题在计算上常是困难的， 理论上的讨论也不能像线性规划那样给出简洁的理论上的讨论也不能像线性规划那样给出简洁的

2、 结果形式和全面透彻的结论结果形式和全面透彻的结论. 这点又限制了非这点又限制了非 线性规划的应用，所以，在数学建模时，要进行线性规划的应用，所以，在数学建模时，要进行 认真的分析，对实际问题进行合理的假设、简化，认真的分析，对实际问题进行合理的假设、简化， 首先考虑用线性规划模型，若线性近似误差较大首先考虑用线性规划模型，若线性近似误差较大 时，则考虑用非线性规划时，则考虑用非线性规划. 问题问题1 抽水费用最小问题抽水费用最小问题 某地区有某地区有3个泵站个泵站: 第第 个泵站的抽水费用为个泵站的抽水费用为 其中其中 为抽水流量为抽水流量. 泵站与各灌溉地块泵站与各灌溉地块 用渠道连接用渠

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

4、ij ij zf xfx 4 1 3 1 , 1,2,3 , 1,2,3,4 0. iji j ijijj i ij xQi c xbj x .st 设从泵站设从泵站 到地块到地块 的输水量为的输水量为ij, ij x 分析分析 问题的关键是确立决策变量和目标函数问题的关键是确立决策变量和目标函数. 注注: 在上面的问题中在上面的问题中, 输水费用函数输水费用函数 一般不是一般不是 的线性函数的线性函数. 因而相应的规划不是线性规划因而相应的规划不是线性规划. f xx 问题问题2 砂石运输问题砂石运输问题 设有设有 立方米的砂石立方米的砂石,要由甲地运到乙地要由甲地运到乙地, 运输前需运输前

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

6、 建模建模 设木箱的长宽高分别为设木箱的长宽高分别为 运费与成本费的总运费与成本费的总 和为和为 则目标函数为则目标函数为 123 ,x x x ,W 12312 13231 min 0.1/20 10405 , WVx x xx x x xx xx 0. i x 若在上述问题中若在上述问题中, 箱子的底与两侧使用废料来做箱子的底与两侧使用废料来做, 而而 废料只有废料只有4平方米平方米, 则问题为则问题为: 123231 min 0.1/405 ,WVx x xx xx 1312 . . 24.stx xx x 0. i x 在上面问题中在上面问题中, 目标函数与约束条件中的每一项可表达目标

7、函数与约束条件中的每一项可表达 成成 的形式（其中的的形式（其中的 为整数）为整数） , 数学上将其成为广义多项式数学上将其成为广义多项式, 相应的规划称为几何规划相应的规划称为几何规划. 当系数为正数时当系数为正数时, 规划称为正项几何规划规划称为正项几何规划. 312 123 n n ax x xx i 非线性规划问题的标准形式为非线性规划问题的标准形式为： min ( ) ( )0,1,2, . . ( )0,1,2, i j f x gxim s t hxjr 非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类： 无约束非线性规划模型：无约束非线性规划模型：

8、 等式约束非线性规划模型：等式约束非线性规划模型： min ( ) n f x xR min ( ) . . ( )0,1,2, j f x st h xjr 不等式约束非线性规划模型：不等式约束非线性规划模型： min ( ) . . ( )0,1,2, i f x st g xim 针对上述三类非线性规划模型，其常用求解的基针对上述三类非线性规划模型，其常用求解的基 本思路可归纳如下：本思路可归纳如下： 1) 无约束的非线性规划问题无约束的非线性规划问题 无约束非线性规划一般可写成无约束非线性规划一般可写成 min,f x 其中其中 1 12 ,. T n xx xxfC 解法解法 1.求

9、求 的梯度的梯度 f x , f 2.令梯度令梯度 解出解出 的驻点的驻点 0,f f x * 12 , T n x xx 3.验证验证 在该点的在该点的Hessian矩阵是否为正（负）定的矩阵是否为正（负）定的, 若成立若成立, 则该点为函数的极小（大）值点则该点为函数的极小（大）值点. f x 例例7 求函数求函数 的极小点的极小点. 22 12122 44412f xxxx xx 解解 的梯度为的梯度为 f x 1221 84,8412 ,fxxxx 令令 则驻点为则驻点为 函数的函数的Hessian阵为阵为0,f 1,2. T 2 12 2 2 84 . 48 f G x x x 注意

10、到该矩阵为正定阵注意到该矩阵为正定阵, 因而该点为极小值点因而该点为极小值点. 注意到此方法只有对一些特殊的函数才有效注意到此方法只有对一些特殊的函数才有效. 一般情一般情 况下况下, 要求出函数的驻点是比较困难的要求出函数的驻点是比较困难的. 下面我们简单下面我们简单 介绍求解该类问题的数值解法介绍求解该类问题的数值解法. f x1.给出给出 的极小点的极小点 的一个初始估计值的一个初始估计值 称为初称为初 始点始点; * x 0 ,x 2.如果如果 已求得已求得, 并且不是极小点并且不是极小点, 设法选取一个方向设法选取一个方向 （该方向称为搜索方向）（该方向称为搜索方向）, 使目标函数使

11、目标函数 沿该方沿该方 向是下降的（一般取梯度方向）向是下降的（一般取梯度方向）; , k x k s f x 3.在射线在射线 取适当的步长取适当的步长, 记记 0 kk xs , k , kkk k f xsf x 由此确定点由此确定点 其中的其中的 一般取使得一般取使得 上式取到极小值的值上式取到极小值的值. 1 , kkk k xxs k 4.检验检验 是否为函数是否为函数 的极小值的极小值, 或者满足或者满足 精度的要求精度的要求, 若不是若不是, 再回到第二步再回到第二步. 1k f x f x 2)2) 只有等式约束的非线性规划问题通常可用消只有等式约束的非线性规划问题通常可用消

12、 元法、拉格朗日乘子法或反函数法，将其化为元法、拉格朗日乘子法或反函数法，将其化为 无约束问题求解无约束问题求解. . 3)3) 具有不等式约束的非线性规划问题解起来很具有不等式约束的非线性规划问题解起来很 复杂，求解这一类问题，通常将不等式化为复杂，求解这一类问题，通常将不等式化为 等式约束，再将约束问题化为无约束问题，等式约束，再将约束问题化为无约束问题， 用线性逼近的方法将非线性规划问题化为线用线性逼近的方法将非线性规划问题化为线 性规划问题性规划问题. 下面介绍一个简单的非线性规划问题的下面介绍一个简单的非线性规划问题的 例子，其中的一些约束条件是等式，这类非线例子，其中的一些约束条件

13、是等式，这类非线 性规划问题可用拉格朗日方法求解性规划问题可用拉格朗日方法求解. 例8（石油最优储存方法）有一石油运输公司，（石油最优储存方法）有一石油运输公司， 为了减少开支，希望作了节省石油的存储空间为了减少开支，希望作了节省石油的存储空间. . 但要求存储的石油能满足客户的要求但要求存储的石油能满足客户的要求. .为简化问为简化问 题，假设只经营两种油，各种符号表示的意义题，假设只经营两种油，各种符号表示的意义 如表如表4 4所示所示. .其中供给率指石油公司供给客户的其中供给率指石油公司供给客户的 速度速度. . 表表4 4 各种符号表示意义表各种符号表示意义表 第第i i种油的存储量

14、种油的存储量 第第i i种油的价格种油的价格 第第i i种油的供给率种油的供给率 第第i i种油的每单位的存储费用种油的每单位的存储费用 第第i i种油的每单位的存储空间种油的每单位的存储空间 总存储公式总存储公式 i a i b i h i t T i x 由由历史数据得到的经验公式为历史数据得到的经验公式为 : : 且提供数据如表且提供数据如表5 5所示：所示： 1 11 12 222 12 12 121 122 min ( ,) 22 . . ( ,) abh xa bh x f x x xx st g x xt xt xT 表表5 5 数据表数据表 已知总存储空间已知总存储空间24T

15、代入数据后得到的模型为：代入数据后得到的模型为： 模型求解：模型求解： 拉格朗日函数的形式为：拉格朗日函数的形式为： 1212 12 12 2720 min ( ,)0.250.10 . 2424 f x xxx xx stxx 121212 ( , )( ,)( ,)L x xf x xg x xT 即即: : 121212 12 2720 ( , )0.250.102424L x xxxxx xx 2 11 2 22 12 27 0.2520 20 0.1040 24240 L xx L xx L xx 对对 求各个变量的偏导数，并令它们等求各个变量的偏导数，并令它们等 于零，得于零，得:

16、 : 12 ( , )L x x 解这个线性方程组得：解这个线性方程组得： 1212 5.0968,3.4516,0.3947,( ,)12.71xxf x x 从而可得最小值是从而可得最小值是 . 12.71 非线性规划解法非线性规划解法 例例9 求解非线性规划求解非线性规划 22 12 min (1.5)zxx 22 12 12 12 1, 21, ,0. xx xx x x . .st 解解1 图解法图解法 1 x 2 x 3.25f 0.25f 1,0 解解2 用用Lingo软件求解软件求解 min=(x1-1.5)2+x22; x12+x22=1; Local optimal sol

17、ution found. Objective value: 0.2500004 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.000000 6 6、多目标规划模型、多目标规划模型 在许多实际问题中，衡量一个方案

18、的好坏标在许多实际问题中，衡量一个方案的好坏标 准往往不止一个，例如设计一个导弹，既要射程准往往不止一个，例如设计一个导弹，既要射程 最远，又要燃料最省，还要精度最高最远，又要燃料最省，还要精度最高. 这一类问题这一类问题 统称为多目标最优化问题或多目标规划问题统称为多目标最优化问题或多目标规划问题. 我们我们 先来看一个生产计划的例子先来看一个生产计划的例子. 123 ,x xx 我们希望购买我们希望购买DVDDVD的总数量最小，即的总数量最小，即 : 100 1 min j j zy 由此，可以得到问题三的双目标整数线性规划模型由此，可以得到问题三的双目标整数线性规划模型 如下：如下： 1

19、00 1 1000 100 11 1000 100 11 1000 1 100 1 min 1 max 27000 100030.95 1.61,100 301,1000 . . 1,10001,100 011,10001, j j ijij ij ij ij ijj i iji j ijij ij zy wc x x xyj xzi s t xcij xij 或 100 011,1000 1,100 i j zi yj 或 取整 100 1 1000 100 11 1000 1 100 1 1000 100 11 min 100030.95 1.61,100 301,1000 . . 1 2

20、7000 1,10001,100 011,10001,1 j j ij ij ijj i iji j ijij ij ijij ij zy x xyj xzi s t c x xcij xij 或 00 011,1000 1,100 i j zi yj 或 取整 表表6 6 当当 时最小购买量的时最小购买量的 值值 (1,2,.,100) j yj DVDDVD编号编号D01D01D02D02D03D03D04D04D05D05D06D06D07D07D08D08D09D09D10D10 最少购买量最少购买量1414212117172424121217171919212122221414 DV

21、DDVD编号编号D11D11D12D12D13D13D14D14D15D15D16D16D17D17D18D18D19D19D20D20 最少购买量最少购买量1818181817171717171724241818161618182323 DVDDVD编号编号D21D21D22D22D23D23D24D24D25D25D26D26D27D27D28D28D29D29D30D30 最少购买量最少购买量2020181822221414181817171515121216162424 DVDDVD编号编号D31D31D32D32D33D33D34D34D35D35D36D36D37D37D38D38

22、D39D39D40D40 最少购买量最少购买量1919222220201919222222221313171717171717 DVDDVD编号编号D41D41D42D42D43D43D44D44D45D45D46D46D47D47D48D48D49D49D50D50 最少购买量最少购买量3232202016162121222216162020151520202020 0.95 续上表 DVDDVD编号编号D51D51D52D52D53D53D54D54D55D55D56D56D57D57D58D58D59D59D60D60 最少购买量最少购买量242417171919171719191818

23、1919171720202121 DVDDVD编号编号D61D61D62D62D63D63D64D64D65D65D66D66D67D67D68D68D69D69D70D70 最少购买量最少购买量1616191919192020171719191717212120201919 DVDDVD编号编号D71D71D72D72D73D73D74D74D75D75D76D76D77D77D78D78D79D79D80D80 最少购买量最少购买量2121222215152020151514141212171719191717 DVDDVD编号编号D81D81D82D82D83D83D84D84D85D8

24、5D86D86D87D87D88D88D89D89D90D90 最少购买量最少购买量1818101014141212212113132222151513131717 DVDDVD编号编号D91D91D92D92D93D93D94D94D95D95D96D96D97D97D98D98D99D99D100D100 最少购买量最少购买量2424171715151414252515152222202011112222 我们利用规划模型求得每种我们利用规划模型求得每种DVDDVD的购买量后，需要的购买量后，需要 对其进行可行性校验，测试此结果是否可以满足对其进行可行性校验，测试此结果是否可以满足 一个月内比例为一个月内比例为95%95%的会员得到他想看的的会员得到他想看的DVDDVD，且，且 具有尽可能大的总体满意度具有尽可能大的总体满意度. . 校验方法：校验方法： （一）根据订单和求得的（一）根据订单和求得的DVDDVD购买数量，利用购买数量，利用 问题二的规划模型进行第一次分配，对分配情况：问题二的规划模型进行第一次分配，对分配情况： 租赁的会员，租赁的会员，DVDDVD的分配情况，剩余的各种的