第三章 非线性规划

第三章 非线性规划

§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 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 11max

s.t.

n

i i

i

A x

a 1

.,,1,0)1(n i x x i i

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP ）。可概括为一般形式

)(min x f

q j x h j ,,1,

0)(s.t.

(NP)

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 称为不等式约束。

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：

（i ）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。

（ii ）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。

（iii ）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。

（iv ）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。

1.2 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。

1.3 非线性规划的Matlab 解法

Matlab 中非线性规划的数学模型写成以下形式 )(min x f

)(0)(x Ceq x C Beq x Aeq B

Ax ,

其中)(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 求下列非线性规划问题

.0,020

8)( min 2

12

2122

12221x x x x x x x x x f （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)

就可以求得当1,121 x x 时，最小值10 y 。 1.4 求解非线性规划的基本迭代格式 记（NP ）的可行域为K 。 若K x *

，并且 K x x f x f ),

()(*

则称*

x 是（NP ）的整体最优解，)(*

x f 是(NP)的整体最优值。如果有

**,),()(x x K x x f x f

则称*

x 是（NP ）的严格整体最优解，)(*

x f 是(NP)的严格整体最优值。

若K x *，并且存在*

x 的邻域)(*x N ，使 K x N x x f x f )(),

()(**

，

则称*

x 是（NP ）的局部最优解，)(*

x f 是(NP)的局部最优值。如果有

K x N x x f x f )(),

()(**

则称*

x 是（NP ）的严格局部最优解，)(*

x f 是(NP)的严格局部最优值。

由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。

对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点n

R x

出发，按照某一特定的迭代规则产生一个点列

}{k x ，使得当}{k x 是有穷点列时，其最后一个点是(NP)的最优解；当}{k x 是无穷点

列时，它有极限点，并且其极限点是(NP)的最优解。

设n

k R x 是某迭代方法的第k 轮迭代点，n k R x

1

是第1 k 轮迭代点，记

k k k k p t x x 1

（1）

这里1,,1 k n k k p R p R t ，显然k

p 是由点k x 与点1

k x 确定的方向。式（1）就

是求解非线性规划模型(NP)的基本迭代格式。

通常，我们把基本迭代格式（1）中的k

p 称为第k 轮搜索方向，k t 为沿k

p 方向的步长，使用迭代方法求解(NP)的关键在于，如何构造每一轮的搜索方向和确定适当的步长。

设0, p R x n

，若存在0 ，使 ),0(),()( t x f tp x f ， 称向量p 是f 在点x 处的下降方向。

设0, p R x n

，若存在0 t ，使

K tp x ，

称向量p 是点x 处关于K 的可行方向。

一个向量p ，若既是函数f 在点x 处的下降方向，又是该点关于区域K 的可行方向，则称之为函数f 在点x 处关于K 的可行下降方向。

现在，我们给出用基本迭代格式（1）求解(NP)的一般步骤如下：

0° 选取初始点0

x ，令0: k 。

1° 构造搜索方向，依照一定规则，构造f 在点k

x 处关于K 的可行下降方向作为搜索方向k

p 。

2° 寻求搜索步长。以k x 为起点沿搜索方向k

p 寻求适当的步长k t ，使目标函数值有某种意义的下降。 3° 求出下一个迭代点。按迭代格式（1）求出

k k k k p t x x

1

。 若1

k x

已满足某种终止条件，停止迭代。

4° 以1

k x 代替k

x ，回到1°步。

1.5 凸函数、凸规划

设)(x f 为定义在n 维欧氏空间)

