第4章非线性规划.ppt

使用符号求解的程序如下 syms x x0=solve(x^3-x^2+2*x-3) %求函数零点的符号解 x0=vpa(x0,6) %化成小数格式的数据 也求得全部的零点 0.1378 1.5273i，1.2757。
求数值解的 Matlab 程序如下 y=@(x) x^3-x^2+2*x-3; x=fsolve(y,rand) %只能求给定初始值附近的一个零点
[x,fval]＝fminsearch(fun,x0,options)
例 3.4 求多元函数 f (x, y) x3 y3 3x2 3y2 9x
的极值。
解 编写 Matlab 程序如下 clc, clear f=@(x) x(1)^3-x(2)^3+3*x(1)^2+3*x(2)^2-9*x(1); % 定义匿名函数 g=@(x) -f(x); [xy1,z1]=fminunc(f, rand(2,1)) %求极小值点 [xy2,z2]=fminsearch(g,rand(2,1)); %求极大值点 xy2, z2=-z2
求得当 x1 0.5522, x2 1.2033, x3 0.9478时，最小 值 y 10.6511。
3.2 无约束问题的 Matlab 解法 3.2.1 无约束极值问题的符号解
例 3.3 求多元函数 f (x, y) x3 y3 3x2 3y2 9x
的极值。
解 先解方程组 fx(x, y) 3x2 6x 9 0 fy(x, y) 3 y2 6 y 0
2
2
1 21 , 1 21 。
2
2
求数值解的程序如下 f=@(x) [x(1)^2+x(1)-6; x(2)^2+x(1)-6]; xy=fsolve(f,rand(2,1)) %只能求给定初始值 附近的一组解

min f (x) x Rn
⑵ 等式约束非线性规划模型： min f (x) s.t. hj (x) 0, j 1,2, r
⑶ 不等式约束非线性规划模型： min f (x) s.t. gi (x) 0,i 1,2, m
针对上述三类非线性规划模型,其常用求解的基 本思路可归纳如下：
1 无约束的非线性规划问题
2 只有等式约束的非线性规划问题通常可用消元 法、拉格朗日乘子法或反函数法,将其化为无 约束问题求解.
3 具有不等式约束的非线性规划问题解起来很复 杂,求解这一类问题，通常将不等式化为等式 约束，再将约束问题化为无约束问题，用线 性逼近的方法将非线性规划问题化为线性规 划问题.
下面介绍一个简单的非线性规划问题的 例子,其中的一些约束条件是等式，这类非线 性规划问题可用拉格朗日方法求解.
表示当约束条件右边的值增大一个单位后，相
应目标函数值的增加值。比如说：如总存储空间由 24 变 为 25 时 ， 最 优 值 会 由 12.71 变 为 12.71 0.3947 13.10。
非线性规划解法
例9 求解非线性规划
min z (x1 1.5)2 x22
s.t.
x12
x22
1,
bj ,
i 1, 2,3 j 1, 2,3, 4
xij 0.
注: 在上面的问题中, 输水费用函数 f x 一般不是x
的线性函数. 因而相应的规划不是线性规划.
问题2 砂石运输问题
设有V立方米的砂石,要由甲地运到乙地, 运输前需
先装入一个有底无盖并在底部装有滑行器的木箱中. 砂 石运到乙地后, 从箱中倒出,在继续用空箱装运. 不论箱 子大小, 每装运一箱, 需0.1元, 箱底和两端的材料费为 20元/米2, 箱子两侧的材料费为5元/米2, 箱底的两个滑 行器与箱子同长, 材料费为2.5元/米. 问木箱的长宽高各 为多少米,才能使运费与箱子的成本费的总和为最小.

