最优化理论与方法12014简版.doc

《最优化理论与方法》讲义( 上) 第一章绪论 学科简介最优化这一数学分支, 为这些问题的解决提供了理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科。 优化的含义优化是从处理各种事物的一切可能的方案中,寻求最优的方案。( 1) 来源: 优化一语来自英文 Optimization , 其本意是寻优的过程; ( 2 )优化过程: 是寻找约束空间下给定函数取极大值(以 ma x 表示) 或极小(以 min 表示) 的过程。 发展概况第一阶段—人类智能优化第二阶段—数学规划方法优化第三阶段—工程优化第四阶段—现代优化方法 研究意义研究意义: 最优化在本质上是一门交叉学科, 它对许多学科产生了重大影响,并已成为不同领域中很多工作都不可或缺的工具。应用范围: 信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。总之, 它是一门应用性相当广泛的学科, 讨论决策的问题具有最佳选择之特性。它寻找最佳的计算方法, 研究这些计算方法的理论性质及其实际计算表现。 示例例 1 资源分配问题某工厂生产 A和 B 两种产品, A 产品单位价格为 AP 万元, B产品单位价格为 BP 万元。每生产一个单位 A 产品需消耗煤 Ca 吨,电 Ea 度, 人工 La 个人日; 每生产一个单位 B 产品需消耗煤 Cb 吨,电 Eb 度, 人工 Lb 个人日。现有可利用生产资源煤 C吨,电 E度, 劳动力 L个人日, 欲找出其最优分配方案, 使产值最大。分析: (1) 产值的表达式; (2) 优化变量确定: A 产品 Ax , B 产品 Bx ; (3) 优化约束条件: ①生产资源煤约束; ②生产资源电约束; ③生产资源劳动力约束。例 2 指派问题设有四项任务 1B 、 2B 、 3B 、 4B 派四个人 1A 、 2A 、 3A 、 4A 去完成。每个人都可以承担四项任务中的任何一项,但所消耗的资金不同。设 iA 完成 jB 所需资金为 ijc 。如何分配任务,使总支出最少? 分析:设变量??????任务完成不指派, 任务完成指派 j ji ijBA BAx0 ,1 则总支出可表示为: ijij ijxcS????? 41 41 数学模型: ijij ijxcS????? 41 41 min ???? 414,3,2,1,1.. j ijixts???? 414,3,2,1,1 i ijjx?? 4,3,2,1,,1,0??jix ij 最优化的数学模型最优化的数学模型是描述实际优化问题目标函数、变量关系、有关约束条件和意图的数学表达式, 并能反映物理现象各主要因素的内在联系,是进行最优化的基础。 基本概念 1、决策变量(Decision variables) —问题中要确定的未知量,表明规划中的用数量表示的方案、措施, 可由决策者决定和控制, 也称优化变量。决策变量或优化变量的全体实际上是一组变量, 可用一个列向量表示。优化变量的数目称为优化问题的维数,如 n 个优化变量, 则称为 n 维优化问题。?? Tnnxxxx x xX??,, 21 2 1??????????????优化问题的维数表征优化的自由度。优化变量愈多, 则问题的自由度愈大、可供选择的方案愈多,但难度亦愈大、求解亦愈复杂。通常, 小型优化问题:一般含有 2— 10 个优化变量; 中型优化问题: 10— 50 个优化变量; 大型优化问题: 50 个以上的优化变量。如何选定优化变量? 确定优化变量时应注意以下几点: ( 1 )抓主要,舍次要。( 2 )根据要解决问题的特殊性来选择优化变量。 2、约束条件(Constraint conditions) —指决策变量取值时受到的各种资源条件的限制。约束又可按其数学表达形式分成等式约束和不等式约束两种类型: (1) 等式约束: ?? 0?xh (2) 不等式约束: ?? 0?xg 根据约束的性质可以把它们区分成: 性能约束—针对性能要求而提出的限制条件称作性能约束。边界约束—只是对设计变量的取值范围加以限制的约束称作边界约束。图 1-2 优化问题中的约束面(或约束线) (a) 、二变量问题的约束线(b) 三变量问题的约束面可行域:在优化问题中,满足所有约束条件的点所构成的集合。如约束条件?? 016 22 211????xxXg 和?? 02 22???xXg 的二维设计问题的可行域 D。图约束条件规定的可行域 D 一般情况下,可行域可表示为: ????????????mjxh luxgD j u,,2,1,0 ,,2,1,0??→不可行域:D →可行点和不可行点: 约束边界上的可行点为边界点, 其余可行点为内点。→起作用的约束与不