双层规划.doc

双层规划

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

二、 常见双层规划的分类
（1）线性双层规划
线性双层规划（Linear Bilevel Programming，简称LBM）是双层规划的一个特例，其上、下层目标函数和约束条件都是线性的，是双层规划中最为常见且形式最为简单的一种情况，在实际中应用十分广泛，主要涉及管理决策、交通网络布局、工程设计等诸多方面。
一般来说，求解线性双层规划问题是非常困难的，Jeroslow指出线性双层规划是一个NP—hard问题，Ben—Ayed及Bard对此结论给出了简短的证明；Hallsen对性双层规划是强NP一hard问题给出了严格的证明。后来，Vicente指出，寻找线性双层规划的局部最优解也是NP一hard问题，不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的，它也可能是一个非凸问题，.并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。
自20世纪70年代以来，己提出了几十种求解线性双层规划的算法，主要有以下几
类不同的算法：
（a）极点算法：极点搜索思想的理论基础是线性双层规划的最优解必在诱导域的极
点处取得。首先可以利用各种方法来寻找诱导域的极点，然后从中再找出线性双层规划
问题的局部最优解或全局最优解。
（b）分枝定界法：其基本思路是，根据事先选定的分枝准则，将所求解的问题分成
一系列子问题，并从中选取一个子问题进行检验，决定其取舍。分枝定界法计算量很大，
但它能求得全局最优解。
（c）K-T法：其基本思路是将线性双层规划问题中的下层规划问题用它的Kuhn一Tucke:条件代替，将线性双层规划问题化为单层非线性规划问题求解，最初用于求解线性双层资源控制问题。这种算法仅对线性约束的上层和凸二次规划的下层这种特殊情况有效。
（d）模糊数学算法：其基本思路是充分利用模糊集理论中隶属函数及模糊算子的概念和性质，分别建立上层决策变量的隶属函数和上、下层决策者目标函数的偏好隶属函数，双层决策问题转化为单层优化问题，分别对各单层规划的解进行讨论，最终把线性双层规划转化为求解一个线性规划问题，求得两层决策问题的满意解。
（2）凸双层规划
凸双层规划（Convex Bilevel Programming），即上层目标函数是凸函数，下层目标函数是凸二次函数，约束条件均为线性的一类非线性双层规划。对这类问题，在一定条件保证下，将原问题转化为一个单层的数学规划，通过对其对应的松弛问题有关性质的讨论，给出恰当的定界规则和分支原则，隐含地考虑到互补松弛条件的所有组合，利用分支定界技术给出一种求全局解的算法。
（3）混合整数线性双层规划
整数规划一类要求问题中的全部或一部分变量为整数的数学规划。 一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。
（4）非线性双层规划
双层规划（Non-linear Bilevel Programming，简称NLBP）的一般形式为：
（a）
（b）
（c)
（d）
其中，，。则上层变量，下层变量。同样，函数、分别是上层、下层目标函数，而向量值函数、分别是上层、下层约束条件。上层约束条件中包含着来自两层变量（与用表示的约束不同）是一个特殊的角色，因为这些条件不能约束下层决策者，它们不直接的被强制执行。
如果上下层目标函数、至少有一个非线性的，称之为非线性双层规划。此外，如果上下层变量在 增加整数约束，称之为证书双层规划。

三、 常见双层规划的模型及其应用
在双层规划模型中，不同的决策者控制着相应的决策变量，并优化各自的目标函数。下层决策者首先进行决策，这样上层决策者必须预测到下层可能的反应。下层根据上层的决策进行反应，以优化个人的目标函数。因为双方可供选择的策略集是相互依赖的，上层的决策会影响下层可选的决策和目标的实现，反之亦然。
设上层决策者控制的变量为；下层决策者控制的变量为。
（a）下层以最优解反馈到上层的双层规划数学模型为：
（BP）

（b）下层以最优值反馈到上层的双层规划数学模型为：

其中，，，，集合和集合包含了变量的其他约束，如变量的非负性或整数要求等。
对于上述双层规划问题（），即使当，，，均是连续函数，并且集合和是紧集，（）也可能没有最优解。导致这种可能性的原因是对某个，下层问题可能有多个最优解，下面的例子将说明这种情况。
例1.1

，
点实现了上、下层目标函数的最小值，但对于固定的点， 下层决策者可以选择任何满足和的正数，，这样的，对下层都是可行的，而且都是最优的，但上层目标函数值却是不一样的，当，
时，；而下层也可以选择，，这样下层目标函数值，而上层目标函数值。因此下层问题懂得多解性导致上层问题可能得不到最优解。 当然下层问题的多解性不仅会导致双层规划的无解，而且还会对双层规划问题产生许多影响。

