基于MATLAB的設施選址0-1規劃的實現

姚益新

(華北電力大學，北京 102206)

基于MATLAB的設施選址0-1規劃的實現

姚益新

(華北電力大學，北京 102206)

設施選址問題由于涉及的因素紛繁復雜，造成其求解的難度也一直很大。針對這個問題，本文使用matlab軟件對采用0-1規劃的設施選址問題進行了解答，并進行了實例的論證，結果表明在使用matlab對0-1規劃的設施選址問題進行解答時，具有調用函數簡單，求解方便等優點。

設施選址；0-1規劃；matlab

一、前言

選址作為企業活動中最重要的長期決策之一，選址的好壞將對服務方式、服務質量、服務效率、服務成本等造成直接的影響，進而影響到企業利潤及其市場競爭力。而設施選址作為眾多選址問題的一個重要研究領域，更是關系到經濟、政治、文化、社會、生態等各個社會方面，是一項綜合的系統工程，在當前將建設資源節約型、環境友好型社會作為加快轉變經濟發展方式的重要著力點的時代背景下，其研究無疑具有重大現實意義[1]。設施選址規劃的研究方法主要依靠運籌學、拓撲學、管理學等計量方法，這是設施選址與其他選址問題的重要區別[2]。在選址問題的討論時，涉及到從多個地址中選擇適當的個數和地點進行選址的問題，此時通常采用0-1規劃來實現[3]。

二、選址0-1規劃模型

0-1規劃是決策變量僅取值0或1的一種特殊的整數規劃。0-1變量可以數量化地描述諸如開與關、取與棄、有與無等現象所反映的離散變量間的邏輯關系、順序關系以及互斥的約束條件，因此0-1規劃非常適合用來解決如線路設計、工廠選址、生產計劃安排等人們所關心的多種問題[4]。

0-1規劃的基本數學模型為

(1)

三、0-1規劃的MATLAB實現

在MATLAB中由于自變量的取值非常有限，因此如果自變量個數不多的話，完全可用窮舉法得到最優解。對于自變量個數比較多的情況，可以用隱枚舉法求得最優解。與窮舉法不同的是，隱枚舉法只檢查自變量取值組合的一部分，它通過找到的可行解不斷改進目標值，于是它只檢查優于目標值的取值組合，因此在應用隱枚舉法之前必須先給一個可行解。

在MATLAB中編程實現的枚舉法法函數為：ZeroOneprog。功能為用枚舉法(包括窮舉法和隱枚舉法)求解0-1規劃。其調用格式為：

[intx,intf]=ZeroOneprog(c,A,b,x0)

其中，c：目標函數系數向量；

A：不等式約束右端向量；

x0：初始可行整數解；

intx：目標函數取最小值時的自變量值；

intf：目標函數的最小值。

四、實例分析

某地政府決定計劃投資5000萬在某地區建立物流配送中心。已知該區域有15個社區，并有7個位置可以建設物流配送中心，但是每個配送中心只能覆蓋有限個社區，且由于地理位置、氣候以及交通等因素，每個可選位置建設物流配送中心的費用及覆蓋范圍也各有差異。社區分布及物流配送中心建設點的位置示意圖如圖1所示，每個位置建設物流配送中心的費用以及可以覆蓋的社區如表1所示，每個社區的人口數如表2所示。

表1 各位置建設物流配送中心的費用及所能覆蓋的社區

表2 各社區的人口數量

問題：要求在建設費用不超過5000萬的前提條件下，在7個位置中選擇合適的位置建立物流配送中心，使得使覆蓋的人口盡可能的多；

(一)模型的假設。

假設一：各社區人口數量不發生變化；

假設二：各社區內居民對物流配送中心的使用率相同，均為α；

假設三：若某社區在某物流配送中心的覆蓋范圍之內，那么該社區中所有客戶均被改物流配送中心覆蓋；

假設四：各物流配送中心不會重復建設；

假設五：各物流配送中心的重復覆蓋不對配送服務的質量造成影響；

(二)符號說明。

xi：各物流配送中心的建設情況(xi=1表示第i個物流中心需要建設，xi=0表示第i個物流中心無需建設)；

