- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
最优化问题的分类
对向量x=(1,–2,3)T,有 || x ||1= 6 || x ||2 = 14 ≈ 3.74166 || x ||3 = 3 36 ≈ 3.30193 || x ||∞= 3.
其中||x||p是p的单调递减函数.
根据数学模型中有无约束函数分为：无约束的最优 化问题和有约束的最优化问题.
m
n
∑ ∑ Q =
( yi −
a
ϕ
j
j
(
xi
))2
i =1
j =0
因此,由数据拟合问题得数学模型为
m
n
∑ ∑ min
( yi −
a
ϕ
j
j
(
xi
))2
i =1
j =0
其中xi,yi (i=1,2,…,m) 及 ϕ j (x), j = 1, 2,L, n 已知.
最优化问题的一般形式为:
P: min f ( x) s.t. hi (x) = 0, i = 1, 2,L, m g j (x) ≥ 0, j = 1, 2,L, p
26
可行点列的产生 在xk处求得一个方向pk(下降方向),在射线 xk+αpk (α >0) 上求一点：xk+1=xk+αk pk , 使得 f (xk+1)≤f (xk), 其中αk 称为步长.
定义1.2.1(下降方向) 在点xk处,对于方向pk≠0, 若存在实数b>0,使得任意的α∈(0,b),都有 f (xk+αpk)<f (xk), 则称pk为函数f (x)在点xk处的一个下降方向.
44
则总支出可表示为: S = ∑ ∑ cij xij i=1 j=1
= ∑ ∑ 数学模型: min S
41
1.ijsx=∑.t1j 12i=,3,4
4
s.t.
∑1.ijsx=∑.t1j 12i=,3,4
x1ij=∑j ij
j =1
=1
i = 1, 2,3, 4
4
∑ xij = 1, j = 1, 2,3, 4
31
32
-8-
19
20
-5-
相关定义
定义1.1.4 (局部最优解) 若x*∈D,存在x*的某邻域 Nδ(x*),使得对于一切x∈D∩Nδ (x*),恒有f (x*)≤f (x), 则称为最优化问题(P)的局部最优解, 其中Nδ (x*)={x| ||x–x*||<δ,δ>0}. 当x≠x*时,若上面的不等式为严格不等式则称x*为问 题(P)的严格局部最优解. 显然,整体最优解一定是局部最优解,而局部最优解不 一定是整体最优解. x*对应的目标函数值f (x*)称为最优值,记为f *.
设Ai→Bj的水泥量为xij,已知Ai→Bj单价为cij,单位为元,
则总运费为:
s = ∑ ∑ m k
cij xij
i=1 j =1
7
8
-2-
数学模型:
mk
min ∑ ∑ cij xij i=1 j =1
k
s.t. ∑ xij = ai (i = 1, 2,L, m) j =1
m
∑ xij = bj , ( j = 1, 2,L, k)
3
4
-1-
四、主要参考书 教材:解可新 、韩健、林友联:最优化方法(修订版),天津 大学出版社,2004年8月. 其它参考书: 1.蒋金山,何春雄,潘少华:最优化计算方法,广州:华南理工 大学出版社,2007年10月. 2.谢政,李建平,汤泽滢:非线性最优化.长沙:国防科技大学 出版社,2003年9月. 3.李董辉等 :数值最优化.北京:科学出版社,2005年. 4.谢政,李建平,陈挚:非线性最优化理论与方法.北京:高等 教育出版社,2010年1月.
目录
第一章 最优化问题概述p.7 第二章 线性规划 第三章 无约束最优化方法 第四章 约束最优化方法
5
第一章 最优化问题概述
§1.1 最优化问题的数学模型与基本概念
例 1.1.1 运输问题
设有m个水泥厂A1,A2, …, Am,年产量各为a1, a2, …,am
吨.有k个城市B1,B2…, Bk用这些水泥厂生产的水泥,年
相关定义
求解最优化问题(P),就是求目标函数f (x)在约束条件 (1.2),(1.3)下的极小点,实际上是求可行域D上的整体 最优解.但是,在一般情况下,整体最优解是很难求出 的,往往只能求出局部最优解. 在求解时需要范数的概念,以下给出定义.
22
常用的向量范数
1–范数 2–范数(欧氏范数) ∞–范数 p–范数
bm Bm
An ≥ dn
图1-2
11
12
-3-
例 1.1.3 指派问题
设有四项任务B1,B2,B3,B4派四个人A1,A2, A3,A4去完成. 每个人都可以承担四项任务中的任何一项,但所消耗 的资金不同.设Ai完成Bj所需资金为cij. 如何分配任务,使总支出最少?
设变量
xij
=
1 0
指派Ai完成Bj 不指派Ai完成Bj
否则令k:=k+1, 转(1)
可行方向
定义1.2.2(可行方向) 已知区域 D ⊂ Rn , xk∈D,对于向 量pk≠0,若存在实数b>0, 使得对任意的α∈(0,b), 有:xk+αpk∈D,则称pk为点xk处关于区域D的可行方向.
对于D的内点(存在邻域包含于D),任意方向可行,对于 边界点(任意邻域既有D的点也有不在D中的点),则有 些方向可行,有些方向不可行. 若下降方向关于域D可行,则称为可行下降方向.
i =1
xij ≥ 0, (i = 1, 2,L, m, j = 1, 2,L, k )
注:平衡条件
m
∑
a i
=
k
∑bj
作为已知条件并不出现在约
i =1
j =1
束条件中.
例1.1.2 生产计划问题
设某工厂有m种资源B1,B2, …,Bm,数量分别为: b1,b2, …, bm,用这些资源生产n种产品A1, A2, …, An.每 生产一个单位的Aj产品需要消耗资源Bi的量为aij,根 据合同规定,产品Aj的量不少于dj.再设Aj的单价为cj. 问如何安排生产计划,才能既完成合同,又使该厂总收 入最多?
通常称满足gkTpk<0的方向pk是f (x)在xk处的一个下降
方向. 其中 ∇f (x) = ( ∂f , ∂f L, ∂f )T , 称为f (x)在x处的梯度.
∂x1 ∂x2 ∂xn
29
最优化问题的算法的一般迭代格式
给定初始点x0,令k=0. (1) 确定xk处的可行下降方向pk; (2) 确定步长αk,使得f (xk+αkpk)<f (xk), (3) 令xk+1=xk+αkpk; (4) 若xk+1满足某种终止准则,则停止迭代, 以xk+1为近似最优解;或者已经达到最大迭代步数,也 可终止迭代.
需求量b1,b2, …,bk吨.再设由Ai到Bj每吨水泥的运价为
cij元.假设产销是平衡的,即:
m
k
∑ ai = ∑ bj
i =1
j =1
试设计一个调运方案,在满足需要的同时使总运费最省.
6
由题意可画出如下的运输费用图:
a1 A1
B1 b1
a2 A2 产量
B2 b2
需求量
am Am
Bk bk
图1-1
最优化方法
合肥工大数学学院
前言
一、什么是最优化 最优化是一门应用性相当广泛的学科,它讨论决策
问题的最佳选择之特性,寻找最佳的计算方法,研究这些 计算方法的理论性质及其实际计算表现.
应用范围:信息工程及设计、经济规划、生产管 理、交通运输、国防工业以及科学研究等诸多领域.
1
2
二、包含的内容 按照优化思想分为经典方法与现代方法.
根据目标函数和约束函数的函数类型分类：线性最 优化问题,非线性最优化问题,二次规划,多目标规划, 动态规划,整数规划,0–1规划.
25
§1.2 最优化问题的一般算法
迭代算法 迭代算法：选取一个初始可行点x0∈D,由这个初始 可行点出发,依次产生一个可行点列: x1 , x2 ,···, xk ,···, 记为{xk}, 使得某个xk恰好是问题的一个最优解,或者该点列收 敛到问题的一个最优解x*. 下降算法：在迭代算法中一般要求 f (xk+1)≤f (xk).
14
最小二乘法
解这种问题常用的方法是最小二乘法,以一个简单的
函数序列
ϕ1(x),ϕ2 (x),L,ϕn (x)
为基本函数.
一般选取1, x, x2,···, xn为基本函数,即以
n
f (x) = ∑ ajx j j=0
作为近似表达式.
15
16
-4-
最小二乘法
最优化问题
系数的选取要使得下面的平方和最小:
9
10
假设产品Aj的计划产量为xj. 由题意可画出如下的生产与消耗的关系图:
b1 B1 b2 B2
消耗 aij
A1 ≥ d1 A2 ≥ d2
n
数学模型 max ∑ c j x j j =1
n
s.t. ∑ aij x j ≤ bi (i = 1, 2,L, m) j =1
x j ≥ d j ( j = 1, 2,L, n)
i =1
xij ∈{0,1}, i, j = 1, 2,3, 4
13
例 1.1.4 数据拟合问题
在实验数据处理或统计资料分析中常遇到如下问 题.设两个变量x和y,已知存在函数关系,但其解析表达 式未知或者虽然为已知,但过于复杂. 设已取得一组数据:
