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