最优化方法PPT完整版.ppt

最优化方法 主讲 主要内容 第一章 最优化问题概述 第二章 线性规划 第三章 无约束最优化方法 第四章 约束最优化方法 第五章 多目标最优化方法 第六章 动态规划 第 一 章 最优化问题 概述 一、什么是最优化方法 二、最优化问题 　　当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。 总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法， 另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同， 学科分支很多，因此这个学科名下到底包含哪些分支，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 　　从数学上比较一般的观点来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。这里在函数和自变量两个词上之所以打上引号，是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得多。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型，它还可以利用数学符号更简洁地表示成：Min F(X)或Max F(X)。 　　解决最优化问题的关键步骤是，如何把实际问题抽象成上述数学模型，也就是构造出目标函数与约束条件。一但这一步完成，对于简单问题，可借图形或微积分来求解。遇到比较复杂的课题，可先搞清它属于运筹学哪一分枝，并在此基础上尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo等，来计算。下面举一个简单例子来具体说明这个关键步骤。 举例：　　设有一条2OO千米长的高速公路，沿途有7个城镇，在每个城镇都有一个汽车维修点，今计划建一座仓库供应这些维修点的另配件。问题是，该仓库应建在何处最好？ 　　首先将问题图示如下：在长L＝2OO的直线上分布7个点，坐标分别是：X0=0，X1=…，X6=200，设仓库建在X处，今问：x=？时这个位置“最好”。什么是“最好”？即目标函数是什么？当我们考虑“最好”的标准不同时，则相应的目标函数就有所区别，从而其解也就不尽一样。对上述问题我们研究三种均有一定实际意义的目标。 　　目标一：让仓库到各维修点距离之和为最小，即目标函数 　　 它是逐段直线函数，约束条件是仓库建在X0与X6之间，即 X0≤x≤X6。通过作目标函数的图形或者分析它的增量的正负，可得到问题的解是：x＝X3。 目标二：让仓库离最远的维修点的距离为最小，即新的目标函数是 目标三：让仓库到各维修点距离平方之和为最小，即第三个目标函数是 三、预备知识 (二)、向量和子空间投影定理 1、 n维欧氏空间：Rn 定义1? 设 性质1 设α、β、γ∈ Rn， k∈ R则 　　（1）(α,β)=(β, α) ； 　　（2） (α+β, γ)=(α, γ)+( β, γ ) ； 　　（3） (kα,β)=k(α, β) ； 　　（4） (α, α)≥0 ，等号成立当且仅当α=0 。 定义2?? 定义了内积运算的 n维实向量空间称为欧氏空间，仍记为 Rn。 定义3??设α∈ Rn ，称非负实数√(α, α) 为向量α的长度，记为|α| 。长度为1的向量称为单位向量。 定理1 （Cauchy-Schwarz不等式）设 α、β∈ Rn， 则|(α,β)|≤|α|| β| ，等号成立当且仅当 α与 β线性相关。？ 证明：（1）若α 与 β线性相关，不妨设β=kα ，则|(α, β)|= |(α, kα)|= |k|(α, α),而 （六）、基本概念和符号 1、向量和子空间投影定理 (1) n维欧氏空间：Rn 点（向量）：x ? Rn, x = (x1 ,x2 ,…,xn)T 分量 xi ? R (实数集) 方向（自由向量）：d ? Rn, d ? 0 d =(d1 ,d2 ,…,dn)T 表示从0指向d 的方向 实用中，常用 x + ?d