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

《求解指派問題的伏格爾方法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、明的獨(dú)特解法(如匈牙利法等).然而,在實(shí)際應(yīng)用中不難發(fā)現(xiàn),對(duì)于指派問題不僅在理論上可以用求解運(yùn)輸問題的方法求解,而且解法清晰明了,特別是利用求解運(yùn)輸問題的伏格爾(Vogel)方法來求解指派問題,會(huì)顯示出更多的優(yōu)點(diǎn).運(yùn)輸問題和指派問題的比較指派問題是指在有n項(xiàng)任務(wù)要n個(gè)人員完成,而第i個(gè)人員做第j項(xiàng)工作的花費(fèi)時(shí)間(效率)為cij(i,j=1,2,?,n)的情況下,如何進(jìn)行人員和任務(wù)的指派方可以使所花費(fèi)的總時(shí)間最短(或效率最高);運(yùn)輸問題是在已知產(chǎn)量分別為ai的m個(gè)產(chǎn)地和銷量分別為bj的n個(gè)銷地,而從第i個(gè)產(chǎn)地到第j個(gè)銷地的單位運(yùn)價(jià)為c

3、ij(i=1,2,?,m;j=1,2,?,n)的情況下,如何進(jìn)行調(diào)運(yùn)以獲得總運(yùn)費(fèi)最省的運(yùn)輸方案(決策變量xij是指從第i個(gè)產(chǎn)地調(diào)運(yùn)到第j個(gè)銷地的調(diào)運(yùn)量).這兩個(gè)問題是運(yùn)籌學(xué)中既古典又基本且具有廣泛應(yīng)用的問題,對(duì)此問題及其拓展問題的求解方法的研究仍然是運(yùn)籌學(xué)界的一個(gè)熱點(diǎn).為了對(duì)指派問題和運(yùn)輸問題有一個(gè)清晰的認(rèn)識(shí),我們從分析其數(shù)學(xué)模型出發(fā),從而得出適宜的求解方法和步驟.1.1數(shù)學(xué)模型的比較指派問題的數(shù)學(xué)模型為[1,2]1nn∑∑cijxij,minz=i=1j=1nn∑xij∑xij=1,xij=1或0,i,j=1,2,?,n.s.t.

4、D=xij

5、=1,i=1j=1收稿日期:2002210210基金項(xiàng)目:國家高等學(xué)校骨干教師資助計(jì)劃(GG2110529003921004);空軍工程大學(xué)導(dǎo)彈學(xué)院拔尖人才基金資助項(xiàng)目作者簡介:葉微(1961—),男,陜西西安人,西安交通大學(xué)講師,博士研究生運(yùn)輸問題的數(shù)學(xué)模型為[1,3]mn∑∑cijxij,minz=i=1j=1mn∑xij∑xijs.t.D=xij

6、=ai,≥0,i=1,2,?,m;j=1,2,?,n.=bj,xiji=1j=1x=(x11,x12,?,x1n,x21,?,x2n,?,xmn)T,c=(c11,c12

7、,?,c1n,c21,?,c2n,?,cmn)T,b=(a1,a2,?,am,b1,b2,?,bn)T,A=(P11,P12,?,P1n,P21,?,P2n,?,Pmm),其中=ej+em+j=(0,?,0,1,0,?,0,1,0,?,0)T,ei為單位矩陣I(m+n)×(m+n)的第i列.若記Pij則運(yùn)輸問題的數(shù)學(xué)模型就變?yōu)閙inz=cTx,Ax=b,s.t.(1)x≥0.模型明確表明指派問題是運(yùn)輸問題的特例,即mn=n,ai=bj=1,i,j=1,2,?n;且由n于∑ai=∑bj=n.這就是說,指派問題是產(chǎn)銷量都是n的產(chǎn)銷平衡的

8、運(yùn)輸問題;決策變量i=1j=1xij全部是0-1變量(xij=0,1),cij表示第i個(gè)人員做第j個(gè)工作的花費(fèi)時(shí)間(或效率),xij=1表示指派第i個(gè)人員做第j個(gè)工作,xij=0表示不指派第i個(gè)人員做第j個(gè)工作.若采用前述向量矩陣記號(hào),并令m=n,則指派問題的數(shù)學(xué)模型就可簡記為z=cTx,Ax=1,x∈{0,1}.mins.t.(2)其中x∈{0,1}表示向量x的分量都是0或1,在(1)和(2)中A都是以0或1為元素的0-1矩陣.1.2指派問題解的特性在指派問題中,由其背景要求知道它的解中所含元素1的個(gè)數(shù)必須是n.又由于這里i,j的

9、取值都是從1到n,由運(yùn)輸問題基本解的特性知道,對(duì)于這樣的問題,它的解中所含非空格的個(gè)數(shù)應(yīng)該是2n-1,這中間所差的n-1個(gè)非空格的值都應(yīng)以0來補(bǔ)充.這就說明,指派問題的解是運(yùn)輸問題的退化解,當(dāng)然也可以認(rèn)為指派問題是一類退化的運(yùn)輸問題.1.3求解方法的比較這里以求解指派問題的匈牙利方法和求解運(yùn)輸問題的伏格爾方法來進(jìn)行比較.指派問題的匈牙利解法雖然步驟較少,但記憶起來容易混淆.特別是在作最少的直線覆蓋所有的0元素時(shí),主觀性比較大,難以掌握規(guī)律.運(yùn)輸問題的伏格爾方法雖然計(jì)算量大,但很容易計(jì)算,而且它所給出的初始解很接近最優(yōu)解,有時(shí)候用伏格

10、爾方法給出的初始解就是最優(yōu)解.若考慮用伏格爾方法求解指派問題,可以運(yùn)用劃去行列的辦法取代添零的麻煩.1.4注意問題如果用伏格爾方法給出的初始解不是最優(yōu)解,在閉回路調(diào)整時(shí),因指派問題不存在給甲加上多少,給乙減去多少的說法,即要么是甲,要