现代化方法讲座第3讲ppt课件

,现代优化方法讲座,第二部分双层规划,.,到目前为止，对于双层规划的求解算法归纳起来，可以分为五大类：,2.5双层规划求解算法,现代优化方法讲座,（1）极点搜索法（ExtremePointSearchMethod）：这种方法主要用于求解双层线性规划，其基本观点就是：双层线性规划问题的任何解都出现在下层问题的约束集合的极点位置。因此，首先可以利用各种方法来寻找约束空间的极点（不要求寻找全部极点），然后从中再找出双层问题的局部最优解或全局最优解。,.,2.5双层规划求解算法,现代优化方法讲座,（2）K-T法（Karush-Kuhn-TuckerMethod，简称K-T法）：这种方法将双层问题中的下层问题用它的Karush-Kuhn-Tucker条件代替，主要用于求解双层线性规划问题，最初用于求解双层线性资源控制问题。,.,（3）下降法（DescentMethod）：这种方法是基于用各种可能的方法得到的下层问题对上层决策变量的梯度信息，主要用于求解非线性连续变量的双层规划问题。从本质上讲，这是一种迭代求解方法，利用得到的下层问题对上层决策变量的梯度信息来产生一系列使上层目标函数减小的点。最具代表性的下降算法是基于灵敏度分析的求解算法。,现代优化方法讲座,2.5双层规划求解算法,.,（4）直接搜索法（DirectSearchMethod）：直接使目标函数最小的方法，如Abdulaal和LeBlanc（1979）使用的Hooke-Jeeves搜索法就属于此类，在搜索解的过程中，这种方法取决于上层目标函数值的变化。,现代优化方法讲座,2.5双层规划求解算法,.,（5）非数值优化方法：这类方法主要包括模拟退火、遗传算法和蚁群算法等。这种非数值优化方法目前主要用来求解城市交通连续平衡网络设计问题（Cree和Masher，1998）及其它相关优化问题，但由于此类求解算法在求解双层规划模型时具体的参数（如编码长度等优化参数）难以确定，所以收敛性一般难以保证，况且在实践应用中可解释性也不理想。所以在求解具体双层规划模型时还属于探索阶段。,现代优化方法讲座,2.6双层规划应用,现代优化方法讲座,2.6双层规划的应用,（1）交通已有大量文献将双层规划应用于交通领域。网络设计问题（NetworkDesignProblem）。,相互作用,网络规划者决定投资费用目的使网络中系统费用最小,用户选择出行路径目的使自己的出行费用最小,相互作用,投资费用运行费用取决于交通流量,现代优化方法讲座,2.6双层规划的应用,（1）交通O-D需求估计问题。交通信号控制问题。如何进行信号控制，使车辆使用者作出合理反应，减少交通堵塞和延迟，也可作为双层规划问题来进行优化解决。,现代优化方法讲座,2.6双层规划应用（续）,（2）管理只顾自己的局部利益，而忽略了整体利益，是目前管理中存在的一个比较普遍的问题。双层规划的特点恰恰是从整体的角度出发，兼顾全局，希望达到整体最优。因此，在管理问题中应用双层规划方法，将会取得很好的效果。这方面的研究也比较多。,现代优化方法讲座,2.6双层规划应用（续）,（2）管理资源分配。资源分配是一类比较复杂的管理问题，上层部门将资源分配给多个下层部门，下层部门根据分配的资源和自己已有的资源组织生产，使自己的效益最大。一些公共设施建设，如电站、水库、污物处理站建设等，实质上也是资源分配问题，只不过下层不是部门的效益最大，而是公共设施产生的社会效益最大。价格问题。例如应用到铁路旅客票价制定问题。,现代优化方法讲座,2.6双层规划应用（续）,供应链管理。供应链管理的重要性得到认可。过去，厂商与其供应商持敌对态度，都想从对方那里获得利润，导致产品开发周期过长、产品质量无法提高、成本居高不下等问题。如何使厂商与供应商紧密合作，达到双赢的目的，成为一个热点研究问题。建立双层规划模型，以各成员利润最大化为下层目标，以供应链的综合绩效为上层目标，来进行优化研究，具有重要的应用价值和现实意义。,现代优化方法讲座,2.6双层规划应用（续）,生产计划。其它方面如兵力部署、设施定位、政策规划等。（3）工程设计问题。,总之，双层规划的上层一般是保证系统最优，下层保证个体最优。,2.7.1城市交通平衡网络设计问题交通运输供给能力的不足，严重影响了旅客和各种商品在自然空间上的合理流动，阻碍了国民经济的快速发展，为了克服这一现象，就需要增加交通运输能力，为此必须增加对交通基础设施建设的投资力度。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,资金不足是最大障碍,网络设计时需要决策,2.7双层规划在城市交通网络平衡设计问题中的应用,实质上是在一定约束条件下的最优投资决策问题。,对现有交通网络进行改进,城市交通网络设计问题研究内容,资金投入最少,增加新的路段或更新改善已有路段的能力调整路口的交通信号建设立交桥等,使整个交通网络某种系统性能最优,2.7.2用双层规划描述城市交通网络设计问题利用一定的投资对交通网络进行改善由交通规划部门决策，但改善后的路网效果如何需看用户的出行反应。因此城市交通网络设计问题可以用双层规划进行描述。网络设计问题就是在考虑了投资对整个系统中的供应方和需求方的影响之后，寻找并选择最优投资策略使系统的社会福利最大。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,在进行网络设计时，如果不考虑网络用户的路径选择行为，而一味的增加或改建已有路段，有时不仅不能达到改善整个系统交通状况的目的，反而会使整个系统的交通状况更加恶化，表现为系统总费用不仅没有减少，反而会增加。（举例）因此在进行交通网络设计时，必须考虑网络中用户的路径选择行为，即进行规划时要考虑路网改建后是否能达到预先所期望的目标。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,.,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,考虑一个网络如图所示，有四条路段，四个节点，一个O-D对（从节点O到节点D，总需求量为6）。路段14的阻抗函数（单位为：分钟）分别为：,O,D,网络中只有两条路径，第一条通过节点1、3（用13表示），第二条通过节点1、4（用14表示）。由于网络的对称性，O-D需求量平均分配到两条路径13和14上。每条路径上流量为3。,.,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,.,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,现增加一条路段5，其路段阻抗函数为：,此时，网络中又出现了第三条路径,通过节点1、5、4（用154表示）,这个新网络的UE解是,可见增加网络固定设施通行能力后，并未如预料的那样减少拥挤程度，反而增加了。,.,现代优化方法讲座,其中由下述规划求得：,2.7双层规划在城市交通网络平衡设计问题中的应用,因此，双层网络设计模型就是在满足投资预算约束条件下，考虑了网络用户路径选择行为后，寻找最佳路网改进方案使系统目标函数最优。,交通规划者为了达到使社会效益最大而采取的最优决策,反映了网络中用户的路径选择行为,上层规划,下层规划,这种双层规划是在下层保证用户选择行为符合用户平衡配流原则情况下的网络设计，因此称为城市交通网络平衡设计问题。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,(1)下层用户平衡配流问题著名的Braess诡异现象表明：在进行网络设计时，如果不考虑网络用户的路径选择行为，而一味的增加或改建已有路段，有时不仅不能达到改善整个系统交通状况的目的，反而会使整个系统的交通状况更加恶化，表现为系统总阻抗不仅没有减少，反而会增加，因此在进行交通网络设计时，必须考虑网络中用户的路径选择行为。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,.,如何描述用户的路径选择行为？,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,最常用的是交通流量分配理论它即是根据用户出行选择行为得到的路径选择结果用户平衡配流,.,现代优化方法讲座,Wardrop平衡配流原则描述如下：在起终点之间所有可供选择的路线中，使用者所利用的各条路线上的出行费用全都相等，而且不大于未被利用路线上的出行费用。满足这一原则的交通状态被定义为Wardrop平衡状态，上述配流原则又可称为用户平衡配流。Beckmann采用以下数学形式描述Wardrop平衡状态：,其中为平衡状态下O-D对之间的出行费用。,.,现代优化方法讲座,在用户平衡（UE）配流模型的例子中，只有路段费用是流量的严格增函数的假定，在这种情况下，可以表示成一个变分不等式模型，并且有唯一路段解。如果再加上一个假定，即路段费用仅仅是该路段流量的函数，与其它路段上的流量没有关系，那么就可以得到一个等价的规划模型。,.,现代优化方法讲座,Beckmann在提出了用户平衡配流模型如下：,s.t.，（1.3）,，（1.4）,，（1.5）,（1.2）,一般来说，下层模型有如下几种：固定需求条件下的用户平衡模（UE）型。弹性需求条件下的UE模型。运量分布与UE配流的组合模型。随机用户平衡模型。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,(2)上层网络优化问题在交通网络设计问题中，有两种投资策略，一种是投资改进现有网络中的某些路段，增加其能力，另一种是在现有网络中增加新的路段。与此相对应，上层决策变量有二种形式，如下：离散形式的上层决策变量-离散网络设计问题DNDP（DiscreteNetworkDesignProblem）。连续形式的上层决策变量-连续网络设计问题CNDP（ContinuousNetworkDesignProblem）。,2.7双层规划在城市交通网络平衡设计问题中的应用,2.7.3固定需求条件下的城市交通连续平衡网络设计问题,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,常用的符号定义如下：,城市交通连续平衡网络设计问题，就是在网络用户的路径选择行为符合用户平衡配流准则的前提条件下，通过改进现有网络中的某些路段（增加路段的能力)而使整个网络达到某种性能指标最优的目的。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,：路段的能力增加，,：路段的能力增加的向量表示（上层决策变量），。,：路段的阻抗函数，。,：路段能力增加的投资函数，。,：匹配投资费用与系统总阻抗单位的系数。,上层规划模型,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,上层问题是一个标准的城市交通网络设计问题，第一个式子是城市交通网络设计问题的目标函数，处于上层的网络规划者对某些路段进行投资，增加这些路段的能力，目的是使使整个网络的系统总阻抗和总的投资额之和最小；约束要求路段能力增加非负。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,其中由下述规划求得,下层问题是一个标准的用户平衡配流问题，处于下层的网络用户在给定路段能力的情况下，其路径选择行为符合UE准则。,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,现代优化方法讲座,2.7双层规划在城市交通网络平衡设计问题中的应用,国外铁路运价决定原理主要：运输价值原则:所研究的运输服务对需求者的使用价值或效用。,现代优化方法讲座,2.8铁路旅客票价制定的双层规划模型,需求价格,表示的是旅客票价的最高限度，如果旅客票价高于这个价格，旅客就会放弃选择铁路作为出行方式，而选择其他的交通方式（公路或民航）。,现代优化方法讲座,2.8铁路旅客票价制定的双层规划模型,表示的是旅客票价的最低限度，如果旅客票价低于这个价格，铁路客运部门就难以在客运市场中生存和发展。,运输成本原则:运价应当等于运输服务的生产费用。,供给价格,现代优化方法讲座,2.8铁路旅客票价制定的双层规划模型,在市场经济条件下，铁路旅客票价的制定应该兼顾成本和市场需求两方面的因素。,现代优化方法讲座,上层决策部门：铁路管理部门决策变量：铁路客票价格,下层决策：旅客的出行行为决策变量：交通流量,相互作用,决策部门只能通过政策和管理来影响旅客在出行时对于运输方式的选择，例如通过票价的调整来使得旅客的选择行为发生改变，但不能控制他们的选择。旅客都是根据自己的需要及习惯来选择运输方式。,2.8铁路旅客票价制定的双层规划模型,出行者希望自己总的出行费用最低；铁路客运管理部门总是希望铁路的客运收入最大。这看起来是相互矛盾的，但这两方面相互作用的结果是取得共同的平衡点，即上述双层规划问题的最优解。,2.8铁路旅客票价制定的双层规划模型,其它因素不变,铁路票价上升,铁路客流量减少，转移到其它运输方式,铁路票价下降,铁路客流量增加，吸引其它运输方式的客流,现代优化方法讲座,2.8.1多种交通运输方式竞争条件下铁路客票价格制定的双层规划模型,2.8铁路旅客票价制定的双层规划模型,城市之间的客流分配，一般不存在路径的选择，而只有运输方式的选择。,现代优化方法讲座,2.8铁路旅客票价制定的双层规划模型,从定量角度出发，既保障了出行者使自己的出行费用最小，又能使铁路客运在市场竞争中取得最大的经济效益。,上层规划:描述为铁路客运管理部门在政府规定的范围内制定最佳的客票价格以使铁路客运的经济效益为最大。,下层规划:描述城市间多模式运输竞争条件下，客流在不同运输方式之间的分配模式，目标是使每个出行者在出行过程中的出行费用最低。,现代优化方法讲座,一般情况下，旅客总是力图选择从起点到终点之间总的广义出行费用最低的客运运输方式，,出行时间、旅客票价、安全、方便舒适度等,比如铁路，假定一开始它的出行费用是最低的,如果所有出行者都选择某一种客运运输方式。,那么随着该运输方式客流需求的增加，它总的出行费用就会上升，例如票价上升，出行时间变大，服务质量下降等。使得一部分旅客放弃选择这种运输方式，而选择其它运输方式，而别的运输方式出行费用也会随客流需求的增加而上升。,旅客的选择行为,现代优化方法讲座,最终，在不同的客运运输方式之间会达到一种客流分配的稳定的均衡状态。这种均衡状态可以描述为：在城市之间的所有可供选择的客运运输方式中，旅客所利用的各种客运运输方式的广义出行费用全部相等，并且不大于未被利用的客运运输方式的出行费用。,旅客的选择行为,现代优化方法讲座,旅客的选择行为,可以用下面的数学形式来描述这种均衡状态,如果如果,其中表示城市间第（）种运输方式的广义出行费用，表示均衡状态下城市间的广义出行费用，表示城市间第（）种运输方式的客流量，为城市间所有运输方式的集合。,现代优化方法讲座,其中函数是运输方式的广义费用函数，在这个函数中不同运输方式的客流量是自变量，即（）。取不同的形式，便可以得到不同的客流量在客运运输方式之间的分离模式，最常用的广义费用函数形式有幂函数形式和对数函数形式。,第一个约束表示城市间总的客流需求是已知并且固定的，表示表示城市间总的客流需求；最后一个约束为变量的非负约束。,旅客的选择行为,现代优化方法讲座,（U）其中由下层模型得出（L）,表示城市间铁路客运的客流量，表示城市间铁路客运的旅客票价，表示铁路客运中的平均客运成本。and分别表示城市间的铁路客运的平均客运成本和旅客票价最高限。可以理解为适当的运输成本与适当的利润之和，可以理解为运输成本与政府允许的利润上限之和(或消费者能承受的最大担负能力)。,2.8铁路旅客票价制定的双层规划模型,现代优化方法讲座,例：确定从北京到天津合理的铁路旅客票价,费用综合考虑出行时间、票价、方便性、舒适性、安全性等多种因素。根据京津唐客运市场调查报告北京到天津的总客运量约25000。从北京到天津存在两种运输方式：铁路和公路,现代优化方法讲座,其中为出行时间因素，表示票价因素，为方便、舒适和安全等综合因素；（）为待定参数。,表示不同运输方式的效用，为待定参数。,现代优化方法讲座,.,现代优化方法讲座,模拟退火算法是模仿热力学中固体退火的随机机制设计的。在热力学中，当一个物理系统（固体）处在高温时，它的大量的原子是处于无序的高温运动状态。为使原子进入有序状态，要减少该系统的温度。,如要使该固体变成晶体（晶体的原子是高度格型有序排列的），就要首先将固体加热到能使其原子可进行重新排列的高温，然后逐步小心地冷却它，使其在每个温度级都能达到热平衡状态，直至它冷却成晶体为止。这样的冷却过程就叫“退火（annealing）”。,求解双层规划的模拟退火算法,