高等运筹课件1

高等运筹学主讲刘春山1高等与初等运筹的差别线性与非线性单目标与多目标决策与对策方法的运用与方法的创新2复习一下运筹学

是作什么的3现实世界抽象模型输出模型用户输入结论与建议实施4案例一汽车保险延展计划由保险公司为顾客提供了三种付款方案：方案一：月初一次性福清全年保险费1500美元方案二：分三期等额付款，第一月月初首付，以后每隔两月付一次，每次付款加收服务费3.5美元方案三：月付。第一月月初首付两个月保险费，以后每月月初提前交付，一年付完，最后十次由银行划付（无其他成本），每次付款加收服务费，服务费为每次付款额的3%假定银行月息0.5%，（年存款利息率约为6%）

5

如何建立该问题有效的模型（仿真模型），模型参数化，利率在决策中的敏感性，求解参数：利率，保险费（在电子表格中的体现）6案例二开采铜矿的决策

某省根据初步勘探，发现一个铜矿，该矿含铜量，按估计可能高含量的概率为0.2，中含量的概率为0.3，低含量的概率为0.5。如果决定开采，在高含量的情况下可盈利400万元,中等含量下可盈利100万元,低含量下将亏损160万元.如果不开采,把准备开采的资金用于办工厂将盈利35万元，现在问是否应该开采？7

分析：本问题模型可以用决策树解决。计算各决策的数学期望值。812400100-16035开采不开采30S1:p1=0.2S2:p2=0.3S3:p3=0.5决策点，状态点的表示9

开采的数学期望值为30,所以选择不开采，考虑到“开采”的期望值30与“不开采”的35相比相差不太大。因而省政府计划部门认为可以对该矿作进一步的勘探。进一步的勘探要耗费40万元的勘探费用，其结果可能区分矿区地质结构是否矿物化的情况，在矿物化的情况下，铜矿含铜高含量的概率提高到0.5，中含量和低含量的概率为0.3和0.2，如果地质结构非矿物化则含铜量高、中、低的概率分别为0.05、0.1和0.85。据专家估计该矿区地质结构矿物化和非矿物化的概率分别为0.6和0.4。1013624578-40A1不勘探35A2进一步勘探矿物化0.6非矿物化0.4132.819835开采不开采400100-160S2:(0.3)S3:(0.5)35开采不开采198S1:(0.5)S2:(0.3)S3:(0.2)400100-16035开采不开采-106S1:(0.05)S2:(0.1)S3:(0.85)400100-1604003511

用逆推的方法确定最优策略为：进一步进行勘探，如果勘探结果是矿物化则决定开采，如非矿物化则不开采。这里，“进一步进行勘探”只是为了获得“是否矿物化”这个信息。这个信息对我们的决策有多大的价值呢？当我们没有获得这个信息时，我们采用了“不开采”这个决策，此时收益的期望值是35万元（见图6.4）。当我们获得这个信息后，便可以利用这个信息决策是否开采，此时收益的期望值提高到132.8万元（见图的状态点2），但为获得这个信息要耗费40万元的成本。因此，这个信息的纯价值为：132.8-35-40=57.8（万元）12两大问题：建模与算法

在本课程中将都有所涉及13课程安排

第一章非线性规划第二章多目标规划第三章对策论第四章决策论其他方法14第一章非线性规划

15第一节非线性规划问题一、一般非线性规划16非线性规划

在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。

17

问题的提出例1某公司经营两种设备，第一种设备每件售价30元，第二种设备每件售价450元。据统计，每销售一件第一种设备所需时间平均0.5小时，第二种设备是（2+0.25X2）小时，其中X2是第二种设备的售数量。已知该公司在这段时间内的总营业时间为800小时，试确定使其营业额最大的营业计划。

18

