全國大學(xué)生數(shù)學(xué)建模競(jìng)賽D題解析PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1全國大學(xué)生數(shù)學(xué)建模競(jìng)賽全國大學(xué)生數(shù)學(xué)建模競(jìng)賽D題解析題解析巡檢線路的排班巡檢線路的排班2017年年D題講評(píng)題講評(píng) 題目題目 問題分析及問題問題分析及問題1的求解的求解 問題問題2的求解的求解 問題問題3的求解的求解 閱卷情況簡(jiǎn)述閱卷情況簡(jiǎn)述第1頁/共47頁1. 題目 巡檢線路的排班題目題目 巡檢線路的排班巡檢線路的排班 某化工廠有某化工廠有 26 個(gè)點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)個(gè)點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，各個(gè)點(diǎn)的巡檢周期、巡檢耗時(shí)、兩點(diǎn)之間的連通關(guān)，各個(gè)點(diǎn)的巡檢周期、巡檢耗時(shí)、兩點(diǎn)之間的連通關(guān)系及行走所需時(shí)間在附件中給出。系及行走所需時(shí)間在附件中給出。 每個(gè)點(diǎn)每次巡檢需要一名工人，

2、巡檢工人的巡檢每個(gè)點(diǎn)每次巡檢需要一名工人，巡檢工人的巡檢起始地點(diǎn)在巡檢調(diào)度中心（起始地點(diǎn)在巡檢調(diào)度中心（XJ0022），工人可以按固），工人可以按固定時(shí)間上班，也可以錯(cuò)時(shí)上班，在調(diào)度中心得到巡檢定時(shí)間上班，也可以錯(cuò)時(shí)上班，在調(diào)度中心得到巡檢任務(wù)后開始巡檢。現(xiàn)需要建立模型來安排巡檢人數(shù)和任務(wù)后開始巡檢?，F(xiàn)需要建立模型來安排巡檢人數(shù)和巡檢路線，使得所有點(diǎn)都能按要求完成巡檢，并且耗巡檢路線，使得所有點(diǎn)都能按要求完成巡檢，并且耗費(fèi)的人力資源盡可能少，同時(shí)還應(yīng)考慮每名工人在一費(fèi)的人力資源盡可能少，同時(shí)還應(yīng)考慮每名工人在一時(shí)間段內(nèi)（如一周或一月等）的工作量盡量平衡。時(shí)間段內(nèi)（如一周或一月等）的工作量盡量平

3、衡。表表1 Excel表中的基本信息表中的基本信息第2頁/共47頁表表2 Excel表中的連通關(guān)系表中的連通關(guān)系圖圖1 Excel表中的連通圖表中的連通圖題目題目 巡檢線路的排班巡檢線路的排班第3頁/共47頁問題問題1.如果采用固定上班時(shí)間，不考慮如果采用固定上班時(shí)間，不考慮巡檢人員的休息時(shí)間，采用每天三巡檢人員的休息時(shí)間，采用每天三班倒，每班工作班倒，每班工作8小時(shí)左右，每班需小時(shí)左右，每班需要多少人，巡檢線路如何安排，并要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的給出巡檢人員的巡檢線路和巡檢的時(shí)間表。時(shí)間表。問題問題2. 如果巡檢人員每巡檢如果巡檢人員每巡檢 2 小時(shí)小時(shí)左

4、右需要休息一次，休息時(shí)間左右需要休息一次，休息時(shí)間大約是大約是 5 到到 10 分鐘，在中午分鐘，在中午12 時(shí)和下午時(shí)和下午 6 時(shí)左右需要進(jìn)餐一時(shí)左右需要進(jìn)餐一次，每次進(jìn)餐時(shí)間為次，每次進(jìn)餐時(shí)間為 30 分鐘，分鐘，仍采用每天三班倒，每班需要仍采用每天三班倒，每班需要多少人，巡檢線路如何安排，多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和并給出巡檢人員的巡檢線路和巡檢的時(shí)間表。巡檢的時(shí)間表。題目題目 巡檢線路的排班巡檢線路的排班問題問題3. 如果采用錯(cuò)時(shí)上班，重新討論如果采用錯(cuò)時(shí)上班，重新討論問題問題 1 和問題和問題 2，試分析錯(cuò)時(shí)上，試分析錯(cuò)時(shí)上班是否更節(jié)省人力。班是否更節(jié)省人力

5、。第4頁/共47頁2.問題分析與模型建立問題分析與模型建立問題分析與模型建立 這個(gè)問題說的復(fù)雜一點(diǎn)是旅行商這個(gè)問題說的復(fù)雜一點(diǎn)是旅行商問題（問題（Traveling Salesman Problem, TSP），或者是多旅行商問題（），或者是多旅行商問題（m-TSP），更嚴(yán)格的說，是車輛路徑問），更嚴(yán)格的說，是車輛路徑問題（題（Vehicle Routing Problem, VRP），而且還是帶有時(shí)間窗口的車輛路徑，而且還是帶有時(shí)間窗口的車輛路徑問題（問題（Vehicle Routing Problem with Time Windows, VRPTW）。）。 如果這樣考慮問題，這個(gè)問題將如

