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

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

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