【正文】 所以，繼續(xù)用全有全無分配法求解，得：0,0,200131211??? yyy)(,)(2221???????? hh023?h222 ????????????Z ?????求最佳探索步長*? 的方法：將)(1 kakakakaxyxx ?????代入目標(biāo)函數(shù)中，得m i n10 ?? ?　? ????Aaxyxakakakadwwc)(0)(?這時。返回 （ 2 ）繼續(xù)修正計算 。（ 2 ） 求最佳搜索方向繼續(xù)用全有全無分配法求解，得：0,200,0030201??? yyy（４）一維搜索 , 求最佳搜索步長*? 和交通量修正令6 ??)0200(,)2022(0211???????? hh,013?h15,321????????? ccc22200 1 2 2 30 1 2 2 ????????????Z 1 0 2 3 ?????（５） 收斂判定設(shè) 1?= 2?=0 .01 。15,10,151 0 ,0,1 0 0321321????????? ccchhh（２）第 2 次分配　最短徑路變?yōu)閺铰?2,0,100,10021321??????????? cchhh，153?c這時，結(jié)果接近于均衡解。目標(biāo)函數(shù)：3 00 00 12 12 233222211??????? hhhhhhZ２． 增量分配法采用 2 等分。徑路 3 徑路 1 D 徑路 2 解：1 ． 全有全無分配法 由路段費用函數(shù)可知，在路段交通量為零時，徑路 1最短。反之，返回 Ste p 2 。)(1 kakakakaxyxx ?????Ste p 5 收斂判定。Ste p 4 一維搜索。St ep 3 搜索目標(biāo)函數(shù)的下降方向。一般用前述全有全無分配法求解初始可能解。 N 為分割次數(shù)。Ste p 4 如果 n=N ，則結(jié)束計算。 Ste p 2 更新路段費用)(1??nijijnijxcc?！痉峙溆嬎悴襟E】Ste p 1 根據(jù)需要，以適當(dāng)?shù)男问椒指?OD 交通需求量，即rsnr s ntt ??。3. 增量分配法 （ I nc r ement al as sign m en t m et ho d ）增量分配法時將 OD 交通需求量進(jìn)行適當(dāng)形式的分割（分割數(shù) 、 等分或不等分），然后用全有全無分配法，將分割后的 OD 交通需求量逐漸分配到網(wǎng)絡(luò)上去。反之，令 n= n+ 1 返回 St ep2 。nrsij,?=0: 交通量發(fā)生點 n 的 OD 對ns的最短徑路不經(jīng)過路段ij時。nsijnsnijnijtxx ????? 11?nijx：分配到第1?n個交通量發(fā)生點時，路段ij的交通量。Ste p 2 搜索第 n 個起點到其余各點的最短徑路，求出最短徑路費用? ?ioc ?m i n 和 iF。另外，后述增量分配法和均衡分配法中頻繁使用。全有全無分配法應(yīng)用于沒有通行能力限制的網(wǎng)絡(luò)交通交通量分配等場合。顧名思義，全有 （ al l ）指將 OD 交通需求一次性地全部分配到最短徑路上。1 5 6 4 7 2 3 2 2 2 1 1 1 1 3 3 4 4 6 8 9 節(jié)點及節(jié)點號碼 路段及路段費用 解：將計算過程列于下圖和 表，可以看出，到第７步 為止，全部節(jié)點都被移到集合 K 中，結(jié)束計算。反之，令ji ?，返回 St ep 2 。將節(jié)點j移到集合K。St ep 3 對最小費用尚未確定 的節(jié)點集合?K 中的所有節(jié)點，按下式計算局部最小費用的最小值 jc。設(shè) o 為起點，對節(jié)點 o 有ojco?? ,0，將節(jié)點 o 移到集合 K 。jc：以 o 為起點的最小費用。?K：最短徑路尚未確定的局部最小費用節(jié)點集合。第 4 節(jié) 用戶均衡問題的解法1 ． D ij ks tra 法 （記號確定法）該方法是從離起點最近的點開始，逐漸向全方位枚舉出最短徑路的方法。由式 （ 2 ） 式 （ 4 ）知都為線性函數(shù)，所以形成的領(lǐng)域為凸領(lǐng)域。 對 Bec h m an n 的模型構(gòu)造拉格朗日方程如下：????????rsKku r srskrsrsthhZhL )()(),( ??0?rskh其中，rs?為 ODrs的拉格朗日系數(shù)。因為，?的值恰好與黃金分割比相等，所以被稱為黃金分割法。相反，則處于區(qū)間 ? ?bx ,1。????iiixgxfx )()(),( ??鞍點：),(),(),(****??? xxx ?????0 ),( ?x?? ),(** ?x?x ),(**?x 為鞍點的條件：),2,1(,0,0)()(),(1****njxxxgxxfxxjmjiijj???????????????????),2,1(,0)()(****njxxgxxfxj i jiijj????????????????????? ? ?),2,1(,0,0)(),(***mixgxxiij????????????),2,1(,0)(**mixgiii????? ?0*?jx時，0),(**????jxx ?),2,1( mj ???0*?jx時，0),(**????jxx ?0*?i?時，0),(**????ix??),2,1( ni ???0*?i?時，0),(**????ix??圖 庫恩 塔克條件示意圖)(x? )(x?0?x 0?x)(??)(??0?? 0??(3 ) 一維搜索黃金分割法，斐波那契 （ Fibo nac ci ）法和曲線近似法【 黃金分割法 】黃金分割法是通過比較含有最小點的區(qū)間中兩點的函數(shù)值，將區(qū)間范圍按一定比例縮小，并且將兩點中的一點與上次的函數(shù)值比較求出最小點的反復(fù)計算方法。ｄ . 有約束非線性規(guī)劃問題的解法m i n )( xf.. ts ,0)( ?xgi 　),2,1( mi ???,0?jx 　 ),2,1( ni ??? 求解有約束非線性規(guī)劃問題的必要充分條件，Kuh n T uc he r 定理是非常重要的。令1?? kk，返回 Step ２。Step ２　0)( ??kxf，則結(jié)束計算?！　⒛繕?biāo)函數(shù)進(jìn)行泰勒展開，有：))(()(21)()()()(kkkkTkkxxxHxxxfxxxfxf ???????其中，)(kxH為)( xf在kx點的海賽矩陣。令1?? kk，返回 Step ２。Step ３　求出搜索方向　)(kkxfd ???Step ４　給出 搜索 步長　從使)(kkdxf ??最小的最佳*?值?！?計算步驟 】Step １　令0?k，給出初始點0x。假設(shè)kx為探索點，其探索方向為：Tnkkkkxxfxxfxxfd????????????????)(,)(,)(21??因為，在kx附近，梯度方向為傾斜度的最大方向，所以在局部最小點附近為使得函數(shù)取得最小值的最佳方向．然而，探索點有偏離，則不能保證是較好的探索方向。a ） 有約束非線性規(guī)劃mi n )( xf.. ts　,0)( ?xgi 　),2,1( mi ???構(gòu)造拉格朗日方程：????iiixgxfx )()(),( ??其最佳解應(yīng)滿足：?????????i jiijjxxgxxfxx )()()(?0)()(?????xgxxiji?為拉格朗日系數(shù)。對任意0?x，0?AxxT時，矩陣 A 正則 （ po s i t i ve de f i n i t e ）。局部極小點與全局極小點)(xf2x1x1P 2P1R 2RRb ． 非線性規(guī)劃的種類a ） 無約束非線性規(guī)劃m i n )( xf 為了求出)( xf在 0x附近的變化，采用泰勒展開如下：???????????? xxHxxxfxfxxfTT)(21)()()(0000其中，??????????????nTxxfxxfxxfxf)(,)(,)()(21???????????????????????????????????????????????nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxH2222122222212212212212)()()()()()()()()()(??????????)( xH為函數(shù))( xf的海賽矩陣 ( H e s s i a n m a t ri x ) 。在全域上，)( Xf取最小值的點為全局最小點，其值為全局極小值 （ g l oba l m i nm u m ）。但是， 1P并非是全域R上的最小點。 ?oxf0xxa) 局部極值和全局極值設(shè)函數(shù))( Xf為向量),(21 nxxxX ???， RX ? ，若)()(0XfXf ?，則稱 0X為)( Xf的最小點。0?xf→ 極大值)(xf0)(39。0?xf→ 極小值0)(39。0?xf函數(shù))( xf在 0x處有極值的充分條件：0)(39。x ox 1xt２． W a r dr op 第一法則的等價最優(yōu)化問題W a r dr op 法則理論上合理，實際求解非常困難。徑路 2 徑路 1 1 2 3 2 2 徑路 2 徑路 1 1 2 3 2 2 （ 1 ） 用戶均衡時的交通量與行駛時間徑路 2 徑路 1 O D 交通量 時間 通行能力 ??????????????????? ??aaaaa Cxcxc 1)0()(c )(22 xc )( 11 xct2x 39。將下表中按用戶均衡分配法分配到網(wǎng)絡(luò)上去。rst： OD 對rs間最短徑路的行駛時間。rskC： OD 對rs間第k條徑路的行駛時間。但是，實際吸引點的確定較難。rsD ：點 j 為吸引點 s 時。0 ：點 j 為非發(fā)生，吸引點時。?為使? ?krskp 1的系數(shù)。１：路段 （ji ,）被徑路k包含時。)(),( jsis：由終點到的行駛時間。有效徑路 （ E ff i c i e nt P a t h ） ： 在選擇徑路上不應(yīng)產(chǎn)生返回現(xiàn)象的徑路。當(dāng)???時，分配結(jié)果將與均衡分配法一致。如圖所示道路網(wǎng)，1??和30??時的分配結(jié)果如表所示。?rsak ,?０： OD 交通rs的徑路k不通過路段 a 時。α , β ：系數(shù)。av：路段ａ的交通