现代化方法讲座.ppt

《现代化方法讲座.ppt》由会员分享，可在线阅读，更多相关《现代化方法讲座.ppt（45页珍藏版）》请在三一办公上搜索。

1、,双 层 规 划,现 代 优 化 方 法 讲 座,教学内容：双层规划的基本概念、基本模型、求解的复杂性双层规划的求解方法双层规划的应用（网络设计、旅客票价、选址问题等）教学重点：双层规划的基本特点和基本模型双层规划的应用,现 代 优 化 方 法 讲 座,层次性是系统的六大特征之一。社会-不断发展，实际问题-规模越来越大，结构越来越复杂，进行决策的人也越来越多，而且这些决策者各自处于不同的层次上。一般，高一级决策机构（者）对下一级决策机构（者）行使某种控制、引导权，而下一级决策机构（者）在这一前提下，亦可以在其管理职责范围内行使一定的决策权，但这种决策权处于从属地位。,2.1双层规划简介,现 代

2、 优 化 方 法 讲 座,另外，在这种多层次决策系统中，每一级都有自身的目标函数。高层机构的决策目标：重要、权威、具有全局性。最终的决策结果往往是寻求使各层决策机构之间达到某种协调的具体方案。,2.1双层规划简介,既可使最高层决策机构的目标达到“最优”，也可使作为上级决策“约束”的较低层决策机构的目标在从属位置上相应达到“最优”。,一般称具有以上基本特征的决策问题为主从递阶（或多层）决策问题。主从递阶决策问题最初是由Von Stackelberg于1952年在研究市场经济问题时提出的.因此此问题有时候也称为Stackelberg问题，是一对策论问题，决策者有上下层关系和不同目标，但策略集通常是

3、彼此分离。,现 代 优 化 方 法 讲 座,20世纪60年代，Dantzig和Wolfe提出了大规模线性规划的分解算法，相当于承认有一个核心决策者，他的目标高于一切，其他各层次的决策者实现自己的目标只不过是为实现核心决策者的目标的一种分工。现在的多层规划承认有最高决策者，但允许下层决策者有各自不同的利益。,现 代 优 化 方 法 讲 座,20世纪70年代发展起来的多目标规划通常是寻求一个决策者的互相矛盾的多个目标的折衷解，有些技术，如分层优化，也可用来求层次问题，但下层决策不影响上层，可以逐层独立求解。而当前的多层规划正是要强调下层决策对上层目标的影响，因此多层规划问题通常不能逐层独立求解。,

4、现 代 优 化 方 法 讲 座,20世纪70年代以来，人们在各种现实的层次分散系统优化决策问题的研究中，遇到了用上述方法不能解决的实际问题，开始寻找各种特定的方法解决这些问题，逐渐形成了多层规划的概念和方法。如：Cassidy(1971)的政府政策效力分析，Kyland(1975)的经济层次分析，Bracken(1973-1977)等人的战备武器配置研究，Candler和 Norton(1977)的奶制品工业模型和墨西哥农业模型等。,现 代 优 化 方 法 讲 座,多层规划（Multilevel Programming）一词就是Candler和 Norton在其论文中提出的，它的原意是一组嵌套

5、着的数学规划问题，即在约束条件中含有优化问题的数学规划。20世纪80年代至今，多层规划的数学模型更加明确和形式化了，国内外学者也发表了许多有意义的成果。,现 代 优 化 方 法 讲 座,总之，在过去20年中，多层规划的理论、方法及应用都有很大发展，正在逐渐形成一个新的运筹学分支。目前，很多国家对多层规划的研究都非常重视，把它列为科学基金资助项目，并取得了巨大成功。,现 代 优 化 方 法 讲 座,最为常见且得到广泛研究与应用的多层规划是双层规划问题，即考虑只有两层决策者的情形。这是因为现实的决策系统大都可以看成双层决策。例如：中央和地方，公司和子公司，工厂的厂部和车间，高校的校部和院所等。实际

6、上任何多层决策系统都是一系列双层决策系统的复合。,现 代 优 化 方 法 讲 座,双层规划是具有两个层次系统的规划与管理（控制）问题。很多决策问题由多个具有层次性的决策者组成，这些决策者具有相对的独立性，即是说上层决策只是通过自己的决策去指导（或引导）下层决策者，不直接干涉下层的决策；而下层决策者只需把上层的决策作为参数或约束，它可以在自己的可能范围内自由决策。,现 代 优 化 方 法 讲 座,如果组成这种上、下层关系不止一个时，这样的系统为多层决策系统。如果只有一个上、下层关系时，这样的系统通常称为双层规划问题。由此可见，双层规划问题虽然是多层决策系统的特殊形式，但它是最基本的形式。,现 代

7、 优 化 方 法 讲 座,双层规划：双层规划是双层决策问题的数学模型，它是一种具有双层递阶结构的系统优化问题，上下层问题都有各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响。,现 代 优 化 方 法 讲 座,双层规划的意义在于：可以同时考虑全局和个体双方的利益，并保证首先从全局出发，体现了顾全大局、先集体后个人的思想。目标是做到既不舍小家，又能顾大家。可以很好地解决许多实际问题。,现 代 优 化 方 法 讲 座,现 代 优 化 方 法 讲 座,上层决策部门：决策变量：,下层决策部门：决策变量：,

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

9、策者各自控制一部分决策变量，以优化各自的目标（举例说明）。冲突性各层决策者有各自不同的目标，且这些目标往往是相互矛盾的（举例说明）。,2.2双层规划特点,现 代 优 化 方 法 讲 座,优先性上层决策者优先做出决策，下层决策者在优化自己的目标而选择策略时，不能改变上层的决策（举例说明）。自主性上层的决策可能影响下层的行为，因而部分地影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允许范围内，下层有自主决策权（举例说明）。,2.2双层规划特点（续）,现 代 优 化 方 法 讲 座,制约性下层的决策不但决定着自身目标的实现，而且也影响上层目标的实现，因此上层在选择策略优化自己的目标

