目录 第一章概论…… §1-1概述 §1-2最优化问题数学模型的建立 ●围相申导司是唱 4 §1-3最优化问题的分类…………………………………10 §1-4最优控制问题……………………………………18 §1-5最优化问题的求解方法……………………212 第二章经典最优化力法………………………………………25 §2-1无约束极值………………………………………………26 §2-2多变量函数的微分运算…………………………36 §2-3二次型……… 爱中面 §2-4等式约束最优化问题…… 50 §2-5拉格朗日函数的鞍点………… 62 §2-6凸集及凸函数……………………………………64 附录函数凸性条件定理的证明 …8……72 三章线性规划……… §3-1线性规划的数学模型…………………………………176 §3-2线性规划模型的建立………… …78 §3-3线性規划问题的图解法………… 85 s3-4线性规划的几何理论与基本定理……0 §3-5单纯形算法…………………………………93 §3-6线性规划的对偶问题…………………………104 §3-7整教线性规划………………………………110
第四章非线性规划……………………………………122 s4-1非线性规划的数学模型……………………………,…122 §4-2非线性规划应用举例………………………………126 §4-3库恩-图克定理—一有不等式约束的最优化理论…133 §4-4库恩-图克条件的几何解释……………………146 s4-5鞍点条件 150 s4-6非线性规划的对偶问题…… ……157 §4-7二次规划……………………………………162 §4-8一般凸规划的对偶定理……………………172 第五章直接搜索法求解无约束非线性函数极值问题 176 g5-1概述…………………………176 s5-2 Fibonacci法………………130 §5-3黄金分割法(0.618法)……………188 §5-4进退法(成功失败法)………192 §5-5插值法…………… 193 §5-6坐标轮换法…………………206 §5-7步长加速法……………………………m209 §5-8共轭方向法…………………:212 §5.-9单纯形法……24 §5-10随机搜萦法………29 第六章多维无约束最优化问题的数值计算法(以梯度法 为基础的方法)……………………………………236 §6-1最速下降法(最优梯崖法)………………236 §6-2拟牛顿法…………… 4鲁备话帝命导告命命专命 250 §6-3共轭梯度法……………… 罪导命e命咖申 260 §6-4变尺度法…………………………………266 §6-5高斯-牛顿最小二乘法 ,…281 §6-6几种方法的比较… 283 2
泉考核无约束最优化算法的几种试验函数……………297 第七章有约束最优化问题的数值解法 298 §7-1用罚函数法求解等式约束最优化问题…299 §7-2SUMT外点法……… 看香争 303 §7-3SUMT内点法…………………312 §7-4 SWIFT方法……………………………灬…………321 §7-5用梯度法解有约束的最优化问题…………………32 §7-6线性逼近法…34 §7-7可行方向法…………………………………338 第八章网络最优化问题………………………………………348 §8-1概述………… 348 §8-2最短路问题………………………………………………350 88-3网络最大流问题……………38 §8-4最小费用流问题……………………………1381 §8-5网络最优化理论的其它应用… t393 第九章变分法和连续系统的最优控制………………………402 §9-1最优控制问题 402 §9-2泛函与变分的基本概念…………………………412 §9-3泛函极值的必要条件一欧拉方程………………416 §9-4边界条件………………………… 426 §9-5古典变分法求解最优控制问题……………435 §9-6连续控制系统最优化问题的数值计算(直接法)……458 附录关于系统可控性和可观测性问题……………467 第十章极大值原理及其应用………………………………470 §10-1极大值原理 470 §10-2时间最优控制问题……………………478 §10-3最小燃料消耗问题………………………………487 §10-4最小能量控制… 491
秀10-5线性调节器问题…………495 §10-6线性伺服系统 聊唱备看唱命吾非非e中a 514 10-7极大值原理的证明……517 第十一章离散系统的最优控制 526 §11-1概述 …526 11-2差分方程 ………"528 §11-3离散的欧拉方程…… 542 11-4离散极大值原理……………… 546 11-5离散线性调节器问题……… 看看 s11-6离散极大值原理与连续极大值原理的比较…………553 11-7离散系统的最小时间控制 559 §11-8离散系统最优控制问题的数值计算 …564 第十二章动态规划 ……570 812-1概述………………………………………570 §12-2最优化原理 ………“573 §12-3用动志规划方法求解最优分配问题………574 s12-4离散系绕的动态规划方程 581 §12-5用动态规划求解离散系统最优控制问题的数值 计算方法 §12-6动态规划法解离散线性二次型问题 …593 §12-7连续动态规划… d自音 598 §12-8用连续动态规划解线性二次型问题……………606 附录非线性规划的几个计算机程序( FORTRAN 梯度法……………617 I,共轭梯度法… ……………621 夏.变尺度(DFP)法 ………626 Ⅳ.单纯形法……632 V. SWIFT法 “n638
第一章概论 §1-1概述 过去十几年间最优化理论与方法发展十分迅速。最优化方法在 数学上是一种求极值的方法,它是应用数学的一个分支,现在它已 渗透到科学、技术、工程、经济各领域。 实际上人们做任何一件事,不管是分析问题,还是进行综合、 作出决策,都要用一种标准衡量一下是否达到了最优。在科学实 验、生产技术改进、工程设计,和在生产计划管理、社会经济问题 中,人们总希望采取种种措施,以便在有限的资源条件下或规定的 约束条件下得到最满意的效果。 在进行一项工作时(例如产品设计、物资运输或分配等等)应 用最优化技术,可以帮助我们较快地选择出最优方案,或作出最优 决策。因此最优化方法在各种工程技术、自动控制、系统工程、运 筹学以及经济计划、企业管理各方面都被广泛应用。 数学家们研究最优化问题,已有很多年历史。古希腊数学家毕 达哥拉斯早在公元前500年就已发现了所谓黄金长方形,即长方 形的长与宽的最佳比例为1.618,称为黄金分割比。古希腊和欧洲 的建筑师、美术家认为在建筑、人像雕塑和绘画中应用这个比例将 使建筑和艺术最优美、协调。 1.618是一个很有趣的数字,例如下述一组数字间,存在着奇 妙的关系。 a=0.618
b=1 b-a=0.382 c=1.618 b=0.618 d=2.618 C- 4。236 e-d=1.618 b b =1.618 1.618 a+6=c 6+c=d, e十d=e 1618的倒数0618现在还在优选法中广泛应用着,而0618法 是一种有效的一维搜索最优化方法。1.618恰好是x2+x-2=0 的正数解,而0.618则是x2-x-2=0的正数解。 在微积分出现以前,已有许多人开始研究用数学方法解决最优 化问题。例如欧洲古代城堡几乎都是圆形的。因为公元前187年 212年,阿基米德已证明,给定周长,圆所包围的面积最大,数学 上称为等周问题。中国吉代城堡却是方形的,这是因为给定周长 时,正方形是包围面积最大的四边形;反之给定面积时,正方形是 周长最短的四边形,这两个问题是对偶的。 著名的捷线问题,或称最短时间问题是这样提出的:如果有 个质量为m的小球受到重力的作用,在垂直平面内沿金属丝无摩擦 地下滑到某一·点,为了使下滑时间最短,则金属丝应当具有什么形 状?这是一个求泛函极值问题,要用变分法来解算。伽利略曾猜测 金属丝形状是圆弧,但1694年贝努里证明这种金属丝是一条摆 线,与变分法所得结果一致。 科学和工程技术发展史上也有许多最优化问题的重要结论。例 如“自由能量”最小时化学系统达到平衡;光在两点间行进时间为 最小高斯的最小二乘设想是使试验数据和拟合曲线间的误差平方 和为最小;维纳〔 Wiener)对控制系统的设计思想是误差平方的 时间积分为最小;网络图论中极大流-极小割集定理说明信息流(运
少:i 输流)的极大值等于切割网络通道的极小容量,对于解决信息网络 包括计算机网络)或运输网络(包括电力系统输电网络)极大流 问题来说,是很重要的。最短路径问题也很早就用网络拓扑解决 了 在电工技术中最优化方法的应用也是很广泛的。电路理论中的 基本定理之一是最大功率传输定理,用古典最优化方法—求导数 的方法证明共轭匹配是交流网络传输功率最大的条件。在满足性能 指标要求的前提下,如何选择参数及几何尺寸使电机、变压器、大 功率饱和电抗器等电工设备的体积、重量、费用为最小,这对国民 经济的发展很有意义。电网络设计中常要求在满足电路方程的前提 下,选择网络元件参数,使消耗功率为最小,或使网络的实际响应 值与希望值之间的误差为最小。一个电子系统,应如何设计各元部 件的失效率,使茶统全局可靠性达到规定要求,同时为保证可靠性 所需费用为最小,这在航天设施中是十分重要的问题。一个控制系 统在满足系统动态方程的条件下,应选择怎样的控制变量序列(控 制函数),使系统从初始状态能以最短时间转移到规定的终态,这 就是最优时间控制问题。类似的最优控制问题还有:最少燃料消 耗、最优能量控制、随动系统中跟踪误差平方的积分为最小等等。 目前国内外也已将最优化技术应用于电场的计算和电力系统的可靠 性研究,并用网络最优方法研究电力系统经济运行。 在二十世纪五十年代以前,解决最优化问题的数学方法只限于 古典求导方法和变分法(求无约束极值),或是拉格朗日( Lagrange) 乘子法解决等式约束下的条件极值问题。这类求可导函数或泛函数 极值的必要充分条件称为古典最优化问题。 由于科学技术和生产的迅谜发展,实践中许多最优化问题已经 无法用古典方法来解决。又由于大型快速电子计算机的发展,自五 十年代末以来已经有许多计算机算法解决最优化问题。从理论上 说,其中有代表性的是:库恩( H.w.. Kuhn)和图克(A.W.Tuc
ker)两人推导了关于不等式约束条件下的非线性最优必要条件, 称为库恩-图克定理,贝尔曼( Bellman)的最优化原理和动态规划 理论,庞特里亚金( Pontriagin)的极大值原理,以及卡曼(Kal man)的关于随机控制系统最优滤波器,这些构成了现代最优化技 术及最优控制理论的基础。目前“最优化方法”已成为国内外许多 大学规定的大学生、研究生的必修内容,也是在职技术干部、管理 人员继续学习的重要部分。 最优化方法是一种数学方法,而不是工程方法,它与应用数 学、计算机科学以及各专业领域都有密切的关系。用最优化方法解 决实际问题一般分三步进行 1.提出最优化问题,拟述目标是什么?约束条件是什么?求 什么变量?建立最优化问题的数学模型,确定变量,列出目标函数 及约束式(等式或不等式)。 2.分析模型,选择合适的求解方法。 3.编程序,用计算机求最优解,对算法的收敛性(是否最终 能收敛到最优解)、通用性与简便性、效率(计算时间)及误差等 作出评价。 由此可见,最优化方法是用计算机寻优的方法。大型计算机的 发展及应用为求解大规模最优化问题(又称高维的多变量极值问题) 创造了条件。 §1-2最优化问题数学模型的建立 最优化方法的第一步是要叙述问题和建立问题的数学模型,其 中包括目标函数和约束条件(简称约束),用函数、方程式和不等 式来描述说明所求的最优化问题。其中识别目标、确定目标函数的 数学表达形式这一步尤为困难。以下分别说明变量、约束和目标函 数的确定
变量的确定 变量一般指最优化问题或系统中待确定的某些量。例如,电机的 最优设计中,变量可能为电流密度∫、磁通密度B、轴的长度、直径 以及其它几何尺寸等。电路的最优设计中要确定的变量主要是电路 元件(R、L、C)的数值。对产品设计问题来说,一般变量数较少 (例如几个到几十个),变量数的多少以及约束的多少表示一个最 优化问题的规模大小,因此工程上最优设计问题属于中小规模的最 优化问题。而生产计划、调度问题中变量数可达几百个、几千个, 属于大规模最优化问题。变量用X表示,Ⅹ=(x1,x2…,xn)2 二、约束条件 求目标函数极值时的某些限制称为约束,例如:要求变量为非 负或为整数值,这是一种限制;可用的资源常常是有限的(资源泛 指人力、设备、原料、经費、时间等等);问题的求解应满足一定 技术要求,这也是一种限制(如产品设计中规定产品性能必须达到 的某些指标)。此外还应满足物理系统的基本方程和性能方程(如 电路设计必须服从电路基本定律KCL和KVL,控制系统最优设 计则用状态方程或高阶微分、差分方程来描述其物理性质。如果列 写出来的约束式,越接近实际系统,则所求得的最优化问题的解, 也越接近于实际的最优解。 等式约束9;(x)=0,X∈E",i=1,2,…,m,m<n 不等式约束h,(X〕≥0或≤0j=1,2,…,r。 3.目标函数 “最优化”有一定的标准或评价方法。目标函数是这种标准的 数学描述。目标函数f(X)可以是效果函数或费用函数,f(X) xn)。用效果作为目标函数时,最优化问题是要求极 大值,而费用函数不得超过某个上界成为这个最优化问题的约束 5
反之,目标函数是费用函数时,问题变成了求极小值,而效果函数 不得小于某个下界就成为这个求极小值问题的约束了,这是对偶关 系。 上述费用和效果都是广义的,如费用可以是经费,也可以是时 间、人力、功率、能量、燃料、材料、占地面积或其它资源。而效 果可以是性能指标、利润、效益、精确度、灵敏度等等。也可以将 效果与费用函数统一起来,以单位费用的效果函数或单位效果的费 用函数为目标函数,前者是求极大值,后者则是求极小值。 求极大值和求极小值问题实际上没有什么原则的区别。因为求 f(X)的极小值相当于求-f(X)的极大值(见图1-1),即min f(X)=-max[-∫(X)]。两者的最优值均在x=x*时得到。 综上所述,最优化问题的数学模型可以表示成如下形式: min f(X) X∈En (1-1) 约束条件g:(X)≤0注]讠=1,2,…m 例1]多路输出的有源线性网络最大输出功率问题。 设有源线性网络供电给多路负载(图1-2),每一路的输出电 压为U1,U2,…,Un负载电阻为R1,R2,…,Rn,该网络总 的输出功率为: RI R2 R (1-2) R1,R2,…,Rn为待定的电路参数,(1-2)式表示非线性多变 量方程,即功率P是R1,R2,…Rn这n个变量的非线性函数。 这个问题的数学模型应为 maxP=f(R1,R2,…,Rn) 约束R;>0i=1 (1-3) ,“ r 注]约束条件也可以是g;(X)≥0,由问题性质决定
