隨機(jī)條件下一個(gè)網(wǎng)絡(luò)選址問題的模型及算法

何方國

(黃岡師范學(xué)院 數(shù)理學(xué)院，湖北 黃岡438000)

選址問題是在運(yùn)籌學(xué)和管理科學(xué)領(lǐng)域普遍存在的決策問題，主要研究如何選擇設(shè)施的數(shù)目和最優(yōu)位置來為用戶提供相應(yīng)的服務(wù)。1909 年，WEBER 研究了在平面上確定一個(gè)倉庫的位置使得倉庫與多個(gè)顧客之間的總距離最小的問題，標(biāo)志著選址理論研究的開始。1964 年HAKIMI 提出了網(wǎng)絡(luò)上的p-中值問題，激發(fā)了選址問題的研究，從此該問題的研究開始活躍起來。選址研究中的典型問題，如Weber 問題、中值問題、覆蓋問題、中心問題、多目標(biāo)選址、競爭選址、選址-分配和選址-路線等，都是被廣泛關(guān)注和深入研究的熱點(diǎn)課題，研究結(jié)果也較為成熟［1-2］。筆者以物流網(wǎng)絡(luò)為例討論選址問題。在物流網(wǎng)絡(luò)中，可以用節(jié)點(diǎn)(供貨點(diǎn)、需求點(diǎn))和有向邊(運(yùn)輸路線)構(gòu)成的網(wǎng)絡(luò)或有向圖表示。選址問題是物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的核心，因此相關(guān)研究較多［3-5］。在現(xiàn)有的研究中，絕大部分是在確定性需求條件下構(gòu)造的確定性模型。隨著社會(huì)經(jīng)濟(jì)的發(fā)展及市場競爭環(huán)境的日益復(fù)雜，需求動(dòng)態(tài)變化的特征日益明顯。確定性選址模型不再適應(yīng)動(dòng)態(tài)變化的需求特征，因此能描述需求動(dòng)態(tài)變化特征的不確定性模型就應(yīng)運(yùn)而生。筆者提出了一個(gè)需求與供給不確定的網(wǎng)絡(luò)選址模型，并為求解模型給出了一個(gè)算法。

1 問題的描述與數(shù)學(xué)模型

考慮一個(gè)物流網(wǎng)絡(luò)由m個(gè)分銷點(diǎn)和n個(gè)客戶組成，根據(jù)客戶的需求，貨物從分銷點(diǎn)運(yùn)到需求點(diǎn)。在客戶的需求量和分銷點(diǎn)供貨量呈隨機(jī)需求與供應(yīng)特征的情況下，在給定的m個(gè)候選位置中確定分銷點(diǎn)的個(gè)數(shù)和分銷點(diǎn)的位置，達(dá)到滿足每一個(gè)客戶需求的要求，同時(shí)保證網(wǎng)絡(luò)中所有的費(fèi)用和成本之和達(dá)到最小。為了方便建立數(shù)學(xué)模型，作出以下基本假設(shè)：①各客戶需求量和各分銷點(diǎn)供貨量為隨機(jī)變量，并且服從已知均值和方差的正態(tài)分布。②分銷點(diǎn)的候選位置建設(shè)費(fèi)用已知。③每個(gè)需求點(diǎn)只由一個(gè)分銷點(diǎn)供貨，且總需求不超過分銷點(diǎn)總的供貨能力。其中涉及到的變量定義如下：i為第i個(gè)分銷點(diǎn)，i=1，2，…，m;j為第j個(gè)需求點(diǎn)(客戶)，j=1，2，…，n;di為分銷點(diǎn)i的建設(shè)成本;ξi為分銷點(diǎn)i的供貨能力，ξi～N(μi，);ηj為客戶j的需求量，ηj～N(μ~j，);cij為分銷點(diǎn)i與客戶j之間的單位物流費(fèi);αi為給定的置信水平，或稱滿意率。決策變量包括：

優(yōu)化問題的目標(biāo)函數(shù)為：

其中，第一部分為分銷點(diǎn)與客戶之間的物流費(fèi)用，該費(fèi)用與需求量成正比，第二部分為分銷點(diǎn)的建設(shè)費(fèi)用。由于目標(biāo)函數(shù)含有隨機(jī)變量ηj，按式(1)求Z的最小值是無意義的，因此建立有機(jī)會(huì)約束的期望值模型(模型1)：

模型優(yōu)化的目的是在滿足一系列機(jī)會(huì)約束的前提下使得總費(fèi)用期望值最小。式(3)表示每個(gè)客戶被且只被一個(gè)分銷點(diǎn)服務(wù);式(4)限定與某個(gè)分銷點(diǎn)存在供需關(guān)系的客戶的總需求量不超過該分銷點(diǎn)供貨量的概率大于αi;式(5)表示客戶只能分配給選定的分銷點(diǎn)。這種選址問題具有廣泛的代表性，不僅在物流網(wǎng)絡(luò)而且在通信網(wǎng)絡(luò)及電力網(wǎng)絡(luò)中也有應(yīng)用［6-8］。

