《《非线性规划模型》PPT课件》由会员分享，可在线阅读，更多相关《《非线性规划模型》PPT课件（45页珍藏版）》请在金锄头文库上搜索。
1、5.5.非线性规划模型非线性规划模型 前面介绍了线性规划问题，即目标函数和约前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，即中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划问题的规划问题，即非线性规划问题. . 事实上，客观世界中的问题许多是非线事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的学的
2、假设和简化后得到的. 为了利用线性的为了利用线性的知识，许多非线性问题常进行线性化处理知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近处理的，否则将严重影响模型对实际问题近似的可依赖型似的可依赖型. 由于非线性规划问题在计算上常是困难的，由于非线性规划问题在计算上常是困难的，理论上的讨论也不能像线性规划那样给出简洁的理论上的讨论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论结果形式和全面透彻的结论. 这点又限制了非这点又限制了非线性规划的应用，所以，在数学建模时，要进行线性规划的应
3、用，所以，在数学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划时，则考虑用非线性规划.非线性规划问题的标准形式为：非线性规划问题的标准形式为：非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类： 无约束非线性规划模型：无约束非线性规划模型： 等式约束非线性规划模型：等式约束非线性规划模型： 不等式约束非线性规划模型：不等式约束非线性规划模型：1)1) 无约束的非线性规划问题无约束的非线性规划问题. .针对上
4、述三类非线性规划模型，其常用求解的基针对上述三类非线性规划模型，其常用求解的基本思路可归纳如下：本思路可归纳如下： 在下降迭代算法中，搜索方向起着关键的作在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好用，而当搜索方向确定后，步长又是决定算法好坏的重要因素坏的重要因素. 非线性规划只含一个变量，即一非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，维非线性规划可以用一维搜索方法求得最优解，一维搜索方法主要有进退法和黄金分割法一维搜索方法主要有进退法和黄金分割法. 二维二维的非线性规划也可以像解线性规划那样用图形求的非线性规划也可以像解线性规划
5、那样用图形求解解. 对于二维非线性规划，使用搜索方法是要用对于二维非线性规划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降到梯度的概念，最常用的搜索方法就是最速下降法法.2)2) 只有等式约束的非线性规划问题通常可用消只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为元法、拉格朗日乘子法或反函数法，将其化为无约束问题求解无约束问题求解. .3)3) 具有不等式约束的非线性规划问题解起来很具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等复杂，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，用线式约束，
6、再将约束问题化为无约束问题，用线性逼近的方法将非线性规划问题化为线性规划性逼近的方法将非线性规划问题化为线性规划问题问题. 下面介绍一个简单的非线性规划问题的下面介绍一个简单的非线性规划问题的例子，其中的一些约束条件是等式，这类非线例子，其中的一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解性规划问题可用拉格朗日方法求解. 例7（石油最优储存方法）有一石油运输公司，（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间为了减少开支，希望作了节省石油的存储空间. .但要求存储的石油能满足客户的要求但要求存储的石油能满足客户的要求. .为简化问为简化问题，假设只经
7、营两种油，各种符号表示的意义题，假设只经营两种油，各种符号表示的意义如表如表4 4所示所示. .其中供给率指石油公司供给客户的其中供给率指石油公司供给客户的速度速度. .表表4 4 各种符号表示意义表各种符号表示意义表第第i i种油的存种油的存储量量第第i i种油的价格种油的价格第第i i种油的供种油的供给率率第第i i种油的每种油的每单位的存位的存储费用用第第i i种油的每种油的每单位的存位的存储空空间总存存储公式公式由历史数据得到的经验公式为由历史数据得到的经验公式为 : :且提供数据如表且提供数据如表5 5所示：所示：表表5 5 数据表数据表已知已知总存存储空空间代入数据后得到的模型为：
8、代入数据后得到的模型为：模型求解：模型求解：拉格朗日函数的形式为：拉格朗日函数的形式为： 即即: :对 求各个求各个变量的偏量的偏导数，并令它数，并令它们等于等于零，得零，得: : 解这个线性方程组得：解这个线性方程组得：从而可得最小从而可得最小值是是 . 6 6、多目标规划模型、多目标规划模型 在许多实际问题中，衡量一个方案的好坏标在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高最远，又要燃料最省，还要精度最高. 这一类问这一类问题统称为多目标最优化问题或多目标规划问题题统称为多目标最优
9、化问题或多目标规划问题. 我们先来看一个生产计划的例子我们先来看一个生产计划的例子.我们希望购买我们希望购买DVDDVD的总数量最小，即的总数量最小，即 :由此，可以得到问题三的双目标整数线性规划模型由此，可以得到问题三的双目标整数线性规划模型如下：如下： 表表6 6 当当 时最小购买量的时最小购买量的 值值DVDDVD编号号D0D01 1D0D02 2D0D03 3D0D04 4D0D05 5D0D06 6D0D07 7D0D08 8D0D09 9D1D10 0最少最少购买量量1414212117172424121217171919212122221414DVDDVD编号号D1D11 1D1
10、D12 2D1D13 3D1D14 4D1D15 5D1D16 6D1D17 7D1D18 8D1D19 9D2D20 0最少最少购买量量1818181817171717171724241818161618182323DVDDVD编号号D2D21 1D2D22 2D2D23 3D2D24 4D2D25 5D2D26 6D2D27 7D2D28 8D2D29 9D3D30 0最少最少购买量量2020181822221414181817171515121216162424DVDDVD编号号D3D31 1D3D32 2D3D33 3D3D34 4D3D35 5D3D36 6D3D37 7D3D38
11、8D3D39 9D4D40 0最少最少购买量量1919222220201919222222221313171717171717DVDDVD编号号D4D41 1D4D42 2D4D43 3D4D44 4D4D45 5D4D46 6D4D47 7D4D48 8D4D49 9D5D50 0最少最少购买量量3232202016162121222216162020151520202020续上表DVDDVD编号号D5D51 1D5D52 2D5D53 3D5D54 4D5D55 5D5D56 6D5D57 7D5D58 8D5D59 9D6D60 0最少最少购买量量24241717191917171919
12、18181919171720202121DVDDVD编号号D6D61 1D6D62 2D6D63 3D6D64 4D6D65 5D6D66 6D6D67 7D6D68 8D6D69 9D7D70 0最少最少购买量量1616191919192020171719191717212120201919DVDDVD编号号D7D71 1D7D72 2D7D73 3D7D74 4D7D75 5D7D76 6D7D77 7D7D78 8D7D79 9D8D80 0最少最少购买量量2121222215152020151514141212171719191717DVDDVD编号号D8D81 1D8D82 2D8D
13、83 3D8D84 4D8D85 5D8D86 6D8D87 7D8D88 8D8D89 9D9D90 0最少最少购买量量1818101014141212212113132222151513131717DVDDVD编号号D9D91 1D9D92 2D9D93 3D9D94 4D9D95 5D9D96 6D9D97 7D9D98 8D9D99 9D1D10 00 0最少最少购买量量2424171715151414252515152222202011112222 我们利用规划模型求得每种我们利用规划模型求得每种DVDDVD的购买量后，需要的购买量后，需要对其进行可行性校验，测试此结果是否可以满足对
14、其进行可行性校验，测试此结果是否可以满足一个月内比例为一个月内比例为95%95%的会员得到他想看的的会员得到他想看的DVDDVD，且，且具有尽可能大的总体满意度具有尽可能大的总体满意度. .校验方法：校验方法： （一）根据订单和求得的（一）根据订单和求得的DVDDVD购买数量，利用购买数量，利用问题二的规划模型进行第一次分配，对分配情况：问题二的规划模型进行第一次分配，对分配情况：租赁的会员，租赁的会员，DVDDVD的分配情况，剩余的各种的分配情况，剩余的各种DVDDVD数数量作记录；同时将已租赁的会员在满意指数矩阵量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为的指数全变为0 0，即不
15、考虑对其进行第二次分配，即不考虑对其进行第二次分配. . （二）随机从第一次得到（二）随机从第一次得到DVDDVD的会员中抽取的会员中抽取60%60%，将这部分人所还回的，将这部分人所还回的DVDDVD与第一次分配余下的与第一次分配余下的DVDDVD合在一起，作为第二次分配时各种合在一起，作为第二次分配时各种DVDDVD的现有量的现有量. .然然后，利用问题二的后，利用问题二的0-10-1线性规划模型对第一次未分线性规划模型对第一次未分配到配到DVDDVD的会员进行第二次分配；的会员进行第二次分配； （三）统计出经过两次分配后，得到（三）统计出经过两次分配后，得到DVDDVD的会的会员的比例，
16、若大于员的比例，若大于95%95%，则此次分配成功，则此次分配成功. .利用这利用这种算法进行多次随机模拟，若大多数情况下可以种算法进行多次随机模拟，若大多数情况下可以使得到使得到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再见再见
