发展规划-双层规划.doc

双层规划
双层规划的定义及背景
双层规划（BilevelProgrammingProblem，简称BLPP）是一种具有二层递阶结构的系统优化问题，上层问题和下层问题都有各自的决策变量、约束条件和目标函数。
双层系统优化研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者，并不直接干涉下层的决策；而下层决策者只需要把上层的决策作为参数，他可以在自己的可能范围内自由决策。这种决策机制使得上层决策者在选择策略以优化自己的目标达成时，必须考虑到下层决策者可能采取的策略对自己的不利影响。
，上世纪50年代，为了更好的描述现实中的经济模式，，虽然多层规划与之有共同点，但各层决策者依次做出决策，并且各自的策略集也不必再是分离的。20世纪60年代，Dantaig和Wolfe提出了大规模线性规划的分解算法，承认有一个核心决策者，它的目标高于一切，但与多层规划有很大区别，多层规划承认有最高决策者，大不是绝对的，他允许下层决策者有各自不同的利益。20世纪70年代发展起来的多目标规划通常寻求的是一个决策者的互相矛盾的多个目标额折衷解，而多层规划强调下层决策对上层目标的影响，并且多层规划问题通常不能逐层独立求解。
上世纪70年代以来，在解决实际问题的过程中，人们才逐渐形成多层规划的概念和方法。多层规划（MultilevelProgramming）一词是Candler和Norton在奶制品工业模型和墨西哥农业模型的研究报告中首先提出来的。
上世纪70年代，人们对多目标规划进行了深入的研究，也形成了一些求解多目标规划的有效方法，如分层优化技术，这种技术也可以用来求解层次问题，但这种技术建立在下层的决策不影响上层的目标基础上，而多层规划正是强调下层决策对上层目标的影响。因此多层规划同城不同于多目标规划。
在过去的几十年中，多层规划的理论、方法及应用都有了很大的发展，并且已经成为规划论中的一个新的重要分支，而在多多层规划的研究中，双层规划是一个重要的研究对象，这是因为双层规划是多层规划中的一个特例，同时多层规划可以看作是一系列的双层规划的复合。
双层规划是在研究非平衡经济市场竞争时首先提出的，1973年，在Bracken和Mcgill的文章中，出现了双层规划的数学模型。1977年，在Candler和Norton的科学报告中正式出现了双层规划和多层规划名词。
双层规划研究的是两个各具目标函数的决策者之间按有序的和非合作方式进行的相互作用，上层决策者优先做出决策，下层决策者在上层决策信息下按自己的利益做出反应，由于一方的行为影响另一方策略的选择和目标的实现，并且任何一方又不能完全控制另一方的选择行为，因此上层决策者要根据下层的反应做出符合自身利益的最终决策。
根据上述定义，双层规划具有以下一些主要特点：
（1）层次性。研究的系统是分层管理的，各层决策者依次做出决策，下层服从上层。
（2）独立性。各层决策者各自控制一部分决策变量，以优化各自的目标。
（3）冲突性。各层决策者有各自不同的目标，且这些目标往往是相互矛盾的。
（4）优先性。上层决策者优先做出决策，而下层决策者在优化自己的目标而选择决策时，不能违背上层的决策。
（5）自主性。下层并不是完全无条件服从上层，它有相当的自主权。
（6）制约性。下层的决策不但决定着自身目标的达成，而且影响着上层目标的实现。
（7）依赖性。各层决策者的容许策略集通常是不可分的，他们往往形成一个相互关联
的整体。
常见双层规划的分类
（1）线性双层规划
线性双层规划（LinearBilevelProgramming，简称LBM）是双层规划的一个特例，其上、下层目标函数和约束条件都是线性的，是双层规划中最为常见且形式最为简单的一种情况，在实际中应用十分广泛，主要涉及管理决策、交通网络布局、工程设计等诸多方面。
一般来说，求解线性双层规划问题是非常困难的，Jeroslow指出线性双层规划是一个NP—hard问题，Ben—Ayed及Bard对此结论给出了简短的证明；Hallsen对性双层规划是强NP一hard问题给出了严格的证明。后来，Vicente指出，寻找线性双层规划的局部最优解也是NP一hard问题，不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的，它也可能是一个非凸问题，.并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。
自20世纪70年代以来，己提出了几十种求解线性双层规划的算法，主要有以下几
类不同的算法：
（a）极点算法：极点搜索思想的理论基础是线性双层规划的最优解必在诱导