摘 要:本文針對冰雪天氣中電力搶修問題——既要保證各地之間電力互通，又要實現(xiàn)最小費用和最少時間。我們可以把這個問題看成單個旅行售貨員問題，首先用floyd算法求出任意兩點間的最短距離，而后借用旅行商算法，假定一個旅行商從A點出發(fā)，經(jīng)過所有的鄉(xiāng)鎮(zhèn)一次且僅一次，最后仍回到原來出發(fā)的A點，利用lingo編程求出最短距離及所經(jīng)路線，給出了一較好的搶修方案。

關(guān)鍵詞:電力搶修 旅行商問題 floyd算法

中圖分類號:TM7\t\t\t文獻標(biāo)識碼:A\t\t\t文章編號:1672-3791(2011)10(a)-0140-02

2011年初北方某縣遭遇旱見的雨雪冰凍災(zāi)害，電力設(shè)施損毀嚴(yán)重。某縣電力公司為了搶修當(dāng)?shù)厥軗p電力線路，盡快實現(xiàn)與大電網(wǎng)的聯(lián)通，共派出3個施工搶修隊，分別從A，B，C三地開始施工。如圖1，各鄉(xiāng)鎮(zhèn)之間距離已知，沒有連接的鄉(xiāng)鎮(zhèn)之間由于地形等原因無法架設(shè)線路，另外由于技術(shù)設(shè)備原因，三個施工隊施工進度不一樣，A施工隊每天可以施工10公里，B施工隊每天可以施工8公里，C施工隊每天可以施工16公里，每公里施工費用相同。同時，搶修指揮部提出以下幾點要求:(1)保證各鄉(xiāng)鎮(zhèn)之間電網(wǎng)互通;(2)最大程度節(jié)省費用;(3)最快時間完成施工。

1 模型建立與求解

時間和施工成本是兩個重要的影響因素，在實現(xiàn)各個鄉(xiāng)鎮(zhèn)電網(wǎng)互通的目標(biāo)下，用最短的時間完成施工、施工成本最低，是實現(xiàn)優(yōu)化的最終目標(biāo)。依據(jù)這兩個重要因素，我們對該問題進行如下分析。

(1)三個施工搶修隊分別從A、B、C出發(fā)，完成施工任務(wù)，使各鄉(xiāng)鎮(zhèn)的電網(wǎng)互通。每公里的施工費用相同，施工的總成本受施工路線總長度的影響，而且施工總長度也影響著施工時間，所以，在實現(xiàn)施工時間最短、施工成本最低的目標(biāo)時，施工成本最低目標(biāo)優(yōu)先實現(xiàn)。

(2)施工搶修隊的任務(wù)是實現(xiàn)各鄉(xiāng)鎮(zhèn)電網(wǎng)互通，可以將認為是要求實現(xiàn)將3個大電網(wǎng)供應(yīng)接點和10個鄉(xiāng)鎮(zhèn)互通，由分析(1)可知該問題中施工成本最低這一目標(biāo)優(yōu)先實現(xiàn)，施工成本由施工總長度決定，所以，保證13個節(jié)點互通路線最短就能夠?qū)崿F(xiàn)施工成本最低這一目標(biāo)。

基于以上分析，對該問題建立數(shù)學(xué)模型，并對模型進行求解。

(1)模型的建立:現(xiàn)在把問題一般化，看成單個旅行商問題，設(shè)有13個鄉(xiāng)鎮(zhèn)，把A，B，C也看做鄉(xiāng)鎮(zhèn)，以A，B，C，1，2，…10表示。表示從鄉(xiāng)鎮(zhèn)到鄉(xiāng)鎮(zhèn)的距離，假設(shè)某個施工隊從鄉(xiāng)鎮(zhèn)A出發(fā)到其他每個鄉(xiāng)鎮(zhèn)去一次且僅僅是一次，然后回到鄉(xiāng)鎮(zhèn)A。各鄉(xiāng)鎮(zhèn)之間的距離矩陣如表1。

設(shè)計施工隊如何選擇行走的路線，使總的路程最短?這個問題屬于組合最優(yōu)化問題，用動態(tài)規(guī)劃的遞推方法求解是很方便的。然后類似從B點，C點分別走一遍，算出各自最短路徑，然后取3個當(dāng)中最短的那條。

把A，B，C看成第1，2，3個鄉(xiāng)鎮(zhèn)，其他1，…10個鄉(xiāng)鎮(zhèn)依次往后退，共計13個鄉(xiāng)鎮(zhèn).由于規(guī)定施工隊是從鄉(xiāng)鎮(zhèn)A開始的，設(shè)施工隊走到第i個鄉(xiāng)鎮(zhèn)，記……表示有第1個鄉(xiāng)鎮(zhèn)到第鄉(xiāng)鎮(zhèn)的中間鄉(xiāng)鎮(zhèn)集合。表示到達鄉(xiāng)鎮(zhèn)之前中途所經(jīng)過的鄉(xiāng)鎮(zhèn)的集合，則有因此，可選取作為描述過程的狀態(tài)變量，決策為由一個鄉(xiāng)鎮(zhèn)走到另一個鄉(xiāng)鎮(zhèn)，并定義最優(yōu)值函數(shù)

……

邊界條件為。

(2)模型的求解:我們用floyd算法求出任意兩點之間的最短距離，然后用哈密爾頓算法求出該距離矩陣構(gòu)成的圖中的哈密爾頓圖，如圖2。

那么我們從此圖中可以刪除一個最長的邊32，便找到一個聯(lián)通的路徑，并從余下的樹中A、C兩點處截斷，于是我們得到三段子樹:

①，長度為62。

②，長度為126。

③，長度為56。

從這三個長度我們可以把路徑最長的那段分配給施工速度最快的那個隊，時間為(天)，最短的路段分配給施工最慢的那個隊，時間為(天)，剩下的給另一個施工隊，時間為(天)，則最長的為7.875天，即總施工時間為8天左右。

2 模型評價

本文分析并解決了電力搶修問題，主要優(yōu)點是所用數(shù)學(xué)方法簡單常見，易于求解;但很明顯也存在一些缺點，從結(jié)果中我們很容易看出C施工隊施工了將近8天，而A施工隊只施工了6.2天，這顯然有些不太優(yōu)化，我們可以根據(jù)實際情況把先施工完的那個隊派到施工慢的那些隊要完成的路段上去，這樣可以節(jié)省時間。

參考文獻

[1]\t陳子岐，朱必文，劉峙山.圖論[M].高等教育出版社，1987.

[2]\tRobin J.Wilson.Introduction to graph theory (second edition).1978.

[3]\t趙靜，但琦.數(shù)學(xué)建模與數(shù)學(xué)實驗[M].北京:高等教育出版社，2000．