6、果這樣考慮問題，這個(gè)問題將變得非常復(fù)雜。事實(shí)上，這個(gè)問題并變得非常復(fù)雜。事實(shí)上，這個(gè)問題并沒有沒有這么復(fù)雜，因?yàn)樗挥羞@么復(fù)雜，因?yàn)樗挥?6個(gè)需要個(gè)需要巡視的點(diǎn)，如果每個(gè)巡視點(diǎn)安排一個(gè)巡視的點(diǎn)，如果每個(gè)巡視點(diǎn)安排一個(gè)人的話，一個(gè)班至多是人的話，一個(gè)班至多是26個(gè)人。當(dāng)然個(gè)人。當(dāng)然，沒有那糟糕，如果一個(gè)人能巡視，沒有那糟糕，如果一個(gè)人能巡視35個(gè)點(diǎn)的話，一個(gè)班也就是個(gè)點(diǎn)的話，一個(gè)班也就是 69 個(gè)個(gè)人。因此，只需要啟發(fā)式算法就可能人。因此，只需要啟發(fā)式算法就可能得到問題的計(jì)算結(jié)果得到問題的計(jì)算結(jié)果。第5頁/共47頁問題分析問題分析巡檢人員下限估計(jì)巡檢人員下限估計(jì)2.1 巡檢人員下限估計(jì) 為估計(jì)

7、巡檢人員數(shù)量的下限，先計(jì)算出旅行商問題所需要的時(shí)間（包括路為估計(jì)巡檢人員數(shù)量的下限，先計(jì)算出旅行商問題所需要的時(shí)間（包括路程時(shí)間和巡檢耗時(shí)）。對(duì)于只有程時(shí)間和巡檢耗時(shí)）。對(duì)于只有26個(gè)城市的旅行商問題，無論是精確計(jì)算，個(gè)城市的旅行商問題，無論是精確計(jì)算，還是近似計(jì)算都是不困難的。還是近似計(jì)算都是不困難的。 可以考慮使用可以考慮使用LINGO程程序（見序（見1）得到精確的計(jì)）得到精確的計(jì)算結(jié)果（見圖算結(jié)果（見圖2），其中路），其中路程耗時(shí)程耗時(shí)68分鐘和檢查耗時(shí)分鐘和檢查耗時(shí)67分鐘，共計(jì)分鐘，共計(jì)135分鐘。分鐘。圖圖2 26個(gè)點(diǎn)的個(gè)點(diǎn)的TSP線路圖線路圖第6頁/共47頁 由于巡視點(diǎn)兩次巡視的

8、最小間隔時(shí)由于巡視點(diǎn)兩次巡視的最小間隔時(shí)間是間是35分鐘，且分鐘，且135/35=3.86，因此，因此，一個(gè)班至少需要，一個(gè)班至少需要4名工人。從圖名工人。從圖2 （TSP圖形）和題目要求（從圖形）和題目要求（從22號(hào)點(diǎn)號(hào)點(diǎn)開始巡視）來看，只用開始巡視）來看，只用4名工人巡視名工人巡視，肯定是不夠的，應(yīng)考慮增加，肯定是不夠的，應(yīng)考慮增加1名工名工人，一個(gè)班使用人，一個(gè)班使用5名工人。名工人。 從上述計(jì)算過程來看，實(shí)際上，并從上述計(jì)算過程來看，實(shí)際上，并不需要精確求解不需要精確求解TSP，只需近似計(jì)算，只需近似計(jì)算，估計(jì)出一個(gè)下界即可。，估計(jì)出一個(gè)下界即可。 例如，可例如，可以采用手工計(jì)算，也可

9、以以采用手工計(jì)算，也可以采用某些啟發(fā)式算法，如最近領(lǐng)域法采用某些啟發(fā)式算法，如最近領(lǐng)域法、最近插入法、最遠(yuǎn)插入法、最便宜、最近插入法、最遠(yuǎn)插入法、最便宜插入法、任意插入法和交換兩邊改進(jìn)插入法、任意插入法和交換兩邊改進(jìn)方法等。方法等。 如果不打算自己手工編程，可以如果不打算自己手工編程，可以使用現(xiàn)成的軟件，例如，使用現(xiàn)成的軟件，例如，R軟件中的軟件中的TSP函數(shù)（見函數(shù)（見2）就可以很好地解決）就可以很好地解決這些問題，提供不同的參數(shù)，選擇你這些問題，提供不同的參數(shù)，選擇你喜歡的算法。喜歡的算法。問題分析問題分析巡檢人員下限估計(jì)巡檢人員下限估計(jì)第7頁/共47頁 現(xiàn)知道每個(gè)班需要現(xiàn)知道每個(gè)班需要5

10、名工人，所以名工人，所以需要將巡視點(diǎn)劃分成需要將巡視點(diǎn)劃分成5個(gè)區(qū)域，每個(gè)個(gè)區(qū)域，每個(gè)區(qū)域最多包含區(qū)域最多包含6個(gè)點(diǎn)，最少也要有個(gè)點(diǎn)，最少也要有4個(gè)個(gè)點(diǎn)，其目的是保證每個(gè)區(qū)域的工作量點(diǎn)，其目的是保證每個(gè)區(qū)域的工作量（巡視時(shí)間）盡量平衡。（巡視時(shí)間）盡量平衡。 由于題目要求，每位工人均從由于題目要求，每位工人均從22號(hào)點(diǎn)開始巡視，因此，距號(hào)點(diǎn)開始巡視，因此，距22號(hào)點(diǎn)較近號(hào)點(diǎn)較近的點(diǎn)則多安排一些，而距的點(diǎn)則多安排一些，而距22號(hào)較遠(yuǎn)的號(hào)較遠(yuǎn)的2.2 問題1的求解點(diǎn)則少安排一些。為了完成這種需求點(diǎn)則少安排一些。為了完成這種需求的安排，需要計(jì)算從的安排，需要計(jì)算從22號(hào)點(diǎn)至其余各號(hào)點(diǎn)至其余各點(diǎn)的最短