(n E

中某个凸集R 上的函数，若对任何实数

)10( 以及R 中的任意两点)1(x 和)2(x ，恒有

)()1()())1(()

2()1()2()1(x f x f x x f 则称)(x f 为定义在R 上的凸函数。

若对每一个)10( 和R x x )

2()1(恒有

)()1()())1(()

2()1()2()1(x f x f x x f 则称)(x f 为定义在R 上的严格凸函数。

考虑非线性规划

}

,,2,1,0)(|{)( min l j x g x R x f j R

x 假定其中)(x f 为凸函数，),,2,1)((l j x g j 为凸函数，这样的非线性规划称为

凸规划。

可以证明，凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优解的集合形成一个凸集。当凸规划的目标函数)(x f 为严格凸函数时，其最优解必定唯一（假定最优解存在）。由此可见，凸规划是一类比较简单而又具有重要理论意义的非线性规划。 §2 无约束问题

2.1 一维搜索方法

当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法，0.618法等）；插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切线法，二分法等）。

考虑一维极小化问题

)(min t f b

t a （2）

若)(t f 是],[b a 区间上的下单峰函数，我们介绍通过不断地缩短],[b a 的长度，来搜索得（2）的近似最优解的两个方法。

为了缩短区间],[b a ，逐步搜索得（2）的最优解*

t 的近似值，我们可以采用以下途径：在],[b a 中任取两个关于],[b a 是对称的点1t 和2t （不妨设12t t ，并把它们叫做搜索点），计算)(1t f 和)(2t f 并比较它们的大小。对于单峰函数，若)()(12t f t f ，则必有],[1*

t a t ，因而],[1t a 是缩短了的单峰区间；若)()(21t f t f ，则有

],[2*b t t ，故],[2b t 是缩短了的单峰区间；若)()(12t f t f ，则],[1t a 和],[2b t 都是

缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，显然又可获得更短的单峰区间。如此进行，在单峰区间缩短到充分小时，我们可以取最后的搜索点作为（2）最优解的近似值。

应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快地缩短？ 2.1.1 Fibonacci 法 若数列{n F }满足关系：

110 F F ,,3,2,

12 n F F F n n n

则称}{n F 为Fibonacci 数列，n F 称为第n 个Fibonacci 数，称相邻两个Fibonacci 数之

比

n

n F F 1

为Fibonacci 分数。 当用斐波那契法以n 个探索点来缩短某一区间时，区间长度的第一次缩短率为

n n F F 1

，其后各次分别为2

1231,,,F F F F F F n n n n 。由此，若1t 和)(122t t t 是单峰区间],[b a 中第1个和第2个探索点的话，那么应有比例关系

n n F F a b a t 11 ， n

n F F a b a t 2

2 从而

)(11a b F F a t n n

，)(22a b F F

a t n

n （3） 它们关于],[b a 确是对称的点。

如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超过精度0 ，这就要求最后区间的长度不超过 ，即

n

F a

b （4） 据此，我们应按照预先给定的精度 ，确定使（4）成立的最小整数n 作为搜索次数，直到进行到第n 个探索点时停止。

用上述不断缩短函数)(t f 的单峰区间],[b a 的办法，来求得问题（2）的近似解，

是Kiefer(1953年)提出的，叫做Finbonacci 法，具体步骤如下：

1° 选取初始数据，确定单峰区间],[00b a ，给出搜索精度0 ，由（4）确定搜

索次数n 。

2° 00,,1b b a a k ，计算最初两个搜索点，按（3）计算1t 和2t 。

3° while 1 n k

)(),(2211t f f t f f if 21f f )()()

1(;;1122a b k n F k n F a t t t t a

else

)()

()

1(;;2211b a k n F k n F b t t t t b

end

1 k k

end 4° 当进行至1 n k 时，

)(2

1

21b a t t

这就无法借比较函数值)(1t f 和)(2t f 的大小确定最终区间，为此，取

)

)(2

1()(2

112a b a t b a t

其中 为任意小的数。在1t 和2t 这两点中，以函数值较小者为近似极小点，相应的函数值为近似极小值。并得最终区间],[1t a 或],[2b t 。

由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数，达到预定的某一缩短率。

例3 试用斐波那契法求函数2)(2

t t t f 的近似极小点，要求缩短后的区间

不大于区间]3,1[ 的0.08倍。

程序留作习题。 2.1.2 0.618法

若0 ，满足比例关系

11

称之为黄金分割数，其值为 6180339887.02

1

5

。 黄金分割数 和Fibonacci 分数之间有着重要的关系，它们是

1°

11 n n n n F F

F F ，n 为偶数， 1

1 n n n n F F

F F ，n 为奇数。

2° n

n n F F 1

lim

。

现用不变的区间缩短率0.618，代替斐波那契法每次不同的缩短率，就得到了黄金

分割法（0.618法）。这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果也相当好，因而易于为人们所接受。

用0.618法求解，从第2个探索点开始每增加一个探索点作一轮迭代以后，原单峰区间要缩短0.618倍。计算n 个探索点的函数值可以把原区间],[00b a 连续缩短1 n 次，因为每次的缩短率均为 ，故最后的区间长度为

1

00)( n a b

这就是说，当已知缩短的相对精度为 时，可用下式计算探索点个数n ：

1n

当然，也可以不预先计算探索点的数目n ，而在计算过程中逐次加以判断，看是否已满足了提出的精度要求。

0.618法是一种等速对称进行试探的方法，每次的探索点均取在区间长度的0.618倍和0.382倍处。

2.2 二次插值法 对极小化问题（2），当)(t f 在],[b a 上连续时，可以考虑用多项式插值来进行一维搜索。它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近（2）的最优解。

2.3 无约束极值问题的解法 无约束极值问题可表述为

)(),

( m in n E x x f （5）

求解问题（5）的迭代法大体上分为两种：一是用到函数的一阶导数或二阶导数，

称为解析法。另一是仅用到函数值，称为直接法。

2.3.1 解析法

2.3.1.1 梯度法（最速下降法） 对基本迭代格式

k k k k p t x x 1 （6）

我们总是考虑从点k x 出发沿哪一个方向k

p ，使目标函数f 下降得最快。微积分的知识告诉我们，点k

x 的负梯度方向 )(k

k

x f p ，

是从点k x 出发使f 下降最快的方向。为此，称负梯度方向)(k

x f 为f 在点k

x 处的最速下降方向。

按基本迭代格式（6），每一轮从点k x 出发沿最速下降方向)(k

x f 作一维搜索，来建立求解无约束极值问题的方法，称之为最速下降法。

这个方法的特点是，每轮的搜索方向都是目标函数在当前点下降最快的方向。同

时，用0)( k

x f 或 )(k

x f 作为停止条件。其具体步骤如下：

1°选取初始数据。选取初始点0

x ，给定终止误差，令0: k 。

2°求梯度向量。计算)(k

x f ， 若 )(k

x f ，停止迭代，输出k x 。否则，

进行3°。

3° 构造负梯度方向。取

)(k k x f p . 4° 进行一维搜索。求k t ，使得

)(min )(0

k

k

t k

k k

tp x f p t x f

令,1:,1

k k p t x x

k k k k 转2°。

例4 用最速下降法求解无约束非线性规划问题 2

22

125)(m in x x x f

其中T

x x x ),(21 ，要求选取初始点T

x )2,2(0

，终止误差6

10 。

解：（i ）T

x x x f )50,2()(21 编写M 文件detaf.m 如下 function [f,df]=detaf(x); f=x(1)^2+25*x(2)^2; df(1)=2*x(1); df(2)=50*x(2);

（ii ）编写M 文件zuisu.m clc

x=[2;2];

[f0,g]=detaf(x);

while norm(g)>0.000001 p=-g'/norm(g);

t=1.0;f=detaf(x+t*p); while f>f0

t=t/2;f=detaf(x+t*p); end x=x+t*p

[f0,g]=detaf(x) end

2.3.1.2 Newton 法

考虑目标函数f 在点k

x 处的二次逼近式

))(()(2

1

)()()()()(2k k T k k T k k x x x f x x x x x f x f x Q x f

假定Hesse 阵

22

12122

122)()()()

()(n

k n k

n k k k

x x f x x x f x x x f x x f x f

正定。

由于)(2

k

x f 正定，函数Q 的稳定点1

k x 是)(x Q 的最小点。为求此最小点，令

0))(()()(121 k k k k k x x x f x f x Q ，

即可解得

)()]([121k k k k x f x f x x .

对照基本迭代格式（1），可知从点k

x 出发沿搜索方向。 )()]([1

2

k

k

k

x f x f p

并取步长1 k t 即可得)(x Q 的最小点1 k x 。通常，把方向k

p 叫做从点k

x 出发的

Newton 方向。从一初始点开始，每一轮从当前迭代点出发，沿Newton 方向并取步长为1的求解方法，称之为Newton 法。其具体步骤如下：

1°选取初始数据。选取初始点0

x ，给定终止误差0 ，令0: k 。

2°求梯度向量。计算)(k

x f ，若 )(k x f ，停止迭代，输出k

x 。否则，

进行3°。

3°构造Newton 方向。计算1

2

)]([ k

x f ，取

)()]([1

2k

k

k x f x f p .

4° 求下一迭代点。令1:,1

k k p x x

k

k

k ，转2°。 例5 用Newton 法求解，

2

221424125)(m in x x x x x f

选取T

x )2,2(0

，6

10 。

解：（i ）T x x x x x x x f ]210024[)(2213

22

2

13

1

212221212

2

212430044212x x x x x x x x f 编写M 文件nwfun.m 如下：

function [f,df,d2f]=nwfun(x);

f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2; df(1)=4*x(1)^3+2*x(1)*x(2)^2; df(2)=100*x(2)^3+2*x(1)^2*x(2); d2f(1,1)=12*x(1)^2+2*x(2)^2; d2f(1,2)=4*x(1)*x(2); d2f(2,1)=d2f(1,2);

d2f(2,2)=300*x(2)^2+4*x(1)*x(2);

（ii ）编写M 文件： clc

x=[2;2];

[f0,g1,g2]=nwfun(x)

while norm(g1)>0.00001 %dead loop,for i=1:3 p=-inv(g2)*g1',p=p/norm(p) t=1.0,f=detaf(x+t*p) while f>f0

t=t/2,f=detaf(x+t*p), end x=x+t*p

[f0,g1,g2]=nwfun(x) end

如果目标函数是非二次函数，一般地说，用Newton 法通过有限轮迭代并不能保证可求得其最优解。

Newton 法的优点是收敛速度快；缺点是有时不好用而需采取改进措施，此外，当维数较高时，计算1

2

)]([ k

x f 的工作量很大。

2.3.1.3 变尺度法

变尺度法（Variable Metric Algorithm ）是近20多年来发展起来的，它不仅是求解无约束极值问题非常有效的算法，而且也已被推广用来求解约束极值问题。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性，因而使变尺度法获得了很高的声誉。下面我们就来简要地介绍一种变尺度法—DFP 法的基本原理及其计算过程。这一方法首先由Davidon 在1959年提出，后经Fletcher 和Powell 加以改进。

我们已经知道，牛顿法的搜索方向是)

()]([1

2

k

k

x f x f ，为了不计算二阶

导数矩阵)]([2

k

x f 及其逆阵，我们设法构造另一个矩阵，用它来逼近二阶导数矩阵的逆阵1

2

)]([ k

x f ，这一类方法也称拟牛顿法（Quasi-Newton Method ）。

下面研究如何构造这样的近似矩阵，并将它记为)(k H 。我们要求：每一步都能以现有的信息来确定下一个搜索方向；每做一次选代，目标函数值均有所下降；这些近似矩阵最后应收敛于解点处的Hesse 阵的逆阵。

当)(x f 是二次函数时，其Hesse 阵为常数阵A ，任两点k x 和1

k x

处的梯度之差为

)()()(11

k k k k x x A x f x

f

或

)]()([111k k k k x f x f A x x

对于非二次函数，仿照二次函数的情形，要求其Hesse 阵的逆阵的第1 k 次近似矩阵)

1( k H

满足关系式

)]()([1)1(1k k k k k x f x f H x x （7）

这就是常说的拟Newton 条件。 若令

k

k k k k k x

x x x f x f G 11)()

()( （8） 则式（7）变为

)()

1(k k k

G H x ， （9）

现假定)(k H 已知，用下式求)1( k H （设)(k H 和)

1( k H 均为对称正定阵）；

)()()1(k k k H H H （10）

其中)(k H 称为第k 次校正矩阵。显然，)

1( k H 应满足拟Newton 条件（9），即要求

)()()()(k k k k G H H x

或

)()()()(k k k k k G H x G H （11）

由此可以设想， )

(k H 的一种比较简单的形式是

T k k k T k k k W G H Q x H )()()()()()()( (12)

其中)

(k Q

和)

(k W

为两个待定列向量。

将式（12）中的)

(k H 代入（11），得

)()()()()()()()()()(k k k k T k k k k T k k G H x G W G H G Q x

这说明，应使

1)()()()()()( k T k k T k G W G Q （13）

考虑到)(k H 应为对称阵，最简单的办法就是取

)

()()()(k k k k k

k k G

H W x

Q （14） 由式（13）得

1)()()()()()( k k T k k k T k k G H G G x （15）

若)

()(k T

k G

x 和)()()()(k k T

k G H G

不等于零，则有

)()()()()()(1)(1)(1k k T k k k T k k T k k G H G x G G x （16） 于是，得校正矩阵

)

()()()()()()()()

()()()()(k k T k k T k k k k T k T k k k G H G H G G H x G x x H

(17) 从而得到

)

()()()

()()()()()

()

1()()()()(k k T k k T k k k k T k T k k k k G H G H G G H x G x x H

H

（18） 上述矩阵称为尺度矩阵。通常，我们取第一个尺度矩阵)

0(H

为单位阵，以后的尺度矩

阵按式（18）逐步形成。可以证明：

（i ）当k

x 不是极小点且)

(k H

正定时，式（17）右端两项的分母不为零，从而可

按式（18）产生下一个尺度矩阵)

1( k H

；

（ii ）若)(k H 为对称正定阵，则由式（18）产生的)

1( k H 也是对称正定阵；

（iii ）由此推出DFP 法的搜索方向为下降方向。 现将DFP 变尺度法的计算步骤总结如下。 1°给定初始点0

x 及梯度允许误差0 。

2°若 )(0x f ，则0

x 即为近似极小点，停止迭代，否则，转向下一步。 3°令

I H )0(（单位矩阵）

， )(0)0(0x f H p

在0

p 方向进行一维搜索，确定最佳步长0 ：

)()(min 0

00

p x f p x f

如此可得下一个近似点

001p x x

4°一般地，设已得到近似点k

x ，算出)(k

x f ，若

)(k

x f

则k

x 即为所求的近似解，停止迭代；否则，计算)

(k H

：

)

1()1()1()1()1()1()1(1)1(11)

1()

()()( )()( k k T k k T k k k k T k T k k k k G H G H G G H x G x x H

H

并令)()

(k k k

x f H

p ，在k p 方向上进行一维搜索，得k ，从而可得下一个近似点

k k k k p x x

1

5°若1

k x 满足精度要求，则1

k x 即为所求的近似解，否则，转回4°，直到求

出某点满足精度要求为止。

2.3.2 直接法

在无约束非线性规划方法中，遇到问题的目标函数不可导或导函数的解析式难以表示时，人们一般需要使用直接搜索方法。同时，由于这些方法一般都比较直观和易于理解，因而在实际应用中常为人们所采用。下面我们介绍Powell 方法。

这个方法主要由所谓基本搜索、加速搜索和调整搜索方向三部分组成，具体步骤如下：

1° 选取初始数据。选取初始点0

x ，n 个线性无关初始方向，组成初搜索方向组

},,,{110 n p p p 。给定终止误差0 ，令0: k 。

2°进行基本搜索。令k

x y :0

，依次沿},,,{1

1

n p p p 中的方向进行一维搜

索。对应地得到辅助迭代点n

y y y ,,,2

1

，即

n

j tp y f p t y f p t y y j j t j j j j j j j ,,1)

(min )(1101111

11

3°构造加速方向。令0

y y p n

n

，若 n p ，停止迭代，输出n k y x 1

。

否则进行4°。

4°确定调整方向。按下式

}1|)()(m ax {)()(11n j y f y f y f y f j j m m

找出m 。若

)]()([2)2()(2)(100m m n n y f y f y y f y f y f

成立，进行5°。否则，进行6°。

5°调整搜索方向组。令

)(min )(:0

1n n t n n n n n n k tp y f p t y f p t y x .

同时，令

},,,,,,{:},,,{11101110n

n m m k n p p p p p p p p ，

1: k k ，转2°。

6°不调整搜索方向组。令1:,:1

k k y x n

k ，转2°。

2.4 Matlab 求函数的极小值和函数的零点

2.4.1 求单变量有界非线性函数在区间上的极小值 ],[ x , )(min b a x f x

Matlab 的命令为

[X,FV AL] = FMINBND(FUN,x1,x2,OPTIONS)，

它的返回值是极小点x 和函数的极小值。这里fun 是用M 文件定义的函数或Matlab 中的单变量数学函数。

例6 求函数 ]5,0[ ,1)3()(2

x x x f 的最小值。 解 编写M 文件fun1.m function f=fun1(x); f=(x-3)^2-1;

在Matlab 的命令窗口输入 [x,y]=fminbnd('fun1',0,5) 即可求得极小点和极小值。

2.4.2 求多变量函数的极小值 , )(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 的一些参数。

例7 求函数2

12

212)1()(100)(x x x x f 的最小值。 解：编写M 文件fun2.m 如下： function [f,g]=fun2(x);

f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;

g=[-400*x(1)*(x(2)-x(1)^2)-2(1-x(1)) 200*(x(2)-x(1)^2)];

在Matlab 命令窗口输入

fminunc('fun2',rand(1,2)) 即可求得函数的极小值。

求多元函数的极值也可以使用Matlab 的命令

[X,FV AL]= FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)。 §3 约束极值问题

带有约束条件的极值问题称为约束极值问题，也叫约束规划问题。 求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法。

3.1 最优性条件

库恩—塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件，但一般说它并不是充分条件（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）。

3.2 二次规划

若某非线性规划的目标函数为自变量x 的二次函数，约束条件又全是线性的，就称这种规划为二次规划。

Matlab 中二次规划的数学模型可表述如下：

b Ax x f Hx x T T

s.t. ,2

1

min 这里H 是实对称矩阵，b f ,是列向量，A 是相应维数的矩阵。

Matlab 中求解二次规划的命令是

[X,FV AL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

X 的返回值是向量x ，FV AL 的返回值是目标函数在X 处的值。（具体细节可以参看在Matlab 指令中运行help quadprog 后的帮助）。

例8 求解二次规划

0,

94 3

36442)( min 21212121222121x x x x x x x -x -x x x -x x f

解 编写如下程序： 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))

