1、 最为常见最为常见且得到广泛研究与应用的多层规划是且得到广泛研究与应用的多层规划是双层规划双层规划问题，即考虑问题，即考虑只有两层决策者只有两层决策者的情形。的情形。 这是因为这是因为现实的决策系统现实的决策系统大都大都可以看成可以看成双层决策双层决策。 例如：中央和地方，公司和子公司，工厂的厂例如：中央和地方，公司和子公司，工厂的厂部和车间，高校的校部和院所等。实际上任何多部和车间，高校的校部和院所等。实际上任何多层决策系统都是一系列双层决策系统的复合。层决策系统都是一系列双层决策系统的复合。 双层规划：双层规划：双层规划是双层决策问题的数学模型，它是一双层规划是双层决策问题的数学模型，它是
2、一种具有双层递阶结构的系统优化问题，上下层种具有双层递阶结构的系统优化问题，上下层问题都有各自的目标函数和约束条件。上层问问题都有各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖于下层问题的最优解，而下有关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响。层问题的最优解又受上层决策变量的影响。 二、双层规划的特点二、双层规划的特点双层规划问题一般具有如下几大特点：双层规划问题一般具有如下几大特点：层次性层次性系统分层管理，下层服从上层，但系统分层管理，下层服从上层，但下层有相对的自主权下层有
3、相对的自主权（举例说明）。（举例说明）。独立性独立性各层决策者各自控制一部分决策变各层决策者各自控制一部分决策变量，以优化各自的目标量，以优化各自的目标（举例说明）（举例说明） 。冲突性冲突性各层决策者有各自不同的目标，且各层决策者有各自不同的目标，且这些目标往往是相互矛盾的这些目标往往是相互矛盾的（举例说明）（举例说明） 。 优先性优先性上层决策者优先做出决策，下层上层决策者优先做出决策，下层决策者在优化自己的目标而选择策略时，不决策者在优化自己的目标而选择策略时，不能改变上层的决策能改变上层的决策（举例说明）（举例说明） 。自主性自主性上层的决策可能影响下层的行为，上层的决策可能影响下层的
4、行为，因而部分地影响下层目标的实现，但上层不因而部分地影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允能完全控制下层的选择行为，在上层决策允许范围内，下层有自主决策权许范围内，下层有自主决策权（举例说明）（举例说明） 。 制约性制约性下层的决策不但决定着自身目标下层的决策不但决定着自身目标的实现，而且也影响上层目标的实现，因此的实现，而且也影响上层目标的实现，因此上层在选择策略优化自己的目标时，必须考上层在选择策略优化自己的目标时，必须考虑到下层可能采取的策略对自己的不利影响虑到下层可能采取的策略对自己的不利影响（举例说明）（举例说明） 。依赖性依赖性各层决策者的容许策略集通
5、常是各层决策者的容许策略集通常是不可分离的，形成一个相关联的整体不可分离的，形成一个相关联的整体（举例（举例说明）说明）。 三、双层规划模型的基本形式三、双层规划模型的基本形式其中其中 由下述规划求得由下述规划求得)(xyy ),(minyxxF0yxG),(. .ts（U）),(minyxyf0yxg),(. .ts（L）上层决策者通过设置上层决策者通过设置 的值的值影响影响下层决下层决策者。下层决策变量策者。下层决策变量 是上层决策变量的是上层决策变量的函函数数，即，即 , ,这个函数一般被称这个函数一般被称为反应函数。为反应函数。xy)(xyy o 一般来说，双层规划模型具有如下形式一般
6、来说，双层规划模型具有如下形式 与一般的数学规划不同，即使当与一般的数学规划不同，即使当 和和 都是连续函数，并且上下层的约束集合是有都是连续函数，并且上下层的约束集合是有界闭的，双层规划也可能没有最优解。界闭的，双层规划也可能没有最优解。GfF,假设上层选择了点假设上层选择了点 ，那么下层面临的是以，那么下层面临的是以 为参数的简单最小值最优化问题。在有些情为参数的简单最小值最优化问题。在有些情况下，对固定的况下，对固定的 ，下层对应的，下层对应的最优问题可能最优问题可能包含不止一个最优解包含不止一个最优解。xxxg什么情况下会有什么情况下会有这种问题？这种问题？ 如：如果所有的函数都是如：
7、如果所有的函数都是线性的线性的，很可能当，很可能当 固定的下层问题的所有最优解组成一个固定的下层问题的所有最优解组成一个集集 ，这意味着，这意味着 中的任何一点对下层是中的任何一点对下层是无差别的，但对上层的目标函数可能会有差别。无差别的，但对上层的目标函数可能会有差别。上层最优解可能只在上层最优解可能只在 中某个特定点上达到，中某个特定点上达到，但是没有办法使下层更愿意选择该点。但是没有办法使下层更愿意选择该点。 XX )(xy)(xy)(xy 线性线性，就是指，就是指y=ax+by=ax+b这种形式，往往指的就这种形式，往往指的就是一次。是一次。线性问题线性问题，往往是比较，往往是比较“良
8、好良好”的问题，因的问题，因为它们形式简单，易求解。如果有误差，因为它们形式简单，易求解。如果有误差，因为是线性的缘故也比较容易估计。常见的线为是线性的缘故也比较容易估计。常见的线性问题有匀速直线运动性问题有匀速直线运动 、商品折扣等。、商品折扣等。非线性非线性，就是指并非一次的其他情况。，就是指并非一次的其他情况。 o 双层规划分类双层规划分类 线性双层规划：线性双层规划：所有目标函数和约束全为线性所有目标函数和约束全为线性 函数函数非线性双层规划：非线性双层规划：上下层目标函数和约束中至上下层目标函数和约束中至 少有一个非线性函数少有一个非线性函数相应的有整数线性双层规划、整数非线性双层相
9、应的有整数线性双层规划、整数非线性双层规划等规划等 求解双层规划问题是非常困难的。求解双层规划问题是非常困难的。 原因原因: : 双层规划问题是一个双层规划问题是一个NP-hardNP-hard （non-deterministic polynomialnon-deterministic polynomial， 缩写缩写NPNP）问题。问题。 双层规划的双层规划的非凸性非凸性。四、双层规划计算的复杂性四、双层规划计算的复杂性即使能找出双层问即使能找出双层问题的解，通常也只题的解，通常也只可能是局部最优解可能是局部最优解而非全局最优解。而非全局最优解。？ NP-hard，其中的NP是指非确定性多
10、项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。 NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。 例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？ 推销员旅行问题显然是 NP
11、 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！ 这将是个天文数字。 旅行推销员问题是数学图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。 迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complet或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜
12、想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。 此类问题中，经典的还有 子集和问题； Hamilton回路问题 问题的复杂性问题的复杂性：是指这个问题本身的复杂程度，：是指这个问题本身的复杂程度，是问题的性质。是问题的性质。 算法的复杂性算法的复杂性：是指解决问题的一个具体的算：是指解决问题的一个具体的算法的执行时间，是算法的性质。法的执行时间，是算法的性质。问题问题 抽象抽象 简化简化 判定性问题判定性问题四、双层规划计算的复杂性四、双层规划计算的复杂性只需回答只需回答yes or no 例如：例如：求从求从A A到到B B的最短路径，的最短路径，可转化成：
13、可转化成：从从A A到到B B是否有长度为是否有长度为1 1的路径？从的路径？从A A到到B B是否有是否有长度为长度为2 2的路径？的路径？，从从A A到到B B是否有长度为是否有长度为k k的的路径？如果问到了路径？如果问到了k k的时候回答了的时候回答了yesyes，则停止，则停止发问，我们可以说从发问，我们可以说从A A到到B B的最短路径就是的最短路径就是k k。四、双层规划计算的复杂性四、双层规划计算的复杂性 四、双层规划计算的复杂性四、双层规划计算的复杂性(a)(b)(c)(d)(e) 定义定义: : 若函数图形上若函数图形上任意两点任意两点的连线段必在函的连线段必在函数图形的上
14、方数图形的上方( (下方下方) )，则称该函数为凸函数，则称该函数为凸函数( (凹凹函数函数) )。数学表达式定义为数学表达式定义为： 函数函数f(X)f(X)，对任意不相等，对任意不相等的的X X1 1，X X2 2(a,b), (a,b), 以及以及(0, 1)(0, 1)，有，有 fXfX1 1+(1-)X+(1-)X2 2f(Xf(X1 1)+(1-)f(X)+(1-)f(X2 2) , ) , 则则f(x)f(x)称作凸函数。称作凸函数。四、双层规划计算的复杂性四、双层规划计算的复杂性 其中其中 由下述规划求得由下述规划求得)(xyy ),(minyxxF0yxG),(. .ts（U
15、）),(minyxyf0yxg),(. .ts（L）第一种情况：第一种情况：如果下列双层规划的最优解为如果下列双层规划的最优解为),(*1*1yx 第二种情况：第二种情况：如果上层决策者控制所有变量，双层规划变为如果上层决策者控制所有变量，双层规划变为),(min,yxyxF0yxG),(0yxg),(. .ts2*2*(,)xy设其最优解为设其最优解为 其中其中),(minyxxF0yxG),(. .ts),(minyxyf0yxg),(. .ts第三种情况：第三种情况：如果上下层决策者分别独立控制各自的决策变如果上下层决策者分别独立控制各自的决策变量，双层规划变为量，双层规划变为3*3*(
16、,)xy设其最优解为设其最优解为那么有下式存在：那么有下式存在： 有下式存在：有下式存在：),(*2*2yxF),(*1*1yxF),(*3*3yxF除双层规划外，后两种情况都是求单层规划，较除双层规划外，后两种情况都是求单层规划，较容易，因此可不直接求双层规划，而直接求后两容易，因此可不直接求双层规划，而直接求后两类单层规划，然后尽量减小类单层规划，然后尽量减小 与与 ， 与与 之间的差异。之间的差异。),(*1*1yxF),(*2*2yxF),(*1*1yxF),(*3*3yxF 其中其中 解解对上述问题，当对上述问题，当 时，由时，由 ，得，得 。当取。当取 时，下层问题的最优目标函数值
17、时，下层问题的最优目标函数值 ，但下层问题的最优解不唯一，满足，但下层问题的最优解不唯一，满足 ，显，显然这对上层目标函数然这对上层目标函数 产生影响。当产生影响。当 时，时， ；当；当 时，时， 。 21minyyxF. .ts10 x21,yy21minyyf121yyx0,21yy. .ts10 x1yx12 y1 xf5 . 0 x5 . 01min xf21yy5 . 01 xF)0 , 5 . 0(),(21yy0F)5 . 0 , 0(),(21yy1F上述例子说明：上述例子说明：当当上层上层给定一个允许决策后，如果给定一个允许决策后，如果下层下层问题的问题的最优解不唯一，将导致
18、整个求解的复杂性，甚最优解不唯一，将导致整个求解的复杂性，甚至无法保证能求得问题的至无法保证能求得问题的最优解最优解。 在交通领域中的应用在交通领域中的应用 在管理中的应用在管理中的应用 资源分配资源分配 价格问题价格问题 供应链管理供应链管理 生产计划生产计划 其它方面其它方面五、双层规划的应用五、双层规划的应用 六、双层规划求解算法六、双层规划求解算法一、极点搜索法一、极点搜索法（Extreme Point Search MethodExtreme Point Search Method）：）：n 用于求解双层线性规划。用于求解双层线性规划。n 基本观点：基本观点：双层线性规划问题的任何解
19、都出现双层线性规划问题的任何解都出现在下层问题的约束集合的极点位置。因此，首先在下层问题的约束集合的极点位置。因此，首先可以利用各种方法来寻找约束空间的可以利用各种方法来寻找约束空间的极点极点（不要（不要求寻找全部极点），然后从中再找出双层问题的求寻找全部极点），然后从中再找出双层问题的局部最优解或全局最优解局部最优解或全局最优解。 二、下降法（二、下降法（Descent MethodDescent Method） ：n 主要用于求解非线性连续变量的双层规划问题主要用于求解非线性连续变量的双层规划问题n 最具代表性的下降算法：基于灵敏度分析的求最具代表性的下降算法：基于灵敏度分析的求解算法。解
20、算法。 三、三、K-T法法（Karush-Kuhn-Tucker Method）：）：这种方法将双层问题中的下层问题用它的这种方法将双层问题中的下层问题用它的Karush-Karush-Kuhn-TuckerKuhn-Tucker条件代替，主要用于求解双层线性规划条件代替，主要用于求解双层线性规划问题，最初用于求解双层线性资源控制问题。问题，最初用于求解双层线性资源控制问题。四、直接搜索法四、直接搜索法（Direct Search Method） ：直接使目标函数最小的方法，如直接使目标函数最小的方法，如AbdulaalAbdulaal和和LeBlancLeBlanc（19791979）使用的
21、）使用的Hooke-JeevesHooke-Jeeves搜索法就属于此类，在搜索法就属于此类，在搜索解的过程中，这种方法取决于上层目标函数值的搜索解的过程中，这种方法取决于上层目标函数值的变化。变化。 五、非数值优化方法五、非数值优化方法（Non-numerical optimization） 这类方法主要包括模拟退火、遗传算法和蚁群算法等。这类方法主要包括模拟退火、遗传算法和蚁群算法等。这种非数值优化方法目前这种非数值优化方法目前主要用来求解城市交通连续平衡主要用来求解城市交通连续平衡网络设计问题（网络设计问题（CreeCree和和MasherMasher，19981998）及其它相关优化问
22、）及其它相关优化问题题 例例1 1 , , 其中其中 解解 yxF5min. .ts0 xyyf min. .ts102yx62yx212 yx382yx182yx0y精品课件！精品课件！ B(8,1)C(12,3)D(16,11)E(10,14)F(0,9)A(0,5)xyS 该例的最优解在点该例的最优解在点D D上达到，上达到，即即 =(16,11)=(16,11)， 在点在点E(10,14)E(10,14)处，上层目标处，上层目标函数值更优，如果上层选函数值更优，如果上层选择择 ，下层选，下层选择择 ，此时下层目标，此时下层目标函数更优但上层则较差。点函数更优但上层则较差。点A(0,5)A(0,5)是问题的一个局部最是问题的一个局部最优解。优解。 ),(*yx11,39*fF10 x2y
