建模案例最佳災情巡視路線

建模案例：最佳災情巡視路線這里介紹1998年全國大學生數(shù)學模型競賽B題中的兩個問題.一、問題今年夏天某縣遭受水災.為考察災情、組織自救，縣領(lǐng)導決定，帶領(lǐng)有關(guān)部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.若分三組（路）巡視，試設計總路程最短且各組盡可能均衡的路線.假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2h，在各村停留時間t=1h，汽車行駛速度V=35km/h鄉(xiāng)鎮(zhèn)、村的公路網(wǎng)示意圖見圖1.圖1假設1．汽車在路上的速度總是一定，不會出現(xiàn)拋錨等現(xiàn)象；2．巡視當中，在每個鄉(xiāng)鎮(zhèn)、村的停留時間一定，不會出現(xiàn)特殊情況而延誤時間；3．每個小組的汽車行駛速度完全一樣；4．分組后，各小組只能走自己區(qū)內(nèi)的路，不能走其他小組的路（除公共路外）.三、模型的建立與求解將公路網(wǎng)圖中，每個鄉(xiāng)（鎮(zhèn)）或村看作圖中的一個節(jié)點，各鄉(xiāng)（鎮(zhèn)）、村之間的公路看作圖中對應節(jié)點間的邊，各條公路的長度（或行駛時間）看作對應邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡圖，問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡圖中尋找從給定點O出發(fā)，行遍所有頂點至少一次再回到O點，使得總權(quán)（路程或時間）最小，此即最佳推銷員回路問題.在加權(quán)圖G中求最佳推銷員回路問題是NP—完全問題，我們采用一種近似算法求出該問題的一個近似最優(yōu)解，來代替最優(yōu)解，算法如下：算法一求加權(quán)圖G（V，E）的最佳推銷員回路的近似算法：用圖論軟件包求出G中任意兩個頂點間的最短路，構(gòu)造出完備圖，，；輸入圖的一個初始H圈；用對角線完全算法產(chǎn)生一個初始H圈；隨機搜索出中若干個H圈，例如2000個；對第2、3、4步所得的每個H圈，用二邊逐次修正法進行優(yōu)化，得到近似最佳H圈；在第5步求出的所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解.由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第2、3、4步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計算結(jié)果.問題一若分為3組巡視，設計總路程最短且各組盡可能均衡的巡視路線.此問題是多個推銷員的最佳推銷員回路問題.即在加權(quán)圖G中求頂點集V的劃分，將G分成n個生成子圖，使得（1）頂點,i=1，2，3,…,n；（2）；（3），其中為的導出子圖中的最佳推銷員回路，為的權(quán)，i，j=1，2，3,…,n；（4）取最小.定義稱為該分組的實際均衡度.為最大容許均衡度.顯然，越小，說明分組的均衡性越好.取定一個后，與滿足條件（3）的分組是一個均衡分組.條件（4）表示總巡視路線最短.此問題包含兩方面：第一，對頂點分組；第二，在每組中求最佳推銷員回路，即為單個推銷員的最佳推銷員問題.由于單個推銷員的最佳推銷員回路問題不存在多項式時間內(nèi)的精確算法，故多個推銷員的問題也不存在多項式時間內(nèi)的精確算法.而圖中節(jié)點數(shù)較多，為53個，我們只能去尋求一種較合理的劃分準則，對圖１進行粗步劃分后，求出各部表3（路程單位：km；時間單位：h）組名路線路線總長度停留時間行走時間完成巡視的總時間=1\*ROMANIO—2—5—6—7—E—8—E—11—G—12—H—12—F—10—F—9—E—7—6—5—2—O195.8175.5922.59=2\*ROMANIIO—R—29—Q—30—Q—28—27—26—N—24—23—22—17—16—17—K—22—23—N—26—P—O199.2165.6921.69=3\*ROMANIIIO—M—25—20—21—K—18—I—15—14—13—J—19—L—6—M—O159.1184.5422.54=4\*ROMANIVO—R—A—33—31—32—35—34—B—1—C—3—D—4—D—3—2—O166184.7422.74上表中符號說明