現(xiàn)代化方法講座第3講

現(xiàn)代優(yōu)化方法講座

第二部分雙層規(guī)劃1

到目前為止，對于雙層規(guī)劃的求解算法歸納起來，可以分為五大類：2.5雙層規(guī)劃求解算法現(xiàn)代優(yōu)化方法講座（1）極點搜索法（ExtremePointSearchMethod）：這種方法主要用于求解雙層線性規(guī)劃，其基本觀點就是：雙層線性規(guī)劃問題的任何解都出現(xiàn)在下層問題的約束集合的極點位置。因此，首先可以利用各種方法來尋找約束空間的極點（不要求尋找全部極點），然后從中再找出雙層問題的局部最優(yōu)解或全局最優(yōu)解。

2

2.5雙層規(guī)劃求解算法現(xiàn)代優(yōu)化方法講座（2）K-T法（Karush-Kuhn-TuckerMethod，簡稱K-T法）

：這種方法將雙層問題中的下層問題用它的Karush-Kuhn-Tucker條件代替，主要用于求解雙層線性規(guī)劃問題，最初用于求解雙層線性資源控制問題。3

（3）下降法（DescentMethod）：這種方法是基于用各種可能的方法得到的下層問題對上層決策變量的梯度信息，主要用于求解非線性連續(xù)變量的雙層規(guī)劃問題。從本質(zhì)上講，這是一種迭代求解方法，利用得到的下層問題對上層決策變量的梯度信息來產(chǎn)生一系列使上層目標(biāo)函數(shù)減小的點。最具代表性的下降算法是基于靈敏度分析的求解算法?，F(xiàn)代優(yōu)化方法講座2.5雙層規(guī)劃求解算法4

（4）直接搜索法（DirectSearchMethod）

：直接使目標(biāo)函數(shù)最小的方法，如Abdulaal和LeBlanc（1979）使用的Hooke-Jeeves搜索法就屬于此類，在搜索解的過程中，這種方法取決于上層目標(biāo)函數(shù)值的變化?，F(xiàn)代優(yōu)化方法講座2.5雙層規(guī)劃求解算法5

（5）非數(shù)值優(yōu)化方法：這類方法主要包括模擬退火、遺傳算法和蟻群算法等。這種非數(shù)值優(yōu)化方法目前主要用來求解城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計問題（Cree和Masher，1998）及其它相關(guān)優(yōu)化問題，但由于此類求解算法在求解雙層規(guī)劃模型時具體的參數(shù)（如編碼長度等優(yōu)化參數(shù)）難以確定，所以收斂性一般難以保證，況且在實踐應(yīng)用中可解釋性也不理想。所以在求解具體雙層規(guī)劃模型時還屬于探索階段。

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃應(yīng)用6

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃的應(yīng)用（1）交通已有大量文獻(xiàn)將雙層規(guī)劃應(yīng)用于交通領(lǐng)域?！?/p>

網(wǎng)絡(luò)設(shè)計問題（NetworkDesignProblem）。相互作用網(wǎng)絡(luò)規(guī)劃者決定投資費(fèi)用目的使網(wǎng)絡(luò)中系統(tǒng)費(fèi)用最小用戶選擇出行路徑目的使自己的出行費(fèi)用最小相互作用投資費(fèi)用運(yùn)行費(fèi)用取決于交通流量7

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃的應(yīng)用（1）交通☆

O-D需求估計問題?！?/p>

交通信號控制問題。如何進(jìn)行信號控制，使車輛使用者作出合理反應(yīng)，減少交通堵塞和延遲，也可作為雙層規(guī)劃問題來進(jìn)行優(yōu)化解決。

