双层规划模型

《双层规划模型》由会员分享，可在线阅读，更多相关《双层规划模型（8页珍藏版）》请在装配图网上搜索。

1、双层规划模型双层规划法 双层规划的一般形式 设 X,Y分别为n,m维欧式空间，XY为X与Y的叉积空间。双层规划模型的一般形式如下： optF(x,y) x optf(x,y) y St. g(x,y)0 其中，xX,yY分别为上层与下层(P2)的决策变量；F(x,y)与f(x,y)是定义于凸区域GXY上取值于实数集的上、下层的目标函数，(x,y)g(x,y)0：g(x,y)为XY的实函数。令S=x存在y,使(x,y)G，G=称为允许集，xS为允许元。 当上层给出的一决策即给出允许元xS，满足下层目标函数及约束条件的最优解，可以表示为： y(x)=Argoptf(x,y):g(x,y)0 y此时

2、，若y(x)为单点集，即存在唯一的y=y(x)y(x)与之相对应，称它为下层对上层的反馈函数(这里我们假设y=y(x)y(x)的唯一性，即要求对每一xS，存在唯一的y(x)，但一般讲这是不必要的。如果不唯一，这时y(x)就成为数集，y=y(x)就成为的x反馈“集”函数。本文不再讨论)。这个问题称为下层规划问题(P2)。可以看出，下层的决策y是依赖于上层决策x的。对每一上层决策xS，满足上层目标函数的最优解可以表示为: optF(x,y(x):g(x,y)0 (3) x若存在x*S，使得F(x*,y(x*)=optF(x,y(x)，称x*,y*为双层规划的最优解。x()即： Fx*,yx*=op

3、tF(x,y(x)=optFx,Argoptf(x,y) xxy()综上所述，双层规划问题是由两个单一规划问题(P1)、(P2)组成的决策变量相互关联的如下规划问题： optF(x,y) x其中y=y(x)如下决定 optf(x,y) y St. g(x,y)0 双层规划问题可以有效地应用于管理部门来组织生产，既充分发挥生产部门的潜力又能得到宏观控制，达到持续、稳定、健康的发展。下面就文章开始的一个以效益兼具公平性为双层目标的双层规划问题建立双层规划模型。 分配选址模型 总公司下面有N个分公司，每一个分公司记为i(i=1,L,N)，经过多因素分析后，在第j(j=1,L,M)个城市中，初步确定备

4、选地址，标号为k(k=1,L,L)。 已知第i个公司所管辖的第j个城市选择第k个地址后的成本与收益分别为cijk， wijk (可以用货币单位或者其他数量折算，见表1)。规定每一城市至少要选建一个超市，即在每一城市的所有备选点中至少要选一个。对于下层的每一分公司来说就是要在选建超市的总成本不超过总公司分配额度的情况下如何在各城市选择合适的备选点k。使得分公司的效益最大?而对于位于上层的总公司来说，就是要考虑如何分配专项投资资金T，即如何决策资金分配向量(S1,S2,L,SN),SiT，使得资金的分配最为“公平合理”?详细分析如下： i=1N一方面，对于每一个分公司i(i=1,L,N)，根据总公

5、司所分配的投资额度S，确立以效益最大为目标的下层规划问题(P2)，即：给定i，满足(5)。其中，目标函数表示第个i分公司在所管辖城市j中通过选择合适的备选点k而获利最大，反映了下层决策者对所分配资金的最佳“使用”：第一个约束条件表示第i个分公司为筹建各超市所投入的总成本不低于从总公司所获得的资金分配；第二个约束条件表示在第j个城市中至少要保证筹建一个超市；决策变量xijk=1表示第i个分公司在第j个城市选择第k个备选点。xijk=0表示第i个分公司在第j个城市中第k个备选点未被选中。 maxxijkwijk j=1k=1MLxijkcijkSi,j=1k=1L (P2)St. (5) xijk

6、1,k=1xijk0,xijk=0or1,j=1,2,L,M,k=1,2,L,LML那么总公司应该如何构建目标函数才能使一个资金分配向量(S1,S2,L,SN) 反映出上层对下层分公司资金分配的公平性(即如何以“公平合理”为目标)。利用遗憾值函数，作为上层决策者的目标函数。这里我们虽也用minmaxri-minri ii()作为目标函数，但给予了新的解释，即目标函数表示公司间的差异最小化，称为公平指数。原因如下：任何资金T的一个分配方案，都会给各分公司带来或多或少的遗憾。即分公司本能达到而因资金不充分未能实现的效益。如果一个资金分配方案(S1,S2,L,SN),SiT，能使N个分公司留下的遗憾

7、值。即不满意程度i=1N差距最小就能显示此项资金分配的公平性。可以用如下规划问题表示： minmaxri-minri ii()NSiT, St. i=1Si0其中： MLMLML ri=wijk-xijkwijk/wijk j=1k=1j=1k=1j=1k=1 i=1,2,L,N 目标函数是分公司中具有最大遗憾值与最小遗憾值的差。称为差异化，总公 司的目标就是寻求合理的资金分配方案(S1,S2,L,SN)，使差异化最小。下面给出此双层规划模型的算法。 分配选址模型的求解步骤 按上述双层规划的定义，分配一选址模型的求解可以按以下几步进行。 (1)给出分公司及所管辖城市拟建超市的各备选点的成本与收

8、益(见表1)。 (2)对于总公司的每一投资分配决策S=(S1,S2,L,SN)，分公司i(i=1,L,N)根据投资Si来寻找回报最大的备选点(xijk(Si)=1)，并计算出该分公司在投资分配Si下的遗憾值ri(Si)，见表2。 (3)根据分公司的遗憾程度，调整上层决策，从而经过若干轮上、下层的互动与协调，最终确定一资金分配向量 S=S,S,L,S*(*1*2*N)N(S1,S2,L,SN)SiT，使差异化i=1maxriSi*-minriSi*最小，即 ii()()i(S1,L,SN)minminri(Si)-maxri(Si) i()上述步骤可以用逐次逼近法来实现。逐次逼近法的思想是先在可行域中取一个初值。然后逐步调整至遗憾值较小的解直到最优解的获得。 分配选址问题算例 设总公司现有总数为T=19的资金。要分配给下属的三个分公司，每个分公司管辖二个城市，每一城市有二个备选点可供选择来筹建超市预计各备选点投资后的收益与成本见表4。依上述计算步骤及表3，可得如下结果，见表5-8。 表4 分公司拟在所管辖城市筹建超市的成本与收益 注：每一分公司根据不同数目的投资，寻求回报最大的决策变量和收益值，见表5。如投资在范围3，4中，实际作用为3，小数部分投资不可能产生新的备选点建设，自然也不产生效益。