第10章-双层规划解析

第10章双层规划BiLevelProgramming层次性是系统的六大特征之一。社会---不断发展，实际问题---规模越来越大，结构越来越复杂，进行决策的人也越来越多，而且这些决策者各自处于不同的层次上。一般，高一级决策机构（者）对下一级决策机构（者）行使某种控制、引导权，而下一级决策机构（者）在这一前提下，亦可以在其管理职责范围内行使一定的决策权，但这种决策权处于从属地位。10.1双层规划简介另外，在这种多层次决策系统中，每一级都有自身的目标函数。高层机构的决策目标：重要、权威、具有全局性。最终的决策结果往往是寻求使各层决策机构之间达到某种协调的具体方案。10.1双层规划简介既可使最高层决策机构的目标达到“最优”，也可使作为上级决策“约束”的较低层决策机构的目标在从属位置上相应达到“最优”。一般称具有以上基本特征的决策问题为主从递阶（或多层）决策问题。主从递阶决策问题最初是由VonStackelberg于1952年在研究市场经济问题时提出的.因此此问题有时候也称为Stackelberg问题，是一对策论问题，决策者有上下层关系和不同目标，但策略集通常是彼此分离。20世纪60年代，Dantzig和Wolfe提出了大规模线性规划的分解算法，相当于承认有一个核心决策者，他的目标高于一切，其他各层次的决策者实现自己的目标只不过是为实现核心决策者的目标的一种分工。现在的多层规划承认有最高决策者，但允许下层决策者有各自不同的利益。20世纪70年代发展起来的多目标规划通常是寻求一个决策者的互相矛盾的多个目标的折衷解，有些技术，如分层优化，也可用来求层次问题，但下层决策不影响上层，可以逐层独立求解。而当前的多层规划正是要强调下层决策对上层目标的影响，因此多层规划问题通常不能逐层独立求解。20世纪70年代以来，人们在各种现实的层次分散系统优化决策问题的研究中，遇到了用上述方法不能解决的实际问题，开始寻找各种特定的方法解决这些问题，逐渐形成了多层规划的概念和方法。如：Cassidy(1971)的政府政策效力分析，Kyland(1975)的经济层次分析，Bracken(1973-1977)等人的战备武器配置研究，Candler和Norton(1977)的奶制品工业模型和墨西哥农业模型等。多层规划（MultilevelProgramming）一词就是Candler和Norton在其论文中提出的，它的原意是一组嵌套着的数学规划问题，即在约束条件中含有优化问题的数学规划。20世纪80年代至今，多层规划的数学模型更加明确和形式化了，国内外学者也发表了许多有意义的成果。总之，在过去20年中，多层规划的理论、方法及应用都有很大发展，正在逐渐形成一个新的运筹学分支。目前，很多国家对多层规划的研究都非常重视，把它列为科学基金资助项目，并取得了巨大成功。最为常见且得到广泛研究与应用的多层规划是双层规划问题，即考虑只有两层决策者的情形。这是因为现实的决策系统大都可以看成双层决策。例如：中央和地方，公司和子公司，工厂的厂部和车间，高校的校部和院所等。实际上任何多层决策系统都是一系列双层决策系统的复合。双层规划是具有两个层次系统的规划与管理（控制）问题。很多决策问题由多个具有层次性的决策者组成，这些决策者具有相对的独立性，即是说上层决策只是通过自己的决策去指导（或引导）下层决策者，不直接干涉下层的决策；而下层决策者只需把上层的决策作为参数或约束，它可以在自己的可能范围内自由决策。如果组成这种上、下层关系不止一个时，这样的系统为多层决策系统。如果只有一个上、下层关系时，这样的系统通常称为双层规划问题。由此可见，双层规划问题虽然是多层决策系统的特殊形式，但它是最基本的形式。双层规划：双层规划是双层决策问题的数学模型，它是一种具有双层递阶结构的系统优化问题，上下层问题都有各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响。双层规划的意义在于：可以同时考虑全局和个体双方的利益，并保证首先从全局出发，体现了顾全大局、先集体后个人的思想。目标是做到既不舍小家，又能顾大家。可以很好地解决许多实际问题。上层决策部门：决策变量：下层决策部门：决策变量：相互作用上层给下层一定的信息，下层在这些信息下，按自己的利益或偏好做出反应（决策），上层再根据这些反应，做出符合全局利益的决策。双层规划决策过程如果每个决策者都按规定的指标函数在其可能范围内做出决策，那么，双层决策系统可能描述为双层规划问题。如果每个决策者的指标函数由单个函数组成，这样的双层规划为双层单目标规划问题。如果有的决策者的指标函数是一组函数，这样的双层规划问题为双层多目标规划问题。8.2双层规划特点双层规划问题一般具有如下几大特点：层次性——系统分层管理，下层服从上层，但下层有相对的自主权。独立性——各层决策者各自控制一部分决策变量，以优化各自的目标。冲突性——各层决策者有各自不同的目标，且这些目标往往是相互矛盾的。10.2双层规划特点优先性——上层决策者优先做出决策，下层决策者在优化自己的目标而选择策略时，不能改变上层的决策。自主性——上层的决策可能影响下层的行为，因而部分地影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允许范围内，下层有自主决策权。10.2双层规划特点（续）制约性——下层的决策不但决定着自身目标的实现，而且也影响上层目标的实现，因此上层在选择策略优化自己的目标时，必须考虑到下层可能采取的策略对自己的不利影响。依赖性——各层决策者的容许策略集通常是不可分离的，形成一个相关联的整体。10.3双层规划模型的基本形式其中由下述规划求得)(xyy),(minyxxF0yxG),(..ts（U）),(minyxyf0yxg),(..ts（L）上层决策者通过设置的值影响下层决策者。下层决策变量是上层决策变量的函数，即,这个函数一般被称为反应函数。xy)(xyy一般来说，双层规划模型具有如下形式10.3双层规划模型的基本形式与一般的数学规划不同，即使当、、和都是连续函数，并且上下层的约束集合有界闭的，（）也可能没有最优解。FfGgBP假设上层选择了点，那么下层面临的是以为参数的简单最小值最优化问题。在有些情况下，对固定的，下层对应的最优问题可能包含不止一个最优解。xxx什么情况下会有这种问题？？如：如果所有的函数都是线性的，很可能当＝固定的下层问题的所有最优解组成一个集合，这意味着中的任何一点对下层是无差别的，但对上层的目标函数可能会有差别。上层最优解可能只在中某个特定点上达到，但是没有办法使下层更愿意选择该点。x)(xyx)(xy)(xy双层规划分类线性双层规划：所有目标函数和约束全为线性函数非线性双层规划：上下层目标函数和约束中少有一个非线性函数相应的有整数线性双层规划、整数非线性双层规划等关于双层规划的一些定义记(BP)的约束域为},),(,),(:){(0y0,x0yxg0yxGyx,S}),(:{STyxx定义2.1对每个固定的，称为下层问题的可行解集合，为下层问题的合理反应集。Tx}),(:{)(SSyxyx(){:argmin{(,):()}}PfSxyyxyyxS在上层决策空间上的投影为关于双层规划的一些定义定义2.3如果存在，对任意的满足称是(BP)的全局最优解或最优解。IR),(**yxIR),(yx),(),(**yxyxFF),(**yx定义2.2称为(BP)的可行解集合或诱导域。)}(:),{(xyyxPSIR双层规划的一阶必要条件设是双层规划的最优解，则其一阶必要条件为：),(**yx（1），，，都是一阶连续可微函数；FGfg（2）对，下层问题有唯一解；*x（3）存在，使得是下列问题的可行解：2mEμ),,(μyx),(min,,yxyxFμ0yxG),((,)(,)fyyxygxy0μ0yxgT)),((μ0yxg),(0μ..st例2.1,其中解yxF5min..ts0xyyfmin..ts102yx62yx212yx382yx182yx0y8.3双层规划的基本形式B(8,1)C(12,3)D(16,11)E(10,14)F(0,9)A(0,5)xyS该例的最优解在点D上达到，即=(16,11)，在点E(10,14)处，上层目标函数值更优。点A(0,5)是问题的一个局部最优解。),(**yx11,39**fF求解双层规划问题是非常困难的。原因:双层规划问题是一个NP-hard问题。双层规划的非凸性。10.4双层规划计算复杂性即使能找出双层问题的解，通常也只可能是局部最优解而非全局最优解。由于双层规划问题和博弈论具有一些类似的特性，因此可以利用博弈论中的一些方法来限定双层规划问题解的范围。在博弈论中，同两个选手分别控制各自的决策变量相比，如果一个选手能控制所有的决策变量，那么，这个选手就能更好的优化其自身的目标。10.4双层规划计算复杂性10.4双层规划计算复杂性其中由下述规划求得)(xyy),(minyxxF0yxG),(..ts（U）),(minyxyf0yxg),(..ts（L）第一种情况：如果下列双层规划的最优解为),(*1*1yx10.4双层规划计算复杂性第二种情况：如果上层决策者控制所有变量，双层规划变为),(min,yxyxF0yxG),(0yxg),(..ts2*2*(,)xy设其最优解为10.4双层规划计算复杂性其中),(minyxxF0yxG),(..ts),(minyxyf0yxg),(..ts第三种情况：如果上下层决策者分别独立控制各自的决策变量，双层规划变为3*3*(,)xy设其最优解为10.4双层规划计算复杂性那么有下式存在：),(*2*2yxF),(*1*1yxF),(*3*3yxF除双层规划外，后两种情况都是求单层规划，较容易，因此可不直接求双层规划，而直接求后两类单层规划，然后尽量减小与，与之间的差异。),(*1*1yxF),(*2*2yxF),(*1*1yxF),(*3*3yxF计划经济市场经济其中解对上述问题，当时，由，得。当取时，下层问题的最优目标函数值，但下层问题的最优解不唯一，满足，显然这对上层目标函数产生影响。当时，；当时，。10.4双层规划计算复杂性21minyyxF..ts10x2y1y21minyyf121yyx1y2y0..ts10x1yx12y1xf5.0x5.01minxf21yy5.01xF)0,5.0(),(21yy0F)5.0,0(),(21yy1F上述例子说明：当上层给定一个允许决策后，如果下层问题的最优解不唯一，将导致整个求解的复杂性，甚至无法保证能求得问题的最优解。10.5双层规划求解算法对于双层规划是上层先进行决策，为了说明这种顺序的重要性，考虑下面的例子。其中求解10.5双层规划求解算法21211432),(minyyxxF..ts121xx0,21xx21,yy21212341),(minyyxxf..ts121yy0,21yy例2.310.5双层规划求解算法5.1),(21yy)1,0()2/1,2/1()2/1,2/1(5.25.2值值5.22.52.5xy上层下层xy上层下层同时决策由表可以看出决策顺序很重要，如果控制变量的选手先决策，它的最小费用要比后选择策略或两选手同时决策要优。x121xx)4/3,4/1(),(21xx)4/3,4/1(Ff到目前为止，对于双层规划的求解算法归纳起来，可以分为五大类：10.5双层规划求解算法（1）极点搜索法（ExtremePointSearchMethod）：这种方法主要用于求解双层线性规划，其基本观点就是：双层线性规划问题的任何解都出现在下层问题