优化方法讲稿____11.ppt

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