1. 非线性规划我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。

如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。

在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。

由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。

非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年H.W.库恩和A.W.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。

非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。

无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。

关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。

总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。

求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。

虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。

1.1 非线性规划举例[库存管理问题] 考虑首都名酒专卖商店关于啤酒库存的年管理策略。

假设该商店啤酒的年销售量为A 箱,每箱啤酒的平均库存成本为H 元,每次订货成本都为F 元。

如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。

我们以Q 表示每次定货数量,那么年定货次数可以为Q A ,年订货成本为QAF ⨯。

由于平均库存量为2Q ,所以,年持有成本为2QH ⨯,年库存成本可以表示为: Q HQ A F Q C ⨯+⨯=2)( 将它表示为数学规划问题:min Q H Q A F Q C ⋅+⋅=2)( ..t s 0≥Q其中Q 为决策变量,因为目标函数是非线性的,约束条件是非负约束,所以这是带约束条件的非线性规划问题。

[数据拟合问题] 假设一年期国债利率在市场中的波动符合下述模型εααα+++=---332211n n n n R R R R其中n R 表示一年期国债利率在周期n 开始时的利率,误差ε服从),0(2σN 。

利率的历史观察数据为:表1.9:一年期国债利率历史样本数据 1 23456789101112134.28 4.14 3.85 4.07 4.18 4.66 4.51 4.54 4.59 4.48 4.47 4.47 4.72利用最小二乘法估算3,2,1,=i i α由于在周期t 回归误差的平方为 23322112)(---++-=t t t t t R R R R e ααα,N t ,...5,4=比如说,当4=t 时,232124)28.414.485.307.4(ααα++-=e总回归误差为∑==Nt t e e 422我们需要求解下述数学规划问题:min ∑=---++-=Nt t t t t R R R R e 423322112)(ααα..t s 3,2,1),,(=+∞-∞∈i i α其中i α3,2,1,=i 为决策变量,显然,这是无约束非线性规划问题。

[投资组合管理问题] 假设首都基金管理公司拥有大批量股票S ,并且希望在未来的N 天中将其全部卖出。

股票S 在未来N 天的总期望价值为:∑==Nt t t q p S V 1)(其中,N t q t ,...,2,1,=是基金公司在第t 日卖出股票S 的数量,N t p t ,...,2,1,=是在t 日股票S 的平均价格。

同时,我们假设价格t p 具有下述动态特性:N t q p p t t t ,...,2,1,1=⋅+=-α那么基金管理公司应当如何确定股票S 每日卖出数量?很显然,不同的卖出方案,基金管理公司获得的收益是不同的。

所以目标函数是最大化股票S 的总期望价值。

约束条件为N 日内卖出数量之和应当等于总持有量S ,价格动态特征,以及每日卖出数量大于等于零。

我们可以把它表示为最优化问题:max ∑==Nt t t q p S V 1)(..t s ⎪⎪⎩⎪⎪⎨⎧=≥=+==-=∑N t q N t q p p S q t t t t Nt t ,...,2,1,0,...,3,2,11α其中t q ,N t ,...,2,1=,这是目标函数为非线性函数,约束条件是线性等式约束条件的非线性规划问题。

[生产管理问题] 首都电器制造厂生产二款电视机,A 和B 。

已知电视机A 每月最大的销售量为500台,电视机B 每月的最大销售量为400台。

工厂采用随销售量增加而递减销售价格的定价方式对电视机进行定价,那么单台电视机的利润是随着销售量的增加而递减。

我们分别以A X 和B X 表示电视机A 和B 的月销售量,那么电视机A 的销售收入可以表示为:2)150(300A A X X -它说明第一部A 型电视机的利润为300元,最后一部(第500)A 型电视机的利润为150元。

电视机B 的销售收入可以表示为:2)400100(200B B X X -电视机的生产受到下下述条件限制:)1(装配工时限制:每月最多可供使用的工时是1200小时,而装配一台电视机A 需要2工时,装配一台电视机B 需要1工时。

)2( 机器加工能力限制:每日最多可供使用的机时是1350小时,加工一台电视机A 需要1机时,加工一台电视机B 需要3机时。

那么,如何决定每种电视机的月产量,使月销售收入最大。

如果我们以二款电视机的月销售收入之和作为目标函数,则电视机生产管理的最优化问题被表示为:max 2225.02003.0300B B A A X X X X S -+-=..t s ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≤+≤+0,4005001350312002B A B A B A B A X X X X X X X X 这是目标函数为二次可分离函数,约束条件为线性不等式的非线性规划问题。

1.2 非线性规划模型现在,我们非线性规划问题的应用进行归纳,建立非线性规划通用数学模型。

非线性规划的数学模型可表示为:)(min x f Xx ∈)1.1(其中:R R f n→:是具有n 个自变量的连续(通常存在一阶导数)函数;nR X ⊆,是nR 的子集合。

通常称X 为非线性规划问题)1.1(的可行域,如果nR X =,则非线性规划问题)1.1(就变为无约束条件的非线性规划问题;如果nR X ⊂,则非线性规划问题)1.1(为带约束非线性规划问题。

如果点X x ∈,则称x 为可行点。

称)(x f 为非线性规划问题)1.1(的目标函数,使)(x f 在可行域X 上达到最小值的点*x 为最优解(极小点),对应的目标函数值)(*x f 为最优值(极小值)。

如果)(x f 是线性函数并且X 是n 维空间中的单纯形,非线性规划)1.1(就变成了线性规划问题。

我们通常将非线性规划和线性规划区别对待,非线性规划的求解方法比线性规划复杂许多。

为了方便讨论,我们定义带约束条件的非线性规划的标准模型如下:min )(x f..t s .,...,2,1,0)(,...,2,1,0)(⎩⎨⎧=≤==sj x g mi x h j i )2.1(其中:R R h n i →:和R R g nj →:都是连续,可导函数。

第一组约束,m i x h i ,...,2,1),(=称为等式约束;第二组约束,s j x g j ,...,2,1),(=称为不等式约束。

非线性规划模型)2.1(的可行域可以表示为:},...,2,1,0)(,,...,2,1,0)(|{s j x g m i x h R x X j i n =≥==∈=∶不难看出,带约束非线性规划模型)2.1(的可行域是nR 的子集合,所以它也是非线性规划模型)1.1(的一个特例。

我们将根据非线性规划的标准模型)1.1(,给出非线性规划解的定义。

[定义1.1] 设X x ∈*,nR X ⊆,R R f n→:)1( 如果X x ∈*,并且存在*x 的邻域}0,||:||{)(**≥≤-∈=δδx x R x x N n 使得:)()(*x f x f ≤ )(*x N X x ⋂∈∀则*x 是非线性规划)1.1(的局部最优解或局部极小点,称)(*x f 是非线性规划)1.1(的局部最优值或局部极小值。

)2( 如果X x ∈*,并且存在*x 的邻域}0,||:||{)(**≥≤-∈=δδx x R x x N n 使得:)()(*x f x f < }{))((**x ＼x N X x ⋂∈∀则*x 是非线性规划)1.1(的严格局部最优解或严格局部极小点,称)(*x f 是非线性规划)1.1(的严格局部最优值或严格局部极小值。

[定义1.2] 设X x ∈*,nR X ⊆,R R f n→:)1( 如果X x ∈*,使得:)()(*x f x f ≤ X x ∈∀,则*x 是非线性规划)1.1(的全局最优解或全局极小点,称)(*x f 是非线性规划)1.1(的全局最优值或全局极小值。

)2( 如果X x ∈*,使得:)()(*x f x f ≤ X x ∈∀,则*x 是非线性规划)1.1(的严格全局最优解或严格全局极小点,称)(*x f 是非线性规划)1.1(的严格全局最优值或严格全局极小值。

图)1.1(从几何上说明了局部极小点,严格局部极小点,和严格全局极小点之间的关系。

严格局部极小点 局部极小点 严格全局极小点图)1.1(可以看出,对于非线性规划)1.1(,局部或严格局部极小点不是全局或严格全局极小点,反之全局或严格全局极小点一定是局部或严格局部极小点。

对于只有两个决策变量的非线性规划问题,我们可以通过图解法进行求解。

考虑下述带等式约束的非线性规划问题:min 21)(x x x f +=..t s 022221=-+x x)3.1(其可行域X 是以原点为中心,半径等于2的圆周长上的所有点,见图)2.1(:图)2.1(显然,由于非线性规划)3.1(的目标函数是直线,与可行域X 的最小相交点为)1,1(*--=x ,它是非线性规划)3.1(的全局最优解,全局最优值为2)(*-=x f 。

再考虑下述带等式约束的非线性规划问题:max 21)(x x x f =..t s 221=+x x)4.1(显然,非线性规划)4.1(的可行域X 是连接点)0,2(和点)2,0(直线上的所有点,参见图)3.1(:图)3.1(非线性规划)4.1(的目标函数与可行域X 的交点为)1,1(*=x ,它是非线性规划)4.1(的全局最优解,全局最优值为1)(*=x f 。