4.非线性规划 非线性规划建模—引例 非线性规划模型、基本概念、性质 非线性规划重要算法 用MATLAB解无约束规划
4. 非线性规划 非线性规划建模——引例 非线性规划模型、基本概念、性质 非线性规划重要算法 用MATLAB解无约束规划
引例：供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系， b表示，距离单位：千米)及水泥日用量d(吨)由下表给出。目前有 两个临时料场位于A(⑤，1)，B(2,7),日储量各有20吨。假设从料场 到工地之间均有直线道路相连。 (1)试制定每天的供应计划，即从A,B两料场分别向各工地运 送多少吨水泥，使总的吨千米数最小。 (2)为了进一步减少吨千米数，打算舍弃两个临时料场，改建 两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多 大？ 工地位置(a,b)及水泥日用量w 需点 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.75 w(吨) 3 5
引例： 供应与选址 某公司有6个建筑工地要开工，每个工地的位置(用平面坐标系a， b表示，距离单位：千米 )及水泥日用量d(吨)由下表给出。目前有 两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场 到工地之间均有直线道路相连。 (1) 试制定每天的供应计划，即从A，B两料场分别向各工地运 送多少吨水泥，使总的吨千米数最小。 (2) 为了进一步减少吨千米数，打算舍弃两个临时料场，改建 两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多 大？ 需点 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.75 w(吨) 3 5 4 7 6 11 工地位置(a，b)及水泥日用量w
()的求解：记工地的位置为(4，b),水泥日用量为w =1,,6;料场位置为(c,d),日储量为e,户1,2；从料场j向工 地的运送量为x 目标函数为： minf=∑∑xVc,-a,)2+(d,-b,)2 i=1 i=1 约束条件为： ∑x=d,i=12,…,6 ∑8y≤e,j=1,2 x≥0，i=1,2,…,6;j=1,2. 这是一个线性规划，代入已知数据可方便求解问题(1)； 这也是一个运输问题，也可计算运费之后列出运输表来求 解问题(1)；
(1)的求解： 记工地的位置为(ai，bi )，水泥日用量为wi , i=1,…,6; 料场位置为(cj，dj ), 日储量为ej，j=1,2; 从料场j向工 地i的运送量为xij. 目标函数为： = = = − + − 2 1 6 1 2 2 min ( ) ( ) j i i j j ai d j bi f x c 约束条件为： 0, 1,2, ,6; 1,2. , 1,2 , 1,2, ,6 6 1 2 1 = = = = = = = x i j x e j x d i i j j i i j i j i j 这是一个线性规划, 代入已知数据可方便求解问题(1); 这也是一个运输问题, 也可计算运费之后列出运输表来求 解问题(1);
(2)的模型记工地的位置为(4，b),水泥日用量为w i=1,,6;料场位置为(G,,日储量为e广广1,2；从料 场向工地的运送量为x 此时未知变量为x和 C1,C2,d1,d2: 目标函数为： mimf=∑∑xjV(c,-a)2+(d,-b,)2 i=1 i=1 约束条件为： ∑y=d,i=1,2,…,6 ∑，，≤e,j=1,2 x≥0，i=1,2,…,6;i=1,2. 这是一个非线性规划问题 线性约束的非线性规划问题！
(2)的模型 记工地的位置为(ai，bi )，水泥日用量为wi , i=1,…,6; 料场位置为(cj，dj ), 日储量为ej，j=1,2; 从料 场j向工地i的运送量为xij.——此时未知变量为xij和 c1 ,c2 ,d1 ,d2 ! 目标函数为： = = = − + − 2 1 6 1 2 2 min ( ) ( ) j i i j j ai d j bi f x c 约束条件为： 0, 1,2, ,6; 1,2. , 1,2 , 1,2, ,6 6 1 2 1 = = = = = = = x i j x e j x d i i j j i i j i j i j 这是一个非线性规划问题——线性约束的非线性规划问题！
非线性规划的基本概念 定义如果目标函数或约束条件中至少有一个是非线性 函数时的最优化问题就叫做非线性规划问题. 一般形式： min f(x) X∈R" g(x)s0 i=1,2,,m; s 1h(X)=0j=1,2,,l. 其中X=(化1，x2,,xny∈R,函数f,8,h,满足 FR”→R, 8:R”-→R,h:R"→R 其它情况：求目标函数的最大值或约束条件为小于等 于零的情况，都可通过取其相反数化为上述一般形式
定义 如果目标函数或约束条件中至少有一个是非线性 函数时的最优化问题就叫做非线性规划问题． 非线性规划的基本概念 一般形式: f (X ) n XR min( ) ( ) = = = 0 1,2,..., . 0 1,2,..., ; . . h X j l g X i m s t j i ( , , , ) , 1 2 T n 其中X = x x xn R 函 数f , gi ,hj 满 足 f: R R, g : R R, h : R R n j n i n → → → 其它情况: 求目标函数的最大值或约束条件为小于等 于零的情况，都可通过取其相反数化为上述一般形式．
定义1把满足问题(1)中条件的解X∈R称为可行解（或可行点）， 所有可行点的集合称为可行集（或可行域）.记为D.即： D=xIg;(X)s0,h(X)=0,XER" 问题（①可简记为mimf(x) XED 定义2局部极小值点（局部最优解）； 严格局部极小值点（严格局部最优解） 全局极小值点（全局最优解） 严格全局极小值点（严格全局最优解） 注记：当fg是凸函数而是线性函数时，局部最优为全局 最优。 关键字：Lagrange函数，K一T条件 返回
( ) ( ) n D = X | gi X 0, hj X = 0, X R f (X ) XD min 返回 定义1 把满足问题(1)中条件的解X∈Rn称为可行解(或可行点)， 所有可行点的集合称为可行集(或可行域)．记为D．即: 问题(1)可简记为 定义2 局部极小值点(局部最优解); 严格局部极小值点(严格局部最优解). 全局极小值点(全局最优解) 严格全局极小值点(严格全局最优解). 注记：当f，gi是凸函数而hj是线性函数时，局部最优为全局 最优。 关键字：Lagrange函数，K－T条件
特殊非线性规划：一二次规划 x'Hx c'x 2 s.t.A·x≤b Aeq·x=beg V≤x≤UU 二次规划有成熟的求解算法，特别当H正定或半正定时 这时目标函数为凸函数)，可得到全局最优解！ 二次规划有着非常广泛的应用！
特殊非线性规划:——二次规划 V x U Aeq x beq s t A x b x Hx c x = + . . 2 1 min 二次规划有成熟的求解算法，特别当H正定或半正定时 (这时目标函数为凸函数)，可得到全局最优解！ 二次规划有着非常广泛的应用!
基本求解方法： (1)罚函数法一 内点法/外点法 minf(x） (2)序列线性规划法 g:(x)20 (3)序列二次规划法 s.t. h,(x)=0 (4)信赖域算法 外点法一迭代求解如下无约束规划： T(K,M)=f(x)+M之Lmim(o,g(x+M∑L,(x) {M}为单调递增趋于+o的数列如M+1=10M)} 缺点：每次迭代得到的解往往是不可行的！ 对没有等式约束的问题，可采用内点法： )=w+2as6)rx-/+2g冈 i=1 r单调递减趋O(如rk+1=Brk,0<B<1)” 缺点：不适用于等式约束问题！
基本求解方法： (1)罚函数法——内点法/外点法 (2)序列线性规划法 (3)序列二次规划法 (4)信赖域算法 ( ) ( ) ( ( )) ( ) = = = + + l j k j m i T X Mk f X Mk gi X M h X 1 2 1 2 , min 0, ( ) ( ) ( ) ( ) = = = + = + m i i k k m i k k i g X I X r f X r g X I X r f X r 1 1 1 , ln or ( , ) ( ) ( ) ( ) ( ) = 0 0 . . min h X g X s t f X j i ( 10 )! Mk 为单调递增趋于+ 的数列如Mk+1 = Mk 对没有等式约束的问题，可采用内点法： 外点法——迭代求解如下无约束规划： 缺点：每次迭代得到的解往往是不可行的！ 缺点：不适用于等式约束问题！ 0( ,0 1)! rk 单调递减趋于 如rk+1 = rk
基本求解方法： (1)罚函数法 —内点法/外点法 min f() (2)序列线性规划法 [g:(X)≥0 (3)序列二次规划法 s.t. h,(x)=0 (4)信赖域算法 序列线性规划法 每次求解一个近似线性规划： min f(x)=f(x)+vf(x(x-x) g,(X)≈g(X)+Vg:（X*y(X-X)20i=1,,m n,(X)≈，(X)+Vh,(Xy(X-)=0j=1,…,l X-X≤6k δ.一一步长限制需进行适当更新
基本求解方法： (1)罚函数法——内点法/外点法 (2)序列线性规划法 (3)序列二次规划法 (4)信赖域算法 ( ) ( ) ( ) ( ) k T k k min f X f X + f X X − X g (X ) g (X ) g (X ) (X X ) i m k T k i k i i + − 0 = 1, , h (X) h (X ) h (X ) (X X ) j l k T k j k j j + − = 0 = 1,, ( ) ( ) ( ) = 0 0 . . min h X g X s t f X j i 序列线性规划法——每次求解一个近似线性规划： X − Xk k — —步长限制(需进行适当更新) k
基本求解方法： (1)罚函数法一内点法/外点法 min f() (2)序列线性规划法 [g(x)≥0 (3)序列二次规划法 s.t. h,(x)=0 (4)信赖域算法 序列二次规划法 每次求解一个近似二次规划： minf)≈fx+fxya+a'Bd g:(X)≈g,（K)+Vg.（xyd≥0i=1,,m n,(X)≈，(x)+Vh,(Xyd=0j=1,,l Bs一一当前点Lagrage函数的Iesser矩阵近似， 用类似拟牛顿法迭代新！ d一一下一次的搜索方向
基本求解方法： (1)罚函数法——内点法/外点法 (2)序列线性规划法 (3)序列二次规划法 (4)信赖域算法 f (X) f (X ) f (X ) d d Bk d T T k k 2 1 min + + g (X ) g (X ) g (X ) d i m T k i k i i + 0 = 1, , h (X) h (X ) h (X ) d j l T k j k j j + = 0 = 1,, ( ) ( ) ( ) = 0 0 . . min h X g X s t f X j i 序列二次规划法——每次求解一个近似二次规划： d — —下一次的搜索方向 用类似拟牛顿法迭代更新 ！ Bk — —当前点Lagrage函数的Hessen矩阵近似