高级运筹学-非线性规划

1、运筹学概述运筹学的研究对象是各种系统；运筹学的研究目的是实现系统的最优化，求得合理利用各种资源的最优方案；运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解；运筹学的研究动机是为决策者提供科学决策的依据。 运筹学概述有人曾对世界上500家著名的企业集团或跨国公司进行过调查，发现其中95%曾使用过线性规划，75%使用过运输模型，90%使用过网络计划技术，90%使用过存储模型，43%使用过动态规划。 运筹学的学科背景从狭义到广义的管理科学 狭义的管理科学指： 用科学的方法，特别是定量（运筹学）分析的方法来解决管理问题； 广义的管理科学指：有关管理的学科或学

2、科体系管理科学与工程学科简介管理科学与工程是综合运用系统科学、管理科学、数学、经济和行为科学及工程方法，结合信息技术研究解决社会、经济、工程等方面的管理问题的一门交叉学科。1996年设立，是管理门类的一级学科，与工商管理同,1998年开始授予博士学位点。当时设四个二级学科：工业工程、工程管理、金融工程、管理科学1998年第一批授予管理科学与工程学科博士点的学校，大多是从原有的“系统工程”学科转变而来。 管理科学与工程学科简介管理科学与工程学科背景下的本科专业一般有：工业工程工程管理管理科学信息管理与信息工程物流管理（近年增加） 管理科学与工程学科简介国外相近的系科Industrial engi

3、neeringIndustrial and system engineeringOperations ResearchInformation system & operation managementManagement science 运筹学会与杂志中国运筹学学会(ORSC)The Operations Research Society of China 网站:杂志:,美国运筹与管理学会(IFORMS)Institute for Operations Research and the Management Sciences英文网址：http:/ 中文网站：http:/ 杂志 Decision

4、 AnalysisInformation Systems ResearchINFORMS Journal on ComputingInterfacesManagement ScienceManufacturing & Service Operations ManagementMarketing ScienceMathematics of Operations ResearchOperations ResearchOrganization ScienceTransportation Science 现实中的优化问题物流网络的设计优化；供应链中的多级存储系统的运行优化；港口集装箱调度的优化；制造系

5、统的生产计划与调度优化；金融投资领域;复杂工程系统设计的优化；复杂过程控制系统的参数优化；社会经济系统的优化；。 物流网络的设计优化随着我国物流业的快速发展，不同类型的物流系统的设计，物流园区的设计有很大的实际需求。这些系统设计中有很多优化问题，比如：多个仓库位置的选定，仓库容量的确定，运输方式和运输工具的选择，车辆路径的规划，。 供应链中的多级存储系统的运行优化供应链的运行中也有很多优化的问题分销网络中的多级库存系统的库存补充计划安全库存的分级配置优化考虑缺货或事故情况的处理顺应价格波动的存储计划车辆运输计划和路径优化。 港口集装箱调度的优化现代化港口和铁路集装箱中心站的集装箱运输中有很多的

6、优化问题。比如：船舶的泊次计划集装箱的装/卸载计划堆场的空间计划车辆的作业计划货场的堆放计划码头起重机的调度计划,等等 制造系统的生产计划与调度优化制造系统的生产计划与调度经典的数学规划方法有很多的成功案例。但是，这类系统当考虑到细节时，比如求解车间作业调度问题（JSP）时，一旦考虑托盘的调度，装设时间和运输时间，等等，问题将远比一般的经典JSP更为复杂。 金融投资问题投资组合问题(portfolio)已知某三支股票的价格近十年每年的增长情况,以及500种股票指数变化情况, 假设你现在有一笔资金要进行投资, 并期望年利率至少达到15%, 那么你应该如何投资?。 定量分析的过程定性分析定量分析的

7、前奏应当是一个充分的定性分析表达问题列出表达问题的基本要素：决策变量、不可控量、限制条件等；建立模型列出表达这些要素之间关系的数学方程式求解模型与分析运用算法求解所构建的模型得到最佳方案或满意方案对输入数据和模型结构作灵敏度分析执行决定或修改模型在实际应用过程中不断完善模型 建立模型的重要性建立模型是运筹学方法的精髓建立模型有助于我们把决策问题所遇到的复杂性和可能的不确定性，转变为适于综合分析的逻辑结构；模型是一种媒介，借以认识现实世界。模型是现实的近似表达，要能抓住决策问题的关键，在真实性和可用性之间取得适当的平衡。 油库和加油站地理分布油品配送路线中国石油上海销售公司油品配送决策系统18一

