資源描述:
《物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第9章指派問題和旅行商問題9.1指派問題9.2指派問題的句牙利算法9.3旅行商問題的句牙利算法9.4哥尼斯堡七橋問題與歐拉回路9.1指派問題指派問題是指在滿足特定指派要求條件下,使指派方案總體效果最佳。在生活中經(jīng)常碰到有若干項工作需要分配給若干個人(或部門)來完成,怎么樣才會效率最高呢?這就是指派問題,一也可以說是分配問題。此類問題可以歸納為同一種情況:有個人A1,A2,…An有n項任務(wù)B1,B2,B3,……Bn,指派第i個人去完成第j項任務(wù),可以得到一個,nXn矩陣其中,表示第i個人去完成第j項任務(wù)的效率,這個矩陣稱為效益矩陣或價值矩陣。返回9.2指派問題的匈牙利算法指派問題求解歸結(jié)起來有三
2、種解法:1.一一列舉法,即從概率學(xué)出發(fā),1個人,1項工作,有1種指派;2個人,2項工作,有2種指派;3個人,3項工作,有6種指派;……;n個人,n項工作,一共有,i!種指派方法,然后一一列出來,并逐個計算其效益,找出效益最大的那個指派,當然僅限于,i的個數(shù)少的現(xiàn)象;2.表上作業(yè)法,即將指派問題當做物資調(diào)運問題來求解;3.匈牙利算法。一般說來,我們習慣使用第一種及第三種方法。下面我們來具體介紹匈牙利算法。匈牙利算法是庫恩(W.W.Kuhn)于1955年提出的指派問題的解法,他引用了匈牙利數(shù)學(xué)家狄·考尼格(D.Koni婦一個關(guān)于矩陣中零元素的定理:系數(shù)矩陣中獨立。元素的最多個數(shù)等于覆蓋所有。元素的
3、最少直線數(shù)。匈牙利算法的主要依據(jù)是最優(yōu)解定理,即如果將矩陣的一行(或一列)的各元素中,分別減去該行(或該列)的最小元素得到新矩陣,則以新矩陣為效益矩陣的指派問題的最優(yōu)解和以原矩陣為效益矩陣的指派問題的最優(yōu)解相同。下一頁返回9.2指派問題的匈牙利算法例9.2.1已知有三個人甲、乙、丙,要去完成三項工作A、B,C,如表9.1,表中數(shù)字表示所完成的時間,問怎么樣分配任務(wù)時間最省?解:分析:表中一共三個人,三個任務(wù),一共有3!=3X2X1=6種方法,用(x,y,z)表示八任務(wù)由x完成,B任務(wù)由y完成,C任務(wù)由x完成,則可得:(甲,乙,丙)=5+7+3=15;(甲,丙,乙)=5+5+4=14;(乙,甲,
4、丙)=7+3+3=13;(乙,丙,甲)=7+5+6=18;(丙,甲,乙)=8+3+415;(丙,乙,甲)=8+7+6=210可以很明顯地得到(乙,甲,丙)的方案用時最省,即A任務(wù)由乙完成,B任務(wù)由甲完成,y任務(wù)由丙完成。上一頁下一頁返回9.2指派問題的匈牙利算法綜上所述:求最佳指派問題時,當,n≤3時用“一一列舉法”較合適,較易解題,但是當,y4時,有大于或等于4!=24種的情況。隨著數(shù)字越大,情況越多,此時用匈牙利解法來得簡單。但是,并不是所有的題日都是要求時間最省,或費用最省等求最小值,有時候要求效益最大,收益最多等類型的題日要如何求解呢,這就涉及了將指派達到最大效益的問題轉(zhuǎn)化為最小的問題
5、來解決。上一頁返回9.3旅行商問題的匈牙利算法隨著國家經(jīng)濟的發(fā)展,旅游已經(jīng)成為一個家庭必不可少的一項活動,有跟團的,有獨自的。但不管是怎么樣出行,都希望能夠花最少的時間和金錢玩遍所有想玩的景點,而金錢一定的情況下,只考慮時間最省,即距離最短。旅行商問題(TravelingSalesmanproblem,TSP)是一個著名的組合優(yōu)化問題,TSP問題在物流中的描述是對應(yīng)一個物流配送公司,欲將,n個客戶的訂貨沿最短路線全部送到又返回物流配送公司。如何確定最短路線,此類問題仍可用匈牙利算法來解決。下一頁返回9.3旅行商問題的匈牙利算法設(shè)在n個城市之間進行游玩,旅游距離表為D=其中比表示第i個城市到第J
6、個城市的距離,求最短路徑。說明:1.此類問題中的“∞”表示的是從城市A到城市A的距離,一也就是。,但為了跟后面產(chǎn)生的。作區(qū)別,用“∞”來表示,但是這些項不能用。2.可以用“一一列舉法”,但是當旅行地點多于3個點時,計算量很大,要計算(n-1)!種方案。這是不可取的,一也容易遺漏。3.匈牙利算法與上一節(jié)的方法一樣,但是要注意當旅行路線出現(xiàn)兩條回路時,要把較短的回路當做不存在,拆分后分別令為∞,再次進行計算,直到組織出一條回路。上一頁下一頁返回9.3旅行商問題的匈牙利算法例9.3.1有A、B,C,D四個超市距離表為:5=現(xiàn)在要從某一個超市出發(fā)走遍所有的超市后回到原點,求最短路徑。解:從S1中可以看
7、到各行各列都只有一個0,所以就是最佳路徑為:A—B—C—D—A,總長為:3+2+5+2=12上一頁返回9.4哥尼斯堡七橋問題與歐拉回路一、歐拉回路18世紀,東普魯士的首府哥尼斯堡是一座景色迷人的城市,普萊格爾河橫貫城區(qū),這條河有兩條支流,在城中心匯成大河,在河的中央有一座美hlhl的小島。河上有七座各具特色的橋把島和河岸連接起來,如圖9.1所示。久而久之,就形成了這樣一個問題:能不能既不重復(fù)又不遺