Pyth基础及其求解 8

实用运筹学

－－运用Python建模和求解第7章非线性规划NonlinearProgramming本章内容要点非线性规划的基本概念二次规划可分离规划本章主要内容框架图7.1非线性规划的基本概念前6章所涉及的规划问题的目标函数和约束条件都是线性的。但在许多实际问题中，往往会遇到目标函数或约束条件是非线性的情况，这类规划问题就是非线性规划问题。在规划问题中，如果目标函数或约束条件中有一个是决策变量的非线性函数，则这类规划问题称为非线性规划问题。本章将介绍其中一类比较简单的情形，即目标函数是决策变量的非线性函数，而约束条件是线性的。7.1非线性规划的基本概念例7-1

用一根长度为400米的绳子，围成一块矩形的菜地，问长和宽各为多少米时菜地的面积最大？【解】本问题是一个小学数学问题，现在把它当作一个规划问题来求解。（1）决策变量设矩形菜地的长为x1米，宽为x2米。（2）目标函数菜地的面积最大。（3）约束条件 ①绳子长度为400米 ②非负7.1非线性规划的基本概念利用Python求解例7-1利用scipy.optimize中的函数minimize()求解代码框7-1例7-1.ipynb最优解：矩形菜地的长x1=100矩形菜地的宽x2=100最优目标值（菜地的面积最大）：100007.1.2非线性规划的Python代码例7-2求解复杂的非线性规划问题：7.1.2非线性规划的Python代码利用Python求解例7-2利用scipy.optimize中的函数minimize()求解代码框7-2例7-2.ipynb与初始值有关（x=0作为初始值）x=0.371y=3.193（x=3作为初始值）x=3.126y=6.128（x=4.7作为初始值）x=5.000y=0.0007.1.2非线性规划的Python代码正是局部最优解的存在，才使得非线性规划问题的求解要比线性规划问题的求解复杂得多。当求得一个最优解时，常常无法确定该最优解是不是全局最优解。处理复杂的有几个极大值的非线性规划问题时，一种方法就是用不同的初始值进行测试，然后从这些局部最优解中挑选出最优的一个。虽然这种方法仍然不能保证找到全局最优解，但它毕竟对找到一个相当好的解给予了很大的可能。因此，对一些相对较小的问题而言，这是一种合理的方法。7.2二次规划若某非线性规划的目标函数为决策变量的二次函数，而且是边际收益递减的，约束条件又都是线性的，那么称这种规划为二次规划。决策变量在有限域内变动的边际收益递减的二次规划存在最优解，且此最优解与初始值无关，即局部最优解就是全局最优解。7.2二次规划在营销过程中，营销成本往往是非线性的，而且随着销量的增加，单位营销成本也在增加。也就是说，单位利润随着销量的增加而减少（边际收益递减）。例7-3

考虑非线性营销成本的例1-1。在例1-1中，增加考虑新产品（门和窗）的营销成本。原来估计每扇门的营销成本是75元，每扇窗的营销成本是200元。因此，当时估计的门和窗的单位利润分别是300元和500元。也就是说，如果不考虑营销成本，每扇门的毛利润是375元，每扇窗的毛利润是700元。已知门和窗的营销成本随着销量的增加而呈现非线性增长，若设x1为门的每周产量，x2为窗的每周产量，则门每周的营销成本为25x12，窗每周的营销成本为60x22。7.2二次规划【解】新的模型考虑了非线性的营销成本，所以在原来模型的基础上，需要修改目标函数。（1）决策变量设x1为门的每周产量，x2为窗的每周产量。（2）目标函数①门的每周销售毛利润为375x1，每周营销成本为25x12

，因此，门的每周净利润为375x1－25x12

；②窗的每周销售毛利润为700x2，每周营销成本为60x22

，因此，窗的每周净利润为700x2－60x22

。本问题的目标是两种新产品的总利润最大。7.2二次规划（3）约束条件

依旧是原有的三个车间每周可用工时限制和非负约束。

例7-3的二次规划模型：7.2二次规划利用Python求解例7-3利用cvxpy库求解代码框7-3例7-3.ipynb最优解（最优生产方案）：门的每周产量x1=2.95