8、次配送二次配送油品供应链原油供应商炼油厂油库工业客户/润滑油厂社会客户加油站工业客户分油库 中国石油上海销售公司上海地区嘉兴地区苏州地区湖州地区17个油库，300个加油站，1000多个固定大客户，分4个销售区域2003年销售汽油和柴油 200 万吨，物流成本近 1 亿元人民币 中国石油迫切需要解决的决策问题油品配送决策支持系统战略决策战术决策销售区域划分油品供应分配新建油库选址新建油库规模 日配送调度 多舱位油车调度 跨区域集中调度 紧急调度供应链问题 油品配送决策系统结构与特点先进的信息和控制技术Web、液位仪、GIS大规模、复杂的OR问题巨大数量的数据处理实时决策和人机交互系统要求与特点油

9、品配送决策系统日配送调度计划油品供应分配油库选址物流信息系统GIS系统Internet加 油 站油库车队液 位 仪 油库1车站1油库2加油站加油站加油站加油站车站2加油站加油站加油站加油站1#车辆的配送路线2#车辆的配送路线油品配送路线示意图 配送调度模型(超大型混合整数规划)定义网络 配送调度模型定义网络30 万条可行路线 配送调度模型决策变量 配送调度模型目标函数运输成本未达最佳配送量的惩罚未达最佳运载量的惩罚 配送调度模型每车至多行驶一条可行路线车辆对路线的限制车辆对配送油品种数的限制车辆装载油品限制约束条件 配送调度模型(超大型混合整数规划)约束条件需求约束供需平衡供应约束车辆装载限制

10、 配送调度的人机交互界面路线锁定/解锁按钮解的序列表示区备注区点重新定位按钮待重新定位点列表解的矢图表示区 油库列表 油库出油临时限制缩放功能 系统效果该系统完全改变了公司传统的调度管理方式，显著提高了配送调度的响应速度、决策的正确性和科学性，适应公司的扁平化管理的目标。承运商配送决策系统提货单/发货凭证加 油 站油 库液 位 仪业 务 接口 管 理主管公司管理系统提货单Internet设 备 接 口 管 理发 货 凭 证 系统效果通过使用该系统，中国石油上海销售公司的物流在产品资源分布、产品库存、运输成本、运输车辆、运输和管理人工等五个方面得到了改善，节省成本。根据该公司财务部估计，该系统可

11、使该公司全年的物流成本下降 1000 余万元人民币，节省物流成本10% 以上。 各种散装品的配送调度油品配送决策系统各种业态的实时配送调度第三方物流、邮政、快递的配送调度配送决策系统应用推广大型连锁超市的配送调度家电、乳品等专业销售的配送调度 可视化集成式油品销售物流决策系统 运筹学的分支数学规划线性规划 非线性规划整数规划 动态规划图与网络流 网络计划库存论排队论对策论决策论。 优化问题的分类确定性、静态优化问题数学规划（单目标、多目标）图与网络流决策论（多目标）确定性、动态优化问题动态规划（离散）最优控制（离散、连续）随机性优化问题随机规划存储论排队论决策论（单目标）多人竞争性决策问题博弈

12、论（对策论） 本课程的主要内容非线性规划（一维无约束极值问题）决策论博弈论排队论库存论本课程成绩构成平时30%+期末考试70%平时成绩 = 到课率+作业+论文或测验期末考试:闭卷笔试 非线性规划问题一般数学描述 目标函数或约束函数中至少有一个是非线性的应用背景有着最广泛的应用，应该说所有现实问题都是非线性的，线性模型都是经过简化而来的。机械、电子等行业的器件最优设计问题，如飞行器的结构优化设计等；管理科学中的应用问题更是不胜枚举；系统控制问题。 决策论（decision theory)著名经济学家西蒙有一句名言：“管理就是决策”。“决策”一词本身是一个广义的概念，本课程介绍的是针对在不确定或随

13、机环境下的决策分析方法。应用背景：产品开发决策问题、风险投资决策问题等等 博弈论（Game Theory) 博弈论博弈论研究的问题是：当一个主体，如一个人或一个企业的选择，受到其他人、其他企业选择的影响，而且反过来又影响到其他人、其他企业选择时的决策问题和均衡问题。博弃论又称为“对策论”.博弈论可以解释一些经济和社会现象，比如家电的价格战、民航业的价格战、国家之间的军备竞赛、“劣币逐良币”等等现象,解决竞争环境下的决策问题。 排队论银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等等的排队现象；排队论是运筹学的又一个分支，又叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构、

