非线性规划的概念和原理.docx

第五章 非线性规划的概念和原理

非线性规划的理论是在线性规划的基础上发展起来的。1951年，库恩（H.W.Kuhn）和塔克（A.W.Tucker）等人提出了非线性规划的最优性条件，为它的发展奠定了基础。以后随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。

一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那

样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。

非线性规划的实例及数学模型

[例题6.1]投资问题：

假定国家的下一个五年计划内用于发展某种工业的总投资为b亿元，可供选择兴建的项

目共有几个。已知第j个项目的投资为a

j

亿元，可得收益为c

j

亿元，问应如何进行投资，

才能使盈利率（即单位投资可得到的收益）为最高？

解：令决策变量为x

j

，则x

j

应满足条件x ?x

j j

?1??0

同时x

j

应满足约束条件?n ax ?b

j j

j?1

?ncx

j j

目标函数是要求盈利率f?x,x

1 2

, ,x??

?n

?

j?1

?n ax

j j

j?1

最大。

[例题6.2]厂址选择问题：

设有n个市场，第j个市场位置为?pj,qj?，它对某种货物的需要量为bj?j?1,2,?,n?。现计划建立m个仓库，第i个仓库的存储容量为ai?i?1,2,?,m?。试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。

解：设第i个仓库的位置为?xi,yi??i?1,2,?,m?，第i个仓库到第j个市场的货物供应量为zij?i?1,2,?,m,j?1,2,?,n?，则第i个仓库到第j个市场的距离为

目标函数为

?m?n

d

ij

z d

ij ij

?

?xp?2??yq

?x

p

?2??y

q

?2

i

j

i

j

?x

p

?2??y

q

?2

i

j

i

j

ij

约束条件为：

i?1j?1

i?1

j?1

每个仓库向各市场提供的货物量之和不能超过它的存储容量；

每个市场从各仓库得到的货物量之和应等于它的需要量；

运输量不能为负数。因此，问题的数学模型为：

min?m

i?1

?n z

?x

?x

p

?2??y

q

?2

i

j

i

j

j?1

s.t. ?n

j?1

z ?a,?i?1,2,?,m?

ij i

?m

i?1

z ?b

ij

,?j?1,2,?,n?

j

z ?0,?i?1,2,?,m,j?1,2,?,n?

ij

一般非线性规划的数学模型可表示为：

minf?x?；

s.t. g?X??0 ?i?1,2,?,m?,

i

h?X??0,?j?1,2,?,l?

j

?式中X??x,x, ,x?T

?

1 2 n

?Rn是n维向量，f,g ?i?1,2, ,m?，h

?i j

?

?j?1,2,?,l?都是

Rn?R1的映射（即自变量是n维向量，因变量是实数的函数关系），且其中至少存在一个

非线性映射。

与线性规划类似，把满足约束条件的解称为可行解。若记

???X g?X??0,i?1,2,?,m,h?X??0,j?1,2,?,l?

i j

则称?为可行域。因此上述模型可简记为

min f?X?

s.t. X??

当一个非线性规划问题的自变量X没有任何约束，或说可行域即是整个n维向量空间,

即??Rn，则称这样的非线性规划问题为无约束问题：

min f?X?或min f

X?Rn

?X?

有约束问题与无约束问题是非线性规划的两大类问题，它们在处理方法上有明显的不同。

无约束非线性规划问题

5.2.1无约束极值条件

对于二阶可微的一元函数f?x?，如果x?是局部极小点，则f?