f=f(x); •
(2)若有非线性约束条件：c1 x 0 或c2 x 0, 则建立M
文件c.m定义函数c1 x,c2 x, 一般形式为
function [c1,c2]=c(x)
c1=…
c2=… (3)建立主程序。求解非线性规划的函数是fmincon,
调用格式为 x=fmincon(‘fun’,x0,A1,b1);
故它属于一个整数线性规划问题，这里当成一个线 性规划求解，求得最优解刚好是整数x1=9，x2=0， 故它就是该整数规划的最优解.若用线性规划解法求 得的最优解不是整数，将其取整后不一定是相应整 数规划的最优解，这样的整数规划应用专门的方法 求解.
二、非线性规划
1、二次规划
❖
标准形式：min
z
1
xT
x1 4x2 5
•
x1, x2 0
❖
改写成标准形式：min z
x1 2x2
1 2
x12
1 2
x22
s.t.
2x1 3x2 x1 4x2
6 5
0 0
0 0
x1 x2
❖ 建立M文件fun1.m
❖ 建立主程序(见MATLAB程序(feixianxingguihua1))
工费用如下表.问怎样分配车床的加工任务，才能既满足加
工工件的要求，又使加工费用最低？
车床 类型
甲
乙
单位工件所需加工台时数 工件 1 工件 2 工件 3
0.4
1.1
1.0
0.5
1.2
1.3
单位工件的加工费用 工件 1 工件 2 工件 3
13
9
10
11
12
8
可用台 时数
800

• 满足约束条件的点称可行点，可行点集合构成可行域
2
线性规划与非线性规划
• 非线性规划(Nonlinear Programming)
• 非线性规划的数学模型可以表示为
min f x
xRn
s.t. gi x 0 i hj x 0 j
• 在目标函数或者约束函数中至少有一个函数是非线性的 • 当非线性规划问题的可行域为整个实数域时，称为无约束优化问题，
0
优化问题无界或者不可行
• output.a lgorithm
output.iterations
优化算法类型 算法的迭代次数
• lambda.ineqlin
不等式约束的乘子
lambda.eqlin
等式约束的乘子
14
lambda.lower / upper 变量下界和上界
案例分析
• 假设有四种投资1,2,3,4，第i种投资的收益率 ri 的预期收益均值为 i E ri ，
• 在满足收益率条件下最小化风险模型：
min f x 1 xTQx 2
2 s.t. uT x M
4
xi 1, x 0
1
16
案例分析
Q 社保债券 技术交易中心 管理咨询中心 游乐中心 预期收益
社保债券 2 0.4 0.1 0 7
技术交易中心 管理咨询中心
0.4
0.1
4
3
3
6
-1
1
8
10
游乐中心 0 -1 1 10 14
方差
2 iBiblioteka Erii2
表示投资的风险大小，即收益率关于均值的偏离程度
• 令 xi 为第i个项目的投资额占总投资的比例，向量 x x1, x2, x3, x4 T表示一个

– 无穷多个最优解。若将例1中的目标函数变为 max z=50x1+50x2，则线段BC上的所有点都代表 了最优解；
– 无界解。即可行域的范围延伸到无穷远，目标 函数值可以无穷大或无穷小。一般来说，这说 明模型有错，忽略了一些必要的约束条件；
– 无可行解。若在例1的数学模型中再增加一个约 束条件4x1+3x2≥1200，则可行域为空域，不存在 满足约束条件的解，当然也就不存在最优解了。
• 交叉学科 --涉及经济、管理、数学、工程和系统等 多学科
• 开放性 --不断产生新的问题和学科分支
• 多分支 --问题的复杂和多样性
2
运筹学的主要内容
线性规划
数 非线性规划
学
整数规划
规
动态规划
划
多目标规划
学
双层规划
最优计数问题
科
组 合
网络优化
内
优 排序问题 化 统筹图
容
对策论
随 排队论
机 优 化
13
组织 宝洁公司 法国国家铁路
应用
Interface 每年节支 期刊号 （美元）
重新设计北美生产和分销系统以 1-2/1997 2亿 降低成本并加快了市场进入速 度
制定最优铁路时刻表并调整铁路 1-2/1998 1500万更多
日运营量
年收入
Delta航空公司 IBM
进行上千个国内航线的飞机优化 配置来最大化利润
负。当某一个右端项系数为负时，如 bi<0，则把该 等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2… -ain xn = -bi。
30
例：将以下线性规划问题转化为标准形式
则该极小化问题与下面的极大化问题有相同的最优解，