14、或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等 。 库存论存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施；由此带来一些需要决策的问题：库存量、进货量（如报童问题）、补货的时间等等决策量。库存问题也一直是供应链管理研究中的热点问题。非线性规划Nonlinear Programming 1.1 相关的数学知识一、一般数学描述可行域特别当R=En, 称为无约束优化问题 1.1 相关的数学知识二、解的定义全局最优解、严格全局最优解；局部最优解（极值点、极小点）三、多元函数的偏导偏导数：指函数沿某个坐标轴方向的变化率；

15、梯度：由各个坐标轴方向组成的向量；方向导数：指函数沿某个给定方向的变化率；常用的求梯度公式 1.1 相关的数学知识四、Hessian 矩阵（二阶导数矩阵）几个常用的公式五、正定矩阵定义正定二次函数六、多元函数的Taylor展开 1.1 相关的数学知识七、凸函数、凸规划凸集(convex set)：凸函数(convex )、凹函数(concave)：定义几何意义性质判别条件特别：线性函数既是凸函数也是凹函数凸规划(convex programming) 1.2 解的最优性条件一阶必要条件在极值点的梯度=0二阶充分条件二阶导数矩阵为正定矩阵 1.3下降搜索算法目标函数的等值线（二维，等高线）对二次

16、函数，等值线是一族同心的椭圆；对于非二次函数，在极小点附近，等值线近似一族同心椭圆；具有不同值的等值线不相交；等值线稠密处目标函数变化快，稀疏处变化慢；等值线上一点的梯度与该点的的等值线切线方向相互垂直。 1.3下降搜索算法算法：给定一个初始点X0，然后按照一定的规则产生一个点列Xk，这种产生点列的规则称为算法；下降算法的规则：给定一个初始点X0 ，在点Xk选择一个方向 (向量) Pk, 并沿此方向选择一点Xk+1=Xk+tkPk使得f(Xk+1)f(Xk)。 X0P0P1X1X2P2P3X3X*X4 1.3下降搜索算法算法步骤中的关键要素：给定初始点；确定寻优方向；确定一个步长；判别是否满足

17、终止条件 下降搜索算法下降算法的规则：给定一个初始点X0 ，在点Xk选择一个方向 (向量) Pk, 并沿此方向选择一点Xk+1=Xk+tkPk使得f(Xk+1)f(Xk)。不同的寻优方向选择方法构成不同的算法；有两类方法：解析法利用函数的梯度来构造寻优方向；直接法利用函数值来构造寻优方向；1.4 多维无约束寻优算法简介The Multi-Dimensional Search Procedure 最速下降法（梯度法）The Steepest descent method The Gradient Method基本思想：以负梯度方向作为寻优方向算法步骤：(举例说明)特点：迭代过程简单，存储量少，计

18、算量小；即使是正定二次函数也不能有限步收敛；相邻两次寻优方向是垂直的;寻优路线呈锯齿状（Zig-Zag)，在极小点附近收敛缓慢; X0P0P1X1X2P2P3X3X*X4 其他解析算法共轭梯度法(Conjugate gradient method) 牛顿法（Newtons method) 变尺度法 （Variable Metric Method) （拟牛顿法Quasi-Newton method） 有约束优化问题的算法解的最优性条件Kuhn-Tucker 条件求解算法直接法：可行方向法，梯度投影法等间接法：将有约束问题转换成一系列的无约束问题来求解，如惩罚函数法，乘子法等1.5 一维寻优方法T

19、he One-Dimensional Search Procedure优选法数学家华罗庚他是中国解析数论、典型群、矩阵几何学、自守函数论与多复变函数论等很多方面研究的创始人与开拓者。 优选法是快速寻找最佳方案的科学方法。具体的优选法有很多，如黄金分割法、分数法、对分法等。黄金分割法也称0.618法。 如在炼钢时需加入某种元素来增加钢材强度，若将试验点取在这一元素用量区间的0.618处，获得理想用量的试验次数将大大减少。 实验证明，对一个因素的优化问题，用优选法做16次试验，就可达到“对分法”做2000余次试验的效果。 一、“成功-失败”法基本思想“成功”则大步向前，“失败”则小步后退框图特点简

20、单易行，对初始点选择无严格限制；适用于不可微的函数；在极小点附近收敛慢；可用此方法来确定一个搜索区间。 二、牛顿法（切线法）基本思想：适合二阶连续可微的函数，求导数为0的方程根。迭代公式算法步骤特点适用于二阶可微函数；最快的收敛速度，二阶收敛速度；初始点要求接近极小点；可与“成功-失败”法联合使用。 序贯实验法单峰函数（Unimodal Function,下单峰、单谷) 定义（在极小点左边单调下降，右边单调上升）性质( Unimodality，单峰性)基本思想：通过选择实验点，计算其函数值，比较实验点的函数值大小，缩小包含极值点的区间 二分搜索法The Dichotomy Method wit

