求解指派問題的伏格爾方法

《求解指派問題的伏格爾方法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、求解指派問題的伏格爾方法葉微：，申卯興2，高歆2，程智峰2（1西安交通大學(xué)理學(xué)院，陝西西安710049;2空軍工程大學(xué)導(dǎo)彈學(xué)院，陜西三原713800）摘要:通過對指派問題和運(yùn)輸問題的數(shù)學(xué)模型及其求解方法的分析比較，指出了作為運(yùn)輸問題特類的指派問題的特征及通常求解方法的弱點(diǎn)，在此基礎(chǔ)上給出了求解指派問題的伏格爾（Vogel）方法的思想和步驟，并利用文獻(xiàn)的數(shù)據(jù)給出具體的例證.關(guān)鍵詞:指派問題；運(yùn)輸問題；數(shù)學(xué)模型；求解法；伏格爾方法中圖分類號:0221.1文獻(xiàn)標(biāo)識碼：A在運(yùn)籌學(xué)屮，指派問題通常是作為一類特殊的0-1規(guī)

2、劃問題來認(rèn)識的，它有簡明的獨(dú)特解法（如匈牙利法等）.然而，在實際應(yīng)用中不難發(fā)現(xiàn)，對于指派問題不僅在理論上可以用求解運(yùn)輸問題的方法求解，而且解法清晰明了，特別是利用求解運(yùn)輸問題的伏格爾（Vogel）方法來、々紹垠派問挪么屁5屮雨欠的件占1運(yùn)輸問題和指派問題的比較指派問題是指在有a；項任務(wù)要個人員完成，而第/個人員做第y項工作的花費(fèi)時間（效率）為c.aj=1，2,…，w的情況下，如何進(jìn)行人員和任務(wù)的指派方可以使所花費(fèi)的總時閭最短（或效率最高），?運(yùn)輸問題是在已知產(chǎn)量分別為的w個產(chǎn)地和銷量分別為么的個銷地而從第個產(chǎn)地

3、到第y個銷地的單位運(yùn)價為什（/=1,2，…，爪;j=,n）的情況下，如伺逬行調(diào)運(yùn)以獲得總運(yùn)費(fèi)最省的運(yùn)輸方案（決策變量是指從第/個產(chǎn)地調(diào)運(yùn)到第y個銷地的調(diào)運(yùn)量）.這兩個問題是運(yùn)籌學(xué)中既古典又基本且具有廣泛應(yīng)用的問題，對此問題及其拓展匝題的求解方法的研究仍然是運(yùn)籌學(xué)界的一個熱點(diǎn).為了對指派問題和運(yùn)輸問題有一個清晰的nnminz=^cuxu>s.t.D=[xuIVXij=1,VXij=1,=1或0，/，y=1，2，???，4?收稿日期：2002210210基金項目：國家高等學(xué)校骨干教師資助計劃（GC21105290

4、03921004）;空軍工程大學(xué)導(dǎo)彈學(xué)院拔尖人才基金資助項目運(yùn)輸問題的數(shù)學(xué)模型為s.t.若記minz=巧，Tx=fXll,X12，…,Xln,X21,???,X2",???,Xmn)?b=(9a2f,atn,b],A=(Pii，P】2，…，Pl",其中p'y=ef+em+i=(0,???，0，l,0,…則運(yùn)輸問題的數(shù)學(xué)模型就變?yōu)檗k2,…，W「，?21，…，P2w，…，Pmm)9,0,1,0,…，0)T,q為單位矩陣…⑽幻n的第/列.minz=cTx,JAx=b，s.t.),2,…?，?且由Lx>0.模型明確表明

5、指派問題是運(yùn)輸問題的特例，即〃7=?，《,=/?/=1,/,7。.這就是說，指派問題是產(chǎn)銷量都是〃的產(chǎn)銷平衡的運(yùn)輸問題，?決策變量全部是0-1變量=0，U,G:,■表示第/個人員做第J個工作的花費(fèi)時間(或效率廠~=1表示指派第/個人員做第y個工作，~=0表示不指派第/個人員做第j個工作.若采用前述向量矩陣記號，并令〃/=〃，則指派問題的數(shù)學(xué)模型就可簡記力minz=c1x,fAx=1,s.t.)(2)其中xE{0，l}表示向量X的分量都是0或1，在(1)和(2)中A都是以0或1為元素的0-1矩陣.Lxe/0,1廠

6、1.2指派問題解的特性在指派問題中，由其背景要求知道它的解中所含元素1的個數(shù)必須是。.又甶于這里/,、的取值都是從I到。，由運(yùn)輸問題基本解的特性知道，對于這樣的問題，它的解中所含非空格的個數(shù)應(yīng)該是2/7-1，這中間所差的1個非空格的值都應(yīng)以0來補(bǔ)充.這就說明，指派問題的解是運(yùn)輸問題的退化解，當(dāng)然也可以認(rèn)為指派問題是一類退化的運(yùn)輸問題.1.3求解方法的比較這里以求解指派問題的匈牙利方法和求解運(yùn)輸問題的伏格爾方法來逬行比較.指派問題的匈牙利解法雖然步驟較少，但記憶起來容易混淆.特別是在作最少的直線覆蓋所有的0元素時

7、，主觀性比較大，難以掌握規(guī)律.運(yùn)輸問題的伏格爾方法雖然計算量大，但很容易計算，而且上多少，給乙減去多少的說法，即要么是甲，要么是乙，二者不可并存（產(chǎn)量和銷量均為1廠閃此，在采用閉回路調(diào)整法調(diào)優(yōu)時，應(yīng)把握是以較小花費(fèi)的元素代替較大花費(fèi)的元素，以閉回路中的調(diào)入空格代替閉回路中花費(fèi)最大的元素，并始終以其運(yùn)量1作為調(diào)入調(diào)出量，這樣就達(dá)至I、優(yōu)化的目的.在運(yùn)價表上得到/7個1,便得到了使得總花費(fèi)為最小的指派方案.1.5求解指派間題的伏格爾方法根據(jù)上述分析，我們可以給出求解指派問題的思想方法.?按照求解運(yùn)輸問題伏格爾方法的

8、基本步驟逬行，每步填寫運(yùn)量1,同時劃去行列，得出初始方案.在對初始方案的調(diào)整過程中應(yīng)■^t^mTzTtr1/I士音iHl師嶺屮士甴：吒1刊目帀的伴議亡;土的牛fl昭hnT.（1）在指派H題的效率矩陣上分別計算出各行和各列的最低效率和次最低效率的差額.?行差額W,?和列差額vy,并添加表的最右列（行差額）和最下列（列差額），蘇中Ui=min/djiinf