求得

1.02501)( Min , 0500.19500.1

x f x 。

3.3 罚函数法

利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential Unconstrained Minimization Technique)。

罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法，下面介绍外罚函数法。

考虑如下问题：

)(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 中可以直接利用 max 和 min 函数。）则以增广目标函数),(M x P 为

目标函数的无约束极值问题

),(min M x P

的最优解x 也是原问题的最优解。

例9 求下列非线性规划

.0,x 02x -

0x

8)( min 2

12

2122

12221x x x x x x f 解 (i)编写 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);

(ii)在Matlab 命令窗口输入 [x,y]=fminunc('test',rand(2,1)) 即可求得问题的解。

§4 飞行管理问题

在约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 145 50 159 5 130 150 230 新进入 0 0 52 注：方向角指飞行方向与x 轴正向的夹角。

试根据实际应用背景对你的模型进行评价与推广。

提示：

64))()(())()((22 t y t y t x t x j i j i

11 n i ，n j i 1，},min{0j i T T t

其中n 为飞机的总架数，

))(),((t y t x i i 为t 时刻第i 架飞机的坐标，j i T T ,分别表示第j i ,架飞机飞出正方形区域边界的时刻。这里

i i i vt x t x cos )0()( ，i i i vt y t y sin )0()( ，n i ,,2,1 ；

i i i 0，6

||

i ，n i ,,2,1 ；

其中v 为飞机的速度，i i ,0

分别为第i 架飞机的初始方向角和调整后的方向角。

令

c bt at t y t y t x t x l j i j i j i 222,64))()(())()((

其中2

sin

42

2

j

i v a ，

)]