例2某工厂向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交40台，第二季度末交60台，第三季度末交100台。工厂的最大生产能力为每季度100台，每季的生产费用是f（X）=50X+0.2X2（元），X为该季度生产的发动机数量。若某季度生产的多，多余的发动机可移到下季度向用户交货，这样，工厂就需要支付存储费，每台发动机每季的存储费为4元。问该厂每季应生产多少发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季开始时发动机无存货）。

19

最优动态定价法模型基本特征：1、在各个价格期间给定数量的产品，公司会不段优化价格去获取最大收入2、公司在每个价格期间结束时都会制定新的最优价格，这个新价格考虑了实际销量和真实的库存水平3、从一个价格期间到另一个价格期间，价格都会发生变化，需求较高的时期，价格往往高于需要低时期的价格20

4、通常价格会由于实际销量水平而与计划价格有所偏离。如果实际销量低于计划销量，价格一般会下跌，若实际销量高于计划销量，价格往往会上升。21最佳批量模型我们讨论的最佳批量模型中，包括了一个模型系列，其基本特征是非线性优化，由无约束优化到单一等式约束优化，最终到含有多个不等式约束的非线性优化22

经济订货量公式EQQ在确定性、周期性的补充——存贮——消耗过程中，假设单一产品1均匀消耗，消耗率R即时补充，3不允许缺货4每次订货量Q，固定费K，单位存贮费h均不变，货物单价C23

考虑多产品存贮模型，增加资金约束时，或者增加库存容量约束时，成为单一等式约束优化，用lagrange乘数法求最优解兼有库存与资金约束的多产品EQQ模型具有两个不等式约束的非线性规划24

非线性规划问题的数学模型

minf（X）hi（X）=0i=1，2，…，mgj（X）≥0j=1，2，…，l

minf（X）gj（X）≥0j=1，2，…，l

25

非线性规划的图解x1x20662233最优解X*=(3，3)T可行解可行域D

minf（X）=（x1-2）2+（x2-2）2h（X）=x1+x2-6=0等值线或者等值面

26

非线性规划的图解

minf（X）=（x1-2）2+（x2-2）2h（X）=x1+x2-6≤0x1x206622最优解X*=(2，2)T

D可行域

27

二、多元函数极值的有关概念和性质梯度

f(X)（n维列向量）

海森矩阵H(X)（n×n对称方阵）定理1f(X)的台劳展开式定义δ邻域（严格）局部极小点（严格）全局极小点驻点（平稳点）正定半正定负定（主子式负正间隔）半负定不定定理2、3、4、5局部极小点的一阶必要条件，二阶必要条件，二阶充分条件（严格局部极小点，局部极小点）28

例求f(X)=1/3x12+1/2x22的梯度向量例求f(X)=x12+2x22-4x1-2x1x2海森矩阵29

例生产函数Q=3K1/3L1/2若商品价格为4,要素的价格为Pk=4,PL=3试求该企业得到最大利润时的要素投入水平30

三、正定矩阵与二次型

四凸函数的极值

凸函数严格凸函数（严格）凹函数非凸非凹函数

凸函数的性质1、2、3凸函数的判别定理6、7可引申出凹函数的性质与判别

31凸函数凹函数非凸非凹函数32

凸函数极值的性质定理8、9凸规划定义判别定理：定理10、凸规划性质：定理11例证明f(X)=－x12－x22为严格凹函数两种方法证明利用凹函数的判别定理例凸规划的判别minf(X)=x12+x22－4x1+4g1(x)=x1

－x2

+2≥0g2(x)=－x12＋x2

－1≥0

33第二节一维搜索一元函数极值问题一维搜索的来历求非线性规划的基本思路：1、选定初始点X0k=02、检查Xk是否极小，是停，否继续3、确定搜索方向Pk4、从Xk出发，沿Pk求步长λk,产生Xk＋1令k=k+1转2

34

确定Pk为关键，这决定于不同算法，确定步长有几种方法：1、令其为一常数（最简单）2、任选步长，只要能使f下降3、沿搜索方向使f下降最多即求λk：minf(Xk+λkPk)称这一过程为一维搜索，这样确定的步长为最佳步长4、确定能使f更快接近最优的步长35

