第6章 指派問題與旅行商問題.

1、第第 6 章章 指派問題與旅行商問題指派問題與旅行商問題劉群鋒劉群鋒 講師講師東莞理工學(xué)院東莞理工學(xué)院1 指派問題及其匈牙利算法指派問題及其匈牙利算法p何謂指派問題何謂指派問題n指派指派n個人去完成個人去完成n項任務(wù)項任務(wù)n目標(biāo)：總的效益最高或者總費(fèi)用最低目標(biāo)：總的效益最高或者總費(fèi)用最低n信息：費(fèi)用矩陣或者效益矩陣信息：費(fèi)用矩陣或者效益矩陣nnn2n12n22211n1211ccccccccc1 指派問題及其匈牙利算法指派問題及其匈牙利算法p指派問題的表上作業(yè)法指派問題的表上作業(yè)法nn個收點(diǎn)個收點(diǎn)(收量為收量為1) ，n個發(fā)點(diǎn)個發(fā)點(diǎn)(發(fā)量為發(fā)量為1) 發(fā)點(diǎn)發(fā)點(diǎn) 收點(diǎn)收點(diǎn)A1A2A3發(fā)量發(fā)量B1

2、1B21B31收量收量1111 指派問題及其匈牙利算法指派問題及其匈牙利算法p指派問題的列舉法指派問題的列舉法n適用于適用于n很小的場合很小的場合 A1A2A3B1121323B2211114B31523101 指派問題及其匈牙利算法指派問題及其匈牙利算法p指派問題的匈牙利算法指派問題的匈牙利算法n理論依據(jù)理論依據(jù)l費(fèi)用矩陣的一行費(fèi)用矩陣的一行(列列)的各個元素減去該行的各個元素減去該行(列列)的的最小元素得到新的費(fèi)用矩陣，這兩個費(fèi)用矩陣對最小元素得到新的費(fèi)用矩陣，這兩個費(fèi)用矩陣對應(yīng)的指派問題有相同的最優(yōu)解！應(yīng)的指派問題有相同的最優(yōu)解！n思路思路l讓費(fèi)用矩陣的每行和每列都出現(xiàn)讓費(fèi)用矩陣的每行和

3、每列都出現(xiàn)0l找出不同行不同列的找出不同行不同列的n個個0l這些這些0對應(yīng)的指派就是最優(yōu)指派對應(yīng)的指派就是最優(yōu)指派1 指派問題及其匈牙利算法指派問題及其匈牙利算法p費(fèi)用矩陣如下，求費(fèi)用最小的指派費(fèi)用矩陣如下，求費(fèi)用最小的指派9784563211724351920312215251 指派問題及其匈牙利算法指派問題及其匈牙利算法p費(fèi)用矩陣如下，求費(fèi)用最小的指派費(fèi)用矩陣如下，求費(fèi)用最小的指派936248457713114103710365129311 指派問題及其匈牙利算法指派問題及其匈牙利算法p將將最大效益最大效益指派轉(zhuǎn)化為指派轉(zhuǎn)化為最小費(fèi)用最小費(fèi)用指派指派n用效益矩陣中最大元素減去效益矩陣中的每

4、用效益矩陣中最大元素減去效益矩陣中的每個元素得到費(fèi)用矩陣個元素得到費(fèi)用矩陣1 指派問題及其匈牙利算法指派問題及其匈牙利算法p效益矩陣如下，求效益最大的指派效益矩陣如下，求效益最大的指派9784563211724351920312215251 指派問題及其匈牙利算法指派問題及其匈牙利算法p效益矩陣如下，求效益最大的指派效益矩陣如下，求效益最大的指派936248457713114103710365129313 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p何謂旅行商問題何謂旅行商問題n從一個城市出發(fā)，不重復(fù)地旅行完從一個城市出發(fā)，不重復(fù)地旅行完n個城市，個城市，最后回到出發(fā)點(diǎn)最后回到出發(fā)點(diǎn)n目標(biāo)：

5、找出距離最短或費(fèi)用最低的旅游路線目標(biāo)：找出距離最短或費(fèi)用最低的旅游路線n信息：距離表或旅費(fèi)表信息：距離表或旅費(fèi)表n2n12n211n12cccccc3 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p費(fèi)用矩陣如下，求旅行商問題的最優(yōu)路徑費(fèi)用矩陣如下，求旅行商問題的最優(yōu)路徑8795975866583 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p費(fèi)用矩陣如下，求旅行商問題的最優(yōu)路徑費(fèi)用矩陣如下，求旅行商問題的最優(yōu)路徑12302072210238697692019151434243 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p費(fèi)用矩陣如下，求旅行商問題的最優(yōu)路徑費(fèi)用矩陣如下，求旅行商問題的最優(yōu)路徑

6、545764511261436234714 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p歐拉歐拉“一筆畫一筆畫”條件條件n沒有奇點(diǎn)或者只有沒有奇點(diǎn)或者只有2 2個奇點(diǎn)個奇點(diǎn)p歐拉回路歐拉回路n能夠一筆畫出來的一條能夠一筆畫出來的一條回路回路n所有的點(diǎn)必定是偶點(diǎn)所有的點(diǎn)必定是偶點(diǎn)n必定可以從任何一點(diǎn)出發(fā)一筆畫出必定可以從任何一點(diǎn)出發(fā)一筆畫出p歐拉回路的應(yīng)用歐拉回路的應(yīng)用n中國郵遞員問題中國郵遞員問題n4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題中國

7、郵遞員問題233332223322224 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題的解法中國郵遞員問題的解法n段道圖沒有奇點(diǎn)段道圖沒有奇點(diǎn)l最優(yōu)路線為一條歐拉回路最優(yōu)路線為一條歐拉回路n段道圖有奇點(diǎn)段道圖有奇點(diǎn)l不存在現(xiàn)成的歐拉回路不存在現(xiàn)成的歐拉回路l存在最短路徑嗎？存在最短路徑嗎？4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題中國郵遞員問題233332223322233332223322224 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p有奇點(diǎn)的段道圖怎樣尋找最短路徑？有奇點(diǎn)的段道圖怎樣尋找最短路徑？n添弧法添弧法n用幾條首尾相連的弧連接一對奇點(diǎn)用幾條首尾相連的弧連接一對奇點(diǎn)n添上的弧必須滿足以下條件添上的弧必須滿足以下條件l沒有重疊的添弧沒有重疊的添弧l圈上的添弧總長度不超過圈長的一半圈上的添弧總長度不超過圈長的一半4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題中國郵遞員問題2333322233224 哥尼斯堡七橋問題與歐拉回路哥