11、路，這項(xiàng)工作可用點(diǎn)的最短路，這項(xiàng)工作可用Dijkstra （戴克斯特拉）算法完成。（戴克斯特拉）算法完成。 當(dāng)然，也不需要自己編程計(jì)算，直當(dāng)然，也不需要自己編程計(jì)算，直接調(diào)用接調(diào)用R軟件的軟件的shortest.paths()函函數(shù)和數(shù)和get.shortest.paths()函數(shù)（見函數(shù)（見2）就可完成此問題，所繪圖形如）就可完成此問題，所繪圖形如圖圖3所示。所示。問題分析問題分析 問題問題1 1的求解的求解第8頁/共47頁問題分析問題分析 問題問題1 1的求解的求解圖圖3 22號(hào)點(diǎn)至其余各點(diǎn)的最短路號(hào)點(diǎn)至其余各點(diǎn)的最短路第9頁/共47頁 從圖從圖3出發(fā)，作如下嘗試，將出發(fā)，作如下嘗試，將2

12、2、20、19、2、4和和21號(hào)點(diǎn)編為號(hào)點(diǎn)編為第一組；第一組；23、24、9、8、17和和25號(hào)點(diǎn)編為號(hào)點(diǎn)編為第二組；第二組；1、3、6、14、5和和7號(hào)點(diǎn)編為第號(hào)點(diǎn)編為第三組；三組；26、15、18和和12號(hào)點(diǎn)編為第四組號(hào)點(diǎn)編為第四組；11、13、16和和10號(hào)點(diǎn)編為第五組號(hào)點(diǎn)編為第五組。 每一組都找出相應(yīng)每一組都找出相應(yīng)TSP的結(jié)果，具的結(jié)果，具體分組和相應(yīng)的體分組和相應(yīng)的TSP圖形如圖圖形如圖4所所示。示。 這種分組方式是為了滿足題目的這種分組方式是為了滿足題目的要要求：求：在規(guī)定的巡視時(shí)間間隔內(nèi)完成巡視在規(guī)定的巡視時(shí)間間隔內(nèi)完成巡視；每位工人的工作量盡量平衡，巡視每位工人的工作量盡量平

13、衡，巡視時(shí)間即不能過長(zhǎng)，也不能過短。時(shí)間即不能過長(zhǎng)，也不能過短。問題分析問題分析 問題問題1 1的求解的求解第10頁/共47頁圖圖4 巡檢線路的分組情況，巡檢線路的分組情況，5-TSP問題分析問題分析 問題問題1 1的求解的求解第11頁/共47頁下面給出具體的巡視路線和巡視時(shí)間下面給出具體的巡視路線和巡視時(shí)間：第第1組（組（22、20、19、2、4和和21號(hào)點(diǎn)）的巡視周期是號(hào)點(diǎn)）的巡視周期是29分鐘，而分鐘，而21號(hào)點(diǎn)的周期間隔是號(hào)點(diǎn)的周期間隔是80分鐘，可分鐘，可以兩個(gè)以兩個(gè)35分鐘巡視一次，所以此分鐘巡視一次，所以此時(shí)巡視同期是時(shí)巡視同期是27分鐘。分鐘。第第2組（組（23、24、9、8、

14、17和和25號(hào)點(diǎn)）的巡視，最長(zhǎng)周期是號(hào)點(diǎn)）的巡視，最長(zhǎng)周期是32分分鐘、最短周期鐘、最短周期28分鐘（分鐘（17號(hào)點(diǎn)和號(hào)點(diǎn)和25號(hào)點(diǎn)的時(shí)間間隔為分別為號(hào)點(diǎn)的時(shí)間間隔為分別為480分分鐘和鐘和 120分鐘）。分鐘）。第第3組（組（1、3、6、14、5和和7號(hào)點(diǎn)號(hào)點(diǎn)）的巡視，最長(zhǎng)周期是）的巡視，最長(zhǎng)周期是32分鐘，分鐘，最短周期最短周期19分鐘（分鐘（5號(hào)點(diǎn)和號(hào)點(diǎn)和7號(hào)點(diǎn)號(hào)點(diǎn)的時(shí)間間隔分別為的時(shí)間間隔分別為720分鐘和分鐘和80分分鐘）。鐘）。第第4組（組（26、15、18和和12號(hào)點(diǎn)）的號(hào)點(diǎn)）的巡視，周期長(zhǎng)度是巡視，周期長(zhǎng)度是28分鐘。分鐘。第第5組（組（11、13、16和和10號(hào)點(diǎn)）的號(hào)點(diǎn)）的

15、巡視，周期長(zhǎng)度是巡視，周期長(zhǎng)度是25分鐘。分鐘。問題分析問題分析 問題問題1 1的求解的求解第12頁/共47頁表表3 第第1組巡視的時(shí)間表（部分）組巡視的時(shí)間表（部分）問題分析問題分析 問題問題1 1的求解的求解第13頁/共47頁表表4 第第2組巡視的時(shí)間表（部分）組巡視的時(shí)間表（部分）問題分析問題分析 問題問題1 1的求解的求解第14頁/共47頁表表5 第第3組巡視的時(shí)間表（部分）組巡視的時(shí)間表（部分）問題分析問題分析 問題問題1 1的求解的求解第15頁/共47頁表表6 第第4組巡視的時(shí)間表（部分）組巡視的時(shí)間表（部分）問題分析問題分析 問題問題1 1的求解的求解第16頁/共47頁表表7 第

