第10章-雙層規(guī)劃解析課件_第1頁
第10章-雙層規(guī)劃解析課件_第2頁
第10章-雙層規(guī)劃解析課件_第3頁
第10章-雙層規(guī)劃解析課件_第4頁
第10章-雙層規(guī)劃解析課件_第5頁
已閱讀5頁,還剩81頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

第10章雙層規(guī)劃

BiLevelProgramming第10章雙層規(guī)劃BiLe1

層次性是系統(tǒng)的六大特征之一。社會---不斷發(fā)展,實際問題---規(guī)模越來越大,結構越來越復雜,進行決策的人也越來越多,而且這些決策者各自處于不同的層次上。一般,高一級決策機構(者)對下一級決策機構(者)行使某種控制、引導權,而下一級決策機構(者)在這一前提下,亦可以在其管理職責范圍內行使一定的決策權,但這種決策權處于從屬地位。10.1雙層規(guī)劃簡介層次性是系統(tǒng)的六大特征之一。10.2

另外,在這種多層次決策系統(tǒng)中,每一級都有自身的目標函數。高層機構的決策目標:重要、權威、具有全局性。最終的決策結果往往是尋求使各層決策機構之間達到某種協(xié)調的具體方案。

10.1雙層規(guī)劃簡介既可使最高層決策機構的目標達到“最優(yōu)”,也可使作為上級決策“約束”的較低層決策機構的目標在從屬位置上相應達到“最優(yōu)”。另外,在這種多層次決策系統(tǒng)中,每一級都3

一般稱具有以上基本特征的決策問題為主從遞階(或多層)決策問題。主從遞階決策問題最初是由VonStackelberg于1952年在研究市場經濟問題時提出的.因此此問題有時候也稱為Stackelberg問題,是一對策論問題,決策者有上下層關系和不同目標,但策略集通常是彼此分離。一般稱具有以上基本特征的決策問題為主從遞階(或多層)4

20世紀60年代,Dantzig和Wolfe提出了大規(guī)模線性規(guī)劃的分解算法,相當于承認有一個核心決策者,他的目標高于一切,其他各層次的決策者實現(xiàn)自己的目標只不過是為實現(xiàn)核心決策者的目標的一種分工?,F(xiàn)在的多層規(guī)劃承認有最高決策者,但允許下層決策者有各自不同的利益。20世紀60年代,Dantzig和Wolfe提出了大5

20世紀70年代發(fā)展起來的多目標規(guī)劃通常是尋求一個決策者的互相矛盾的多個目標的折衷解,有些技術,如分層優(yōu)化,也可用來求層次問題,但下層決策不影響上層,可以逐層獨立求解。而當前的多層規(guī)劃正是要強調下層決策對上層目標的影響,因此多層規(guī)劃問題通常不能逐層獨立求解。20世紀70年代發(fā)展起來的多目標規(guī)劃通常是尋求一個決6

20世紀70年代以來,人們在各種現(xiàn)實的層次分散系統(tǒng)優(yōu)化決策問題的研究中,遇到了用上述方法不能解決的實際問題,開始尋找各種特定的方法解決這些問題,逐漸形成了多層規(guī)劃的概念和方法。如:Cassidy(1971)的政府政策效力分析,Kyland(1975)的經濟層次分析,Bracken(1973-1977)等人的戰(zhàn)備武器配置研究,Candler和Norton(1977)的奶制品工業(yè)模型和墨西哥農業(yè)模型等。20世紀70年代以來,人們在各種現(xiàn)實的層次分散系統(tǒng)優(yōu)7

