供應(yīng)鏈中給定選址數(shù)量的選址模型研究

1、研究與探討供應(yīng)鏈中給定選址數(shù)量鷯遺址模型研究LocationProbleminSupplyChainundertheDeterminedPFacilities朱長(zhǎng)虹韓之俊霍映寶Abstract：Thisarticleisinvolvedinhowtoestablishmathematicalmodelstomakethetotalsupplychaincostsmallerwhenthelocationnumberoffacilitie

2、sisdeterminedWeobtaintwoobjectivefunctionsbysettingsomeparametersOneisestablishedundersinglescenario，anotherisstochasticmodelundermultiscenariosWealsogivetwodiferentmethodsfortwomodels選址在整個(gè)供應(yīng)鏈系統(tǒng)中占有非常重要的地位，主要屬于供應(yīng)鏈戰(zhàn)略管理層的研究

3、問(wèn)題。設(shè)施的選址就是確定設(shè)施的數(shù)量、設(shè)施的容量、設(shè)施的位置及向設(shè)施分配任務(wù)的大小。這里所說(shuō)的設(shè)施，具有廣泛的涵義，它通常是指供應(yīng)鏈中各環(huán)節(jié)的節(jié)點(diǎn)，如制造商、供應(yīng)商、倉(cāng)庫(kù)、配送中心、零售商等。設(shè)施選址與庫(kù)存、運(yùn)輸成本等之間有很大的聯(lián)系。隨著設(shè)施數(shù)量的增加，可以減少運(yùn)輸成本，但是當(dāng)設(shè)施數(shù)量增加到一定時(shí)候，由于單個(gè)訂單的數(shù)量過(guò)小，而增加了運(yùn)貨次數(shù)，也使得運(yùn)輸成本急劇增加，確定設(shè)施的數(shù)量，是選址的重要任務(wù)之一。因此，對(duì)供應(yīng)鏈的問(wèn)題建模求解能得到

4、成本最好的設(shè)施配置和數(shù)量，供應(yīng)鏈中的選址問(wèn)題有很多類型，這里我們來(lái)討論當(dāng)選址數(shù)量固定時(shí)的選址問(wèn)題一P一中值問(wèn)題(P—median)一、P一中值問(wèn)題的模型構(gòu)建1參數(shù)介紹與建模。P一中值(P—median)模型是指在一個(gè)給定數(shù)量和位置的需求集合(如：零售商顧客)和一個(gè)候選設(shè)施位置(如：配送中心設(shè)施)集合下，分別為P個(gè)設(shè)施找到合適的位置，并指派每個(gè)需求點(diǎn)到一個(gè)特定的設(shè)施，使之達(dá)到在零售商和配送中心之間的運(yùn)輸費(fèi)用最低。我們?yōu)镻一中值模型定義了以

5、下的符號(hào)：設(shè)定I=顧客集，用i表示J=潛在設(shè)施集，用j表示參數(shù)h=顧客集iEI的年需求dij=從設(shè)施選址jEJ到顧客iEI的每單位裝運(yùn)成本P=選址設(shè)施的需求數(shù)量決策變量Y—f1，如果在j∈J構(gòu)建設(shè)施1o。否則v—f，如果設(shè)施jEJ服務(wù)于顧客i∈Iij10，否則PMP公式如下：(PMP)ml?！畁lmlze∑∑hd~Y(1)ii1jiJst∑Yij=1ViI(2)jiJY≤XjVi∈I，Vj∈J(3)∑Xj=P(4)Xje0，Il(5)Y

6、≥0Vi∈I，VjEJ(6)目標(biāo)函數(shù)(I)計(jì)算了顧客和他們指定的設(shè)施之間的總加權(quán)需求距離。約束條件(2)要求每個(gè)顧客指派給一個(gè)設(shè)施，約束條件(2)保證每個(gè)顧客只有一個(gè)設(shè)施來(lái)提供相應(yīng)的服務(wù)。約束條件(3)要求指定的設(shè)備是開(kāi)放的。約束條件(4)要求只有P個(gè)設(shè)施是開(kāi)放的。約束條件(5)和(6)要求選址變量是二元的，并且分配變量是非負(fù)的。從上面的公式可以看出，求一個(gè)P一中值問(wèn)題需要解決兩個(gè)方面的問(wèn)題：(1)選擇合適的設(shè)施位置(X變量)。(2)指

