5.非线性规划模型 前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划问题.

Presentation on theme: "5.非线性规划模型 前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划问题."— Presentation transcript:

1 5.非线性规划模型 前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划问题.

2 事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的
事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的. 为了利用线性的知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型.

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

4 非线性规划问题的标准形式为：

5 非线性规划模型按约束条件可分为以下三类：
⑴ 无约束非线性规划模型： ⑵ 等式约束非线性规划模型：

6 ⑶ 不等式约束非线性规划模型： 针对上述三类非线性规划模型，其常用求解的基本思路可归纳如下： 1) 无约束的非线性规划问题.

7

8

9 在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要因素
在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要因素. 非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，一维搜索方法主要有进退法和黄金分割法. 二维的非线性规划也可以像解线性规划那样用图形求解. 对于二维非线性规划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法.

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

11 例7．（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间. 但要求存储的石油能满足客户的要求
例7．（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间.但要求存储的石油能满足客户的要求.为简化问题，假设只经营两种油，各种符号表示的意义如表4所示.其中供给率指石油公司供给客户的速度.

12 表4 各种符号表示意义表 第i种油的存储量 第i种油的价格 第i种油的供给率 第i种油的每单位的存储费用 第i种油的每单位的存储空间 总存储公式

13 由历史数据得到的经验公式为 : 且提供数据如表5所示：

14 表5 数据表 已知总存储空间

15 代入数据后得到的模型为： 模型求解： 拉格朗日函数的形式为：

16 即: 对 求各个变量的偏导数，并令它们等于零，得:

17 解这个线性方程组得： 从而可得最小值是

18 6、多目标规划模型 在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产计划的例子.

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34 我们希望购买DVD的总数量最小，即 : 由此，可以得到问题三的双目标整数线性规划模型 如下：

35

36

37

38

39 表6 当 时最小购买量的 值 DVD编号 D01 D02 D03 D04 D05 D06 D07 D08 D09 D10 最少购买量 14
表6 当 时最小购买量的 值 DVD编号 D01 D02 D03 D04 D05 D06 D07 D08 D09 D10 最少购买量 14 21 17 24 12 19 22 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 18 16 23 D21 D22 D23 D24 D25 D26 D27 D28 D29 D30 20 15 D31 D32 D33 D34 D35 D36 D37 D38 D39 D40 13 D41 D42 D43 D44 D45 D46 D47 D48 D49 D50 32

40 续上表 DVD编号 D51 D52 D53 D54 D55 D56 D57 D58 D59 D60 最少购买量 24 17 19 18 20
21 D61 D62 D63 D64 D65 D66 D67 D68 D69 D70 16 D71 D72 D73 D74 D75 D76 D77 D78 D79 D80 22 15 14 12 D81 D82 D83 D84 D85 D86 D87 D88 D89 D90 10 13 D91 D92 D93 D94 D95 D96 D97 D98 D99 D100 25 11

41 我们利用规划模型求得每种DVD的购买量后，需要 对其进行可行性校验，测试此结果是否可以满足 一个月内比例为95%的会员得到他想看的DVD，且 具有尽可能大的总体满意度.

42 校验方法： （一）根据订单和求得的DVD购买数量，利用问题二的规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0，即不考虑对其进行第二次分配. （二）随机从第一次得到DVD的会员中抽取60%，将这部分人所还回的DVD与第一次分配余下的DVD合在一起，作为第二次分配时各种DVD的现有量.然后，利用问题二的0-1线性规划模型对第一次未分配到DVD的会员进行第二次分配；

43 （三）统计出经过两次分配后，得到DVD的会员的比例，若大于95%，则此次分配成功
（三）统计出经过两次分配后，得到DVD的会员的比例，若大于95%，则此次分配成功.利用这种算法进行多次随机模拟，若大多数情况下可以使得到DVD的会员大于95%，则认为模型三是合理的.

44 校验结果： 表7 7次模拟结果每次的观看比例列表
因为每次检验需时约1小时，我们只对问题三求得的结果进行了7次模拟，其中6次符合要求（观看比例大于95%）.下面给出7次模拟得到的观看比例（表7）： 表7 7次模拟结果每次的观看比例列表 验证次数 1 2 3 4 5 6 7 观看比例 95.8％ 96.6％ 93.4％ 95.3％ 95.9％ 96.1％ 95.7％

45 再见