为了使求导等计算更加简便，我们对目标函数和约束条件作一些形式上的修正：
n
∑ min F（X）=
(Ci2,i0
+
S2 i,i
0
)
（n≤6）
i =1
s.t. gij（X）=min dij2-64≥0 (i,j=1,2,……6,i≠00j) t>0
│ ai │≤π/6
其中， Ci,i0 = cos ai − cos ai0 , Si,i0 = sin ai − sin ai0
为障碍函数。 在 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) 的值将无限增大，由此关于该增广
且 S0≠Ø 我们可以仿照外部罚函数法的叠加办法来构造增广目标函数，使得该增广目标 函数在可行域内部离边界较远处与原问题的目标函数 f(x) 尽可能接近，而在靠近边界是 函数之迅速增大
常取
B(x,r) = r ∑ 1/gj(x), (r>0)
或
B(x,r) = r ∑ ln (gj(x)), (r>0)
目标函数的无约束问题
min F(x,rk)
(1)
得最优解必落在可行域内部，且难以接近可行域边界。若原余额书问题的最优解在 内部，
则党 渠道某一适当值时，无约束问题 1 的最优解可以达到它。若原问题的最优解在 S 的边
界上，则随障碍因子 rk 逐渐减小，相应的问题的最优解点烈将向 S 边界上的问题的最优
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)
飞机编号 调整角度(rad)
1 0.0004
2 0.0007
3 2.0623 表二
4 -0.4955
5 -0.0001
6 1.5671
容易检验，这里给出的的确是质量很高的最优解。可是算法的耗费时间却并不令人满意。 即便如此，这种方法也有其可用之处。它能在较短的时间内给出一个较为接近最优解的可行 解，从这个可行解出发，我们可以构造相应的罚函数较快地得出满足精度要求的最优解。
由于题目所涉及数据变量不是太多，可以先考虑用逐步求精的直接搜索法来求解， MATLAB 软件也提供了相应的函数可以方便的调用。这种方法每次用一定的步长以较少的 循环次数进行“粗选”，在“粗选”出的几个解的附近一间小的步长进行“精选”，逐次推进， 直到达到所需精度。为了控制计算时间，还可以采用以下的优化方法：
极小值。设精度要求为ε，当 Xk − Xk − 1 <ε时结束运算。Xk 即为所求最优解。
考虑到精确性要求和运算的便利，我们取 M1=1，Mk= 8 10 Mk-1，ε=0.5*10-2。
我们使用求解无约束规划问题的经典算法 SUMT 来具体处理题中所给的数据记录，初 始值由短时间的直接搜索所得的近似解带入，可得结果：
问题来求解。增广目标函数由两个部分构成，一部分是原问题的目标函数，另一部分是由约
束函数构造出的“惩罚”项，“惩罚”项的作用是对“违规”的点进行“惩罚”。罚函数法主
要有两种形式。一种称为外部罚函数法，或称外点法，这种方法的迭代点一般在可行域的外
部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近；
另一种成为内部罚函数法，或称内点法，它从满足约束条件的可行域的内点开始迭代，并对
企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大，从而保证迭
代点的可行性。
1. 外部罚函数法(外点法)
约束非线形规划问题
min f(x),
s.t. g(x)>=0,
其中 g (x) = (g 1(x),…,gm(x)),
01 级混合八班 徐涛 3013001231 01 级混合八班 王菁 3013001215 01 级混合六班 赵晓楠 3013001155
罚函数求解带约束的规划问题（教案）
§1 求解带约束的非线性规划问题
罚函数法求解带约束的非线形规划问题的基本思想是：利用问题的目标函数和约束函数
构造出带参数的所谓增广目标函数，把约束非线形规划问题转化为一系列无约束非线形规划
定义罚函数：
∑ Pk(x)=
m i =1
[(gi
(x) − ai)2 + (gi(x) (bi − ai)2 + 0.5
−
bi)2
]k
; k>K
作如下整理，得到箱约束多项式规划问题： min fk(x)=f(x)+Pk(x); st. x∈Xn
其中 Xn≡［0,1］n；
可 以 证 明 ， 若 x*=(x*1,x*2,…,x*n)T 是 该 问 题 的 的 最 优 解 , 不 失 一 般 性 , 设
修改为带正参数 M（称为罚因子）的函数
P(x) =M ∑[min (0,gj(x))]²
则
min F(x,M) = f(x) + M∑[min (0,gj(x))]²
的最优解 x(M) 为原问题的最优解或近似最优解。这时，若 x (M) ∈S 则它必定是问题的
最优解；若对于某一个罚因子 M ，使得 x (M) -∈S ，则加大 M 的值，罚函数的“惩罚”
xi*∈(0,1),i=1,2,…,t,xi*∈{0,1},i=t+1,t+2,…,n. 设 =( 1,…, t,
,…, )T, 其 中
i∈{0,1}(i=1,2,…,t).那么, 也是此问题的最优解。
§3 应用举例
下面我们应用罚函数方法来解决一个实际问题。试考虑如下情形的飞行管理策略： 在约 10000 米高空的某边长为 160 公里的正方形区域内，经常有若干架飞机作水平飞行。 区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进 入该区域的飞机到达区域边缘的时候，记录其数据后，要立即计算并判断是否会与区域内的 飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角度， 以避免碰撞。现假定条件如下： （1） 不碰撞的标准为任意两架飞机的距离达于 8 公里； （2） 飞机飞行方向角调整的幅度不应超过 30 度； （3） 所有飞机飞行速度均为每小时 800 公里； （4） 进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在 60 公里以上； （5） 最多需考虑 6 架飞机； （6） 不必考虑飞机离开次区域后的状况。 请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计 算（方向角误差不超过 0.01 度），要求飞机飞行方向角调整的幅度尽量小。 设该区域 4 个定点的坐标 (0,0)，(160,0)，(160,160)，(0,160)。记录数据为：
（1） 将底层循环内判别相撞的函数分散设在每层循环下，使在高层发现相撞后可 提前结束循环；
（2） 进入新一层循环后以积累的偏差平房与已得最小偏差平方和进行比较，若大 则结束该层循环。
这些措施可以大大平均搜索次数，节省运算时间。就题中特例，该算法用 MATLAB 解 决，耗时约为 6-7 秒。所的结果为（为了与后面的方法作比较，保留了较高的精度）：
将带约束的规划问题转化为无约束非线形规划问题来求解的一个直观想法是：设法加大
不可行点处对应的目标函数值，使不可行点不能成为相应无约束问题的最优解，于是对于可
行域 S= { x | g(x) >= 0} 作一惩罚函数
P(x) = 0, x∈S;
K, else
其中 K 是预先选定的很大的数。然后构造一个增广目标函数
解逼近。这就是内部罚函数的求解过程。很显然该方法的初始点 x(0) 必须在可行域 整数规划问题。0-1 整数规划是 NP 完全的，问题复杂度较高，目 前已知的分枝定界法和隐枚举法在需要处理的元素太多时效果并不理想，且不能保证一定能 找到最优解，用计算机处理问题涉及矩阵运算时具有较大的空间和实践复杂度，算法还需要 改进。在这里我们可以利用罚函数，将整系数多项式 0-1 规划问题转化为箱约束多项式规划 问题，便于用各种数学软件进行算法处理。 考虑一般的 0-1 整规划形式：
首先，我们做出如下假设以简化问题： （1） 飞机进入控制区域后完全服从地面控制台的调度，飞机未接到指令时保持飞
行状态不变； （2） 飞机接到指令后可立即转到所需的角度，即不考虑转弯半径的影响，调整在
瞬时完成； （3） 飞机在区域内至多调整一次方向； （4） 已在区域内的飞机已经调整完全，不会相撞；
设 ai0 为第 i 架飞机的初始方向角， ai 为第 i 架飞机的方位角，(xi,yi)是飞机的坐标，可 以用 ai 的正弦函数来表示，dij（t）表示时刻 t 时 i,j 两架飞机的距离，则问题的目标函数和
−
bi)2
]k
l
∑ 记： α = 2 ≤| λi | ；
i =1
(bi − ai)2 +1
β
=
min{ (bi
− ai)2
,i + 0.5
= 1, 2,...m} ；
γ
=
(bi − ai)2 max{
,i
(bi − ai)2 + 0.5
= 1, 2,...m} ；
K= max{ln(α +1) / ln β ,α +1, − ln(m +1) / ln γ } ;