8

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃應(yīng)用（續(xù)）（2）管理只顧自己的局部利益，而忽略了整體利益，是目前管理中存在的一個比較普遍的問題。雙層規(guī)劃的特點恰恰是從整體的角度出發(fā)，兼顧全局，希望達(dá)到整體最優(yōu)。因此，在管理問題中應(yīng)用雙層規(guī)劃方法，將會取得很好的效果。這方面的研究也比較多。9

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃應(yīng)用（續(xù)）（2）管理☆資源分配。資源分配是一類比較復(fù)雜的管理問題，上層部門將資源分配給多個下層部門，下層部門根據(jù)分配的資源和自己已有的資源組織生產(chǎn)，使自己的效益最大。一些公共設(shè)施建設(shè)，如電站、水庫、污物處理站建設(shè)等，實質(zhì)上也是資源分配問題，只不過下層不是部門的效益最大，而是公共設(shè)施產(chǎn)生的社會效益最大?！顑r格問題。例如應(yīng)用到鐵路旅客票價制定問題。

10

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃應(yīng)用（續(xù)）☆供應(yīng)鏈管理。供應(yīng)鏈管理的重要性得到認(rèn)可。過去，廠商與其供應(yīng)商持?jǐn)硨B(tài)度，都想從對方那里獲得利潤，導(dǎo)致產(chǎn)品開發(fā)周期過長、產(chǎn)品質(zhì)量無法提高、成本居高不下等問題。如何使廠商與供應(yīng)商緊密合作，達(dá)到雙贏的目的，成為一個熱點研究問題。建立雙層規(guī)劃模型，以各成員利潤最大化為下層目標(biāo)，以供應(yīng)鏈的綜合績效為上層目標(biāo)，來進(jìn)行優(yōu)化研究，具有重要的應(yīng)用價值和現(xiàn)實意義。11

現(xiàn)代優(yōu)化方法講座2.6雙層規(guī)劃應(yīng)用（續(xù)）☆生產(chǎn)計劃?！钇渌矫嫒绫Σ渴?、設(shè)施定位、政策規(guī)劃等。（3）工程設(shè)計問題?？傊p層規(guī)劃的上層一般是保證系統(tǒng)最優(yōu)，下層保證個體最優(yōu)。12

2.7.1城市交通平衡網(wǎng)絡(luò)設(shè)計問題

交通運(yùn)輸供給能力的不足，嚴(yán)重影響了旅客和各種商品在自然空間上的合理流動，阻礙了國民經(jīng)濟(jì)的快速發(fā)展，為了克服這一現(xiàn)象，就需要增加交通運(yùn)輸能力，為此必須增加對交通基礎(chǔ)設(shè)施建設(shè)的投資力度。

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

資金不足是最大障礙網(wǎng)絡(luò)設(shè)計時需要決策13

2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

實質(zhì)上是在一定約束條件下的最優(yōu)投資決策問題。

對現(xiàn)有交通網(wǎng)絡(luò)進(jìn)行改進(jìn)城市交通網(wǎng)絡(luò)設(shè)計問題研究內(nèi)容資金投入最少增加新的路段或更新改善已有路段的能力調(diào)整路口的交通信號建設(shè)立交橋等使整個交通網(wǎng)絡(luò)某種系統(tǒng)性能最優(yōu)14

2.7.2用雙層規(guī)劃描述城市交通網(wǎng)絡(luò)設(shè)計問題

