双层规划

1双层规划一、双层规划的定义及背景双层规划（BilevelProgrammingProblem，简称BLPP）是一种具有二层递阶结构的系统优化问题，上层问题和下层问题都有各自的决策变量、约束条件和目标函数。双层系统优化研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者，并不直接干涉下层的决策；而下层决策者只需要把上层的决策作为参数，他可以在自己的可能范围内自由决策。这种决策机制使得上层决策者在选择策略以优化自己的目标达成时，必须考虑到下层决策者可能采取的策略对自己的不利影响。首先提出层次规划模型的是H.VStackelberg，上世纪50年代，为了更好的描述现实中的经济模式，H.VStackelberg在他的专著中首次提出了层次规划这种概念，虽然多层规划与之有共同点，但各层决策者依次做出决策，并且各自的策略集也不必再是分离的。20世纪60年代，Dantaig和Wolfe提出了大规模线性规划的分解算法，承认有一个核心决策者，它的目标高于一切，但与多层规划有很大区别，多层规划承认有最高决策者，大不是绝对的，他允许下层决策者有各自不同的利益。20世纪70年代发展起来的多目标规划通常寻求的是一个决策者的互相矛盾的多个目标额折衷解，而多层规划强调下层决策对上层目标的影响，并且多层规划问题通常不能逐层独立求解。上世纪70年代以来，在解决实际问题的过程中，人们才逐渐形成多层规划的概念和方法。多层规划（MultilevelProgramming）一词是Candler和Norton在奶制品工业模型和墨西哥农业模型的研究报告中首先提出来的。上世纪70年代，人们对多目标规划进行了深入的研究，也形成了一些求解多目标规划的有效方法，如分层优化技术，这种技术也可以用来求解层次问题，但这种技术建立在下层的决策不影响上层的目标基础上，而多层规划正是强调下层决策对上层目标的影响。因此多层规划同城不同于多目标规划。在过去的几十年中，多层规划的理论、方法及应用都有了很大的发展，并且已经成为规划论中的一个新的重要分支，而在多多层规划的研究中，双层规划是一个重要的研究对象，这是因为双层规划是多层规划中的一个特例，同时多层规划可以看作是一系列的双层规划的复合。双层规划是在研究非平衡经济市场竞争时首先提出的，1973年，在Bracken和Mcgill的文章中，出现了双层规划的数学模型。1977年，在Candler和Norton的科学报告中正式出现了双层规划和多层规划名词。双层规划研究的是两个各具目标函数的决策者之间按有序的和非合作方式进行的相互作用，上层决策者优先做出决策，下层决策者在上层决策信息下按自己的利益做出反应，由于一方的行为影响另一方策略的选择和目标的实现，并且任何一方又不能完全控制另一方的选择行为，因此上层决策者要根据下层的反应做出符合自身利益的最终决策。根据上述定义，双层规划具有以下一些主要特点：（1）层次性。研究的系统是分层管理的，各层决策者依次做出决策，下层服从上层。（2）独立性。各层决策者各自控制一部分决策变量，以优化各自的目标。（3）冲突性。各层决策者有各自不同的目标，且这些目标往往是相互矛盾的。（4）优先性。上层决策者优先做出决策，而下层决策者在优化自己的目标而选择决策时，不能违背上层的决策。2（5）自主性。下层并不是完全无条件服从上层，它有相当的自主权。（6）制约性。下层的决策不但决定着自身目标的达成，而且影响着上层目标的实现。（7）依赖性。各层决策者的容许策略集通常是不可分的，他们往往形成一个相互关联的整体。二、常见双层规划的分类（1）线性双层规划线性双层规划（LinearBilevelProgramming，简称LBM）是双层规划的一个特例，其上、下层目标函数和约束条件都是线性的，是双层规划中最为常见且形式最为简单的一种情况，在实际中应用十分广泛，主要涉及管理决策、交通网络布局、工程设计等诸多方面。一般来说，求解线性双层规划问题是非常困难的，Jeroslow指出线性双层规划是一个NP—hard问题，Ben—Ayed及Bard对此结论给出了简短的证明；Hallsen对性双层规划是强NP一hard问题给出了严格的证明。后来，Vicente指出，寻找线性双层规划的局部最优解也是NP一hard问题，不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的，它也可能是一个非凸问题，.并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。自20世纪70年代以来，己提出了几十种求解线性双层规划的算法，主要有以下几类不同的算法：（a）极点算法：极点搜索思想的理论基础是线性双层规划的最优解必在诱导域的极点处取得。首先可以利用各种方法来寻找诱导域的极点，然后从中再找出线性双层规划问题的局部最优解或全局最优解。（b）分枝定界法：其基本思路是，根据事先选定的分枝准则，将所求解的问题分成一系列子问题，并从中选取一个子问题进行检验，决定其取舍。分枝定界法计算量很大，但它能求得全局最优解。（c）K-T法：其基本思路是将线性双层规划问题中的下层规划问题用它的Kuhn一Tucke:条件代替，将线性双层规划问题化为单层非线性规划问题求解，最初用于求解线性双层资源控制问题。这种算法仅对线性约束的上层和凸二次规划的下层这种特殊情况有效。（d）模糊数学算法：其基本思路是充分利用模糊集理论中隶属函数及模糊算子的概念和性质，分别建立上层决策变量的隶属函数和上、下层决策者目标函数的偏好隶属函数，双层决策问题转化为单层优化问题，分别对各单层规划的解进行讨论，最终把线性双层规划转化为求解一个线性规划问题，求得两层决策问题的满意解。（2）凸双层规划凸双层规划（ConvexBilevelProgramming），即上层目标函数是凸函数，下层目标函数是凸二次函数，约束条件均为线性的一类非线性双层规划。对这类问题，在一定条件保证下，将原问题转化为一个单层的数学规划，通过对其对应的松弛问题有关性质的讨论，给出恰当的定界规则和分支原则，隐含地考虑到互补松弛条件的所有组合，利用分支定界技术给出一种求全局解的算法。（3）混合整数线性双层规划整数规划一类要求问题中的全部或一部分变量为整数的数学规划。一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最3优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。（4）非线性双层规划双层规划（Non-linearBilevelProgramming，简称NLBP）的一般形式为：yXxyxF,),(min（a）解其中yyxGts0),(..（b）yyxf　),(min（c)0),(..yxgts（d）其中，1nxR，2nyR。则上层变量1nxR，下层变量2nyR。同样，函数12:nnFRRR、12:nnfRRR分别是上层、下层目标函数，而向量值函数121:nnmGRRR、122:nnmgRRR分别是上层、下层约束条件。上层约束条件中包含着来自两层变量（与用X表示的约束不同）是一个特殊的角色，因为这些条件不能约束下层决策者，它们不直接的被强制执行。如果上下层目标函数(,)Fxy、(,)fxy至少有一个非线性的，称之为非线性双层规划。此外，如果上下层变量在增加整数约束，称之为证书双层规划。三、常见双层规划的模型及其应用在双层规划模型中，不同的决策者控制着相应的决策变量，并优化各自的目标函数。下层决策者首先进行决策，这样上层决策者必须预测到下层可能的反应。下层根据上层的决策进行反应，以优化个人的目标函数。因为双方可供选择的策略集是相互依赖的，上层的决策会影响下层可选的决策和目标的实现，反之亦然。设上层决策者控制的变量为12(,,...,)TnnxxxxXR；下层决策者控制的变量为12(,,...,)TnnyyyyYR。（a）下层以最优解反馈到上层的双层规划数学模型为：（BP）Xxy)minF(x,解其中y,0),(..yxGtsYyyxf),(min0),(..yxgts（b）下层以最优值反馈到上层的双层规划数学模型为：4XxxvxF))(,(min0))(,(..xvxGtsYyyxgyxfxv}0),(|),(min{)(其中F，:fXYR，:nmpGRRR，:nmqgRRR，集合X和集合Y包含了变量的其他约束，如变量的非负性或整数要求等。对于上述双层规划问题（BP），即使当F，f，G，g均是连续函数，并且集合X和Y是紧集，（BP）也可能没有最优解。导致这种可能性的原因是对某个xX，下层问题可能有多个最优解，下面的例子将说明这种情况。例1.11min100100xFxy解其中y,0..xts12minyfyy12..1stxyy121yy10y，20y点12(010)xyy，，实现了上、下层目标函数的最小值，但对于固定的x点0x，下层决策者可以选择任何满足121yy和121yy的正数10y，20y，这样的10y，20y对下层都是可行的，而且都是最优的，但上层目标函数值却是不一样的，当21y，20y时100F，1f；而下层也可以选择10y，21y，这样下层目标函数值1f，而上层目标函数值0F。因此下层问题懂得多解性导致上层问题可能得不到最优解。当然下层问题的多解性不仅会导致双层规划的无解，而且还会对双层规划问题产生许多影响。1、双层规划在区域港口内陆运输网络上的应用[2][3][6]1）基本参数n可以建设港口内陆集散中心的潜在地点的数量；j在第j地建港口内陆集散中心的最大允许容量；51jf在第j地建内陆集散中心的固定成本费用；()jjfa在第j地建内陆集散中心的变动成本费用；ijc从生产地i到内陆集散中心j的单位运输费用；ijg从内陆集散中心j到出口港k的单位运输费用；ip生产地i的生产量；kq出口港k的容量；d总运输需求量。2）决策变量jy，1jy，表示在第j地建内陆集散中心；jy=0，表示在第j地不建内陆集散中心。ja，表示在第j地建内陆集散中心的容量；ijx，货物从生产地i到集散中心j的运输量；jkz，货物从集散中心j到出口港k的运输量。上层规划可以描述为物流规划部门在满足运输总需求的条件下确定货物集散中心的数量和规模,使得总成本（固定成本和变动成本）最小；下层规划描述了在多个货物集散中心和出口港口存在的条件下，物流服务企业的运输量在不同运输路线的分配，使得物流服务企业的总运输成本最小。对于上层规划来说,其数学模型为：11min(())nfffjjfSfyfaa1..0,1;0njfjfjjaydstya（P）当上层规划达到最优时，即确定了各港口内陆集散中心的容量ja，则下层规划便根据上层规划确定的各集散中心的容量ja，,寻求最优的运输方案,这里包含两个运输问题，一个是从生产地运到内陆集散中心，另一个是从内陆集散中心运往出口港。从生产地到内陆集散中心的运输问题即下层规划的第一个模型为111minmnijijffScx61111,1,...,,1,...,..0,1,...,;1,...,mijjjnijijmnijijijzajnxpimstxdximjn（LP1）其中ja由上层规划决策确定。从内陆集散中心到出口港的运输问题即下层规划的第二个模型为：211mintnijijkfSgz1111,1,...,,1,...,..0,1,...,;1,...,tijj