第10章-双层规划解析.ppt

1、,第10章 双 层 规 划,BiLevel Programming,层次性是系统的六大特征之一。 社会-不断发展，实际问题-规模越来越大，结构越来越复杂，进行决策的人也越来越多，而且这些决策者各自处于不同的层次上。 一般，高一级决策机构（者）对下一级决策机构（者）行使某种控制、引导权，而下一级决策机构（者）在这一前提下，亦可以在其管理职责范围内行使一定的决策权，但这种决策权处于从属地位。,10.1双层规划简介,另外，在这种多层次决策系统中，每一级都有自身的目标函数。 高层机构的决策目标：重要、权威、具有全局性。 最终的决策结果往往是寻求使各层决策机构之间达到某种协调的具体方案。,10.1双层规

2、划简介,既可使最高层决策机构的目标达到“最优”，也可使作为上级决策“约束”的较低层决策机构的目标在从属位置上相应达到“最优” 。,一般称具有以上基本特征的决策问题为主从递阶（或多层）决策问题。 主从递阶决策问题最初是由Von Stackelberg于1952年在研究市场经济问题时提出的. 因此此问题有时候也称为Stackelberg问题，是一对策论问题，决策者有上下层关系和不同目标，但策略集通常是彼此分离。,20世纪60年代，Dantzig和Wolfe提出了大规模线性规划的分解算法，相当于承认有一个核心决策者，他的目标高于一切，其他各层次的决策者实现自己的目标只不过是为实现核心决策者的目标的一

3、种分工。 现在的多层规划承认有最高决策者，但允许下层决策者有各自不同的利益。,20世纪70年代发展起来的多目标规划通常是寻求一个决策者的互相矛盾的多个目标的折衷解，有些技术，如分层优化，也可用来求层次问题，但下层决策不影响上层，可以逐层独立求解。 而当前的多层规划正是要强调下层决策对上层目标的影响，因此多层规划问题通常不能逐层独立求解。,20世纪70年代以来，人们在各种现实的层次分散系统优化决策问题的研究中，遇到了用上述方法不能解决的实际问题，开始寻找各种特定的方法解决这些问题，逐渐形成了多层规划的概念和方法。 如：Cassidy(1971)的政府政策效力分析，Kyland(1975)的经济层

4、次分析，Bracken (1973-1977)等人的战备武器配置研究，Candler和 Norton(1977)的奶制品工业模型和墨西哥农业模型等。,多层规划（Multilevel Programming）一词就是Candler和 Norton在其论文中提出的，它的原意是一组嵌套着的数学规划问题，即在约束条件中含有优化问题的数学规划。 20世纪80年代至今，多层规划的数学模型更加明确和形式化了，国内外学者也发表了许多有意义的成果。,总之，在过去20年中，多层规划的理论、方法及应用都有很大发展，正在逐渐形成一个新的运筹学分支。目前，很多国家对多层规划的研究都非常重视，把它列为科学基金资助项目，并

5、取得了巨大成功。,最为常见且得到广泛研究与应用的多层规划是双层规划问题，即考虑只有两层决策者的情形。 这是因为现实的决策系统大都可以看成双层决策。 例如：中央和地方，公司和子公司，工厂的厂部和车间，高校的校部和院所等。实际上任何多层决策系统都是一系列双层决策系统的复合。,双层规划是具有两个层次系统的规划与管理（控制）问题。 很多决策问题由多个具有层次性的决策者组成，这些决策者具有相对的独立性，即是说上层决策只是通过自己的决策去指导（或引导）下层决策者，不直接干涉下层的决策；而下层决策者只需把上层的决策作为参数或约束，它可以在自己的可能范围内自由决策。,如果组成这种上、下层关系不止一个时，这样的

6、系统为多层决策系统。 如果只有一个上、下层关系时，这样的系统通常称为双层规划问题。 由此可见，双层规划问题虽然是多层决策系统的特殊形式，但它是最基本的形式。,双层规划： 双层规划是双层决策问题的数学模型，它是一种具有双层递阶结构的系统优化问题，上下层问题都有各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响。,双层规划的意义在于： 可以同时考虑全局和个体双方的利益，并保证首先从全局出发，体现了顾全大局、先集体后个人的思想。 目标是做到既不舍小家，又能顾大家。 可以很好地解决许多实际问题。,上层决策

