鋼管定購和運(yùn)輸問題的二次規(guī)劃模型

鋼管定購和運(yùn)輸問題的二次規(guī)劃模型

1主管道鋼管的運(yùn)輸及鋪設(shè)問題如圖1所示，鋪設(shè)了一條a1a2以產(chǎn)生天然氣的管道。附近有七家鋼廠，它們相距遙遠(yuǎn)。s3。這些管道可以生產(chǎn)這種管道。在圖中，粗線代表鐵路，細(xì)線代表道路，兩條水道表示放置于需要配置的管道（假設(shè)沿管道或現(xiàn)有道路，或設(shè)計(jì)道路），圓圈表示車站，每條鐵路、公路和管道旁邊的阿拉伯表示距離（單位公里）。為方便計(jì),1km主管道鋼管稱為1單位鋼管.1個(gè)鋼廠如果承擔(dān)制造這種鋼管,至少需要生產(chǎn)500個(gè)單位.鋼廠Si在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為si個(gè)單位,鋼管出廠銷價(jià)1單位鋼管為Pi萬元,如表1.單位鋼管的鐵路運(yùn)價(jià)如表2.1000km以上每增加1至100km運(yùn)價(jià)增加5萬元.公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元(不足整km部分按整km計(jì)算).鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)(不只是運(yùn)到A1,A2,…,A15,而是管道全線).問題1請(qǐng)制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃,使總費(fèi)用最小(給出總費(fèi)用).問題2如果要鋪設(shè)的管道不是一條線,而一個(gè)樹形圖,鐵路、公路和管道構(gòu)成網(wǎng)絡(luò),請(qǐng)就這種更一般的情形給出一種解決辦法,并對(duì)圖2按問題1的要求給出模型和結(jié)果.2最省路徑的確定。根據(jù)下的條件和費(fèi)用區(qū)域的限制,有各鋪設(shè)兩端為了求出定購計(jì)劃,首先應(yīng)該知道從各鋼廠到各鋪設(shè)路段運(yùn)送單位鋼管所需費(fèi)用最小的路徑.為此,我們定義:定義1使得從鋼廠Si運(yùn)送單位鋼管到鋪設(shè)端點(diǎn)Aj的費(fèi)用最小的路徑稱為從Si到Aj的最省路徑.如果可以預(yù)先知道運(yùn)往各鋪設(shè)端點(diǎn)的鋼管量,那么原問題就是一個(gè)純粹的運(yùn)輸問題,而運(yùn)輸問題已經(jīng)有著比較成熟的解法.然而我們遇到的并非如此簡單.各鋪設(shè)端點(diǎn)只有一個(gè)相當(dāng)大的取值范圍(而不是一個(gè)確定的值),確定這些值只能由運(yùn)輸和鋪設(shè)的限制條件以及費(fèi)用極小來決定.由于需鋪設(shè)的總長度是相當(dāng)長的,而一根鋼管的長度相對(duì)來說就小得多,所以可以認(rèn)為:從鋪設(shè)端點(diǎn)運(yùn)送鋼管到鋪設(shè)地點(diǎn)時(shí),鋼管是連續(xù)不斷、均勻地卸下的.基于以上原因,我們決定,首先求出各鋼廠到各鋪設(shè)端點(diǎn)的最省路徑,然后根據(jù)限制條件和費(fèi)用極小建立連續(xù)型規(guī)劃模型,最后求出整個(gè)購運(yùn)計(jì)劃.3路與段公路假設(shè)1施工公路與普通公路路況一樣;假設(shè)2在實(shí)際運(yùn)輸時(shí),經(jīng)過的路徑不會(huì)出現(xiàn)這樣的情況:公路夾于兩段鐵路之間,或鐵路夾于兩段公路之間;假設(shè)3在實(shí)際運(yùn)輸時(shí),總是這樣來運(yùn)輸?shù)?先運(yùn)往鋪設(shè)端點(diǎn)(指A1,A2,…)再運(yùn)到鋪設(shè)地點(diǎn);假設(shè)4鋪設(shè)是均勻、連續(xù)的,卸貨也是均勻、連續(xù)的.在后面的論述中,我們總是假設(shè)所有的鋼管量以km為單位,所有的費(fèi)用以萬元為單位.4模型的構(gòu)建首先,我們針對(duì)圖1建立數(shù)學(xué)模型.4.1鐵路和公路監(jiān)控容易知道,要使總費(fèi)用最小,所走的路徑就應(yīng)該是最省路徑.所以我們首先求出各條最省路徑.對(duì)于在一般賦權(quán)圖中求最短路徑問題已有許多成熟的方法,可以運(yùn)用到這里.但由于鐵路費(fèi)用比較特殊(單位路長費(fèi)用不是定值),所以必須做些特殊處理.經(jīng)過觀察我們發(fā)現(xiàn),圖1中所有鐵路及火車站構(gòu)成一顆樹,要把鋼管從任一鋼廠運(yùn)至鋪設(shè)地點(diǎn)上都必須至少經(jīng)過一個(gè)交接點(diǎn)(Bi),再根據(jù)假設(shè)2,每一次運(yùn)輸只能經(jīng)過1個(gè)交接點(diǎn).這樣,在一次運(yùn)輸中,經(jīng)過的鐵路將是連接出發(fā)點(diǎn)(鋼廠)和交接點(diǎn)的那條通路.不妨把它們直接用鐵路連起來.這樣我們可以按照如下方法構(gòu)造新圖:(Ⅰ)在圖1中將所有的鋼廠與交接點(diǎn)全部用鐵路連接起來,鐵路長度與圖1中相應(yīng)的鐵路總長度一樣.如果某個(gè)點(diǎn)既是鋼廠又是交接點(diǎn),則把它們拆成2個(gè)點(diǎn),1個(gè)代表鋼廠,1個(gè)代表交接點(diǎn),它們之間的鐵路長度賦值為0.(Ⅱ)略去圖1中的鐵路及火車站(除交接點(diǎn)外).這樣就得到1個(gè)新圖,重新擺放各點(diǎn)的位置后的形狀如圖3.我們給圖3的所有邊都賦予邊權(quán),它們的值是運(yùn)送單位鋼管經(jīng)過該邊的費(fèi)用(而不是路的長度).在此必須說明的是,在假設(shè)2的前提下,圖1與圖3是等效的.等效的意思是指:在圖1中從任何1個(gè)鋼廠走到任何1個(gè)鋪設(shè)點(diǎn),不管所走的是哪一條路,在圖3中都有惟一的路徑與之相對(duì)應(yīng),并且費(fèi)用相等.這樣,圖3中的所有的邊權(quán)值都可以從圖1及鐵路、公路運(yùn)價(jià)求出.譬如,S1B1=160,B1A2=0.3,A1A2=10.4.由于篇幅關(guān)系,在此不再一一給出.圖3是一個(gè)典型的賦權(quán)圖,可用Dijkstra算法、逐次逼近法等算法求出從Si到Aj的最省路徑和相應(yīng)費(fèi)用,在此我們采用逐次逼近法.為節(jié)省篇幅,結(jié)果在此將不給出,讀者可自行計(jì)算,程序可參見文獻(xiàn).4.2鋼管向左運(yùn)輸鋼管時(shí)的費(fèi)用設(shè)從鋼廠Si運(yùn)往鋪設(shè)端點(diǎn)Aj的鋼管量為xij,那么,購買費(fèi)用為Ψ1=7∑i=115∑j=1Ρixij.Ψ1=∑i=17∑j=115Pixij.用wij表示從Si到Aj的最省路徑相應(yīng)的費(fèi)用,則運(yùn)輸過程中的費(fèi)用為Ψ2=7∑i=115∑j=1(wij)xij.Ψ2=∑i=17∑j=115(wij)xij.因?yàn)殇摴苓\(yùn)到鋪設(shè)端點(diǎn)Aj后,還要運(yùn)往鋪設(shè)地點(diǎn).在圖3中,鋪設(shè)端點(diǎn)的度最大為2,所以每個(gè)端點(diǎn)運(yùn)送的方向最多有2個(gè),可設(shè)Aj向左運(yùn)送的鋼管量為Lj,向右運(yùn)送的鋼管量為Rj,顯然有Rj+Lj=7∑i=1xij,j=1,2,?,15,R15=0,L1=0.(1)Rj+Lj=∑i=17xij,j=1,2,?,15,R15=0,L1=0.(1)再由假設(shè)4,卸貨是均勻的,當(dāng)從鋪設(shè)端點(diǎn)Aj向左運(yùn)輸鋼管走了tkm時(shí),剩余在車上的鋼管量為Lj-t,所以將鋼管運(yùn)至Aj后再向左運(yùn)輸需要的費(fèi)用(Ψ3)Lj=e?∫Lj0(Lj-t)dt=12?eL2j.(Ψ3)Lj=e?∫Lj0(Lj?t)dt=12?eL2j.其中e是運(yùn)輸1單位鋼管每公里的公路運(yùn)費(fèi)。同理,將鋼管運(yùn)至Aj后再向右運(yùn)輸需要的費(fèi)用(Ψ3)Rj=e?∫Rj0(Rj-t)dt=12?eR2j.(Ψ3)Rj=e?∫Rj0(Rj?t)dt=12?eR2j.因此這期間的總費(fèi)用為Ψ3=15∑j=1((Ψ3)Lj+(Ψ3)Rj)=15∑j=112?e(L2j+R2j).Ψ3=∑j=115((Ψ3)Lj+(Ψ3)Rj)=∑j=11512?e(L2j+R2j).購買費(fèi)用、從鋼廠運(yùn)往鋪設(shè)端點(diǎn)的費(fèi)用、從鋪設(shè)端點(diǎn)運(yùn)至鋪設(shè)地點(diǎn)的費(fèi)用構(gòu)成了全部費(fèi)用的總和.所以,總費(fèi)用為Ψ=Ψ1+Ψ2+Ψ3=7∑i=115∑j=1Ρixij+7∑i=115∑j=1wijxij+15∑j=112?e(L2j+R2j).(2)Ψ=Ψ1+Ψ2+Ψ3=∑i=17∑j=115Pixij+∑i=17∑j=115wijxij+∑j=11512?e(L2j+R2j).(2)4.3個(gè)等價(jià)形式的生產(chǎn)根據(jù)需鋪設(shè)的鋼管總長度為5171個(gè)單位,而且運(yùn)輸量總是非負(fù)的,所以7∑i=115∑j=1xij=5171.(3)∑i=17∑j=115xij=5171.(3)再根據(jù)假設(shè)4,鋪設(shè)是均勻的(不重疊不遺漏),所以有Rj+Lj+1=AjAj+1,j=1,2,…,14,(4)其中AjAj+1表示從Aj到Aj+1需要鋪設(shè)鋼管的長度.由于鋼廠Si的產(chǎn)量上限為si,所以15∑j=1xij≤si,i=1,2,?,7.(5)∑j=115xij≤si,i=1,2,?,7.(5)而每個(gè)鋼廠都有自己的產(chǎn)量下限.如果生產(chǎn),則必須不小于500,否則就不生產(chǎn),產(chǎn)量為0.即15∑j=1xij=0∑j=115xij=0,或15∑j=1xij≥500,i=1,2,?,7?(6)∑j=115xij≥500,i=1,2,?,7?(6)為了方便求解,我們將上式改寫成如下等價(jià)形式(在產(chǎn)量非負(fù)的條件下):15∑j=1xij(15∑j=1xij-500)≥0,i=1,2,?,7.(7)∑j=115xij(∑j=115xij?500)≥0,i=1,2,?,7.(7)4.4鋼管購運(yùn)計(jì)劃數(shù)學(xué)模型由(1)～(7)可以得到一個(gè)連續(xù)非線性規(guī)劃模型:minΨ=7∑i=115∑j=1Ρixij+7∑i=115∑j=1wijxij+15∑j=112?e(L2j+R2j).S.Τ.7∑i=115∑j=1xij=5171.15∑j=1xij≤si,i=1,2,?,7?Rj+Lj=7∑i=1xij,j=1,2,?,15,R15=0,L1=0.(9)Rj+Lj+1=AjAj+1,j=1,2,?,14?15∑j=1xij(15∑j=1xij-500)≥0?i=1,2,?,7?xij≥0,i=1,?,7,j=1,?,15.minΨ=∑i=17∑j=115Pixij+∑i=17∑j=115wijxij+∑j=11512?e(L2j+R2j).S.T.∑i=17∑j=115xij=5171.∑j=115xij≤si,i=1,2,?,7?Rj+Lj=∑i=17xij,j=1,2,?,15,R15=0,L1=0.(9)Rj+Lj+1=AjAj+1,j=1,2,?,14?∑j=115xij(∑j=115xij?500)≥0?i=1,2,?,7?xij≥0,i=1,?,7,j=1,?,15.這就是我們所要建立的鋼管購運(yùn)計(jì)劃數(shù)學(xué)模型.5鋼管運(yùn)輸費(fèi)的確定這是1個(gè)非線性規(guī)劃模型.由于模型中變量太多,人工求解很難進(jìn)行.我們使用數(shù)學(xué)軟件LINGO6.0,成功地求解這個(gè)模型,從而得到完整的購運(yùn)計(jì)劃.首先是去鋼廠購買鋼管的計(jì)劃,表3列出了具體的購買方案,所花費(fèi)用Ψ1=797725;然后是將鋼管運(yùn)至鋪設(shè)端點(diǎn),運(yùn)輸方案也在表3中給出,運(yùn)輸費(fèi)Ψ2=399731.55;最后是把鋼管從鋪設(shè)端點(diǎn)運(yùn)到鋪設(shè)地點(diǎn),表4給出了運(yùn)輸方法,運(yùn)輸費(fèi)Ψ3=15∑j=112e(R2j+L2j)=80916.45Ψ3=∑j=11512e(R2j+L2j)=80916.45.這樣總費(fèi)用就是Ψ=Ψ1+Ψ2+Ψ3=1278373.6關(guān)于相關(guān)系數(shù)的模型如果要鋪設(shè)的管道不是一條線,而是一個(gè)樹形圖,鐵路、公路和管道構(gòu)成網(wǎng)絡(luò),我們的方法同樣是適用的,因?yàn)樵谇笞钍÷窂綍r(shí),我們并不排除鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)的情形.實(shí)際上,圖2與圖1的差別主要是鋪設(shè)端點(diǎn)的度數(shù)不同.因此,只要對(duì)第一個(gè)模型稍作修改,就可以解決這種更一般的情形了.對(duì)圖2運(yùn)用相同的方法進(jìn)行改造,得到的新圖如圖4所示,其中的邊權(quán)可以根據(jù)圖2求出.在圖4中,鋪設(shè)路徑上的結(jié)點(diǎn)的最大度數(shù)為3,從結(jié)點(diǎn)運(yùn)往鋪設(shè)地點(diǎn)的方向數(shù)最多有3個(gè),分別用D1j,D2j,D3j表示從Aj運(yùn)往3個(gè)方向的運(yùn)量,各方向的取法如下(其中的方向都是指在圖4中的方向):(i)如果結(jié)點(diǎn)Aj的度為1,說明從該結(jié)點(diǎn)運(yùn)出的方向只有一個(gè),D1j就是這個(gè)方向上的運(yùn)量,并且令D2j=0,D3j=0.這樣的結(jié)點(diǎn)有A1,A15,A16,A18,A21;(ii)如果結(jié)點(diǎn)Aj的度為2,說明從該結(jié)點(diǎn)運(yùn)出的方向有2個(gè),D1j表示向左方向的運(yùn)量,D2j表示向右方向的運(yùn)量,并且令D3j=0.這樣的結(jié)點(diǎn)有A2,A3,A4,A5,A6,A7,A8,A10,A12,A13,A14,A19,A20.(iii)如果結(jié)點(diǎn)Aj的度為3,則D1j表示向左方向的運(yùn)量,D2j表示向右方向的運(yùn)量,D3j表示向下的運(yùn)量.這樣的結(jié)點(diǎn)有A9,A11,A17.用類似于前面建立模型的方法對(duì)問題三建立模型如下:minΨ=7∑i=121∑j=1Ρixij+7∑i=115∑j=1wijxij+21∑j=112?e(D12j+D22j+D32j).S.Τ.7∑i=121∑j=1xij=5903?21∑j=1xij≤si,i=1,2,?,7?21∑j=1xij(21∑j=1xij-500)≥0?i=1,2,?,7?D1j+D2j+D3j=7∑i=1xij,j=1,2,?,21?D2j+D1j+1=AjAj+1,j=1,2,?,14?D39+D116=42,D311+D117=10?D217+D118=130,D317+D119=190?D219+D120=260,D220+D121=100?D11=D215=D216=D316=D218=0?D318=D319=D320=D221=D321=0?D3j=0,j=1,?,8,10,12,?,15.xij≥0,i=1,?,7,j=1,?,21.minΨ=∑i=17∑j=121Pixij+∑i=17∑j=115wijxij+∑j=12112?e(D12j+D22j+D32j).S.T.∑i=17∑j=121xij=5903?∑j=121xij≤si,i=1,2,?,7?∑j=121xij(∑j=121xij?500)≥0?i=1,2,?,7?D1j+D2j+D3j=∑i=17xij,j=1,2,?,21?D2j+D1j+1=AjAj+1,j=1,2,?,14?D39+D116=42,D311+D117=10?D217+D118=130,D317+D119=190?D219+D120=260,D220+D121=100?D11=D215=D216=D316=D218=0?D318=D319=D320=D221=D321=0?D3j=0,j=1,?,8,10,12,?,15.xij≥0,i=1,?,7,j=1,?,21.求解以上模型得到表5、表6的購買和運(yùn)輸計(jì)劃.由此可知Ψ1=910515,Ψ2=412089.55,Ψ3=21∑j=112e(D12j+D22j+