最优化理论与方法

《最优化理论与方法》由会员分享，可在线阅读，更多相关《最优化理论与方法（327页珍藏版）》请在金锄头文库上搜索。

1、最优化理论与方法课件制作：北方民族大学 高岳林 任子晖目 录 第一章 概论 第二章 线性规划 第三章 无约束非线性规划 第四章 约束非线性规划 第五章 多目标规划 第六章 整数规划 第七章 动态规划第一章 概论模型举例最优化问题的模型与分类第二章 线性规划凸集与凸函数线性规划的几何特征线性规划的标准型线性规划的基本定理单纯型法大M法第三章 无约束非线性规划最优性条件一维搜索最速下降法与共轭梯度法牛顿法与拟牛顿法第四章 约束优化方法最优性条件二次规划可行方向法惩罚函数法复型法第五章 多目标规划模型举例向量集的优化问题有效解和弱有效解评价函数法第六章 整数规划整数规划问题的基本概念线性整数规划问题

2、的分枝定界法 01的隐枚举法第七节 动态规划动态规划的基本概念动态规划的最优性与基本方程第一章 概论 随着生产、经济、技术的发展，工程技术、管理人员在实际工作中， 肯定会面临这样的一类问题：工程设计中怎样选择参数，使得设计既 满足要求，又能降低成本；资源分配中，怎样的分配方案既能满足各 方面的基本要求，又能获得好的经济效益；生产计划安排中，选择怎 样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种 成分的比例才能提高质量、降低成本；城建规划中，怎样安排工厂、 机关、学校、商店、医院、住宅和其他单位的合理布局，才能方便群 众，有利于城市各行各业的发展；农田规划中，怎样安排农作物的合 理

3、布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定 最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局 ；在人类活动的各个领域，诸如此类问题，不胜枚举。这一类问题的 共同特点，就是要在所有可能的方案中，选出最合理的，达到事先规 定的最优目标的方案，这个方案可称为最优方案，寻求最优方案的方 法称为最优化方法，它是一门应用广泛、实用性强的学科。定义1：寻找最优方案的方法称为最优化方 法。所谓的最优方案就是要在所有可能的方案中 ，选出最合理的，达到事先规定的最优目标 的方案，最优化结合管理，经济等一些领域 ，而最根本的要以我们的数学知识为基础， 现已被广泛地应用于工程，国防，管理和

4、经 济等许多重要的领域。 1.1 模型举例 当我们要量化一个问题时，首先需要将此问题转化为一个 数学问题，即建立数学模型。抓住其主要因素，理清其相 互的联系，然后综合地运用有关学科的知识和数学知识才 能完成。下面举几个例子。例1：配棉问题所谓的配棉问题就是要根据棉纱的质量指标，采 用各种价格不同的棉花，按一定的比例配制成纱 ，使其即达到质量指标又使总成本最低。棉纱的质量指标一般有棉结和品质指标来决定， 这两项指标都可以用数量形式来表示，一般来说 ，棉结粒越少越好，品质指标越大越好。个年纺能力为15000锭的小厂在采用最优化方法配 棉时，某一产品32D纯棉纱的棉花配比质量指标 及单价如下： 原料

5、品名单价 （元/t）混合比（% ）棉结（粒）品质指标 混棉单价（元/t）国棉131 8400 25 60 3800 2100国棉229 7500 35 65 3500 2625国棉327 6700 40 80 2500 2680平均合计 100 70 3175 7405有关部门对32D纯棉纱规定的质量指标为棉 结不多于70粒，品质指标不小于2900。下面我们建立数学模型：首先：根据问题需要设置变量：设 分 别为国棉131,229,327的棉花配比，然后用 所设置的变量把所追求的目标及所受的约束 ，用数学语言表达出来，即得到该问题的数 学模型。 本例的目标是混棉单价最小，用 即可 表示为： 本例

6、关于32D纯棉纱的质量指标作为约束条 件表出，即有： 又因为 的实际意义，它们应为百分 数且和为100%，故又有： 故32D纯棉纱配棉问题的数学模型为： 例2：资金使用问题 设有400万元资金，要求4年内使用完，若在一年 内使用资金 万元，则可得到效益 万元，（效 率不能再次使用），当年使用的资金可存入银行 ，年利率为10%，试制定出资金的使用计划，以 使4年资金效益之和最大。 很明显，不同的使用方案，所取得的效益之和是 不同的，如第一年就把400万元全部用完，则效益 总和为20万元，若前三年均不使用而存入银行， 则第四年把本息和400=532.4万元全部用完，则效 益总和为 万元，比第一种方

7、案效 益大3万多元 。第一年 第二年 第三年 第四年现有资金 400 345.2 265.1 152.8使用资 金86.2 104.2 126.2 152.8效益总和为 万元，使第一种效益总和的两倍多。注：此例反映出进行定量的优化计算作用，故一 些工业人士称最优化方法是不需要增加投入而增 加产出的手段 。为了将上述的问题转化为最优化问题，先建立数 学模型，设变量 分别表示第 年所使 用的资金数，于是所追求的目标-4年的效益总 和最大，即可表示为： 所受的约束为每年的使用金额既不能为负数 又不能超过当年资金拥有数，即：第一年： 第二年：第三年： 第四年： 故资金使用问题的数学模型为：例3：汽轮机