7、部门： 决策变量：,下层决策部门： 决策变量：,相互作用,上层给下层一定的信息，下层在这些信息下，按自己的利益或偏好做出反应（决策）， 上层再根据这些反应，做出符合全局利益的决策。,双层规划决策过程,如果每个决策者都按规定的指标函数在其可能范围内做出决策，那么，双层决策系统可能描述为双层规划问题。 如果每个决策者的指标函数由单个函数组成，这样的双层规划为双层单目标规划问题。 如果有的决策者的指标函数是一组函数，这样的双层规划问题为双层多目标规划问题。,8.2双层规划特点,双层规划问题一般具有如下几大特点： 层次性系统分层管理，下层服从上层，但下层有相对的自主权。 独立性各层决策者各自控制一部分

8、决策变量，以优化各自的目标 。 冲突性各层决策者有各自不同的目标，且这些目标往往是相互矛盾的 。,10.2双层规划特点,优先性上层决策者优先做出决策，下层决策者在优化自己的目标而选择策略时，不能改变上层的决策 。 自主性上层的决策可能影响下层的行为，因而部分地影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允许范围内，下层有自主决策权 。,10.2双层规划特点（续）,制约性下层的决策不但决定着自身目标的实现，而且也影响上层目标的实现，因此上层在选择策略优化自己的目标时，必须考虑到下层可能采取的策略对自己的不利影响 。 依赖性各层决策者的容许策略集通常是不可分离的，形成一个相关联

9、的整体。,10.3双层规划模型的基本形式,其中 由下述规划求得,（U）,（L）,上层决策者通过设置 的值影响下层决策者。下层决策变量 是上层决策变量的函数，即 ,这个函数一般被称为反应函数。,一般来说，双层规划模型具有如下形式,10.3双层规划模型的基本形式,与一般的数学规划不同，即使当 、 、 和 都是连续函数，并且上下层的约束集合有界闭的，（ ）也可能没有最优解。,假设上层选择了点 ，那么下层面临的是以 为参数的简单最小值最优化问题。在有些情况下，对固定的 ，下层对应的最优问题可能包含不止一个最优解。,什么情况下会有这种问题？,如：如果所有的函数都是线性的，很可能当 固定的下层问题的所有最

10、优解组成一个集合 ，这意味着 中的任何一点对下层是无差别的，但对上层的目标函数可能会有差别。上层最优解可能只在 中某个特定点上达到，但是没有办法使下层更愿意选择该点。,双层规划分类,线性双层规划：所有目标函数和约束全为线性函数 非线性双层规划：上下层目标函数和约束中少有一个非线性函数 相应的有整数线性双层规划、整数非线性双层规划等,关于双层规划的一些定义,记(BP)的约束域为,定义2.1 对每个固定的 ，称 为下层问题的可行解集合， 为下层问题的合理反应集。,在上层决策空间上的投影为,关于双层规划的一些定义,定义2.3 如果存在 ，对任意 的满足 称 是(BP)的全局最优解或最优解。,定义2.

11、2 称 为(BP)的可行解集合或诱导域。,双层规划的一阶必要条件,设 是双层规划的最优解，则其一阶必要条件为：,（1） ， ， ， 都是一阶连续可微函数；,（2）对 ，下层问题有唯一解；,（3）存在 ，使得 是下列问题的可行解：,例2.1 , 其中 解,8.3双层规划的基本形式,该例的最优解在点D上达到，即 =(16,11)， 在点E(10,14)处，上层目标函数值更优。点A(0,5)是问题的一个局部最优解。,求解双层规划问题是非常困难的。原因: 双层规划问题是一个NP-hard问题。 双层规划的非凸性。,10.4双层规划计算复杂性,即使能找出双层问题的解，通常也只可能是局部最优解而非全局最优

