高等运筹课件1

1、1高等运筹学主讲 刘春山2高等与初等运筹的差别线性与非线性单目标与多目标决策与对策方法的运用与方法的创新3复习一下运筹学是作什么的4现实世界现实世界抽象模型输出模型用户输入结论与建议实施5案例一汽车保险延展计划由保险公司为顾客提供了三种 付款方案：方案一：月初一次性福清全年保险费1500美元方案二：分三期等额付款，第一月月初首付，以后每隔两月付一次，每次付款加收服务费3.5美元方案三：月付。第一月月初首付两个月保险费，以后每月月初提前交付，一年付完，最后十次由银行划付（无其他成本），每次付款加收服务费，服务费为每次付款额的3%假定银行月息0.5%，（年存款利息率约为6%） 6 如何建立该问题有

2、效的模型（仿真模型），模型参数化，利率在决策中的敏感性，求解参数：利率，保险费（在电子表格中的体现）7案例二开采铜矿的决策开采铜矿的决策 某省根据初步勘探，发现一个铜矿，该某省根据初步勘探，发现一个铜矿，该矿含铜量，按估计可能高含量的概率为矿含铜量，按估计可能高含量的概率为0.20.2，中含量的概率为中含量的概率为0.30.3，低含量的概率为，低含量的概率为0.50.5。如果决定开采，在高含量的情况下可盈利如果决定开采，在高含量的情况下可盈利400400万元万元, ,中等含量下可盈利中等含量下可盈利100100万元万元, ,低含低含量下将亏损量下将亏损160160万元万元. .如果不开采如果不

3、开采, ,把准备开把准备开采的资金用于办工厂将盈利采的资金用于办工厂将盈利3535万元，现在万元，现在问是否应该开采？问是否应该开采？8 分析：本问题模型可以用决策树解决。计算各决策的数学期望值。912400100-16035开采开采不开采不开采30S1:p1= 0.2S2:p2= 0.3S3:p3= 0.5决策点，状态点的表示决策点，状态点的表示10 开采的数学期望值为开采的数学期望值为30,所以选择不开采所以选择不开采，考虑到考虑到“开采开采”的期望值的期望值3030与与“不开采不开采”的的3535相比相差不太大。因而省政府计划部门认为可相比相差不太大。因而省政府计划部门认为可以对该矿作进

4、一步的勘探。进一步的勘探要耗以对该矿作进一步的勘探。进一步的勘探要耗费费4040万元的勘探费用，其结果可能区分矿区地万元的勘探费用，其结果可能区分矿区地质结构是否矿物化的情况，在矿物化的情况下，质结构是否矿物化的情况，在矿物化的情况下，铜矿含铜高含量的概率提高到铜矿含铜高含量的概率提高到0.50.5，中含量和，中含量和低含量的概率为低含量的概率为0.30.3和和0.20.2，如果地质结构非矿，如果地质结构非矿物化则含铜量高、中、低的概率分别为物化则含铜量高、中、低的概率分别为0.050.05、0.10.1和和0.850.85。据专家估计该矿区地质结构矿物。据专家估计该矿区地质结构矿物化和非矿物

5、化的概率分别为化和非矿物化的概率分别为0.60.6和和0.40.4。1113624578-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-1604003512 用逆推的方法确定最优策略为：进一步进行勘探，用逆推的方法确定最优策略为：进一步进行勘探，如果勘探结果是矿物化则

6、决定开采，如非矿物如果勘探结果是矿物化则决定开采，如非矿物化则不开采。这里，化则不开采。这里，“进一步进行勘探进一步进行勘探”只是只是为了获得为了获得“是否矿物化是否矿物化”这个信息。这个信息这个信息。这个信息对我们的决策有多大的价值呢？当我们没有获对我们的决策有多大的价值呢？当我们没有获得这个信息时，我们采用了得这个信息时，我们采用了“不开采不开采”这个决这个决策，此时收益的期望值是策，此时收益的期望值是3535万元（见图万元（见图6.46.4）。）。当我们获得这个信息后，便可以利用这个信息当我们获得这个信息后，便可以利用这个信息决策是否开采，此时收益的期望值提高到决策是否开采，此时收益的期

7、望值提高到132.8132.8万元（见图万元（见图 的状态点的状态点2 2），但为获得这），但为获得这个信息要耗费个信息要耗费4040万元的成本。因此，这个信息万元的成本。因此，这个信息的纯价值为：的纯价值为：132.8-35-40 = 57.8132.8-35-40 = 57.8（万元）（万元） 13两大问题：建模与算法在本课程中将都有所涉及14课程安排第一章 非线性规划第二章 多目标规划第三章 对策论第四章 决策论其他方法15第一章第一章非线性规划非线性规划 16第一节 非线性规划问题一 、一般非线性规划17非线性规划非线性规划 在科学管理和其他领域中，大量应用问题可以在科学管理和其他领域

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

