1、 BiLevel Programming 层次性层次性是系统的六大特征之一。是系统的六大特征之一。社会社会-不断发展，实际问题不断发展，实际问题-规模越来越大，规模越来越大，结构越来越复杂，进行决策的人也越来越多，而且结构越来越复杂，进行决策的人也越来越多，而且这些决策者这些决策者各自处于不同各自处于不同的层次上。的层次上。一般，高一级决策机构（者）对下一级决策机一般，高一级决策机构（者）对下一级决策机构（者）行使某种构（者）行使某种控制、引导权控制、引导权，而下一级决策机，而下一级决策机构（者）在这一前提下，亦可以在其管理职责范围构（者）在这一前提下，亦可以在其管理职责范围内行使一定的决策权
2、，但这种决策权处于内行使一定的决策权，但这种决策权处于从属从属地位。地位。10.1双层规划简介双层规划简介 另外，在这种多层次决策系统中，每一级都有另外，在这种多层次决策系统中，每一级都有自身的目标函数自身的目标函数。高层机构的决策目标：高层机构的决策目标：重要、权威、具有全局性重要、权威、具有全局性。最终的决策结果往往是寻求使各层决策机构之间达最终的决策结果往往是寻求使各层决策机构之间达到某种协调的到某种协调的具体方案具体方案。10.1双层规划简介双层规划简介既可使最高层决策机构的目标达到既可使最高层决策机构的目标达到“最优最优”，也可使作为上级决策也可使作为上级决策“约束约束”的较低层决策
3、的较低层决策机构的目标在从属位置上相应达到机构的目标在从属位置上相应达到“最最优优”。一般称具有以上基本特征的决策问题为主从递阶一般称具有以上基本特征的决策问题为主从递阶（或多层）决策问题。（或多层）决策问题。主从递阶决策问题最初是由主从递阶决策问题最初是由Von StackelbergVon Stackelberg于于19521952年在研究市场经济问题时提出的年在研究市场经济问题时提出的.因此此问题有时候也称为因此此问题有时候也称为StackelbergStackelberg问题，是问题，是一对策论问题，决策者有上下层关系和不同目标，一对策论问题，决策者有上下层关系和不同目标，但策略集通常
4、是彼此分离。但策略集通常是彼此分离。2020世纪世纪6060年代，年代，DantzigDantzig和和WolfeWolfe提出了大规模提出了大规模线性规划的分解算法，相当于承认有一个核心决线性规划的分解算法，相当于承认有一个核心决策者，他的目标高于一切，其他各层次的决策者策者，他的目标高于一切，其他各层次的决策者实现自己的目标只不过是为实现核心决策者的目实现自己的目标只不过是为实现核心决策者的目标的一种分工。标的一种分工。现在的多层规划承认有最高决策者，但允许下层现在的多层规划承认有最高决策者，但允许下层决策者有各自不同的利益。决策者有各自不同的利益。2020世纪世纪7070年代发展起来的多
5、目标规划通常是寻求年代发展起来的多目标规划通常是寻求一个决策者的互相矛盾的多个目标的折衷解，有一个决策者的互相矛盾的多个目标的折衷解，有些技术，如分层优化，也可用来求层次问题，但些技术，如分层优化，也可用来求层次问题，但下层决策不影响上层，可以逐层独立求解。下层决策不影响上层，可以逐层独立求解。而当前的多层规划正是要强调下层决策对上层目而当前的多层规划正是要强调下层决策对上层目标的影响，因此多层规划问题通常不能逐层独立标的影响，因此多层规划问题通常不能逐层独立求解。求解。2020世纪世纪7070年代以来，人们在各种现实的层次分散年代以来，人们在各种现实的层次分散系统优化决策问题的研究中，遇到了
6、用上述方法不系统优化决策问题的研究中，遇到了用上述方法不能解决的实际问题，开始寻找各种特定的方法解决能解决的实际问题，开始寻找各种特定的方法解决这些问题，逐渐形成了多层规划的概念和方法。这些问题，逐渐形成了多层规划的概念和方法。如：如：Cassidy(1971)Cassidy(1971)的政府政策效力分析，的政府政策效力分析，Kyland(1975)Kyland(1975)的经济层次分析，的经济层次分析，Bracken(1973-1977)Bracken(1973-1977)等人的战备武器等人的战备武器配置研究，配置研究，CandlerCandler和和 Norton(1977)Norton(
7、1977)的奶制品工业模型和的奶制品工业模型和墨西哥农业模型等。墨西哥农业模型等。多层规划（多层规划（Multilevel ProgrammingMultilevel Programming）一词就）一词就是是CandlerCandler和和 NortonNorton在其论文中提出的，它的在其论文中提出的，它的原意是一组嵌套着的数学规划问题，即在约束条原意是一组嵌套着的数学规划问题，即在约束条件中含有优化问题的数学规划。件中含有优化问题的数学规划。2020世纪世纪8080年代至今，多层规划的数学模型更加明年代至今，多层规划的数学模型更加明确和形式化了，国内外学者也发表了许多有意义确和形式化了，
8、国内外学者也发表了许多有意义的成果。的成果。总之，在过去总之，在过去2020年中，多层规划的理论、方法及年中，多层规划的理论、方法及应用都有很大发展，正在逐渐形成一个新的运筹应用都有很大发展，正在逐渐形成一个新的运筹学分支。目前，很多国家对多层规划的研究都非学分支。目前，很多国家对多层规划的研究都非常重视，把它列为科学基金资助项目，并取得了常重视，把它列为科学基金资助项目，并取得了巨大成功。巨大成功。最为常见且得到广泛研究与应用的多层规划是最为常见且得到广泛研究与应用的多层规划是双层规划双层规划问题，即考虑只有两层决策者的情形。问题，即考虑只有两层决策者的情形。这是因为这是因为现实的决策系统现
9、实的决策系统大都可以看成双层决策。大都可以看成双层决策。例如：中央和地方，公司和子公司，工厂的厂部例如：中央和地方，公司和子公司，工厂的厂部和车间，高校的校部和院所等。实际上任何多层和车间，高校的校部和院所等。实际上任何多层决策系统都是一系列双层决策系统的复合。决策系统都是一系列双层决策系统的复合。双层规划是具有两个层次系统的规划与管理（控双层规划是具有两个层次系统的规划与管理（控制）问题。制）问题。很多决策问题由多个具有层次性的决策者组成，很多决策问题由多个具有层次性的决策者组成，这些决策者具有这些决策者具有相对的独立性相对的独立性，即是说上层决策只是，即是说上层决策只是通过自己的决策去通过
10、自己的决策去指导（或引导）指导（或引导）下层决策者，不直下层决策者，不直接接干涉干涉下层的决策；而下层决策者只需把上层的决策下层的决策；而下层决策者只需把上层的决策作为作为参数或约束参数或约束，它可以在自己的可能范围内，它可以在自己的可能范围内自由决自由决策策。如果组成这种上、下层关系不止一个时，这样的如果组成这种上、下层关系不止一个时，这样的系统为系统为多层决策多层决策系统。系统。如果只有一个上、下层关系时，这样的系统通常称如果只有一个上、下层关系时，这样的系统通常称为为双层规划双层规划问题。问题。由此可见，双层规划问题虽然是多层决策系统的由此可见，双层规划问题虽然是多层决策系统的特殊形式，
11、但它是特殊形式，但它是最基本最基本的形式。的形式。双层规划：双层规划：双层规划是双层决策问题的数学模型，它是一种具双层规划是双层决策问题的数学模型，它是一种具有双层递阶结构的系统优化问题，上下层问题都有有双层递阶结构的系统优化问题，上下层问题都有各自的目标函数和约束条件。上层问题的目标函数各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖和约束条件不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响。层决策变量的影响。双层规划的意义在于：双层规划的意义在于：可以同时考虑可
12、以同时考虑全局全局和和个体个体双方的利益，并保证双方的利益，并保证首先首先从全局从全局出发，体现了顾全大局、先集体后个人的思出发，体现了顾全大局、先集体后个人的思想。想。目标是做到既不舍小家，又能顾大家。目标是做到既不舍小家，又能顾大家。可以很好地解决许多实际问题。可以很好地解决许多实际问题。上层决策部门：上层决策部门：决策变量：决策变量：下层决策部门：下层决策部门：决策变量：决策变量：相互作用相互作用上层给下层一定的信息，上层给下层一定的信息，下层在这些信息下，按自下层在这些信息下，按自己的利益或偏好做出反应己的利益或偏好做出反应（决策），（决策），上层再根据这些反应，做上层再根据这些反应，
13、做出符合全局利益的决策。出符合全局利益的决策。双层规划决策过程双层规划决策过程 如果每个决策者都按规定的指标函数在其可能如果每个决策者都按规定的指标函数在其可能范围内做出决策，那么，双层决策系统可能描述为范围内做出决策，那么，双层决策系统可能描述为双层规划问题。双层规划问题。如果每个决策者的指标函数由单个函数组成，这如果每个决策者的指标函数由单个函数组成，这样的双层规划为样的双层规划为双层单目标规划双层单目标规划问题。问题。如果有的决策者的指标函数是一组函数，这样的如果有的决策者的指标函数是一组函数，这样的双层规划问题为双层规划问题为双层多目标规划双层多目标规划问题。问题。8.28.2双层规划
14、特点双层规划特点双层规划问题一般具有如下几大特点：双层规划问题一般具有如下几大特点：层次性层次性系统分层管理，下层服从上层，但下系统分层管理，下层服从上层，但下层有相对的自主权。层有相对的自主权。独立性独立性各层决策者各自控制一部分决策变量，各层决策者各自控制一部分决策变量，以优化各自的目标以优化各自的目标 。冲突性冲突性各层决策者有各自不同的目标，且这各层决策者有各自不同的目标，且这些目标往往是相互矛盾的些目标往往是相互矛盾的 。10.210.2双层规划特点双层规划特点优先性优先性上层决策者优先做出决策，下层决策上层决策者优先做出决策，下层决策者在优化自己的目标而选择策略时，不能改变上者在优
15、化自己的目标而选择策略时，不能改变上层的决策层的决策 。自主性自主性上层的决策可能影响下层的行为，因上层的决策可能影响下层的行为，因而部分地影响下层目标的实现，但上层不能完全而部分地影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允许范围内，控制下层的选择行为，在上层决策允许范围内，下层有自主决策权下层有自主决策权 。10.210.2双层规划特点（续）双层规划特点（续）制约性制约性下层的决策不但决定着自身目标的实下层的决策不但决定着自身目标的实现，而且也影响上层目标的实现，因此上层在选现，而且也影响上层目标的实现，因此上层在选择策略优化自己的目标时，必须考虑到下层可能择策略优化
16、自己的目标时，必须考虑到下层可能采取的策略对自己的不利影响采取的策略对自己的不利影响 。依赖性依赖性各层决策者的容许策略集通常是不可各层决策者的容许策略集通常是不可分离的，形成一个相关联的整体。分离的，形成一个相关联的整体。10.3双层规划模型的基本形式双层规划模型的基本形式其中其中 由下述规划求得由下述规划求得)(xyy),(minyxxF0yxG),(.ts（U）),(minyxyf0yxg),(.ts（L）上层决策者通过设置上层决策者通过设置 的值的值影响影响下层决策下层决策者。下层决策变量者。下层决策变量 是上层决策变量的是上层决策变量的函函数数，即，即 ,这个函数一般被称为这个函数一
17、般被称为反应函数。反应函数。xy)(xyy o 一般来说，双层规划模型具有如下形式一般来说，双层规划模型具有如下形式 10.3双层规划模型的基本形式双层规划模型的基本形式与一般的数学规划不同，即使当与一般的数学规划不同，即使当 、和和 都是都是连续函数，并且上下层的约束集合有界闭的，（连续函数，并且上下层的约束集合有界闭的，（）也可能没有最优解。也可能没有最优解。FfGgBP假设上层选择了点假设上层选择了点 ，那么下层面临的是以，那么下层面临的是以 为参为参数的简单最小值最优化问题。在有些情况下，对固定数的简单最小值最优化问题。在有些情况下，对固定的的 ，下层对应的，下层对应的最优问题可能包含
18、不止一个最优解最优问题可能包含不止一个最优解。xxx什么情况下会有这种问题？什么情况下会有这种问题？如：如果所有的函数都是线性的，很可能当如：如果所有的函数都是线性的，很可能当 固定的下层问题的所有最优解组成一个集合固定的下层问题的所有最优解组成一个集合 ，这意味着这意味着 中的任何一点对下层是无差别的，但中的任何一点对下层是无差别的，但对上层的目标函数可能会有差别。上层最优解可能对上层的目标函数可能会有差别。上层最优解可能只在只在 中某个特定点上达到，但是没有办法使下中某个特定点上达到，但是没有办法使下层更愿意选择该点。层更愿意选择该点。x)(xyx)(xy)(xy o 双层规划分类双层规划
19、分类 线性双层规划：线性双层规划：所有目标函数和约束全为所有目标函数和约束全为线性函数线性函数非线性双层规划：非线性双层规划：上下层目标函数和约束上下层目标函数和约束中少有一个非线性函数中少有一个非线性函数相应的有整数线性双层规划、整数非线性相应的有整数线性双层规划、整数非线性双层规划等双层规划等 关于双层规划的一些定义关于双层规划的一些定义记(BP)的约束域为,),(,),(:)(0y0,x0yxg0yxGyx,S),(:STyxx定义定义2.12.1 对每个固定的对每个固定的 ，称，称 为下层问题的为下层问题的可行解可行解集合，集合，为下层问为下层问题的题的合理反应集合理反应集。Tx),(
20、:)(SSyxyx():argmin(,):()PfSxy yx yyxS 在上层决策空间上的投影为 关于双层规划的一些定义关于双层规划的一些定义定义定义2.32.3 如果存在如果存在 ，对任意，对任意 的的满足满足称称 是是(BP)(BP)的全局最优解或最优解。的全局最优解或最优解。IR),(*yxIR),(yx),(),(*yxyxFF),(*yx定义定义2.22.2 称称 为为(BP)(BP)的的可行解集合或诱导域可行解集合或诱导域。)(:),(xyyxPSIR 双层规划的一阶双层规划的一阶必要条件必要条件设设 是双层规划的最优解，则其是双层规划的最优解，则其一阶必要条件一阶必要条件为：
21、为：),(*yx（1 1），都是一阶连续可微函数；都是一阶连续可微函数；FGfg（2 2）对）对 ，下层问题有唯一解；，下层问题有唯一解；*x（3 3）存在）存在 ，使得，使得 是下列问题的可行解：是下列问题的可行解：2mE),(yx),(min,yxyxF0yxG),(,)(,)fyyx yg x y00yxgT),(0yxg),(0.st 例2.1 ,其中 解 yxF5min.ts0 xyyf min.ts102yx62yx212 yx382yx182yx0y 8.3双层规划的基本形式双层规划的基本形式B(8,1)C(12,3)D(16,11)E(10,14)F(0,9)A(0,5)xyS
22、 该例的最优解在点该例的最优解在点D上达上达到，即到，即 =(16,11)，在点在点E(10,14)处，上层目标处，上层目标函数值更优。点函数值更优。点A(0,5)是问是问题的一个局部最优解。题的一个局部最优解。),(*yx11,39*fF 求解双层规划问题是非常困难的。原因求解双层规划问题是非常困难的。原因:双层规划问题是一个双层规划问题是一个NP-hardNP-hard问题。问题。双层规划的双层规划的非凸性非凸性。10.4双层规划计算复杂性双层规划计算复杂性即使能找出双即使能找出双层问题的解，层问题的解，通常也只可能通常也只可能是局部最优解是局部最优解而非全局最优而非全局最优解。解。由于双
23、层规划问题和博弈论具有一些类似的特由于双层规划问题和博弈论具有一些类似的特性，因此可以利用博弈论中的一些方法来限定双层性，因此可以利用博弈论中的一些方法来限定双层规划问题解的范围。在博弈论中，同两个选手分别规划问题解的范围。在博弈论中，同两个选手分别控制各自的决策变量相比，如果一个选手能控制所控制各自的决策变量相比，如果一个选手能控制所有的决策变量，那么，这个选手就能更好的优化其有的决策变量，那么，这个选手就能更好的优化其自身的目标。自身的目标。10.4双层规划计算复杂性双层规划计算复杂性 10.4双层规划计算复杂性双层规划计算复杂性其中其中 由下述规划求得由下述规划求得)(xyy),(min
24、yxxF0yxG),(.ts（U）),(minyxyf0yxg),(.ts（L）第一种情况：第一种情况：如果下列双层规划的最优解为如果下列双层规划的最优解为),(*1*1yx 10.4双层规划计算复杂性双层规划计算复杂性第二种情况：第二种情况：如果上层决策者控制所有变量，双层规划变为如果上层决策者控制所有变量，双层规划变为),(min,yxyxF0yxG),(0yxg),(.ts2*2*(,)xy设其最优解为设其最优解为 10.4双层规划计算复杂性双层规划计算复杂性其中其中),(minyxxF0yxG),(.ts),(minyxyf0yxg),(.ts第三种情况：第三种情况：如果上下层决策者分
25、别独立控制各自的决策变如果上下层决策者分别独立控制各自的决策变量，双层规划变为量，双层规划变为3*3*(,)xy设其最优解为设其最优解为 10.4双层规划计算复杂性双层规划计算复杂性那么有下式存在：那么有下式存在：),(*2*2yxF),(*1*1yxF),(*3*3yxF除双层规划外，后两种情况都是求单层规划，较除双层规划外，后两种情况都是求单层规划，较容易，因此可不直接求双层规划，而直接求后两容易，因此可不直接求双层规划，而直接求后两类单层规划，然后尽量减小类单层规划，然后尽量减小 与与，与与 之间的差异。之间的差异。),(*1*1yxF),(*2*2yxF),(*1*1yxF),(*3*
26、3yxF计划经济计划经济市场经济市场经济 其中其中 解解对上述问题，当对上述问题，当 时，由时，由 ，得，得 。当取。当取 时，下层问题的最优目标函数值时，下层问题的最优目标函数值 ，但下层问题的最优解不唯一，满足，但下层问题的最优解不唯一，满足 ，显，显然这对上层目标函数然这对上层目标函数 产生影响。当产生影响。当 时，时，；当；当 时，时，。10.4双层规划计算复杂性双层规划计算复杂性21minyyxF.ts10 x2y1y21minyyf121yyx1y2y0.ts10 x1yx12 y1 xf5.0 x5.01min xf21yy5.01 xF)0,5.0(),(21yy0F)5.0,
27、0(),(21yy1F上述例子说明：上述例子说明：当上层给定一个允许决策后，如果下层问题的当上层给定一个允许决策后，如果下层问题的最优解不唯一，将导致整个求解的复杂性，甚最优解不唯一，将导致整个求解的复杂性，甚至无法保证能求得问题的最优解。至无法保证能求得问题的最优解。10.5双层规划求解算法双层规划求解算法对于双层规划是上层先进行决策，为了说明这对于双层规划是上层先进行决策，为了说明这种顺序的重要性，考虑下面的例子。种顺序的重要性，考虑下面的例子。其中其中 求解求解 10.5双层规划求解算法双层规划求解算法21211432),(minyyxxF.ts121 xx0,21xx21,yy2121
28、2341),(minyyxxf.ts121 yy0,21yy例例2.32.3 10.5双层规划求解算法双层规划求解算法5.1),(21yy)1,0()2/1,2/1()2/1,2/1(5.25.2值值值值5.22.52.5xy上层上层下层下层xy上层上层下层下层 同时决策同时决策由表可以看出决策顺序很重要，如果控制由表可以看出决策顺序很重要，如果控制 变量变量的选手先决策，它的最小费用要比后选择策略或两的选手先决策，它的最小费用要比后选择策略或两选手同时决策要优。选手同时决策要优。x121 xx)4/3,4/1(),(21xx)4/3,4/1(Ff 到目前为止，对于双层规划的求解算法归纳起来，
29、到目前为止，对于双层规划的求解算法归纳起来，可以分为五大类：可以分为五大类：10.5双层规划求解算法双层规划求解算法（1 1）极点搜索法（）极点搜索法（Extreme Point Search MethodExtreme Point Search Method）：这这种方法主要用于求解双层线性规划，其基本观点就是：双层种方法主要用于求解双层线性规划，其基本观点就是：双层线性规划问题的任何解都出现在下层问题的约束集合的极点线性规划问题的任何解都出现在下层问题的约束集合的极点位置。因此，首先可以利用各种方法来寻找约束空间的极点位置。因此，首先可以利用各种方法来寻找约束空间的极点（不要求寻找全部极点
30、），然后从中再找出双层问题的局部（不要求寻找全部极点），然后从中再找出双层问题的局部最优解或全局最优解。最优解或全局最优解。10.5双层规划求解算法双层规划求解算法（2 2）K-TK-T法（法（Karush-Kuhn-Tucker MethodKarush-Kuhn-Tucker Method，简称，简称K-K-T T法）法）：这种方法将双层问题中的下层问题用它的：这种方法将双层问题中的下层问题用它的Karush-Kuhn-TuckerKarush-Kuhn-Tucker条件代替，主要用于求解双层线性条件代替，主要用于求解双层线性规划问题，最初用于求解双层线性资源控制问题。规划问题，最初用于求
31、解双层线性资源控制问题。（3 3）下降法）下降法（Descent MethodDescent Method）：这种方法是基于用：这种方法是基于用各种可能的方法得到的下层问题对上层决策变量的梯度信各种可能的方法得到的下层问题对上层决策变量的梯度信息，主要用于求解非线性连续变量的双层规划问题。从本息，主要用于求解非线性连续变量的双层规划问题。从本质上讲，这是一种迭代求解方法，利用得到的下层问题对质上讲，这是一种迭代求解方法，利用得到的下层问题对上层决策变量的梯度信息来产生一系列使上层目标函数减上层决策变量的梯度信息来产生一系列使上层目标函数减小的点。最具代表性的下降算法是基于灵敏度分析的求解小的点
32、。最具代表性的下降算法是基于灵敏度分析的求解算法。算法。10.5双层规划求解算法双层规划求解算法 （4 4）直接搜索法）直接搜索法（Direct Search MethodDirect Search Method）：直接使：直接使目标函数最小的方法，如目标函数最小的方法，如AbdulaalAbdulaal和和LeBlancLeBlanc（19791979）使用的使用的Hooke-JeevesHooke-Jeeves搜索法就属于此类，在搜索解的过搜索法就属于此类，在搜索解的过程中，这种方法取决于上层目标函数值的变化。程中，这种方法取决于上层目标函数值的变化。10.5双层规划求解算法双层规划求解算
33、法 （5 5）非数值优化方法）非数值优化方法：这类方法主要包括模拟退火、遗：这类方法主要包括模拟退火、遗传算法和蚁群算法等。这种非数值优化方法目前主要用来传算法和蚁群算法等。这种非数值优化方法目前主要用来求解城市交通连续平衡网络设计问题（求解城市交通连续平衡网络设计问题（CreeCree和和MasherMasher，19981998）及其它相关优化问题，但由于此类求解算法在求解）及其它相关优化问题，但由于此类求解算法在求解双层规划模型时具体的参数（如编码长度等优化参数）难双层规划模型时具体的参数（如编码长度等优化参数）难以确定，所以收敛性一般难以保证，况且在实践应用中可以确定，所以收敛性一般难
34、以保证，况且在实践应用中可解释性也不理想。所以在求解具体双层规划模型时还属于解释性也不理想。所以在求解具体双层规划模型时还属于探索阶段。探索阶段。10.5双层规划求解算法双层规划求解算法 10.6双层规划的应用双层规划的应用（1 1）交通）交通已有大量文献将双层规划应用于交通领域。已有大量文献将双层规划应用于交通领域。网络设计问题（网络设计问题（Network Design ProblemNetwork Design Problem）。相互作用相互作用网络规划者决定投资费用网络规划者决定投资费用目的使网络中目的使网络中系统费用系统费用最小最小用户用户选择出行路径选择出行路径目的使自己的出行费用
35、最小目的使自己的出行费用最小相互作用相互作用投资费投资费用用运行费运行费用用取决于取决于交通流交通流量量 10.6双层规划的应用双层规划的应用（1 1）交通）交通 O-DO-D（Origin-DestinationOrigin-Destination）需求估计问题）需求估计问题。交通信号控制问题交通信号控制问题。如何进行信号控制，使车。如何进行信号控制，使车辆使用者作出合理反应，减少交通堵塞和延迟，也辆使用者作出合理反应，减少交通堵塞和延迟，也可作为双层规划问题来进行优化解决。可作为双层规划问题来进行优化解决。10.6双层规划应用（续）双层规划应用（续）（2 2）管理）管理只顾自己的局部利益，
36、而忽略了整体利益，是目只顾自己的局部利益，而忽略了整体利益，是目前管理中存在的一个比较普遍的问题。双层规划前管理中存在的一个比较普遍的问题。双层规划的特点恰恰是从整体的角度出发，兼顾全局，希的特点恰恰是从整体的角度出发，兼顾全局，希望达到整体最优。因此，在管理问题中应用双层望达到整体最优。因此，在管理问题中应用双层规划方法，将会取得很好的效果。这方面的研究规划方法，将会取得很好的效果。这方面的研究也比较多。也比较多。10.6双层规划应用（续）双层规划应用（续）（2 2）管理）管理 资源分配资源分配。资源分配是一类比较复杂的管理资源分配是一类比较复杂的管理问题，上层部门将资源分配给多个下层部门，
37、下问题，上层部门将资源分配给多个下层部门，下层部门根据分配的资源和自己已有的资源组织生层部门根据分配的资源和自己已有的资源组织生产，使自己的效益最大。一些公共设施建设，如产，使自己的效益最大。一些公共设施建设，如电站、水库、污物处理站建设等，实质上也是资电站、水库、污物处理站建设等，实质上也是资源分配问题，只不过下层不是部门的效益最大，源分配问题，只不过下层不是部门的效益最大，而是公共设施产生的社会效益最大。而是公共设施产生的社会效益最大。价格问题价格问题。例如应用到铁路旅客票价制定问例如应用到铁路旅客票价制定问题。题。10.6双层规划应用（续）双层规划应用（续）供应链管理供应链管理。供应链管
38、理的重要性得到认可。过去，厂供应链管理的重要性得到认可。过去，厂商与其供应商持敌对态度，都想从对方那里获得利润，导致商与其供应商持敌对态度，都想从对方那里获得利润，导致产品开发周期过长、产品质量无法提高、成本居高不下等问产品开发周期过长、产品质量无法提高、成本居高不下等问题。如何使厂商与供应商紧密合作，达到双赢的目的，成为题。如何使厂商与供应商紧密合作，达到双赢的目的，成为一个热点研究问题。建立双层规划模型，以各成员利润最大一个热点研究问题。建立双层规划模型，以各成员利润最大化为下层目标，以供应链的综合绩效为上层目标，来进行优化为下层目标，以供应链的综合绩效为上层目标，来进行优化研究，具有重要
39、的应用价值和现实意义。化研究，具有重要的应用价值和现实意义。10.6双层规划应用（续）双层规划应用（续）生产计划生产计划。其它方面如兵力部署、设施定位、政策规其它方面如兵力部署、设施定位、政策规划等划等。（3 3）工程设计问题）工程设计问题。城市交通网络设计问题城市交通网络设计问题 10.7.110.7.1城市交通平衡网络设计问题城市交通平衡网络设计问题 交通运输供给能力的不足，交通运输供给能力的不足，严重影响了旅客和严重影响了旅客和各种商品在自然空间上的合理流动，阻碍了国民各种商品在自然空间上的合理流动，阻碍了国民经济的快速发展，为了克服这一现象，就需要增经济的快速发展，为了克服这一现象，就
40、需要增加交通运输能力，为此加交通运输能力，为此必须增加对交通基础设施必须增加对交通基础设施建设的建设的投资力度投资力度 。10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 资金不足是资金不足是最大障碍最大障碍网络设计时网络设计时需要决策需要决策 10.7 10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 实质上是在一定约束条件下实质上是在一定约束条件下的最优投资决策问题的最优投资决策问题。对现有交通网络进行改进对现有交通网络进行改进城市交通城市交通网络设计网络设计问题研究问题研究内容内容资金投资金投入入
41、最少最少增加新的路段或更新增加新的路段或更新改善已有路段的能力改善已有路段的能力调整路口的交通信号调整路口的交通信号建设立交桥等建设立交桥等 使整个交使整个交通网络某通网络某种种系统性系统性能能最优最优 10.7.210.7.2用双层规划描述城市交通网络设计问题用双层规划描述城市交通网络设计问题 利用一定的投资对交通网络进行改善由利用一定的投资对交通网络进行改善由交通规划交通规划部门决策部门决策，但改善后的路网效果如何需看，但改善后的路网效果如何需看用户的用户的出行反应出行反应。因此城市交通网络设计问题可以用。因此城市交通网络设计问题可以用双双层规划层规划进行描述。进行描述。网络设计问题就是在
42、考虑了投资对整个系统中的网络设计问题就是在考虑了投资对整个系统中的供应方和需求方供应方和需求方的影响之后，寻找并选择最优投的影响之后，寻找并选择最优投资策略使系统的社会福利最大。资策略使系统的社会福利最大。10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 在进行网络设计时，如果不考虑网络用户的路径在进行网络设计时，如果不考虑网络用户的路径选择行为，而一味的增加或改建已有路段，有时选择行为，而一味的增加或改建已有路段，有时不仅不能达到改善整个系统交通状况的目的，反不仅不能达到改善整个系统交通状况的目的，反而会使整个系统的交通状况更加恶化，表现为系而会
43、使整个系统的交通状况更加恶化，表现为系统总费用不仅没有减少，反而会增加。统总费用不仅没有减少，反而会增加。（举例）（举例）因此在进行交通网络设计时，必须考虑网络中用因此在进行交通网络设计时，必须考虑网络中用户的路径选择行为，即进行规划时要考虑路网改户的路径选择行为，即进行规划时要考虑路网改建后是否能达到预先所期望的目标。建后是否能达到预先所期望的目标。10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 考虑一个网络如图所示，有四条路段，四个节点，一个考虑一
44、个网络如图所示，有四条路段，四个节点，一个O-O-DD对（对（从节点从节点O O到节点到节点DD，总需求量为，总需求量为6 6）。路段）。路段1 14 4的阻的阻抗函数（单位为：分钟）分别为：抗函数（单位为：分钟）分别为：OOD D1 12 23 34 4222()10cff111()50c ff333()10c ff444()50cff网络中只有两条路径，第一条通过节点网络中只有两条路径，第一条通过节点1 1、3 3（用（用1313表表示），第二条通过节点示），第二条通过节点2 2、4 4（用（用2424表示）。由于网络表示）。由于网络的对称性，的对称性，O-DO-D需求量平均分配到两条路径
45、需求量平均分配到两条路径1313和和2424上。每条路径上流量为上。每条路径上流量为3 3。10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 123453,30,30,53cccc498totalTOOD D1 12 23 34 41p2p222()10cff111()50c ff333()10c ff444()50cff 10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 552498totalT现增加一条路段现增加一条路段5，其路，其路段阻抗函数为：段阻抗函数为：55510)(ffc此时，网络中又出现
46、了第此时，网络中又出现了第三条路径三条路径,通过节点通过节点1 1、5 5、4 4（用（用154154表示）表示）OOD D1 12 23 34 41p2p3p5这个新网络的这个新网络的UEUE解是解是 1232ppp123452,4,4,2,2fffff可见增加网络固定设施通行能力后，可见增加网络固定设施通行能力后，并未如预料的那样减少拥挤程度，反并未如预料的那样减少拥挤程度，反而增加了。而增加了。)(,(minyfyyZ0yfyG)(,(其中其中 由下述规划求得：由下述规划求得：)(yf),(minfyfz0fyg),(10.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通
47、网络平衡设计问题中的应用 因此，双层网络设计模型就是因此，双层网络设计模型就是在满足投资预算约束条件在满足投资预算约束条件下，考虑了网络用户路径选择行为后下，考虑了网络用户路径选择行为后，寻找最佳路网改，寻找最佳路网改进方案进方案 使系统目标函数最优。使系统目标函数最优。*y交通规划者为了达到使社会效益最大而采取的最优决策反映了网络中用户的路径选择行为上层规划上层规划下层规划下层规划 铁路旅客票价制定的双层规划模型铁路旅客票价制定的双层规划模型 国外铁路运价决定原理主要：国外铁路运价决定原理主要：运输价值原则运输价值原则:所研究的运输服务对需求者的所研究的运输服务对需求者的使用价值或效用。使用
48、价值或效用。需求价格需求价格表示的是旅客票价的最高限度，如果旅客票价高表示的是旅客票价的最高限度，如果旅客票价高于这个价格，旅客就会放弃选择铁路作为出行方于这个价格，旅客就会放弃选择铁路作为出行方式，而选择其他的交通方式（公路或民航）。式，而选择其他的交通方式（公路或民航）。铁路旅客票价制定的双层规划模型铁路旅客票价制定的双层规划模型 表示的是旅客票价的最低限度，如果旅客票价低表示的是旅客票价的最低限度，如果旅客票价低于这个价格，铁路客运部门就难以在客运市场中于这个价格，铁路客运部门就难以在客运市场中生存和发展。生存和发展。运输成本原则运输成本原则:运价应当等于运输服务的生运价应当等于运输服务
49、的生产费用产费用。供给价格供给价格 铁路旅客票价制定的双层规划模型铁路旅客票价制定的双层规划模型 在市场经济条件下，铁路旅客票价的制定在市场经济条件下，铁路旅客票价的制定应该兼顾应该兼顾成本成本和和市场需求市场需求两方面的因素。两方面的因素。上层决策部门：铁路管理部门 决策变量：铁路客票价格下层决策：旅客的出行行为 决策变量：交通流量相互作用相互作用v 决策部门只能通过决策部门只能通过政策和管理来影响旅客政策和管理来影响旅客在出行时对于运输方式在出行时对于运输方式的选择，例如通过票价的选择，例如通过票价的调整来使得旅客的选的调整来使得旅客的选择行为发生改变，但不择行为发生改变，但不能控制他们的
50、选择。能控制他们的选择。v 旅客都是根据自己旅客都是根据自己的需要及习惯来选择运的需要及习惯来选择运输方式。输方式。10.8 铁路旅客票价制定的双层规划模型铁路旅客票价制定的双层规划模型 v出行者出行者希望自己总的出行费用最低；希望自己总的出行费用最低；v铁路客运管理部门铁路客运管理部门总是希望铁路的客运收入最大。总是希望铁路的客运收入最大。v这看起来是相互矛盾的，但这两方面相互作用的结果是这看起来是相互矛盾的，但这两方面相互作用的结果是取得共同的平衡点，即上述双层规划问题的最优解。取得共同的平衡点，即上述双层规划问题的最优解。10.8 铁路旅客票价制定的双层规划模型铁路旅客票价制定的双层规划