可见一维搜索是求目标函数minf(Xk+λPk)的λ，即求以λ为自变量的一元函数的最优解与最优值，可以直接用求极值的方法

36

如果解析解不易求得，一般采用迭代方法求解，本节介绍的基本为迭代方法，基本步骤为：1、初值x0k=02、判断xk，满足条件终止，否则继续3、迭代xkxk+1k=k+1转2关键在于确定判别规则，及迭代公式37

一、牛顿法与对分法利用局部极小点的一阶必要条件，对于一元函数有f’(x)=0，该方程解析解有时候不易求得，用迭代法求解。38

x0x1x2x*f’(x)0判别规则：|f’(xk)|<ε迭代公式：xk+1=xk-f’(xk)/f”（xk）牛顿法39

牛顿法发散的情况f’(x)x0x1x2x*40f’(x)ab

c对分法判别规则最后的区间很小迭代方法，三点中去掉一个边界点，保留正负两点，41

二、抛物线法（二次插值法），0.618法基本思想利用f(x)在三个不同点的函数值，形成高、低、高，缩小区间迭代42抛物线法x3x1x2x4判别规则：|x2-x4|<ε迭代方法：四点中去掉一个边界点，保留高低高三点43

已知三点求抛物线参数的方法：求解三元线性方程组的解440.618法abx1x2判别规则搜索区间很小迭代方法：四点去掉一边界点，保留高低高三点45第三节无约束最优化方法约束最优化问题往往可转化为无约束问题可采用解析法：用到梯度或海森矩阵直接法：不用导数。以下基本为解析法依照前面的步骤关键确定搜索方向，及步长（一般可采用一维搜索），判别规则一般为梯度很小。因此各种方法的主要区别是搜索方向。46

一、最速下降法思路：沿目标函数在该点下降最快的方向进行一维搜索，这个方向是负梯度方向472030f(Xk)Xk负梯度方向是函数f在Xk处下降最快方向等值面48搜索方向Pk=-f(Xk)迭代公式为：Xk+1=Xk+λkPk=Xk－λkf(Xk)

O向量的和的图示XPX+P49X0X3X1梯度法的缺陷若目标函数等值线为一族同心园，一步即可达到极小点50

例用梯度法求f(X)=1/3x12+1/2x22设初始点为x0=(3,2)’51

二、牛顿法由于梯度法有时收敛慢，牛顿法在确定搜索方向时不仅考虑了这点的梯度，而且考虑了梯度的变化趋势。基本思想是在目标函数具有二阶连续导数的条件下，用二次函数去近似f，然后以其极小点近似f的极小点。52

运用函数的台劳展开式并略去高于二次的项可得牛顿方向（搜索方向）Pk=－H(xk)

f(xk)例3P236求f(X)=x12+2x22-4x1-2x1x2设x0=(1,1)’二次函数一次收敛53

三、共轭梯度法避免牛顿法的求逆，及最速下降法的慢收敛性54什么是共轭方向二元正定二次函数的等值线，在极小点附近可用一族同心椭圆表示，P0P1P0X0

X155试证明（P1）TAP0=0即P1与P0共轭说明二维正定二次函数，从任一点出发沿相互共轭的方向P1与P0进行两次一维搜索，即可收敛到极小点对于n维二次函数，至多经n步总可收敛一般共轭梯度法在二次性强区域收敛好，最速下降法在非二次性区域能够使目标下降快。56

初始方向P1=-

f(xk)搜索方向Pk+1=-

f(xk＋1)+VkPK其中Vk=‖

f(xk＋1)‖2/‖

f(xk)‖2N次搜索为一轮57

四、座标轮换法1、使用一维搜索的座标轮换法搜索方向按坐标轮换，P1=e1=(1,0,0,0…)TP2=e2=(0,1,0,0…)T。。。轮换n次判别一次，若‖Xn-X