案例选讲课件_1_非线性规划

1、第五讲第五讲非线性规划非线性规划5.1 引言引言 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题。 与线性规划一样，非线性规划也是运筹学的一个重要分支，于 20 世纪 50 年代开始逐步形成，到20 世纪 70 年代开始处于兴旺发展时期。随着计算机技术的日益发展，很多领域越来越重视这门学科，应用非线性规划方法进行设计、管理等，非线性规划理论自身也得到了进一步的发展。 与线性规划问题不同，非线性规划问题可以有约束条件，也可以没有约束条件。 但无论如何，非线性规划总可以用如下的一般形式一般形式来描述： min f (x) s.t. gi(x) 0，i

2、 = 1, , m (5.1.1) hj(x) = 0，j = 1, , l其中 x = (x1, x2, , xn)TRn，f，g，h 是定义在 Rn 上的实值函数。 如果采用向量表示法，则线性规划的一般形式可以写成： min f (x) s.t. g(x) 0 h(x) = 0其中：g(x) = (g1(x), , gm(x)T h(x) = (h1(x), , hl(x)T 至于求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式。 5.2 引例引例 引例引例 5.2.1 (项目投资问题)有一投资者有资金 5000 美元和两个可能的投资项目，令 xj(j =

3、 1, 2)表示他分配到投资项目 j 的资金(以千美元为单位)。从历史资料分析，投资项目 1 和 2 分别有预计的年收益 20% 和 16%，同时与项目 1 和 2 有关的总的风险损失由总收益的方差来衡量，由式 2x12 + x22 + (x1.+ x2)2 给出，即风险损失随着总投资和单项投资的增加而增加。投资者希望使期望的收益为最大，同时使风险损失为最小，应怎样进行投资？ 建立模型：max Z = 20 x1 + 16x2 2x12 + x22 + (x1 + x2)2 s.t. x1 + x2 5 x1, x2 0其中，非负常数 反映风险损失和收益之间的权衡。 当 = 0 时，他将资金全

4、部投到最大期望收益的项目，属冒险型； 当 时，期望回收的目标收益可以忽略不计，他主要考虑使风险损失为最小。 引例引例 5.2.2 (生产计划问题)Carron(卡隆)化学公司年轻工程师 R 和 D 合成了一种轰动一时的新肥料，只用两种可互相替换的基本原料来制造。公司想利用这个机会生产尽可能多的这种新肥料，公司目前有资金 40000 美元，可购买单价分别为 8000 美元和 5000 美元的原料。当用数量为 x1 和 x2 两种原料合成时，肥料的数量 Q 由下式给出：Q = 4x1 + 2x2 0.5x12 0.25x22 试确定购买原料的计划。 建立模型： max Q = 4x1 + 2x2

5、0.5x12 0.25x22 s.t. 8x1 + 5x2 40 x1, x2 0 引例引例 5.2.3 (供应与选址问题)某公司有 6 个建筑工地要开工，每个工地的位置(用平面坐标系 (ai, bi) 表示，距离单位：千米)及水泥日用量 d(吨)由下表给出。目前有两个临时料场位于 A(5, 1)，B(2, 7)，日储量各有 20 吨。假设从料场到工地之间均有直线道路相连。123456ai1.258.750.55.7537.25bi1.250.754.7556.57.25d3547611 (1) 试制定每天的供应计划，即从 A、B 两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 (2)

6、 为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为 20吨，问应建在何处，节省的吨千米数有多大？ 建立模型：记工地的位置为 (ai, bi)，水泥日用量为 di，i = 1, , 6；料场位置为 (xj, yj)，日储量为 ej，j = 1, 2；从料场 j 向工地 i 的运送量为 Xij。于是216122)()(minjiijijijbyaxXf2 , 1 ,6 , , 2 , 1 ,6121jeXidXjiijijij 当使用临时料场时，决策变量为：Xij(此时，x1 = 5，x2 = 2，y1 = 1，y2 = 7)； 当不使用临时料场时，决策变量为：Xij，xj，

7、yj。5.3 非线性规划问题的求解非线性规划问题的求解 尽管非线性规划也有相当丰富的求解方法，但远不如线性规划那样具有高效、通用的解法。 一般来说，求解非线性规划问题要比求解线性规划问题困难的多，目前还没有适合于各种问题的一般算法，各个算法都有一定的局限性。 定义定义 5.3.1 记非线性规划问题的可行域为 K。 (1) 若 x*K，且对于 xK，都有f (x*) f (x)则称 x* 是非线性规划的全局最优解全局最优解，f (x*) 是其全局最优值全局最优值。如果对 xK，x x*，都有 f (x*) f (x)则称 x* 是非线性规划的严格全局最优解严格全局最优解，f (x*) 是其严格全

8、局最优值严格全局最优值。 (2) 若 x*K，且存在 x* 的邻域 N (x*)，对于 xN (x*)K，都有f (x*) f (x)则称 x* 是非线性规划的局部最优解局部最优解，f (x*) 是其局部最优值局部最优值。如果对 xN (x*)K，x x*，都有 f (x*) 0(正定)而 x0 是 f (x) 极大点的充分条件为f (x0) = 0，2f (x0) 0(负定) 事实上事实上，如果设 x = (x1, , xn)T，则利用多元函数的泰勒展开式，我们有其中 R 为 x 的高阶无穷小，即 R = o| x |2。Rxxfxxxfxfxxf)(! 21 )()()(02TT000 于

9、是，当 x0 为函数 f (x) 的驻点时可以得到即：当 xi(i = 1, , n)足够小时，上式右端的正负号完全由二次型 xT2f (x0)x 决定，从而完全由 Hessian 矩阵 2f (x) 的正(负)定性决定。 注记注记：微积分中求一元函数和二元函数极值的方法，是这个定理的特例。Rxxfxxfxxf)(! 21)()(02T00 5.3.2 无约束优化的梯度下降法无约束优化的梯度下降法 对于无约束优化问题min f (x) (1) x = (x1, x2, , xn)TRn如果 f (x) 可微，根据古典分析的方法，可利用f (x) = 0 (2)求驻点，然后再利用 Hessian

10、 矩阵 2f (x) 来判定这些驻点是否极小值点，从而求出无约束优化问题(1)的最优解。 但是，用古典分析的方法求解无约束优化问题(1)实际上是行不通的，这是由于： (1) 实际应用中相当数量的函数 f.(x) 不具有解析性，故非线性方程组 f (x) = 0 无法形成； (2) 即使形成了方程组 f (x) = 0，由于它是一个 n 元非线性方程组，因而求它的解与解决原问题一样地困难； (3) 即使求得了 f (x) = 0 的解 x*，但由于最优性条件不被满足或者难于验证，因此仍无法确定 x* 是否为(1)的解。 例如，有些曲面有许多甚至无穷多极大值和极小值，则无法验证最优性条件。 鉴于上

11、述种种原因，对于(1)的求解，通常采用一些比较切合实际、行之有效的数值算法。最常用的是迭代算法(搜索算法)。 迭代算法迭代算法的基本思想是：从一个选定的初始点 x0Rn 出发，按照某一特定的迭代规则产生一个点列 xk，使得当 xk 是有穷点列时，其最后一个点是(1)的最优解；当 xk 是无穷点列时，它有极限点，并且其极限点是(1)的最优解。 设 xkRn 是某迭代算法的第 k 轮迭代点，而 xk+1Rn 是第 k +1 轮迭代点，记xk+1 = xk + k pk这里 kR 称为步长步长，pkRn 称为搜索方向搜索方向。在 k 和 pk 确定之后，由 xkRn 就可以确定 xk+1Rn。 各种

12、不同迭代算法的差别，在于选择 k 和 pk(特别是 pk)的方法不同。 使用最广泛的一类是下降算法下降算法，它每迭代一次都使目标函数值有所下降，即 f (xk+1) 0，并令 k: = 0； 2 计算 pk = f (xk)； 3 检验是否满足收敛性判别准则：| pk | 若满足判别准则，则停止迭代，得到点 x* xk，否则进行 4； 4 单变量极值问题的最优解 kR： 5 令xk+1 = xk + k pk；k: = k + 1返回 2。)()(min0kkkkkpxfpxf 例例 用梯度下降法求解 min f (x) = 2x12 + x22。 解解 (1) 取初始点 x0 = (1, 1

13、)T，并设定允许误差 = 0.05。计算得 p0 = f (x0) = (4x01, 2x02)|x1 = 1, x2 = 1 = (4, 2)T 由于 | p0 | = 0.05 = ，则 x0 不能为近似最优解。 因此，需要考虑最优步长 0。20 令 代入 f (x) = 2x12 + x22，则 f (x0 + p0) = 2(1 4)2 + (1 2)2。 再求解单变量极值问题：得 0 = 5/18，于是：x1 = x0 + 0 p0 = (1/9, 4/9)T。214100px)(min000pxf (2) 计算得 p1 = f (x1) = (4x11 2x12)|x11 = 1/

14、9, x12 = 4/9 = (4/9, 8/9)T 由于 | p1 | = 0.05 = ，则 x1 不能为近似最优解。 因此，需要考虑最优步长 1。 令84419111px9/20故再求解单变量极值问题：得 1 = 5/12，于是x2 = x1 + 1 p1 = (2/27, 2/27)T (3) 计算得 p2 = f (x2) = (8/27, 4/27)，. 如此继续下去，直到满足收敛准则为止。22119849412)(pxf)(min110pxf 该问题的最优解为 x* = (0, 0)T，f.(x*) = 0，如图所示。-10-50510-10-505100501001502002

15、50300 梯度下降法是求解无约束优化问题的最基本的算法，它在最优化方法中占有重要地位。 梯度下降法的优点是计算量小，存储变量少，对初始点要求不高。但缺点是： (1) f (x) 仅仅反映了函数在点 x 处的局部性质，对局部来说是最速的下降方向，但对整体求解过程并不一定使函数值下降的最快。 (2) 梯度下降法对初值比较敏感，算法将会在很大的程度上被初始点的选择影响而陷入局部最小点。 (3) 在梯度下降法的在开头几步，目标函数下降较快，但在接近极小点时，收敛速度就不理想了。特别是当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。 因此，梯度下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极

16、值点时宜选用其它收敛快的算法。 5.3.3 非线性规划的罚函数法非线性规划的罚函数法 实际应用中，绝大多数优化问题都是有约束的问题。线性规划已有单纯形法这一通用解法，但非线性规划目前还没有适合于各种问题的一般算法，各个算法都有特定的适用范围，带有一定的局限性。 非线性规划问题是一类有约束的优化问题，其一般形式如下：min f (x) (3) s.t. gi(x) 0, i = 1, 2, , m hj(x) = 0, j = 1, 2, , l x = (x1, x2, , xn)TRn 求解时除了要使目标函数在每次迭代时有所下降，还要时刻注意解的可行性问题，这就给寻优工作带来很大困难。 求解

17、非线性规划问题的常见方法为： 将约束问题转化为无约束问题 将非线性规划问题转化为线性规划问题 将复杂问题转化为较简单的问题 在此，我们仅介绍将约束问题转化为无约束问题的求解方法。 首先考虑等式约束问题：min f (x) (4) s.t. hj(x) = 0, j = 1, 2, , l x = (x1, x2, , xn)TRn 对于问题(4)，有如下的 Lagrange 定理。 定理定理 (Lagrange 定理)设 f , hj(j = 1, 2, , l)在可行点 x* 的某个邻域 N(x*, ) 内可微，向量组hj(x*) 线性无关；令L(x, ) = f (x) TH(x)其中 =

18、 (1, , l)TRn，H(x) = (h1(x), , hl(x)。 如果 x* 是问题(4)的局部最优解，则存在实向量 * = (1*, , l*)T，使得 L(x*, *) = 0，即0*)(*)(1*ljjjxhxf 显然，Lagrange 定理的意义在于能将问题(4)的求解转化为无约束问题的求解。 然而，对于一般的非线性规划问题(3)，则无法直接应用 Lagrange 定理将约束问题转化为无约束问题。为此，人们引入了求解一般非线性规划问题的罚函数法罚函数法。 罚函数法的基本思想是：利用问题(3)的目标函数和约束函数构造出带参数的所谓增广目增广目标函数标函数，从而把约束非线形规划问题

19、转化为一系列无约束非线形规划问题来求解。 增广目标函数由两个部分构成，一部分是原问题的目标函数，另一部分是由约束函数构造出的“惩罚”项，“惩罚”项的作用是对“违规”的点进行“惩罚”。 罚函数法主要有两种形式。 一种称为外部罚函数法，或称外点法外点法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近。 另一种称为内部罚函数法，或称内点法内点法，它从满足约束条件的可行域的内点开始迭代，并对企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大，从而保证迭代点的可行性。 外点法的具体操作方式为：根据不等式约束 gi(x)

20、 0 与等式约束 min0, gi(x) = 0 的等价性，构造增广目标函数(也称为罚函数罚函数)：从而将问题(3)转化为无约束问题： min T(x, M) x = (x1, x2, , xn)TRn其中 M 是一个较大的正数。jjjmiixhMxgMxfMxT1212)()(, 0min)(),( 外点法的迭代步骤外点法的迭代步骤 1 给定初始点 x0Rn，取 M1 0， 1(如取 = 10)，给定允许误差 0，并令 k: = 1； 2 求无约束优化问题 min T(x, Mk)，x = (x1, x2, , xn)TRn的最优解 xk = x(Mk)； 3 若存在 i(1 i m)，使得

21、 gi(xk) ，则取 Mk+1 = Mk，令 k: = k + 1，返回 2；否则，停止迭代，得最优解 x* xk。 注记：上述算法第三步中 gi(xk) 的含义为：当取定 0 M1 M2 Mk 0(如取 r1 = 1)，0 0； 2 求可行域 D 的一个内点 x0D0(其中 D0 = x | gi(x) 0 为可行域中所有严格内点的集合)，令 k: = 1； 3 求无约束优化问题 min I(x, rk)，x = (x1, x2, , xn)TRn的最优解 xk = x(rk)； 4 检验是否满足判别准则或者若满足，则停止迭代，得最优解 x* xk；否则取 rk+1 = rk，令 k: =

22、 k + 1，返回 3。mikikxgr1)(lnmikikxgr1)(1 注记：上述算法第四步中判别准则的含义为：当取定 r1 r2 rk 0 以后，相应于 min I(x, rk) 的最优解 xk 都在可行域 D 内。这也是内点法这一名称的缘由。 内点法的优点是每步迭代得到的最优解都在可行域 D 内，故易得较好的近似最优解；而缺点则是：在求解一系列无约束优化问题过程中，计算代价太大。 附：内点的求法附：内点的求法 在内点法中，要求内点集合D0 = x | gi(x) 0, i = 1, 2, , m 方法可行的最起码的条件，而且迭代过程必须由内点开始。实际操作中，如果内点不是凭直观可用找出

23、时，则需要用迭代方法找出初始内点。这里给出的方法也是基于内点法的思想。 迭代步骤迭代步骤 1 任取一点 x0Rn，取 r1 0(如取 r1 = 1)，令 k: = 0； 2 定出指标集 Sk 和 Tk：Sk = i | gi(xk) 0, 1 i mTk = i | gi(xk) 0, 1 i m 3 检验集合 Sk 是否为空集。若 Sk = ，则 xkR0，迭代停止；否则，转到 4； 4 以 xk 为初始点，在保持对集合Rk = x | gi(x) 0, iTk可行性的情况下，求 min Vk+1(x) 的最优解 xk+1，其中转到 5； 5 令 rk+2 满足 0 rk+2 rk+1(例如

24、取 rk+2 = rk+1/10)，令 k: = k + 1，转到 2。0 ,)(1)()(111kTiikSiikrxgrxgxVkk 5.3.4 用用 Matlab 解非线性规划解非线性规划 在 Matlab 的优化工具箱中，给出了几个求解非线性规划的函数： 详细内容参加课件：基于 MATLAB 优化工具箱的优化计算一元函数极小值 X = fminbnd(F,x1,x2)无约束极小值 X = fminunc(F,X0) X = fminsearch(F,X0)约束极小值(非线性规划) X = fmincon(FG,X0)非线性最小二乘 X = lsqnonlin(F,X0)5.4 二次规划

25、模型及其求解二次规划模型及其求解 在非线性规划问题中，有一类特殊形式：二次规划二次规划。 二次规划问题是指二次目标函数达到极大(或极小)，且满足各项线性约束的优化问题。 二次规划问题与线性规划问题的区别只在于目标函数还含有 xj2 和 xjxk(j k)等二次项。 设 xi(i = 1, 2, , n)为二次规划问题的决策变量，令 x = (x1, , xn)T，则任意一个二次规划问题都可以转化成如下的标准形式： min Z = 0.5xTHx + CTx s.t. Ax b x 0 二次规划可以直接利用 Matlab 来求解。Matlab 中二次规划函数为：quadprog( )。 例 5.

26、5.1 求解下面的二次规划问题 max Q = x1 + 2x2 0.5x12 0.5x22 s.t. 2x1 + 3x2 6 x1 + 4x2 5 x1, x2 0 解：(1) 首先将问题转化为标准形式： min Z = 0.5xTHx + f Tx s.t. Ax b x 0其中 (2) 利用 Matlab 可求得最优解为：x* = (0.7647, 1.0588)T，最优值为：z* = 2.0294。 56 ,4312 ,21 ,1001 ,21bAfHxxx5.5 范例范例原油采购与加工原油采购与加工：某公司用两种原油(A 和 B)混合加工成两种汽油(甲和乙)。甲、乙两种汽油含原油 A

27、 的最低比例分别为 50% 和 60%，每吨售价分别为 4800 元和 5600 元。该公司现有原油 A 和 B 的库存量分别为 500 吨和 1000 吨，还可以从市场上买到不超过 1500 吨的原油 A。原油 A 的市场价为：购买量不超过 500 吨时的单价为 10000 元/吨；购买量超过 500 吨但不超过 1000 吨时，超过 500 吨的部分单价为 8000 元/吨；购买量超过 1000 吨时，超过 1000 吨的部分单价为 6000 元/吨。该公司应如何安排原油的采购和加工？ 解解：建立模型建立模型 首先考虑决策变量。 设原油 A 用于生产甲、乙两种汽油的数量分别为 x11 和

28、x12，原油 B 用于生产甲、乙两种汽油的数量分别为 x21 和 x22，原油 A 的购买量为 x(价格以千元/吨为单位)。 则容易得到目标函数为 Z = 4.8(x11 + x21) + 5.6(x12 + x22) c(x)其中 c(x) 为采购原油 A 的费用。 下面考虑约束条件。 (1) 所有决策变量均非负。 (2) 根据题目所给的数据，采购的支出 c(x) 可表示为如下的分段线性函数(价格以千元/吨为单位)： 15001000,630001000500,810005000,10)(xxxxxxxc (3) 成品油的混合比例限定： (4) 两种原油的总量限定： x11 + x12 50

29、0 + x(原油 A 的总量) x21 + x22 1000(原油 B 的总量) x 1500(原油 A 的采购量) 于是，相应的数学规划模型为：, 5 . 0211111 xxx6 . 0221212 xxx15001000,630001000500,810005000,10)(0 , , , ,6 . 05 . 015001000500s.t. )()(6 . 5)(8 . 4max 222112112212122111112221121122122111xxxxxxxcxxxxxxxxxxxxxxxxxxcxxxxZ其中 模型求解模型求解 由于 c(x) 是分段函数，而是分式，都不是线性

30、函数，因此所建立的模型是一个非线性规划模型。 特别地，对于分段函数 c(x)，即使求解非线性规划的软件也很难输入和求解。因此，为了有效地求解这个模型，必须考虑化简模型。6 . 0 , 5 . 0221212211111xxxxxx 一般来讲，求解非线性规划模型时，优先考虑能否将其中的非线性函数线性化。 在这个模型中，分式和分段函数中出现的决策变量都是一次的，因而将其线性化是有可有可能的能的。 首先，将分式线性化是容易做到的。处理后的模型形式如下：15001000,630001000500,810005000,10)(0 , , , ,06 . 04 . 005 . 05 . 015001000

31、500s.t. )()(6 . 5)(8 . 4max 22211211221222112221121122122111xxxxxxxcxxxxxxxxxxxxxxxxcxxxxZ其中 接下来考虑如何处理 c(x)。 方法一方法一 一个典型的想法是增加决策变量，即将原油的采购量 x 分解为三个量：分别用 x1, x2, x3 表示以价格 10 千元/吨、8 千元/吨、6 千元/吨采购的原油 A 的吨数，则总支出为c(x) = 10 x1 + 8x2 + 6x3，x = x1 + x2 + x3 这时模型简化为如下的非线性规划模型： 0 , , , , , ,500 ,500 ,50006 .

32、04 . 005 . 05 . 01000)(500s.t. )6810()(6 . 5)(8 . 4max32122211211321221222112221321121132122122111xxxxxxxxxxxxxxxxxxxxxxxxxxxxZ? x1 500 x2 = x3 = 0 0 x2 500 x2 = 500 且 x3 = 0 0 0；而约束条件 (x2 500) x3 = 0 的含义为：只有 x2 = 500 时，才有可能 x3 0。 求解上述模型得：x11 = 500，x12 = 0，x21 = 500，x22 = 0，x1 = 0，x2 = 0，x3 = 0。 于是，

33、该公司应该利用库存的 500 吨原油 A 和 500 吨原油 B 生产 1000 吨汽油甲，不购买新的原油 A，此时总利润为 4800000元。 方法二方法二 通过引入 01 变量，将方法一中的约束条件 (x1 500) x2 = 0 和 (x1 500) x2 = 0 转化为线性约束。 令 y1 = 1，y2 = 1，y3 = 1 分别表示以 10 千元/吨、8 千元/吨、6 千元/吨的价格采购原油A，则方法一中给出的模型可以转化为如下的 01 规划模型： 1 , 0 , , , 0 , , , , , ,50050050050050006 . 04 . 005 . 05 . 01000)(

34、500s.t. )6810()(6 . 5)(8 . 4max3213212221121133223112221222112221321121132122122111yyyxxxxxxxyxyxyyxyxxxxxxxxxxxxxxxxxxZ是一个 01 的线性规划模型 求解这个 01 规划模型得： y1 = 1, y2 = 1, y3 = 0 x11 = 0, x12 = 1500, x21 = 0, x22 = 1000 x1 = 500, x2 = 500, x3 = 0 于是，该公司的采购与加工计划应该为：购买 1000 吨原油 A，与库存的 500 吨原油 A 和 1000 吨原油 B

35、 一起，共生产 2500 吨汽油乙，此时总利润为 5000000 元。 这种方案优于非线性规划求得的方案。 方法三方法三 直接处理分段线性函数 c(x)。 记 x 轴上的分点为 b1 = 0，b2 = 500，b3 = 1000，b4 = 1500。当 x 在第 1 个小区间 b1, b2 时，记 x = z1b1 + z2b2，z1 + z2 = 1，z1, z2 0。因为 c(x) 在区间 b1, b2 内是线性的，所以 c(x) = z1c(b1) + z2c(b2)。同样，当 x 在第 2 个小区间 b2, b3 内时，x = z2b2 + z3b3，z2 + z3 = 1，z2, z

36、3 0，c(x) = z2c(b2) + z3c(b3)。当 x 在第 3 个小区间 b3, b4 内时，x = z3b3 + z4b4，z3 + z4 = 1，z3, z4 0，c(x) = z3c(b3) + z4c(b4)。 为了表示 x 在哪个小区间，引入 01 变量yk(k = 1, 2, 3)，当 x 在第 k 个小区间时，yk = 1，否则，yk = 0。这样，z1, z2, z3, z4, y1, y2, y3 应满足 z1 y1，z2 y1 + y2，z3 y2 + y3，z4 y3， z1 + z2 + z3 + z4 = 1，zk 0（k = 1, 2, 3, 4） y1 + y2 + y3 = 1，y1, y2, y30, 1 此时，x 和 c(x) 可以统一地表示为 x = z1b1 + z2b2 + z3b3 + z4b4 = 500