f(x) 为凸集 S 上的严格凸函数。 性质: 当- f(x) 为凸函数（严格凸函数）时，则称
f(x) 为凹函数（严格凹函数）。
严格凸函数
凸函数
严格凹函数
x1
x 2
2.2 凸集、凸函数和凸规划(续)
定理： f(x) 为凸集 S 上的凸函数 S 上任 意有限点的凸组合的函数值不大于各点函 数值的凸组合。
△可行方_ 向：
设 x∈S，d∈Rn, d≠0, 若存在 0
_
使 x d S, (0, ) ，
称d 为该点的可行方向。
同时满足上述两个性质的方向称 下降可行方向。
迭代算法的停止标准
1）
|| X k1 X k || 1
或
||
X k 1 || X k
X ||
k
考虑（fs）
s.t. x∈S
常用一种线性搜索的方式构造{xk}序列来求解 迭代中从一点出发沿下降可行方向找一个
新的、更优的点。
△下降方向 ：
设 x _∈S，d ∈Rn,d≠0,若存在 ，0
使 在
_
_
x _f点(x的 下d )降 方f (x向),。 (0, )
，称d 为
4 常用的搜索算法结构
以及
4) 全局收敛： 对任意初始点x(1), 算法均收敛。
5) 局部收敛： 当x(1) 充分接近解x*时，算法才收敛。
2. 实用收敛性：
定义解集
S* = { x | x 具有某种性质 }
例：S*={x|x---g.opt} S*={x|x---l.opt}
S*={x| f(x)=0} S*={x|f′(x)≤β } (β为给定实数,称为阈值
xn2

整数规划的解法
总结词
整数规划的解法可以分为精确解法和近似解法两大类。
详细描述
整数规划的解法可以分为两大类，一类是精确解法，另一类是近似解法。精确解法包括割平面法、分支定界法等， 这些方法可以找到整数规划的精确最优解。而近似解法包括启发式算法、元启发式算法等，这些方法可以找到整 数规划的近似最优解，但不一定能保证找到最优解。
模拟退火算法采用Metropolis准则来 判断是否接受一个较差解，即如果新 解的能量比当前解的能量低，或者新 解的能量虽然较高但接受的概率足够 小，则接受新解。
模拟退火算法的应用
01
模拟退火算法在旅行商问题中得到了广泛应用。通过模拟退火算 法，可以求解旅行商问题的最优解，即在给定一组城市和每对城 市之间的距离后，求解访问每个城市恰好一次并返回出发城市的 最短路径。
动态规划的解法
确定问题的阶段和状态
首先需要确定问题的阶段和状态，以便将问 题分解为子问题。
建立状态转移方程
根据问题的特性，建立状态转移方程，描述 状态之间的转移关系。
求解子问题
求解每个子问题，并存储其解以供将来使用。
递推求解
从最后一个阶段开始，通过递推方式向前求 解每个阶段的最优解。
动态规划的应用
线性规划的解法
单纯形法
01
单纯形法是求解线性规划问题的经典方法，通过迭代过程逐步
找到最优解。
对偶理论
02
对偶理论是线性规划的一个重要概念，它通过引入对偶问题来
简化求解过程。
分解算法
03
分解算法是将大规模线性规划问题分解为若干个小问题，分别
求解后再综合得到最优解。
线性规划的应用
生产计划
线性规划可以用于生产计划问题， 通过优化资源配置和生产流程， 提高生产效率和利润。

bij
Bi'j
j 1
j 1
j 1
j i
j i
j i
式中：Bi'i 和Bi'j 分别是以 及互导纳。
1 xij
为支路导纳建立起来的节点导纳矩阵的自导纳
2019/11/19
13
写成矩阵形式，即得到n个节点电力系统的直流潮流数学模型
P B'0
上式是一个线性方程组，可以一次直接求解得到结果，因而计算 速度非常快。
⑵ 从一定初值出发原来的潮流问题无解。
F(k ) 正值， (k) 0 ⑶ 有别于以上两种情况。
(k) 1, F (k)不为零或不断波动。 这种情况的原因可能是解存在，但计算精度不够。
为计算最优乘子而增加的计算量很少，见图2-10。
2019/11/19
10
第八节 几种特殊性质的潮流计算问题简介
x(k) J (x(k) )(1) f (x(k) )
作为搜索方向，并称之为目标函数在 x(k ) 处的牛顿方向。 接着是如何决定最优步长因子 *(k )的问题。
对一定的 x(k)，目标函数 F(k1是) 步长因子 (k )的一个一元函数
F(k1) F (x(k) (k)x(k) ) ( (k) )
引入标量乘子以调节变量x的修正步长，于是有
f (x) ys y(x(0) ) J (x(0) )(x) y(x) ys y(x(0) ) J (x(0) )(x) 2 y(x) 0
其中 f (x) [ f1(x), f2 (x),, fn (x)]T
2019/11/19
8
其中
上式是一个关于 的三次代数方程，可以用卡丹公式或牛顿法等求

6
信息与计算科学系
数学 建模
在一组等式或不等式的约束下，求一个函数的最大 值（或最小值）问题，其中至少有一个非线性函数，这 类问题称之为非线性规划问题。可概括为一般形式
min f ( x)，
s.t. hj ( x) 0, j 1, , q, （3.1） gi ( x) 0, i 1, , p.
其中 x [x1, , xn]T 称为模型（3.1）的决策变量， f 称 为目标函数， gi (i 1, , p)和hj ( j 1, ,q)称为约束函 数。另外，gi ( x) 0 (i 1, , p)称为等式约束，hj ( x) 0
3
信息与计算科学系
数学 建模
例 3.1 （投资决策问题）某企业有n个项目可供选择
投资，并且至少要对其中一个项目投资。已知该企业拥有
总资金 A元，投资于第i(i 1, ,n)个项目需花资金ai 元， 并预计可收益bi 元。试选择最佳投资方案。
解 设投资决策变量为
xi
1, 决定投资第i个项目 ，i 1, , n，
x(1)+x(2)^2+x(3)^3-20]; %非线性不等式约束
h=[-x(1)-x(2)^2+2;
x(2)+2*x(3)^2-3]; %非线性等式约束
11
信息与计算科学系
数学 建模
（3）编写主程序文件如下 [x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[],'fu n2')
14
信息与计)是极小值点，对应的极小值 f (1,0) 5； 点(1,2)，( 3,0)不是极值点； 点( 3,2)是极大值点，对应的极大值 f ( 3,2) 31。

