版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、最优化及最优化方法,最优化是一门应用十分广泛的学科,它研究在有限种或无限种可行方案中挑选最优方案,构造寻求最优解的计算方法。达到最优目标的方案,称为最优方案,搜索最优方案的方法,称为最优化方法。这种方法的数学理论,称为最优化理论。 最优化方法(也称做运筹学方法)是近几十年形成的,它主要运用数学方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。,最优化方法的研究对象及应用,最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统,求得一个合理运用人力、物 力和财力的最佳方案,发挥和提高系统的效能及效益,最终达到系统的最优目标。 实践表明
2、,随着科学技术的日益进步和生产经营的日益发展,最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法,被人们广泛地应用到空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、公共管理、经济管理等各个领域,发挥着越来越重要的作用。,最优化方法的具体应用举例,最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方面。 最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中,从各种设计参数的优选到最佳结构形状的选取等,结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的
3、最优设计是另一个应用最优化方法的重要领域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展(见优选法)。,最优化方法的具体应用举例, 最优计划:现代国民经济或部门经济的计划,直至企业的发展规划和年度生产计划,尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。 最优管理:一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用,使最优管理得到迅速的发展。,最优化方法的具体应用举例,最优控制:主要用于对各种控
4、制系统的优化。例如,导弹系统的最优控制,能保证用最少燃料 完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控制,化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化方法的进一步发展,还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制。,最优化的发展简史,最优化是一个古老的课题。长期以来,人们对最优化问题进行着探讨和研究。 公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1. 618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前,已有许多学者开
5、始研究用数学方法解决最优化问题。例如阿基米德证明:给定周长,圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。,最优化的发展简史,但是最优化方法真正形成为科学方法则在17世纪以后。 17世纪,I.牛顿和G.W.莱布尼茨在他们所创建的微积分中,提出求解具有多个自变量的实值函数的最大值和最小值的方法,后来又出现Lagrange乘数法。以后又进一步讨论具有未知函数的函数极值,从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。,最优化的发展简史,第二次世界大战前后,由于军事上的需要和科学技术和生产的迅速发展,许多实际的最优化问题已经无法用古典方法来解决,这就促进了近代最优化方法的
6、产生。 近代最优化方法的形成和发展过程中最重要的事件有: 1847年法国数学家Cauchy研究了函数值沿什么方向下降最快的问题,提出最速下降法。 1939年前苏联数学家.B.提出了解决下料问题和运输问题这两种线性规划问题的求解方法。,最优化的发展简史,以苏联 .康托罗维奇和美国G.B.丹齐克为代表的线性规划; 以美国库恩和塔克尔为代表的非线性规划;以美国R.贝尔曼为代表的动态规划; 以苏联.庞特里亚金为代表的极大值原理等。这些方法后来都形成体系,成为近代很活跃的学科,对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用。,最优化方法的内容,最优化方法包括的内容很广泛,如线性规划、非
7、线性规划、整数规划、几何规划、动态规划、随机规划、多目标规划、组合优化(在给定有限集的所有具备某些条件的子集中,按某种目标找出一个最优子集的一类数学规划)等等。,几何规划,非线性规划的一个分支。是最有效的最优化的方法之一。几何规划最初是由数学家R.J.达芬和 E.L.彼得森及C.M.查纳等人于1961年在研究工程费用极小化问题基础上提出的,直到1967年几何规划一书出版后才正式定名。几何规划的数学基础是G.H.哈代的平均理论。由于几何平均不等式的关键性作用,几何规划由此得名。几何规划的目标函数和约束条件均由广义多项式构成 ,这是一类特殊的非线性规划,利用其对偶原理,可以把高度非线性问题的求解转
8、化为具有线性约束的优化问题求解,使计算大为简化。几何规划理论研究和算法软件开发、发展都很快,并且在化工、机械、土木、电气、核工程等部门的工程优化设计和企业管理、资源分配、环境保护以及技术经济分析等方面都得到广泛应用。,整数规划,整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划。是近三十年来发展起来的、规划论的一个分支. 整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。 一般认为非线性的整数规划可分成线性部分和整数部分,因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求解答必须是整数。例如,所求解是机器的台
9、数,工作的人数或装货的车数等。为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划。,在整数规划中,如果所有变量都限制为整数,则称为纯整数规划;如果仅一部分变量限制为整数,则称为混合整数规划。整数规划的一种特殊情形是0-1规划,它的变数仅限于0或1。 整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ,30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题,称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题(衍生问题称为松弛问题的源
10、问题)。通过松弛问题的解来确定它的源问题的归宿,即源问题应被舍弃,还是再生成一个或多个它本身的衍生问题来替代它。随即 ,再选择一个尚未被舍弃的,或替代的原问题的衍生问题,重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法,它们都是在上述框架下形成的。 01规划在整数规划中占有重要地位,一方面因为许多实际问题,例如指派问题、选地问题、送货问题都可归结为此类规划,另一方面任何有界变量的整数规划都与01规划等价,用01规划方法还可以把多种非线性规划问题表示成整数规划问题,所以不少人致力于这个方向的研究。求解01规划的常用方法是分枝定界法,对各种特殊问题还有一
11、些特殊方法,例如求解指派问题用匈牙利方法就比较方便。,组合最优化,在给定有限集的所有具备某些条件的子集中,按某种目标找出一个最优子集的一类数学规划。又称组合规划。从最广泛的意义上说,组合规划与整数规划这两者的领域是一致的,都是指在有限个可供选择的方案的组成集合中,选择使目标函数达到极值的最优子集。 组合最优化发展的初期,研究一些比较实用的基本上属于网络极值方面的问题 ,如广播网的设计 、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后,对拟阵中的一些理论问题的研究成为组合规划研究的新课题,并得到应用。现在应用的主要方面仍是网络上的最优化问题,如最短路问题
12、、最大(小)支撑树问题、最优边无关集问题、最小截集问题、推销员问题等。,整数规划与组合最优化的关系,整数规划与组合最优化从广泛的意义上说,两者的领域是一致的,都是在有限个可供选择的方案中,寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如,背袋(或装载)问题、固定费用问题、和睦探险队问题(组合学的对集问题)、有效探险队问题(组合学的覆盖问题)、送货问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。,随机规划,随机规划是对含有随机变量的优化问题建模的有效的工具并已有一
13、个世纪的历史。 第一种随机规划是美国经济学家丹泽1955年提出的,康托罗维奇在这方面的贡献,不在于这个新方法本身,而在于把它应用于制定最优计划。是广泛使用的期望值模型,即在期望约束条件下,使得期望收益达到最大或期望损失达到最小的优化方法。 第二种是由查纳斯(A.Charnes)和库伯(W.W.Cooper)于1959年提出的机会约束规划,是在一定的概率意义下达到最优的理论。 第三种即是刘宝碇教授于1997年提出的相关机会规划,是一种使事件的机会在随机环境下达到最优的理论。它与期望值模型和机会约束规划一起构成了随机规划的三个分支。,随机规划是处理数据带有随机性的一类数学规划,它与确定性数学规划最
14、大的不同在于其系数中引进了随机变量,这使得随机规划比起确定性数学规划更适合于实际问题。在管理科学、运筹学、经济学、最优控制等领域,随机规划有着广泛的应用。 随机规划的求解方法 随机规划的求解方法大致分两种。 第一种是转化法,即将随机规划转化成各自的确定性等价类,然后利用已有的确定性规划的求解方法解之; 另一种是逼近方法,利用随机模拟技术,通过一定的遗传算法程序,得到随机规划问题的近似最优解和目标函数的近似最优值。,讲授内容,教材:最优化方法及应用案例 .绪论 .线性规划 .非线性规划 .动态规划 .多目标优化及其应用,预备知识和学习要求,学习该课程的需要具备的基本知识 高等数学 线性代数 学习
15、该课程的要求 态度决定一切 正确理解基本概念和原理 掌握最优化方法的思想 能够运用最优化方法分析解决实际问题,最优化问题的数学模型一般形式,最优化问题,(目标函数),(不等式约束),(等式约束),其中,最优化问题分类,经典优化问题(静态优化问题)和现代优化问题(动态优化问题) 1、经典优化问题(静态优化问题) 根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题; 根据目标函数和约束函数的函数类型分类:线性最优化问题(整数规划、规划)、非线性最优化问题、二次规划、多目标规划。 2、现代优化问题(动态优化问题) 动态规划与最优控制问题 组合优化问题,最优解的相关定义,定义.1 可
16、行解满足约束条(1.2)和(1.3) 的x称为可行解,也称为可行点或容许点。,定义.2 可行域全体可行解构成的集合称为可行域,也称为容许集,记为D,即:,定义.3 整体(全局)最优解,对于一切,则称,恒有,为最优化,问题的整体(全局)最优解。,若,恒有,则称,为最优化,问题的严格整体,(全局)最优解。,定义.4 局部最优解若:,存在,的某邻域,使得对于一切,恒有,则称,为最优化问题的局,部最优解。,其中,同样有:严格局部最优解。,而局部最优解不一定是整体最优解。,显然,整体最优解一定是局部最优解,,注意:,求解最优化问题,实际上是求可行域,D上的整体最优解。,但是,,在一般情况下,,整体最优解
17、是很难求出的,往往只能求出局部最优解。,定义.5 范数:,在,维向量空间,中,,定义实函数,使其满足以下三个条件:,()对任意,有,在,当且仅当,时,()对任意,及实数,有,()对任意,有,则称函数,为,上的向量范数。,两类比较常见的范数,P-范数:,其中最常用的是2-范数,即:,范数:,最优化方法概述,求解 的一种算法,通常是指一种产生点列的程序。常表现为 的一种映射F,它常常满足以下两点要求: (1) ;(2) 式(1)实际上常表现为 。因此通常构造映射F的关键就在于设计一种能从 出发,确定方向 与步长 的方法,要求满足式(2)并使整个序列(或子列)具有收敛性。,迭代算法,选取一个初始可行
18、点 由这个初始可行点出发,依次产生一个可行点列:,恰好是问题的一个最优解,或者该点列 收敛到问题的一个最优解。,可行点列的产生,在,处求得一个方向,(可行下降方向),在射线,上求一点:,使得,其中,称为步长。,下降方向,定义1.6,下降方向:,在点,处,,对于方向,若存在实数,使得任意的,有:,成立,,则称,为函数,在点,处,的一个下降方向。,当,具有连续的一阶偏导数,令,由Taylor公式:,当,时,有,所以(,充分小时),是,在,处的一个,下降方向。,通常称满足:,的方向,为,在,处的下降方向。,可行方向,定义1.7,可行方向:,已知区域,对于向量,若存在实数,使得任意的,有:,则称,为,
19、点处,关于区域,的可行方向。,下降方向关于区域,可行,则称为可行下降,方向。,最优化问题的算法的一般迭代格式,给定初始点,令,()确定,处的可行下降方向,()确定步长,使得:,()令,()若,满足某种终止准则,则停止;,否则令,转(),收敛性,如果一个算法只有当初始点充分接近最优解时,产生的点列才收敛,则称该算法为具有局部收敛的算法。,如果对任意的初始点,由算法产生的点列都收敛,则称该算法为具有全局收敛的算法。,具有全局收敛性的算法才有实用意义。但对算法的局部收敛性分析,在理论上是重要的,因为它是全局收敛性分析的基础。,收敛速度,定义1.8,设序列,收敛于,而且,若,则称序列,为线性收敛的,称
20、,为收敛比;,若,则称序列,为超线性收敛的。,收敛速度,定义1.9,设序列,收敛于,若对,则称序列,为,有:,阶收敛的。,特别当:,时称为二阶收敛的。,终止准则,对于一种算法,应该有某种终止准则,当某次迭代,满足终止准则时,就停止迭代。常用的终止准则有:,(1),或,或,(),其中,是预先给定的。,(2),最优化模型的建立,建立数学模型:在对实际问题深入研究的基础上, 利用有关数学的知识和概念,对自然规律的真实 描述(数学描述)或模拟。 实例分析 1、生产计划问题 资源分配问题 书第4-5页例 第195页 资源分配问题就是将数量一定的一种或若干种资源(例如原材料、资金、设备、设施、劳力等),恰
21、当地分配给若干使用者或地区,从而使目标函数最优。,线性规划模型,2、食谱问题 设市场上可买到 种不同的食品,第 种食品的单位售价为 。每种食品含有 种基本营养成分,第 种食品每一个单位含有第 种营养成分为 。又设每人每天对第 种营养成分的需要量不少于 。试确定在保证营养要求条件下的最经济食谱。,线性规划模型,3、选址问题(类似的问题P89) 某城市要建设一个煤气供应中心,该中心向城市中 个用户(用户位置固定)提供输送煤气服务。对于给定的坐标系而言,已知第 个用户位置的坐标为 。如果输送管道不受道路影响(即只考虑直线距离),问如何确定该中心的位置,才能使总的输送管道最短,同时中心到第 个用户的距
22、离必须介于 和 之间 。,非线性规划模型,4、最短路问题(图论极值问题) 或最优管道铺设问题 (类似问题166页),动态规划模型,线性规划,1、线性规划模型的建立 2、线性规划模型的寻优,线性规划模型的建立,建立优化模型的三大要素 (1)确定决策变量 (2)确定目标(决策准则) (3)确定约束条件 实例分析 (1)生产计划 资源分配问题,例2.1 某厂计划在下一个生产周期内生产甲、乙两种产品,需要消耗R1、R2、和R3三种资源(例如钢材、煤炭或设备台时等),已知每件产品对这三种资源的消耗、这三种资源可供使用的量及每单位产品可获得的利润如表2.1所示。问应如何安排生产计划,使得既能充分利用现有资
23、源,又使总利润最大?试建立问题的数学模型。(P10-11),表2-1,(2)原材料的合理利用问题(P11-12),(3)0-1背包问题(P12) 背包问题(P13),(4) 运输问题,(5)分派(指派)问题,线性的特点,比例性 可加性,共同的特征,每一个线性规划问题都用一组决策变量 表示某一方案,这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的; (2) 要有各种资源 和使用有关资源的技术数据,创造新价值的数据;,共同的特征(继续),(3) 存在可以量化的约束条件,这些约束 条件可以用一组线性等式或线性不等式 来表示; (4) 要有一个达到目标的要求,它可用决策 变量的线性函
24、数(称为目标函数)来表示。 按问题的不同,要求目标函数实现最大化 或最小化。,它们的对应关系可用表格表示:,线性规划的一般模型形式,线性规划模型的标准形式,线性规划模型的几种表示形式,向量表示式,矩阵表示式,如何变换为标准形,(1) 当目标函数为求极(最)大值时,即 , 这时只需令 ,即转化为 。这就同标准形的目标函数的形式一致了。 (2) 约束方程为不等式。这里有两种情况:一种是约束方程为“”不等式,则可在“”不等式的左端加入非负松弛变量,把原“”不等式变为等式;另一种是约束方程为“”不等式,则可在“”不等式的左端减去一个非负剩余变量(也可称松弛变量),把不等式约束条件变为等式约束条件。,如
25、何变换为标准型(续),(3)当约束条件的右端常数项 时,只需将等式或不等式两端同乘以 即可。 (4)当决策变量的取值约束为 时,令 ,则有 。 (5)当决策变量的取值无任何约束时,令 ,则由 表示的 不受任何取值的约束。,线性规划的分类,线 性 规 划,一般线性规划,特殊线 性规划,整数规划,运输问题,纯整数规划,混合整数规划,0-1规划,指派问题的 线性规划,解的相关概念,基本概念 定义2.1 在线性规划问题中,凡是满足其全部约束条件(包括变量取值约束)的一组决策变量的取值称作该线性规划问题的可行解。 定义2.2 线性规划问题中,可行解的集合称为该问题的可行域。 定义2.3 在线性规划问题的
26、可行域中,使目标函数值达到最优(最大或最小)的可行解称为该问题的最优解。相应的目标函数值称为最优值。,凸集,定义1,设集合,若对于任意两点,及实数,都有:,则称集合,为凸集,注:,常见的凸集:空集,整个欧氏空间,超平面:,半空间:,例1:,证明超球,为凸集,证明:,设,为超球中的任意两点,,则有:,即点,属于超球,所以超球为凸集,凸集的性质,(),有限个(可以改成无限)凸集的交集,为凸集,(),设,是凸集,,是一实数,,则下面的,集合是凸集:,(),设,是凸集,,则,的和集,是凸集,注:,和集和并集有很大的区别,凸集的并集,未必是凸集,而凸集的和集是凸集,例:,表示,轴上的点,表示,轴上的点,
27、则,表示两个轴的所有点,,它不是凸集;,而,凸集,推论:,设,是凸集,,则,也是凸集,,其中,是实数,定义2:,设,实数,则,称为,的凸组合,注:,凸集中任意有限个点的凸组合仍然在该,凸集中,极点(顶点),定义1,设,为凸集,,若,中不存在,两个相异的点,及某一实数,使得,则称,为,的极点,例:,则,上的点均为极点,证:,设,若存在,及,使得,则:,不等式要取等号,必须,且,容易证明,根据定义可知,为极点,与算法有关的概念,无穷多解 图解法中,此情况出现在目标函数等值直线向优化方向平移时,最后与可行域边界的一条边重合,此时,除该直线段的两个端点(即可行域的两个顶点)外,直线段上所有点的目标函数
28、值都达到最优。 无界解 图解法中,此情况出现在可行域为无界区域,且目标函数等值直线向优化方向平移时,始终无法脱离可行域。发生这种情况往往是建模时遗漏了某些约束条件所至。 无解 当可行域为空集时,问题不存在可行解。发生此情况是因为模型中出现了相互矛盾的约束条件。,图解法中解的概念,与算法有关的概念,可行解、最优解 基、基向量、基变量 基解、基可行解 可行基,与单纯形法有关的解概念,可行解、最优解,满足约束条件(1-2),(1-3)式的解 称为线性规划问题的可行解,其中使目标函数达到最小值的可行解称为最优解。,基、基向量、基变量,基解、基可行解,基解:满足约束方程组(1-2)且非基变量为0的解。
29、基可行解:满足非负条件(1-3)的基解. 基可行解的非零分量的数目也不大于m,并且都是非负的。,可行基,对应于基可行解的基,称为可行基。 约束方程组(1-2)具有基解的数目最多是 个。一般基可行解的数目要小于基解的数目。 以上提到的几种解的概念,它们之间的关系可用图6表明。 另外还要说明一点,基解中的非零分量的个数小于m个时,该基解是退化解。在以下讨论时,假设不出现退化的情况。以上给出了线性规划问题的解的概念和定义,它们将有助于用来分析线性规划问题的求解过程。,可行解、基解、基可行解之间的关系,图6,与算法有关的概念,与内点法有关的解概念,与算法有关的概念,与其他算法有关的解概念,与算法有关的
30、概念,与其他算法有关的解概念,线性规划的寻优方法,图解法 单纯形方法 内点法 计算机求解 分支定界法 隐枚举法 表上作业法 匈牙利法,只有二个变量的线性规划问题,一般LP,特殊LP,整数线性规划问题,0-1规划问题,平衡运输问题,指派问题,重要的方法,图解法,对于只有两个变量的线性规划问题,可以采用在平面上作图的方法求解,称为图解法。 例1 用图解法求解 因存在 ,所以必须在直角坐标的第1象限内作图,求解。,(1)在平面直角坐标系上画出可行域,(2)画出目标函数等值线,并沿其法线方向平移等值线,以求得最优解。目标值在(4,2)点,达到最大值14,目标函数,图1,可能出现的几种情况,(1)无穷多
31、最优解(多重最优解),目标函数 max z=2x1+4x2,图3,(2)无界解,图4,(3)无可行解,当存在矛盾的约束条件时,为无可行域。,如果在例1的数学模型中增加一个约束条件:,该问题的可行域为空集,即无可行解,,不存在可行域,增加的约束条件,图5,小结,(1) 线性规划问题的模型特征 (2) 通过图解法了解如何求解线性规划 问题 (3) 为求解高维线性规划问题,必须建 立的概念,线性规划的单纯形方法,线性规划问题的几个定理 单纯形法的原理 初始基可行解的确定,线性规划问题的几个定理,定理1 若线性规划问题存在可行解,则问题的 可行域是凸集。 定理2 线性规划问题的基可行解对应线性规划 问
32、题可行域(凸集)的顶点(极点)。 定理3 若线性规划问题有最优解,则一定存在 一个基可行解是最优解。 结论:求解线性规划问题归结为找最优基可行 解, 即在其可行域(凸集)的顶点(极点) 中找使目标函数最小的顶点(极点)。,单纯形法的原理,单纯形方法的基本思想 从一个基可行解出发,求一个使目标函数值有所改善的基可行解;通过不断改进基可行解,力图达到最优基可行解。 它主要通过基可行解的转换完成。 基可行解的转换 考虑矩阵形式的标准形问题: 式中,最优性检验和解的判别,单纯形方法的计算步骤,步骤1 找一个初始基可行解(常用大M法和两阶法找)。 步骤2 解 步骤3 求单纯形乘子 ,解,使用表格形式的单
33、纯形方法,使用表格形式的单纯形方法,用单纯形法解下列问题:,初始基可行解的确定,大M法 基本思想:在约束中增加人工变量 ,同时改变目标函数 ,加上罚项 ,其中 是很大的正数,这样,在极小化目标函数的过程中,由于大 的存在,将使人工变量离基。 考虑线性规划问题,大M法,引进人工变量 ,研究下列问题: 用单纯形法求解线性规划问题(1-14),获得其解,它与(1-13)的解的关系如下:,大M法,达到问题(1-14)的最优解,且 ,这时得到的 为问题(1-13)的最优解。 达到问题(1-14)的最优解,且 ,这时问题(1-13)无可行解。 问题(1-14)不存在有限最优值,在单纯形表中, , 这时 问
34、题(1-13)无界。 问题(1-14)不存在有限最优值,在单纯形表中, , 这时 问题(1-13)无可行解。,大M法,用大M法求解下列问题:,两个阶段法,基本思想:在约束中增加人工变量 ,以构造一个单位矩阵。对添加了人工变量的线性规划问题分两个阶段计算。 第一阶段是用单纯形方法消去人工变量(如果可能的话),即把人工变量 都变成非基变量,求出原来问题的一个基本可行解。消去人工变量 的一种方法是解下列第一阶段问题:,两个阶段法,求解(1-16),设得到的最优基本可行解是 ,此时必有下列三种情形之一: 这时(1-13)无可行解。 的分量都是非基变量,这时的基变量都 是原来的变量,又知 是(1-16)
35、的基可行解,因此 是(1-13)的一个基可行解。,两个阶段法,的某些分量是基变量,这时可用主元消去法,把原来变量中的某些非基变量引进基,替换出基变量中的人工变量,再开始两阶段法的第二阶段。应该指出,为替换出人工变量而采用的主元消去法,在主元的选择上,并不要求遵守单纯形法确定离进基变量的规则。 两阶段法的第二阶段,就是从得到的基可行解出发,用单纯形方法求(1-13)的最优解。即在问题(1-16)中去掉人工变量,以第一阶段最后的基变量为初始基变量开始迭代。操作上可直接在第一阶段的最终单纯形表基础上进行,只需在表中除去人工变量列、恢复目标价值向量为原问题之前的状况即可。,两个阶段法,用两阶段法求解下
36、列问题:,内点法,卡玛卡(Karmarkar)算法 -投影尺度法 在大型问题的应用中,显示出能与单纯形法竞争的潜力 不能直接用于通常形式的线性规划问题 原仿射尺度法 (改进的内点法 ) 可以直接求解标准形式的线性规划问题,理论依据,定理2.5 在仿射尺度变换 下, 的正卦限中的点仍变为正卦限中的点,但其分量值发生变化。特别地, 的像点为 。 定理2.6 设为行满秩矩阵 ,则向量 在 的零空间上 的正交投影为,基本思想,先找出一个内点可行解 ;从该点出发,在可行域的内部寻求一个使目标函数值下降的可行方向,沿该方向移动到一个新的内点可行解 ;如此逐步移动,当移动到与最优解充分接近时,迭代停止。,计
37、算步骤及框图,计算步骤 (P41-42) 关键的问题是:对于任一迭代点 ,如何求得一个适当的移动方向 ,使 是一个改进的内点可行解。 利用仿射尺度变换 的逆变换 定理2.5-2.6,可找到: ,计算框图P42,例题及初始内点可行解的确定,例2.10 用原仿射尺度算法求解如下问题(P43-44) 初始内点可行解的确定(P44) 方法:类似于单纯形方法的大M法。,线性规划问题的计算机求解,现在已经出现了很多能够求解线性规划问题的计算机软件产品,如Lindo,Lingo或Matlab等。下面以Matlab 6.x 为背景,介绍如何在Matlab中求解线性规划。 将模型转换成如下“标准形式”:,线性规
38、划问题的计算机求解,在上述标准形式中,目标函数求极小,约束条件严格地分为三类:不等式约束且取“ ”不等号、等式约束及变量取值范围约束。其中,线性规划问题的计算机求解,调用时需注意以下几点: (1)Matlab提供了一种机制,允许调用某个函数时提供 的参数个数少于定义该函数时所定义的参数个数。因此,在调用函数linprog传递参数时必须按语法指定的顺序对应传递,若缺少某些参数,除非其位于参数表的尾部,否则调用时必须以空数组“”形式占位。 (2)若问题的模型为目标函数求最(极)大,须先将目标函数转换为最(极)小。 (3)代码中所使用的标点分隔符,如逗号、分号、括号等,必须是半角字符。,线性规划问题
39、的计算机求解,写出下列问题的Matlab调用代码:,分支定界法 与隐枚举法,解决的问题各是什么? 理论依据 Discuss 基本思想 计算步骤及框图 计算中的说明 计算机求解的异同? 讲P62例2.13 练P90 7(1),分支定界法的计算框图,隐枚举法的计算框图,表上作业法 与匈牙利法,解决的问题各是什么? 理论依据 Discuss 基本思想 计算步骤及框图 计算中的说明 表上作业法是单纯形法在求解运输问题时的一种简化方法,其实质是单纯形法。 结合算法步骤讲P63例2.14和P67例2.15.,表上作业法的计算框图,匈牙利法的计算框图,第三专题 非线性优化问题,1、非线性优化模型的建立 2、
40、非线性优化模型的寻优,非线性优化模型的建立,确定决策变量 确定目标(决策准则) 确定约束条件,实例分析,(1)投资决策问题(P88) (2)曲线拟合问题 在实验数据处理或统计资料分析中,常常遇到这样的问题:如何利用有关变量的实验数据(资料)去确定这些变量间的函数关系。例如,已知某物体的温度 与时间 之间有如下形式的经验函数关系: 其中 是待定参数。通过测试获得n 组温度与时间之间的实验数据 ,试确定参数 使理论曲线尽可能地与 n个测试点拟合。,非线性规划问题的共同特征,都是求一个目标函数在一组约束条件下 的极值问题。 在目标函数或约束条件中,至少有一个是变量的非线性函数。,非线性规划问题,一般
41、形式: 向量形式:,非线性优化问题的寻优,相关概念及理论 一维最优化方法 多维无约束最优化方法 多维有约束最优化方法,非线性规划的相关概念及理论,一阶导数、二阶导数和n元函数的Taylor公式,定义4,设函数,定义在凸集,上,,若对任意的,及任意的,都有:,则称函数,为凸集,上的凸函数,定义5,严格凸函数,注:,将上述定义中的不等式反向,可以得到,凹函数的定义,凸函数,例1:,设,试证明,在,上是严格凸函数,证明:,设,且,都有:,因此,在,上是严格凸函数,例2:,试证线性函数是,证明:,设,上的凸函数,则,所以,是凸函数,类似可以证明,是凹函数,凸函数的几何性质,对一元函数,在几何上,表示连
42、接,的线段,表示在点,处的,函数值,所以一元凸函数表示连接函数图形上任意两点,的线段总是位于曲线弧的上方,凸函数的性质,(),设,(),设,函数,,是凸集,上的凸函数,,实数,则,也是,上的凸函数,是凸集,上的凸,实数,则,也是,上的凸函数,(),设,是凸集,上的凸函数,,是实数,,则水平集,是凸集,下面的图形给出了凸函数,的等值线的图形,可以看出水平集是凸集,凸函数的判定,定理1,设,上,,令,则:,(1),是定义在凸集,是凸集,上的凸函数的充要条件是对,任意的,一元函数,为,上的凸函数.,(2),设,若,在,上为严格,凸函数,,则,在,上为严格凸函数,该定理的几何意义是:凸函数上任意两点之
43、,间的部分是一段向下凸的弧,一阶条件,定理2.1,设在凸集,上,可微,,则:,在,上为凸函数的充要条件是对任意的,都有:,定理2.2,严格凸函数(充要条件),二阶条件,定理3,设在开凸集,内,二阶可微,则,(1),是,内的凸函数的充要条件为,,在,内任一点,处,,的海色矩阵,半正定,其中:,二阶条件,定理3,设在开凸集,内,(2),若在,内,正定,则,在,内,二阶可微,则,是严格凸函数,注:,反之不成立,例:,显然是严格凸的,,但在点,处,不是正定的,凸规划,定义6,设,为凸集,,为,上的凸函数,,则称规划问题,为凸规划问题,定理4,(1),凸规划问题的任一局部极小点,是,整体极小点,全体极小
44、点组成凸集,(2),若,是凸集,上的严格凸函数,,且凸规划问题,整体极小点存在,,则整体极小点是唯一的,非线性规划的最优性条件,最优性条件:是指非线性规划模型的最优解所要满足的必要和充分条件。 无约束最优性条件 约束最优性条件,无约束最优性条件,一(单)元函数的最优性条件,(),若,(),为,的局部极小点,,则,若,则,为,的严格局部极小点;,若,(),为,的局部极小点,,则:,多元函数的一阶必要条件(P106-107),定理1:,若,为,的局部极小点,,且在,内,一阶连续可导,,则,注:,(1),仅仅是必要条件,而非充分条件,(2),满足,的点称为驻点,驻点分为:极小点,极大点,鞍点,多元函
45、数的二阶充分条件,定理2:,若在,内,二阶连续可导,,且,正定,则,为严格局部,极小点,注:,如果,负定,则,为严格局部极大点,二阶必要条件和充要条件,定理3:,若,为,的局部极小点,,且在,内,二阶连续可导,,则,半正定,定理4:,设,在,上是凸函数且有一阶连续,偏导数,,则,为,的整体极小点的充要,条件是,例1:,利用极值条件解下列问题:,解:,令,即:,得到驻点:,函数,的海色阵:,由此,,在点,处的海色阵依次为:,由于矩阵,不定,,则,不是极小点,负定,,则,不是极小点,,实际上它是极大点,正定,,则,是局部极小点,约束最优性条件(p133-p136),定义1:,有效约束:,若(*)中
46、的一个可行点,使得,某个不等式约束,变成等式,,即,则,称为关于,的有效(积极)约束,非有效约束:,若对,则,称为,关于,的非有效(无效)约束,有效集:,定义2:,锥:,的子集,,如果它关于正的数乘运算,是封闭的,如果锥也是凸集,则称为凸锥,凸锥关于加法和正的数乘运算是封闭的,一阶必要条件,定理3.5:,(Kuhn-Tucker一阶必要条件)(1951),设,在,(K-T条件),一阶必要条件,定理1:,(Kuhn-Tucker一阶必要条件),(互补松弛条件),例2:,验证 是否满足Kuhn-Tucker条件:,试验证最优点,为KT点,解:,令,所以,即:,所以:,是KT点,Lagrange函数
47、及K-T条件,在一定凸性下的最优性的充分条件,一维最优化方法(线性搜索方法),已知,并且求出了,处的可行下降方向,从,出发,,沿方向,求目标函数的最优解,,或者选取,使得:,问题描述,即,设其最优解为,(叫精确步长因子),,所以线性搜索是求解一元函数,的最优化问,题(也叫一维最优化问题)。,我们来求解:,于是得到一个新点:,一般地,线性搜索算法分成两个阶段:,第一阶段确定包含理想的步长因子,(或问题最优解)的搜索区间;,第二阶段采用某种分割技术或插值方法,缩小这个区间。,搜索区间:,搜索区间求取方法,进退法:一种简单的确定初始搜索区间方法. 基本思想:是从一点出发,按一定步长,试图确定出函数值
48、呈现“高-低-高”的三点,即 这里 。 具体地说,就是给出初始点 ,初始步长 ,若 ,则下一步从新点 出发,加大步长,再向前搜索,直到 目标函数上升为止。,若 ,则下一步仍以 为出发点,沿反方向同样搜索,直到目标函数上升就停止。这样便得到一个搜索区间。这种方法叫进退法。 计算步骤:见P96 计算框图:见P97,黄金分割法(0.618法),基本思想: 它通过对试探点的函数值进行比较,使得包含极小点的区间不断缩短,当区间长度小到精度范围之内时,可以粗略地认为区间上各点的函数值均接近于极小值。,设,在,上为下单峰函数,,即有唯一,的极小点,在,左边,严格下降,,在,右边,严格上升。,在,内任取,若,
49、则,若,则,单峰函数:,黄金分割法,黄金分割法,若第一次选取的试点为,则下一步保留,的区间为,或,两者的机会是均等的,因此我们选取试点时希望,设,则,另外,我们希望如果缩小的区间包含原来的,试点,则该试点在下一步被利用若保留的区,我们希望原来的,间为,前一次的试点,在这个区间内,在缩小的区间内成为,新的,我们根据这条件 来计算,计算,的公式为:,因此我们希望:,即:,化简得:,若保留区间为,我们得到的结果是,一致的,该方法称为黄金分割法,实际计算取:,所以黄金分割法又称为0.618法,黄金分割法每次缩小区间的比例是一致的,,每次将区间长度缩小到原来的0.618倍,黄金分割法的算法步骤,Step
50、1,给定,以及,令,Step2,Step3,转Step.,令,转Step.,若,则,停;,否则,转Step.,Step4,若,则,转Step3.,黄金分割法的算法步骤,Step5,若,则,转Step3.,若,则,转Step3.,例1(黄金分割法),用黄金分割法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的0.08倍,解:,函数,在区间,上为下单峰函数,,第一次迭代:,缩短后区间为,第二次迭代:,缩短后区间为,Fibonacci法,为了尽快得到结果,希望区间缩小的尽量小。,如果在区间只有一个试点,我们无法将区间缩小。,如果知道两个试点,根据,的大,小关系,,可以得到缩小的区
51、间,或者,它与0.618法的主要区别之一在于:搜索区间长 度的缩短率不是采用0.618,而是采用Fibonacci数。,下面我们考虑任给一个,另外一种思维方式为,,的单峰区间,如果给定试点的个数,如何使最后确定,最优值的区间尽量的小。,按什么方式取点,,求,次函数值之后,,可最多将多长的原始区间,长度缩小为,设,为试点个数为,最终区间,长度为,时、,原始区间,的最大可能长度。,的包含,设最初两个试点为,和,若极小点在,内,,至多还有,个试点,,则,若极小点在,内,,包括,在内可以有,个试点,,则,因此,,如果我们采取合适的技巧,可以使得:,另外,,显然,,从而,满足差分方程:,此为Fibona
52、cci数列,一般写为:,若原始区间为,要求最终区间长度,则,由此可确定,区间缩短之后与,之前的比依次为:,确定之后,最初两个试点分别为:,关于,对称,由于,上述过程完成了依次迭代,新区间仍记为,若已经进行了,次迭代,,第,次迭代时,,还有,个试点(包括已经计算过的函数值的一个),注意:,()若在一定的误差范围内,,则认为,在,内。,()最后的两个试点的选取方式:,例3.1(Fibonacci法),用Fibonacci法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的0.08倍,解:,函数,在区间,上为下单峰函数,,由,可知,应取,Fibonacci算法与0.618法几乎完全
53、相同 。,第一次迭代:,缩短后区间为,第二次迭代:,缩短后区间为,第三次迭代:,缩短后区间为,第四次迭代:,缩短后区间为,第五次迭代:,取最优解,Fibonacci方法评价,Fibonacci法的优点,()如果缩小的区间包含原来的试点,则该,试点在下一步被利用;,()效率最高,有限个试点的情况下,可将,最优点所在的区间缩小到最小,Fibonacci法的缺点,()搜索前先要计算搜索的步数;,()每次搜索试点计算的公式不一致,1、黄金分割法(0.618法)与Fibonacci法,的区别与联系是什么?,2、请读者自己写出算法和程序,二分法,若,的导数存在且容易计算,,则线性搜索,的速度可以得到提高,
54、下面的二分法每次将,区间缩小至原来的二分之一,设,为下单峰函数,,若,在,内,具有连续的一阶导数,,且,取,若,则,为极小点;,若,则以,代替,若,则以,代替,二分法每次迭代都将区间缩短一半,故二分法的收敛速度也是线性的,收敛比为1/2。,。,计算步骤:见P105 计算框图:见P106,多维无约束最优化方法,最速下降法 (阻尼)牛顿法 共轭梯度法,问题提出,问题:,在点,处,,沿什么方向,下降最快?,分析:,考查:,显然当,时,,取极小值,因此:,结论:,负梯度方向使,下降最快,,亦即最速,下降方向,最速下降法,最速下降法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,计
55、算下降方向,Step4:,计算步长因子,Step5:,令,转步.,问题:,设,是正定二次函数,由精确的线搜索确定的,特别当:,例1:,用最速下降法求解:,解:,分析:,(1),因此:,最速下降法是整体收敛的,,且是线性收敛的,(2),两个相邻的搜索方向是正交的,收敛性分析,定理1:,设,在,上存在且一致连续,,则最速下降法产生的序列,满足或者对某个,有,或者,证明:,对于最速下降法,,由以上定理立得,收敛性分析,定理2:,设,二次连续可微,,且,其中,是个正常数,,对任何给定的初始点,最速下降算法或有限终止,,或者,或者,证明:,用以上的结论:,最速下降法优点,(1),程序设计简单,计算量小,
56、存储量小,,对初始点没有特别要求,(2),有着很好的整体收敛性,即使对一般的,目标函数,它也整体收敛,最速下降法缺点,最速下降法是线性收敛的,并且有时是,很慢的线性收敛,原因:,仅反映,在,处,的局部性质,相继两次迭代中搜索,方向是正交的,小结,最速下降法是基本算法之一,而非有效,的实用算法,最速下降法的本质是用线性函数来近似,目标函数,,要想得到快速算法,需要考,虑对目标函数的高阶逼近,基本思想,利用目标函数,在点,处的二阶Taylor,展开式去近似目标函数,,用二次函数的极小点,去逼近目标函数的极小点,牛顿法,算法构造,问题:,设,二阶连续可微,,海色阵,正定,如何从,因为,正定,,则,有
57、唯一极小点,,用这个,极小点作为,所以要求:,即:,因此:,这就是牛顿法迭代公式,注:,这里,牛顿法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,否则计算,Step4:,令,转步.,并且求解方程,得出,例1:,用牛顿法求解:,解:,牛顿法收敛定理,定理1:,设,二次连续可微,,是,的局,部极小点,,正定,假定,的海色阵,满足Lipschitz条件,即存在,使得对于所有,有:,其中,是海色阵,的,元素,则当,充分靠近,时,,对于一切,牛顿迭代有意义,,迭代序列,收敛到,并且具有二阶收敛速度,牛顿法优点,(1),(2),对正定二次函数,迭代一次就可以得到,极小点,如果,正定
58、且初始点选取合适,,算法,二阶收敛,牛顿法缺点,(1),(2),对多数问题算法不是整体收敛的,每次都需要计算,计算量大,(3),每次都需要解,方程组有时奇异或病态的,,无法确定,或,不是下降方向,(4),收敛到鞍点或极大点的可能性并不小,阻尼牛顿法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,否则计算,Step4:,沿,并且求解方程,得出,进行线搜索,,得出,Step5:,令,转Step2.,阻尼牛顿法收敛定理,定理2:,设,二阶连续可微,,又设对任意的,存在常数,使得,在,上满足:,则在精确线搜索条件下,,阻尼牛顿法产生的点列,满足:,(1),当,是有限点列时,,其最后一个点为,的唯一极小点,(2),当,是无限点列时,,收敛到,的唯一极小点,阻尼牛顿法收敛定理,定理3:,设,二阶连续可微,,又设对任意的,存在常数,使得,在,上满足:,则在Wolfe不精确线搜索条件下,,阻尼牛顿法,产生的点列,满足:,且,收敛到,的唯一极小点,例2:,用阻尼牛顿法求解:,解:,显然,不是正定的,,但:,于是,,沿方向,进行线搜索,,得其极小点,从而迭代不能继续下去,带保护的牛顿法算法,给出,Step1:,若,为奇异的,转Ste
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学五年级劳动课程“种植金银花”教学设计
- 高中地理选择性必修3第三章第二节污染物的跨境转移教学设计
- 初中七年级美术教案-山水新声创作与鉴赏
- 初中八年级数学《一元二次方程的概念》教学设计(沪教版五四制上册专题21.1)
- 八年级物理教学设计 光的直线传播 核心素养导向下的实验探究与模型构建
- 高中体育与健康一年级一分钟跳绳教学设计
- 九年级物理内能第一课时教案
- 高中二年级物理模块综合检测教学设计
- 高三化学阿伏加德罗常数正误判断教学设计
- 2026年中考语文二轮复习作文专题教学设计:初中九年级普通素材转化高阶立意的三种思维路径
- 2026全球牙科诊疗椅人机工程学创新设计与用户体验提升分析报告
- 2025 重症脓毒症与感染性休克救治指南(中文版)完整原文 + 详细解读
- 2026年重症医学5c考试题库带答案
- 洗衣机装配工岗前工艺控制考核试卷含答案
- 《数字人民币智能合约互联互通建设管理规范》编制说明
- 四川省政府采购评审专家考试真题库及答案(完整版)-四川评标评审专家
- ICU三管感染防控集束化管理
- 2026年湖北省荆州市编制教师招聘考试参考题库及答案解析(综合卷)
- 2026年健康管理师《技能操作》考前冲刺模拟试题及答案
- GB/T 16895.3-2024低压电气装置第5-54部分:电气设备的选择和安装接地配置和保护导体
- TZGCSC 010-2024 数字道路路侧雷视一体机数据接口规范
评论
0/150
提交评论