多層規(guī)劃(MultilevelProgramming)一詞就是Candler和Norton在其論文中提出的,它的原意是一組嵌套著的數學規(guī)劃問題,即在約束條件中含有優(yōu)化問題的數學規(guī)劃。20世紀80年代至今,多層規(guī)劃的數學模型更加明確和形式化了,國內外學者也發(fā)表了許多有意義的成果。多層規(guī)劃(MultilevelProgrammin8

總之,在過去20年中,多層規(guī)劃的理論、方法及應用都有很大發(fā)展,正在逐漸形成一個新的運籌學分支。目前,很多國家對多層規(guī)劃的研究都非常重視,把它列為科學基金資助項目,并取得了巨大成功??傊谶^去20年中,多層規(guī)劃的理論、方法及應用都有9

最為常見且得到廣泛研究與應用的多層規(guī)劃是雙層規(guī)劃問題,即考慮只有兩層決策者的情形。這是因為現(xiàn)實的決策系統(tǒng)大都可以看成雙層決策。例如:中央和地方,公司和子公司,工廠的廠部和車間,高校的校部和院所等。實際上任何多層決策系統(tǒng)都是一系列雙層決策系統(tǒng)的復合。最為常見且得到廣泛研究與應用的多層規(guī)劃是雙層規(guī)劃10

雙層規(guī)劃是具有兩個層次系統(tǒng)的規(guī)劃與管理(控制)問題。很多決策問題由多個具有層次性的決策者組成,這些決策者具有相對的獨立性,即是說上層決策只是通過自己的決策去指導(或引導)下層決策者,不直接干涉下層的決策;而下層決策者只需把上層的決策作為參數或約束,它可以在自己的可能范圍內自由決策。雙層規(guī)劃是具有兩個層次系統(tǒng)的規(guī)劃與管理(控制11

如果組成這種上、下層關系不止一個時,這樣的系統(tǒng)為多層決策系統(tǒng)。如果只有一個上、下層關系時,這樣的系統(tǒng)通常稱為雙層規(guī)劃問題。由此可見,雙層規(guī)劃問題雖然是多層決策系統(tǒng)的特殊形式,但它是最基本的形式。

12

雙層規(guī)劃:雙層規(guī)劃是雙層決策問題的數學模型,它是一種具有雙層遞階結構的系統(tǒng)優(yōu)化問題,上下層問題都有各自的目標函數和約束條件。上層問題的目標函數和約束條件不僅與上層決策變量有關,而且還依賴于下層問題的最優(yōu)解,而下層問題的最優(yōu)解又受上層決策變量的影響。雙層規(guī)劃:13

雙層規(guī)劃的意義在于:可以同時考慮全局和個體雙方的利益,并保證首先從全局出發(fā),體現(xiàn)了顧全大局、先集體后個人的思想。目標是做到既不舍小家,又能顧大家??梢院芎玫亟鉀Q許多實際問題。雙層規(guī)劃的意義在于:14

上層決策部門:決策變量:下層決策部門:決策變量:相互作用上層給下層一定的信息,下層在這些信息下,按自己的利益或偏好做出反應(決策),上層再根據這些反應,做出符合全局利益的決策。雙層規(guī)劃決策過程上層決策部門:下層決策部門:相互作用上層給下層一定的15

如果每個決策者都按規(guī)定的指標函數在其可能范圍內做出決策,那么,雙層決策系統(tǒng)可能描述為雙層規(guī)劃問題。如果每個決策者的指標函數由單個函數組成,這樣的雙層規(guī)劃為雙層單目標規(guī)劃問題。如果有的決策者的指標函數是一組函數,這樣的雙層規(guī)劃問題為雙層多目標規(guī)劃問題。如果每個決策者都按規(guī)定的指標函數在其可能范圍16

8.2雙層規(guī)劃特點雙層規(guī)劃問題一般具有如下幾大特點:層次性——系統(tǒng)分層管理,下層服從上層,但下層有相對的自主權。獨立性——各層決策者各自控制一部分決策變量,以優(yōu)化各自的目標。沖突性——各層決策者有各自不同的目標,且這些目標往往是相互矛盾的

。8.2雙層規(guī)劃特點雙層規(guī)劃問題一般具有如下幾大特點:17

10.2雙層規(guī)劃特點優(yōu)先性——上層決策者優(yōu)先做出決策,下層決策者在優(yōu)化自己的目標而選擇策略時,不能改變上層的決策。自主性——上層的決策可能影響下層的行為,因而部分地影響下層目標的實現(xiàn),但上層不能完全控制下層的選擇行為,在上層決策允許范圍內,下層有自主決策權。10.2雙層規(guī)劃特點優(yōu)先性——上層決策者優(yōu)先做出決策18

10.2雙層規(guī)劃特點(續(xù))制約性——下層的決策不但決定著自身目標的實現(xiàn),而且也影響上層目標的實現(xiàn),因此上層在選擇策略優(yōu)化自己的目標時,必須考慮到下層可能采取的策略對自己的不利影響。依賴性——各層決策者的容許策略集通常是不可分離的,形成一個相關聯(lián)的整體。10.2雙層規(guī)劃特點(續(xù))19

10.3雙層規(guī)劃模型的基本形式其中由下述規(guī)劃求得(U)(L)上層決策者通過設置的值影響下層決策者。下層決策變量是上層決策變量的函數,即,這個函數一般被稱為反應函數。

一般來說,雙層規(guī)劃模型具有如下形式

10.3雙層規(guī)劃模型的基本形式其中20

10.3雙層規(guī)劃模型的基本形式與一般的數學規(guī)劃不同,即使當、、和都是連續(xù)函數,并且上下層的約束集合有界閉的,()也可能沒有最優(yōu)解。假設上層選擇了點,那么下層面臨的是以為參數的簡單最小值最優(yōu)化問題。在有些情況下,對固定的,下層對應的最優(yōu)問題可能包含不止一個最優(yōu)解。什么情況下會有這種問題??10.3雙層規(guī)劃模型的基本形式與一般的數學規(guī)劃不同,21

如:如果所有的函數都是線性的,很可能當=固定的下層問題的所有最優(yōu)解組成一個集合,這意味著中的任何一點對下層是無差別的,但對上層的目標函數可能會有差別。上層最優(yōu)解可能只在中某個特定點上達到,但是沒有辦法使下層更愿意選擇該點。

如:如果所有的函數都是線性的,很可能當=22

雙層規(guī)劃分類

線性雙層規(guī)劃:所有目標函數和約束全為線性函數非線性雙層規(guī)劃:上下層目標函數和約束中少有一個非線性函數相應的有整數線性雙層規(guī)劃、整數非線性雙層規(guī)劃等雙層規(guī)劃分類線性雙層規(guī)劃:所有目標函數和約束全23

關于雙層規(guī)劃的一些定義記(BP)的約束域為定義2.1

對每個固定的,稱為下層問題的可行解集合,為下層問題的合理反應集。在上層決策空間上的投影為關于雙層規(guī)劃的一些定義記(BP)的約束域為定義2.124

關于雙層規(guī)劃的一些定義定義2.3如果存在,對任意的滿足稱是(BP)的全局最優(yōu)解或最優(yōu)解。定義2.2

稱為(BP)的可行解集合或誘導域。關于雙層規(guī)劃的一些定義定義2.3如果存在25

雙層規(guī)劃的一階必要條件設是雙層規(guī)劃的最優(yōu)解,則其一階必要條件為:(1),,,都是一階連續(xù)可微函數;(2)對,下層問題有唯一解;(3)存在,使得是下列問題的可行解:

雙層規(guī)劃的一階必要條件設是雙層26

例2.1

,其中解

例2.127

8.3雙層規(guī)劃的基本形式

該例的最優(yōu)解在點D上達到,即=(16,11),在點E(10,14)處,上層目標函數值更優(yōu)。點A(0,5)是問題的一個局部最優(yōu)解。

8.3雙層規(guī)劃的基本形式該例的最優(yōu)解在點D上達到,28

求解雙層規(guī)劃問題是非常困難的。原因:雙層規(guī)劃問題是一個NP-hard問題。雙層規(guī)劃的非凸性。10.4雙層規(guī)劃計算復雜性即使能找出雙層問題的解,通常也只可能是局部最優(yōu)解而非全局最優(yōu)解。求解雙層規(guī)劃問題是非常困難的。原因29

由于雙層規(guī)劃問題和博弈論具有一些類似的特性,因此可以利用博弈論中的一些方法來限定雙層規(guī)劃問題解的范圍。在博弈論中,同兩個選手分別控制各自的決策變量相比,如果一個選手能控制所有的決策變量,那么,這個選手就能更好的優(yōu)化其自身的目標。10.4雙層規(guī)劃計算復雜性由于雙層規(guī)劃問題和博弈論具有一些類似的特性,30

10.4雙層規(guī)劃計算復雜性其中由下述規(guī)劃求得(U)(L)第一種情況:如果下列雙層規(guī)劃的最優(yōu)解為10.4雙層規(guī)劃計算復雜性其中31

10.4雙層規(guī)劃計算復雜性第二種情況:如果上層決策者控制所有變量,雙層規(guī)劃變?yōu)樵O其最優(yōu)解為10.4雙層規(guī)劃計算復雜性第二種情況:設其最優(yōu)解為32

10.4雙層規(guī)劃計算復雜性其中第三種情況:如果上下層決策者分別獨立控制各自的決策變量,雙層規(guī)劃變?yōu)樵O其最優(yōu)解為10.4雙層規(guī)劃計算復雜性其中第三種情況:設其最優(yōu)解33