第16页/共147页
1.4 凸规划
非线性规划的数学模型
Minf(X)
(1.1)
hi(X)=0 i=1,2, … ,m
(1.2)
gj(X) ≥ 0 j=1,2, … ,l
(1.3)
满足约束条件(1.2)和(1.3)的点称为可行点
(可行解)，所有可行点的集合称为可行域.
若某个可行解使目标函数(1.1)最小，就称
第18页/共147页
• 例5. 求解非线性规划
x2 g2(x) 0
g1(x) 0
A
min f (x) x12 x22 4x1 4 O s.t. g1(x) x1 x2 2 0
2
4
x1
g2 (x) x12 x2 1 0
x1 0, x2 0
最优点A(0.58,1.34), min f 3.8
f(X)在S上的局部极小点, f(X* )为局部极小值。 严格局部极小点(值)：对于所有X≠X* 且
与X*的距离小于ε的X∈S,f(X)>f(X* ),则称 X* 为f(X)在S上的严格局部极小点， f(X* )为
第4页/共147页
严格局部极小值。 全局极小点(值)：对于所有的X ∈S，都
有f(X)≥f(X* ),则称X* 为f(X)在S上的全局 极小点，f(X* )为全局极小值。
则称f(X)为定义在S上的严格凸函数. 将(1.5)和(1.6)中的不等号反向,即可得到凹函数
第8页/共147页
凸函数的性质
• 性质1 设f(X)为定义在凸集S上的凸函数, 则对 任意实数b≥ 0,函数bf(X)也是定义在S上的凸 函数.
• 性质2 设f1(X)和 f2(X)为定义在凸集S上的两 个凸函数,则其和f(X)= f1(X)+f2(X)仍为定义 在S上的凸函数.

