-
二层规划问题(bilevel programming problems,BPP)[1-2]是一类具有二层递阶结构的系统优化问题,它包含两个规划问题,即上层规划问题和下层规划问题.由于求解二层规划问题是一个强NP难问题,因此不少学者针对部分特殊的BPP模型提出求解算法.当下层问题的最优解唯一时,上、下层目标一致,得到唯一解,这时称二层规划问题是适定的.当下层问题的最优解不唯一时,通常采用乐观模型、悲观模型等数学模型[3-12].但是乐观模型和悲观模型是两种极端情况,与现实不一定相符,因此有学者在两者之间找到一种中间状态,平衡上、下层完全合作与完全不合作的极端情形,采用合作度将上、下层目标函数联立,创建了部分合作模型[13].由于合作度不满足下层决策需依赖上层决策这一条件,也就是说上、下层依然是分离的,因此文献[7]对具有不适定性的二层规划问题模型采用合作系数建立部分合作模型,并考虑了下层问题的合作度依赖于上层决策这一因素.文献[4]对二层规划模型(BLP)作了比较详细的介绍.文献[5-6]分别对BLP模型的算法、收敛性作了研究.
部分合作模型已被广泛应用到经济、工业等各个方面,也由用单纯的合作度连接上、下两层目标函数变为用含上层问题的自变量的合作度系数构建部分合作模型.受文献[11]的启发,本文对BLP的部分合作模型进行探讨,定义了一种新的满意度函数,该满意度函数相比文献[7]中的变量少,计算较为简易,并在此满意度函数下构建了新的部分合作模型,最后通过求解算例,验证了模型的可行性.
全文HTML
-
在本文中,考虑如下的二层规划模型(BLP):
其中y是下层问题的解,
其中:x∈
$\mathbb{R}$ s,y∈$\mathbb{R}$ t分别为上、下层规划问题的决策变量;F,f:$\mathbb{R}$ s×$\mathbb{R}$ t→$\mathbb{R}$ 分别为上、下层规划问题的目标函数;G,g:$\mathbb{R}$ s×$\mathbb{R}$ t→$\mathbb{R}$ 分别为上、下层规划问题的约束函数.定义X和Y分别为上、下层问题的可行集,即对于任意一个x∈X,BLP问题的下层规划问题的最优解集合称为反应集ψ(x),即
对任意的x∈X,ψ(x)中的元素唯一时,称下层最优解唯一.当存在一点x0∈X,使得ψ(x0)中的元素不唯一时,那么下层最优解不唯一,则称该二层规划问题不适定.
对于不适定二层规划问题,存在两种极端情况.一种是乐观模型,即上层决策者认为下层完全配合上层目标,总是将对上层目标函数最有利的解反馈给上层,使得上层目标函数最优,设其乐观解为(x0,y0),则有
另一种是悲观模型,即上层决策者认为下层完全不配合上层目标,总是将对上层目标函数最不利的解反馈给上层,使得上层目标函数最差,设其悲观解为(xp,yp),则有
如果下层与上层的合作情况并非上述两种极端情况,而是采取部分合作的态度与上层合作,即为部分合作模型.定义β为下层问题的合作度,0≤β≤1(β=1为乐观模型,β=0为悲观模型).部分合作模型为:
上、下层目标函数都是使自身达到最优.当下层反馈给上层的解最不理想时,记F表示F(x,y),FL为上层目标函数的容忍极限值.同理,记f表示f(x,y),fL为下层目标函数的容忍极限值,即它们分别是下面优化问题的最优值:
本文利用FL,fL定义了上、下层目标函数的满意度,针对部分合作模型,在符合满意度函数所需的条件下,引入了一种新的合作度.该满意度函数变量较少,计算时较为简易,且保证了下层问题的合作度也依赖于上层决策.
-
定义1 记
称μ(F),μ(F)为目标函数F,f的隶属函数,即上、下层目标函数的满意度,其中0≤μ(F)≤1,0≤μ(F)≤1.当目标函数值越接近决策者的容忍极限值时,μ(F),μ(F)越接近0直至等于0.反之,当目标函数值越远离容忍极限值时,μ(F),μ(F)越接近1直至等于1.
定义如下的总体满意度函数:
其中:0≤d(F,f)≤1.随着目标函数值F,f的减小,d(F,f)的值逐渐接近1或等于1.当目标函数值F,f越接近决策者的容忍极限值FL,fL时,d(F,f)越接近0直至等于0,因此,利用d(F,f)的值来刻画上、下层函数的总体满意度也是合理的.
为了顾及下层决策者的利益,本文将下层问题的满意度函数作为部分合作模型中的合作度来构建新的部分合作模型.
根据上述隶属函数,定义下层问题的合作度如下:
如果直接以下层满意度作为合作系数来求解不适定二层规划问题,会不同程度地破坏二层规划问题中上层在主体中的结构,最后得到的协调解极大可能会偏向下层.因此,为了保证上层的利益,首先让上层决策者选取适当的最小满意度水平μ1*,在此满意度水平下,下层决策者再选取一个自己可能的满意度水平μ2*,然后构造约束条件,限制x,y的范围.于是,以下层满意度作为合作度的部分合作模型构建如下:
得到如下等价模型:
需要注意的是,当上层或者下层的理想值和容忍极限值相等时,上、下层满意度的定义没有意义,这时(4)式不能用于求解此类不适定二层规划问题.
下面的定理保证基于满意度的部分合作模型总存在介于乐观值和悲观值之间的函数值,即在新的部分合作模型中总能找到好于悲观值的函数值.记满足(4)式的约束条件的x,y的范围分别为X1,Y1.
定理1 对∀x∈X1,总有下式成立,
证 由于F(x0,y0),F(xP,yP)分别为乐观模型和悲观模型的最优值,因此有
故对∀x∈X1,0≤β(x)≤1,有
即有
同理可得:
即有
由(5),(6)式可知,定理成立.
为了使上、下层决策者都可以得到比较满意的结果且不影响二层规划的主从递阶性,给出以下算法.
首先假设总体满意度区间为[dL,dU],其中dL,dU分别为悲观模型和乐观模型所对应的总体满意度,若计算出的总体满意度不属于[dL,dU],那么上层决策者须调整最小满意度水平μ1*.更新最小满意度μ1*的规则如下:
1) 若D(F,f) < dL,则上层决策者需要减少自己的最小满意度水平μ1*.
2) 若D(F,f)>dU,则上层决策者需要增加自己的最小满意度水平μ1*.
算法1模糊交互式协调算法
步骤1选取满足式(1),(2)的FL,fL;
步骤2上层决策者首先宣布自己可能的最小满意度水平μ1*;
步骤3根据上层决策者宣布的最小满意度水平μ1*,下层决策者给定其可能的最小满意度水平μ2*;
步骤4用MATLAB求解模型(4),得到上、下层函数最优值F,f;
步骤5计算对应函数值的总体满意度D(F,f),如果D(F,f)∈[dL,dU],停止运算.否则,根据更新上层决策者的最小满意度规则,得到新的μ1*,转步骤3.
-
下面通过算例验证以下层满意度函数作为合作系数的部分合作模型的可行性.
例1
对∀x∈X,下层问题的反应集ψ(x)={(y1,y2,y3)|x1+x2+y1+y2+y3=4}.乐观最优解(x0,y0)=(x1,x2,y1,y2,y3)=(0,0,0,0,0),乐观值F(x0,y0)=0;悲观最优解
$\left( {{x_p}, {y_p}} \right) = \left( {{x_1}, {x_2}, {y_1}, {y_2}, {y_3}} \right) = \left( {\frac{4}{3}, \frac{4}{3}, 0, \frac{4}{3}, 0} \right)$ ,悲观值$F\left( {{x_p}, {y_p}} \right) = \frac{{16}}{3}$ .上、下层目标函数的容忍极限值为:
所以下层满意度函数为:
带入模型(4)得:
各模型计算结果见表 1.
通过表 1可以看出,在以本文定义的下层满意度函数作为合作系数的部分模型中,随着上、下层目标函数的最小满意度水平值的不断改变,相应的上、下层函数的函数值也发生改变,而且总能找到比悲观解更好的解,且在μ1*=0.6, μ2*=0.6时总体满意度最高,D(F,f)=0.876.
在本文研究的BLP模型下,传统的满意度函数为
其中:FU,fU为目标函数的理想值;FL,fL为目标函数的容忍极限值.显然,该满意度函数变量较多,计算更为复杂.在传统满意度函数下,求出算例所需变量FU,FL,fU,fL的值,然后通过逐步调整μ1*得到一系列的值,当μ1*=0,μ2*=0.75时获得最大的总体满意度, D(F,f)=0.744,0.744<0.876,由此说明,在本文定义的满意度函数下建立的部分合作模型求得的总体满意度更高,结果更好.
-
本文针对部分合作模型采取了一种新的满意度函数.该满意度函数变量少,利于求解运算,并以下层满意度函数作为合作系数建立新的部分合作模型.通过改变上、下层问题的最小满意度水平,得到一系列的解,计算相应的总体满意度.算例结果表明在该满意度函数下的部分合作模型是可行的.