应用罚函数法实施航空港管理.docVIP

01级混合八班 徐涛 3013001231 01级混合八班 王菁 3013001215 01级混合六班 赵晓楠 3013001155 罚函数求解带约束的规划问题（教案） §1 求解带约束的非线性规划问题 罚函数法求解带约束的非线形规划问题的基本思想是：利用问题的目标函数和约束函数构造出带参数的所谓增广目标函数，把约束非线形规划问题转化为一系列无约束非线形规划问题来求解。增广目标函数由两个部分构成，一部分是原问题的目标函数，另一部分是由约束函数构造出的“惩罚”项，“惩罚”项的作用是对“违规”的点进行“惩罚”。罚函数法主要有两种形式。一种称为外部罚函数法，或称外点法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近；另一种成为内部罚函数法，或称内点法，它从满足约束条件的可行域的内点开始迭代，并对企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大，从而保证迭代点的可行性。 外部罚函数法(外点法) 约束非线形规划问题 min f(x), s.t. g(x)=0, 其中g (x) = (g 1(x),…,gm(x)), 将带约束的规划问题转化为无约束非线形规划问题来求解的一个直观想法是：设法加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束问题的最优解，于是对于可行域 S= { x | g(x) = 0} 作一惩罚函数 P(x) = 0, x∈S; K, else 其中K是预先选定的很大的数。然后构造一个增广目标函数 F (x) = f (x) + P (x) , 显然x∈S时，F（x）与f (x)相等，而x S?时，相应的F值很大。因此以F(x)为目标函数的无约束问题 minF x) = f(x) + P (x) （1） 的最优解也是原问题（NP）的最优解。 上述P(x)虽然简单，但因它的不连续性导致无约束问题（1）求解的困难。为此将P(x)修改为带正参数M（称为罚因子）的函数 P(x) =M ∑[min (0,gj(x))]2 则 min F(x,M) = f(x) + M∑[min (0,gj(x))]2 的最优解x(M) 为原问题的最优解或近似最优解。这时，若x (M) ∈S 则它必定是问题的最优解；若对于某一个罚因子M ，使得 x (M) -∈S ，则加大M 的值，罚函数的“惩罚”作用也将随之加大，因此当 M 是很大的数时，即使x (M) -∈S ，它与 S 的“距离”也不会太远，而且随M 的增大，“距离会越来越近，因此外部罚函数法就是选区一个丹增且趋于无穷的罚因子列 0 M1 M2 … Mk …, 从而构成一系列无约束非线性规划问题 min F(x,Mk) = f(x) + Mk∑[min (0,gj(x))]2 2． 内部罚函数（内点法） 对于仅带不等式约束的非线性规划问题，也可考虑使用另一种“惩罚”方式。引进的罚函数的作用相当于在可行域的边界上设置障碍，是求解的迭代过程始终在可行域内部进行。由于这种罚函数使得迭代点保持在可行域内部，故称为内部罚函数或障碍函数。 记可行域内部为 S0={ x | g(x) 0 , j=1, 2, …, m} 且 S0≠? 我们可以仿照外部罚函数法的叠加办法来构造增广目标函数，使得该增广目标函数在可行域内部离边界较远处与原问题的目标函数f(x) 尽可能接近，而在靠近边界是函数之迅速增大 常取 B(x,r) = r ∑ 1/gj(x), (r0) 或 B(x,r) = r ∑ ln (gj(x)), (r0) 为障碍函数。 在S 的边界上，B(x,r) 为正无穷大。 社选区一旦剪切区域0的“障碍”引子列{ rk} k=1, 2, …, ，由每一 rk 作一对应的障碍函数B(x,rk) ，在利用它构造出定义在 S0 内的增广目标函数列 F(x,rk) =f(x) + B(x,rk) 则若点 x(k) 从S0 内向S 的边界趋近时，F(x,rk) 的