1、双层规划在区域港口内陆运输网络上的应用
　1）基本参数
可以建设港口内陆集散中心的潜在地点的数量；
在第j 地建港口内陆集散中心的最大允许容量；
在第j 地建内陆集散中心的固定成本费用；
在第j 地建内陆集散中心的变动成本费用；
从生产地i 到内陆集散中心j 的单位运输费用；
从内陆集散中心j 到出口港k 的单位运输费用；
生产地i 的生产量；
出口港k 的容量；
d总运输需求量。
　2）决策变量
，，表示在第j 地建内陆集散中心；= 0 ，表示在第j 地不建内陆集散中心。
，表示在第j 地建内陆集散中心的容量；
，货物从生产地i 到集散中心j 的运输量；
，货物从集散中心j 到出口港k 的运输量。
上层规划可以描述为物流规划部门在满足运输总需求的条件下确定货物集散中心的数量和规模,使得总成本（固定成本和变动成本）最小；下层规划描述了在多个货物集散中心和出口港口存在的条件下，物流服务企业的运输量在不同运输路线的分配，使得物流服务企业的总运输成本最小。
对于上层规划来说,其数学模型为：

（P）
当上层规划达到最优时，即确定了各港口内陆集散中心的容量，则下层规划便根据上层规划确定的各集散中心的容量，,寻求最优的运输方案,这里包含两个运输问题，一个是从生产地运到内陆集散中心，另一个是从内陆集散中心运往出口港。
从生产地到内陆集散中心的运输问题即下层规划的第一个模型为

（LP1）
其中由上层规划决策确定。
从内陆集散中心到出口港的运输问题即下层规划的第二个模型为：

（LP2）
因而整个问题形成一个双层规划问题,即求解如下的数学规划问题：

（BP）
其中：，由下述规划所确定：
（LP1）

（LP2）
其中
我们把上述双层规划归结成一个值型双层规划。上层规划确定了各个内陆集散中心的容量，,下层规划根据内陆集散中心的容量确定最佳运输方案，以求得最小费用。

2、双层规划在宏观调控上的应用
国民经济系统包含了众多个厂商、众多个消费者和政府等三类行为主体。整个市场体系既涉及了产品市场，又涉及了要素市场。其中产品市场不仅考虑了其供求状况。同时还考虑了国际市场中的对外贸易情况；而要素市场主要考虑了资金市场和劳动市场的供求状况。
1）厂商
设国民经济系统中共有l 个厂商，生产m 种产品，并记厂商集合为，记产品集合为。
2）消费者
设国民经济系统中共有个消费者，并记消费者集合为，其个人收入分别记为，。
3）政府
在现代宏观经济中。政府是极其重要的行为主体, 它要对国民经济进行干预和调控。进而保证其平稳有序地运行（政府的另外一个作用在于它是构成总需求的重要方面）。
4）市场
产品市场：记第种产品的价格为，这里是模型的外生变量。无论对于单个厂商还是对于单个消费者来说它都是常数，。设第j 种产品的投资需求、政府需求以及净出口总和为IGNX。
A、 上层规划模型
根据上面的描述可以得到政府追求社会福利最大化的上层规划模型为：
；

其中: 式(1)是产品市场供求平衡约束条件，式(2)是资金市场供求约束条件, 式(3) 是劳动市场供求约束条件,式(4) 是转移支付约束条件( 它表明政府的个税收入至多全部补贴于低收入者)，式(5) 是基本效率约束条件( 它要求政府对消费者征收个人所得税后, 其个人可支配收入的排序与初始收入的排序应是一致的)，式(6)是政府宏观调控变量和其他模型内生变量非负或非正约束条件。需要特别指出的是: 厂商的决策变量和消费者的决策变量由下层规划模型求解得出。
B、 下层规划模型
在国民经济系统这一递阶系统中，处于下层的是众多厂商和众多消费者。他们在产品价格和政府宏观调控变量给定的前提下进行最优决策。
可得到厂商追求利润最大化的优化模型为:
；

其中: 式( 7) 是厂商生产可行性约束条件, 式(8)是厂商决策变量的非负约束条件。
可得到消费者追求效用最大化的优化模型为:
；

其中: 式(9)是消费者收入约束条件,式(10)是消费者决策变量的非负约束条件。
由此可见下层规划模型是由个以产品税率、资金利率、劳动工资率为参数的线性规划和个以个人所得税率为参数的非线性规划共计()个规划组成. 所以基于双层规划的宏观经济调控模型为:
；