利用一定的投資對交通網(wǎng)絡(luò)進(jìn)行改善由交通規(guī)劃部門決策，但改善后的路網(wǎng)效果如何需看用戶的出行反應(yīng)。因此城市交通網(wǎng)絡(luò)設(shè)計問題可以用雙層規(guī)劃進(jìn)行描述。網(wǎng)絡(luò)設(shè)計問題就是在考慮了投資對整個系統(tǒng)中的供應(yīng)方和需求方的影響之后，尋找并選擇最優(yōu)投資策略使系統(tǒng)的社會福利最大?，F(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

15

在進(jìn)行網(wǎng)絡(luò)設(shè)計時，如果不考慮網(wǎng)絡(luò)用戶的路徑選擇行為，而一味的增加或改建已有路段，有時不僅不能達(dá)到改善整個系統(tǒng)交通狀況的目的，反而會使整個系統(tǒng)的交通狀況更加惡化，表現(xiàn)為系統(tǒng)總費(fèi)用不僅沒有減少，反而會增加。（舉例）因此在進(jìn)行交通網(wǎng)絡(luò)設(shè)計時，必須考慮網(wǎng)絡(luò)中用戶的路徑選擇行為，即進(jìn)行規(guī)劃時要考慮路網(wǎng)改建后是否能達(dá)到預(yù)先所期望的目標(biāo)?，F(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

16

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

考慮一個網(wǎng)絡(luò)如圖所示，有四條路段，四個節(jié)點，一個O-D對（從節(jié)點O到節(jié)點D，總需求量為6）。路段1～4的阻抗函數(shù)（單位為：分鐘）分別為：

OD網(wǎng)絡(luò)中只有兩條路徑，第一條通過節(jié)點1、3（用1→3表示），第二條通過節(jié)點1、4（用1→4表示）。由于網(wǎng)絡(luò)的對稱性，O-D需求量平均分配到兩條路徑1→3和1→4上。每條路徑上流量為3。17

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

OD123418

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

現(xiàn)增加一條路段5，其路段阻抗函數(shù)為：此時，網(wǎng)絡(luò)中又出現(xiàn)了第三條路徑,通過節(jié)點1、5、4（用1→5→4表示）OD1234這個新網(wǎng)絡(luò)的UE解是可見增加網(wǎng)絡(luò)固定設(shè)施通行能力后，并未如預(yù)料的那樣減少擁擠程度，反而增加了。19

現(xiàn)代優(yōu)化方法講座其中由下述規(guī)劃求得：

2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

因此，雙層網(wǎng)絡(luò)設(shè)計模型就是在滿足投資預(yù)算約束條件下，考慮了網(wǎng)絡(luò)用戶路徑選擇行為后，尋找最佳路網(wǎng)改進(jìn)方案使系統(tǒng)目標(biāo)函數(shù)最優(yōu)。

交通規(guī)劃者為了達(dá)到使社會效益最大而采取的最優(yōu)決策反映了網(wǎng)絡(luò)中用戶的路徑選擇行為上層規(guī)劃下層規(guī)劃20

這種雙層規(guī)劃是在下層保證用戶選擇行為符合用戶平衡配流原則情況下的網(wǎng)絡(luò)設(shè)計，因此稱為城市交通網(wǎng)絡(luò)平衡設(shè)計問題。

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

21

(1)下層用戶平衡配流問題

著名的Braess詭異現(xiàn)象表明：在進(jìn)行網(wǎng)絡(luò)設(shè)計時，如果不考慮網(wǎng)絡(luò)用戶的路徑選擇行為，而一味的增加或改建已有路段，有時不僅不能達(dá)到改善整個系統(tǒng)交通狀況的目的，反而會使整個系統(tǒng)的交通狀況更加惡化，表現(xiàn)為系統(tǒng)總阻抗不僅沒有減少，反而會增加，因此在進(jìn)行交通網(wǎng)絡(luò)設(shè)計時，必須考慮網(wǎng)絡(luò)中用戶的路徑選擇行為。

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

22

如何描述用戶的路徑選擇行為？現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

最常用的是交通流量分配理論它即是根據(jù)用戶出行選擇行為得到的路徑選擇結(jié)果用戶平衡配流23

現(xiàn)代優(yōu)化方法講座Wardrop平衡配流原則描述如下：在起終點之間所有可供選擇的路線中，使用者所利用的各條路線上的出行費(fèi)用全都相等，而且不大于未被利用路線上的出行費(fèi)用。滿足這一原則的交通狀態(tài)被定義為Wardrop平衡狀態(tài)，上述配流原則又可稱為用戶平衡配流。Beckmann采用以下數(shù)學(xué)形式描述Wardrop平衡狀態(tài)：

其中為平衡狀態(tài)下O-D對之間的出行費(fèi)用。

24

現(xiàn)代優(yōu)化方法講座在用戶平衡（UE）配流模型的例子中，只有路段費(fèi)用是流量的嚴(yán)格增函數(shù)的假定，在這種情況下，可以表示成一個變分不等式模型，并且有唯一路段解。如果再加上一個假定，即路段費(fèi)用僅僅是該路段流量的函數(shù)，與其它路段上的流量沒有關(guān)系，那么就可以得到一個等價的規(guī)劃模型。

25

現(xiàn)代優(yōu)化方法講座Beckmann在提出了用戶平衡配流模型如下：

s.t.，（1.3）

，（1.4）

，（1.5）

（1.2）26

一般來說，下層模型有如下幾種：①固定需求條件下的用戶平衡模（UE）型。②彈性需求條件下的UE模型。③運(yùn)量分布與UE配流的組合模型。④隨機(jī)用戶平衡模型。

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

27

(2)上層網(wǎng)絡(luò)優(yōu)化問題

在交通網(wǎng)絡(luò)設(shè)計問題中，有兩種投資策略，一種是投資改進(jìn)現(xiàn)有網(wǎng)絡(luò)中的某些路段，增加其能力，另一種是在現(xiàn)有網(wǎng)絡(luò)中增加新的路段。與此相對應(yīng)，上層決策變量有二種形式，如下：①離散形式的上層決策變量----離散網(wǎng)絡(luò)設(shè)計問題DNDP（DiscreteNetworkDesignProblem）。②連續(xù)形式的上層決策變量----連續(xù)網(wǎng)絡(luò)設(shè)計問題CNDP（ContinuousNetworkDesignProblem）。

2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

28

2.7.3固定需求條件下的城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計問題

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

常用的符號定義如下：

城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計問題，就是在網(wǎng)絡(luò)用戶的路徑選擇行為符合用戶平衡配流準(zhǔn)則的前提條件下，通過改進(jìn)現(xiàn)有網(wǎng)絡(luò)中的某些路段（增加路段的能力)而使整個網(wǎng)絡(luò)達(dá)到某種性能指標(biāo)最優(yōu)的目的。29

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

：路段的能力增加，

：路段的能力增加的向量表示（上層決策變量），。：路段的阻抗函數(shù)，。：路段能力增加的投資函數(shù)，。：匹配投資費(fèi)用與系統(tǒng)總阻抗單位的系數(shù)。30

上層規(guī)劃模型現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

上層問題是一個標(biāo)準(zhǔn)的城市交通網(wǎng)絡(luò)設(shè)計問題，第一個式子是城市交通網(wǎng)絡(luò)設(shè)計問題的目標(biāo)函數(shù)，處于上層的網(wǎng)絡(luò)規(guī)劃者對某些路段進(jìn)行投資，增加這些路段的能力，目的是使使整個網(wǎng)絡(luò)的系統(tǒng)總阻抗和總的投資額之和最??；約束要求路段能力增加非負(fù)。31

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

其中由下述規(guī)劃求得下層問題是一個標(biāo)準(zhǔn)的用戶平衡配流問題，處于下層的網(wǎng)絡(luò)用戶在給定路段能力的情況下，其路徑選擇行為符合UE準(zhǔn)則。32

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

24B13A5DC33

現(xiàn)代優(yōu)化方法講座2.7雙層規(guī)劃在城市交通網(wǎng)絡(luò)平衡設(shè)計問題中的應(yīng)用

需求量1002001.341.210.000.971.1012.7811.730.0010.3411.7434國外鐵路運(yùn)價決定原理主要：運(yùn)輸價值原則:所研究的運(yùn)輸服務(wù)對需求者的使用價值或效用。

現(xiàn)代優(yōu)化方法講座2.8鐵路旅客票價制定的雙層規(guī)劃模型

需求價格表示的是旅客票價的最高限度，如果旅客票價高于這個價格，旅客就會放棄選擇鐵路作為出行方式，而選擇其他的交通方式（公路或民航）。35

現(xiàn)代優(yōu)化方法講座2.8鐵路旅客票價制定的雙層規(guī)劃模型

表示的是旅客票價的最低限度，如果旅客票價低于這個價格，鐵路客運(yùn)部門就難以在客運(yùn)市場中生存和發(fā)展。運(yùn)輸成本原則:運(yùn)價應(yīng)當(dāng)?shù)扔谶\(yùn)輸服務(wù)的生產(chǎn)費(fèi)用。供給價格36

