双层规划模型

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 Y分别为上层（ P1）与下层（P2）的决策变量； F x,y 与 f x,y 是 定义于凸区域 G X Y 上取值于实数集的上、下层的目标函数，Gx, 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 0x（3）若存在 x S，

3、使得F x ,y xopt F x,y x ，称 x ,y 为双层规划的最优解。即：F x , y xopt F x, y x opt F x, Argopt f x, yx 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 个城市中至少要保证筹建一个超市；决策变量 xijk

6、 1表示第 i 个分公司在第 j 个城市选择第 k 个备选点。 xijk 0 表示第 i 个分公司在第 j 个城 市中第 k 个备选点未被选中。MLmaxxijk wijkj 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 maxri min rii

7、i 作为目标函数， 但给予了新的解释， 即目标函数表示公司间的差异最小化， 称为 公平指数。原因如下：任何资金 T 的一个分配方案，都会给各分公司带来或多或 少的遗憾。 即分公司本能达到而因资金不充分未能实现的效益。 如果一个资金分 N配方案 S1,S2, ,SN , Si T，能使 N个分公司留下的遗憾值。即不满意程度 i1差距最小就能显示此项资金分配的公平性。可以用如下规划问题表示：min maxri 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 1k 1i

8、 1,2, , N7)目标函数是分公司中具有最大遗憾值与最小遗憾值的差。 称为差异化， 总公 司的目标就是寻求合理的资金分配方案 S1, S2, ,SN ，使差异化最小。下面给出 此双层规划模型的算法。分配选址模型的求解步骤 按上述双层规划的定义，分配一选址模型的求解可以按以下几步进行。(1) 给出分公司及所管辖城市拟建超市的各备选点的成本与收益 (见表 1)。(2) 对于总公司的每一投资分配决策 S S1,S2, ,SN ，分公司 i i 1, ,N 根 据投资 Si 来寻找回报最大的备选点 (xijk Si 1)，并计算出该分公司在投资分配Si 下的遗憾值 ri Si ，见表2。(3) 根

9、据分公司的遗憾程度，调整上层决策，从而经过若干轮上、下层的互 动与协调，最终确定一资金分配向量NS S1 , S2 , , SNS1 , S2 , , SNSi T ，使差异化i1maxri Si min ri Si 最小，即iimin min ri Si max ri SiS1, , SN i i i i i i上述步骤可以用逐次逼近法来实现。 逐次逼近法的思想是先在可行域中取一 个初值。然后逐步调整至遗憾值较小的解直到最优解的获得。 分配选址问题算例设总公司现有总数为 T 19 的资金。要分配给下属的三个分公司， 每个分公 司管辖二个城市， 每一城市有二个备选点可供选择来筹建超市 预计各备

10、选点投 资后的收益与成本见表 4。依上述计算步骤及表 3，可得如下结果，见表 5-8。表 4 分公司拟在所管辖城市筹建超市的成本与收益注：每一分公司根据不同数目的投资，寻求回报最大的决策变量和收益值， 见表 5。如投资在范围 3，4中，实际作用为 3，小数部分投资不可能产生新的备 选点建设，自然也不产生效益。表7 第3个分公司投资S、后最大收益及遗憾值S3X311312X321X)22最大收 益厂(SJ0,4)无可行解(4,5)101040.625,6)0110 15.50.48©7)101170337.8)0111&50.198.9)0111&50.199,10)0

11、111&501910111110.50表8上层投资分配向量、总投資额及各公司差异化值T=Sj + §2 +&SiSzS3nr103340.670.530.62044Lt4340600.530.620.09为最小 *3440.670.20 j0.620473350.670.5310.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.20OM085370.400