16、第5組巡視的時(shí)間表（部分）組巡視的時(shí)間表（部分）問題分析問題分析 問題問題1 1的求解的求解第17頁/共47頁3.問題2的求解問題問題2 2 休息時(shí)間休息時(shí)間3.1 休息時(shí)間 為了簡(jiǎn)化問題，先不用考慮為了簡(jiǎn)化問題，先不用考慮“每巡每巡視視2小時(shí)左右休息大約小時(shí)左右休息大約5到到10分鐘分鐘”這這一要求。一要求。 因?yàn)樵趩栴}因?yàn)樵趩栴}1的求解過程中，的求解過程中，5名名工人在巡視過程中，多次出現(xiàn)工人在巡視過程中，多次出現(xiàn)5分鐘分鐘的空余時(shí)間，這些空余時(shí)間可作休息的空余時(shí)間，這些空余時(shí)間可作休息時(shí)間。時(shí)間。 在問題在問題1的討論中，每班需要的討論中，每班需要5名名工人，考慮兩次進(jìn)餐時(shí)間（工人，考慮

17、兩次進(jìn)餐時(shí)間（1小時(shí)）小時(shí)），就需要增加，就需要增加5小時(shí)，如果再考慮進(jìn)小時(shí)，如果再考慮進(jìn)餐的銜接時(shí)間，需要增加的時(shí)間還不餐的銜接時(shí)間，需要增加的時(shí)間還不止止5小時(shí)，所以僅依賴于原來的小時(shí)，所以僅依賴于原來的5名工名工人而擠出進(jìn)餐時(shí)間幾乎是不可能的。人而擠出進(jìn)餐時(shí)間幾乎是不可能的。 因此，需要增加因此，需要增加1名工人讓他在名工人讓他在其他工人進(jìn)餐時(shí)，完成巡視工作。其他工人進(jìn)餐時(shí)，完成巡視工作。3.2 進(jìn)餐時(shí)間第18頁/共47頁排班的方法是：排班的方法是：原來的排班時(shí)間不變；原來的排班時(shí)間不變；5名工人的進(jìn)餐時(shí)間安排在名工人的進(jìn)餐時(shí)間安排在11時(shí)至?xí)r至13時(shí)之間，和時(shí)之間，和17時(shí)至?xí)r至19時(shí)

18、之間；時(shí)之間；進(jìn)餐時(shí)間為進(jìn)餐時(shí)間為35分鐘（最小的時(shí)間間隔），進(jìn)餐時(shí)的巡視工作由第分鐘（最小的時(shí)間間隔），進(jìn)餐時(shí)的巡視工作由第6名（機(jī)名（機(jī)動(dòng)）工人完成；動(dòng)）工人完成；第第6名（機(jī)動(dòng)）工人的進(jìn)餐時(shí)間可安排在他不替班的非工作時(shí)間。名（機(jī)動(dòng)）工人的進(jìn)餐時(shí)間可安排在他不替班的非工作時(shí)間。 表表8至表至表12給出了部分排班的時(shí)間表（白班和中班），圖中的黃色部分是可給出了部分排班的時(shí)間表（白班和中班），圖中的黃色部分是可用于吃飯的時(shí)間。用于吃飯的時(shí)間。 第第6名（機(jī)動(dòng)）工人的巡視時(shí)間表，以及替換組的情況如表名（機(jī)動(dòng)）工人的巡視時(shí)間表，以及替換組的情況如表13所示。所示。問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第

19、19頁/共47頁表表8 第第1組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第20頁/共47頁表表9 第第2組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第21頁/共47頁表表10 第第3組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第22頁/共47頁表表11 第第4組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第23頁/共47頁表表12 第第5組巡視的時(shí)間表（部分

20、，包含進(jìn)餐時(shí)間）組巡視的時(shí)間表（部分，包含進(jìn)餐時(shí)間）問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第24頁/共47頁表表13 第第6組（機(jī)動(dòng)）的巡視時(shí)間表組（機(jī)動(dòng)）的巡視時(shí)間表問題問題2 2 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第25頁/共47頁4.問題3的求解4.1 上班時(shí)間 問題問題3是考慮錯(cuò)時(shí)上班能否更省人是考慮錯(cuò)時(shí)上班能否更省人力。力。 由前面的分析（巡視人員的下限和由前面的分析（巡視人員的下限和問題問題1）, 知道人員的下限是每班知道人員的下限是每班4人人，而固定時(shí)間上班則需要每班，而固定時(shí)間上班則需要每班5人。人。那么，是否能省下這那么，是否能省下這1個(gè)人成為問題個(gè)人成為問題的關(guān)鍵。的關(guān)鍵。 如果能省，應(yīng)在哪個(gè)地方

21、省；如果如果能省，應(yīng)在哪個(gè)地方省；如果不能省，這個(gè)問題也就沒有討論的必不能省，這個(gè)問題也就沒有討論的必要了。要了。 每個(gè)點(diǎn)的檢查時(shí)間（共計(jì)每個(gè)點(diǎn)的檢查時(shí)間（共計(jì)67分鐘）分鐘）肯定是不能省，因此，要省也只能省肯定是不能省，因此，要省也只能省下巡視中所花的路程時(shí)間。下巡視中所花的路程時(shí)間。 巡視全部點(diǎn)（巡視全部點(diǎn)（26個(gè)點(diǎn)）的最短路個(gè)點(diǎn)）的最短路程這恰好是一個(gè)旅行商問題，由前面程這恰好是一個(gè)旅行商問題，由前面的計(jì)算已知，這個(gè)時(shí)間是的計(jì)算已知，這個(gè)時(shí)間是68分鐘。分鐘。問題問題3 3 上班時(shí)間上班時(shí)間第26頁/共47頁 那么巡視全部點(diǎn)的最短時(shí)間是那么巡視全部點(diǎn)的最短時(shí)間是135分鐘。而題目要求，要

