運輸問(wèn)題時(shí)間優(yōu)化算法

中國管理科學(xué)990405中國管理科學(xué)R資源系統CHINESE JOURNAL OF MANAGEMENT數字化期刊WANFANG DATA ( CHINAINFO)SCIENCEDIGITIZED PE RIODICAL1999年第7卷第4期vol.7 No.4 1999運輸問(wèn)題時(shí)間優(yōu)化算法楊建軍郭乃林韓曉明李仲強摘要:運輸問(wèn)題是線(xiàn)性規劃中的一類(lèi)特殊問(wèn)題,適用于求解目標函數符合線(xiàn)性疊加關(guān)系的費用或距離問(wèn)題,對于實(shí)際運輸問(wèn)題中的運輸時(shí)間優(yōu)化問(wèn)題則難以給出優(yōu)化解。本文結合科研實(shí)踐提出了運輸問(wèn)題中有關(guān)時(shí)間優(yōu)化的迭代算法模型,此模型可給出整體運輸時(shí)間最優(yōu)的運輸方案,通過(guò)實(shí)際檢驗證明,此算法簡(jiǎn)便、穩定、計算結果符合實(shí)際情況。關(guān)鍵詞:線(xiàn)性規劃;運輸問(wèn)題;時(shí)間優(yōu)化;算法模型.Time Optimization Algorithm for Transportation ProblemY angJianjunGuo N ailinH an Xiaoming(TheAir ForceMissile Insitute, Sanyuan713800)Li Zhongqiang(TheAir ForceOil Institute,Sanyuan713800)Abstract:T ransportation problem is a special problem in linear programming.This paper setsupan iteration algorithm for time optimization related to transportation problem,which can giveaglobal transportation time optimized project.A practical verification shows, this algorithm is simpleand stalble,the results accord with the fact.KeyW ords.linear programmingtransportation problem;time optimization;algorithm1線(xiàn)性 規劃中的運輸問(wèn)題運輸問(wèn)題是線(xiàn)性規劃中的-類(lèi)特殊問(wèn)題,在實(shí)踐中常用來(lái)解決運輸計劃制定、物資調運、運費優(yōu)化等實(shí)際問(wèn)題,在解決此類(lèi)問(wèn)題中，目標函數為符合線(xiàn)性疊加原理的費用,此時(shí)線(xiàn)性規劃中的運輸問(wèn)題模型可稱(chēng)之為費用優(yōu)化運輸問(wèn)題模型。費用優(yōu)化運輸問(wèn)題的數學(xué)模型為:minz=，(目標函數)中國煤化工MHCNM HGEx=b, j-=.2-,n(約束條件)fel//E/2/7平據ggg9904/990495.htm,(第1/ 8頁(yè)) 2010-3-23 14:57:17中國管理科學(xué)990405高x≤a, 1=.,..m(約束條件)Xj≥0(非負條件)式中: Z-費用優(yōu)化運輸問(wèn)題模型的目標函數;Xx;供應點(diǎn)到需求點(diǎn)j的供櫻崢;Ci;供應點(diǎn)i到需求點(diǎn)j的單位運費;b;需求點(diǎn)j的需求量;a供應點(diǎn)i的可供應量。.當各供應點(diǎn)的可供應量之和等于各需求點(diǎn)需求量之和，即鳴一點(diǎn)時(shí),為產(chǎn)銷(xiāo)平衡運輸問(wèn)題,可通過(guò)表上作業(yè)法進(jìn)行求解。對于產(chǎn)銷(xiāo)不平衡的運輸問(wèn)題可通過(guò)增加虛供點(diǎn)或虛收點(diǎn)將問(wèn)題轉化為產(chǎn)銷(xiāo)平衡的運輸問(wèn)題進(jìn)行求解。費用優(yōu)化運輸問(wèn)題模型的目標函數為運輸費用的線(xiàn)性疊加,因此費用優(yōu)化運輸問(wèn)題模型:是對于符合線(xiàn)性疊加原理的運輸費用的優(yōu)化。對于通常運輸費用作為決定因素的運輸問(wèn)題,費用優(yōu)化運輸問(wèn)題時(shí)間優(yōu)化算法第4期運輸問(wèn)題模型是-種行之有效的數學(xué)模型。2時(shí)間優(yōu)化運輸問(wèn)題的特點(diǎn)對戰時(shí)軍用物資運輸或在某些緊急條件下,運輸時(shí)間成為最主要的決定因素,即整體運輸時(shí)間最短成為優(yōu)化的第- -目標,這時(shí)運用費用優(yōu)化運輸問(wèn)題模型就難以給出滿(mǎn)意的結果。費用優(yōu)化運輸問(wèn)題模型的優(yōu)化目標為整體運輸費用最小,運輸費用具有線(xiàn)性疊加特性,或認為具有串聯(lián)特性,即整體運輸費用等于各分段費用的線(xiàn)性疊加;而運輸時(shí)間則.不具有線(xiàn)性疊加特性,因為各供應點(diǎn)的操作(裝卸和運輸)可同時(shí)或平行進(jìn)行,整體完成時(shí)間并不是各分段時(shí)間的線(xiàn)性疊加,而是由各分段時(shí)間中的最大值控制, 運輸時(shí)間的這一特點(diǎn)使運輸時(shí)間的優(yōu)化具有明顯的并聯(lián)特性。對于具有并聯(lián)特性的運輸時(shí)間的優(yōu)化，目前尚無(wú)十分成熟的算法。在對運輸問(wèn)題進(jìn)行時(shí)間優(yōu)化時(shí),在所有的供應點(diǎn)中必有一個(gè)或多個(gè)控制點(diǎn),即這些供應點(diǎn)的供應時(shí)間(包括裝卸時(shí)間和運輸時(shí)間兩項之和)在所有的供應點(diǎn)中最大,只有縮短控制點(diǎn)的供應時(shí)間才對運輸方案的整體供應時(shí)間的優(yōu)化具有直接意義，因為即使縮.短其它供應點(diǎn)的供應時(shí)間,整體供應時(shí)間并沒(méi)有得到改進(jìn)。在對運輸問(wèn)題進(jìn)行時(shí)間優(yōu)化時(shí),在保證運輸時(shí)間最優(yōu)的條件下，可同時(shí)考慮經(jīng)濟性因素,即把運輸經(jīng)濟性因素作為第二優(yōu)化目標。3時(shí)間優(yōu)化運輸問(wèn)題算法模型的建立和模型框圖在研究時(shí)間優(yōu)化運輸問(wèn)題特點(diǎn)的基礎上,建立了以費用優(yōu)中國煤化工基礎,控制點(diǎn)供應時(shí)間調整、供應點(diǎn)優(yōu)化選擇為輔助的時(shí)間優(yōu)化運輸MYHCN MH9NMH.型。此模型所給出的運輸方案是在滿(mǎn)足時(shí)間最優(yōu)條件下的最經(jīng)濟的運輸方案。fl/ Iv0萬(wàn)教據ggg9904/990495.htm,(第2/ 8頁(yè)) 2010-3-23 14:57:17中國管理科學(xué)990405在考慮供應點(diǎn)的供應時(shí)間時(shí), 考慮兩個(gè)時(shí)間因素,即裝卸時(shí)間和運輸時(shí)間。裝卸時(shí)間指供應點(diǎn)裝卸物資所需的時(shí)間,運輸時(shí)間指供應點(diǎn)到需求點(diǎn)的運輸時(shí)間,兩個(gè)時(shí)間因素之和即為供應點(diǎn)的供應時(shí)間。在實(shí)際問(wèn)題中, 某些供應點(diǎn)與某些需求點(diǎn)間可能不存在供應關(guān)系,在制定優(yōu)化運輸方案中應考慮到這一因素。在模型的初始數據中令這些供應點(diǎn)與需求點(diǎn)之間的距離為一個(gè)足夠大的數字,如99999千米,則程序在優(yōu)化運算時(shí)就自動(dòng)不選取這些供應點(diǎn)來(lái)供應那些不存在供應關(guān)系的需求點(diǎn)。在計算各供應點(diǎn)的保障時(shí)間時(shí),常遇到一個(gè)供應點(diǎn)供應多個(gè)需求點(diǎn)的情況,在這種.情況下依據發(fā)運先遠后近的原則計算此供應點(diǎn)的供應時(shí)間,即認為供應點(diǎn)可連續裝卸，在裝卸的過(guò)程中可同時(shí)發(fā)運,發(fā)運采用先給距離遠的需求點(diǎn)發(fā)運,后給距離近的需求點(diǎn)發(fā)運,此時(shí)的供應時(shí)間為總裝卸時(shí)間和與總裝卸時(shí)間不重合的運輸時(shí)間之和?？梢宰C明對于一個(gè)供應點(diǎn)供應多個(gè)需求點(diǎn)的情況,這種供應方式所需的供應時(shí)間最短。時(shí)間優(yōu)化運輸問(wèn)題數學(xué)模型對費用優(yōu)化運輸問(wèn)題數學(xué)模型的重要改進(jìn)是在費用優(yōu)化運輸問(wèn)題數學(xué)模型的基礎上增加了控制點(diǎn)供應時(shí)間調整模型和供應點(diǎn)選擇模型。在控制點(diǎn)供應時(shí)間調整模型中采用供應時(shí)間排序的方法確定各供應點(diǎn)供應時(shí)間的序列。在裝卸時(shí)間遠大于運輸時(shí)間的條件下,為減少運算量可采用平均時(shí)間替代供應時(shí)間,平均時(shí)間定義為供應點(diǎn)的供應量除以供應點(diǎn)的裝卸能力,可以證明在忽略運輸時(shí)間的條件下,總平均時(shí)間(所有供應點(diǎn)的供應量之和除以所有供應點(diǎn)的裝卸能力之和)是最理想時(shí)間,最大供應時(shí)間等于總平均時(shí)間的供應方案是時(shí)間最優(yōu)方案。在運輸時(shí)間不.能忽略或計算精度要求較高時(shí),不能采用平均時(shí)間替代供應時(shí)間。在確定了各供應點(diǎn)供應時(shí)間的序列后,則將供應時(shí)間最大的供應點(diǎn)的部分供應量調整到供應時(shí)間最小的供應.點(diǎn)去,調整的前提是這兩個(gè)供應點(diǎn)對某-或某些需求點(diǎn)同時(shí)具有供應關(guān)系，反復迭代進(jìn)行排序和調整, 直至調整過(guò)程不能再進(jìn)行為止。供應點(diǎn)選擇模型的主要部分仍為費用優(yōu)化運輸問(wèn)題模型,對供應點(diǎn)的選擇仍以就近供應為原則,在此基礎上,增加供應點(diǎn)供應量限制準則。若供應點(diǎn)在優(yōu)化供應量條件下不能滿(mǎn)足供應時(shí)間限制,則限制供應點(diǎn)的供應量,使其滿(mǎn)足供應時(shí)間要求。時(shí)間優(yōu)化運輸問(wèn)題模型的數學(xué)表達為:費用優(yōu)化運輸問(wèn)題數學(xué)模型(略)3.2 控制點(diǎn)供應時(shí)間調整模型(推導見(jiàn)附尋)xz=(XmaxX QminXminX Qmax+QmaxX Qmin(mx~Tmin)Nys)/(Qmax+Qmin)Xmax2=Xmax1-XtXmin2= EXmin1+Xu式中: xc最優(yōu)調整量;Xmax供應時(shí)間最大的供應點(diǎn)的總供應量;Xmin供應時(shí)間最小的供應點(diǎn)的總供應量;Xmax1供應時(shí)間最大的供應點(diǎn)調整前的總供應量;Xmx2供應時(shí)間最大的供應點(diǎn)調整后的總供應量;中國煤化工Xmin1供應時(shí)間最小的供應點(diǎn)調整前的總供應量;MHCNM HGXmn2供應時(shí)間最小的供應點(diǎn)調整后的總供應量;fel//E/2/7平據gggg9904/990405.htm,(第3/ 8頁(yè)) 20103-23 14:57:17中國管理科學(xué)990405Qmax供應時(shí)間最大的供應點(diǎn)的裝卸能力;Qmin供應時(shí)間最小的供應點(diǎn)的裝卸能力;Cmax供應時(shí)間最大的供應點(diǎn)到所供需求點(diǎn)的距離中的最小值;Cmin供應時(shí)間最小的供應點(diǎn)到所供需求點(diǎn)的距離中的最小值;V供應時(shí)間到所供需求點(diǎn)的平均運輸速度。供應點(diǎn)選擇模型供應點(diǎn)供應量限制準則Xx=(xCi;/ys)x Qi式中: Xixz供應點(diǎn)i的限制供應量;tx2需求點(diǎn)j的限制供應時(shí)間;q;供應點(diǎn)i到需求點(diǎn)j的距離;Q;供應點(diǎn)i的裝卸能力。依據以.上數學(xué)模型,編制計算程序,計算程序流程框圖見(jiàn)圖1。計算步驟如下:數據輸人和整理l 費用優(yōu)化運輸問(wèn)題模型] ￥↓求各供應點(diǎn)的總供應量|計算供應時(shí)間Y可調整否?> +供應時(shí)間調整N<供應時(shí) 間滿(mǎn)足要求否?> +| 供應點(diǎn)選擇輸出結果圖1計算程 序流程框圖( 1)數據輸入和整理模塊的功用為輸入原始數據;對輸)中國煤化干序以減少優(yōu)化送代次數;各需求點(diǎn)的需求量為實(shí)際需求量,各供應MHCNMH各供應點(diǎn)的可供量。( 2)以各需求點(diǎn)的實(shí)際需求量、各供應點(diǎn)的初始可供應量、各供應點(diǎn)與各需求點(diǎn)fle// 0亳螯掘zgg/gg999005.htm (第4/ 8頁(yè)) 2010-3-23 14:57:17中國管理科學(xué)990405間的距離矩陣(或費用矩陣)為依據進(jìn)行距離優(yōu)化(或費用優(yōu)化) ,產(chǎn)生初始供應點(diǎn)、初始供應點(diǎn)的初始供應量和分配方案,這- -過(guò)程實(shí)際上就是線(xiàn)性規劃運輸問(wèn)題求解;(3)在獲得供應量和分配方案后,依據各供應點(diǎn)的裝卸能力和運輸距離計算供應時(shí)間;( 4)進(jìn)行供應時(shí)間調整,產(chǎn)生初始供應點(diǎn)調整后的供應量、以各需求點(diǎn)的實(shí)際需求量、各供應點(diǎn)調整后的供應量、各供應點(diǎn)與各需求點(diǎn)間的距離矩陣(或費用矩陣)為依據重新進(jìn)行距離優(yōu)化(或費用優(yōu)化) , 產(chǎn)生初始供應點(diǎn)新一輪的供應量和分配方案;(5)循環(huán)進(jìn)行第(3)-(4)步,直至調整前后的結果趨于一致,即無(wú)法再進(jìn)行新一輪的調整, 如再進(jìn)行調整,分配結果將保持不變。(6)調整完成后,計算供應時(shí)間;( 7)若供應時(shí)間已滿(mǎn)足要求,則輸出結果;若供應時(shí)間不能滿(mǎn)足要求,則進(jìn)行供應點(diǎn)選擇;(8)供應點(diǎn)選擇,在限制不滿(mǎn)足供應時(shí)間要求的初始供應點(diǎn)的供應量的條件下,增加新的供應點(diǎn)。若在所有供應點(diǎn)已全部參加供應后,仍不能滿(mǎn)足供應時(shí)間要求,則按限定供應時(shí)間要求確定各供應點(diǎn)的供應量,并給出提示,此時(shí)的總供應量不能滿(mǎn)足總需求。4計算實(shí)例和結果分析在以.上模型的基礎上,編制了計算機程序。通過(guò)課題數據的實(shí)際檢驗, 證明計算模型合理、穩定、計算速度較快、計算結果符合實(shí)際情況要求。為進(jìn)一步說(shuō)明時(shí)間優(yōu)化運輸問(wèn)題模型在時(shí)間優(yōu)化方面的優(yōu)勢,本文結合實(shí)際情況給出一套模擬數據,分別采用費用優(yōu)化運輸問(wèn)題模型和時(shí)間優(yōu)化運輸問(wèn)題模型進(jìn)行了對比計算。計算實(shí)例:有甲、乙、丙、丁四個(gè)需求點(diǎn),A、B、C、D、E、F、G、H、J、K、L、M十一個(gè)供應點(diǎn);已知數據為,需求點(diǎn)的需求量和供應點(diǎn)的可供應量、需求點(diǎn)和供應點(diǎn)間的運輸距離、供應點(diǎn)的裝卸能力、運輸速度(取平均值, 每小時(shí)30千米)。計算實(shí)例的原始數據見(jiàn)表1。為便于對比,對于以上數據分別采用費用優(yōu)化運輸問(wèn)題模型和時(shí)間優(yōu)化運輸問(wèn)題模型形成兩個(gè)運輸方案,采用費用優(yōu)化運輸問(wèn)題模型所形成的分配方案見(jiàn)表2;采用時(shí)間優(yōu)化運輸問(wèn)題模型所形成的分配方案見(jiàn)表3。從表1和表2中可看出,費用優(yōu)化運輸問(wèn)題模型計算生成的分配方案按距離最近原則進(jìn)行分配,獲得的結果為運輸費用最小的分配方案。從表3所示的時(shí)間優(yōu)化運輸問(wèn)題模型分配方案可看出,采用時(shí)間優(yōu)化后, 最大供應時(shí)間從原費用優(yōu)化分配方案的263小時(shí)減少到118小時(shí),供應點(diǎn)供應順序仍保持就近供應的特點(diǎn),這一點(diǎn)可從表1和表3的對照中看出。對于單一供應點(diǎn)即可滿(mǎn)足供應時(shí)間要求的情況,時(shí)間優(yōu)化運輸問(wèn)題模型所給出的分配方案仍遵循費用優(yōu)化運輸問(wèn)題模型的分配結果,給出的供應方案仍為最經(jīng)濟的供應方案。由此可見(jiàn),時(shí)間優(yōu)化運輸問(wèn)題模型給出的分配方案是在滿(mǎn)足限定供應時(shí)間要求下的最經(jīng)濟的運輸方案。中國煤化工表1原始數據(距離陣單位:kmYHCNM HGfel//E/2/7平據ggg9904/990495.htm,(第5/ 8頁(yè)) 2010-3-23 14:57:17中國管理科學(xué)990405供應點(diǎn)裝卸能供應點(diǎn)可供量供應點(diǎn)/需求點(diǎn)|甲需求點(diǎn)|乙需求點(diǎn)丙需求點(diǎn)丁需求點(diǎn)(噸/小時(shí))力(噸)A供應點(diǎn)999999290045B供應點(diǎn)15005776000C供應點(diǎn)2017000D供應點(diǎn)40080090000E供應點(diǎn)2035901171120F供應點(diǎn)16062220000G供應點(diǎn)9999914869560000H供應點(diǎn)1319150000J供應點(diǎn)30000K供應點(diǎn)2308060000L供應點(diǎn)5005080000M供應點(diǎn)52需求點(diǎn)總需求75000需求量(噸)91916403156142892注:若表中距離為99999，則表明該供應點(diǎn)與該需求點(diǎn)之間無(wú)供應關(guān)系。表2費用優(yōu)化運輸問(wèn)題模型分配方案 (分配量(供應時(shí)間)單位:噸(小時(shí)) )供應點(diǎn)裝卸供應點(diǎn)可供供應點(diǎn)/需能力甲需求點(diǎn)乙需求點(diǎn)|丙需 求點(diǎn)丁需求點(diǎn).量求點(diǎn)(噸/小時(shí))09191 ( 177 )E供應點(diǎn).640 ( 14)1500( 20 )931561 ( 263 )C中國煤化工0YHCNMHGOfle//E Vv0萬(wàn)教據gggg9904/990405.htm,(第6/ 8頁(yè)) 20103-23 14:57:17中國管理科學(xué)990405需求點(diǎn)總需求需求量1500919164031561(噸)42892注:表中括號中的數字表示供應時(shí)間(單位:小時(shí))表3時(shí)間優(yōu)化運輸問(wèn)題模型分配方案 (分配量(供應時(shí)間)單位:噸(小時(shí)) )供應點(diǎn)裝卸供應點(diǎn)可供供應點(diǎn)/需能力甲需求點(diǎn)乙需求點(diǎn)|丙需求點(diǎn)丁需求點(diǎn)量求點(diǎn)(噸/小.時(shí))A供應點(diǎn)045B供應點(diǎn)57C供應點(diǎn)4325( 83 )524325D供應點(diǎn)3086( 118 )3086E供應點(diǎn)9546( 118 )1209546F供應點(diǎn)4866( 83 )624866G供應點(diǎn)640 ( 14)69H供應點(diǎn)1500( 20 )91J供應點(diǎn)14148 ( 118 )14148K供應點(diǎn)8L供應點(diǎn)60M供應點(diǎn)4781 ( 118)47819191.對于調整后供應時(shí)間仍不能滿(mǎn)足要求的情況,程序將給出提示,供決策者選擇,選擇退出系統修改供應時(shí)間要求或選擇按限定供應時(shí)間供應,生成限定供應時(shí)間要求下的分配方案,此時(shí)總需求量不能得到滿(mǎn)足,程序將給出提示并標明各需求點(diǎn)需求量被滿(mǎn)足的百分比。通過(guò)大量的實(shí)際計算可知,時(shí)間優(yōu)化運輸問(wèn)題模型的優(yōu)化結果符合實(shí)際情況,程序運行穩定、計算速度較快,模型對于解決運輸問(wèn)題的時(shí)間優(yōu)化行之有效。5結束語(yǔ).中國煤化工.MHCNMHG時(shí)間優(yōu)化運輸問(wèn)題模型解決了物資調運中時(shí)間因素位于第L位的九化叫越,通過(guò)實(shí)際課題運用考驗證明, 模型的建立是合理、簡(jiǎn)潔和實(shí)用的。fl/ Iv0萬(wàn)教據zg9/gg9904/99005.htm (第7/ 8頁(yè)) 2010-3- 23 14:57:17中國管理科學(xué)990405本文所介紹的時(shí)間優(yōu)化運輸問(wèn)題模型是我們所研制的計算機輔助決策系統中的一個(gè)關(guān)鍵模塊,為充分利用決策者的經(jīng)驗和智慧,時(shí)間優(yōu)化運輸問(wèn)題模型在程序設計上采用了人工干預技術(shù),對于實(shí)際應用中可能出現的多種情況,程序均會(huì )給出提示,提示情況出現的現象并給出處理建議,由決策者做出選擇,控制程序的跳轉, 程序則對不同情況做出相應的處理和調整。時(shí)間優(yōu)化運輸問(wèn)題模型是對費用優(yōu)化運輸問(wèn)題模型的改進(jìn),使用者可根據課題的實(shí)際要求,參考此模型的思路建立符合自身實(shí)際情況的模型。作者單位:楊建軍郭乃林 韓曉明 (空軍導彈學(xué)院,三原713800 )李仲強(空軍油料研究所,三原713800 )參考文獻[1]《運籌學(xué)》教材編寫(xiě)組.運籌學(xué)(修訂版).清華大學(xué)出版社, 1997.[2]胡運權.運籌學(xué)基礎及應用.哈爾濱工業(yè)大學(xué)出版社, 1993.[3]五院校合編運籌學(xué)-經(jīng)濟管理決策方法.四川大學(xué)出版社, 1989.[4]李書(shū)濤.決策支持系統原理與技術(shù).北京理工大學(xué)出版社, 1996.[5]馬紹民綜合保障I程.北京.國防工業(yè)出版社, 1995.附錄:控制點(diǎn)供應時(shí)間調整模型的推導設最優(yōu)調整量為xz,則在供應時(shí)間最大的供應點(diǎn)的供應時(shí)間等于供應時(shí)間最小的供應點(diǎn)的供應時(shí)間條件下,有Xmax Xrq/Qmax+ CmaxN ys=(Xmin+ x)/Qmin+ CminN ys此式經(jīng)過(guò)變換,解出最優(yōu)調整量xt的表達式。xz=(XmaxX Qmin-XminX 9max+QmaX Qmin( Cmax Cmin)N y)(Qmax+ Qmin)將供應時(shí)間最大的供應點(diǎn)的總供應量減去最優(yōu)調整量,供應時(shí)間最小的供應點(diǎn)的總供應量加上最優(yōu)調整量,即得到兩供應點(diǎn)新一輪的總供應量。Xmax2= EXmax1-XtXmin2=Xmin1+Xx收稿日期: 1999-04-05中國煤化工MHCNM HGfel//E/2/7平據ggg9904/990495.htm,(第8/ 8頁(yè)) 2010-3-23 14:57:17