12、解。,由于双层规划问题和博弈论具有一些类似的特性，因此可以利用博弈论中的一些方法来限定双层规划问题解的范围。在博弈论中，同两个选手分别控制各自的决策变量相比，如果一个选手能控制所有的决策变量，那么，这个选手就能更好的优化其自身的目标。,10.4双层规划计算复杂性,10.4双层规划计算复杂性,其中 由下述规划求得,（U）,（L）,第一种情况： 如果下列双层规划的最优解为,10.4双层规划计算复杂性,第二种情况： 如果上层决策者控制所有变量，双层规划变为,设其最优解为,10.4双层规划计算复杂性,其中,第三种情况： 如果上下层决策者分别独立控制各自的决策变量，双层规划变为,设其最优解为,10.4双

13、层规划计算复杂性,那么有下式存在：,除双层规划外，后两种情况都是求单层规划，较容易，因此可不直接求双层规划，而直接求后两类单层规划，然后尽量减小 与 ， 与 之间的差异。,其中 解,对上述问题，当 时，由 ，得 。当取 时，下层问题的最优目标函数值 ，但下层问题的最优解不唯一，满足 ，显然这对上层目标函数 产生影响。当 时， ；当 时， 。,10.4双层规划计算复杂性,上述例子说明： 当上层给定一个允许决策后，如果下层问题的最优解不唯一，将导致整个求解的复杂性，甚至无法保证能求得问题的最优解。,10.5双层规划求解算法,对于双层规划是上层先进行决策，为了说明这种顺序的重要性，考虑下面的例子。,

14、其中 求解,10.5双层规划求解算法,例2.3,10.5双层规划求解算法,值,值,上层,下层,同时决策,由表可以看出决策顺序很重要，如果控制 变量的选手先决策，它的最小费用要比后选择策略或两选手同时决策要优。,到目前为止，对于双层规划的求解算法归纳起来，可以分为五大类：,10.5双层规划求解算法,（1）极点搜索法（Extreme Point Search Method）：这种方法主要用于求解双层线性规划，其基本观点就是：双层线性规划问题的任何解都出现在下层问题的约束集合的极点位置。因此，首先可以利用各种方法来寻找约束空间的极点（不要求寻找全部极点），然后从中再找出双层问题的局部最优解或全局最优

15、解。,10.5双层规划求解算法,（2）K-T法（Karush-Kuhn-Tucker Method，简称K-T法） ：这种方法将双层问题中的下层问题用它的Karush-Kuhn-Tucker条件代替，主要用于求解双层线性规划问题，最初用于求解双层线性资源控制问题。,（3）下降法（Descent Method） ：这种方法是基于用各种可能的方法得到的下层问题对上层决策变量的梯度信息，主要用于求解非线性连续变量的双层规划问题。从本质上讲，这是一种迭代求解方法，利用得到的下层问题对上层决策变量的梯度信息来产生一系列使上层目标函数减小的点。最具代表性的下降算法是基于灵敏度分析的求解算法。,10.5双层

16、规划求解算法,（4）直接搜索法（Direct Search Method） ：直接使目标函数最小的方法，如Abdulaal和LeBlanc（1979）使用的Hooke-Jeeves搜索法就属于此类，在搜索解的过程中，这种方法取决于上层目标函数值的变化。,10.5双层规划求解算法,（5）非数值优化方法：这类方法主要包括模拟退火、遗传算法和蚁群算法等。这种非数值优化方法目前主要用来求解城市交通连续平衡网络设计问题（Cree和Masher，1998）及其它相关优化问题，但由于此类求解算法在求解双层规划模型时具体的参数（如编码长度等优化参数）难以确定，所以收敛性一般难以保证，况且在实践应用中可解释性也

17、不理想。所以在求解具体双层规划模型时还属于探索阶段。,10.5双层规划求解算法,10.6双层规划的应用,（1）交通 已有大量文献将双层规划应用于交通领域。 网络设计问题（Network Design Problem）。,相互作用,网络规划者决定投资费用 目的使网络中系统费用最小,用户选择出行路径 目的使自己的出行费用最小,相互作用,投资费用 运行费用 取决于交通流量,10.6双层规划的应用,（1）交通 O-D（Origin-Destination）需求估计问题。 交通信号控制问题。如何进行信号控制，使车辆使用者作出合理反应，减少交通堵塞和延迟，也可作为双层规划问题来进行优化解决。,10.6双层