21、hout Derivatives基本思想对称取点，等比例缩小区间特点：简单对称取点，不论取哪个区间，其长度相等；每次要计算两次函数值 黄金分割法（0.618法)The Golden Section Search Method基本思想：对称取点，等比例的缩小区间，除第一次外，每次只需计算一次函数值，可使区间缩小。b0a0t11t12b1a1f(t11)f(t12)t22t21 黄金分割法（0.618法)The Golden Section Search Method实验点的计算公式算法步骤特点：具有相同的区间缩短率0.618；精度不如Fobonacci分数法；适用于不可微、不连续函数，可以先用“

22、成功-失败”法搜索到一个包含极小点的区间。 Fibonacci分数法The Fibonacci Search Method问题：如何选择实验点，计算n次函数值能得到多大的区间缩短率？换句话说，计算n次函数值能将多大的区间缩短到1。答案：若对称取点，利用上次已有的实验点的函数值，计算n次函数值可获得1/Fn区间缩短率。 Fibonacci分数法Fibonacci 数列 (Fibonacci Sequence) F0=1, F1=1, F2=2, F3=3, F4=5, Fk=Fk-1+Fk-2实验点的计算公式计算步骤算例 Fibonacci 分数法特点：需要预先确定迭代次数n;在计算n次函数值情

23、况下，该方法获得最大的区间缩短率，精度最高；适用于不可微、不连续函数。 作业P196, 6.12, 6.13, 6.141.6 最优化技术的新发展 最优化技术的发展1940s1970s：数学规划阶段目标和约束是解析函数； 1970s2000s：智能优化阶段目标和约束可以放宽为含有判断逻辑的计算机程序； 2000s未来：基于仿真优化阶段用大量仿真的统计数据来进行性能评价。 最优化技术的基本步骤 搜索：在定义域内寻找最优解；评估：按照问题的目标对解的质量进行评价；选择 ：对获得的解进行比较，判断，选择。 对于迭代算法还要判断终止条件。 数学规划方法数学规划-线性规划，非线性规划，动态规划，数学规划

24、的基本步骤三步曲选一个初始解；LP:大M，二阶段法NLP:任意点或一个内点 数学规划方法（2）停止判据停止规则最优性检验；LP:检验数当0时有可能减小NLP: 数学规划方法（3）向改进方向移动改进解LP:转轴变换(进基、退基)NLP:向负梯度方向移动(共轭梯度方向、牛顿方向) 数学规划方法（4）停机选择一个初始解 停止准则向改进方向移动启动YN评估解问题：解的评估呢？评估解 数学规划方法（5）数学规划方法的局限性对问题中目标函数、约束函数有很高的要求有显式表达，线性、连续、可微，且高阶可微;只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；最优性达到的条件太苛刻问题的目标函数为凸函

25、数，可行域为凸集；在非双凸条件下，没有跳出局部最优解的能力。 实际优化问题往往不满足双凸条件 智能优化方法智能优化方法的产生对问题的描述要宽松(目标和约束函数) 可以用一段程序来描述(程序中带判断、循环)，函数可以非连续、非凸、非可微、非显式；并不苛求最优解通常满意解、理想解就可以了；计算快速、高效,可随时终止(根据时间定解的质量)。 智能优化方法（2）智能优化方法的好多名字：高级启发式(Advanced Heuristics)智能优化(Intelligent Optimization)计算智能(Intelligent Computation)进化计算(Evolutionary computa

26、tion)软计算(Soft Computation)自然计算(Natural Computation) 智能优化方法（3）智能优化的主流算法：1975年Holland提出遗传算法(Genetic Algorithm)-GA1977年Glover提出禁忌搜索算法(Tabu Search)-TS1982年Kirkpatrick提出模拟退火算法(Simulated Annealing)-SA1995年Dorigo提出蚁群算法(Ant Colony Optimization)-ACO1995年Kennedy & Eherhart提出粒子群优化 (Particle Swarm Optimization)-PSO 智能优化方法（6）智能优化算法的计算量分析：GA的评估次数：遗传代数种群大小TS的评估次数：迭代次数领域大小SA的评估次数：降温次数内循环次数隐含假设是：目标函数的计算（解的评估）很容易，所以根本不注意节省计算次数。重复计算不可避免。