現(xiàn)代優(yōu)化方法講座2.8鐵路旅客票價制定的雙層規(guī)劃模型

在市場經(jīng)濟(jì)條件下，鐵路旅客票價的制定應(yīng)該兼顧成本和市場需求兩方面的因素。37

現(xiàn)代優(yōu)化方法講座上層決策部門：鐵路管理部門決策變量：鐵路客票價格下層決策：旅客的出行行為決策變量：交通流量相互作用

決策部門只能通過政策和管理來影響旅客在出行時對于運(yùn)輸方式的選擇，例如通過票價的調(diào)整來使得旅客的選擇行為發(fā)生改變，但不能控制他們的選擇。

旅客都是根據(jù)自己的需要及習(xí)慣來選擇運(yùn)輸方式。2.8鐵路旅客票價制定的雙層規(guī)劃模型

38

出行者希望自己總的出行費(fèi)用最低；鐵路客運(yùn)管理部門總是希望鐵路的客運(yùn)收入最大。這看起來是相互矛盾的，但這兩方面相互作用的結(jié)果是取得共同的平衡點，即上述雙層規(guī)劃問題的最優(yōu)解。

2.8鐵路旅客票價制定的雙層規(guī)劃模型

其它因素不變鐵路票價上升鐵路客流量減少，轉(zhuǎn)移到其它運(yùn)輸方式鐵路票價下降鐵路客流量增加，吸引其它運(yùn)輸方式的客流39

