物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt

ID:55783348

大小:576.00 KB

頁數(shù):28頁

時間:2020-06-01

物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt_第1頁
物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt_第2頁
物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt_第3頁
物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt_第4頁
物流數(shù)學(xué)教學(xué)課件作者劉秀芬第九章.ppt_第5頁
資源描述:

《物流數(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ù)又不遺

當前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