a：物流配送中心使用率(0

M：物流配送中心的建設總成本；

W：在某建設方案下，物流配送中心覆蓋的等效人口。

(三)模型準備。

根據表1和表2中的信息，我們可以將所有社區對應的物流配送中心的位置情況統計如表3所示：

表3 各個社區對應的物流配送中心的位置情況

(四)建立模型。

對于該案例中的物流配送中心，只有建設和不建設這兩種情況，因此，我們可以采用0-1規劃的思想進行建模。設xi為每一個物流配送中心的建設情況，則有：

其中xi=1表示第i個物流配送中心需要建設，xi=0表示第i個物流配送中心不需要建設。同時需要考慮，同一個社區，有可能有多個物流配送中心覆蓋，如果覆蓋同一社區的物流配送中心都進行了建設之后，那么該社區的人口就會被重復計算。

本案例要求在建設費用不超過5000萬的前提條件下物流配送中心覆蓋的人口最大，那么我們可以根據表1和表2中的數據，將目標函數表述如下：

maxW=2*x1+4*max{x1,x2}+13*x2+6max{x1,x3}9max{x2,x4}+4x4+7.5max{x3,x6}+12.5max{x3,x4,x5}+10max{x4,x5}11max{x3,x6}+6x6+14max{x5,x6,x7}+9x7+3.5x7+6max{x6,x7}

(2)

約束條件為：建設物流配送中心的費用不超過5000萬元的預算，表達式如下：

9.5x1+7x2+19x3+14x4+17.5x5+13x6+11x7≤50

(3)

考慮到物流配送中心需要建設與否，我們有

(4)

最終模型為

maxW=2*x1+4*max{x1,x2}+13*x2+6*max{x1,x3}+9*max{x2,x4}+4*x4+7.5*max{x3,x6}+12.5*max{x3,x4,x5}+10*max{x4,x5}+11*max{x3,x6}+6*x6+14*max{x5,x6,x7}+9*x7+3.5*x7+6*max{x6,x7}

(5)

(五)模型解答。

代入原模型，可將上述模型轉換為：

min=-2*x1-13*x2-4*x4-6*x6-12.5*x7-4*b1-6*b2-9*b3

-18.5*b4-12.5*b5-10*b6-14*b7-6*b8

在MATLAB中輸入下列命令

>>c=[-2;-13;0;-4;0;-6;-12.5;-4;-6;-9;-18.5;-12.5;-10;-14;-6]

>>A=[9.5 7 19 14 17.5 13 11 0 0 0 0 0 0 0;0.5 0.5 0 0 0 0 0-1 0 0 0 0 0 0 0;-1-1 0 0 0 0 0 1 0 0 0 0 0 0 0;0.5 0 0.5 0 0 0 0 0-1 0 0 0 0 0 0;-1 0-1 0 0 0 0 0 1 0 0 0 0 0 0;0 0.5 0 0.5 0 0 0 0 0-1 0 0 0 0 0;0-1 0-1 0 0 0 0 0 1 0 0 0 0 0;0 0 0.5 0 0 0.5 0 0 0 0-1 0 0 0 0;0 0-1 0 0-1 0 0 0 0 1 0 0 0 0;0 0 1/3 1/3 1/3 0 0 0 0 0 0-1 0 0 0;0 0-1-1-1 0 0 0 0 0 0 1 0 0 0;0 0 0 0.5 0.5 0 0 0 0 0 0 0-1 0 0;0 0 0-1-1 0 0 0 0 0 0 0 1 0 0;0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0-1 0;0 0 0 0 0 0.5 0.5 0 0 0 0 0 0 0-1;0 0 0 0 0-1-1 0 0 0 0 0 0 0 1]

>>b=[50;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0];x0=[1;1;1;1;1;1;1;1;1;1;1;1;1;1;1]

>>[intx,intf]=ZeroOneprog(c,A,b,x0)

所得結果為

intx=(0,1,0,1,0,1,1,1,0,1,1,1,1,1,1)

由計算結果可知，當選擇在2，4，6，7號位置建設物流配送中心時，可以達到覆蓋人口最多的目標。在這種方案下，建設物流配送中心總費用為7+14+13+11=45(百萬元)，覆蓋2，3，5，6，7，8，9，10，11，12，13，14，15社區，總人口為109.5千人。

五、總結

本文給出了物流規劃與設計中的0-1整數規劃模型，并通過使用MATLAB來求解。使用0-1整數規劃模型能夠很好的解決在數個備選地址間選擇最優的選址地點的問題，優點是建模中做了適當的抽象化，將較為復雜的問題簡化為數學模型，既找到合理解，又提高運算速度及效率，這對數據的分析是大有裨益的[5]。其具有較強的可操作性和一定的參考價值，得到的結果也較接近實際。缺點在于忽略了某些實際因素的影響，得到的結果與實際結果存在一定的偏差。另外MATLAB在目標函數中取最大值的問題時不能做出準確的闡述，這是一個缺憾。若要解決這個問題可用Linggo軟件來求解，在同一社區，面對同時被多個物流配送中心覆蓋，社區的人口就會被重復計算的問題我們可以用布爾代數的思想來避免這種情況。

[1]萬波.公共服務設施選址問題研究[D].華中科技大學,2012.

[2]劉海龍,李成嚴.物流中心選址方法研究[J].黑龍江科技信息.2010(4s):42-43

[3]丁小東,姚志剛,程高.LINGO語言與0-1混合整數規劃選址模型的再結合[J].物流工程與管理.2009(10):72-75.

[4]沈萍,陳燕,李捷,楊雪君.物流配送中心選址問題的0-1規劃并行算法.計算技術與自動化[J].2012,09(3):80-82

[5]管志忠,呂楠.0-1線性規劃模型的MATLAB實現及應用[J].徐州工程學院學報.2007(12):64-67

0221.1

A

1671-864X(2015)11-0197-02

姚益新(1989-)，男，漢族，江蘇常州，碩士研究生，華北電力大學，物流工程(物流與供應鏈管理)。