当前位置：文档之家 › 第三讲--多变量最优化 PPT

第三讲--多变量最优化 PPT

  • 格式：ppt
  • 大小：560.00 KB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

最优化方法课程PPT

最优化方法课程PPT
x
∞
表示
= max { xi }
x 1 = ∑ xi
x 2 = (∑ x
1 2 2 i
)
7
二、数学预备知识
范数的内积 范数不等式
x y = ∑ xi yi
T i =1 n
x+ y ≤ x + y
三角不等式 柯西不等式
x0 = ( x1 ( 0 ) , x2 ( 0 ) ,..., xn ( 0 ) )
() () ()
4
一、最优化方法的基本概念
(2) 非线性规划 非线性规划(Nonlinear Programming, NLP)
f(x)，Ci(x) ( i ∈ E U I )，其中之一均为线性函数 ，
(3) 无约束最优化问题 Unconstraint Optimization Problem) 无约束最优化问题(
λ)x(2)
x(2)
x
17
二、数学预备知识
(3) 凸函数的判定准则 一阶判定条件： 在凸集S上具有一阶连续偏导数 一阶判定条件： f(x)在凸集 上具有一阶连续偏导数，则 在凸集 上具有一阶连续偏导数， f(x)为S上凸函数的充要条件是 为 上凸函数的充要条件是
f x
f(x)
( ) ≥ f ( x ) + ∇f ( x ) ( x ( ) − x ( ) )
x
2 21 1
没有约束条件C 没有约束条件 i(x)
5
一、最优化方法的基本概念
4 数学规划模型的分类 主要是针对决策变量x 来进行分类： 主要是针对决策变量 1, x2,…xn来进行分类：
连续型 离散型
线性规划 LP (有、无约束 有 无约束)
非线性规划NLP 非线性规划 (有、无约束 有 无约束)

最优化理论与算法完整版课件 PPT

最优化理论与算法完整版课件 PPT

Bazaraa, J. J. Jarvis, John Wiley & Sons, Inc.,
1977.
组合最优化算法和复杂性
Combinatorial
Optimization 蔡茂诚、刘振宏
Algorithms and Complexity
清华大学出版社，1988 I运nc筹.,学19基82础/1手99册8
最优化首先是一种理念, 运筹学的“三个代表”
其次才是一种方法.
• 模型
• 理论
2021/4/9
• 算法
5
绪论---运筹学（Operations Research -
运筹学O方R）法
最优化/数学规划方法
连续优化：线性规划、 非线性规划、非光滑优 化、全局优化、变分法、 二次规划、分式规划等
离散优化：组合优化、 网络优化、整数规划等
2021/4/9
11
1. 食谱问题
我每天要求一定量的两种维生素，Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到。
维生素
Vc(mg) Vb(mg) 单价(US$)
奶中含量
2 3 3
蛋中含量
4 2 2.5
每日需求 40 50
需要确定每天喝奶和吃蛋的量， 目标以便以最低可能的花费购买这些食物， 而满足最低限度的维生素需求量。
最优化理论与算法
2021/4/9
1
提纲
使用教材：
最优化理论与算法 陈宝林
参考书 ：
数学规划 黄红选， 韩继业 清华大学出版社
1. 线性规划 对偶定理
2. 非线性规划 K-K-T 定理
3. 组合最优化 算法设计技巧
2021/4/9
2
其他参考书目

最优化方法PPT

最优化方法PPT