2 不確定性模型的轉(zhuǎn)化

不確定性模型轉(zhuǎn)化是一個(gè)隨機(jī)規(guī)劃問題，模型中需求供給滿足正態(tài)分布，該模型可以轉(zhuǎn)化成確定性的等價(jià)模型。

定理1 設(shè)ξi和ηj分別為服從正態(tài)分布且為相互獨(dú)立的隨機(jī)變量，則式(4)有：

證明 令g(x)=∑jηjxij-ξi，顯然g(x)服從正態(tài)分布，且期望和方差分別為E(g(x))=這樣可以得到變量：

η 服從標(biāo)準(zhǔn)正態(tài)分布，因此：

其中，Φ-1為標(biāo)準(zhǔn)正態(tài)分布函數(shù)的逆。假設(shè)機(jī)會(huì)約束有Pr{η1x1+η2x2+η3x3≤ξ}≥0.95 ，其中η1，η2，η3，ξ 分別服從正態(tài)分布N(1，1)，N(2，1)，N(3，1)和N(4，1)。由于Φ-1(0.95)=1.645，則可得其等價(jià)形式為：

式(4)通過等價(jià)變換為確定性的不等式后，仍是一個(gè)非線性優(yōu)化問題。希望通過近似線性化之后變成一個(gè)線性優(yōu)化問題。根據(jù)數(shù)學(xué)歸納法，可以證明下列結(jié)論成立。

定理2 若mi(i= 1，2，…，l)為正數(shù)，則且mi相等時(shí)取等號(hào)。

定理2 表明，當(dāng)mi較小或者是相差不大時(shí)，可以用近似表示而在研究的問題中標(biāo)準(zhǔn)差σi都較小且相差不大，因?yàn)檎Ｇ闆r下需求量不會(huì)有很大的波動(dòng)，實(shí)際上這個(gè)前提比較容易滿足。因此約束適當(dāng)放松成線性約束。這樣把表示成

且滿足式(3)和式(5)。

3 拉格朗日松弛法求解

對(duì)于不同的選址問題有不同算法［9-10］。筆者利用次梯度搜索結(jié)合拉格朗日松弛方法來求解。首先對(duì)限制條件式(3)和式(7)進(jìn)行松弛得到拉格朗日松弛問題，并求解得到原問題的一個(gè)下界ZLB;其次根據(jù)當(dāng)前的可行解得到原問題的一個(gè)上界ZUB;然后利用次梯度法調(diào)整拉格朗日乘子得到原問題的上下界并校正，直到得到一個(gè)可接受的近似解或迭代次數(shù)足夠多則算法停止。解的質(zhì)量由相對(duì)對(duì)偶間隙(ZUB-ZLB)/ZLB來衡量。

通過拉格朗日乘子將約束條件式(3)和式(7)轉(zhuǎn)移到目標(biāo)函數(shù)中。原問題的拉格朗日松弛問題為：

顯然L(λ，γ)是式(6)最優(yōu)值的一個(gè)下界。拉格朗日乘子γi，λj在模型中起到了影子價(jià)格的作用，反映了對(duì)違反供需平衡約束的懲罰。模型經(jīng)過松弛轉(zhuǎn)換后，供需之間的依賴關(guān)系只反映在式(8)中。利用拉格朗日松弛法，可得到式(8)對(duì)偶函數(shù)如下(約束條件相同)：

若令Z*為原問題的最優(yōu)解，則有L(λ，γ)≤D≤Z*。所得的松弛問題與原問題的目標(biāo)函數(shù)比較，松弛問題改變了目標(biāo)函數(shù)中xij的系數(shù)。在最小化松弛問題的過程中，如果xij的系數(shù)足夠小，能夠抵消yi所帶來的目標(biāo)函數(shù)值的上升，則yi=1，否則yi=0。松弛問題的物理意義在于通過拉格朗日乘子建立了需求與建設(shè)成本之間的關(guān)系。如果需求所帶來的費(fèi)用壓力足夠大，就建設(shè)某個(gè)分銷點(diǎn);否則不建設(shè)該分銷點(diǎn)?；谠摲治觯瑢?duì)給定的拉格朗日乘子γi，λj，確定yi，xij的方法(即解松弛問題式(8))如下，令：若Ki＜0，則yi=1，否則yi=0;若yi=1 且Cj＜0，則xij=1，否則xij=0。

因此求解模型2 的整個(gè)算法步驟如下：

(1)設(shè)k=0，選取確定的拉格朗日乘子γi，λj，ZLB= -∞，ZUB= +∞。

(2)求解松弛問題式(8)得到y(tǒng)i，xij，由式(9)計(jì)算得到原問題的一個(gè)下界如果得到的解既滿足可行性條件xij≤yi，又滿足互補(bǔ)松弛性γi(∑Bjxij-Ai)=0，或者說存在一個(gè)次梯度為0，則該解是最優(yōu)解，算法停止;否則校正下界ZLB=