10.4雙層規(guī)劃計算復雜性那么有下式存在:除雙層規(guī)劃外,后兩種情況都是求單層規(guī)劃,較容易,因此可不直接求雙層規(guī)劃,而直接求后兩類單層規(guī)劃,然后盡量減小與,與之間的差異。計劃經濟市場經濟10.4雙層規(guī)劃計算復雜性那么有下式存在:除雙層規(guī)劃34

其中解對上述問題,當時,由,得。當取時,下層問題的最優(yōu)目標函數值,但下層問題的最優(yōu)解不唯一,滿足

,顯然這對上層目標函數產生影響。當時,;當時,。

10.4雙層規(guī)劃計算復雜性其中解對上述問題,當35上述例子說明:當上層給定一個允許決策后,如果下層問題的最優(yōu)解不唯一,將導致整個求解的復雜性,甚至無法保證能求得問題的最優(yōu)解。

10.5雙層規(guī)劃求解算法

對于雙層規(guī)劃是上層先進行決策,為了說明這種順序的重要性,考慮下面的例子。上述例子說明:10.5雙層規(guī)劃求解算法 對于雙層規(guī)劃36其中求解

10.5雙層規(guī)劃求解算法

例2.3其中求解10.5雙層規(guī)劃求解37

10.5雙層規(guī)劃求解算法值值上層下層上層下層同時決策由表可以看出決策順序很重要,如果控制變量的選手先決策,它的最小費用要比后選擇策略或兩選手同時決策要優(yōu)。10.5雙層規(guī)劃求解算法值值上層下層上層下層同時決策38

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