18、规划应用（续）,（2）管理 只顾自己的局部利益，而忽略了整体利益，是目前管理中存在的一个比较普遍的问题。双层规划的特点恰恰是从整体的角度出发，兼顾全局，希望达到整体最优。因此，在管理问题中应用双层规划方法，将会取得很好的效果。这方面的研究也比较多。,10.6双层规划应用（续）,（2）管理 资源分配。资源分配是一类比较复杂的管理问题，上层部门将资源分配给多个下层部门，下层部门根据分配的资源和自己已有的资源组织生产，使自己的效益最大。一些公共设施建设，如电站、水库、污物处理站建设等，实质上也是资源分配问题，只不过下层不是部门的效益最大，而是公共设施产生的社会效益最大。 价格问题。例如应用到铁路旅客

19、票价制定问题。,10.6双层规划应用（续）, 供应链管理。供应链管理的重要性得到认可。过去，厂商与其供应商持敌对态度，都想从对方那里获得利润，导致产品开发周期过长、产品质量无法提高、成本居高不下等问题。如何使厂商与供应商紧密合作，达到双赢的目的，成为一个热点研究问题。建立双层规划模型，以各成员利润最大化为下层目标，以供应链的综合绩效为上层目标，来进行优化研究，具有重要的应用价值和现实意义。,10.6双层规划应用（续）, 生产计划。 其它方面如兵力部署、设施定位、政策规划等。 （3）工程设计问题。,城市交通网络设计问题,10.7.1城市交通平衡网络设计问题 交通运输供给能力的不足，严重影响了旅客

20、和各种商品在自然空间上的合理流动，阻碍了国民经济的快速发展，为了克服这一现象，就需要增加交通运输能力，为此必须增加对交通基础设施建设的投资力度 。,10.7 双层规划在城市交通网络平衡设计问题中的应用,资金不足是最大障碍,网络设计时 需要决策,10.7 双层规划在城市交通网络平衡设计问题中的应用,实质上是在一定约束条件下的最优投资决策问题。,对现有交通网络进行改进,城市交通 网络设计 问题研究 内容,资金投 入最少,增加新的路段或更新 改善已有路段的能力 调整路口的交通信号 建设立交桥等,使整个交 通网络某 种系统性 能最优,10.7.2用双层规划描述城市交通网络设计问题 利用一定的投资对交通

21、网络进行改善由交通规划部门决策，但改善后的路网效果如何需看用户的出行反应。因此城市交通网络设计问题可以用双层规划进行描述。 网络设计问题就是在考虑了投资对整个系统中的供应方和需求方的影响之后，寻找并选择最优投资策略使系统的社会福利最大。,10.7 双层规划在城市交通网络平衡设计问题中的应用,在进行网络设计时，如果不考虑网络用户的路径选择行为，而一味的增加或改建已有路段，有时不仅不能达到改善整个系统交通状况的目的，反而会使整个系统的交通状况更加恶化，表现为系统总费用不仅没有减少，反而会增加。 （举例） 因此在进行交通网络设计时，必须考虑网络中用户的路径选择行为，即进行规划时要考虑路网改建后是否能

22、达到预先所期望的目标。,10.7 双层规划在城市交通网络平衡设计问题中的应用,10.7 双层规划在城市交通网络平衡设计问题中的应用,考虑一个网络如图所示，有四条路段，四个节点，一个O-D对（从节点O到节点D，总需求量为6）。路段14的阻抗函数（单位为：分钟）分别为：,O,D,1,2,3,4,网络中只有两条路径，第一条通过节点1、3（用13表示），第二条通过节点2、4（用24表示）。由于网络的对称性，O-D需求量平均分配到两条路径13和24上。每条路径上流量为3。,10.7 双层规划在城市交通网络平衡设计问题中的应用,10.7 双层规划在城市交通网络平衡设计问题中的应用,现增加一条路段5，其路段

