姚益新

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

基于MATLAB的設(shè)施選址0-1規(guī)劃的實(shí)現(xiàn)

姚益新

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

設(shè)施選址問題由于涉及的因素紛繁復(fù)雜，造成其求解的難度也一直很大。針對這個問題，本文使用matlab軟件對采用0-1規(guī)劃的設(shè)施選址問題進(jìn)行了解答，并進(jìn)行了實(shí)例的論證，結(jié)果表明在使用matlab對0-1規(guī)劃的設(shè)施選址問題進(jìn)行解答時(shí)，具有調(diào)用函數(shù)簡單，求解方便等優(yōu)點(diǎn)。

設(shè)施選址；0-1規(guī)劃；matlab

一、前言

選址作為企業(yè)活動中最重要的長期決策之一，選址的好壞將對服務(wù)方式、服務(wù)質(zhì)量、服務(wù)效率、服務(wù)成本等造成直接的影響，進(jìn)而影響到企業(yè)利潤及其市場競爭力。而設(shè)施選址作為眾多選址問題的一個重要研究領(lǐng)域，更是關(guān)系到經(jīng)濟(jì)、政治、文化、社會、生態(tài)等各個社會方面，是一項(xiàng)綜合的系統(tǒng)工程，在當(dāng)前將建設(shè)資源節(jié)約型、環(huán)境友好型社會作為加快轉(zhuǎn)變經(jīng)濟(jì)發(fā)展方式的重要著力點(diǎn)的時(shí)代背景下，其研究無疑具有重大現(xiàn)實(shí)意義[1]。設(shè)施選址規(guī)劃的研究方法主要依靠運(yùn)籌學(xué)、拓?fù)鋵W(xué)、管理學(xué)等計(jì)量方法，這是設(shè)施選址與其他選址問題的重要區(qū)別[2]。在選址問題的討論時(shí)，涉及到從多個地址中選擇適當(dāng)?shù)膫€數(shù)和地點(diǎn)進(jìn)行選址的問題，此時(shí)通常采用0-1規(guī)劃來實(shí)現(xiàn)[3]。

二、選址0-1規(guī)劃模型

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

0-1規(guī)劃的基本數(shù)學(xué)模型為

(1)

三、0-1規(guī)劃的MATLAB實(shí)現(xiàn)

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

在MATLAB中編程實(shí)現(xiàn)的枚舉法法函數(shù)為：ZeroOneprog。功能為用枚舉法(包括窮舉法和隱枚舉法)求解0-1規(guī)劃。其調(diào)用格式為：

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

其中，c：目標(biāo)函數(shù)系數(shù)向量；

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

x0：初始可行整數(shù)解；

intx：目標(biāo)函數(shù)取最小值時(shí)的自變量值；

intf：目標(biāo)函數(shù)的最小值。

四、實(shí)例分析

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

表1 各位置建設(shè)物流配送中心的費(fèi)用及所能覆蓋的社區(qū)

表2 各社區(qū)的人口數(shù)量

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

(一)模型的假設(shè)。

假設(shè)一：各社區(qū)人口數(shù)量不發(fā)生變化；

假設(shè)二：各社區(qū)內(nèi)居民對物流配送中心的使用率相同，均為α；

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

假設(shè)四：各物流配送中心不會重復(fù)建設(shè)；

假設(shè)五：各物流配送中心的重復(fù)覆蓋不對配送服務(wù)的質(zhì)量造成影響；

(二)符號說明。

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

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

M：物流配送中心的建設(shè)總成本；

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

(三)模型準(zhǔn)備。

根據(jù)表1和表2中的信息，我們可以將所有社區(qū)對應(yīng)的物流配送中心的位置情況統(tǒng)計(jì)如表3所示：

表3 各個社區(qū)對應(yīng)的物流配送中心的位置情況

(四)建立模型。

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

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

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

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)

約束條件為：建設(shè)物流配送中心的費(fèi)用不超過5000萬元的預(yù)算，表達(dá)式如下：

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

(3)

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

(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)

(五)模型解答。

代入原模型，可將上述模型轉(zhuǎn)換為：

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)

所得結(jié)果為

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

由計(jì)算結(jié)果可知，當(dāng)選擇在2，4，6，7號位置建設(shè)物流配送中心時(shí)，可以達(dá)到覆蓋人口最多的目標(biāo)。在這種方案下，建設(shè)物流配送中心總費(fèi)用為7+14+13+11=45(百萬元)，覆蓋2，3，5，6，7，8，9，10，11，12，13，14，15社區(qū)，總?cè)丝跒?09.5千人。

五、總結(jié)

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

[1]萬波.公共服務(wù)設(shè)施選址問題研究[D].華中科技大學(xué),2012.

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

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

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

[5]管志忠,呂楠.0-1線性規(guī)劃模型的MATLAB實(shí)現(xiàn)及應(yīng)用[J].徐州工程學(xué)院學(xué)報(bào).2007(12):64-67

0221.1

A

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

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