22、在規(guī)定的時(shí)間分鐘。而題目要求，要在規(guī)定的時(shí)間間隔（最短為間隔（最短為35分鐘）內(nèi)完成各點(diǎn)的分鐘）內(nèi)完成各點(diǎn)的巡視。巡視。 這樣，只能換一種排班方法，讓每這樣，只能換一種排班方法，讓每名巡視工人完成一輪（名巡視工人完成一輪（26個(gè)點(diǎn)）的巡個(gè)點(diǎn)）的巡視，而每名工人的上班時(shí)間向后錯(cuò)視，而每名工人的上班時(shí)間向后錯(cuò)35分鐘，即在前一位工人開始巡視的分鐘，即在前一位工人開始巡視的35分鐘之后，再安排另一名工人巡視。分鐘之后，再安排另一名工人巡視。 對(duì)于巡視間隔要求大于對(duì)于巡視間隔要求大于35分鐘的分鐘的點(diǎn)，可以采用下面的方法處理：點(diǎn)，可以采用下面的方法處理：l無論哪一個(gè)點(diǎn)，一律在無論哪一個(gè)點(diǎn)，一律在35分

23、鐘巡分鐘巡視一次，這樣肯定滿足題目的要視一次，這樣肯定滿足題目的要求；求；l在滿足巡視時(shí)間間隔要求的情況在滿足巡視時(shí)間間隔要求的情況下，可以不巡視，但要在相應(yīng)點(diǎn)下，可以不巡視，但要在相應(yīng)點(diǎn)處休息，休息的時(shí)間就是該點(diǎn)的處休息，休息的時(shí)間就是該點(diǎn)的巡視需要的時(shí)間。巡視需要的時(shí)間。問題問題3 3 上班時(shí)間上班時(shí)間第27頁/共47頁 因此，得到如下的排班方法：第因此，得到如下的排班方法：第1名工人在名工人在8:00開始巡視（上班或換開始巡視（上班或換班），第班），第2名工人則在名工人則在8:35開始巡視開始巡視，第，第3名是名是9:10，第，第4名是名是9:45。而每。而每位工人都走最優(yōu)的旅行商路線。

24、位工人都走最優(yōu)的旅行商路線。 注意到，每名巡視工人的間隔時(shí)注意到，每名巡視工人的間隔時(shí)間是間是35分鐘，分鐘，4名工人的間隔時(shí)間是名工人的間隔時(shí)間是140分鐘，而一次分鐘，而一次26個(gè)點(diǎn)的旅行商問個(gè)點(diǎn)的旅行商問題的用時(shí)是題的用時(shí)是135分鐘。分鐘。 如果第如果第1名工人在第一輪巡視后名工人在第一輪巡視后，休息，休息5分鐘，那么他要在分鐘，那么他要在10:20開始開始第二輪的巡視，與第一輪巡視的第第二輪的巡視，與第一輪巡視的第4名工人的巡視時(shí)間間隔正好相差名工人的巡視時(shí)間間隔正好相差35分分鐘。第鐘。第2名工人第二輪巡視的開始時(shí)名工人第二輪巡視的開始時(shí)間是間是10:55，與第，與第1名工人相差名

25、工人相差35分鐘分鐘，以此類推。，以此類推。 由上述推導(dǎo)可知，由上述推導(dǎo)可知，4名工人足夠滿名工人足夠滿足巡視的要求，同時(shí)也達(dá)到了巡視人足巡視的要求，同時(shí)也達(dá)到了巡視人員要求的下界，是最優(yōu)的。員要求的下界，是最優(yōu)的。問題問題3 3 上班時(shí)間上班時(shí)間第28頁/共47頁表表14 錯(cuò)時(shí)上班的時(shí)間表（部分）錯(cuò)時(shí)上班的時(shí)間表（部分）問題問題3 3 上班時(shí)間上班時(shí)間第29頁/共47頁4.2 換班時(shí)間 由于題目要求，上班或換班的地點(diǎn)由于題目要求，上班或換班的地點(diǎn)只能是調(diào)度中心，也就是說，只能在只能是調(diào)度中心，也就是說，只能在完成一輪（完成一輪（26個(gè)點(diǎn)）巡視后才能換班個(gè)點(diǎn)）巡視后才能換班。因此，每名工人的換

26、班時(shí)間只能是。因此，每名工人的換班時(shí)間只能是140分鐘的整數(shù)倍，選擇合適的時(shí)間分鐘的整數(shù)倍，選擇合適的時(shí)間點(diǎn)，工作點(diǎn)，工作7個(gè)小時(shí)開始換班。個(gè)小時(shí)開始換班。 例如，第一班工作的例如，第一班工作的4名工人上班名工人上班的時(shí)間分別是的時(shí)間分別是8:00、8:35、9:10和和9:45，那么，第二班的，那么，第二班的4名工人的換名工人的換班時(shí)間分別是班時(shí)間分別是15:00、15:35、16:10和和16:45，第三班的，第三班的4名工人的換班時(shí)名工人的換班時(shí)間分別是間分別是22:00、22:35、23:10和和23:45。 由于每天是由于每天是24小時(shí)，而換班的時(shí)間小時(shí)，而換班的時(shí)間是是7小時(shí)，三班

27、下來是小時(shí)，三班下來是21小時(shí)，所以小時(shí)，所以每天的換班時(shí)間比前一天提前每天的換班時(shí)間比前一天提前3小時(shí)小時(shí)。 問題問題3 3 換班時(shí)間換班時(shí)間第30頁/共47頁 也就是說，第一班的也就是說，第一班的4名工人在第名工人在第二天的換班時(shí)間分別是二天的換班時(shí)間分別是5:00、5:35、6:10和和6:45；第二班的；第二班的4名工人在第名工人在第二天的換班時(shí)間分別是二天的換班時(shí)間分別是12:00、12:35、 13:10和和13:45；第三班的；第三班的4名工人名工人在第二天的換班時(shí)間分別是在第二天的換班時(shí)間分別是19:00、 19:35、20:10和和20:45。 以后的各天以此類推，每天提早以

