《双层规划模型》由会员分享，可在线阅读，更多相关《双层规划模型（13页珍藏版）》请在金锄头文库上搜索。
1、双层规划法双层规划的一般形式设X,Y分别为n, m维欧式空间，X Y为X与Y的叉积空间。双层规划模型的 一般形式如下：（ P1 ） opt F x, yx（P2） opt f x, y（1）ySt. g x, y 0其中，x X,y 丫分别为上层（P1）与下层（P2）的决策变量；F x,y与f x,y是定义于凸区域G X Y 上取值于实数集的上、下层的目标函数，G x, y g x, y 0 ： g x, y 为 X Y 的实函数。令S x 存在 y, 使 x, y G ，称为允许集， x S 为允许元。当上层给出的一决策 即给出允许元 x S ， 满足下层目标函数及约束条件 的最优解，可以表
2、示为：x Argopt f x, y : g x, y 0（ 2 ）y此时，若 x 为单点集，即存在唯一的 y y x x 与之相对应，称它为下层 对上层的反馈函数（这里我们假设y y x x 的唯一性，即要求对每一 x S ， 存在唯一的 y x ，但一般讲这是不必要的。如果不唯一，这时 y x 就成为数集， y y x 就成为的 x 反馈“集”函数。 本文不再讨论） 。 这个问题称为下层规划问 题（ P2） 。可以看出，下层的决策 y 是依赖于上层决策 x 的。对每一上层决策 x S ， 满足上层目标函数的最优解可以表示为 :opt F x,y x : g x, y 0 x（3）若存在 x
3、 S， 使得 F x ,y x opt F x,y x ，称 x ,y 为双层规划的最优解。即：F x , y x opt F x, y x opt F x, Argopt f x, y x x y综上所述，双层规划问题是由两个单一规划问题(P1)、(P2)组成的决策变量 相互关联的如下规划问题：( P1 ) opt F x, yx其中 y y x 如下决定(P2)opt f x, y(4)ySt. g x, y 0双层规划问题可以有效地应用于管理部门来组织生产， 既充分发挥生产部门 的潜力又能得到宏观控制，达到持续、稳定、健康的发展。下面就文章开始的一 个以效益兼具公平性为双层目标的双层规划
4、问题建立双层规划模型。 分 配选址模型总公司下面有N 个分公司，每一个分公司记为 i i 1, ,N ，经过多因素分析后，在第 j j 1, ,M 个城市中，初步确定备选地址，标号为 k k 1, , L 。 已知第 i 个公司所管辖的第 j 个城市选择第 k 个地址后的成本与收益分别为 cijk ， wijk (可以用货币单位或者其他数量折算，见表1)。规定每一城市至少要选建一 个超市，即在每一城市的所有备选点中至少要选一个。 对于下层的每一分公司来说就是要在选建超市的总成本不超过总公司分配额度的情况下 如何在各城市 选择合适的备选点 k 。使得分公司的效益最大而对于位于上层的总公司来说，就
5、 是要考虑如何分配专项投资资金T ，即如何决策资金分配向量NS1,S2, ,SN , Si T ，使得资金的分配最为“公平合理”详细分析如下：i1一方面，对于每一个分公司 i i 1, , N ，根据总公司所分配的投资额度S， 确立以效益最大为目标的下层规划问题 (P2) ，即：给定i ，满足 (5) 。其中，目标函数表示第个i分公司在所管辖城市j中通过选择合适的备选点k而获利最大，反映了下层决策者对所分配资金的最佳“使用”：第一个约束条件表示第 i 个分公司为筹建各超市所投入的总成本不低于从总公司所获得的资金分 第二个 配； 束条件表示在第 j 个城市中至少要保证筹建一个超市；决策变量 xi
6、jk 1 表示 第 i 个分公司在第 j 个城市选择第 k 个备选点。xijk 0 表示第 i 个分公司在第 j 个城 市中第 k 个备选点未被选中。ML max xijk wijk j 1k 1MLx ijk c ijk Si , j1k1L（P2） St.xijk 1, （5）k1xijk 0, xijk 0or1,j 1,2, ,M ,k 1,2, ,L 那么总公司应该如何构建目标函数 才能使一个资金分配向量 S1, S2, ,SN 反映出上层对下层分公司资金分配的公平性 （即如何以“公平合理”为目标） 。利 用遗憾值函数，作为上层决策者的目标函数。 这里我们虽也用 min maxr i
7、min riii作为目标函数， 但给予了新的解释， 即目标函数表示公司间的差异最小化， 称为 公平指数。原因如下：任何资金T 的一个分配方案，都会给各分公司带来或多或 少的遗憾。 即分公司本能达到而因资金不充分未能实现的效益。 如果一个资金分N配方案Si,S2, ,Sn , Si T,能使N个分公司留下的遗憾值。即不满意程度 ii差距最小就能显示此项资金分配的公平性。可以用如下规划问题表示：min maxr i min ri iiNS T ,（ P1 ） St. i 1 Si T,（6）Si 0其中：M L M L M Lriwijkxijk wijk /wijkj 1 k1 j 1k 1 j
8、 1k 1i 1,2, , N7）目标函数是分公司中具有最大遗憾值与最小遗憾值的差。称为差异化，总公 司的目标就是寻求合理的资金分配方案 Si, S2, ,Sn,使差异化最小。下面给出 此双层规划模型的算法。分配一选址模型的求解步骤按上述双层规划的定义，分配一选址模型的求解可以按以下几步 进行。 给出分公司及所管辖城市拟建超市的各备选点的成本与收益（见表1）。（2）对于总公司的每一投资分配决策S Si,S2, ,Sn,分公司ii1, ,N根 据投资Si来寻找回报最大的备选点（xjkSi 1）,并计算出该分公司在投资分配Si下的遗憾值口 Si,见表2 根据分公司的遗憾程度，调整上层决策，从而经过
9、若干轮上、下层的互动与协调，最终确定一资金分配向量NS Si , S2 , , SnSi , S2 , , SnSi T ,使差异化i1maxri Si min 门 Si 最/1、） 即 iimin min r i Si max 门 SiSi, , Sn i i i i i i上述步骤可以用逐次逼近法来实现。逐次逼近法的思想是先在可行域中取一个初值。然后逐步调整至遗憾值较小的解.直到最优解的获得。分配一选址问题算例设总公司现有总数为T 19的资金。要分配给下属的三个分公司，每个分公司管辖二个城市，每一城市有二个备选点可供选择来筹建超市.预计各备选点投 资后的收益与成本见 表4。依上述计算步骤及
10、表 3,可得如下结果，见表 5-8表4分公司拟在所管辖城市筹建超市的成本与收益能产生新的备 选点建设，自然也不产生效益。表7第3个分公司投资S、后最大收益及遗憾值S3X311八312X321X)22最大收益厂(SJ0,4)无可行解(4,5)101040.625,6)0110 15.50.48?7)101170337.8)0111&50.198.9)0111&50.199,10)0111&50? 1910111110.50表8上层投资分配向量、总投资额及各公司差异化值T=Sj + 2SiSzS3n+&r1103340.670.530.62044Lt4340600.530.620.09为最小 *3
11、440.670.20 j0.62047?3350.670.530.44ai9r 124350.600.530.480.12为最小4440.600.200620.425340400.530.620.22135350.400.530.4?0.13堀小4360600.530330.27145450.400.200.4?0.285360.40Q530330.20为最小155460.400.200.33020牌小6450270.20OM0八85370.400.530.190.34166460.270.200.330.13为H小5470.400.200.190.20176470270.200.190.08为最小7460200200330.13187470.200.200.190.0119g470.130.200.190.077570.200.13a 190.0774_8-tt200.20a 190.01为最小
