数学建模规划理论及模型省公共课一等奖全国赛课获奖课件.pptx

5.5.5.5.非线性规划模型非线性规划模型非线性规划模型非线性规划模型 前面介绍了线性规划问题，即目标函数和约前面介绍了线性规划问题，即目标函数和约束条件都是线性函数规划问题，但在实际工作中，束条件都是线性函数规划问题，但在实际工作中，还经常会碰到另一类更普通规划问题，即目标函还经常会碰到另一类更普通规划问题，即目标函数和约束条件中最少有一个是非线性函数规划问数和约束条件中最少有一个是非线性函数规划问题，即非线性规划问题题，即非线性规划问题.第1页 实际上，客观世界中问题许多是非线性，实际上，客观世界中问题许多是非线性，给予线性大多是近似，是在作了科学假设和给予线性大多是近似，是在作了科学假设和简化后得到简化后得到.为了利用线性知识，许多非线为了利用线性知识，许多非线性问题常进行线性化处理性问题常进行线性化处理.但在实际问题中，但在实际问题中，有一些是不能进行线性化处理，不然将严重有一些是不能进行线性化处理，不然将严重影响模型对实际问题近似可依赖型影响模型对实际问题近似可依赖型.第2页 因为非线性规划问题在计算上常是困难，因为非线性规划问题在计算上常是困难，理论上讨论也不能像线性规划那样给出简练结果理论上讨论也不能像线性规划那样给出简练结果形式和全方面透彻结论形式和全方面透彻结论.这点又限制了非线性这点又限制了非线性规划应用，所以，在数学建模时，要进行认真分规划应用，所以，在数学建模时，要进行认真分析，对实际问题进行合理假设、简化，首先考虑析，对实际问题进行合理假设、简化，首先考虑用线性规划模型，若线性近似误差较大时，则考用线性规划模型，若线性近似误差较大时，则考虑用非线性规划虑用非线性规划.第3页非线性规划问题标准形式为：非线性规划问题标准形式为：非线性规划问题标准形式为：非线性规划问题标准形式为：第4页非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类：无约束非线性规划模型：无约束非线性规划模型：等式约束非线性规划模型：等式约束非线性规划模型：第5页 不等式约束非线性规划模型：不等式约束非线性规划模型：1)1)无约束非线性规划问题无约束非线性规划问题.针对上述三类非线性规划模型，其惯用求解基本针对上述三类非线性规划模型，其惯用求解基本思绪可归纳以下：思绪可归纳以下：第6页第7页第8页 在下降迭代算法中，搜索方向起着关键作用，在下降迭代算法中，搜索方向起着关键作用，而当搜索方向确定后，步长又是决定算法好坏主而当搜索方向确定后，步长又是决定算法好坏主要原因要原因.非线性规划只含一个变量，即一维非线非线性规划只含一个变量，即一维非线性规划能够用一维搜索方法求得最优解，一维搜性规划能够用一维搜索方法求得最优解，一维搜索方法主要有进退法和黄金分割法索方法主要有进退法和黄金分割法.二维非线性二维非线性规划也能够像解线性规划那样用图形求解规划也能够像解线性规划那样用图形求解.对于对于二维非线性规划，使用搜索方法是要用到梯度概二维非线性规划，使用搜索方法是要用到梯度概念，最惯用搜索方法就是最速下降法念，最惯用搜索方法就是最速下降法.第9页2)2)只有等式约束非线性规划问题通常可用消元只有等式约束非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为无法、拉格朗日乘子法或反函数法，将其化为无约束问题求解约束问题求解.3)3)含有不等式约束非线性规划问题解起来很复含有不等式约束非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式杂，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，用线性约束，再将约束问题化为无约束问题，用线性迫近方法将非线性规划问题化为线性规划问题迫近方法将非线性规划问题化为线性规划问题.下面介绍一个简单非线性规划问题例子，下面介绍一个简单非线性规划问题例子，其中一些约束条件是等式，这类非线性规划问其中一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解题可用拉格朗日方法求解.第10页 例7（石油最优储存方法）有一石油运输企业，（石油最优储存方法）有一石油运输企业，为了降低开支，希望作了节约石油存放空间为了降低开支，希望作了节约石油存放空间.但但要求存放石油能满足客户要求要求存放石油能满足客户要求.为简化问题，假为简化问题，假设只经营两种油，各种符号表示意义如表设只经营两种油，各种符号表示意义如表4 4所表所表示示.其中供给率指石油企业供给客户速度其中供给率指石油企业供给客户速度.第11页表表表表4 4 4 4 各种符号表示意义表各种符号表示意义表各种符号表示意义表各种符号表示意义表第第i种油存放量种油存放量第第i种油价格种油价格第第i种油供给率种油供给率第第i种油每单位存放费用种油每单位存放费用第第i种油每单位存放空间种油每单位存放空间总存放公式总存放公式第12页由历史数据得到经验公式为由历史数据得到经验公式为:且提供数据如表且提供数据如表5 5所表示：所表示：第13页表表5 5 数据表数据表已知已知总总存放空存放空间间第14页代入数据后得到模型为：代入数据后得到模型为：模型求解：模型求解：拉格朗日函数形式为：拉格朗日函数形式为：第15页即即即即:对对 求各个求各个变变量偏量偏导导数，并令它数，并令它们们等于零，等于零，得得:第16页解这个线性方程组得：解这个线性方程组得：解这个线性方程组得：解这个线性方程组得：从而可得最小从而可得最小值值是是 .第17页6 6 6 6、多目标规划模型、多目标规划模型、多目标规划模型、多目标规划模型 在许多实际问题中，衡量一个方案好坏标准在许多实际问题中，衡量一个方案好坏标准往往不止一个，比如设计一个导弹，既要射程最往往不止一个，比如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高远，又要燃料最省，还要精度最高.这一类问题这一类问题统称为多目标最优化问题或多目标规划问题统称为多目标最优化问题或多目标规划问题.我我们先来看一个生产计划例子们先来看一个生产计划例子.第18页第19页第20页第21页第22页第23页第24页第25页第26页第27页第28页第29页第30页第31页第32页第33页我们希望购置我们希望购置我们希望购置我们希望购置DVDDVDDVDDVD总数量最小，即总数量最小，即总数量最小，即总数量最小，即:由此，能够得到问题三双目标整数线性规划模型由此，能够得到问题三双目标整数线性规划模型以下：以下：第34页第35页第36页第37页第38页表表表表6 6 6 6 当当当当 时最小购置量时最小购置量时最小购置量时最小购置量 值值值值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 1D2D22 2D2D23 3D2D24 4D2D25 5D2D26 6D2D27 7D2D28 8D2D29 9D3D30 0最最少少购购置置量量2020181822221414181817171515121216162424DVDDVD编编号号D3D31 1D3D32 2D3D33 3D3D34 4D3D35 5D3D36 6D3D37 7D3D38 8D3D39 9D4D40 0最最少少购购置置量量1919222220201919222222221313171717171717DVDDVD编编号号D4D41 1D4D42 2D4D43 3D4D44 4D4D45 5D4D46 6D4D47 7D4D48 8D4D49 9D5D50 0最最少少购购置置量量3232202016162121222216162020151520202020第39页续上表续上表DVDDVD编编号号D5D51 1D5D52 2D5D53 3D5D54 4D5D55 5D5D56 6D5D57 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最最少少购购置置量量2121222215152020151514141212171719191717DVDDVD编编号号D8D81 1D8D82 2D8D83 3D8D84 4D8D85 5D8D86 6D8D87 7D8D88 8D8D89 9D9D90 0最最少少购购置置量量1818101014141212212113132222151513131717DVDDVD编编号号D9D91 1D9D92 2D9D93 3D9D94 4D9D95 5D9D96 6D9D97 7D9D98 8D9D99 9D1D10 00 0最最少少购购置置量量2424171715151414252515152222202011112222第40页 我们利用规划模型求得每种我们利用规划模型求得每种DVDDVD购置量后，需要对购置量后，需要对其进行可行性校验，测试此结果是否能够满足一其进行可行性校验，测试此结果是否能够满足一个月内百分比为个月内百分比为95%95%会员得到他想看会员得到他想看DVDDVD，且含有，且含有尽可能大总体满意度尽可能大总体满意度.第41页校验方法：校验方法：校验方法：校验方法：（一）依据订单和求得（一）依据订单和求得DVDDVD购置数量，利用问购置数量，利用问题二规划模型进行第一次分配，对分配情况：租题二规划模型进行第一次分配，对分配情况：租赁会员，赁会员，DVDDVD分配情况，剩下各种分配情况，剩下各种DVDDVD数量作统计；数量作统计；同时将已租赁会员在满意指数矩阵指数全变为同时将已租赁会员在满意指数矩阵指数全变为0 0，即不考虑对其进行第二次分配即不考虑对其进行第二次分配.（二）随机从第一次得到（二）随机从第一次得到DVDDVD会员中抽取会员中抽取60%60%，将这部分人所还回将这部分人所还回DVDDVD与第一次分配余下与第一次分配余下DVDDVD合在一合在一起，作为第二次分配时各种起，作为第二次分配时各种DVDDVD现有量现有量.然后，利用然后，利用问题二问题二0-10-1线性规划模型对第一次未分配到线性规划模型对第一次未分配到DVDDVD会员会员进行第二次分配；进行第二次分配；第42页 （三）统计出经过两次分配后，得到（三）统计出经过两次分配后，得到DVDDVD会员会员百分比，若大于百分比，若大于95%95%，则此次分配成功，则此次分配成功.利用这种利用这种算法进行屡次随机模拟，若大多数情况下能够使算法进行屡次随机模拟，若大多数情况下能够使得到得到DVDDVD会员大于会员大于95%95%，则认为模型三是合理，则认为模型三是合理.第43页校验结果：校验结果：校验结果：校验结果：因为每次检验需时约因为每次检验需时约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第44页再见再见第45页