28、后的各天以此類推，每天提早3個(gè)小時(shí)換班。個(gè)小時(shí)換班。 一周一周7天，有天，有7個(gè)個(gè)24小時(shí)，恰好有小時(shí)，恰好有8個(gè)個(gè)21小時(shí)，所以這種換班方案一周重小時(shí)，所以這種換班方案一周重復(fù)一次。具體換班方案如表復(fù)一次。具體換班方案如表15所示。所示。4.3 中間休息 與問題與問題2相同，這里不用考慮每相同，這里不用考慮每2個(gè)個(gè)小時(shí)左右休息小時(shí)左右休息5分鐘的問題，因?yàn)檫@分鐘的問題，因?yàn)檫@里面有太多的休息時(shí)間。例如，一輪里面有太多的休息時(shí)間。例如，一輪巡視后，可休息巡視后，可休息5分鐘。分鐘。問題問題3 3 換班時(shí)間換班時(shí)間第31頁/共47頁表表15 錯(cuò)時(shí)上班的換班時(shí)間表錯(cuò)時(shí)上班的換班時(shí)間表問題問題3 3

29、 中間休息中間休息第32頁/共47頁4.4 進(jìn)餐時(shí)間 考慮進(jìn)餐時(shí)間會(huì)使排班麻煩一些?？紤]進(jìn)餐時(shí)間會(huì)使排班麻煩一些。 首先由于進(jìn)餐時(shí)間增加了首先由于進(jìn)餐時(shí)間增加了4個(gè)小時(shí)，個(gè)小時(shí)，所以，不可能在一個(gè)班內(nèi)由所以，不可能在一個(gè)班內(nèi)由4名工人名工人完成。與問題完成。與問題2一樣，需要增加一樣，需要增加1名機(jī)名機(jī)動(dòng)工人，頂替工人吃飯時(shí)的巡視。動(dòng)工人，頂替工人吃飯時(shí)的巡視。 由于題目要求，換班只能在由于題目要求，換班只能在22號(hào)號(hào)點(diǎn)完成，也就是說，吃飯的換班時(shí)間點(diǎn)完成，也就是說，吃飯的換班時(shí)間也只能在也只能在22號(hào)點(diǎn)完成，也就是在完成號(hào)點(diǎn)完成，也就是在完成某一輪的巡視后，才可以考慮進(jìn)餐。某一輪的巡視后，才

30、可以考慮進(jìn)餐。 還以第一班工作時(shí)間為例，考慮進(jìn)還以第一班工作時(shí)間為例，考慮進(jìn)餐時(shí)間的安排。餐時(shí)間的安排。 從從8:35開始工作的第開始工作的第2名工人，在名工人，在10:50完成第一輪的巡視，如果他不完成第一輪的巡視，如果他不進(jìn)餐，將在進(jìn)餐，將在10:55開始第二輪的巡視開始第二輪的巡視，這時(shí)，可以考慮讓他停止工作，選，這時(shí)，可以考慮讓他停止工作，選擇吃午飯，他的工作由機(jī)動(dòng)（第擇吃午飯，他的工作由機(jī)動(dòng)（第5名名）工人替代完成。）工人替代完成。問題問題3 3 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第33頁/共47頁 在在30分鐘后，讓分鐘后，讓11:25完成第一輪完成第一輪巡視的第巡視的第3名工人休息進(jìn)餐，而第名工人

31、休息進(jìn)餐，而第2名名工人來接替他，在工人來接替他，在11:30開始工作。開始工作。 之后，第之后，第3名工作完成進(jìn)餐后，接名工作完成進(jìn)餐后，接替替12:05開始工作的第開始工作的第4名工人，讓第名工人，讓第4名工人吃午飯。名工人吃午飯。 第第4名工人午飯后，在名工人午飯后，在12:40接替第接替第1名工人的工作，第名工人的工作，第1名工人開始吃午名工人開始吃午飯。飯。 第第1名工人在午飯后就不工作了，名工人在午飯后就不工作了，需要等到下午需要等到下午18:30分，接替第分，接替第2名工名工人的工作，直到這個(gè)班工作結(jié)束。在人的工作，直到這個(gè)班工作結(jié)束。在這中間也不考慮他吃晚飯的時(shí)間，因這中間也不

32、考慮他吃晚飯的時(shí)間，因?yàn)樗梢栽跒樗梢栽?8:30以前吃完晚飯。以前吃完晚飯。 此時(shí)此時(shí)(18:30)，第，第2名工人在吃晚飯名工人在吃晚飯，飯后，飯后(19:05)他接替第他接替第3位工人的工位工人的工作。作。 19:05，第，第3名工人在吃晚飯，名工人在吃晚飯，19:40接替第接替第4位工人的工作。位工人的工作。問題問題3 3 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第34頁/共47頁 20:15，第，第4位工人開始工作，接替位工人開始工作，接替第第5位（機(jī)動(dòng)）工人的工作。而機(jī)動(dòng)位（機(jī)動(dòng)）工人的工作。而機(jī)動(dòng)工人則下班休息（這時(shí)不用考慮他是工人則下班休息（這時(shí)不用考慮他是否吃晚飯），因?yàn)榈降诙斓姆癯酝盹垼?，因?yàn)?/p>