sin ))(sin 0()0(())0()0([(2j i j i j i y y x x v b

64))0()0(())0()0((22 j i j i y y x x c

则两架飞机不碰撞的条件是042

ac b 。

习 题 三

1. 用Matlab 的非线性规划命令fmincon 求解飞行管理问题。

2. 用罚函数法求解飞行管理问题。

3. 某工厂向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交40台，第二季末交60台，第三季末交80台。工厂的最大生产能力为每季100台，每

季的生产费用是2

2.050)(x x x f （元），此处x 为该季生产发动机的台数。若工厂生产的多，多余的发动机可移到下季向用户交货，这样，工厂就需支付存贮费，每台发动机每季的存贮费为4元。问该厂每季应生产多少台发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季度开始时发动机无存货）。

图解法和单纯形法求解线性规划问题

图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式

非线性规划的论文

摘要 本文旨在对非线性规划的算法和应用进行研究。非线性规划是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、以美国库恩和塔克尔为代表的非线性规划；

第三章 非线性规划[001]

第三章 非线性规划 §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)(

用最速下降法求解无约束非线性规划问题

运 筹 学 实 习 报 告 姓名： xxxxxxxxxx 学号： xxxxxxxxxxx 专业班级： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日

题目：用最速下降法求解无约束非线性规划问题 摘要： 无约束最优化问题的求解方法分为解析法和直接法两大类。解析法需要计 算函数的梯度，其中最速下降法就属于解析法中的一种。对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。本文通过理论的计算方法，进一步分析，最后用c++编程实现求出允许误差内的最优解。此编程可用于计算符合下列形式的函数求最优解过程： f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中：a[i] (i=0,1,2,3,4,5) 为函数的系数。 本文以“ 李占利 主编，中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法，5.1 最速下降法 ”例5—1为实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。然后应用c++语言编程，得到在精度范围内的精确最优解。 C++编程计算的最优解为 : T x x ]0329218.0,00823045.0[)3(*-==。 即转化为分数结果为：?? ????-==412432) 3(*x x 。 满足精度要求的模为： 101 0736154.0||||)3(= <=εp 。 关键词：无约束非线性规划 解析法 最速下降法 梯度 模 最优解

数学建模-非线性规划

-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 ==

第三章线性规划

第三章 线性规划 §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 线性规划的图解法

2-线性规划问题的图解法

第二节 线性规划问题的图解法 对一个线性规划问题，建立数学模型之后，面临着如何求解的问题。这里先介绍含有两个未知变量的线性规划问题的图解法，它简单直观。 图解法的步骤： 步骤1：确定可行域。 第1步： 绘制约束等式直线，确定由约束等式直线决定的两个区域中哪个区域对应着由约束条件所定义的正确的不等式。我们通过画出指向正确区域的箭头，来说明这个正确区域。 第2步：确定可行域。 步骤2：画出目标函数的等值线，标出目标值改进的方向。 步骤3：确定最优解。用图示的方式朝着不断改进的目标函数值的方向，移动目标函数的等值线，直到等值线正好接触到可行域的边界。等值线正好接触到可行城边界的接触点对应着线性优化模型的最优解。 例1－3，用图解法求解线性规划问题 12 12121212max 23221228..416412,0 z x x x x x x s t x x x x =++≤??+≤??≤??≤?≥?? 解： 图1－3 （1） 画出线性规划问题的可行域，它是为以O(0,0)、A(0,3)、B(2,3)、C(4,2)、 D(0,4)为顶点的凸5边形，如图1－3。 （2） 画出一条目标函数的等值线12236x x +=，图1－3中红颜色的虚 线。

（3） 目标函数的等值线往上移动时，目标函数值增大（图1－3中红颜 色的实线）。由于问题的解要满足全部约束条件，因此目标函数的 等值线要与可行域有交点。当目标函数的等值线移动到 122314x x +=时，它与可行域只有一个交点，再往上移动时，与 可行域不再有交点。这就是说最优解为：124,2x x ==，最优目标 函数值为14。 例1-3中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况： （1）唯一最优解（2）多重最优解。 （3）无界解。 （4）无可行解。 这里我们不再举例，请大家自己阅读教材。 当线性规划问题的求解结果出现（3）、（4）两种情况时，一般说明线性规划问题建模有错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。

【人教A版】高中数学必修5同步辅导与检测：第三章3.3-3.3.2第2课时简单线性规划的应用(含答案)

第三章 不等式 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

无约束非线性规划求解方法及其实现

无约束非线性规划求解方法及其实现 作者：杨玲指导老师：陈素根 摘要: 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。

关键词最优化共轭梯度法非线性无约束 1 引言 1.1 无约束非线性规划问题是最基本的非线性规划问题，在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。 2 正文 2.1主要介绍无约束非线性规划的相关概念 一个非线性规划问题的自变量x没有任何约束，或说可行域即是整个n维向量空间：n 错误！未找到引用源。,则称 x R

《运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案

第三章线性规划对偶理论与灵敏度分析习题 一、思考题 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第三章3.3-3.3.2第2课时简单线性规划的应用

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万元，假设种植黄瓜和韭菜的产量、成本和售价如下表：

非线性规划模型

非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 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 ≤≤

无约束非线性规划求解方法及其实现--论文

无约束非线性规划求解方法及其实现 摘要: 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。

关键词最优化共轭梯度法非线性无约束 1 引言 1.1 无约束非线性规划问题是最基本的非线性规划问题，在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。 2 正文 2.1主要介绍无约束非线性规划的相关概念 一个非线性规划问题的自变量x没有任何约束，或说可行域即是整个n维向量空间：n 错误！未找到引用源。,则称 x R