23、阻抗函数为：,此时，网络中又出现了第三条路径,通过节点1、5、4（用154表示）,5,这个新网络的UE解是,可见增加网络固定设施通行能力后，并未如预料的那样减少拥挤程度，反而增加了。,其中 由下述规划求得：,10.7 双层规划在城市交通网络平衡设计问题中的应用,因此，双层网络设计模型就是在满足投资预算约束条件下，考虑了网络用户路径选择行为后，寻找最佳路网改进方案 使系统目标函数最优。,交通规划者为了 达到使社会效益 最大而采取的最 优决策,反映了网络中用户 的路径选择行为,上层规划,下层规划,铁路旅客票价制定的双层规划模型,国外铁路运价决定原理主要： 运输价值原则: 所研究的运输服务对需求者的

24、使用价值或效用。,需求价格,表示的是旅客票价的最高限度，如果旅客票价高于这个价格，旅客就会放弃选择铁路作为出行方式，而选择其他的交通方式（公路或民航）。,铁路旅客票价制定的双层规划模型,表示的是旅客票价的最低限度，如果旅客票价低于这个价格，铁路客运部门就难以在客运市场中生存和发展。,运输成本原则: 运价应当等于运输服务的生产费用。,供给价格,铁路旅客票价制定的双层规划模型,在市场经济条件下，铁路旅客票价的制定应该兼顾成本和市场需求两方面的因素。,上层决策部门：铁路管理部门 决策变量：铁路客票价格,下层决策：旅客的出行行为 决策变量：交通流量,相互作用,决策部门只能通过政策和管理来影响旅客在出行

25、时对于运输方式的选择，例如通过票价的调整来使得旅客的选择行为发生改变，但不能控制他们的选择。 旅客都是根据自己的需要及习惯来选择运输方式。,10.8 铁路旅客票价制定的双层规划模型,出行者希望自己总的出行费用最低； 铁路客运管理部门总是希望铁路的客运收入最大。 这看起来是相互矛盾的，但这两方面相互作用的结果是取得共同的平衡点，即上述双层规划问题的最优解。,10.8 铁路旅客票价制定的双层规划模型,其它因素不变,铁路票价上升,铁路客流量减少， 转移到其它运输方式,铁路票价下降,铁路客流量增加， 吸引其它运输方式 的客流,10.8.1 多种交通运输方式竞争条件下铁路客票价格制定的双层规划模型,10

26、.8 铁路旅客票价制定的双层规划模型,城市之间的客流分配，一般不存在路径的选择，而只有运输方式的选择,10.8 铁路旅客票价制定的双层规划模型,从定量角度出发，既保障了出行者使自己的出行费用最小，又能使铁路客运在市场竞争中取得最大的经济效益。,上层规划: 描述为铁路客运管理部门 在政府规定的范围内制定最佳的客票 价格以使铁路客运的经济效益为最大。,下层规划:描述城市间多模式运输竞争 条件下，客流在不同运输方式之间的 分配模式，目标是使每个出行者在出 行过程中的出行费用最低。,一般情况下，旅客总是力图选择从起点到终点之间总的广义出行费用最低的客运运输方式，,10.8 铁路旅客票价制定的双层规划模

27、型,出行时间、旅客票价、安全、方便舒适度等,比如铁路，假定一开始它的出行费用是最低的,如果所有出行者都选择某一种客运运输方式。,那么随着该运输方式客流需求的增加，它总的出行费用就会上升，例如票价上升，出行时间变大，服务质量下降等。使得一部分旅客放弃选择这种运输方式，而选择其它运输方式，而别的运输方式出行费用也会随客流需求的增加而上升。,最终，在不同的客运运输方式之间会达到一种客流分配的稳定的均衡状态。这种均衡状态可以描述为：在城市之间的所有可供选择的客运运输方式中，旅客所利用的各种客运运输方式的广义出行费用全部相等，并且不大于未被利用的客运运输方式的出行费用。,10.8 铁路旅客票价制定的双层

28、规划模型,10.8 铁路旅客票价制定的双层规划模型,可以用下面的数学形式来描述这种均衡状态,如果 如果,其中 表示城市间第 （ ）种运输方式的广义出行费用， 表示均衡状态下城市间的广义出行费用， 表示城市间第 （ ）种运输方式的客流量， 为城市间所有运输方式的集合。,10.8 铁路旅客票价制定的双层规划模型,其中函数 是运输方式的广义费用函数，在这个函数中不同运输方式的客流量是自变量，即 （ ）。 取不同的形式，便可以得到不同的客流量在客运运输方式之间的分离模式，最常用的广义费用函数形式有幂函数形式和对数函数形式。,第一个约束表示城市间总的客流需求是已知并且固定的， 表示表示城市间总的客流需求