(4)若存在可接受的θ，使得|(ZUB-ZLB)/ZLB| ＜θ，或迭代次數(shù)已經(jīng)達(dá)到了某個(gè)極限，則停止迭代。

(5)利用次梯度算法調(diào)整拉格朗日乘子，其中θk為迭代第k步的步長。

(6)令k=k+1，返回步驟(2)。

4 算法的實(shí)例

給定5 個(gè)可能的分銷點(diǎn)的候選位置，同時(shí)給定10 個(gè)已有的客戶點(diǎn)，即m=5，n=10。假設(shè)每個(gè)客戶只能由一個(gè)分銷點(diǎn)提供服務(wù)，分銷點(diǎn)的供應(yīng)量和客戶的需求量分別服從正態(tài)分布N(μi，σi2)，i=1，2，…，5 和N(μj，σj2)，j=1，2，…，10。設(shè)所有隨機(jī)變量的方差均為1，給定的置信水平(客戶滿意率)均不低于85%。分銷點(diǎn)的建設(shè)成本di(i=1，2，…，5)和單位物流費(fèi)用矩陣Cij(如表1 所示)，μi={42，55，65，60，50};μj={18，23，14，15，20，11，19，10，20，16};di={32，37，29，38，34}。用Matlab 編程實(shí)現(xiàn)拉格朗日松弛算法。計(jì)算時(shí)首先轉(zhuǎn)化成確定性模型，然后轉(zhuǎn)化為整數(shù)線性規(guī)劃。應(yīng)用上述算法得到：yi={0，1，1，0，1}，確定了網(wǎng)絡(luò)選址的位置和數(shù)量;網(wǎng)絡(luò)選址的費(fèi)用和為574。得出的解滿足原問題的約束條件，是原問題的可行解，同時(shí)也是原問題的近似最優(yōu)解。此時(shí)xij為：x23=x26=x28=x29=x32=x35=x37=x51=x54=x5，10=1，其余為0。

表1 供貨點(diǎn)i 到需求點(diǎn)j 的單位物流費(fèi)用

5 結(jié)論

筆者對(duì)不確定的供需物流網(wǎng)絡(luò)優(yōu)化問題進(jìn)行了研究，按照成本最低化原則，給出了包含不確定參數(shù)的選址數(shù)學(xué)模型。當(dāng)產(chǎn)品的供應(yīng)量和需求量均滿足正態(tài)分布時(shí)，以隨機(jī)理論為基礎(chǔ)，證明了在正態(tài)分布的情況下，該問題的數(shù)學(xué)模型可以轉(zhuǎn)化為確定性的數(shù)學(xué)模型。采用拉格朗日松弛算法對(duì)系統(tǒng)費(fèi)用進(jìn)行優(yōu)化。通過將原問題簡化，把一個(gè)非線性優(yōu)化問題簡化為線性問題進(jìn)行求解，然后利用次梯度搜索結(jié)合拉格朗日松弛方法來求解，獲得總費(fèi)用最小的分銷點(diǎn)數(shù)量和位置的選擇方案，以及分銷點(diǎn)與客戶之間的供需關(guān)系。實(shí)例數(shù)值結(jié)果證明了該模型和算法的有效性。

［1］王非，徐渝.離散設(shè)施選址問題研究綜述［J］. 運(yùn)籌與管理，2006，15(5)：64 -68.

［2］王丹，馬云峰. 競爭與合作設(shè)施并存的最大覆蓋選址問題［J］. 武漢理工大學(xué)學(xué)報(bào)：信息與管理工程版，2010，32(4)：628 -630.

［3］楊豐梅，華國偉.選址問題研究的若干進(jìn)展［J］. 運(yùn)籌與管理，2005，14(6)：1 -6.

［4］蔣利軍，蔣明，趙正佳.配送中心選址問題研究文獻(xiàn)綜述［J］.物流科技，2008(4)：31 -33.

［5］萬波.基于層級(jí)模型的嵌套型公共設(shè)施選址問題研究［J］. 武漢理工大學(xué)學(xué)報(bào)：信息與管理工程版，2012，32(2)：218 -222.

［6］呂靜，樊鎖海.會(huì)議選址問題的優(yōu)化模型［J］. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41(3)：141 -149.

［7］FARAHANI R Z.Multiple criteria facility location problems：a survey［J］.Applied Mathematical Modelling，2010(6)：1689-1709.

［8］ANDREAS K.Facility location models for distribution system design［J］. European Journal of Operational Research，2005，162(1)：4 -29.

［9］朱思峰.多目標(biāo)優(yōu)化量子免疫算法求解基站選址問題［J］.華中科技大學(xué)學(xué)報(bào)，2012，40(1)：49 -53.

［10］沈萍，陳燕.物流配送中心選址問題的0 -1 規(guī)劃并行算法［J］. 計(jì)算技術(shù)與自動(dòng)化，2012，31(3)：131 -133.