要使其最大, 则 令
得两个驻点： 因此, 每个角剪去边长为 a 的正方形可使所制成的水槽容积最大．
6
10
例:某制药厂生产甲、乙两种药品, 生产这两种药品要消耗 某种维生素. 生产每吨药品所需要的维生素量, 所占用的设 备时间, 以及该厂每周可提供的资源总量如下表所示:
维生素(公斤) 设备(台)
每吨产品的消耗
h(x)=b(x)-a(x)+c 转换成h(x)≥0的不等式约束形式
23
问题(1.1.1)是最优化问题的一般数学表现形式.
只要在问题中存在任何约束条件, 就称为约束最优化 问题. 只有等式约束
min f (x) s.t. ci (x) 0
称为等式约束最优化问题
i 1,, m
24
只有不等式约束
式为
min c1x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1 a21x1 a22 x2 a2n xn b2


s.t.aa
m1 m1
x1 x1

am2 x2 amn xn bm am1,2 x2 am1,n xn
min f (x) s.t. ci (x) 0 i 1,, m
称为不等式约束最优化问题. 如果既有等式约束, 又有不等式约束, 则称为混合 约束问题.
25
如果问题中无任何约束条件, 则称为无约束最优化 问题. 无约束最优化问题的数学模型为
min f(x) , x∈Rn , (1.1.2) 一般简记为
Ⅶ
Ⅶ
2．9
1
201
0
1
0
0
2．1
0
022
1
1
3
0
1．5
3
120
3
1
0
4
余料（米） 0
0.1 0.2 0.3 0.8 0.9 1.１
1.4
设x j 表示用第j 种下料方案下料的原料根数, j=1,2…,8,
目标: 使余料总长度最小化
min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8
19
最优化的数学模型的一般形式:
其中
min s.t.
f (x) ci (x) 0 ci (x) 0
i 1,, m i m 1,, p
x (x1, x2 ,, xn )T R n f : Rn R1
ci : Rn R1
为连续函数, 通常还要求连续可微
2
学习本课程所需的数学知识
向量、向量的模(范数)、向量的运算、 线性相关与无关、基. 矩阵的运算及性质、矩阵的秩、特征值、正定 性. 向量函数、连续性、可微性、梯度、海森矩阵、 向量函数(多元函数)的Taylor定理
3
主要参考书目： 理论方面： (1)袁亚湘、孙文瑜著,《最优化理论与方法》, 科学 出版社, 2005 (2) 何坚勇, 《最优化方法》, 清华大学出版社,
2007 计算方面： (3) 曹卫华, 郭正, 《最优化技术方法及MATLAB的 实现》, 化学工业出版社，2005 (4) 朱德通, 《最优化模型与实验》, 同济大学出版 社, 2003
4
其它参考书： (5)卢名高、刘庆吉编著, 《最优化应用技术》, 石油
工业出版社,2002 (6)唐焕文, 秦学志,《实用最优化方法》, 大连理工大
最优化方法
1
前言
什么是最优化 最优化是一门应用性相当广泛的学科, 它讨论决策问 题的最佳选择之特性, 寻找最佳的计算方法, 研究这 些计算方法的理论性质及其实际计算表现
研究内容: 在有限种或无限种可行方案中挑选最优方 案, 构造寻求最优解的计算方法 研究目的: 主要解决最优计划、最优分配、最优决策、 最佳设计、最佳管理等最优化问题. 应用领域：科学工程、国防、交通、管理、经济、金 融、计算机等
化学成分含量（%） 产品中化学成分的最低含量（%）
甲
乙
12
3
4
2
3
2
3
15
5
３
２
数学模型：
min z 3x1 2 x2
x1 x2 1 s.t.122xx1 133xx2 224
3x1 15x2 0 x1 0, x2 0
这是一个原料配制问题, 是在生产任务确定的条件下, 合理 的组织生产, 使所消耗的资源数最少的数学规划问题.
6
第一章 基本概念
7
§1.1 最优化问题简介
8
第1章 基本概念
1.1 最优化问题简介 1.2 凸集和凸函数 1.3 最优性条件 1.4 最优化方法概述
9
举例
例：对边长为a的正方形铁板, 在四个角处剪去相等的正方形以 制成方形无盖水槽, 问如何剪法使水槽的容积最大？ 解 设剪去的正方形边长为x, 由题意易知, 与此相应的水槽容积为
例如, 对于求目标函数f(x)极大的问题 max f ( x)
可转换成求- f ( x) 极小的问题 min (x)
其中(x) f (x)
22
又如对于形如ci(x)≤0的不等式约束, 可同样转换成 上述形式的不等式约束
hi (x)≥0 , 其中hi(x) =-ci(x) 还有像a(x)≤b(x)+c的不等式约束, 可通过令
(1.1.1)
20
目标函数 f(x) 决策变量 x 约束函数 ci(x) 等式约束 ci(x)=0 (i=1, 2, …..,m) 不等式约束 ci(x)≥0 (i=m+1, m+2, …..,p) min 极小化 s.t. 受约束
21
根据实际问题的不同要求, 最优化模型有不同的形 式, 但经过适当的变换都可以转换成上述一般的形 式
在满足一组约束条件的限制下, 寻求决策变量x1, x2的决策值, 使目 标函数达到最大值.
13
例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混 合配制而成的特种产品. 已知甲、乙两种原料都含有A、B、C三种化 学成分, 两种原料分别所含三种化学成分的百分比含量, 以及按合同规 定的产品中三种化学成分的最低含量如下表所示：
圆钢（米） Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ
Ⅶ
Ⅶ
2．9
1
201
0
1
0
0
2．1
0
022
1
1
3
0
1．5
3
120
3
1
0
4
料头（米） 0
0.1 0.2 0.3 0.8 0.9 1.１
1.4
问题归纳为如何混合使用这8种不同的下料方案, 来制造100 套钢架, 且要使剩余的余料总长为最短.
17
圆钢（米） Ⅰ
ⅡⅢⅣ Ⅴ Ⅵ
约束：三种规格圆钢根数
x1+2x2+ x4+ x6 ≥100
2x3+2x4+x5+ x6+3x7 ≥100
3x1+x2+2x3+3x5+x6+4x8 ≥100
非负取整条件
xj≥0 (j=1,2…8)且取整数 18
圆钢（米） Ⅰ
ⅡⅢⅣ Ⅴ Ⅵ
Ⅶ
Ⅶ
2．9
1
201
0
1
0
0
2．1
0
022
1
1
3
0
1．5
3
120
min f (x)
26
无约束最优化问题是最优化的基础 一则很多实际的最优化问题本身就是无约束最优化
问题 二则许多约束最优化方法都是通过变换把约束最优
化问题转换成无约束最优化问题后, 用适当的无约 束优化方法求解.
27
根据模型(1.1.1)中函数的具体性质和复杂程度, 最优 化问题又有许多不同的类型. 根据决策变量的取值是离散的还是连续的分为离散 最优化和连续最优化 离散最优化通常又称组合最优化, 如整数规划、资源 配置、邮路问题、生产安排等问题都是离散最优化 问题的典型例子 离散最优化问题的求解较之连续最优化问题的求解 难度更大, 本书只介绍连续最优化的理论与方法.
学出版社, 2004 (7)钱颂迪, 《运筹学》, 清华大学出版社, 1990 (8)解可新、韩健, 《最优化方法》, 天津大学出版社,
2004
5
目录
第1章 基本概念 第2章 线性规划 第3章 线性搜索与信赖域方法 第4章 无约束最优化方法 第5章 线性与非线性最小二乘问题 第6章 二次规划 第7章 约束最优化的理论与方法
3x1 x2 2x3
3x5 x6 4x8 100
ቤተ መጻሕፍቲ ባይዱ
x j 0，j 1, 28 , 且为整数
这是一个下料问题, 是在生产任务确定的条件下, 合理的组织生产， 使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时, 寻求变量x1至x8的值,使目标函数取得最 小值.
单位利润(万元)
每吨产品的消耗
甲
乙
30
20
5
1
5
２
每周资源总量
160 15
数学模型为
max z=5x1+2x2
30x1 20x2 160 s.t.5xx1 14x2 15
x1 0, x2 0
这是一个如何合理的使用有限的资源, 使生产经营的效益达到最 大的数学规划问题.
3
1
0
4
料头（米） 0
0.1 0.2 0.3 0.8 0.9