10、时，必须考虑到下层可能采取的策略对自己的不利影响（举例说明）。依赖性各层决策者的容许策略集通常是不可分离的，形成一个相关联的整体（举例说明）。,2.3双层规划模型的基本形式,现 代 优 化 方 法 讲 座,其中 由下述规划求得,（U）,（L）,上层决策者通过设置 的值影响下层决策者。下层决策变量 是上层决策变量的函数，即,这个函数一般被称为反应函数。,一般来说，双层规划模型具有如下形式,2.3双层规划模型的基本形式,与一般的数学规划不同，即使当、和 都是连续函数，并且上下层的约束集合有界闭的，（）也可能没有最优解。,假设上层选择了点，那么下层面临的是以 为参数的简单最小值最优化问题。在有些情况

11、下，对固定的，下层对应的最优问题可能包含不止一个最优解。,什么情况下会有这种问题？,现 代 优 化 方 法 讲 座,如：如果所有的函数都是线性的，很可能当 固定的下层问题的所有最优解组成一个集合，这意味着 中的任何一点对下层是无差别的，但对上层的目标函数可能会有差别。上层最优解可能只在 中某个特定点上达到，但是没有办法使下层更愿意选择该点。,现 代 优 化 方 法 讲 座,双层规划分类,线性双层规划：所有目标函数和约束全为线性函数非线性双层规划：上下层目标函数和约束中少有一个非线性函数相应的有整数线性双层规划、整数非线性双层规划等,关于双层规划的一些定义,现 代 优 化 方 法 讲 座,记(B

12、P)的约束域为,定义2.1 对每个固定的，称 为下层问题的可行解集合，为下层问题的合理反应集。,在上层决策空间上的投影为,关于双层规划的一些定义,现 代 优 化 方 法 讲 座,定义2.3 如果存在，对任意 的满足称 是(BP)的全局最优解或最优解。,定义2.2 称 为(BP)的可行解集合或诱导域。,双层规划的一阶必要条件,现 代 优 化 方 法 讲 座,设 是双层规划的最优解，则其一阶必要条件为：,（1），都是一阶连续可微函数；,（2）对，下层问题有唯一解；,（3）存在，使得 是下列问题的可行解：,2.3双层规划的基本形式,现 代 优 化 方 法 讲 座,例2.1,其中 解,2.3双层规划的

13、基本形式,现 代 优 化 方 法 讲 座,该例的最优解在点D上达到，即=(16,11)，在点E(10,14)处，上层目标函数值更优，如果上层选择，下层选择，此时下层目标函数更优但上层则较差。点A(0,5)是问题的一个局部最优解。,求解双层规划问题是非常困难的。原因:双层规划问题是一个NP-hard问题。双层规划的非凸性。,2.4双层规划计算复杂性,现 代 优 化 方 法 讲 座,即使能找出双层问题的解，通常也只可能是局部最优解而非全局最优解。,由于双层规划问题和博弈论具有一些类似的特性，因此可以利用博弈论中的一些方法来限定双层规划问题解的范围。在博弈论中，同两个选手分别控制各自的决策变量相比，

14、如果一个选手能控制所有的决策变量，那么，这个选手就能更好的优化其自身的目标。,现 代 优 化 方 法 讲 座,2.4双层规划计算复杂性,现 代 优 化 方 法 讲 座,2.4双层规划计算复杂性,其中 由下述规划求得,（U）,（L）,第一种情况：如果下列双层规划的最优解为,现 代 优 化 方 法 讲 座,2.4双层规划计算复杂性,第二种情况：如果上层决策者控制所有变量，双层规划变为,设其最优解为,现 代 优 化 方 法 讲 座,2.4双层规划计算复杂性,其中,第三种情况：如果上下层决策者分别独立控制各自的决策变量，双层规划变为,设其最优解为,现 代 优 化 方 法 讲 座,2.4双层规划计算复杂

15、性,那么有下式存在：,除双层规划外，后两种情况都是求单层规划，较容易，因此可不直接求双层规划，而直接求后两类单层规划，然后尽量减小 与，与 之间的差异。,当上层给定一个允许决策后，如果下层问题的最优解不唯一，将导致整个求解的复杂性，甚至无法保证能求得问题的最优解。,2.5双层规划求解算法,现 代 优 化 方 法 讲 座,对于双层规划是上层先进行决策，为了说明这种顺序的重要性，考虑下面的例子。,其中 求解,2.5双层规划求解算法,现 代 优 化 方 法 讲 座,例2.3,2.5双层规划求解算法,现 代 优 化 方 法 讲 座,值,值,同时决策,由表可以看出决策顺序很重要，如果控制 变量的选手先决

16、策，它的最小费用要比后选择策略或两选手同时决策要优。,现 代 优 化 方 法 讲 座,注意与多目标规划的区别,到目前为止，对于双层规划的求解算法归纳起来，可以分为五大类：,2.5双层规划求解算法,现 代 优 化 方 法 讲 座,（1）极点搜索法（Extreme Point Search Method）：这种方法主要用于求解双层线性规划，其基本观点就是：双层线性规划问题的任何解都出现在下层问题的约束集合的极点位置。因此，首先可以利用各种方法来寻找约束空间的极点（不要求寻找全部极点），然后从中再找出双层问题的局部最优解或全局最优解。,2.5双层规划求解算法,现 代 优 化 方 法 讲 座,（2）K

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

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