《最优化理论与方法》讲义

(上) 第一章 绪论

1.1 学科简介

最优化这一数学分支，为这些问题的解决提供了理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科。 1.1.1 优化的含义

优化是从处理各种事物的一切可能的方案中，寻求最优的方案。 （1）来源：优化一语来自英文Optimization，其本意是寻优的过程；

（2）优化过程：是寻找约束空间下给定函数取极大值（以max表示)或极小(以min表示)的过程。 1.2 发展概况

第一阶段—人类智能优化 第二阶段—数学规划方法优化 第三阶段—工程优化 第四阶段—现代优化方法 1.3研究意义

研究意义：最优化在本质上是一门交叉学科，它对许多学科产生了重大影响，并已成为不同领域中很多工作都不可或缺的工具。

应用范围：信息工程及设计、经济规划、生产管理、交通运输、

国防工业以及科学研究等诸多领域。

总之，它是一门应用性相当广泛的学科，讨论决策的问题具有最佳选择之特性。它寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。 1.4 示例

例1 资源分配问题

某工厂生产A和B两种产品，A产品单位价格为PA万元，B产品单位价格为PB万元。每生产一个单位A 产品需消耗煤aC吨，电aE度，人工aL个人日；每生产一个单位B 产品需消耗煤bC吨，电bE度，人工bL个人日。现有可利用生产资源煤C 吨，电E 度，劳动力L个人日，欲找出其最优分配方案，使产值最大。分析：(1)产值的表达式；(2)优化变量确定：A 产品xA，B 产品xB；(3)优化约束条件： ①生产资源煤约束； ②生产资源电约束； ③生产资源劳动力约束。

例2 指派问题

设有四项任务B1、B2、B3、B4派四个人A1、A2、A3、A4去完成。每个人都可以承担四项任务中的任何一项，但所消耗的资金不同。设

Ai完成Bj所需资金为cij。如何分配任务，使总支出最少?

??1,指派Ai完成Bj任务分析：设变量xij??

不指派A完成Bj任务??0，则总支出可表示为：S???cijxij

i?1j?144数学模型：minS???cijxij

i?1j?144s.t.?xj?144ij?1,i?1,2,3,4

?xi?1ij?1,j?1,2,3,4

xij??0,1?,i,j?1,2,3,4

1.5 最优化的数学模型

最优化的数学模型是描述实际优化问题目标函数、变量关系、有关约束条件和意图的数学表达式，并能反映物理现象各主要因素的内在联系，是进行最优化的基础。 1.5.1 基本概念

1、决策变量(Decision variables)—问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制，也称优化变量。

决策变量或优化变量的全体实际上是一组变量，可用一个列向量表示。优化变量的数目称为优化问题的维数，如n个优化变量，则称为n维优化问题。

?x1??x?TX??2???x1,x2,?xn?

??????xn?优化问题的维数表征优化的自由度。优化变量愈多，则问题的自由度愈大、可供选择的方案愈多，但难度亦愈大、求解亦愈复杂。

通常，小型优化问题：一般含有2—10个优化变量； 中型优化问题：10—50个优化变量； 大型优化问题：50个以上的优化变量。 如何选定优化变量？确定优化变量时应注意以下几点： （1）抓主要，舍次要。

（2）根据要解决问题的特殊性来选择优化变量。

2、约束条件(Constraint conditions)—指决策变量取值时受到的各种资源条件的限制。约束又可按其数学表达形式分成等式约束和不等式约束两种类型：

(1)等式约束：h?x??0 (2)不等式约束：g?x??0

根据约束的性质可以把它们区分成：

性能约束—针对性能要求而提出的限制条件称作性能约束。 边界约束—只是对设计变量的取值范围加以限制的约束称作边界约束。

图1-2 优化问题中的约束面(或约束线)

(a)、二变量问题的约束线 (b)三变量问题的约束面

可行域：在优化问题中，满足所有约束条件的点所构成的集合。