最优化理论与方法

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

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

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

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

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

5、下：,有关部门对32D纯棉纱规定的质量指标为棉结不多于70粒，品质指标不小于2900。下面我们建立数学模型：首先：根据问题需要设置变量：设 分别为国棉131,229,327的棉花配比，然后用所设置的变量把所追求的目标及所受的约束，用数学语言表达出来，即得到该问题的数学模型。,本例的目标是混棉单价最小，用 即可表示为： 本例关于32D纯棉纱的质量指标作为约束条件表出，即有：,又因为 的实际意义，它们应为百分数且和为100%，故又有：,故32D纯棉纱配棉问题的数学模型为：,例2：资金使用问题 设有400万元资金，要求4年内使用完，若在一年内使用资金 万元，则可得到效益 万元，（效率不能再次使用），

6、当年使用的资金可存入银行，年利率为10%，试制定出资金的使用计划，以使4年资金效益之和最大。很明显，不同的使用方案，所取得的效益之和是不同的，如第一年就把400万元全部用完，则效益总和为20万元，若前三年均不使用而存入银行，则第四年把本息和400=532.4万元全部用完，则效益总和为 万元，比第一种方案效益大3万多元 。,效益总和为 万元，使第一种效益总和的两倍多。注：此例反映出进行定量的优化计算作用，故一些工业人士称最优化方法是不需要增加投入而增加产出的手段 。为了将上述的问题转化为最优化问题，先建立数学模型，设变量 分别表示第 年所使用的资金数，于是所追求的目标-4年的效益总和最大，即可表

7、示为：,所受的约束为每年的使用金额既不能为负数又不能超过当年资金拥有数，即：第一年： 第二年：第三年： 第四年：,故资金使用问题的数学模型为：,例3：汽轮机排序问题 环形排序问题：由于考虑其共振的因素，一百多个叶片的质量及几何形状各不相同。转动时产生的惯性离心力也就存在差异，如何确定它们的安转位置（排列顺序），使诸离心力的合力最小。 设有 个叶片，第 个叶片在转动时产生的惯性离心的数值（模）为 ，转子的一周被分为 等份，安装位置用辐角 表示，如将第 个叶片安装在位置 上，它产生的离心力（向量）可用复数表示：,设叶片的排序方案用排列 来表示，即叶片 排在第 位，那么合力就是：问题就是求排列 使

8、为最小。于是，设变量为 ，其意义为：,这样合力可表示为：而 于是问题的目标可以表示为： ，而约束条件为每片叶子只能安装在一个位置上，即：,而且每个位置上只能安装一片叶子，即：故汽轮机叶片排序问题的数学模型为 ：,例4：投资的收益与风险 市场上有 种资产(如股票，债券等) 共投资者选择，某公司有一笔数额为 的资产作为一个时期的投资，公司财务人员对几种资产进行了评估，估算出在这一时期内购买 的平均收益率为 ，并预测购买 的风险损失率为 ,考虑到投资越分散，总的风险越小，公司决定，当用这笔资金购买若干种资产时，总体风险可用所投资的 中最大的一个风险来度量。,购买 要付交易费，费率为 ，并且当购买不超

9、过给定值 时，交易费按购买 计算（不买无需付费），另外，假定同期存款利率 且既无交易费又无风险。已知 时的相关数据如下：,试给该公司设计一种投资组合方案，即用给定的资金 ，有选择地购买若干种资产或银行生息，使净收益尽可能的大，总风险尽可能的小。,设变量 分别表示存入银行和购买 的金额， 表示 不购买 ， 表示购买 ，目标有两个：第一个目标：第二个目标：约束是总资金为 ， 以及 之间的关系。,故投资的收益和风险的数学模型为：,1.2 最优化问题的模型与分类,数学规划定义：在一些等式或不等式约束条件下， 求一个目标函数的极大或极小的优化模型称为数学规划。数学规划分为：约束数学规划和无约束数学规划。

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

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

12、题称为二次规划问题，常记为QP。若变量限制取整数，则称为整数规划；若变量限制取0或1，则称为01规划；若变量既可取整数，又可取小数，则成为混合整数规划。若所研究的问题只含一个目标，则称为单目标规划；若所研究的问题需要同时考虑多个目标，则成为多目标规划。,组合优化 组合优化为一个又有有限个元素组成的集合 和定义在E的某些子集组成的集合上的实值函数。 若E只有有限个元素，E的所有子集也只有有限个，故组合优化问题的解必然存在，而且一定可以用原始的方法-逐个列举法得到。,图论，网络流定义：所谓的图是由一组点和一组点与点之间的连线（边）组成的总体组成的，图论所研究的问题主要分为两类：在给定的图中具有某种性质的点和边是否存在，若存在，有多少？或至多（少）有多少？如何构造具有某些给定性质的图或子图？网络：各边赋有权值的图：分为有向网络和无向 网络。网络流：路，流,动态规划定义：动态规划方法将一个最优化问题视为符合最优性原理，无后效性的多阶段决策过程，并进行求解的方法。注：最优决策的任何截断仍是最优的。特点：将一个复杂的问题转化为若干个较为简单的问题。,第二章 线性规划 2.1 凸集与凸函数 1.凸集及基本性质 Def：设集合 ,若 , 有 ，则称集合为凸集。 由定义可直接验证：设 为凸集， ，则 是凸集。 是凸集。 是凸集。 是凸集。,