双层规划模型复习进程

双层规划模型双层规划法双层规划的一般形式设X,Y分别为n,m维欧式空间，X Y为X与丫的叉积空间。双层规划模型的 一般形式如下：（P1） opt F x, yx（P2）opt f x, y（ 1）ySt.g x, y 0其中，x X,y Y分别为上层（P1）与下层（P2）的决策变量；Fx,y与fx,y 是定义于凸区域G X Y上取值于实数集的上、下层的目标函数，G x, y g x, y 0 : g x,y为X 丫的实函数。令S x存在y,使x,y G ， 称为允许集，x S为允许元。当上层给出的一决策即给出允许元 x S，满足下层目标函数及约束条件 的最优解，可以表示为：x Argopt f x, y : g x, y 0y（2）此时，若 x为单点集，即存在唯一的y y x x与之相对应，称它为下 层对上层的反馈函数（这里我们假设y yx x的唯一性，即要求对每一 x S，存在唯一的y x ,但一般讲这是不必要的。如果不唯一，这时yx就成为数集，y y x就成为的x反馈“集”函数。本文不再讨论。这个问题称为下 层规划问题（P2）。可以看出，下层的决策y是依赖于上层决策x的。对每一上 层决策x S，满足上层目标函数的最优解可以表示为：opt F x, y x : g x, y 0（3）x若存在x S ,使得Fx,yx optFx, yx ，称x ,y为双层规划的最优x解。即：F x ,y x opt F x, y x opt F x, Argopt f x, yxxy综上所述，双层规划问题是由两个单一规划问题（P1）、（P2）组成的决策变量相互关联的如下规划问题：（P1） opt F x, yx其中y y x如下决定（P2）opt f x, y（ 4）ySt. g x, y 0双层规划问题可以有效地应用于管理部门来组织生产，既充分发挥生产部 门的潜力又能得到宏观控制，达到持续、稳定、健康的发展。下面就文章开始 的一个以效益兼具公平性为双层目标的双层规划问题建立双层规划模型。 分配一选址模型总公司下面有N个分公司，每一个分公司记为i i 1, ,N，经过多因素分 析后，在第j j 1, M个城市中，初步确定备选地址，标号为k k 1, L。已知第i个公司所管辖的第j个城市选择第k个地址后的成本与收益分别为%，w （可以用货币单位或者其他数量折算，见表1）。规定每一城市至少要选建一个超市，即在每一城市的所有备选点中至少要选一个。对于下层的每一 分公司来说就是要在选建超市的总成本不超过总公司分配额度的情况下如 何在各城市选择合适的备选点k。使得分公司的效益最大？而对于位于上层的总公司来说，就是要考虑如何分配专项投资资金 T ,即如何决策资金分配向量NSi,S2, ,Sn , Si T，使得资金的分配最为“公平合理”？详细分析如下：i 1一方面，对于每一个分公司i i 1, ,N，根据总公司所分配的投资额度S，确立以效益最大为目标的下层规划问题 （P2），即：给定i，满足。其 中，目标函数表示第个i分公司在所管辖城市j中通过选择合适的备选点k而获 利最大，反映了下层决策者对所分配资金的最佳“使用”：第一个约束条件表示 第i个分公司为筹建各超市所投入的总成本不低于从总公司所获得的资金分配； 第二个约束条件表示在第j个城市中至少要保证筹建一个超市；决策变量Xijk 1表示第i个分公司在第j个城市选择第k个备选点。Xijk 0表示第i个分 公司在第j个城市中第k个备选点未被选中。M LmaxjXijk Wjk1 k 1MLXijk CijkSi,j 1k 1L(P2)St.Xijk1,k 1Xijk0, Xijk0or1,j 1,2,M,k1,2, ,L那么总公司应该如何构建目标函数才能使一个资金分配向量Si,S2, ,Sn反映出上层对下层分公司资金分配的公平性 （即如何以“公平合 理”为目标。利用遗憾值函数，作为上层决策者的目标函数。这里我们虽也用 min maxri min riii作为目标函数，但给予了新的解释，即目标函数表示公司间的差异最小化，称 为公平指数。原因如下：任何资金 T的一个分配方案，都会给各分公司带来或 多或少的遗憾。即分公司本能达到而因资金不充分未能实现的效益。如果一个N资金分配方案Si,S2, ,Sn , Si T ,能使N个分公司留下的遗憾值。即不满i 1意程度差距最小就能显示此项资金分配的公平性。可以用如下规划问题表示：minmax ri min niiN(P1) St. i；SSi T,i 0(6)其中：M LMLMLriwXijk Wijk/Wijkj 1 k 1j 1 k 1j 1 k 1i 1,2, ,N(7)目标函数是分公司中具有最大遗憾值与最小遗憾值的差。称为差异化，总公司的目标就是寻求合理的资金分配方案S1,S2, ,Sn，使差异化最小。下面给出此双层规划模型的算法。分配一选址模型的求解步骤按上述双层规划的定义，分配一选址模型的求解可以按以下几步进行。(1) 给出分公司及所管辖城市拟建超市的各备选点的成本与收益(见表1)。(2) 对于总公司的每一投资分配决策S SS2, ,Sn，分公司i i 1, ,N 根据投资Si来寻找回报最大的备选点(Xjk Si 1)，并计算出该分公司在投资分 配Si下的遗憾值a Si ，见表2。(3) 根据分公司的遗憾程度，调整上层决策，从而经过若干轮上、下层的互动与协调，最终确定一资金分配向量NSSi , S2, SnSi , S2, Sn Si T，使差异化i 1max ri Si min 仃 Si 最小，即ii$叫叫"Si呼心上述步骤可以用逐次逼近法来实现。逐次逼近法的思想是先在可行域中取 一个初值。然后逐步调整至遗憾值较小的解.直到最优解的获得。分配一选址问题算例设总公司现有总数为T 19的资金。要分配给下属的三个分公司，每个分 公司管辖二个城市，每一城市有二个备选点可供选择来筹建超市.预计各备选 点投资后的收益与成本见表4。依上述计算步骤及表3,可得如下结果，见表5- 8。表4 分公司拟在所管辖城市筹建超市的成本与收益注：每一分公司根据不同数目的投资，寻求回报最大的决策变量和收益值，见表5。如投资在范围3，4中，实际作用为3,小数部分投资不可能产生 新的备选点建设，自然也不产生效益。