33、到第二天的10:50才接替第才接替第1位工人的工作，讓第位工人的工作，讓第1位工位工人吃午飯。人吃午飯。 這個(gè)過程較為復(fù)雜，詳細(xì)排班請(qǐng)見這個(gè)過程較為復(fù)雜，詳細(xì)排班請(qǐng)見錯(cuò)時(shí)上班的換班時(shí)間表錯(cuò)時(shí)上班的換班時(shí)間表, 表表16顯示了顯示了Excel表中排班和換班的部分表格。表中排班和換班的部分表格。表表16 增加吃飯時(shí)間的排班表增加吃飯時(shí)間的排班表問題問題3 3 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第35頁/共47頁續(xù)表續(xù)表16-2 增加吃飯時(shí)間的排班表增加吃飯時(shí)間的排班表續(xù)表續(xù)表16-1 增加吃飯時(shí)間的排班表增加吃飯時(shí)間的排班表問題問題3 3 進(jìn)餐時(shí)間進(jìn)餐時(shí)間第36頁/共47頁5.閱卷情況簡(jiǎn)述閱卷情況閱卷情況 固定上班

34、時(shí)間固定上班時(shí)間 本人參加了北京地區(qū)和全國的本人參加了北京地區(qū)和全國的D題題閱卷，下面就閱卷中遇到的問題談一閱卷，下面就閱卷中遇到的問題談一談本人一點(diǎn)感受。談本人一點(diǎn)感受。5.1 固定上班時(shí)間 問題問題1和問題和問題2要求：固定時(shí)間上要求：固定時(shí)間上班，并且由巡檢調(diào)度中心（班，并且由巡檢調(diào)度中心（22號(hào)點(diǎn)）號(hào)點(diǎn)）開始巡檢。開始巡檢。 在通常情況下，三班倒的工作時(shí)在通常情況下，三班倒的工作時(shí)間分別是間分別是8:00 16:00，16:00 24:00和和0:00 8:00。 這一點(diǎn)絕大多數(shù)的隊(duì)都注意到了這一點(diǎn)絕大多數(shù)的隊(duì)都注意到了，所以基本上都采用，所以基本上都采用8點(diǎn)、下午點(diǎn)、下午4點(diǎn)和點(diǎn)和凌

35、晨凌晨0點(diǎn)開始上班的模式。當(dāng)然，如點(diǎn)開始上班的模式。當(dāng)然，如果你認(rèn)為有必要，采用其他時(shí)間開始果你認(rèn)為有必要，采用其他時(shí)間開始上班也是正確的，只要是固定時(shí)間上上班也是正確的，只要是固定時(shí)間上班就可以。班就可以。第37頁/共47頁 但這個(gè)固定上班時(shí)間，是每個(gè)班組但這個(gè)固定上班時(shí)間，是每個(gè)班組的固定上班時(shí)間，不是每個(gè)人的固定的固定上班時(shí)間，不是每個(gè)人的固定上班時(shí)間。上班時(shí)間。 例如，一個(gè)班有例如，一個(gè)班有5個(gè)人個(gè)人 (5條巡視線條巡視線路路)，則要求這，則要求這5個(gè)人同時(shí)上班。這也個(gè)人同時(shí)上班。這也是為什么要求大家一定從是為什么要求大家一定從22號(hào)點(diǎn)開始號(hào)點(diǎn)開始的原因，大家需要集中一下（如布置的原因

36、，大家需要集中一下（如布置工作或其他要求）。工作或其他要求）。 有很多隊(duì)理解成每名工人固定時(shí)有很多隊(duì)理解成每名工人固定時(shí)間上班，而上班時(shí)間是不同的，這樣間上班，而上班時(shí)間是不同的，這樣理解問題，巡檢工作從理解問題，巡檢工作從22號(hào)點(diǎn)開始就號(hào)點(diǎn)開始就無意義了，因?yàn)榭梢宰専o意義了，因?yàn)榭梢宰?2號(hào)點(diǎn)、號(hào)點(diǎn)、23號(hào)、號(hào)、1號(hào)點(diǎn)、號(hào)點(diǎn)、26號(hào)點(diǎn)和號(hào)點(diǎn)和11號(hào)點(diǎn)都是從號(hào)點(diǎn)都是從8點(diǎn)開始工作，而這些點(diǎn)開始上班的點(diǎn)開始工作，而這些點(diǎn)開始上班的時(shí)間分別為時(shí)間分別為8:00、7:59、7:52、7:50和和7:45，這種方法相當(dāng)于去掉從，這種方法相當(dāng)于去掉從22號(hào)號(hào)點(diǎn)開始的要求，降低了題目的難度。點(diǎn)開始的要求，

37、降低了題目的難度。事實(shí)上，這種做法只需要事實(shí)上，這種做法只需要4個(gè)人就夠個(gè)人就夠了。了。閱卷情況閱卷情況 固定上班時(shí)間固定上班時(shí)間第38頁/共47頁 還有一個(gè)小問題：每個(gè)班的巡檢工還有一個(gè)小問題：每個(gè)班的巡檢工作是否能在作是否能在8小時(shí)內(nèi)結(jié)束（并不要求小時(shí)內(nèi)結(jié)束（并不要求一定在一定在8小時(shí)內(nèi)回到小時(shí)內(nèi)回到22號(hào)點(diǎn)），這個(gè)號(hào)點(diǎn)），這個(gè)問題基本上沒有學(xué)生討論，但它應(yīng)該問題基本上沒有學(xué)生討論，但它應(yīng)該是問題潛在的要求，因?yàn)樵诮唤影鄷r(shí)是問題潛在的要求，因?yàn)樵诮唤影鄷r(shí)，應(yīng)該簡(jiǎn)短地說明一下本班的巡檢情，應(yīng)該簡(jiǎn)短地說明一下本班的巡檢情況。況。 當(dāng)然，并不需要見面交流，用一下當(dāng)然，并不需要見面交流，用一下現(xiàn)代