7、派客戶到相應(yīng)的設(shè)施中去(Y變量)。一旦設(shè)施的位置確定之后，在確定每個(gè)客戶到不同的設(shè)施中，使費(fèi)用總和最小就十分簡(jiǎn)單了。2對(duì)P一中值模型求解。這些模型大多數(shù)是用拉格朗日松弛算法來(lái)解的，一般是松弛分配約束條件(2)。對(duì)于PMP，拉格朗13子模型是如下的：(PMPLR)maximizeminimizeOXY∑∑hid∑(1一∑Yij)=∑∑ii1JiJii1JiJii1jiJ(hi—dj廣Y2)i(7)iiIstY≤XjVi∈I，Vj∈J(8)

8、Xj=p(9)jiJXjE0，lJVjeI(10)Y≥0Vi∈I，Vj∈I(11)我們限制≥0，因?yàn)槿绻?并且對(duì)于任何j設(shè)YiI_1從來(lái)都不是有利的；因此如果0，設(shè)i=0總是可以得到一個(gè)更嚴(yán)密的約束條件。對(duì)于給定的為了解(PMP—LR)，我們計(jì)算每個(gè)開(kāi)放的設(shè)施的利潤(rùn)(或者對(duì)目標(biāo)函數(shù)的貢獻(xiàn))：i=min0，hidij(12)iEI然后我們?yōu)榫哂凶钚〉膇的P設(shè)施設(shè)定X=1，如果Xi=1并且hidf一0，設(shè)定Yi：1。為了解(PMP—LR)

9、，我們必須把最大化。二、PMP的擴(kuò)展模型隨機(jī)(stochastic)選址問(wèn)題SPMP在以上討論的PMP中，是純粹的以距離為隨機(jī)參數(shù)的成本求和，但是在實(shí)際的供應(yīng)鏈的構(gòu)建中，由于會(huì)出現(xiàn)各種各樣的隨機(jī)情況，我們會(huì)允許模型建立者指定幾個(gè)可能的未來(lái)狀況，或者方案，每個(gè)方案設(shè)立來(lái)自供應(yīng)鏈模型的需求和成本信息，我們把它叫做多方案隨機(jī)環(huán)境。1參數(shù)設(shè)定和SPMP建模。隨機(jī)P一中值模型是在多方案環(huán)境里選擇P設(shè)施和給他們分配零售商使總期望運(yùn)輸成本降到最低的問(wèn)

10、題，以一個(gè)要求最大相對(duì)后悔值不比p大的約束為條件。這個(gè)模型被認(rèn)為是SPMP的變化模型P—SPMP，在這里除了DC一零售商其他所有的運(yùn)輸成本等于0，限制條件放在選址設(shè)施的數(shù)量里。pSPMP如下：(pSPMP)minimize∑∑∑ilBY(13)st_∑Y1Vi∈I，Vs∈SJEIY≤XJVi∈I，Vj∈I，VS∈S∑∑dY≤(1p)ziEIJEI∑x__P】EI(14)(15)(16)(17)Xj0，1VjI(18)Y≥0ViEI，Vj

11、EI，VS∈S(19)2變量分離法求解SPMP建模。我們提出了變量分離法解(P—SPMP)。我們?cè)黾恿艘粋€(gè)變量W，W會(huì)等于Y；當(dāng)約束要求W=Y松弛時(shí)我們很好地得到了分解的公式。(P—SPMP)的變量分離公式如下：(pSPMP—vs)minimizep∑∑sESiEI∑qdY(1—13)∑∑∑jEIsEsiEIjEIq。dY(20)(21)(22)∑∑dW蜘≤(1P)z’(23)i∈1jE1∑Xj=P(24)jEIW=Y(25)XjE0，

