第一章 概述ppt课件.ppt

《第一章 概述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、参考书.陈宝林《最优化理论与算法》.解可新等《最优化方法》.薛嘉庆《最优化原理与方法》.盛昭瀚等《最优化方法基本教程》.部分英文教材1ChapterOne概述及预备知识2最优化又称数学规划(MathematicalProgramming),大约在1947年诞生,是运筹学(OperationResearch)的一个分支.概括地说，最优化就是从所有可能的方案中选取最合理的一种以达到最优目标的学科。达取最优化目标的方案就是最优方案，搜寻最优方案的方法就是最优化方法，这种方法的数学理论就是最优化理论。1.1最优化定义（optimization）SectionOne最优化问题的数学模型与基本概念31.2

2、优化分类优化理论与算法线性规划非线性规划动态规划整数规划几何规划随机规划网络规划拓扑规划……组合规划4按照问题涉及到的变量是否是离散变量进行分类：具有连续变量的优化问题（我们本学科的讲授内容，也即我们通常所讲的优化）具有离散变量的优化问题（组合最优化问题）这两类问题具有不同的特点，所以解决这两类问题的方法也是完全不同的。由于现实世界的绝大多数问题都是处于离散状态，所以目前组合优化问题作为侧重于应用的运筹技术之一，得到日益广泛的应用。5附组合优化问题技术及其应用简介组合最优化对于具有离散变量的问题，从有限个解中寻找最优解的问题就是组合最优化问题。简单应用：古老的婚配问题一个遥远的地方，一个酋长的

3、三人女儿A，B，C准备嫁给三个求婚者D，E，F。按当地习俗，求婚者必须向酋长交纳一定数量的牛作为财礼。设已知求婚者愿意对酋长的每个女儿提供的牛的数量。假设酋长只以获得尽可能多的牛为目的，试找出一种方案。6组合最优化的应用举例1．最短路问题管道铺设路线费用最少货物运输时间最短（费用最少）通讯路线最可靠2．最小支撑树问题电话通讯网的架设地区交通网络的建设73.决策树模型.市场风险投资决策.技术引进决策.产品推销策略4．分配问题.分房问题.有限资源的最佳配置5．网络计划技术.有效组织实施工程86.网络流问题.交通流量最大.物流运输费用最少7．网络图的其他一些应用问题.欧拉图.机关设计问题.汽车共用问

4、题.工厂选址问题9组合最优化的应用成功应用领域举例平板的最优激光铅化油田的最优勘探血液银行的管理考古发掘物的顺序排列基因密码计算机切割的最优安排消防队和灾情点的调试计划垃圾清除或街道清洗的调度计划按订货以最小角边料切割纸或钢材等公交汽车线路的最优安排或链接10最优化理论与方法目前已渗透到生产、管理、商业、军事和决策等各个方面。1.3优化应用案例案例一　生产活动安排问题案例二　工厂（市场）选址问题11问题描述设有m种资源B1,…,Bm,它们的可使用量分别为b1,…,bm,用于生产n种产品A1,…,An,设生产1个产品Aj需消耗资源Bi的单位数为aij，而产品Aj每单位的利润为cj，问如何安排生产

5、活动可使总利润最大？案例一　生产活动安排问题12题设:为了使总利润最大，要生产Aj的量为xj：c1c2c3……cnA1A2A3……Anx1x2x3……xn总利润：生产条件约束：资源数量的限制，即用于生产的资源不能超过每种资源的总量…b1b2…bmB1B2…Bma11a21…am1a12a22…am2a13a23…am3a1na2n…amn.....A1A2A3……An13数学模型s.t.¨¨max“s.t.”即subjectto,表示变量的约束条件“Max”即maximum,表示最大值，同样，可用“min”表示极小值minimum14案例二　工厂（市场）选址问题问题描述设有n个市场，第j个市场

6、的位置为(aj,bj)，对某种货物的需求量为qj，j=1,2,…n。现计划建立m个货栈，第i个货栈的容量为ci，i=1,2,…m。试确定货栈的位置，使各货栈到各市场的运输量与路程的乘积最小。15引入数学符号：(xi,yi)：第i个货栈的位置，i=1,2,…mWij：第i个货栈供给第j个市场的货物量i=1,2,…m，j=1,2,…ndij：第i个货栈到第j个市场的距离运输量与路程的乘积和162。每个市场从各货栈得到的货物量等于它的需求量3。货物的运输量不能为负问题的条件约束：1。每个货栈向各市场的货物供应量不能超过它的容量17确立数学模型18最优化问题的一般形式优化问题就是求目标函数在约束条件下

7、的极小点...m=l=0称为无约束问题,否则称为约束最优化问题..f,si,hj都为线性函数称为线性规划问题,..否则为非线性规划问题f:RnR1目标函数x:n维的列向量Si:RnR1等式约束Hj:RnR1不等式约束19最优化问题的向量形式minf(x)s.t.s(x)0h(x)=0其中201.4基本概念可行解若xRn满足所有约束条件:即xD={x

8、si(x)0,hj(x)=0,i=