运行输出：
最优解 1.00012815099165 -0.00000145071779
k= 33
练习题：
1、用外点法求解下列模型
min( x12 2x22 ) s.t. x1 x2 1
2、将例子程序改写为一个较为通用的罚函数 法程序。（考虑要提供哪些参数）
2. 内点法（障碍函数法）
min f (x) s.t. gi (x) 0,i 1,2,, m
第二步：求 (k) 最优的目标函数
function r=fungetlamada(lamada) %关于lamada的一元函数，求最优步长 global x0 d=fun1gra(x0); r=2*(x0(1)-lamada*d(1))^2+(x0(2)lamada*d(2))^2; %注意负号表示是负梯度
a 1, b 1 ，a,b 为常数，通常取 a=b=2。
算法步骤
（1）给定初始点 x(0)，初始罚因子 (1) ， 放大系数 c>1；允许误差 e>0,设置 k=1；
（2）以 x(k-1)作为搜索初始点，求解无约束规划问题 min f (x) P(x) ，令 x(k)为所求极小点。
lamada=fminsearch(‘fungetlamada’,la mada);%求最优步长lamada
x0=x0-lamada*fun1gra(x0);%计算x0 d=fun1gra(x0);%计算梯度 k=k+1;%迭代次数
end
disp('x='),disp(x0),disp('k='),disp (k),disp('funobj='),disp(2*x0(1)^2+ x0(2)^2)

则称 gi ( x) 0 是点 x 处的积极约束。
或起作用约束（紧约束\积极约束\有效约束）。
记 I ( x ) { i | gi ( x ) 0,1 i l }, 称 I ( x )为点 x 处的积极约束指标集。
2 例：设 g1 ( x) 2 x12 x2 0, g 2 ( x) x12 x2 1 0, g3 ( x) x1 0 .
定义4: 可行下降方向
设点 x Q ， 给定向量 d ，如果 d 既是点 x 处的可行方向， 又是该点的下降方向，则称 d 为点 x 处的可行下降方向。 6
min f ( x ) 给定点 x Q , 记点 x 的积极约束指标集为 ( x )。给定 s .t . g(x) 0 I
定理2:
向量 d ，如果 d 满足 gi ( x )T d 0 f ( x )T d 0 i I ( x)
则向量 d 是点 x 处的可行下降方向。
证略
③极值点的必要条件: 定理3:
设 x* Q，( x*)是其积极约束指标集。 I
f ( x ) 和 gi ( x ) (i I ( x*) ) 在点 x * 处可微，
9
最优性条件
无约束规划
min f ( x ) n
xR
定理：可微函数解的必要条件：x*是局部解,则： f ( x*) 0. x*是驻点(稳定点)
可微凸函数解的充要条件：x*是整体极小解当且仅当 f ( x*) 0.
(t ) f ( x * td )
10
约束规划最优性条件的几何表述
共面梯度被线性标示
12
约束规划最优性条件的几何表述
min f ( x ) s .t . ci ( x ) 0, i 1, ..., p

