下载文档原格式
最优化理论与算法第二版教学设计一、课程背景随着社会的发展，各行各业对效率的要求越来越高。
优化理论与算法作为一门重要的数学工具，已经成为计算机科学、工业工程、运筹学、统计学等诸多领域必不可少的一部分。
本课程主要介绍常见的最优化算法、模型与理论，旨在让学生在课程学习中掌握优化问题的建模与求解方法，了解常见的优化算法及其应用，并培养学生解决实际问题的能力。
二、课程目标本课程旨在培养学生以下能力：•掌握最优化问题的概念与一般形式；•熟悉线性规划、整数规划、动态规划、贪心算法、分治算法、模拟退火等常见的最优化算法及其应用；•熟练运用MATLAB等工具对优化问题进行数值求解；•能够分析、解决实际问题中的优化问题。
三、教学大纲第一章最优化理论基础•最优化问题与应用•最优化问题的概率与形式化描述•不等式约束条件的最优化问题•拉格朗日乘数法第二章线性规划•线性规划的基本概念•线性规划模型的构建•单纯形法与其扩展算法•求解线性规划的MATLAB工具箱lpSolve第三章整数规划•整数规划的基本概念•分支限界法、割平面法等求解整数规划的方法•求解整数规划的MATLAB工具箱IntLinProg 第四章动态规划•动态规划的基本思想与模型•背包问题的动态规划算法•求解非线性规划的MATLAB工具箱fmincon 第五章贪心算法与分治算法•贪心算法的基本思想与模型•贪心算法求解集合覆盖、活动选择等问题•分治算法的基本思想与模型•分治算法求解归并排序、快速排序等算法第六章模拟退火与遗传算法•模拟退火算法的基本思想及其应用•遗传算法的基本思想及其应用•求解非线性规划的MATLAB工具箱fminsearch四、课程教学教学方式本课程为理论与实践相结合的课程，采用教师讲解、案例分析、课堂练习和课程论文等多种教学方式。
课程中将提供足够的例子和案例分析，以丰富课程内容。
教材主教材为《最优化理论与算法第二版》（作者：D.M.库珀等，译者：范玉平、钱启祥）。
第一章 进化优化算法概述1．1 进化算法的一般框架自1960年以来，进化算法已经发展出相当多的种类，但一般认为进化算法有5个基本组成部分[3]：1．问题解的遗传表示。
2．种群的初始化方法。
3．根据个体适应度对其进行优劣判定的评价函数。
4．产生新的种群的进化算子5．算法的参数取值1.1.1进化优化算法解决对象的描述进化算法主要是求解优化问题，其数学模型如下：Maximizey =f (x )(1.1)Subject to g(x )=()(1x g ,)(2x g ，…，)(x g m )≤0 （1.2）其中 x =（1x ，2x ，…，n x ）∈X ，x 是决策向量，X 是决策向量形成的决策空间；y 是决策目标。
这是个最大化问题，对于最小化问题可以令y '=C -f (x )转化为最大化问题，因此，它们在本质上是一致的。
根据优化函数f (x )是否连续可以将最优化问题分为二大类：连续函数的最优化与离散函数的最优化。
后者也可以称为组合优化问题。
根据是否包含约束条件（1.2）可分为约束优化问题和无约束优化问题。
此外，若y 是一个决策向量，则是一个多目标的优化问题，我们将在第二章进一步讨论。
1.1.2进化优化算法结构进化算法的一般结构如图 1.1所示，进化算法维持由一群个体组成的种群P (t )(t 为进化代数)。
每个个体代表问题的一个潜在解。
每个个体通过目标函数评价得到适应度并根据优胜劣汰的原则进行选择。
被选择的个体经历遗传操作产生新的个体,主要有两种遗传操作：杂交是将多个个体的有关部分组合起来形成新的个体，变异是将一个个体改变而获得新的个体。
新产生的个体（子代）继续被评价优劣。
从父代种群和子代种群中选择比较优秀的个体形成新的种群。
在若干代后，算法收敛到一个最优个体，该个体很有可能代表问题的最优或次优解。
图1.1 进化算法流程图1.1.3进化算法几个环节的解释遗传编码：如何将问题的解编码成染色体是进化算法使用中的关键问题，目前的编码方式主要有二进制编码[4]、Gray编码、实数编码、字符编码等，对于更复杂的问题，用合适自然的数据结构来表示染色体的等位基因，可以有效抓住问题的本质，但总的来说，完整的遗传编码理论尚未建立，部分文献[5~7]的讨论都有都有一定的局限性。
第一章最优化理论方法优化理论是一门实践性很强的学科。
所谓最优化问题，一般是指按照给定的标准在某些约束条件下选取最优的解集。
他被广泛地应用于生产管理、军事指挥和科学试验等领域，如工程设计中的最优设计、军事指挥中的最优火力配置问题等。
优化理论和方法于20世纪50年代形成基础理论。
在第二次世界大战期间，出于军事上的需要，提出并解决了大量的优化问题。
但作为一门新兴学科，则是在G.B.Dantzig提出求解线性规划问题的单纯形法，H.W.Kuhnh和A.W.Tucker 提出非线性规划基本定理，以及R.Bellman提出动态规划的最优化原理以后。
之后，由于计算机的发展，使优化理论得到了飞速的发展，至今已形成具有多分支的综合学科。
其主要分支有：线性规划、非线性规划、动态规划、图论与网络、对策论、决策论等。
1.极小值优化1.1标量最小值优化求解单变量最优化问题的方法有多种，根据目标函数是否需要求导，可以分为两类，即直接法和间接法。
直接法不需要对目标函数进行求导，而间接法则需要用到目标函数的导数。
常用的一维直接法主要有消去法和近似法两种。
消去法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含极小点的区间，缩小搜索区间，直到搜索区间缩小到给定的允许精度为止。
该法的优点是算法简单，效率较高，稳定性好。
多项式近似法用于目标函数比较复杂的情况。
此时搜索一个与它近似的函数代替目标函数，并用近似函数的极小点作为原函数极小点的近似。
常用的近似函数为二次和三次多项式、间接法需要计算目标函数的导数，优点是计算速度很快。
常见的间接法包括牛顿切线法、对分法、割线法和三次差值多项式近似法等。
如果函数的导数容易求得，一般来说应首先考虑使用三次插值法，因为它具有较高的效率。
在只需要计算函数值得方法中，二次差值是一个很好的方法，它的收敛速度快，特别是在极小点所在区间较小时尤为如此。
1.2无约束最小值优化无约束最优化问题在实际应用中也比较常见，如工程中常见的参数反演问题。
最优化理论与算法（数学专业研究生）第一章 引论§1.1 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。
其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。
近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。
现在已形成一个相当庞大的研究领域。
关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。
本课程所涉及的内容属于前者。
二、最优化问题的一般形式 1、无约束最优化问题min ()nx Rf x ∈ （1.1） 2、约束最优化问题min ()()0, ..()0, i i f x c x i E s t c x i I=∈⎧⎨≥∈⎩ （1.2）这里E 和I 均为指标集。
§1.2数学基础一、 范数 1. 向量范数max i x x ∞= （l ∞范数） （1.3）11ni i x x ==∑ （1l 范数） （1.4）12221()ni i x x ==∑ （2l 范数） （1.5）11()np pi pi xx ==∑ （p l 范数） （1.6）12()TAxx Ax = （A 正定） （椭球范数） （1.7）事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。
2．矩阵范数定义1.1 方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤； 若还进一步满足： ⑤ pp AxA x ≤则称之为与向量范数p相协调（相容）的方阵范数。
第一章绪论§1.1引言最优化：就是从所有可能的方案中，选出最合理的，达到事先规定的最优目标的学科。
这样的问题称为最优化问题，达到最优目标的方案称为最优方案，寻找最优方案的方法称为最优化方法。
广义上：运筹学(Operation Research)狭义上：数学规划（programming)发展:(1)最优化问题是一个古老的问题。
早在17世纪，Newton和Leibniz已经提出了函数的极值问题，但没有系统的理论.因为算法不完善及计算工具不先进，以后二、三百年发展缓慢。
（2）第二次世界大战中由于军事上(战略、战术）的需要，如资源调配问题运输问题提出了许多不能用古典方法解决的问题，从而产生了线性规划，非线性规划、动态规划、组合优化等新方法，产生运筹学，（3）但直到20世纪40年代，最优化的理论和算法才得以迅速发展，并不断完善，逐步成为一门系统的学科。
在实际中最优化方法发挥的作用越来越大，其应用越来越广泛，尤其是在工程设计中的应用。
重要性：因为应用广泛所需数学知识：高等数学、线性代数§1.2 优化问题的模型举例例1 产品调运问题设某产品有个产地，各产地产品的产量分别为m 12,,,m a a a 有n 个销售地，每个销地的销量分别为12,,,n b b b 设由第i 个产地到第j 个销地的运费单价为ijc 问如何安排运输计划，使总运费最小（假设产销平衡）。
ij x 解设由第i 个产地到第j 个销地的运输量为1n j =∑1m i =∑min1(1,2,,)n ij i j x a i m ===∑ 1(1,2,,)m ij j i x b j n ===∑ ..s t ij ij c x 1a i a m a 1b j b n b ij c ij x例2将非线性方程组的求解转化为一优化问题。
11221212(,,,)0(,,,)0(,,,)0n n n n f x x x f x x x f x x x =⎧⎪=⎪⎨⎪⎪=⎩212121min (,,,)(,,,)nn i n i x x x f x x x ϕ==∑ 解非线性方程组在有解的情况下，等价于§1.3 优化问题的模型与分类1 根据问题不同特点的分类（1）无约束优化问题（unconstraint optimizationproblem ）12min (,,,)n f x x x 12(,,,)Tn x x x = x min ()n x R f ∈x min (),nf R ∈x x (P)(P)min ()..()0,1,2,,j f s t h j l ⎧⎨==⎩ x x min ()..()0,1,2,,i f s t g i m ⎧⎨≥=⎩ x x min ()..()0,1,2,,,()0,1,2,,i j f s t g i m h j l⎧⎪≥=⎨⎪==⎩ x x x （2）约束优化问题（constraint optimization problem ）(P 1)(P 2)(P 3)12(,,,)T n x x x = x 称为决策变量()f x 称为目标函数()j h x 称为约束函数()0(1,2,,),()0(1,2,,)i j g i m h j l ≥=== x x 称为约束条件()i g x 满足约束条件的点称为可行解（feasible solution ）{}|()0,1,2,,;()0,1,2,,i j R g i m h j l =≥=== x x x (P3)的可行域（feasible region ）2 根据函数类型分类1)线性规划（linear programming）.2)二次规划。