3、双层规划在供应链中的应用
供应链网络设施选址是一个重要的基础性决策问题, 它直接影响到供应链系统运作中的相关成本。由于顾客需求的日益多样化和全球动态经济环境的逐渐形成, 使企业间的竞争日趋激烈。目前解决此问题已形成了多种方法, 按选择的离散程度大致可分为连续选址模型和离散选址模型两种。
供应链选址双层规划模型的建立：在实际的物流中心选址决策中，在新物流中心建立前一般已存在若干个旧物流中心，这些物流中心之间存在着竞争，也就是说客户需求不仅仅由新建的物流中心满足, 有一部分需求可能由已有物流中心提供。针对于此建立了改进的基于
竞争的供应链物流中心选址双层规划模型。
A、上层规划模型
上层规划( U)可以描述为决策部门在允许的固定范围内确定最佳的新选物流中心的中点以使总成本最小（包括固定成本和可变成本）。而下层规划( L) 则描述了在多个物流中心存在的条件下，客户需求量在不同物流中心之间的分配模式，它的目标是使每个客户的费用最低。具体模型如下所示。
（1）
（2）
（3）
（4）
（5）
（6）
（7）
式中：
—地点的配送中心为第个客户提供服务所需支出的单位费用；
—第个客户在地点的配送中心得到满足的需求量；
—在地点建配送中心的固定投资费用；
—在地点建配送中心时，此值为1，否则为0；
—修建配送中心的总投资预算；
—从工厂到配送中心的运输量；
—从工厂到配送中心的运输单价；
—工厂的供应能力；
—配送中心的供应能力。
上层目标函数是从决策者的角度出发。使修建配送中心的总费用与满足消费者需求的费用之和最小。（1）式右边第一项代表了为满足客户需求所花费的总的可变成本；右边第二项代表修建配送中心所花费的总的固定成本。固定成本包括土地使用费、建设费和营运费等；第三项代表由上游工厂至配送中心的运送成本；（2）式保证修建的配送中心费用不超过其总投资额；（3）式保证至少建一个新的配送中心；（4）式保证从上游工厂发运到各配送中心的货物总量不超过它的供应能力；（5）式保证配送中心的货物进出总量相等；（6）式表示通过配送中心的货物进出总量相等；（7）式为变量的0-1约束。需要指出的是中由下层规划（）求得。
B、下层模型
在现实配送系统中, 由于单一客户的需求量不是由某个配送中心全部满足的, 并且还存在已有配送中心竞争的影响。所以在下层目标规划中假设已有配送中心L个, 这样K个客
户就是在n+l 个配送中心中分配他们的需求量。可以这样描述下层问题:
（8）
（9）
（10）
； （11）
（12）
式中：
—第个客户在地点的配送中心得到满足的需求量；
—第个客户选择地点配送中心服务所需要支出的单位费用；
—第个客户总的需求量；
—地点配送中心总的供应能力；
—任意大的正数。
下层规划表示客户选择最优配送中心, 即各个用户在各配送中心间分配需求量, 使用户的总支出费用最小。（9）式保证每个用户的需求都能得到满足；(10)式保证选择配送中心的各个用户的需求量之和不超过该配送中心总的供应能力；(11)式保证需求量总是在已建的配送中心处分配；(12)式为变量的非负约束。

四、参考文献
[1] 安起光,孟庆春.社会福利最大化与消费者效用最大化的关系研究[J].中国管理科学, 2002,第10卷第三期21-25.
[2] 汪传旭,蒋良奎.基于双层规划的区域港口内陆运输网络优化决策[J].管理工程学报,2008,4.第22卷第2期67-69.
[3] 张小宁.双层优化交通模型及其算法[J].同济大学学报(自然科学版),2005.第32卷2期69-73.
[4] Hong Li,Yongchang Jiao and Li Zhang.Orthogonal genetic algorithm for solving quadratic bilevel programming problems[J]. 系统工程与电子技术(英文版).2010,10,5.
[5] 刘晓.供货商选择模型与方法综述[J].中国管理科学,2004,第12卷第1期139-148.
[6] 王坚英,张仁颐.上海港国际集装箱运输系统规划[J ].上海交通大学学报,2003.
[7] 王先甲,冯尚友.二层系统最优化理论[M].北京:科学出版社,1995.
[8] 高国飞,张星臣.双层规划模型在供应链选址中的应用[J].物流技术,2008.第27卷第8期86-88.
[9] Olivier Blanchard.Macroeconomics[M].Prentice-Hall: Inc,2000.
[10] 肖剑,但斌,张旭梅.供货商选择的双层规划模型及遗传算法求解[J].重庆大学学报(自然科学版),2007,6.第30卷第6期156-158.
[11] PAN Qingfei1,AN Zhonghua.Exact Penalty Method for the Nonlinear Bilevel Programming Problem[J]. 武汉大学自然科学学报(英文版),2010,12,5.
[12] 孟庆春,安起光.基于双层规划的宏观调控模型研究[J].山东大学学报(理学版)，2006,8.第41卷第4期81-84.
[13] 赵志刚,顾新一.求解供应链分销模型的双层规划方法[J].上海理工大学学报,2006,3.第28卷第3期300-301.
12