【正文】 力和長度相等。O ╲ D 1 2 31 0 22 0 23 0 0 解：利用用戶均衡分配，可以得到以下兩種結(jié)果。x 1x用戶均衡的概念 )( 22 xc )( 11 xccoc2x 39。B e c k m a nn （ 1956 ）等價(jià)數(shù)理最優(yōu)化模型 （有約束非線性最優(yōu)化問題）m i n　　? ???AaxaadxxcZ0)(.. ts ??????rsKkrsrskrsth , ?????????rsrskrskaKkaAahxrs,? 0,0 ??arskxh3 ． 非線性規(guī)劃基礎(chǔ)知識(shí)a. 極值問題a) 極值條件函數(shù))( xf在 0x處有極值的必要條件：0)(39。39。39。 ?oxfx0x極小值 極大值)(xf0)(39。考慮圖示情況， 21, PP分別是)( Xf在領(lǐng)域 21, RR上的最小點(diǎn)。如 21, PP所示，僅其附近領(lǐng)域上的最小點(diǎn)稱為局部極小點(diǎn)，對(duì)應(yīng)的函數(shù)值為局部極小值 （ l oc a l m i nm um ）。圖中 2P點(diǎn)既為局部最小點(diǎn)，也為全局極小點(diǎn)。因此， )( xf 在 0x處取得據(jù)局部極小值的１階必要條件為：0)()()(02010??????????nxxfxxfxxf??)( xf在 0x處取得據(jù)局部極小值的２階必要條件為0)(0??? XXHXT，并且對(duì)任意0?? x成立。因此，)( xH在 0x處必須是正則矩陣。c. 非線性規(guī)劃問題的解法a) 梯度法 ( 最速下降法 s t e e pe s t de s c e n t m e t h od )所謂梯度法是指在探索點(diǎn)的探索方向取該點(diǎn)梯度的相反方向。另外，梯度法在初期步驟的探索速度較快，之后隨著計(jì)算的進(jìn)行探索速度將變得非常緩慢。Step ２　0)( ??kxf，則結(jié)束計(jì)算。Step ５ 　 更 新 試 行 點(diǎn) 　kkkdxx*1????。梯度法示意圖 2x1x),( 11 xd),( 00 xd),( 11 xdb ） 牛頓法　　牛頓法不僅利用目標(biāo)函數(shù)的 1 階偏導(dǎo)數(shù)，而且還利用 2 階偏導(dǎo)數(shù)。0))(()( ????kkkxxxHxf ???? （ａ）所以，)]()([1 kkkkxfxHxx ????【 計(jì)算步驟 】Step １　令0?k，給出初始點(diǎn)0x。Step ３　解連立方程0)()( ???kkkdxHxf，求出探索方向kdStep ４　更新試行點(diǎn)kkkdxx ??? 1。牛頓法不進(jìn)行一維最優(yōu)化在反復(fù)計(jì)算的初期階段，有時(shí)步長過大，目標(biāo)函數(shù)得不到改良?！?Kuhn T uch er 定理 】設(shè) )( xf 為凸函數(shù)，)( xgi),2,1( mi ??? 為凹函數(shù)，并且連續(xù)可微，則 0*?x 為非線性問題解的必要充分條件為),(**?x成為下式的鞍點(diǎn) （ sad dl e poi n t ）或ＫＴ點(diǎn)。求圖中區(qū)間? ?ba ,中存在唯一最小點(diǎn)函數(shù))( xf的最小點(diǎn)時(shí)，? ?ba ,中的兩點(diǎn) 21, xx用以下方法確定：???????abxbabax12這時(shí)，如果 )()(12xfxf ? ，那么，最小點(diǎn)處于區(qū)間 ? ?2, xa。 ? 應(yīng)滿足的條件：???????1221xbxbaxax由第一式得：?)(1abbx ????)(2abax ???代入第二式，并整理得：?????1)15( ????。)(xfa 1x 2x bx（ 4 ）解的等價(jià)性與唯一性a ）解的 等價(jià)性證明 這里證明， Bec h m an n 的模型與 W ar dr op 的第一法則是等價(jià)的。根據(jù)庫恩－塔克條件：0),(**???rskrskhhLh?　和　?????????rsKkhhhLrsrskrsk,0,0),(**?0),(**???rshL??，??? rs由第一式得，0?rskh時(shí)，0),(**???rskhhL ?，????? rsKkrs,0?rskh時(shí)，0),(**???rskhhL ?，????? rsKkrs,這里，rskrs KkrsrskrsrskAaxarskhthhdwwchLrsa???????????????????????????? ?? ??? ??//)(0?rsrskaaAaxahxdxdwwcda????????????? ??/)(0 ，????? rsKkrs,AaKkrshhhxrsrskarskKkrskrskarsrskars?????????????????????????,//,??所以，????????????AarsrsrskaaarskrsKkxchL ,)(/,??又因?yàn)椋????Aarsrskaaacxc,)( ?所以有，0?rskh時(shí)，??????? rsKkcrsrsrsk,0?0?rskh時(shí)，??????? rsKkcrsrsrsk,0?b ）解的唯一性證明條件：式 （ 2 ） 式 （ 4 ）形成凸領(lǐng)域，并且式 （ 1 ）為狹義凸函數(shù)。Z函數(shù)為凸函數(shù)的條件為：0/22???axZ由式 （ 1 ）知，AaxcxZaaa????? ),(/badxxdcaaa?? (,0/)(時(shí)）????baxxZ20 ，ba ?(時(shí)），Aba ?? ,所以，海賽矩陣為：????????????nnnaaadxxdcdxxdcdxxdcZ/)(0/)(0/)(1112??????因?yàn)?，一般情況下，路阻函數(shù)為單增函數(shù)，所以，Aadxxdcaaa??? ,0/)(所以，有唯一解。【 記號(hào) 】K : 最短徑路和最小費(fèi)用已經(jīng)確定的節(jié)點(diǎn)集合。mF：最短徑路的途徑節(jié)點(diǎn)集合?！居?jì)算步驟】Ste p 1 設(shè)所有節(jié)點(diǎn)? ?j的局部最小費(fèi)用為??jc或?yàn)樽銐虼蟮闹?，并設(shè)??? KjFj,0。Ste p 2 檢查以節(jié)點(diǎn)i為起點(diǎn)的所有路段的終點(diǎn)? ?m，若滿足 mimdcc ??，則令iFdccmmim??? ,。?????????Kppccppj:),(m i n。St ep 4 如果??pc以外的節(jié)點(diǎn)是否全部被移到集合 K中，則結(jié)束計(jì)算?！咀疃虖铰返拿杜e】 利用 jF枚舉出任意節(jié)點(diǎn)j到起點(diǎn) o 的最短徑路：)()()()( ?????????bghjFfFgFhFj ??起點(diǎn) o【例題】用 Dijkstra 法計(jì)算下圖從點(diǎn) 1 到其它節(jié)點(diǎn)的最短經(jīng)路 。例如，從節(jié)點(diǎn)１到節(jié)點(diǎn)６的最短徑路為： 1)(4)(7)(6 476 ?????? FFF1 5 6 4 7 2 3 2 2 2 1 1 1 1 3 3 4 4 6 8 9 表　　 Di jk st ra 法的計(jì)算過程和結(jié)果路段 各節(jié)點(diǎn)的mc 局部最小徑路mF 最小費(fèi)用節(jié)點(diǎn)計(jì)算順序始點(diǎn)終點(diǎn) 節(jié)點(diǎn)號(hào)碼 節(jié)點(diǎn)號(hào)碼 }{m i nppc1 2 3 4 5 6 7 1 2 3 4 5 6 71 0 ∞ ∞ ∞ ∞ ∞ ∞ 0 0 0 0 0 0 0 12 1 2 ， 4 ， 5 0 2 ∞ 4 9 ∞ ∞ 0 1 0 1 1 0 0 23 2 3 ， 4 0 2 10 4 9 ∞ ∞ 0 1 2 1 1 0 0 44 4 5 ， 7 0 2 10 4 8 ∞ 6 0 1 2 1 4 0 4 75 7 3 ， 6 0 2 9 4 8 7 6 0 1 7 1 4 7 4 66 6 5 ， 7 0 2 9 4 8 7 6 0 1 7 1 4 7 4 57 5 4 ， 6 0 2 9 4 8 7 6 0 1 7 1 4 7 4 32. 全有全無法 （ al l o r no thin g m et ho d ）全有全無分配法是將 OD 交通需求沿最短經(jīng)路一次分配到路網(wǎng)上去的方法，也被稱為交通需求分配。全無 （ no th in g ）指對(duì)最短徑路以外的徑路不分配交通需求量。在美國芝加哥城交通解析中，首次獲得應(yīng)用?！痉峙溆?jì)算步驟】Ste p 1 令0,0 ??ijxn（始點(diǎn) i ，終點(diǎn) j 的路段交通量）。Ste p 3 按? ?ioc ?m i n 的相反順序，用下式求出流入節(jié)點(diǎn)j并處于最短徑路上的路段)(iFi→j間的交通量 ijx。1: 交通量發(fā)生點(diǎn) n 的 OD 對(duì) ns 的最短徑路經(jīng)過路段ij時(shí)。St ep 4 如果 n= N ，則結(jié)束計(jì)算。 N 為網(wǎng)絡(luò)中交通量發(fā)生點(diǎn)的集合。實(shí)際工作中，如何分割 OD 交通需求量是很重要的，一般多用 5 ― 10 分割，并且采用不等分。令 n=1 ， 0?nijx 。Ste p 3 用全有全無分配法將第 n 次分割 OD 交通需求量rsnt分配到最短經(jīng)路上。反之，令 n=n+ 1 返回 Ste p2 。4. 均衡分配 （ Fr an k W ol fe ）法St ep 1 給出初始可能解? ?kax，令 0?k 。St ep 2 更新路段費(fèi)用函數(shù))(kakaxc。用最短徑路搜索法求出各 OD 間的最短徑路，在用全有全無分配法求出探索方向? ?kay。將下式代入到目標(biāo)函數(shù)中，求出最佳探索步長*? 。設(shè) 1?和 2?為任意小數(shù)，若滿足下式，則結(jié)束計(jì)算。11)()( ?????? kakaAakakaccxx21/)(m a x ???? kakakaxxx【例題】設(shè)圖示交通網(wǎng)絡(luò)的 OD 交通需求量為 200?t 輛，各徑路的交通費(fèi)用函數(shù)分別為：11 hc ?? ，220 2 hc ?? ，33 hc ??試用全有全無分配法 、 增量分配法和均衡分配法求出分配結(jié)果，并進(jìn)行比較。利用該方法的以下結(jié)果：15,10,0,200321321????????? ccchhh因?yàn)椋?5,132?? ccc，所以，沒有得到均衡解。（ 1 ） 第 1 次分配全有全無分配法相同，徑路 1 最短。目標(biāo)函數(shù)為：1 2 51 0 0 05 0 05 0 00 1 2 1 2 233222211?????????? hhhhhhZ21 25?３． 均衡分配法【 模型 】m i n 2332222110 1 2 1 2 hhhhhhZ ??????.. ts ???31200kkh)3,2,1(,0 ?? khk（ 1 ） 用全有全無分配法求解初始可能解30 00,15,10,2520 ,0,20 0321030201?????????? Zccchhh。11)()( ?????? kakaAakakaccxx21/)(ma x ???? kakakaxxx顯然，收斂條件得不到滿足。這時(shí)的最短徑路為徑