現(xiàn)代優(yōu)化方法講座2.8.1多種交通運(yùn)輸方式競爭條件下鐵路客票價格制定的雙層規(guī)劃模型

2.8鐵路旅客票價制定的雙層規(guī)劃模型

城市之間的客流分配，一般不存在路徑的選擇，而只有運(yùn)輸方式的選擇。40

現(xiàn)代優(yōu)化方法講座2.8鐵路旅客票價制定的雙層規(guī)劃模型從定量角度出發(fā)，既保障了出行者使自己的出行費(fèi)用最小，又能使鐵路客運(yùn)在市場競爭中取得最大的經(jīng)濟(jì)效益。

上層規(guī)劃:

描述為鐵路客運(yùn)管理部門在政府規(guī)定的范圍內(nèi)制定最佳的客票價格以使鐵路客運(yùn)的經(jīng)濟(jì)效益為最大。下層規(guī)劃:描述城市間多模式運(yùn)輸競爭條件下，客流在不同運(yùn)輸方式之間的分配模式，目標(biāo)是使每個出行者在出行過程中的出行費(fèi)用最低。41

現(xiàn)代優(yōu)化方法講座

一般情況下，旅客總是力圖選擇從起點到終點之間總的廣義出行費(fèi)用最低的客運(yùn)運(yùn)輸方式，出行時間、旅客票價、安全、方便舒適度等比如鐵路，假定一開始它的出行費(fèi)用是最低的如果所有出行者都選擇某一種客運(yùn)運(yùn)輸方式。那么隨著該運(yùn)輸方式客流需求的增加，它總的出行費(fèi)用就會上升，例如票價上升，出行時間變大，服務(wù)質(zhì)量下降等。使得一部分旅客放棄選擇這種運(yùn)輸方式，而選擇其它運(yùn)輸方式，而別的運(yùn)輸方式出行費(fèi)用也會隨客流需求的增加而上升。旅客的選擇行為42

