第9讲-双层规划

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