到目前為止,對于雙層規(guī)劃的求解算法歸納起來,可以分為39

10.5雙層規(guī)劃求解算法(2)K-T法(Karush-Kuhn-TuckerMethod,簡稱K-T法)

:這種方法將雙層問題中的下層問題用它的Karush-Kuhn-Tucker條件代替,主要用于求解雙層線性規(guī)劃問題,最初用于求解雙層線性資源控制問題。10.5雙層規(guī)劃求解算法(2)K-T法(Karush40

(3)下降法(DescentMethod):這種方法是基于用各種可能的方法得到的下層問題對上層決策變量的梯度信息,主要用于求解非線性連續(xù)變量的雙層規(guī)劃問題。從本質上講,這是一種迭代求解方法,利用得到的下層問題對上層決策變量的梯度信息來產生一系列使上層目標函數減小的點。最具代表性的下降算法是基于靈敏度分析的求解算法。10.5雙層規(guī)劃求解算法(3)下降法(DescentMethod):這種41

(4)直接搜索法(DirectSearchMethod)

:直接使目標函數最小的方法,如Abdulaal和LeBlanc(1979)使用的Hooke-Jeeves搜索法就屬于此類,在搜索解的過程中,這種方法取決于上層目標函數值的變化。10.5雙層規(guī)劃求解算法10.5雙層規(guī)劃求解算法42

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

10.5雙層規(guī)劃求解算法(5)非數值優(yōu)化方法:這類方法主要包括模擬退火、遺傳43

10.6雙層規(guī)劃的應用(1)交通已有大量文獻將雙層規(guī)劃應用于交通領域?!?/p>

網絡設計問題(NetworkDesignProblem)。相互作用網絡規(guī)劃者決定投資費用目的使網絡中系統(tǒng)費用最小用戶選擇出行路徑目的使自己的出行費用最小相互作用投資費用運行費用取決于交通流量10.6雙層規(guī)劃的應用(1)交通相互作用網絡規(guī)劃者決44

10.6雙層規(guī)劃的應用(1)交通☆

O-D(Origin-Destination)需求估計問題。☆

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

10.6雙層規(guī)劃的應用(1)交通45

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

10.6雙層規(guī)劃應用(續(xù))(2)管理☆資源分配。資源分配是一類比較復雜的管理問題,上層部門將資源分配給多個下層部門,下層部門根據分配的資源和自己已有的資源組織生產,使自己的效益最大。一些公共設施建設,如電站、水庫、污物處理站建設等,實質上也是資源分配問題,只不過下層不是部門的效益最大,而是公共設施產生的社會效益最大?!顑r格問題。例如應用到鐵路旅客票價制定問題。

10.6雙層規(guī)劃應用(續(xù))(2)管理47

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

10.6雙層規(guī)劃應用(續(xù))☆生產計劃。☆其它方面如兵力部署、設施定位、政策規(guī)劃等。(3)工程設計問題。10.6雙層規(guī)劃應用(續(xù))49

城市交通網絡設計問題城市交通網絡設計問題50

10.7.1城市交通平衡網絡設計問題

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

10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

資金不足是最大障礙網絡設計時需要決策10.7.1城市交通平衡網絡設計問題10.7雙層51

10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

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

對現(xiàn)有交通網絡進行改進城市交通網絡設計問題研究內容資金投入最少增加新的路段或更新改善已有路段的能力調整路口的交通信號建設立交橋等使整個交通網絡某種系統(tǒng)性能最優(yōu)10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用52

10.7.2用雙層規(guī)劃描述城市交通網絡設計問題

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

10.7.2用雙層規(guī)劃描述城市交通網絡設計問題1053

在進行網絡設計時,如果不考慮網絡用戶的路徑選擇行為,而一味的增加或改建已有路段,有時不僅不能達到改善整個系統(tǒng)交通狀況的目的,反而會使整個系統(tǒng)的交通狀況更加惡化,表現(xiàn)為系統(tǒng)總費用不僅沒有減少,反而會增加。(舉例)因此在進行交通網絡設計時,必須考慮網絡中用戶的路徑選擇行為,即進行規(guī)劃時要考慮路網改建后是否能達到預先所期望的目標。10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

在進行網絡設計時,如果不考慮網絡用戶的路徑選擇行為,54

10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

考慮一個網絡如圖所示,有四條路段,四個節(jié)點,一個O-D對(從節(jié)點O到節(jié)點D,總需求量為6)。路段1~4的阻抗函數(單位為:分鐘)分別為:

OD1234網絡中只有兩條路徑,第一條通過節(jié)點1、3(用1→3表示),第二條通過節(jié)點2、4(用2→4表示)。由于網絡的對稱性,O-D需求量平均分配到兩條路徑1→3和2→4上。每條路徑上流量為3。10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用55

10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

OD123410.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用56

10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

現(xiàn)增加一條路段5,其路段阻抗函數為:此時,網絡中又出現(xiàn)了第三條路徑,通過節(jié)點1、5、4(用1→5→4表示)OD12345這個新網絡的UE解是可見增加網絡固定設施通行能力后,并未如預料的那樣減少擁擠程度,反而增加了。10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用57

其中由下述規(guī)劃求得:

10.7雙層規(guī)劃在城市交通網絡平衡設計問題中的應用

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

交通規(guī)劃者為了達到使社會效益最大而采取的最優(yōu)決策反映了網絡中用戶的路徑選擇行為上層規(guī)劃下層規(guī)劃其中由下述規(guī)劃求得:10.7雙層規(guī)58

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

國外鐵路運價決定原理主要:運輸價值原則:所研究的運輸服務對需求者的使用價值或效用。需求價格表示的是旅客票價的最高限度,如果旅客票價高于這個價格,旅客就會放棄選擇鐵路作為出行方式,而選擇其他的交通方式(公路或民航)。鐵路旅客票價制定的雙層規(guī)劃模型國外鐵路運價決定原理59

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

表示的是旅客票價的最低限度,如果旅客票價低于這個價格,鐵路客運部門就難以在客運市場中生存和發(fā)展。運輸成本原則:運價應當等于運輸服務的生產費用。供給價格鐵路旅客票價制定的雙層規(guī)劃模型表示的是旅客票價的最60

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

在市場經濟條件下,鐵路旅客票價的制定應該兼顧成本和市場需求兩方面的因素。鐵路旅客票價制定的雙層規(guī)劃模型在市場經濟條件下,鐵61

上層決策部門:鐵路管理部門決策變量:鐵路客票價格下層決策:旅客的出行行為決策變量:交通流量相互作用

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

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

上層決策部門:鐵路管理部門下層決策:旅客的出行行為相62

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

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

其它因素不變鐵路票價上升鐵路客流量減少,轉移到其它運輸方式鐵路票價下降鐵路客流量增加,吸引其它運輸方式的客流出行者希望自己總的出行費用最低;10.8鐵路旅客票63

10.8.1多種交通運輸方式競爭條件下鐵路客票價格制定的雙層規(guī)劃模型

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

城市之間的客流分配,一般不存在路徑的選擇,而只有運輸方式的選擇10.8.1多種交通運輸方式競爭條件下鐵路客票價格64

10.8鐵路旅客票價制定的雙層規(guī)劃模型從定量角度出發(fā),既保障了出行者使自己的出行費用最小,又能使鐵路客運在市場競爭中取得最大的經濟效益。

上層規(guī)劃:

描述為鐵路客運管理部門在政府規(guī)定的范圍內制定最佳的客票價格以使鐵路客運的經濟效益為最大。下層規(guī)劃:描述城市間多模式運輸競爭條件下,客流在不同運輸方式之間的分配模式,目標是使每個出行者在出行過程中的出行費用最低。10.8鐵路旅客票價制定的雙層規(guī)劃模型從定量角度65

一般情況下,旅客總是力圖選擇從起點到終點之間總的廣義出行費用最低的客運運輸方式,10.8鐵路旅客票價制定的雙層規(guī)劃模型

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

最終,在不同的客運運輸方式之間會達到一種客流分配的穩(wěn)定的均衡狀態(tài)。這種均衡狀態(tài)可以描述為:在城市之間的所有可供選擇的客運運輸方式中,旅客所利用的各種客運運輸方式的廣義出行費用全部相等,并且不大于未被利用的客運運輸方式的出行費用。

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

最終,在不同的客運運輸方式之間會達到一種客流分配的穩(wěn)67

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

可以用下面的數學形式來描述這種均衡狀態(tài)如果如果

其中表示城市間第()種運輸方式的廣義出行費用,表示均衡狀態(tài)下城市間的廣義出行費用,表示城市間第()種運輸方式的客流量,為城市間所有運輸方式的集合。10.8鐵路旅客票價制定的雙層規(guī)劃模型可以用下面68

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

其中函數是運輸方式的廣義費用函數,在這個函數中不同運輸方式的客流量是自變量,即()。取不同的形式,便可以得到不同的客流量在客運運輸方式之間的分離模式,最常用的廣義費用函數形式有冪函數形式和對數函數形式。第一個約束表示城市間總的客流需求是已知并且固定的,表示表示城市間總的客流需求;最后一個約束為變量的非負約束。

10.8鐵路旅客票價制定的雙層規(guī)劃模型第一個約束69

(U)

其中由下層模型得出(L)

表示城市間鐵路客運的客流量,表示城市間鐵路客運的旅客票價,表示鐵路客運中的平均客運成本。and分別表示城市間的鐵路客運的平均客運成本和旅客票價最高限。可以理解為適當的運輸成本與適當的利潤之和,可以理解為是的運輸成本與政府允許的利潤上限之和(或消費者能承受的最大擔負能力)。

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

(U)70

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

例:確定從北京到天津合理的鐵路旅客票價費用綜合考慮出行時間、票價、方便性、舒適性、安全性等多種因素。根據《京津唐客運市場調查報告》北京到天津的總客運量約25000。從北京到天津存在兩種運輸方式:鐵路和公路天津北京鐵路公路鐵路旅客票價制定的雙層規(guī)劃模型例:確定從北京到天津71

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

其中為出行時間因素,表示票價因素,為方便、舒適和安全等綜合因素;()為待定參數。表示不同運輸方式的效用,為待定參數。

鐵路旅客票價制定的雙層規(guī)劃模型其中為出行72

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

鐵路客運量(人次)初始值(元)最優(yōu)旅客票價(元)511951.8826.661011950.7126.66354011949.3726.6611948.6726.66鐵路旅客票價制定的雙層規(guī)劃模型鐵路客運量(人次)初73

我們可以把物流中心的選址問題看作一個領導者和跟隨著(Leader-Follower)問題,其中決策部門是指導者(Leader),客戶對物流中心的選擇行為或者客戶需求在各物流中心的分配為跟隨者(Follower)。決策部門可以通過政策和管理來改變某個物流中心的位置和配送成本,從而影響客戶對物流中心的選擇,但不能控制他們的選擇??蛻魟t對現(xiàn)有的物流中心進行比較,根據自己的需求特點和行為習慣來選擇物流中心。這種關系我們可以用雙層規(guī)劃模型來描述。10.9物流中心選址問題我們可以把物流中心的選址問題看作一個領導者和74

10.9物流中心選址問題上層決策部門:物流規(guī)劃部門決策變量:物流中心的備選地點下層決策部門:用戶決策變量:用戶需求在各物流中心的分配量相互作用上層規(guī)劃可以描述為決策部門在允許的固定投資范圍內確定最佳的物流中心的地點以使得總成本最小(包括固定成本和變動成本)。下層規(guī)劃則描述了在多個物流中心存在的條件下,客戶需求量在不同物流中心之間的分配模式,它的目標是使每個客戶的費用最低。

10.9物流中心選址問題上層決策部門:物流規(guī)劃部75

10.9物流中心選址問題其中為第個客戶由地點的物流中心提供服務的廣義單位費用,這里假定它僅是需求量的函數,一般隨著分配需求量的增大,廣義費用也增加;為第個客戶在地點的物流中心得到滿足的需求量;為在地建物流中心的固定投資;

表示在地建物流中心時,此值為1,否則為0。

上層規(guī)劃為:10.9物流中心選址問題其中為第76

10.9物流中心選址問題下層規(guī)劃為:其中為客戶點的總需求量,為一任意大的正數。下層規(guī)劃表示客戶對物流中心的選擇行為,即各個用戶在各物流中心間分配需求量,以使其總費用最小。從宏觀上講,下層規(guī)劃主要是得到客戶需求量的分布情況。第一個約束保證每個用戶的需求都能得到滿足;第二個約束保證需求量總是在已建的物流中心處分配;最后一個約束為變量的非負約束。10.9物流中心選址問題下層規(guī)劃為:其中77

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

求解雙層規(guī)劃的模擬退火算法模擬退火算法是模仿熱力學中固體退火的隨機機制設計的。78

所謂的熱平衡狀態(tài)就是指其中任何原子具有能量的概率服從Boltzman(波茨曼)分布:

Metropolis于1953年模仿上述熱力學的退火方法發(fā)明了一個計算多下

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論