9、种问一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域题的一般算法，这是需要深入研究的一个领域。 18 问题的提出问题的提出例例1 某公司经营两种设备，第一种设备每件售价某公司经营两种设备，第一种设备每件售价 30 元，第二种设备每件售价元，第二种设备每件售价 450 元。据统计，每销元。据统计，每销售一件第一种设备所需时间平均售一件第一种设备所需时间平均 0.5 小时，第二种设小时，第二种设备是（备是（2 + 0.25X2）小时，其中）小时，其中 X2 是第二种设备的是第二种设备的售数量。已知该公司在这段时间内的总营业时间为售数量。已知该公司在这段时间内的

10、总营业时间为 800 小时，试确定使其营业额最大的营业计划。小时，试确定使其营业额最大的营业计划。 19 例例2 某工厂向用户提供发动机，按合同规定，其交某工厂向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交货数量和日期是：第一季度末交 40 台，第二季度末台，第二季度末交交 60 台，第三季度末交台，第三季度末交 100 台。工厂的最大生产能台。工厂的最大生产能力为每季度力为每季度 100 台，每季的生产费用是台，每季的生产费用是 f（X）= 50X + 0.2X2 （元），（元），X 为该季度生产的发为该季度生产的发动机数量。若某季度生产的多，多余的发动机可移到动机数量。若某

11、季度生产的多，多余的发动机可移到下季度向用户交货，这样，工厂就需要支付存储费，下季度向用户交货，这样，工厂就需要支付存储费，每台发动机每季的存储费为每台发动机每季的存储费为 4 元。问该厂每季应生产元。问该厂每季应生产多少发动机，才能既满足交货合同，又使工厂所花费多少发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季开始时发动机无存货）。的费用最少（假定第一季开始时发动机无存货）。 20 最优动态定价法模型基本特征：1、在各个价格期间给定数量的产品，公司会不段优化价格去获取最大收入2、公司在每个价格期间结束时都会制定新的最优价格，这个新价格考虑了实际销量和真实的库存水平3、从一个

12、价格期间到另一个价格期间，价格都会发生变化，需求较高的时期，价格往往高于需要低时期的价格21 4、通常价格会由于实际销量水平而与计划价格有所偏离。如果实际销量低于计划销量，价格一般会下跌，若实际销量高于计划销量，价格往往会上升。22最佳批量模型我们讨论的最佳批量模型中，包括了一个模型系列，其基本特征是非线性优化，由无约束优化到单一等式约束优化，最终到含有多个不等式约束的非线性优化23 经济订货量公式EQQ在确定性、周期性的补充存贮消耗过程中，假设单一产品1均匀消耗，消耗率R即时补充，3不允许缺货4 每次订货量Q ，固定费K，单位存贮费h均不变，货物单价C24 考虑多产品存贮模型，增加资金约束时

13、，或者增加库存容量约束时，成为单一等式约束优化，用lagrange乘数法求最优解兼有库存与资金约束的多产品EQQ模型具有两个不等式约束的非线性规划25 微观经济中的非线性规划 消费者选择 成本最小化那么如何求非线性规划问题的最优解呢？那么如何求非线性规划问题的最优解呢？回顾一下线性规划的图解法回顾一下线性规划的图解法26 非线性规划问题的数学模型非线性规划问题的数学模型 min f（X） hi（X）= 0 i = 1，2，m gj（X） 0 j = 1，2，l min f（X） gj（X） 0 j = 1，2，l 27 非线性规划的图解非线性规划的图解x1x20662233最优解最优解 X*

14、= ( 3，3 )T可行解可行解 可行域可行域D min f（X）=（x1 - 2）2 +（x2 - 2）2 h（X）= x1 + x2 - 6 = 0等值线或者等值面 28 非线性规划的图解非线性规划的图解 min f（X）=（x1 - 2）2 +（x2 - 2）2 h（X）= x1 + x2 - 6 0 x1x206622最优解最优解 X* = ( 2，2 )T D可行域可行域 29 回顾一下一元函数极值的求法那么多元函数极值问题应该怎么求30 二、多元函数极值的有关概念和性质 梯度梯度 f(X)（n维列向量） 海森矩阵海森矩阵 H(X)（nn对称方阵）定理 1 f(X)的台劳展开式台劳展

15、开式 定义 邻域邻域 （严格）局部极小点（严格）局部极小点 （严（严格）全局极小点格）全局极小点 驻点（平稳点）正定驻点（平稳点）正定 半正定半正定 负定（主子式负正间隔）负定（主子式负正间隔） 半负半负定定 不定不定定理2、3、4、5 局部极小点的一阶必要条件，二阶必要条件，二阶充分条件（严格局部极小点，局部极小点）31 例 求f(X)=1/3x12+ 1/ 2x22 的梯度向量例 求f(X)= x12+ 2x22 -4x1-2x1x2海森矩阵32 例例 生产函数Q=3K1/3L1/2 若商品价格为4,要素的价格为Pk=4,PL=3 试求该企业得到最大利润时的要素投入水平（消费者最优商品组合