共117页第8页
同时太阳系这个"整体"又是它所属的"更大整 体"--银河系的一个组成部分。世界上的具体系统是 纷繁复杂的，必须按照一定的标准，将千差万别的 系统分门别类，以便分析、研究和管理，如：教育 系统、医疗卫生系统、宇航系统、通讯系统等等。 如果系统与外界或它所处的外部环境有物质、能量 和信息的交流，那么这个系统就是一个开放系统， 否则就是一个封闭系统。开放系统具有很强的生命 力，它可能促进经济实力的迅速增长，使落后地区 尽早走上现代化。如改革开放以来已大大增强了我 们的综合国力。而我国的许多边远山区农村，由于 交通不便，相对封闭，还处于比较落后的状态。
会科学和思维科学的相互渗透与交融汇流，产生了 具有高度抽象性和广泛综合性的系统论、控制论和 信息论。
系统论是研究系统的模式、性能、行为和规律 的一门科学。它为人们认识各种系统的组成、结构、 性能、行为和发展规律提供了一般方法论的指导。 系统论的创始人是美籍奥地利理论生物学家和哲学 家路德维格·贝塔朗菲。系统是由若干相互联系的 基本要素构成的，它是具有确定的特性和功能的有 机整体。如太阳系是由太阳及其围绕它运转的行星 （金星、地球、火星、木星等等）和卫星构成的。
从数学上比较一般的观点来看，所谓最优化问题可 以概括为这样一种数学模型：给定一个“函数”，F(X)， 以及“自变量”X应满足的一定条件，求X为怎样的值时， F(X)取得其最大值或最小值。这里在函数和自变量两个 词上之所以打上引号，是想强调它们的含意比中学数学 和大学微积分中函数的定义要广泛得多。通常，称F(X) 为“目标函数”，X应满足的条件为“约束条件”。约 束条件一般用一个集合D表示为：X∈D。求目标函数 F(X)在约束条件X∈D下的最小值或最大值问题，就是一 般最优问题的数学模型，它还可以利用数学符号更简洁 地表示成：Min F(X)或Max F(X)。

《多目标优化方法》PPT课件

《多目标优化方法》PPT课件

cij
b1, b2 , b3, b4
解: 设变量 xij ,i 1,2,3; j 1表,2,3示,4 由 运Ai往
总吨公里数为
,总d运ij xi费j 为
求解
i1 j1
的B j货物数,于是
,问题ci优j xij化为
i1 j1
34
min
dij * xij
i1 j1
34
min
cij * xij
点 B1, B2 , B。3, 其B4 需要量分别为
b1, b2 , b3, b4
且
3
ai
，4 b已j 知
到
i
j
的A距i 离和B单j 位运价分别为
(km)和 (元di)j ,现要决定如ci何j 调运多少,才能使总的
吨,公里数和总运费都尽量少?
解: 设变量 xij , i 1,2,3; 表j 示1由,2,3,4运往 的货物Ai数,于是总
可以看到：
当P=1时,(VP)就是非线性规划, 称为单目标规划。
对于单目标问题Min f (x,) x1, x2 总D可比较
与 f (x2的) 大小.
f (x1)
对于多目标规划(VP),对于 x1, x2 D， f (x1与) f (都x2 ) 是P 维向量,如何比较两个向量的大小?
多目标优化的非劣解集 Noninferior solution for the model
积为
,它x决1 *定x2重量,而梁的强度取决于截面
形
。
1 6
x1
*
x22
因此,容易列出 梁的数学模型:
min
x1 * x2
max
1 6
*
x1
*

最优化课件,超级有用

最优化课件,超级有用

(n )
即不管 Xi 服从什么分布,当 n 相当大时,它们的均值接近于 它们的数学期望
18
结束
2.
X1, X 2 ,L , X n
独立同分布,记
1n X n i1 X i
EX i , DX i 2 则有中心极限定理:
X x
x
R, lim n
P
/
n
x
1
-u2
e 2 du
2
12
结束
4. X ~ U (a,b) EX a b DX 1 (b a)2
2
12
5.
X ~ E() EX 1
DX
1
2
6. X ~ N (a, 2 ) EX a DX 2
13
结束
二.多维随机变量及其分布
• n 维随机变量常记为: X ( X1, X 2 ,L , X n ) 特别地, 2 维随机变量常记为: ( X ,Y )
(5) X ,Y独立，E ( XY) EX EY
10
结束
g( xk ) pk
Eg ( x)
k 1
X 离散型
g(
x)
f
(
x)dx
X 连续型
2.方差:DX=E(X-EX)2
•X是离散型: DX xk EX 2 pk
k 1
•X是连续型,其密度函数是 f(x):
DX x EX 2 f (x)dx
(1) f (x) 0, x (, );(2) f ( x)dx 1
•知道了密度函数f (x),就可以解决任何事件的概率计算: b
P(a X b) f (x)dx
a
•一元随机变量的分布函数F (x)=P(Xx)

第三讲 无约束优化(多维无约束优化方法)

第三讲 无约束优化(多维无约束优化方法)

2019/10/21
5
1. 梯度法（最速下降法 ）
（2）迭代公式 ： X (k 1) X (k) k S (k) X k f X k
或
X (k1) X (k) k
f f
X k X k
f
X k


