一种求解线性二层规划的罚函数方法

张 涛

杨世明 (长江大学地球物理与石油资源学院，湖北 荆州 434023)

一种求解线性二层规划的罚函数方法

杨世明 (长江大学地球物理与石油资源学院，湖北 荆州 434023)

利用下层问题的最优性条件代替下层问题，同时取互补条件为上层目标函数的罚项，将线性二层规划转化为相应的单层规划。分析表明，该罚函数为精确罚函数。最后，设计了线性二层规划的罚函数算法,并用数值试验验证了算法的可行性。

线性二层规划； K-T条件；罚函数

二层规划是一种具有递阶结构的系统优化问题，在二层规划模型中,上、下层问题都有自己的目标函数和约束条件。上层问题的目标函数不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响[1]。二层规划是NP难问题[2]，因此对二层规划的研究大多数集中于线性二层规划-上、下层目标函数以及约束条件均为线性函数，在求解线性二层规划的方法中，一类重要的转化思想是以下层问题的K-T条件代替下层问题，然后求解相应的带互补约束条件的数学规划问题。下面，笔者依然采用以下层问题的K-T条件代替下层问题的转化思想，将线性二层规划转化为带互补条件的数学规划问题，并取互补条件为上层目标函数的罚项，构造线性二层规划的罚方法，通过理论分析，得到所设计的罚函数为精确罚函数。

1 基本概念

假设C1,x∈Rm,C2,b,y∈Rn2,a∈Rm,A1∈Rm×n1,A2∈Rm×n2，则线性二层规划可以写为：

s.t.A1x+A2y≤a

(1)

对于问题(1)，以下层问题的K-T条件代替下层问题有：