16、，生产要素最佳组合的相似性-无差异曲线，等产量曲线；效用函数，生产函数）33 三、正定矩阵与二次型 四 凸函数的极值 凸函数凸函数 严格凸函数严格凸函数 （严格）凹函数（严格）凹函数非凸非凹函数非凸非凹函数 凸函数的性质 1、2、3 凸函数的判别 定理6、7 可引申出凹函数的性质与判别 34凸函数凹函数非凸非凹函数35 凸函数极值的性质 定理8 、9凸规划 定义 判别定理：定理10、凸规划性质：定理11例例 证明 f(X)=x12 x22为严格凹函数两种方法证明 利用凹函数的判别定理例例 凸规划的判别minf(X)= x12+ x224x1+4 g1(x)= x1 x2 +20 g2(x)=

17、x1 2 x2 10 36第二节 一维搜索一元函数极值问题一维搜索的来历求非线性规划 的基本思路：1、选定初始点X0 k=02、检查Xk是否极小，是停，否继续3、确定搜索方向Pk4、从Xk出发，沿Pk求步长k ,产生Xk1令k=k+1转2 37 确定Pk为关键，这决定于不同算法，确定步长有几种方法：1、令其为一常数（最简单）2、任选步长，只要能使f下降3、沿搜索方向使f下降最多即求 k ：minf(Xk+ k Pk)称这一过程为一维搜一维搜索索，这样确定的步长为最佳步长4、确定能使f更快接近最优的步长38 可见一维搜索是求目标函数可见一维搜索是求目标函数minf(Xk+ Pk)的的 ，即求以，

18、即求以 为自变量的为自变量的一元函数的最优解与最优值，可以直接一元函数的最优解与最优值，可以直接用求极值的方法用求极值的方法 39 如果解析解不易求得，一般采用迭代方法求解，本节介绍的基本为迭代方法，基本步骤为：1、初值x0 k=02、判断xk，满足条件终止，否则继续3、迭代xk xk+1 k=k+1转2关键在于确定 判别规则，及迭代公式40 一、牛顿法与对分法利用局部极小点的一阶 必要条件，对于一元函数有f(x)=0，该方程解析解有时候不易求得，用迭代法求解。41 x0 x1x2x*f (x)0判别规则：判别规则：|f (xk)|迭代公式：迭代公式：xk+1=xk-f (xk)/f ”（xk

19、）牛顿法牛顿法42 牛顿法发散的情况牛顿法发散的情况f(x)x0 x1x2x*43f(x)ab c对分法对分法判别规则判别规则最后的区间很小最后的区间很小迭代方法，三点中去掉迭代方法，三点中去掉一个边界点，保留正负一个边界点，保留正负两点两点，44 二、抛物线法 （二次插值法），0.618法基本思想 利用f(x)在三个不同点的函数值，形成高、低、高，缩小区间迭代45抛物线法抛物线法x3x1x2x4判别规则：判别规则：|x2- x4|0,对于所有X,P(X)0,当且仅当XD时，P(X)=0 P(X)是罚函数罚函数， 为罚因子，64 不断增加，使F极小点X不断靠近可行域P(X)的取法：当st hj

20、(X)=0 j=1,2,l时，取P(X)=hj(X)2当st gi(X)0 i=1,2m 时，取 P(X)=min 0,gi(X) 265xMP(x)g(x)=x-a0aM=1M=10M=10066 例：求解非线性规划 minf(X)=x1+x2 g1(X)=-x12+x20 g2(x)=x1067 2、内点法 基本思想：从原问题可行点出发，在可行域边界建立一个障碍函数q(X)，阻挡可行点离开可行域，从而使迭代在可行域内部逐渐逼近约束最优解。逐渐缩小r当约束为gi(X)0 时，q(X)=r1/ gi(X)68 例：用内点法求解 minf(x)=x3/3 x-a069 第二章第二章 多目标规划多

21、目标规划70第一节 基本概念例：由n种成分组成的香蕉配方，可用x=(x1,x2,.xn)表示，对于每个配方要同时考察几个指标，如强度f1(x),硬度f2(x) ，伸长率，变形率等，如何得到好的配方。再如薪酬设计，业绩考评等都需要考虑多方面的指标。 绝对最优解 有效解 弱有效解（非劣解） 71fi(x)xf1(x)f2(x)f2(x)fi(x)xf1(x)f2(x)f1(x)f1(x)f2(x)例 minf(x)=(f1(x),f2(x)72 练习 1、f1(x)=2x-x2 f2(x)= R=0,2 max2、f1(x)=2x-x2 f2(x)=x R=0,2 max3、 f1(x)=2x-x

22、2 f2(x)=1/8(-12x2+36x-15) R=0,2 max x 0 x1 2x+3 1x273 4、f1(x)=-3x1+2x2 f2=x1+2x2 求max5、上例中f2= 4x1+3x2其他不变 求max-2x1-3x2+180-2x1- x2+100 x1 0 x2 0R:74第二节 化多为少法1、主要目标法2、线性加权和法找合理权系数的方法：法以两目标规划为例 75f1*f10f2*f20M2M1Cf1 f2 f1越小越好,f2越大越好M1与M2连线左上区域边界是非劣解，可知C点是非劣解。f10=minf1=f1(x1)f20=maxf2 = f2(x2) f1*= f1(x2)f2*= f2(x