f ，f x1 x2
X (2) 1
S (1)
S为S（2）的共轭方向。
S即为S(1)的共轭方向。
2019/10/21
18
（2）共轭梯度法的基本原理
2）共轭方向的构造
S k1 f X k1 k S k
上式的意义是以新的负梯度方向 f X k1 ，加上原
负梯度的一部分k S k 来构造 S k1 。
2019/10/21
3
1. 梯度法（最速下降法 ）
数值迭代格式
X (k 1) X (k ) k S (k )
从数值迭代格式可以看出，构造一种算法的关键 是如何确定一个有利的搜索方向。
梯度方向是函数值上升最快的方向，负梯度 方向是函数值下降最快的方向。
2019/10/21
以负梯度方向作为搜索方向
4）牛顿法不能保证函数值稳定下降，严重时还会造 成点列发散导致迭代失败。
2019/10/21
1 27
3. 多维牛顿法（阻尼牛顿法）
问题的提出
因函数不一定是二次函数，基本牛顿法的步长因子 恒为1，有时会导致迭代发散而失效。
改进方法
仍取牛顿方向，但改用最优步长因子：
X (k1) X (k ) k [H ( X (k ) )]1f ( X (k) ) 一维搜索求最优步长
'X 0

多目标优化设计方法PPT39页

