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

關(guān)鍵詞：整數(shù)規(guī)劃；0-1規(guī)劃；圖論；孤立點(diǎn)

中圖分類號：F22 文獻(xiàn)標(biāo)志碼：A 文章編號：1673-291X（2013）07-0307-02

引言

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

一、問題簡述

問題1：救護(hù)站的選址問題

某市有8個(gè)行政區(qū)，各區(qū)之間的救護(hù)車輛的行車時(shí)間（單位：min）（如表1所示）。市政府?dāng)M在市區(qū)內(nèi)建立公共救護(hù)中

表1 各區(qū)之間的行車時(shí)間表

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

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

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

圖1 各城區(qū)和消防站示意圖

二、救護(hù)站選址問題的分析與解決

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

圖2 各區(qū)之間不超過10分鐘的的交通圖

由于設(shè)置公共救護(hù)中心的宗旨是各區(qū)都應(yīng)該能夠救護(hù)到，且救護(hù)時(shí)間不超過10分鐘，因此如果我們建立去掉某個(gè)區(qū)域的子圖，子圖中應(yīng)該沒有孤立點(diǎn)，這樣就可以判定該區(qū)域是否應(yīng)該保留。通過對圖2去掉區(qū)域1，建立相應(yīng)的子圖，我們可以發(fā)現(xiàn)區(qū)域1去掉后，會有2、7兩個(gè)區(qū)域形成孤立點(diǎn)，因此1區(qū)域應(yīng)該建立公共救護(hù)中心，它解決了1、2、7區(qū)域的救護(hù)問題。而對3、4、5、6、8號區(qū)域進(jìn)行分析，可以發(fā)現(xiàn)8號區(qū)域只和6號區(qū)域連通，去掉6號區(qū)域，8號區(qū)域?qū)⒊蔀楣铝Ⅻc(diǎn)，而去掉其他各點(diǎn)都不會形成孤立點(diǎn)。因此分析可以得到：該問題最少要建立兩個(gè)救護(hù)站，分別在1、6號區(qū)域設(shè)立公共救護(hù)站，就可以覆蓋8個(gè)區(qū)域，實(shí)現(xiàn)公共救護(hù)問題。

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

在這個(gè)問題中，①，②，③，④四個(gè)消防站負(fù)責(zé)11個(gè)消防區(qū)域，現(xiàn)在的問題是能否減少消防站的數(shù)目，仍能保證各地區(qū)的防火任務(wù)？和上個(gè)問題的解決思路是一致的。如果我們建立去掉某個(gè)消防站的子圖，那么根據(jù)消防的宗旨，應(yīng)該在相應(yīng)的子圖中沒有孤立點(diǎn)。當(dāng)我們?nèi)サ簪偬栂勒竞螅梢园l(fā)現(xiàn)3號區(qū)域成為孤立點(diǎn)；當(dāng)我們?nèi)サ簪厶栂勒竞螅梢园l(fā)現(xiàn)5號區(qū)域成為孤立點(diǎn)；當(dāng)我們?nèi)サ簪芴栂勒竞?，可以發(fā)現(xiàn)10號區(qū)域成為孤立點(diǎn)。唯有在去掉②號消防站后，沒有孤立點(diǎn)的形成。因此②號消防站屬于重復(fù)建設(shè)，可以去掉，并且對全市的消防安全沒有影響。圖3是去掉①號消防站，3號區(qū)域變成孤立點(diǎn)的示意圖。

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

四、歸納總結(jié)

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

參考文獻(xiàn)：

[1] 葉其孝.數(shù)學(xué)建模教學(xué)活動(dòng)與大學(xué)生教育改革[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，1997，（1）：192-196.

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

[3] 韓中庚，郭曉麗，杜劍平，等.實(shí)用運(yùn)籌學(xué)模型、方法與計(jì)算[M].北京：清華大學(xué)出版社，2007.

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

[5] 李衛(wèi)國.線性規(guī)劃中圖解法的最優(yōu)解問題[J].長春理工大學(xué)學(xué)報(bào)，2010，（4）：178-179.

[6] 單泠，許亞丹.抓好數(shù)學(xué)建模教學(xué)，激發(fā)學(xué)生創(chuàng)新思維[J]，中國高等教育：半月刊，2001，（15-16）：54-55.

[7] 胡云權(quán)，郭耀煌.運(yùn)籌學(xué)教程：第2版[M].北京：清華大學(xué)出版社，2003.

[8] Frank R.Giordano William P.Fox Steven B.Horton Maurice D.Weir 數(shù)學(xué)模型[M].葉其孝，姜啟源，譯.北京：機(jī)械工業(yè)出版社，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[責(zé)任編輯 陳 鶴]