12、1Vi∈I(26)Y0，1)Vi∈1，Vj∈1，VS∈S(27)W0，1Vi∈I，VjEI，VS∈S(28)參數(shù)0≤B≤1確保Y和W包含在目標(biāo)函數(shù)中；因?yàn)閅=W，目標(biāo)函數(shù)(20)是和(P—SPMP)一樣的。為了解(P—SPMP—VS)，我們松弛具有拉格朗日乘子的約束條件(21)。注意在這種情形下，是不受限制的符號(hào)。對(duì)于確定的，產(chǎn)生的子模型分解成了一個(gè)XY模型和一個(gè)W模型：XY模型：minimize∑∑∑(Y(21)sESiEIjElst

13、Y≤xjVi∈I，Vj∈I，VS∈S(22)Exj=P(23)JEIXjE0，1VjEI(24)YE0，1Vi∈I，VjEI，VS∈S(25)W模型：minimize∑∑∑【(1一B)w(26)sESiEIiElst∑W：1vi∈I，vs∈S(27)jEI∑∑dw≤(1p)z’Vs∈S(28)iEIiEIW∈0，1Vi∈I，Vj∈I，VS∈S(29)為了解XY模型，我們計(jì)算了開(kāi)放每個(gè)設(shè)施j對(duì)目標(biāo)函數(shù)的貢獻(xiàn)Vj：研究與探討l45Vj=mi

14、n0，13q(30)SiI對(duì)于具有最小V的P設(shè)施，我們?cè)O(shè)X_1，并且，如果X_1并且13qjLd0時(shí)，我們?cè)O(shè)Y=1。W模型簡(jiǎn)化為了多重選擇背包問(wèn)題的ISI實(shí)例，一個(gè)經(jīng)典的背包模型的擴(kuò)展；MCKP問(wèn)題沒(méi)有整數(shù)特性，使得這個(gè)松弛法的約束比從松弛算子(14)和(16)中得到的約束更嚴(yán)密。要么通過(guò)MCKP方法求出最優(yōu)解，要么利用啟發(fā)式選擇一個(gè)最優(yōu)目標(biāo)函數(shù)值作為下界；否則的話，拉格朗日子模型不能保證會(huì)產(chǎn)生下界。如果啟發(fā)式地解模型，變量可以用啟發(fā)解

15、法來(lái)設(shè)定，但是用在次梯度優(yōu)化法中的下界就不會(huì)和拉格朗日子模型的解的真實(shí)值相等。我們已經(jīng)發(fā)現(xiàn)因?yàn)椴幌嗟葘?dǎo)致實(shí)質(zhì)收斂問(wèn)題。更好的方法是利用下界法，而不只是下界本身來(lái)設(shè)定變量。然而，不是所有啟發(fā)式算法都能返回下界解。因此，當(dāng)做使用哪個(gè)MCKP算法和如何設(shè)置變量的決策時(shí)必須十分謹(jǐn)慎。一旦XY問(wèn)題和W問(wèn)題解出來(lái)了，就把兩個(gè)目標(biāo)值加到目標(biāo)函數(shù)(13)得到下界：然后通過(guò)DC(distributioncenters)交換啟發(fā)式求得目標(biāo)函數(shù)的上界。上面討

16、論了P一中值問(wèn)題的兩種情況，一個(gè)單一方案的情況和一個(gè)隨機(jī)(多種)方案的情況，我們?yōu)槠湓O(shè)置了兩個(gè)不同的數(shù)學(xué)模型，并給出了求解模型的拉格朗日法和變量分離法的子模型。并介紹了多重背包法和啟發(fā)式法在求解模型運(yùn)算中的使用。P一中值問(wèn)題一般使用于工廠或者倉(cāng)庫(kù)的選址問(wèn)題，例如，投資者利用有限的資金在某地區(qū)建立P個(gè)工廠或倉(cāng)庫(kù)，要求在他們和零售商或顧客之間的費(fèi)用最小。(作者單位：南京理工大學(xué)經(jīng)濟(jì)管理學(xué)院，南京財(cái)經(jīng)大學(xué)工商管理學(xué)院)SS∈∈VVLLEEVV