窗的每周产量x2=4.57最优目标值（总利润最大）：2835.357.3可分离规划当利润（或成本）曲线是分段直线时，可分离规划技术可将非线性规划问题转化为相应的线性规划问题。这有助于非常有效地求解问题。可分离规划技术为利润（或成本）曲线上的每段直线引入新的决策变量，以代替原来单一的决策变量。也就是为利润（或成本）曲线的每个线段给出一个分离的决策变量。产品每周最大产量（扇）单位利润（元）正常生产加班生产总计正常生产加班生产门314300200窗336500100车间3的约束条件：7.3.1边际收益递减的可分离规划例7-4

需要加班的例1-1。

表7-1给出了车间1和车间2每周在正常工作时间和加班时间生产门和窗的最大数量及单位利润。车间3不需要加班，约束条件也不需要改变。7.3.1边际收益递减的可分离规划【解】（1）决策变量例1-1中的决策变量是：门的每周产量x1，窗的每周产量x2。由于加班生产的产品单位利润减少，所以利用可分离规划技术，将正常工作时间和加班时间的产量分开，引入新的决策变量：

x1R为正常工作时间内门的每周产量，

x1O为加班时间内门的每周产量；

x2R为正常工作时间内窗的每周产量，

x2O为加班时间内窗的每周产量。并且有：x1=x1R+x1O

，

x2=x2R+x2O7.3.1边际收益递减的可分离规划（2）目标函数

两种新产品的总利润最大。由于正常工作时间和加班时间生产的产品的单位利润不同，所以在目标函数中用的是新引入的决策变量。（3）约束条件①原有的例1-1的三个车间的约束还是有效的，只不过用（x1R＋x1O）代替x1，用（x2R＋x2O）代替x2。②正常工作时间和加班时间的每周最大产量约束③非负用新引入的4个决策变量7.3.1边际收益递减的可分离规划利用Python求解例7-4利用pulp库求解代码框7-4例7-4（无总产量）.ipynb用新引入的4个决策变量代替原来的2个决策变量（无总产量）最优解（最优生产计划）：正常生产门的每周产量x1R=3.0加班生产门的每周产量x1O=1.0正常生产窗的每周产量x2R=3.0加班生产窗的每周产量x2O=0.0门的每周总产量x1R+x1O=4.0窗的每周总产量x2R+x2O=3.0最优目标值（总利润最大）：2600.07.3.1边际收益递减的可分离规划由于总产量＝每种产品在正常工作时间内和加班时间内的产量总和，也就是说，有x1=x1R+x1O，x2=x2R+x2O因此例7-4的数学模型也可以写为用原来的2个决策变量＋新引入的4个决策变量7.3.1边际收益递减的可分离规划利用Python求解例7-4利用pulp库求解代码框7-5例7-4（有总产量）.ipynb用原来的2个决策变量＋新引入的4个决策变量（有总产量）最优解（最优生产计划）：正常生产门的每周产量x1R=3.0加班生产门的每周产量x1O=1.0正常生产窗的每周产量x2R=3.0加班生产窗的每周产量x2O=0.0门的每周总产量x1=4.0窗的每周总产量x2=3.0最优目标值（总利润最大）：2600.07.3.2边际收益递增的可分离规划例7-5

原油采购与加工问题。某公司用两种原油（A和B）混合加工成两种汽油（甲和乙），甲和乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过400吨时的单价为10000元/吨；购买量超过400吨但不超过900吨时，超过400吨的部分单价为8000元/吨；购买量超过900吨时，超过900吨的部分单价为6000元/吨。该公司应如何安排原油的采购和加工？7.3.2边际收益递增的可分离规划例7-5的混合0-1线性规划模型7.3.2边际收益递增的可分离规利用Python求解例7-5利用pulp库求解代码框7-6例7-5.ipynb最优解（最原油的采购和加工方案）：购买原油A：x=1000.0

两种原油（A和B）用于混合加工汽油甲：

xA1=0.0，xB1=0.0

汽油甲总量=0.0

两种原油（A和B）用于混合加工汽油乙：

xA2=1500.0，xB2=1000.0

汽油乙总量=2500.0最优目标值（总利润最大）：540.0

其中，总销售收入：1400.0

总购买支出：860.0本章上机实验1．实验目的

掌握利用Py