现代化方法讲座第3讲.ppt

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