第三章 非线性规划
一、非线性规划模型的建立
1.1 非线性规划模型简介
如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不像线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。
下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。
例1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i =个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解: 设投资决策变量为
??
?=个项目
决定不投资第
，个项目决定投资第i i x i 0,1，n i ,,1 =
则投资总额为∑=n
i i i x a 1
，投资总收益为∑=n
i i i x b 1
。因为该公司至少要对一个项目投资，并且总
的投资金额不能超过总资金A ，故有限制条件
∑=≤<
n
i i i
A x a
1
另外，由于),,1(n i x i =只取值0或1，所以还有 .,,1,0)1(n i x x i i ==-
最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：
∑∑===
n
i i
i
n
i i
i
x a
x
b Q 1
1max
∑=≤<
n
i i i
A x a
1
0s.t. (3.1)
.,,1,0)1(n i x x i i ==-
上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP ）。
1.2 非线性规划模型的一般形式
)(min
x f
q j x h j ,,1,
0)(s.t.
=≤ (3.2)
p i x g i ,,1,0)( ==
其中T
n x x x ][1
=称为模型（NP ）的决策变量，f 称为目标函数，i g ),,1(p i =和
),,1(q j h j =称为约束函数。另外，0)(=x g i ),,1(p i =称为等式约束，0)(≤x h j ),,1(q j =称为不等式约束。
特别称
n
E x x f ∈),
(m in (3.3)
为无约束极值问题。
称
b Ax x f
Hx x T
T
≤+ s.t. ,2
1min
(3.4)
为二次规划问题。其中目标函数为自变量x 的二次函数，约束条件则全是线性函数。
二、非线性规划的求解方法
2.1 非线性规划解的概念
定义3.1 把满足问题（3.2）中条件的解n E X ∈称为可行解（或可行点），所有可行点的
集合称为可行集（或可行域）。记为D 。即()(){}n i j E x x g x h X D ∈=≤=,0,0| 问题(3.2)可简记为 ()x f D
x ∈min 。
定义 3.2 对于问题(3.2)，设 D X ∈*，若存在0>δ,使得对一切D X ∈，且
D X
X
∈-*
，都有()()X f X
f <*
，则称*
X
是()x f 在D 上的局部极小值点
（局部最优解）。特别地当*X X ≠时，若()()X f X f <*
，则称*
X
是()x f 在D 上的严格
局部极小值点（严格局部最优解）。
定义 3.3 对于问题(3.2),设D X ∈*,对任意的D X ∈,都有()()X f X
f <*
则称*
X
是
()x f 在D 上的全局极小值点（全局最优解）
。特别地当*
X X ≠时，若()()X f X f <*
，
则称*
X 是()x f 在D 上的严格全局极小值点（严格全局最优解）。
2.2 非线性规划的基本解法 2.2.1无约束极值问题求解方法
无约束极值问题的求解方法主要有：一维搜索算法；最速下降法；牛顿法和拟牛顿法。 2.2.2 有约束问题求解方法 (1) 近似规划法
近似规划法的基本思想是将非线性规划问题中的目标函数和约束条件近似为线性函数，并限制变量的取值范围，从而得到一个近似线性规划问题。对近似线性规划问题求解可得原问题的一个近似解，从这个近似解出发，重复以上步骤，产生一个由线性规划最优解组成的序列。这样的序列往往收敛于非线性规划问题的最有解。 (2) 罚函数法
罚函数法的基本思想是通过构造罚函数将非线性规划问题的求解，转化为求解一系列无约束极值问题，这类方法也称为序列无约束最小化方法，简记为SUMT (Sequential
Unconstrained Minimization Technique)。
该方法主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法。
三、非线性规划的Matlab 解法
3.1有约束问题
Matlab 中非线性规划的数学模型写成以下形式:
)(min x f
?????
??=≤=?≤0
)(0)(x Ceq x C Beq
x Aeq B Ax (3.5)
其中)(x f 是标量函数，Beq Aeq B A ,,,是相应维数的矩阵和向量，)(),(x Ceq x C 是非线性向量函数。
Matlab 中的命令是:
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)
它的返回值是向量x ，其中FUN 是用M 文件定义的函数)(x f ；X0是x 的初始值；A,B,Aeq,Beq 定义了线性约束Beq X Aeq B X A =≤*,*，如果没有等式约束，则A=[],B=[],Aeq=[],Beq=[]；LB 和UB 是变量x 的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x 无下界，则LB=-inf ，如果x 无上界，则UB=inf ；NONLCON 是用M 文件定义的非线性向量函数)(),(x Ceq x C ；OPTIONS 定义了优化参数，可以使用Matlab 缺省的参数设置。
例2 求下列非线性规划问题
8)(min 2
22
1++=x x x f
???????≥=+--≥-.0,020
2
12
21221x x x x x x (3.6) 解 （i ）编写M 文件fun1.m
function f=fun1(x); f=x(1)^2+x(2)^2+8; 和M 文件fun2.m
function [g,h]=fun2(x); g=-x(1)^2+x(2);
h=-x(1)-x(2)^2+2; %等式约束 （ii ）在Matlab 的命令窗口依次输入
options=optimset;
[x,y]=fmincon('fun1',rand(2,1),[],[],[],[],zeros(2,1),[], ... 'fun2', options)
x = 1 1 y = 10 3.2 无约束问题
Matlab 中无约束极值问题写成以下形式
)(min x f x
其中x 是一个向量，)(x f 是一个标量函数。
Matlab 中的基本命令是
[X,FV AL]=FMINUNC(FUN,X0,OPTIONS,P1,P2, ...)
它的返回值是向量x 的值和函数的极小值。FUN 是一个M 文件，当FUN 只有一个返回值时，它的返回值是函数)(x f ；当FUN 有两个返回值时，它的第二个返回值是)(x f 的一阶导数行向量；当FUN 有三个返回值时，它的第三个返回值是)(x f 的二阶导数阵（Hessian 阵）。X0是向量x 的初始值，OPTIONS 是优化参数，使用缺省参数时，OPTIONS 为空矩阵。P1，P2是可以传递给FUN 的一些参数。
例3 求函数2
12
2
12)1()(100)(x x x x f -+-=的最小值。 解：编写M 文件fun2.m 如下：
function f=fun3(x);
f=100*(x(2)-x(1)^2)^2+(1-x(1))^2; 在Matlab 命令窗口输入
x=fminunc('fun2',rand(1,2)) x =
1.0000 1.0000
求多元函数的极值也可以使用Matlab 的命令
[X,FV AL]= FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)
3.3 罚函数法
利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题 考虑如下问题：
)(min x f
s.t. ???
??===≥=≤t.,1,i ,0)(k s,,1,i ,0)(,,,1 ,0)(i
x x h r i x g i i
取一个充分大的数 0>M ，构造函数
∑∑∑===+-+=t
i i
s
i i r
i i x k
M
x h M
x g M
x f M x P 1
1
1
|)(|)0),(min(
)0),(max(
)(),(
（或||)(||)0),(m in()0),(m ax()(),(321x K M x H M x G M x f M x P +++=
这里 ??????????=)( )()(1x g x g x G r ，???
?
??????=)( )()(1x h x h x H s ，??????????=)( )()(1x k x k x K t ，321,,M M M 为适当的行向
量，Matlab 中可以直接利用 m ax 和 min 函数。）则以增广目标函数),(M x P 为目标函数的无约束极值问题
),(min M x P
的最优解x 也是原问题的最优解。
例4 用罚函数法求例2中的非线性规划问题 解 首先，编写 M 文件 test.m
function g=test(x);
M=50000;
f=x(1)^2+x(2)^2+8;
g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)… +M*abs(-x(1)-x(2)^2+2);
其次，在Matlab 命令窗口输入
[x,y]=fminunc('test',rand(2,1)) x =
0.8214 0.4447 y =
4.9050e+004 3.4 二次规划
若某非线性规划的目标函数为自变量x 的二次函数，约束条件又全是线性的，就称这种规划为二次规划。
Matlab 中二次规划的数学模型可表述如下：
UB
x LB beq x Aeq b
Ax x f
Hx x T
T
≤≤=?≤+ s.t.
2
1min
(3.7)
这里H 是实对称矩阵，UB LB beq b f ,,,,是列向量，Aeq A ,是相应维数的矩阵。
Matlab 中求解二次规划的命令是
[X,FV AL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)
X 的返回值是向量x ，FV AL 的返回值是目标函数在X 处的值。 例5 求解二次规划
?????
??≥≤+≤++=0, 94 3 36442)( min 2
1212121222121x x x x x x
x -x -x x x -x x f (3.8)
解 在Matlab 命令窗口输入
h=[4,-4;-4,8];
f=[-6;-3]; a=[1,1;4,1]; b=[3;9];
[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))
Warning: Large-scale method does not currently solve this problem formulation,
switching to medium-scale method. > In quadprog at 242
Optimization terminated. x =
1.9500 1.0500 value =
-11.0250
四、非线性规划建模实例
4.1 选址问题
某公司有6个建筑工地要开工,每个工地的位置(用平面坐标系a,b 表示,距离单位:km)及水泥日用量d(单位:t)由下表给出.现计划建两个临时料场,日储量各有20t.假设从料场到工地之间均有直线道路相连.试确定料场的位置,使各料场对各建筑工地的运输量与路程乘积之和为最小。
工地位置(a,b)及水泥日用量d
4.1.1 模型建立
记工地的位置为(a i ,b i ),水泥的日用量为d i ,i=1,…,6；料场的位置为(x j ,y j ),日储量为e j ,j=1,2；从料场j 向工地i 的运送量为X ij 。在各工地用量必须满足和各料场运送量不超过日储量的条件下,使总的吨千米数最小,这是非线性规划问题。可建立数学模型如下：
()()∑∑
==-+-=
6
1
2
1
2
2
i j i j i j
ij
b y a x
X f min
s.t. ?????
?
?????≥=≤==∑∑==0216
2161
2
1
ij i j ij j i ij X ,j ,
e X ,,i ,d X (3.9)
4.1.2 模型求解
利用MATLAB编程（留给读者）求解得：两个料场的坐标分别为：
(6.3875,4.3943),(5.7511,7.1867), 总的吨千米数最小为105.4626。由料场A,B向6个工地运料方案见下表：
4.2 飞行管理问题
在约10，000m高空的某边长160km的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：
1）不碰撞的标准为任意两架飞机的距离大于8km;
2）飞机飞行方向角调整的幅度不应超过30度；
3）所有飞机飞行速度均为每小时800km;
4）进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在60km以上；
5）最多需考虑6架飞机；
6）不必考虑飞机离开此区域后的状况。
请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算（方向角误差不超过0.01度），要求飞机飞行方向角调整的幅度尽量小。
设该区域4个顶点的座标为(0,0)，(160,0)，(160,160)，(0,160)。记录数据为：
飞机编号横座标x纵座标y方向角（度）
1 150 140 243
2 85 85 236
3 150 155 220.5
4 14
5 50 159 5 130 150 230 新进入 0 0 52 注：方向角指飞行方向与x 轴正向的夹角。
4.2.1 问题分析
首先我们来研究两架飞机不碰撞的条件：记两架飞机的初始位置为：()()0
000,,,j j
i i y x y x 。时刻t 飞机的位置为：
),(,sin )(,cos )(00
j i i vt y t y vt x t x i i i i i i =??
???+=+=θθ
两架飞机的距离
,
)()()]sin )(sin ()cos )(cos [(2])(sin )cos [(cos ))
()(())
()((2
2
0000
2
22
2
2
2
2
j i j i j i j
i
j i j
i
j i j i j i j i ij y y x x t y y x x v t
v t y t y t x t x r -+-+--+--+-+-=-+-=θθθθθθθθ
引入记号
)],
sin )(sin ()cos )(cos [(2],
)(sin )cos [(cos 00002
22j i j
i
j i j
i
ij j i j i ij y y x x v b v a θθθθθθθθ--+--=-+-=
则两架飞机的距离可表示为：
)0()(2
2
2
ij ij ij ij r t b t a t r ++=
因此两架飞机不碰撞的条件是：64)0()(2
22>++=ij ij ij ij r t b t a t r 。
由于不必考虑在区域外的碰撞，所以两架飞机都在区域中的时间为),min(j i ij t t t = 其中他t i 为第i 架飞机在区域内的时间：
???
???
????
???-≥-<≤≥≤<-≤<≤-≤-≤<--≥-<≤--≥≤<--≤-<<--≤<≤-=0
00000
0000
0000
000tan ,223tan ,23,sin ,
tan ,23tan ,2,cos ,tan ,2tan ,20,sin ,tan ,223tan ,20,cos i i i i i i i i i i
i
i i i i i i i i
i i
i i i i i i i i i
i i i i i i i i i i i x D y or x y if v y x y or x y D if v x x y D or x D y D if v x D x D y or x D y D if v x D t θπθπθπθπθθπθπθπθπθθπθπθπθθθπθπ
θπθθ
4.2.2 模型建立
记第i 架飞机的初始方向角为0
i θ，调整后的方向角为i i i θθθ?+=0
，其中i θ?为调整
角度。则目标函数为总的调整量：∑
=?=
N
i i f 1
θ
结合前面的不碰撞条件可得下述非线性规划模型：
???
?
?????
=≤?≠=<>?=∑=N i j i N j i t t t r t s f i ij ij N
i i ,,1,6,,,1,,,64)(..,
min 2
1
π
θθ 4.2.3 模型求解
首先将目标函数改为：∑=?=
N
i i
f 1
2
θ
,其次考虑到区域对角线的长度为D 2，从而任一
架飞机在区域内停留的时间不会超过v D t m 2=
，所以约束条件中的ij t t <可修改为：
m t t <。注意到)(2
t r ij 是t 的二次函数，可以利用
0d )(d 2
=t
t r ij ，求得ij ij a b t 2-=。若
ij t t <<0，则代人)0()(2
2
2
ij ij ij ij r t b t a t r ++=即可求得)(2t r ij 。
下面是求解飞行管理问题的Matlab 程序： 先写两个函数文件如下：
function f=air1(x) %目标函数
f=x*x';
function [c ceq]=air2(x) %非线性约束函数
x0=[150 85 150 145 130 0];
y0=[140 85 155 59 159 0];
alpha0=[243 236 220.5 159 230 52]*pi/180;
v=800;D=160;
co=cos(alpha0+x);
si=sin(alpha0+x);
tm=sqrt(2)*D/v;
for i=2:6
for j=1:i-1
a(i,j)=v^2*((co(i)-co(j))^2+(si(i)-si(j))^2);
b(i,j)=2*v*((x0(i)-x0(j))*(co(i)-co(j))+(y0(i)-y0(j))
*(si(i)-si(j)));
r(i,j)=(x0(i)-x0(j))^2+(y0(i)-y0(j))^2;
t(i,j)=-b(i,j)/(2*(a(i,j)));
if t(i,j)<0 | t(i,j)>tm
d(i,j)=1000;
else
d(i,j)=a(i,j)*t(i,j)^2+b(i,j)*t(i,j)+r(i,j);
end
end
end
c=64-[d(2,1),d(3,1:2),d(4,1:3),d(5,1:4),d(6,1:5)];
ceq=[];
然后在Matlab命令窗口中输入：
x0=[0 0 0 0 0 0];
[x,fval]=fmincon('air1',x0,[],[],[],[],vlb,vub,'air2')
x =
-0.0000 -0.0000 0.0195 -0.0000 0.0247 0.0438
fval =
0.0029
由于非线性规划通常只能找到局部最优解，我们可以尝试不同的初值求解，再通过比较找到较优的解。
习题三
1．梯子长度问题
一楼房的后面是一个很大的花园。在花园中紧靠着楼房有一个温室，温室伸入花园2m，3m，温室正上方是楼房的窗台。清洁工打扫窗台周围，他得用梯子越过温室，一头放在花园中，一头靠在楼房的墙上。因为温室是不能承受梯子压力的，所以梯子太短是不行的。现清洁工只有一架7m长的梯子，你认为它能达到要求吗？能满足要求的梯子的最小长度为多少？
a
b
2.某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台．每季度的生产费用为()2
=（元），其中x是该季生产的台数．若交货后有剩余，可x
f+
bx
ax
用于下季度交货，但需支付存储费，每台每季度c元．已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低．
第四章 非线性规划 ???? ???? 无约束最优化问题线性规划约束最优化问题非线性规划 ?? ?凸规划约束最优化问题非凸规划 ?? ?直接解法约束最优化问题求解方法间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。 直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。 第一节 目标函数的约束极值问题 所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。 对于带有约束条件的目标函数，其求最优解的过程可归结为： 一、约束与方向的定义 一）起作用约束与松弛约束 对于一个不等式约束()0g X ≤来说，如果所讨论的设计点() k X 使该约束()0g X =(或 者说() k X 当时正处在该约束的边界上)时，则称这个约束是() k X 点的一个起作用约束或紧约 束，而其他满足()0g X <的约束称为松弛约束。
冗余约束 40g ≤ 当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 {}()()()|()0,1,2, ,k k u I X u g X u m === 其意义是对() k X 点此时所有起作用约束下标的集合。 二）冗余约束 如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影 响，或是约束面不与可行域D 相交，即此约束称为冗余约束。 三）可行方向 可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。 1）设计点为自由点 设计点() k X 在可行域内是一个自由点，在各个方 向上都可以作出移动得到新点仍属于可行域，如图所示。 2）设计点为约束边界点 当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。此时，()k X 点的可行方向S 必满足条件： ()0T k i S g X ?≤ （解释：()()cos ,()T k k T k i i i S g X S g X S g X ?=??，,()90T k i S g X ?≥?）） 当,()90T k i S g X ?=?时，方向S 是约束函数i g 在()k X 点处的切线方向，即()0T k i S g X ?=。 当某个设计点x 同时有几个约束起作用时(如
第四章 约束非线性规划 § 4.3 可行方向法 作者：黄希勇 2013.5.28 引入： 对于非线性规划问题，如果不存在约束，从任一个初始点 )0(x 出发，沿)(x f 的负梯度方向进行一维收索，便可求得目标函数的无约束极小值；而对有约束的极小化问题来说，除要使目标函数在每次迭代有所下降之外，还要注意解的可行性问题，为此，在求解约束非线性规划迭代法的设计中，应在每个迭代点)(k x 出构造一个可行下降方向 )(k d 。 引入：有效约束和可行下降方向的概念 考虑非线性规划 ?? ???=≥==m i x g l j x h t s x f i j .....2,10)(......2,10)(.) (min （4.3.1） 其中，)(),(),(x g x h x f i j 均为实值连续函数，且具有二阶连续偏导数。 设)0(x 是非线性规划的一个可行解。现考虑某一不等式约束条件 0)(≥x g i 满足它有两种可能：其一为0)(>x g i ，这时，点)0(x 不是处于由这一约束条件形成的可行域边界上，因而这一约束对)0(x 点的微小摄动不起限制作用，从而称这个约束条件是)0(x 点的不起作用约束(或无效约束)；其二是0)(=x g i ，这时)0(x 点处于该约束条件形成的可行域边界上，
它对)0(x 的摄动起到了某种限制作用，故称这个约束是点的起作用约束(有效约束)。 显而易见，等式约束对所有可行点来说都是起作用约束。 1.1 D e f ： 设可行域是非空集，D x ∈，若对某非零向量n R d ∈，存在0>δ，使对任意),0(δ∈t 均有D td x ∈+,则称d 为从x 出发的可行方向。 若非线性规划的某一可行点)0(x ，对该点的任一方向d 来说，若存在实数't ，使对任意 ]',0[t t ∈均有 )()()0()0(x f td x f <+ 就称方向d 为)0(x 点的一个下降方向。 如果方向d 既是)0(x 点的可行方向，又是这个点的下降方向，就称它是该点的可行下降方向。 Eg 4.4: 略 现考虑非线性规划（4.3.1）式，设)(k x 是它的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，根据以前所说，应在)(k x 点的可行下降方向中选取某一方向)(k d ，并确定步长k t ，使 ???<+=++) ()() ()1() ()()1(k k k k k k x f x f d t x x （4.3.2） 若满足精度要求，迭代停止，)1(+k x 就是所要的点。否则，从)1(+k x 出发继续进行迭代，直到满足要求为止。上述方法称为可行方向法； 其特点是：迭代过程中采用的搜索方向为可行方向，所产生的迭代
第四章 数学规划模型 【教学目的】：深刻理解线性规划，非线性规划，动态规划方法建模的基本特点，并能熟练建立一些实际问题的数学规划模型；熟练掌握用数学软件（Matlab ，Lindo ，Lingo 等）求解优化问题的方法。 【教学重点难点】： 教学重点：线性规划和非线性规划的基本概念和算法，解决数学规划问题的一般思路和 方法，线性规划模型、整数规划模型、非线性规划模型的构建及其Matlab 与Lingo 实现。 教学难点：区分线性规划模型和非线性模型适用的实际问题，以及何时采用线性模型， 何时采用非线性模型，线性模型与非线性模型的转化。 【课时安排】：10学时 【教学方法】：采用多媒体教学手段，配合实例教学法，通过对典型例题的讲解启发学生思维，并给与学生适当的课后思考讨论的时间，加深知识掌握的程度。安排一定课时的上机操作。 【教学内容】： 在众多实际问题中，常常要求决策（确定）一些可控制量的值，使得相关的量（目标）达到最佳（最大或最小）。这些问题就叫优化问题，通常需要建立规划模型进行求解。称这些可控制量为决策变量，相关的目标量为目标函数；一般情况下，决策变量x 的取值是受限制的，不妨记为x ∈Ω，Ω称为可行域，优化问题的数学模型可表示为 Max(或Min)f(x), x ∈Ω 一般情况下，x 是一个多元变量，f(x)为多元函数，可行域比较复杂，一般可用一组不等式组来表示，这样规划问题的一般形式为 () x Min f x . ()0,1,2,,i st g x i m ≤= 虽然，该问题属于多元函数极值问题，但变量个数和约束条件比较多，一般不能用微分法进行解决，而通过规划方法来求解；这里讨论的不是规划问题的具体算法，主要是讨论如何将一个实际问题建立优化模型，并利用优化软件包进行求解。 根据目标函数和约束函数是否为线性，将规划模型分为线性规划和非线性规划。 4.1线性规划 线性规划(LP)研究的实际问题多种多样的，它在工农业生产、经济管理、优化设计与控
第四章 非线性规划 教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。 教学难点：约束最优化问题的最优性条件。 教学课时：24学时 主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。 第一节 基本概念 教学重点：非线性规划问题的引入，非线性方法概述。 教学难点：无。 教学课时：2学时 主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。 1、非线性规划问题举例 例1 曲线最优拟合问题 已知某物体的温度? 与时间t 之间有如下形式的经验函数关系： 3 12c t c c t e φ=++ （*） 其中1c ，2c ，3c 是待定参数。现通过测试获得n 组?与t 之间的实验数据),(i i t ?， i=1，2，…,n 。试确定参数1c ，2c ，3c ，使理论曲线(*)尽可能地与n 个测试点 ),(i i t ?拟合。 ∑=++-n 1i 221)]([ min 3i t c i i e t c c ?
例 2 构件容积问题 通过分析我们可以得到如下的规划模型： ??? ????≥≥=++++=0 ,0 2 ..)3/1( max 212 121222211221x x S x x x x a x x t s x x a V ππππ 基本概念 设n T n R x x x ∈=),...,(1，R R q j x h p i x g x f n j i α:,...,1),(;,...,1),();(==, 如下的数学模型称为数学规划(Mathematical Programming, MP)： ?? ? ??===≤q j x h p i x g t s x f j i ,...,1,0)( ,...,1,0)( ..) ( min 约束集或可行域 X x ∈? MP 的可行解或可行点 MP 中目标函数和约束函数中至少有一个不是x 的线性函数，称(MP)为非线性规划 令 T p x g x g x g ))(),...,(()(1= T p x h x h x h ))(),...,(()(1=， 其中，q n p n R R h R R g αα:,:，那么(MP )可简记为 ?? ? ??≤≤ 0)( 0 ..)( min x h g(x)t s x f 或者 )(min x f X x ∈ 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。 否则，称为约束非线性规划或者约束最优化问题。 定义4.1.1 对于非线性规划(MP )，若X x ∈*，并且有 X ),()(*∈?≤x x f x f 设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S ， 圆锥部分的高h 和圆柱部分的高x 2之 比为a 。确定构件尺寸，使其容积最 大。
摘要 本文旨在对非线性规划的算法和应用进行研究。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年库恩和塔克发表的关于最优性条件(后来称为库恩－塔克条件，又称为K-T条件)的论文是非线性规划正式诞生的一个重要标志。非线性规划在管理、工程、科研、军事、经济等方面都有广泛的应用，并且为最优设计提供了有力的工具。 在第一章我们主要介绍了非线性规划的基础知如非线性规划的数学模型，凸函数和凹函数，极值问题以及下降迭代算法等。 在第二章我们主要对约束条件的线性规划进行了具体介绍。在无约束非线性规划中主要讨论了一维搜索法和多变量函数极值的下降方法。 第三章介绍了求解非线性规划的计算机软件并通过一些基本的例子，从而进一步加深对非线性规划进行理解。 关键词：非线性规划；约束非线性规划；最优解
第一章绪论 1.1非线性规划综述 非线性规划是具有非线性目标函数或约束条件的数学规划，是运筹学的一个重要分支[1]。非线性规划属于最优化方法的一种，是线性规划的延伸。早在17世纪，Newton和Leibniz发明微积分的时代，已经提出函数的极值问题，后来又出现了Lagrange乘子法，Cauchy的最速下降法。但直到20世纪30年代，最优化的理论和方法才得以迅速发展，并不断完善，逐步成为一门系统的学科[2]。 1939年，Kantorovich和Hitchcock等人在生产组织管理和制定交通运输方案方面首先研究和应用了线性规划。 1947年，Dantzig提出了求解线性规划的单纯形法，为线性规划的理论和算法奠定了基础，单纯形法被誉为“20世纪最伟大的创造之一”。 1951年，由Kuhn和Tucker完成了非线性规划的基础性工作 [3]。 1959—1963年，由三位数学家共同研究成功求解无约束问题的DFP变尺度法(该算法是由英国数学家W．C．Davidon提出，由法国数学家R．Fletcher和美国数学家M．J．D.Powell加以简化)，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了多种新的算法[4]。 1965年，德国数学家C．G Broyden提出了求解非线性方程组的拟牛顿算法，并且该算法还包含了DFP算法。 1970年，四位数学家以不同角度对变尺度算法进行了深入研究，提出了BFGS 公式 (C．G Broyden，R Fletcher，D．Goldfarb，D．E Shanno) 。实践表明该算法较之DFP算法和拟Newton法具有更好的数值稳定性。 1970年，无约束优化方法的研究出现了引入注目的成果，英国数学家L．C．W Dixon和美籍华人H．Y．Huang提出了关于“二阶收敛算法的统一研究”的研究成果，提出了一个令三个自由参数的公式族．Huang族和拟牛顿公式，它可包容前面所介绍的所有无约束优化算法。 20世纪70年代，最优化无论在理论和算法上，还是在应用的深度和广度上都有了进一步的发展。随着电子计算机的飞速发展，最优化的应用能力越来越强，从而成为一门十分活跃的学科[5]。 近代最优化方法的形成和发展过程中最重要的事件有： 1、以苏联康托罗维奇和美国丹齐克为代表的线性规划； 2、以美国库恩和塔克尔为代表的非线性规划；
第四章 非线性规划 ?? ?? ???? 无约束最优化问题线性规划约束最优化问题非线性规划 ?? ?凸规划约束最优化问题非凸规划 ?? ?直接解法约束最优化问题求解方法间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。 直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。 第一节 目标函数的约束极值问题 所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。 对于带有约束条件的目标函数，其求最优解的过程可归结为： 一、约束与方向的定义 一）起作用约束与松弛约束 对于一个不等式约束()0g X ≤来说，如果所讨论的设计点() k X 使该约束()0g X =(或 者说() k X 当时正处在该约束的边界上)时，则称这个约束是() k X 点的一个起作用约束或紧约 束，而其他满足()0g X <的约束称为松弛约束。
冗余约束 4 0g ≤ 当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 {}()()()|()0,1,2, ,k k u I X u g X u m === 其意义是对() k X 点此时所有起作用约束下标的集合。 二）冗余约束 如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影 响，或是约束面不与可行域D 相交，即此约束称为冗余约束。 三）可行方向 可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。 1）设计点为自由点 设计点() k X 在可行域内是一个自由点，在各个方 向上都可以作出移动得到新点仍属于可行域，如图所示。 2）设计点为约束边界点 当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。此时，()k X 点的可行方向S 必满足条件： ()0T k i S g X ?≤ （解释：()()cos ,()T k k T k i i i S g X S g X S g X ?=??，,()90T k i S g X ?≥?）） 当,()90T k i S g X ?=?时，方向S 是约束函数i g 在()k X 点处的切线方向，即()0T k i S g X ?=。 当某个设计点x 同时有几个约束起作用时(如
第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例 1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i 个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 个项目 决定不投资第，个项目决定投资第i i x i 0,1，n i ,,1 ， 则投资总额为 n i i i x a 1 ，投资总收益为 n i i i x b 1。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A ，故有限制条件 n i i i A x a 10 另外，由于),,1(n i x i 只取值0或1，所以还有 .,,1,0)1(n i x x i i 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： n i i i n i i i x a x b Q 11 max s.t. n i i i A x a 10 .,,1,0)1(n i x x i i 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 )(min x f q j x h j ,,1,0)(s.t. (NP) p i x g i ,,1,0)(
第五节可行方向法(FDM ) 可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法，也是求解大型约束优化设计问题的主要方法之一。其收敛速度快，效果较好，适用于大中型约 束最优化问题，但程序比较复杂。 可行方向法(Feasible Direction Method)是一种直接搜索方法，其搜索方向的获取利用了目标函数和约束函数的梯度信息。用目标函数的梯度可以得到目标函数值的下降方向，而利用约束函数的梯度则可以得到可行的搜索方向。因此，可行方向法的搜索方向实质上是既使 目标函数值下降，同时又可行的方向，即可行下降方向。满足这一条件的方法就称为可行方 向法。 一、基本原理 当求解目标函数的极小值 min f (X) X R n s.t g u(X)M0 u =1,2,3川,m 当设计点X(k)处于起作用约束g i 上时，下降可行方向S必须同时满足条件： S“g(X k)乞0 S^f (X k) ：：0 由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点 上，因此最优搜索如能沿着约束边界附近进行，就有可能加速最优化搜索的进程。按照这一基本思路，在任意选定一初始点后到最后得到最优点必须解决三个问题：一是如何尽快使最优搜索从初始点到达约束边界 二是到达边界后怎样判断所找到的边界点是否是最优点； 三是如果边界点经判断不是最优点，那么下一步应如何进行最优搜索。 二、如何从初始点尽快到达边界 在任意选定初始点X0之后，首先判断X0是否为可行点，若是可行点，则选择目标函数的负梯度方向作为下一步的搜索方向。若是非可行点，则选择目标函数的梯度方 向为搜索方向。 搜索的步长可采用试探的方法逐步缩小，直到最后到达边界。 如图5-13表示了初始点为可行点时的搜索过程。 从初始点X0出发沿-\f(X°)方向，取步长为t，进行搜索，得到 X1 x1=X° -r f (X0) 若X1仍在可行区内，则把步长加大一倍继续搜索 得到 團银门 初始負到达 边界过理
-32- 第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i L =个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 ?? ?=个项目 决定不投资第，个项目 决定投资第i i x i 0,1，n i ,,1L =， 则投资总额为 ∑=n i i i x a 1，投资总收益为 ∑=n i i i x b 1 。因为该公司至少要对一个项目投资，并 且总的投资金额不能超过总资金A ，故有限制条件 ∑=≤< n i i i A x a 1 另外，由于),,1(n i x i L =只取值0或1，所以还有 .,,1,0)1(n i x x i i L ==? 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： ∑∑=== n i i i n i i i x a x b Q 11max s.t. ∑=≤< n i i i A x a 1 .,,1,0)1(n i x x i i L ==? 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 )(min x f q j x h j ,,1, 0)(s.t. L =≤ (NP) p i x g i ,,1, 0)(L ==
非线性规划（nonlinear programming） 1.非线性规划概念 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。 2.非线性规划发展史 公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为0.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。 最优化方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。 (1)解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。 (2)直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。 (3)数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。 (4)其他方法：如网络最优化方法等。
第三章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足 （目标函数）2134max x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划问题的解的概念 一般线性规划问题的标准型为 ∑==n j j j x c z 1 min (3) ∑==≤n j i j ij m i b x a 1 ,,2,1 s.t. (4) 可行解 满足约束条件（4）的解),,,(21n x x x x =，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。 可行域 所有可行解构成的集合称为问题的可行域，记为R 。 1.3 线性规划的图解法
第四节 复合形法 复合形法(Complex Method)是1965年由博克斯(Box)提出，后经古恩(Gwin)修正的解非线性规划的一种直接搜索法。如同随机方向搜索法一样．在确定搜索方向时，它不需要函数的梯度信息，它是求解非线规划中的一种简单适用的方法。 一、基本原理 对于约束优化问题 (0)min () .. ()0 1,2,3, 1,2,n u i i i f X X R s t g X u m a x b i n ?∈?≤=??≤≤=? 使用迭代格式 1= 1,2,3, k k k k k k X X X X S k α+=+?+ = 所谓复合形是指在n 维设计空间的可行域内由k(＝n+1~2n)个顶点所构成的多面体。 复合形法是一种在可行域内直接的求优方法。 利用复合形各顶点处目标函数值的大小关系，判断目标函数值的下降方向，不断丢掉函数值最大的所谓最差点，代之以既使目标函数值有所下降又能满足所有约束条件的一个新点，从而不断地构成新的复合形。如此重复计算，使新的复合形不断地向可行域的最优点移动和收缩，直至得到满足收敛准则的近似解为止。 由于对复合形不必保持规则图形，顶点数较多，因此可以求解非线性的约束问题，面且计算稳定可靠。但不能用于解含有等式约束的问题。 二、复合形的迭代步骤 一）确定复合形的顶点 复合形法是一种在可行域内直接的求优方法，要求第一个复合形的k 个顶点都是可行的。对复合形的顶点数一般推荐取k=2n ，当n 计算问题的维数较多(如n>5)时，可取k ＝n+1。如果复合形顶点数少了，一旦出现丢失顶点现象就可能会出现降维搜索而找不到真正的最优点。 初始复合形的确定方法有如下几种： (1)给定k 个初始顶点。由设计者预先选择k 个设计方案，即人工构造一个初始复合形。由于k 个顶点都必须满足所有的约束条件，因此当设计变量数目较多或约束条件比较复杂时，这样做可能是很不方便的或者是很困难的。 (2)给定一个初始顶点，随机产生其他顶点。如果用常规设计方法能取得一个设计方案，此方案虽然不是最优的，但却是一个可行的。则其他k-1个顶点可用随机法产生 ()(-) 1,2, 1,2,j j i i i i i x a r b a i n j k =+== 式中 ,i i a b —各设计变量的i x 的上、下界限，一般取边界约束值；
第三章 不等式 3.3 二元一次不等式（组）与简单的线性规划问题 3.3.2 简单的线性规划问题 第2课时 简单线性规划的应用 A 级 基础巩固 一、选择题 1．有5辆6吨的汽车，4辆4吨的汽车，要运送最多的货物，完成这项运输任务的线性目标函数为( ) A ．z ＝6x ＋4y B ．z ＝5x ＋4y C ．z ＝x ＋y D ．z ＝4x ＋5y 解析：设需x 辆6吨汽车，y 辆4吨汽车．则运输货物的吨数为z ＝6x ＋4y ，即目标函数z ＝6x ＋4y . 答案：A 2．某服装制造商有10 m 2的棉布料，10 m 2的羊毛料和6 m 2的丝绸料，做一条裤子需要1 m 2的棉布料，2 m 2的羊毛料和1 m 2的丝绸料，做一条裙子需要1 m 2的棉布料，1 m 2的羊毛料和1 m 2的丝绸料，做一条裤子的纯收益是20元，一条裙子的纯收益是40元，为了使收益达到最大，若生产裤子x 条，裙子y 条，利润为z ，则生产这两种服装所满足的数学关系式与目标函数分别为( ) A.?????x ＋y ≤10， 2x ＋y ≤10，x ＋y ≤6，x ，y ∈N z ＝20x ＋40y
B.?????x ＋y ≥10， 2x ＋y ≥10，x ＋y ≤6，x ，y ∈N z ＝20x ＋40y C.???? ?x ＋y ≤10，2x ＋y ≤10，x ＋y ≤6， z ＝20x ＋40y D.?????x ＋y ≤10， 2x ＋y ≤10，x ＋y ≤6，x ，y ∈N z ＝40x ＋20y 解析：由题意可知选A. 答案：A 3．实数x ，y 满足?????x ≥1，y ≥0，x －y ≥0，则z ＝ y －1x 的取值范围是( ) A ．[－1，0] B ．(－∞，0] C ．[－1，＋∞) D ．[－1，1) 解析：作出可行域，如图所示，y －1 x 的几何意义是点(x ，y )与点 (0，1)连线l 的斜率，当直线l 过B (1，0)时k 1最小，最小为－1.又直线l 不能与直线x －y ＝0平行，所以k l <1.综上，k ∈[－1，1)． 答案：D
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>* i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=* i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0第四章 非线性规划5-可行方向法
第五节 可行方向法（FDM ） 可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法，也是求解大型约束优化设计问题的主要方法之一。其收敛速度快，效果较好，适用于大中型约束最优化问题，但程序比较复杂。 可行方向法(Feasible Direction Method)是一种直接搜索方法，其搜索方向的获取利用了目标函数和约束函数的梯度信息。用目标函数的梯度可以得到目标函数值的下降方向，而利用约束函数的梯度则可以得到可行的搜索方向。因此，可行方向法的搜索方向实质上是既使目标函数值下降，同时又可行的方向，即可行下降方向。满足这一条件的方法就称为可行方向法。 一、基本原理 当求解目标函数的极小值 min () .. ()0 1,2,3,n u f X X R s t g X u m ?∈?≤=? 当设计点()k X 处于起作用约束i g 上时，下降可行方向S 必须同时满足条件： ()0T k i S g X ?≤ ()0T k S f X ?< 由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点上，因此最优搜索如能沿着约束边界附近进行，就有可能加速最优化搜索的进程。按照这一基本思路，在任意选定—初始点后到最后得到最优点必须解决三个问题： 一是如何尽快使最优搜索从初始点到达约束边界 二是到达边界后怎样判断所找到的边界点是否是最优点； 三是如果边界点经判断不是最优点，那么下一步应如何进行最优搜索。 二、如何从初始点尽快到达边界 在任意选定初始点0X 之后，首先判断0X 是否为可行点，若是可行点，则选择目标函数的负梯度方向 作为下一步的搜索方向。若是非可行点，则选择目标 函数的梯度方向为搜索方向。 搜索的步长可采用试探的方法逐步缩小，直到最 后到达边界。 如图5-13表示了初始点为可行点时的搜索过程。 从初始点0X 出发沿0()f X -?方向，取步长为t ， 进行搜索，得到1X 100()X X t f X =-? 若1X 仍在可行区内，则把步长加大一倍继续搜索 得到
3.3.2 简单的线性规划问题 第2课时简单线性规划的应用 A级基础巩固 一、选择题 1．有5辆6吨的汽车，4辆4吨的汽车，要运送最多的货物，完成这项运输任务的线性目标函数为() A．z＝6x＋4y B．z＝5x＋4y C．z＝x＋y D．z＝4x＋5y 解析：设需x辆6吨汽车，y辆4吨汽车．则运输货物的吨数为z＝6x＋4y，即目标函数z＝6x＋4y. 答案：A 2．某服装制造商有10 m2的棉布料，10 m2的羊毛料和6 m2的丝绸料，做一条裤子需要1 m2的棉布料，2 m2的羊毛料和1 m2的丝绸料，做一条裙子需要1 m2的棉布料，1 m2的羊毛料和1 m2的丝绸料，做一条裤子的纯收益是20元，一条裙子的纯收益是40元，为了使收益达到最大，若生产裤子x条，裙子y条，利润为z，则生产这两种服装所满足的数学关系式与目标函数分别为() A. ?? ? ??x＋y≤10， 2x＋y≤10， x＋y≤6， x，y∈N z＝20x＋40y B. ?? ? ??x＋y≥10， 2x＋y≥10， x＋y≤6， x，y∈N z＝20x＋40y
C. ?? ? ??x＋y≤10， 2x＋y≤10， x＋y≤6， z＝20x＋40y D. ?? ? ??x＋y≤10， 2x＋y≤10， x＋y≤6， x，y∈N z＝40x＋20y 解析：由题意可知选A. 答案：A 3．实数x，y满足 ?? ? ??x≥1， y≥0， x－y≥0， 则z＝ y－1 x的取值范围是() A．[－1，0] B．(－∞，0] C．[－1，＋∞) D．[－1，1) 解析：作出可行域，如图所示， y－1 x 的几何意义是点(x，y)与点(0，1)连线l的斜率，当直线l过B(1，0)时k1最小，最小为－1.又直线l不能与直线x－y＝0平行，所以k l<1.综上，k∈[－1，1)． 答案：D 4．某农户计划种植黄瓜和韭菜，种植面积不超过50亩，投入资金不超过54万元，假设种植黄瓜和韭菜的产量、成本和售价如下表：
第二节 SUMT 方法（罚函数法） 一、SUMT 方法的原理 SUMT （sequential unconstrained minimization technique ）法，序列无约束极小化方法,亦称为罚函数法。它是一种不等式约束最优化问题的间接解法 它的基本思想是将原来的目标函数和约束函数按一定的方式构成一个新的函数，在这个新函数中，既包括目标函数，又包括全部约束函数和一个可以变化的乘子。 当这个乘子按一定的方式改变时，就得到一个新函数序列，求每一个新函数的最优解都是一个无约束最优化问题，这样就把一个约束最优化问题转化为一系列无约束最优化问题进行求解。所得到的最优解序列将逐步逼近原问题的最优解。 引例一：min ()f X ax = s.t ()0g X b x =-≤ 显然f （X ）的最优点为x*=b ，对应的最小值为f （X*）=ab 用SUMT 求解函数的最优解 构造函数 11(,)()()k k k X r f X r ax r g X b x Φ=-=-- 0k r >—可变化乘子，它是一个很小的正 数。 其最优解为： *()k X r b =+ 此时对应的(,)k X r Φ的最小值为 ***1(,)k k X r ax r b x ab Φ=--=+ 最优点*()k X r 和最小值*(,)k X r Φ均是k r 的函数。当k r 取不同值时，它们有不同的值，而当0k r →时，**()k X r X b →=，*(,)*k X r f X ab Φ→=（），即最后收敛于约束最优点。 min lim[min (,)]() {|()0}k k i r X r f X R X g X X R →Φ==≤∈ 以上分析从理论上说明了无约束最优化问题min (,)k X r Φ与约束优化问题 min () {|()0}i f X R X g X X R =≤∈之间的联系：约束非线性规划问题可以通过构造新目 标函数序列，用无约束优化方法求其极小点，并逐次逼近原问题的最优点。 问题：如何构造新函数？或者说新函数具有什么特点？
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈???≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈???≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的),2,1()( =k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1( =+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即 .)()()(10 ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）； （3）微积分中的求根法（切线法，二分法等）。 考虑一维极小化问题 )(min t f b t a ≤≤
第四章 非线性规划 本章, 我们介绍两种解决非线性规划问题的软件: 第一种: MATLAB 中的optimization toolbox 中的若干程序; 第二种: LINGO 软件. 1．MATLAB 程序说明 1.1 无约束问题 程序名: unpfun1函数, unpfun2函数 unpfun1 实例: Minimize the function 221122()32f x x x x x =++ 在命令窗口输入以下信息: >> x0=[1,1]; % Then call fminunc to find a minimum of unpfun1 near [1,1] >> [x,fval]=fminunc(@unpfun1,x0) 输出以下信息: Optimization terminated successfully: Search direction less than 2*options.TolX x = 1.0e-008 * -0.7591 0.2665 fval = 1.3953e-016 unpfun2实例：将上述的实例用梯度法做 在命令窗口输入以下信息: >> options = optimset('GradObj','on'); % To minimize this function with the gradient provided >> x0 = [1,1]; >> [x,fval] = fminunc(@unpfun2,x0,options) 输出以下信息: Optimization terminated successfully: First-order optimality less than OPTIONS.TolFun, and no negative/zero curvature detected x = 1.0e-015 * 0.1110 -0.8882