29、；最后一个约束为变量的非负约束。,（U） 其中 由下层模型得出 （L）,表示城市间铁路客运的客流量， 表示城市间铁路客运的旅客票价， 表示铁路客运中的平均客运成本。 and 分别表示城市间的铁路客运的平均客运成本和旅客票价最高限。 可以理解为适当的运输成本与适当的利润之和， 可以理解为是的运输成本与政府允许的利润上限之和(或消费者能承受的最大担负能力)。,10.8 铁路旅客票价制定的双层规划模型,铁路旅客票价制定的双层规划模型,例：确定从北京到天津合理的铁路旅客票价,费用综合考虑出行时间、票价、方便性、舒适性、安全性等多种因素。 根据京津唐客运市场调查报告北京到天津的总客运量约25000。 从

30、北京到天津存在两种运输方式：铁路和公路,铁路旅客票价制定的双层规划模型,其中为 出行时间因素， 表示票价因素， 为方便、舒适和安全等综合因素； （ ）为待定参数。,表示不同运输方式的效用， 为待定参数。,铁路旅客票价制定的双层规划模型,我们可以把物流中心的选址问题看作一个领导者和跟随着（Leader-Follower）问题，其中决策部门是指导者（Leader），客户对物流中心的选择行为或者客户需求在各物流中心的分配为跟随者（Follower）。决策部门可以通过政策和管理来改变某个物流中心的位置和配送成本，从而影响客户对物流中心的选择，但不能控制他们的选择。客户则对现有的物流中心进行比较，根据自

31、己的需求特点和行为习惯来选择物流中心。这种关系我们可以用双层规划模型来描述。,10.9 物流中心选址问题,10.9 物流中心选址问题,上层决策部门：物流规划部门 决策变量：物流中心的备选地点,下层决策部门：用户 决策变量：用户需求在各 物流中心的分配量,相互作用,上层规划可以描述为决策部门在允许的固定投资范围内确定最佳的物流中心的地点以使得总成本最小（包括固定成本和变动成本）。,下层规划则描述了在多个物流中心存在的条件下，客户需求量在不同物流中心之间的分配模式，它的目标是使每个客户的费用最低。,10.9 物流中心选址问题,其中 为第 个客户由 地点的物流中心提供服务的广义单位费用，这里假定它仅

32、是需求量的函数，一般随着分配需求量的增大，广义费用也增加； 为第 个客户在地点 的物流中心得到满足的需求量； 为在 地建物流中心的固定投资； 表示在 地建物流中心时，此值为1，否则为0。,上层规划为：,10.9 物流中心选址问题,下层规划为：,其中 为客户点 的总需求量， 为一任意大的正数。 下层规划表示客户对物流中心的选择行为，即各个用户在各物流中心间分配需求量，以使其总费用最小。从宏观上讲，下层规划主要是得到客户需求量的分布情况。,第一个约束保证每个用户的需求都能得到满足；第二个约束保证需求量总是在已建的物流中心处分配；最后一个约束为变量的非负约束。,模拟退火算法是模仿热力学中固体退火的随机机制设计的。 在热力学中，当一个物理系统（固体）处在高温时，它的大量的原子是处于无序的高温运动状态。为使原子进入有序状态，要减少该系统的温度。,如要使该固体变成晶体（晶体的原子是高度格型有序排列的），就要首先将固体加热到能使其原子可进行重新排列的高温，然后逐步小心地冷却它，使其在每个温度级都能达到热平衡状态，直至它冷却成晶体为止。这样的冷却过程就叫“退火（annealing）”。,求解双层规划的模拟退火算法,所谓的热平衡状态就是指其中任何原子具有能量 的概率服从Boltzman（波茨曼）分布：,Metropolis于1953年模仿上述热力学的退火方法发明了一个计算多下峰目标函数优