现代化方法讲座第3讲.ppt
《现代化方法讲座第3讲.ppt》由会员分享,可在线阅读,更多相关《现代化方法讲座第3讲.ppt(58页珍藏版)》请在咨信网上搜索。
1、 现现 代代 优优 化化 方方 法法 讲讲 座座 第二部分第二部分 双层规划双层规划.到目前为止,对于双层规划的求解算法归纳起来,到目前为止,对于双层规划的求解算法归纳起来,可以分为五大类:可以分为五大类:2.5双层规划求解算法双层规划求解算法现现 代代 优优 化化 方方 法法 讲讲 座座(1 1)极点搜索法()极点搜索法(Extreme Point Search MethodExtreme Point Search Method):这这种方法主要用于求解双层线性规划,其基本观点就是:双层种方法主要用于求解双层线性规划,其基本观点就是:双层线性规划问题的任何解都出现在下层问题的约束集合的极点线
2、性规划问题的任何解都出现在下层问题的约束集合的极点位置。因此,首先可以利用各种方法来寻找约束空间的极点位置。因此,首先可以利用各种方法来寻找约束空间的极点(不要求寻找全部极点),然后从中再找出双层问题的局部(不要求寻找全部极点),然后从中再找出双层问题的局部最优解或全局最优解。最优解或全局最优解。.2.5双层规划求解算法双层规划求解算法现现 代代 优优 化化 方方 法法 讲讲 座座(2 2)K-TK-T法法(Karush-Kuhn-Tucker Karush-Kuhn-Tucker MethodMethod,简简称称K-TK-T法法):这这种种方方法法将将双双层层问问题题中中的的下下层层问问题
3、题用用它它的的Karush-Karush-Kuhn-TuckerKuhn-Tucker条条件件代代替替,主主要要用用于于求求解解双双层层线线性性规规划划问问题题,最初用于求解双层线性资源控制问题。最初用于求解双层线性资源控制问题。.(3 3)下下降降法法(Descent Descent MethodMethod):这这种种方方法法是是基基于于用用各各种种可可能能的的方方法法得得到到的的下下层层问问题题对对上上层层决决策策变变量量的的梯梯度度信信息息,主主要要用用于于求求解解非非线线性性连连续续变变量量的的双双层层规规划划问问题题。从从本本质质上上讲讲,这这是是一一种种迭迭代代求求解解方方法法,
4、利利用用得得到到的的下下层层问问题题对对上上层层决决策策变变量量的的梯梯度度信信息息来来产产生生一一系系列列使使上上层层目目标标函函数数减减小小的的点点。最最具具代代表表性性的的下下降降算算法法是是基基于于灵灵敏敏度度分分析析的的求求解解算法。算法。现现 代代 优优 化化 方方 法法 讲讲 座座2.5双层规划求解算法双层规划求解算法.(4 4)直直接接搜搜索索法法(Direct Direct Search Search MethodMethod):直直接接使使目目标标函函数数最最小小的的方方法法,如如AbdulaalAbdulaal和和LeBlancLeBlanc(19791979)使使用用的
5、的Hooke-JeevesHooke-Jeeves搜搜索索法法就就属属于于此此类类,在在搜搜索索解解的的过过程中,这种方法取决于上层目标函数值的变化。程中,这种方法取决于上层目标函数值的变化。现现 代代 优优 化化 方方 法法 讲讲 座座2.5双层规划求解算法双层规划求解算法.(5 5)非非数数值值优优化化方方法法:这这类类方方法法主主要要包包括括模模拟拟退退火火、遗遗传传算算法法和和蚁蚁群群算算法法等等。这这种种非非数数值值优优化化方方法法目目前前主主要要用用来来求求解解城城市市交交通通连连续续平平衡衡网网络络设设计计问问题题(CreeCree和和MasherMasher,19981998)
6、及及其其它它相相关关优优化化问问题题,但但由由于于此此类类求求解解算算法法在在求求解解双双层层规规划划模模型型时时具具体体的的参参数数(如如编编码码长长度度等等优优化化参参数数)难难以以确确定定,所所以以收收敛敛性性一一般般难难以以保保证证,况况且且在在实实践践应应用用中中可可解解释释性性也也不不理理想想。所所以以在在求求解解具具体体双双层层规规划划模模型型时时还还属属于于探索阶段。探索阶段。现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划应用双层规划应用.现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划的应用双层规划的应用(1 1)交通)交通已有大量文献将双层规划应用
7、于交通领域。已有大量文献将双层规划应用于交通领域。网络设计问题(网络设计问题(Network Design ProblemNetwork Design Problem)。相互作用相互作用网络规划者决定投资费用网络规划者决定投资费用目的使网络中目的使网络中系统费用系统费用最小最小用户用户选择出行路径选择出行路径目的使自己的出行费用最小目的使自己的出行费用最小相互作用相互作用投资费用投资费用运行费用运行费用取决于取决于交交通流量通流量.现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划的应用双层规划的应用(1 1)交通)交通 O-DO-D需求估计问题需求估计问题。交通信号控制问题交通信号
8、控制问题。如何进行信号控制,使车。如何进行信号控制,使车辆使用者作出合理反应,减少交通堵塞和延迟,也辆使用者作出合理反应,减少交通堵塞和延迟,也可作为双层规划问题来进行优化解决。可作为双层规划问题来进行优化解决。.现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划应用(续)双层规划应用(续)(2 2)管理)管理只只顾顾自自己己的的局局部部利利益益,而而忽忽略略了了整整体体利利益益,是是目目前前管管理理中中存存在在的的一一个个比比较较普普遍遍的的问问题题。双双层层规规划划的的特特点点恰恰恰恰是是从从整整体体的的角角度度出出发发,兼兼顾顾全全局局,希希望望达达到到整整体体最最优优。因因此
9、此,在在管管理理问问题题中中应应用用双双层层规规划划方方法,将会取得很好的效果。这方面的研究也比较多。法,将会取得很好的效果。这方面的研究也比较多。.现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划应用(续)双层规划应用(续)(2 2)管理)管理 资资源源分分配配。资资源源分分配配是是一一类类比比较较复复杂杂的的管管理理问问题题,上上层层部部门门将将资资源源分分配配给给多多个个下下层层部部门门,下下层层部部门门根根据据分分配配的的资资源源和和自自己己已已有有的的资资源源组组织织生生产产,使使自自己己的的效效益益最最大大。一一些些公公共共设设施施建建设设,如如电电站站、水水库库、污污
10、物物处处理理站站建建设设等等,实实质质上上也也是是资资源源分分配配问问题题,只只不不过过下下层层不不是是部部门门的的效效益益最最大大,而而是是公公共共设设施产生的社会效益最大。施产生的社会效益最大。价格问题价格问题。例如应用到铁路旅客票价制定问例如应用到铁路旅客票价制定问题。题。.现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划应用(续)双层规划应用(续)供供应应链链管管理理。供供应应链链管管理理的的重重要要性性得得到到认认可可。过过去去,厂厂商商与与其其供供应应商商持持敌敌对对态态度度,都都想想从从对对方方那那里里获获得得利利润润,导导致致产产品品开开发发周周期期过过长长、产产品
11、品质质量量无无法法提提高高、成成本本居居高高不不下下等等问问题题。如如何何使使厂厂商商与与供供应应商商紧紧密密合合作作,达达到到双双赢赢的的目目的的,成成为为一一个个热热点点研研究究问问题题。建建立立双双层层规规划划模模型型,以以各各成成员员利利润润最最大大化化为为下下层层目目标标,以以供供应应链链的的综综合合绩绩效效为为上上层层目目标标,来来进进行行优优化研究,具有重要的应用价值和现实意义。化研究,具有重要的应用价值和现实意义。.现现 代代 优优 化化 方方 法法 讲讲 座座2.6双层规划应用(续)双层规划应用(续)生产计划生产计划。其其它它方方面面如如兵兵力力部部署署、设设施施定定位位、政
12、政策策规规划等划等。(3 3)工程设计问题)工程设计问题。总总之之,双双层层规规划划的的上上层层一一般般是是保保证证系系统统最最优优,下层保证个体最优。下层保证个体最优。.2.7.12.7.1城市交通平衡网络设计问题城市交通平衡网络设计问题 交交通通运运输输供供给给能能力力的的不不足足,严严重重影影响响了了旅旅客客和和各各种种商商品品在在自自然然空空间间上上的的合合理理流流动动,阻阻碍碍了了国国民民经经济济的的快快速速发发展展,为为了了克克服服这这一一现现象象,就就需需要要增增加加交交通通运运输输能能力力,为为此此必必须须增增加加对对交交通通基基础础设设施施建建设设的的投资力度投资力度 。现现
13、 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 资金不足是资金不足是最大障碍最大障碍网络设计时网络设计时需要决策需要决策.2.7 2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 实实质质上上是是在在一一定定约约束束条条件件下下的的最优投资决策最优投资决策问题问题。对现有交通网络进行改进对现有交通网络进行改进城市交通城市交通网络设计网络设计问题研究问题研究内容内容资金投资金投入入最少最少增加新的路段或更新增加新的路段或更新改善已有路段的能力改善已有路段的能力调整路
14、口的交通信号调整路口的交通信号建设立交桥等建设立交桥等 使整个交使整个交通网络某通网络某种种系统性系统性能能最优最优.2.7.22.7.2用双层规划描述城市交通网络设计问题用双层规划描述城市交通网络设计问题 利利用用一一定定的的投投资资对对交交通通网网络络进进行行改改善善由由交交通通规规划划部部门门决决策策,但但改改善善后后的的路路网网效效果果如如何何需需看看用用户户的的出出行行反反应应。因因此此城城市市交交通通网网络络设设计计问问题题可可以以用用双双层规划层规划进行描述。进行描述。网网络络设设计计问问题题就就是是在在考考虑虑了了投投资资对对整整个个系系统统中中的的供供应应方方和和需需求求方方
15、的的影影响响之之后后,寻寻找找并并选选择择最最优优投投资策略使系统的社会福利最大。资策略使系统的社会福利最大。现现 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用.在在进进行行网网络络设设计计时时,如如果果不不考考虑虑网网络络用用户户的的路路径径选选择择行行为为,而而一一味味的的增增加加或或改改建建已已有有路路段段,有有时时不不仅仅不不能能达达到到改改善善整整个个系系统统交交通通状状况况的的目目的的,反反而而会会使使整整个个系系统统的的交交通通状状况况更更加加恶恶化化,表表现现为为系系统总费用不仅没有减少,反
16、而会增加。统总费用不仅没有减少,反而会增加。(举例)(举例)因因此此在在进进行行交交通通网网络络设设计计时时,必必须须考考虑虑网网络络中中用用户户的的路路径径选选择择行行为为,即即进进行行规规划划时时要要考考虑虑路路网网改改建后是否能达到预先所期望的目标。建后是否能达到预先所期望的目标。现现 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用.现现 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 考虑一个网络如图所示,有四条路段
17、,四个节点,一个考虑一个网络如图所示,有四条路段,四个节点,一个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
18、 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解是解是
19、 可见增加网络固定设施通行能力后,可见增加网络固定设施通行能力后,并未如预料的那样减少拥挤程度,反并未如预料的那样减少拥挤程度,反而增加了。而增加了。.现现 代代 优优 化化 方方 法法 讲讲 座座其中其中 由下述规划求得:由下述规划求得:2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 因此,双层网络设计模型就是在满足投资预算约束条件因此,双层网络设计模型就是在满足投资预算约束条件下,考虑了网络用户路径选择行为后,寻找最佳路网改下,考虑了网络用户路径选择行为后,寻找最佳路网改进方案进方案 使系统目标函数最优。使系统目标函数最优。交通规划者为了达到使
20、社会效益最大而采取的最优决策反映了网络中用户的路径选择行为上层规划上层规划下层规划下层规划.这这种种双双层层规规划划是是在在下下层层保保证证用用户户选选择择行行为为符符合合用用户户平平衡衡配配流流原原则则情情况况下下的的网网络络设设计计,因因此此称称为为城市交通网络城市交通网络平衡平衡设计问题。设计问题。现现 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用.(1)(1)下层用户平衡配流问题下层用户平衡配流问题 著著名名的的 Braess Braess 诡诡异异现现象象表表明明:在在进进行行网网络络设设计计时时
21、,如如果果不不考考虑虑网网络络用用户户的的路路径径选选择择行行为为,而而一一味味的的增增加加或或改改建建已已有有路路段段,有有时时不不仅仅不不能能达达到到改改善善整整个个系系统统交交通通状状况况的的目目的的,反反而而会会使使整整个个系系统统的的交交通通状状况况更更加加恶恶化化,表表现现为为系系统统总总阻阻抗抗不不仅仅没没有有减减少少,反反而而会会增增加加,因因此此在在进进行行交交通通网网络设计时,必须考虑网络中用户的络设计时,必须考虑网络中用户的路径选择行为路径选择行为。现现 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设
22、计问题中的应用.如何描述如何描述用户的路径选择行为?用户的路径选择行为?现现 代代 优优 化化 方方 法法 讲讲 座座2.7 双层规划在城市交通网络平衡设计问题中的应用双层规划在城市交通网络平衡设计问题中的应用 最常用的是交通流量分配理论最常用的是交通流量分配理论它它即即是是根根据据用用户户出出行行选选择择行行为为得得到到的的路路径径选选择择结果结果用户平衡配流用户平衡配流.现现 代代 优优 化化 方方 法法 讲讲 座座WardropWardrop平衡配流原则描述如下:平衡配流原则描述如下:在在起起终终点点之之间间所所有有可可供供选选择择的的路路线线中中,使使用用者者所所利利用用的的各各条条路
23、路线线上上的的出出行行费费用用全全都都相相等等,而而且且不不大大于于未未被被利利用用路路线线上上的的出出行行费费用用。满满足足这这一一原原则则的的交交通通状状态态被被定定义义为为WardropWardrop平平衡衡状状态态,上上述述配配流流原原则则又又可可称称为为用用户户平平衡衡配配流流。BeckmannBeckmann采采用用以以下下数数学学形形式式描描述述WardropWardrop平平衡衡状状态:态:其中为平衡状态下其中为平衡状态下O-D对之间的出行费用。对之间的出行费用。.现现 代代 优优 化化 方方 法法 讲讲 座座在在用用户户平平衡衡(UEUE)配配流流模模型型的的例例子子中中,只
24、只有有路路段段费费用用是是流流量量的的严严格格增增函函数数的的假假定定,在在这这种种情情况况下下,可可以以表表示示成成一一个个变变分分不不等等式式模模型型,并并且且有有唯唯一一路路段段解解。如如果果再再加加上上一一个个假假定定,即即路路段段费费用用仅仅仅仅是是该该路路段段流流量量的的函函数数,与与其其它它路路段段上上的的流流量量没没有有关关系系,那么就可以得到一个等价的规划模型。,那么就可以得到一个等价的规划模型。.现现 代代 优优 化化 方方 法法 讲讲 座座Beckmann在在提出了用户平衡配流模型如下:提出了用户平衡配流模型如下:s.t.,(1.3),(1.4),(1.5)(1.2).一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 现代化 方法 讲座
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。