8、排序问题环形排序问题：由于考虑其共振的因素，一百多 个叶片的质量及几何形状各不相同。转动时产生 的惯性离心力也就存在差异，如何确定它们的安 转位置（排列顺序），使诸离心力的合力最小。设有 个叶片，第 个叶片在转动时产生的惯性离 心的数值（模）为 ，转子的一周被分为 等份，安装位置用辐角 表示，如 将第 个叶片安装在位置 上，它产生的离心力 （向量）可用复数表示：设叶片的排序方案用排列 来表示 ，即叶片 排在第 位，那么合力就是：问题就是求排列 使 为最小。于是，设变量为 ，其意义 为：这样合力可表示为：而 于是问题的目标可以表示为： ，而约 束条件为每片叶子只能安装在一个位置上， 即：而且每个

9、位置上只能安装一片叶子，即：故汽轮机叶片排序问题的数学模型为 ：例4：投资的收益与风险 市场上有 种资产(如股票，债券等) 共投资者选择，某公司有一笔数额为 的 资产作为一个时期的投资，公司财务人员对 几种资产进行了评估，估算出在这一时期内 购买 的平均收益率为 ，并预测购买 的 风险损失率为 ,考虑到投资越分散，总的风 险越小，公司决定，当用这笔资金购买若干 种资产时，总体风险可用所投资的 中最大 的一个风险来度量。 购买 要付交易费，费率为 ，并且当购买 不超过给定值 时，交易费按购买 计算（ 不买无需付费），另外，假定同期存款利率 且既无交易费又无风险。已知 时的相 关数据如下： （%）

10、（ %）（%）( 元)28 2.5 1 10321 1.5 2 19823 5.5 4.5 5225 2.6 6.5 40试给该公司设计一种投资组合方案，即用给 定的资金 ，有选择地购买若干种资产或 银行生息，使净收益尽可能的大，总风险尽 可能的小。 设变量 分别表示存入银行和购买 的金额， 表示 不购买 ， 表 示购买 ，目标有两个：第一个目标：第二个目标：约束是总资金为 ， 以及 之间的关系。故投资的收益和风险的数学模型为：1.2 最优化问题的模型与分类数学规划定义：在一些等式或不等式约束条件下， 求一个目标函数的极大或极小的优化模型称 为数学规划。数学规划分为：约束数学规划和无约束数学

11、规划。约束数学规划一般形式为：(P)其中 称为优化向量或决策变 量； 称为目标函数；约束函数 分别称为不等式约 束和等式约束，等式约束和不等式约束统称为约束条件 。 令： ,我们称D 为（P）的约束集合（约束区域）或可行域 。若 ，则称 为可行点或可行解，设 若对任意的 ，都有 ，则称 为 优化问题（P）的全局最优解（极小点或极 大点）若存在 的一个 的领域： 当 时，有 ，称 为优化 问题（P）的局部最优解，如 时，有 ，称 为优化问题（P）的 严格局部最优解。问题的分类1无约束优化问题当 时，问题(P)称为无约束优化问题， 无约束优化问题是指在空间 上寻求使目标函数 达到极小或最小的点（解

12、）。2约束优化问题若指标集I与E中至少有一个非空，则称(P)为约 束优化问题，约束优化问题是在约束集D上寻求使目标函数达到极小或最小的点（解） 。 若 ，即问题(P)只含有等式约束，此时称问题 (P)为等式约束优化问题； 若 ，即问题(P)只含不等式约束，此时称问题 (P)问不等式约束优化问题； 否则称问题(P)为混合优化问题。如果目标函数目标函数和约束函数都是线性，则称问题为 线性规划，线性规划常记为LP；如果目标函数和约束函数中至少有一个是非线性函数，则 称问题为非线性规划，常记为NP；在非线性规划中，若约束函数均是线性函数，则称问题为 线性约束非线性规划问题，常记为NLP；目标函数为二次

13、函数的线性约束问题称为二 次规划问题，常记为QP。若变量限制取整数，则称为整数规划；若变 量限制取0或1，则称为01规划；若变量 既可取整数，又可取小数，则成为混合整数 规划。若所研究的问题只含一个目标，则称为单目 标规划；若所研究的问题需要同时考虑多个 目标，则成为多目标规划。组合优化组合优化为一个又有有限个元素组成的 集合 和定义在E的某些子集组成 的集合上的实值函数。若E只有有限个元素，E的所有子集也只 有有限个，故组合优化问题的解必然存在， 而且一定可以用原始的方法-逐个列举法 得到。图论，网络流 定义：所谓的图是由一组点和一组点与点之间的 连线（边）组成的总体组成的，图论所研究的问 题主要分为两类： 在给定的图中具有某种性质的点和边是否存在， 若存在，有多少？或至多（少）有多少？ 如何构造具有某些给定性质的图或子图？ 网络：各边赋有权值的图：分为有向网络和无向 网络。 网络流：路，流动态规划定义：动态规划方法将一个最优化问题视为符合最优性原理，无 后效性的多阶段决