從圖論角度對布點問題求解

摘 要：在日常生產和生活中，往往有一類問題是關于有限的資源在一定條件下的合理利用問題，且要達到最大的利益或者價值。其中包含站點的位置選址問題，通常我們把這類問題歸納為整數規劃中的最優問題，利用MATLAB軟件我們可以輕松的得到問題的數值解。但對站點的位置選址問題，我們發現利用圖論的理論，從圖論角度進行分析和求解，可以更輕松。

關鍵詞：整數規劃；0-1規劃；圖論；孤立點

中圖分類號：F22 文獻標志碼：A 文章編號：1673-291X（2013）07-0307-02

引言

數學模型（Mathematical Model）是用數學符號對一類實際問題或實際發生的現象的（近似的）描述。數學建模（Mathematical Modeling）則是獲得該模型并對之求解、驗證并得到結論的全過程。數學建模不僅是了解事物的基本規律，而且從應用的觀點來看更重要的是預測和控制所建模的系統行為的強有力的工具[1]。圖論是運籌學的一個重要分支，它是以圖為研究對象，圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點表示事物，用連接兩點間的線表示相應的兩個事物之間具有的特定關系[2～3]。圖論應用領域廣泛，隨著科學技術的發展和計算機的出現與廣泛的應用，圖論的理論得到了進一步的發展。特別是龐大的復雜系統工程和管理問題都可以轉換成圖的問題，從而可以解決很多工程設計和管理決策中的最優化問題。在本文中，我們引入下述兩個案例：救護站的選址問題和消防站選址問題[4～5]，應用圖論理論，根據實際問題的要求，在布點選址過程中不應該出現孤立點的結點，可以得到更簡單的解決思路和方法。

一、問題簡述

問題1：救護站的選址問題

某市有8個行政區，各區之間的救護車輛的行車時間（單位：min）（如表1所示）。市政府擬在市區內建立公共救護中

表1 各區之間的行車時間表

心，設計要求從各區到救護中心的行車路線都不超過10min。該市政府請你提供可行的設計方案：全市至少要建幾個救護中心，具體建立在哪個區？

問題2：消防站的選址問題

某城市的消防總部將全市劃分為11個防火區，現有4個消防站，圖1給出的是該城市防火區域和消防站的位置示意。其中①，②，③，④表示消防站，1，2，…，11表示防火區域。根據歷史的資料證實，各消防站的可在事先規定允許的時間內對所負責的區域火災予以撲滅，圖中虛線即表示各地區有那個消防站負責，沒有虛線連接的表示不負責?，F在總部提出：能否減少消防站的數目，仍能保證負責各地區的防火任務？如果可以的話，應當關閉那個？

圖1 各城區和消防站示意圖

二、救護站選址問題的分析與解決

對于問題1，我們通過各區之間的行車時間表數據建立各區之間的交通圖，在該圖中，我們過濾行車時間超過10分鐘的數據，得到下頁圖2：各區之間不超過10分鐘的交通圖。

圖2 各區之間不超過10分鐘的的交通圖

由于設置公共救護中心的宗旨是各區都應該能夠救護到，且救護時間不超過10分鐘，因此如果我們建立去掉某個區域的子圖，子圖中應該沒有孤立點，這樣就可以判定該區域是否應該保留。通過對圖2去掉區域1，建立相應的子圖，我們可以發現區域1去掉后，會有2、7兩個區域形成孤立點，因此1區域應該建立公共救護中心，它解決了1、2、7區域的救護問題。而對3、4、5、6、8號區域進行分析，可以發現8號區域只和6號區域連通，去掉6號區域，8號區域將成為孤立點，而去掉其他各點都不會形成孤立點。因此分析可以得到：該問題最少要建立兩個救護站，分別在1、6號區域設立公共救護站，就可以覆蓋8個區域，實現公共救護問題。

三、消防站問題的分析與解決

在這個問題中，①，②，③，④四個消防站負責11個消防區域，現在的問題是能否減少消防站的數目，仍能保證各地區的防火任務？和上個問題的解決思路是一致的。如果我們建立去掉某個消防站的子圖，那么根據消防的宗旨，應該在相應的子圖中沒有孤立點。當我們去掉①號消防站后，可以發現3號區域成為孤立點；當我們去掉③號消防站后，可以發現5號區域成為孤立點；當我們去掉④號消防站后，可以發現10號區域成為孤立點。唯有在去掉②號消防站后，沒有孤立點的形成。因此②號消防站屬于重復建設，可以去掉，并且對全市的消防安全沒有影響。圖3是去掉①號消防站，3號區域變成孤立點的示意圖。

圖3 去掉①號消防站的示意圖

四、歸納總結

如何在條件允許的范圍內，盡可能地找出一個“最好”的辦法，把需要的事情做好始終是運籌學的中心問題 [5～6]。隨著運籌學的分支越來越細密，理論方法越來越完善，研究領域越來越廣泛，運籌學的實際意義也越來越凸顯[7～8]。從不同的方法在解決同一個問題的靈活性上，我們可以看出運籌學中方法的多樣性。也同時給我們提示：從不同的角度看問題、用不同的方法解決問題可能會使問題的解決得到事半功倍的效果。在本文中我們通過圖論簡單的理論，解決了布點問題。但是盡管本文提供了一種思想，但對于復雜情況下的布點情況沒有進行進一步的分析，沒有給出進一步的系統理論。因此我們有待于進一步進行研究，以期給出更好的結果。

參考文獻：

[1] 葉其孝.數學建模教學活動與大學生教育改革[J].數學的實踐與認識，1997，（1）：192-196.

[2] 姜啟源，謝金星，葉俊.數學模型：第3版[M].北京：高等教育出版社，2003.

[3] 韓中庚，郭曉麗，杜劍平，等.實用運籌學模型、方法與計算[M].北京：清華大學出版社，2007.

[4] 劉鑫，鄧曉莉.0-1整數規劃在消防特勤站選址上的應用[J].消防技術與產品信息，2010，（6）：16-18.

[5] 李衛國.線性規劃中圖解法的最優解問題[J].長春理工大學學報，2010，（4）：178-179.

[6] 單泠，許亞丹.抓好數學建模教學，激發學生創新思維[J]，中國高等教育：半月刊，2001，（15-16）：54-55.

[7] 胡云權，郭耀煌.運籌學教程：第2版[M].北京：清華大學出版社，2003.

[8] Frank R.Giordano William P.Fox Steven B.Horton Maurice D.Weir 數學模型[M].葉其孝，姜啟源，譯.北京：機械工業出版社，2010：4.

Site Location Problem Solving from the Angle of Graph Theory

CHEN Hui，LI Jin-na

（Department of the Fundamentals，Yantai Vocational College，Yantai 264670，China）

Abstract：In daily production process and life，there is often existing a kind of problem concerning the total utilization of limited resources under certain conditions，and to achieve maximum benefit or value，which contains the location of the site location problem.We usually sum up this type of problem for the integer programming optimization ones.By using software MATLAB we can easily get the numerical solution.But for the location of the site location problem，we found it can be more easily that analyzing and solving from the graph theory angle，and by using graph theory.

Key words：Integer Linear Programming；0-1 integer programming；graph；isolated points[責任編輯 陳 鶴]