则称X * 为f(X )在上的全局极小点。 f(X *)为全局极小值。 若对于所有 X X * ，且X ，都有
f(X ) f(X *) 则称X * 为f(X )在上的严格全局极小点。 f(X *)为严格全局极小值。
如果将上述不等式反向 ，即可得到局部极 大值与全局极大值的定 义。
第11页
定理1：极值存在的必要条件
两边乘以“1”。 第5页
非线性规划的图解问题
图解法可以给人以直观概念，当只有两个自变量时， 非线性规划也像线性规划一样，可以利用图解法。
例：min f (X ) (x1 2)2 (x2 1)2
x1 x2 5 0
A
若令目标函数f ( X）＝C
C为某一常数。
则f ( X）＝C就代表一条曲线，
一般地，解非线性规划问题要比解线性规划问 题困难的多，因为它不像解线性规划问题有单纯形 法这一通用的方法，非线性规划目前还没有适合于 各种问题的一般算法，各个方法都有自己特定的应 用范围。
第2页
非线性规划模型
例：某金属制品厂要加工一批容积为1米3的长方 形容器，按规格要求，上下底的材料为25元/m2，侧 面的材料为40元/m2，试确定长、宽、高的尺寸，使 这个容器的成本最低。
设容器的长为x1，宽为x2，则高为1/x1x2。根据题意 得：
min
f
( x1 ,
x2 )
50 x1x2
80[
1 x1x2
( x1
x2 )]
x1, x2 0
第3页
例：某公司经营两种设备，第一种设备每件售价30元， 第二种设备每件售价为450元，根据统计，售出一件 第一种设备所需营业时间平均为0.5小时，第二种设备 为（2＋0.25x2）小时，其中x2是第二种设备的售出数 量，已知该公司在这段时间内的总营业时间为800小 时，试决定使其营业额最大的营业计划。

层次分析法
将多目标问题分解为若干层次，逐层进行分析和比较 ，确定各目标的优先级。
进化算法
借鉴生物进化原理，通过种群进化、基因交叉、变异 等操作，寻找多目标问题的非劣解集。
多目标规划的应用案例
生产计划问题
在生产过程中，需要平衡产量、成本、交货期等多个目标 ，通过多目标规划进行优化。
ห้องสมุดไป่ตู้
01
金融投资组合
投资者需要在风险和收益之间进行权衡 ，通过多目标规划选择最优的投资组合 。
02
03
城市交通规划
城市交通规划需要考虑交通流量、道 路建设成本、环境影响等多个目标， 通过多目标规划进行优化。
06
动态规划
动态规划的基本概念
1
动态规划是一种通过将原问题分解为相互重叠的 子问题，并存储子问题的解以避免重复计算的方 法。
2
它是一种优化技术，用于解决多阶段决策问题， 其中每个阶段的决策都会影响后续阶段的决策。
02
线性规划
线性规划的基本概念
01
线性规划是一种数学优化技术，用于在有限资源约 束下最大化或最小化线性目标函数。
02
它通过建立和解决线性等式或不等式约束下的优化 问题，来找到最优解决方案。
03
线性规划问题具有可加性、齐次性和凸性的特点。
线性规划的求解方法
单纯形法
单纯形法是解决线性规划问题的 经典算法，通过迭代过程逐步改 进可行解，直到找到最优解。
管理运筹学主要研究如何运用定量方 法对组织中的各种资源进行最优配置 和有效利用，以实现组织的目标和战 略。
管理运筹学的应用领域
01
生产与运作管理
涉及生产计划、调度、质量控制等 方面的优化问题。

二、函数的凸性
1.一元函数的情况 2.多元函数的情况 3.凸函数的基本性质 4. 函数的凸性与局部极值及全局最优值之间的关系
1.一元函数的情况
图 14-1
2.多元函数的情况
图 14-2
3.凸函数的基本性质
(1)若f1(x)与f2(x)为凸集D上的两个凸函数， 则对 任意的正数a与b， 函数af1(x)+bf2(x)仍为D上的凸 函数。 (2) 当函数f (x)在凸集D上二阶导数连续时， 则对 于所有的x ∈D， f (x)为凸函数的充分必要条件是： 赫森矩阵A为半正定。若赫森矩阵A为正定， 则f (x)为严格凸函数。
二、罚函数法
一、拉格朗日(Lagrangian)乘子法
引进待定乘子λ，将有等式约束的寻优问题转化 为无约束的寻优问题的做法，称为拉格朗日乘子 法。
二、罚函数法
1.内点法 2.外点法 3.内点法与外点法的比较 4.计算实例
二、罚函数法
1.内点法
2.外点法
3.内点法与外点法的比较
内点法与外点法相比较各有优缺点： (1)内点法首先要在可行域内求可行的初始点， 这当约束条件增多时，往往是困难的；而外点法 则不需要。 (2)内点法不能处理等式约束问题，而对于外点 法来说，当约束条件中出现等式约束时，外点法 的难易程度等同于不等式约束的情况。 (3)外点法在边界点的可微性较差，其惩罚项的 一阶偏微商存在，且连续，但其二阶偏微商在边 界上却不存在。
4. 函数的凸性与局部极值及全局最优值之间的关系
设f (x)为定义在凸集D上的一个函数， 一般来说， f (x)的极值点不一定是它的最优点。但是， 若f (x) 为D上的一个凸函数， 则f (x)的任何极值点， 同 时也是它的最优点。若f (x)是严格的凸函数， 则 它有唯一的最优点。