38、通訊工具是可以的?，F(xiàn)代通訊工具是可以的。 題目明確要求，給出巡檢人員的巡題目明確要求，給出巡檢人員的巡檢線路和巡檢的時(shí)間表，但很多隊(duì)只檢線路和巡檢的時(shí)間表，但很多隊(duì)只給出巡檢線路圖，并沒有給出具體的給出巡檢線路圖，并沒有給出具體的巡檢點(diǎn)的時(shí)間表。巡檢點(diǎn)的時(shí)間表。 由于沒有巡檢點(diǎn)的排班時(shí)間表，因由于沒有巡檢點(diǎn)的排班時(shí)間表，因此無法判斷該隊(duì)的結(jié)果是否正確，是此無法判斷該隊(duì)的結(jié)果是否正確，是否滿足巡檢要求。本質(zhì)上沒有完成題否滿足巡檢要求。本質(zhì)上沒有完成題目要求，分?jǐn)?shù)上也會(huì)打折扣的。目要求，分?jǐn)?shù)上也會(huì)打折扣的。5.2 巡檢線路與時(shí)間表閱卷情況閱卷情況 巡檢時(shí)間表巡檢時(shí)間表第39頁/共47頁5.3 休息

39、時(shí)間與進(jìn)餐時(shí)間 問題問題2要求：每巡檢要求：每巡檢2小時(shí)左右需小時(shí)左右需要休息一次，休息時(shí)間大約是要休息一次，休息時(shí)間大約是5到到10分鐘。在中午分鐘。在中午12時(shí)和下午時(shí)和下午6時(shí)左右需時(shí)左右需要進(jìn)餐一次，進(jìn)餐時(shí)間為要進(jìn)餐一次，進(jìn)餐時(shí)間為30分鐘。分鐘。 實(shí)際上實(shí)際上, 如果每名巡檢人員的排班如果每名巡檢人員的排班時(shí)間較均勻，這里并不需要真的考慮時(shí)間較均勻，這里并不需要真的考慮休息時(shí)間的安排，因?yàn)樵谘矙z中有大休息時(shí)間的安排，因?yàn)樵谘矙z中有大量的量的5分鐘可以作為休息時(shí)間。分鐘可以作為休息時(shí)間。 進(jìn)餐時(shí)間不是固定的，否則，大家進(jìn)餐時(shí)間不是固定的，否則，大家都在中午都在中午12時(shí)進(jìn)餐，這樣就需要

40、再派時(shí)進(jìn)餐，這樣就需要再派其他的工人來頂替進(jìn)餐時(shí)的空缺，需其他的工人來頂替進(jìn)餐時(shí)的空缺，需要的人數(shù)是原來的要的人數(shù)是原來的2倍，這顯然過于倍，這顯然過于浪費(fèi)人力。浪費(fèi)人力。 當(dāng)進(jìn)餐時(shí)間不固定時(shí)，只需要增加當(dāng)進(jìn)餐時(shí)間不固定時(shí)，只需要增加一名工人就夠了，這名工人的工作是一名工人就夠了，這名工人的工作是接替中午和晚上需要進(jìn)餐的工人，這接替中午和晚上需要進(jìn)餐的工人，這里的重點(diǎn)是具體的替班時(shí)間表。里的重點(diǎn)是具體的替班時(shí)間表。閱卷情況閱卷情況 休息與進(jìn)餐時(shí)間休息與進(jìn)餐時(shí)間第40頁/共47頁5.4 錯(cuò)時(shí)上班的討論 問題問題3是討論錯(cuò)時(shí)上班是否更節(jié)省是討論錯(cuò)時(shí)上班是否更節(jié)省人力，如果不能更節(jié)省人力，這一問人力

41、，如果不能更節(jié)省人力，這一問也就沒有討論的必要。有的隊(duì)，討論也就沒有討論的必要。有的隊(duì)，討論了半天還是不能更省人力?？梢圆孪肓税胩爝€是不能更省人力。可以猜想，該隊(duì)?wèi)?yīng)該沒有完成題目的要求。，該隊(duì)?wèi)?yīng)該沒有完成題目的要求。 實(shí)際上，更省人力是這個(gè)問題的重實(shí)際上，更省人力是這個(gè)問題的重點(diǎn)，需要分析在哪些地方可以更省人點(diǎn)，需要分析在哪些地方可以更省人力。力。 巡檢時(shí)間肯定是不能省的，要省也巡檢時(shí)間肯定是不能省的，要省也只能是巡檢路線，盡量少走重復(fù)路線只能是巡檢路線，盡量少走重復(fù)路線。這自然會(huì)想到旅行商問題。但我。這自然會(huì)想到旅行商問題。但我們發(fā)現(xiàn)，很多?？茖W(xué)校沒有培訓(xùn)過圖們發(fā)現(xiàn)，很多?？茖W(xué)校沒有培訓(xùn)過圖論方面的相關(guān)知識(shí)。論方面的相關(guān)知識(shí)。 經(jīng)過驗(yàn)算經(jīng)過驗(yàn)算,旅行商問題的解是旅行商問題的解是135分分鐘，巡檢點(diǎn)的最小間隔時(shí)間是鐘，巡檢點(diǎn)的最小間隔時(shí)間是35分鐘分鐘，因此，需要，因此，需要4名工人就可以能完成名工人就可以能完成工作。工作。閱卷情況閱卷情況 錯(cuò)時(shí)上班時(shí)間錯(cuò)時(shí)上班時(shí)間第41頁/共47頁 排班方法有點(diǎn)像列車時(shí)刻表，每隔排班方法有點(diǎn)像列車時(shí)