目的是将多目标优化问题转化为单目标 优化问题
7.4 功效系数法
一、功效系数 极小值
多目标优化设 计中，各子目 标的要求不同
极大值 一个合适的数值
每个子目标都用一个功效函数di表示 ——其值为功效系数
功效函数的范围[0,1]
fi(X)的值满意时，di=1 fi(X)的值不满意时，di=0
7.4 功效系数法（续）
1、基本思想
这种方法是对各目标函数的最优值放宽要求， 可以对各目标函数的最优值取给定的宽容值，即 ε1>0， ε2>0,…。这样，在求后一个目标函数的 最优值时，对前一目标函数不严格限制在最优解 内，而是在前一目标函数最优值附近的某一范围 内进行优化，因而避免了计算过程的中断。
若干个最优解组成的集合称为绝对最优解集,用 Da*b 表示。
只有当F(X)的各个子目标fi(X)的最优点都存在，并且 全部重叠于同一点时，才存在有绝对最优解。
7.1 概述（续）
2、有效解（非劣解） 设 X* D (D为可行域）， 若不存在 X D ，使
fi ( X ) fi ( X*)(i 1, 2,..., m)
hj ( X ) 0, ( j 1, 2,..., k)
向量形式的目标函数
设计变量应满足的所 有约束条件
7.1 概述（续）
二、几个基本概念
1、最优解 设 X* D (D为可行域）， 若对于任意 X D ，恒使
fi ( X*) fi ( X )(i 1, 2,..., m)
成立，则称X*为多目标优 化问题的绝对最优解，简称最优解。
评价函数：
7.2 统一目标函数法（续）
二、统一目标函数的构造方法（续） 3、平方和加权法 基本思想：在理想点法的基础上引入权数

最优化方法Lecture3_单纯形法1


cB 0 0 4
xB x3 x4 x1 T B1b 7 6 3T , xN x2 x5 T 0
f1 cB B1b 12, w cB B1 0 0 4
z2 c2 wP2 c2 4 z5 c5 wP5 c5 4 最大判别数是z2 c2， x2是进基变量。计算
xk
min
bi yik
|
yik
0
br yrk
0
则得新解 x x1, , xr1, 0, xr1, , xm , 0, , xk , 0, , 0T
且
f x f
x0
zk
ck
br yrk
f
x0
.
旧基为 P1, , Pr , , Pm 新基为 P1, , Pk , , Pm
xr 为离基变量 xk 为进基变量。
2 s.t.
BxB NxN b
xB B1b B1NxN
xB , xN 0
min
3 s.t.
f x cB B1b B1NxN cN xN
xB B1NxN B1b
1 等价于
xB , xN 0
min f x
4
s.t.
0 f x Im xB
B1NxN B1b
f x 0xB cB B1N cN xN cB B1b
y2 B1P2 1 5 1T , 而b B1b 7 6 3T
br yr1
min
b1 y12
,
b2 y22
min
7
1
,
6 5
6 5
b2 y22
x4为离基变量，用P2代替P4得到新基。
1 2 1 0 0
A P1
P2
P3
P4

数学建模案例之多变量最优化

数学建模案例之多变量无约束最优化问题1[1]：某家液晶电视机制造商计划推出两种产品：一种47英寸液晶电视机，制造商建议零售价每台7900元。

另一种42英寸液晶电视机，零售价6500元。

公司付出的成本为47英寸液晶电视机每台4500元，42英寸液晶电视机每台3800元，再加上3200000元的固定成本。

在竞争的销售市场中，每年售出的液晶电视机数量会影响液晶电视机的平均售。

据估计，对每种类型的电视，每多售出一台，平均销售价格会下降0.08元。

而且47英寸液晶电视机的销售量会影响42英寸液晶电视机的销售，反之也是如此。

据估计，每售出一台47英寸液晶电视机，42英寸的液晶电视机平均售价会下降0.024元，而每售出一台42英寸的液晶电视机，47英寸液晶电视机的平均售价会下降0.032元。

问：（1）问每种电视应该各生产多少台，使总利润最大？（2）对你在（1）中求出的结果讨论42英寸液晶电视机的价格弹性系数的灵敏性。

1．问题分析、假设与符号说明这里涉及较多的变量：s：47英寸液晶电视机的售出数量（台）；t：42英寸液晶电视机的售出数量（台）；p：47英寸液晶电视机的售出价格（元/台）；q：42英寸液晶电视机的售出价格（元/台）；C：生产液晶电视机的成本（元）；R：液晶电视机销售的收入（元）；P：液晶电视机销售的利润（元）这里涉及的常量有：两种液晶电视机的初始定价分别为：339元和399元，成本分别为：195元和225元；每种液晶电视机每多销售一台，平均售价下降系数a=0.01元（称为价格弹性系数）；两种液晶电视机之间的销售相互影响系数分别为0.04元和0.03元；固定成本400000元。

变量之间的相互关系确定：假设1：对每种类型的液晶电视机，每多售出一台，平均销售价格会下降1元。

假设2：据估计，每售出一台42英寸液晶电视机，47英寸的液晶电视机平均售价会下降0.3元，而每售出一台47英寸的液晶电视机，42英寸液晶电视机的平均售价会下降0.4元。

多目标优化方法讲义(PPT64张)


决策空间 可行域
目标空间 可行域
示例2
m i n( F X ) f ( Xf ) ,2 ( X ) 1
T
3 6 4 1 1 L 3 f ( X ) x ( ) 2 1 4 4 4 4 4 4 3 E Dx Dx Dx 2 2 61 2 1 2 9.78 10 x1 s.t. g1 ( X ) 180 0 7 4 4.096 10 x2
4
2 1 2
2 2
1
2 1
2 2

3 6 4 1 1 L 3 f ( X ) x (4 4 4 4 ) 4 4 2 1 3 E Dx Dx Dx 2 2 1 2 1 2
9.78 106 x1 s.t. g1 ( X ) 180 0 7 4 4.096 10 x2 g2 ( X ) 75.2 x2 0 g3 ( X ) x2 40 0 g4 ( X ) x1 0
(1) (1) (1)
(1)
( 2)
, fm ( X )
(1) (2)
T
F(X
(2)
) f1 ( X
(2)
), f2 ( X
(2)
),
, fm ( X ) , m) X (2)
T
若对于每一个分量，都有 fl ( X (1) ) fl ( X (1) ) (l 1, 2, 则显然，X (1)优于X (2)，记为X (1)
向量不等式的含义为
p p f ( X ) f ( X ) j 1 , 2 , , m , 但 至 少 有 一 个 f ( X ) f ( X ) j j l l
决策空间 非劣解集
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

考虑y对于a的灵敏性。 计算可得，在a=0.01时，有
dPPdxPdyP da xda yda a
P a
x12
S (y,a ) 5 5 1 4 1 0 7 0 0 2(2 1 5 9 0 2 .0 0 0 1 0/3 9 ) 0 .4 0
因此，19英寸彩电的价格弹性系数提高10%， 会使利润下降4%.
'-7/1000*x - 1/50*y + 174 = 0', 'x', 'y') >> dxda = diff(s.x, a) >> sxa = dxda * a / s.x >> a = 0.01 >> eval(sxa)
Matlab 优化函数
无约束多变量函数极小
fminunc
1） 建立目标函数的m-文件

>> syms a >> z = (339 - a*x - 0.003*y).*x + (399 - 0.004*x - 0.01*y).*y
- (400000 + 195*x + 225*y) >> dzdx = diff(z, x) >> dzdy = diff(z, y) >> s = solve('-2*a*x + 144 - 7/1000*y = 0',
问题是：每种彩电应该各生产多少台？
提出问题：
变量：
x=19英寸彩电的售出数量（每年） y=21英寸彩电的售出数量（每年） p=19英寸彩电的销售价格（美元） q=21英寸彩电的销售价格（美元） R=彩电销售的收入（美元/年） C=生产彩电的成本（美元）
假设：
p 3 3 9 0 .0 1 x 0 .0 0 3 y q 3 9 9 0 .0 0 4 x 0 .0 1 y Rpxqy C 4 0 0 0 0 0 1 9 5 x 2 2 5 y PRC
S ( x ,a ) ( 2 2 1 6 0 0 0 0 0 0 0 ) ( 0 .0 1) 4 0 0 1 .1 4 1 0 6 7 5 5 4 0 0 0 /1 1 73 5 1
S(y,a) 9695 0.27 36153
如果将19英寸彩电的价格弹性系数提高10%，则 我们应将19英寸彩电的生产量缩小11%，21英寸 彩电的生产量扩大2.7%.
计算机代数系统--matlab
>> [x, y] = meshgrid(0:400:10000, 0:400:10000); >> z = (339 - 0.01*x - 0.003*y).*x + (399 - 0.004*x - 0.01*y).*y
- (400000 + 195*x + 225*y); >> mesh(x, y, z)
可画出x和y关于a的曲线图.
19英寸彩电的价格弹性系数a的提高，会导致 19英寸彩电的最优生产量x的下降，及21英寸 彩电的最优生产量y的提高。而且，图中显示 x比y对于a更敏感。
计算可得，在a=0.01时，有
dx 66480000000 22160000000 da(40000a49)2 41067
解得全局极大值点 x4735,y7043.
f 21592000553641. 39
回答问题：
这家公司可以通过生成4735台19英寸彩电和 7043台21英寸彩电来获得最大利润，每年获得 的净利润为553641美元，每台19英寸彩电的平 均售价为270.52美元，每台21英寸彩电的平均 售价为309.63美元。生产的总支出为美元，相 应的利润率为19%。因此建议这家公司应该实 行推出新产品的计划。
x, y 0
P=彩电销售的利润（美元/年）
目标：最大化利润函数P
选择建模方法 无约束多变量最优化问题
建立模型： PRC
(3390.01x0.003y)x(3990.004x0.01y)y (400000195x225y) 144x0.01x2174y0.01y20.007xy400000
求解模型： P 1440.02x 0.007y 0 x P 1740.007x 0.02y 0 y
在竞争的销售市场中，每年售出的彩电数量会影响彩电的平 均售价。据估计，对每种类型的彩电，每多售出一台，平均 销售价格会下降1美分。而且19英寸彩电的销售会影响21英 寸彩电的销售，反之亦然。据估计，每售出一台21英寸彩电， 19英寸彩电的平均售价会下降0.3美分，而每售出一台19英 寸彩电，21英寸彩电的平均售价会下降0.4美分。
'-7/1000*x - 1/50*y + 174 = 0', 'x', 'y') >> subs(z, {x, y}, [s.x, s.y])
大家应该也有点累了，稍作休息
大家有疑问的，可以询问和交流
灵敏性分析 在向公司报告结论之前，应对我们关于彩电市场 和生产过程所做的假设进行灵敏性分析，以保证 结果具有稳健性。 我们主要关心的是决策变量x和y的值，因为公司 要据此来确定生产量。
>> syms x y >> z = (339 - 0.01*x - 0.003*y).*x + (399 - 0.004*x - 0.01*y).*y
- (400000 + 195*x + 225*y); >> dzdx = diff(z, x) >> dzdy = diff(z, y) >> s = solve(‘-1/50*x + 144 - 7/1000*y = 0',
第三讲--多变量最优化
例：竞争性产品生产中的利润最大化
一家彩电制造商计划推出两种新产品：一种19英寸液晶平板 电视机，制造商建议零售价为339美元；另一种21英寸液晶 平板电视机，零售价为399美元。公司付出的成本为19英寸 彩电每台195美元，21英寸彩电每台225美元，还要加上 400000美元的固定成本。
对19英寸彩电的价格弹性系数a的灵敏性进行分析.
P(339ax0.003y)x(3990.004x0.01y)y (400000195x225y)
144x0.01x2174y0.01y20.007xy400000
求偏导数并令其为零，可解得
x 1662000 400000a 49
y 8700 581700 40000a 49