現(xiàn)代優(yōu)化方法講座最終，在不同的客運(yùn)運(yùn)輸方式之間會達(dá)到一種客流分配的穩(wěn)定的均衡狀態(tài)。這種均衡狀態(tài)可以描述為：在城市之間的所有可供選擇的客運(yùn)運(yùn)輸方式中，旅客所利用的各種客運(yùn)運(yùn)輸方式的廣義出行費(fèi)用全部相等，并且不大于未被利用的客運(yùn)運(yùn)輸方式的出行費(fèi)用。

旅客的選擇行為43

現(xiàn)代優(yōu)化方法講座旅客的選擇行為可以用下面的數(shù)學(xué)形式來描述這種均衡狀態(tài)如果如果

其中表示城市間第（）種運(yùn)輸方式的廣義出行費(fèi)用，表示均衡狀態(tài)下城市間的廣義出行費(fèi)用，表示城市間第（）種運(yùn)輸方式的客流量，為城市間所有運(yùn)輸方式的集合。44

現(xiàn)代優(yōu)化方法講座其中函數(shù)是運(yùn)輸方式的廣義費(fèi)用函數(shù)，在這個函數(shù)中不同運(yùn)輸方式的客流量是自變量，即（）。取不同的形式，便可以得到不同的客流量在客運(yùn)運(yùn)輸方式之間的分離模式，最常用的廣義費(fèi)用函數(shù)形式有冪函數(shù)形式和對數(shù)函數(shù)形式。第一個約束表示城市間總的客流需求是已知并且固定的，表示表示城市間總的客流需求；最后一個約束為變量的非負(fù)約束。

旅客的選擇行為45

現(xiàn)代優(yōu)化方法講座（U）

其中由下層模型得出（L）

表示城市間鐵路客運(yùn)的客流量，表示城市間鐵路客運(yùn)的旅客票價，表示鐵路客運(yùn)中的平均客運(yùn)成本。and分別表示城市間的鐵路客運(yùn)的平均客運(yùn)成本和旅客票價最高限?？梢岳斫鉃檫m當(dāng)?shù)倪\(yùn)輸成本與適當(dāng)?shù)睦麧欀?，可以理解為運(yùn)輸成本與政府允許的利潤上限之和(或消費(fèi)者能承受的最大擔(dān)負(fù)能力)。

2.8鐵路旅客票價制定的雙層規(guī)劃模型

46

現(xiàn)代優(yōu)化方法講座例：確定從北京到天津合理的鐵路旅客票價費(fèi)用綜合考慮出行時間、票價、方便性、舒適性、安全性等多種因素。根據(jù)《京津唐客運(yùn)市場調(diào)查報告》北京到天津的總客運(yùn)量約25000。從北京到天津存在兩種運(yùn)輸方式：鐵路和公路天津北京鐵路公路47

現(xiàn)代優(yōu)化方法講座其中為出行時間因素，表示票價因素，為方便、舒適和安全等綜合因素；（）為待定參數(shù)。表示不同運(yùn)輸方式的效用，為待定參數(shù)。

48

現(xiàn)代優(yōu)化方法講座鐵路客運(yùn)量（人次）初始值（元）最優(yōu)旅客票價（元）511951.8826.661011950.7126.66354011949.3726.6611948.6726.6649

現(xiàn)代優(yōu)化方法講座模擬退火算法是模仿熱力學(xué)中固體退火的隨機(jī)機(jī)制設(shè)計的。在熱力學(xué)中，當(dāng)一個物理系統(tǒng)（固體）處在高溫時，它的大量的原子是處于無序的高溫運(yùn)動狀態(tài)。為使原子進(jìn)入有序狀態(tài)，要減少該系統(tǒng)的溫度。如要使該固體變成晶體（晶體的原子是高度格型有序排列的），就要首先將固體加熱到能使其原子可進(jìn)行重新排列的高溫，然后逐步小心地冷卻它，使其在每個溫度級都能達(dá)到熱平衡狀態(tài)，直至它冷卻成晶體為止。這樣的冷卻過程就叫“退火（annealing）”。

求解雙層規(guī)劃的模擬退火算法50

現(xiàn)代優(yōu)