生產(chǎn)與分銷聯(lián)合決策的雙層機(jī)會(huì)約束規(guī)劃問(wèn)題研究

周夢(mèng)瑩

摘 要：生產(chǎn)與分銷的決策在供應(yīng)鏈中是非常關(guān)鍵的。目前很多企業(yè)在進(jìn)行決策時(shí)，沒(méi)有考慮到生產(chǎn)與分銷的關(guān)系以及供應(yīng)鏈系統(tǒng)的不確定性。文章考慮在不確定生產(chǎn)與隨機(jī)需求條件下，如何將生產(chǎn)與分銷進(jìn)行聯(lián)動(dòng)決策的問(wèn)題。建立了一個(gè)包含隨機(jī)變量的雙層機(jī)會(huì)約束規(guī)劃模型，將分銷與生產(chǎn)的決策模型分別作為上下層，且雙層都以成本最小化為目標(biāo)函數(shù)。進(jìn)而利用確定性等價(jià)類方法、Monte Carlo隨機(jī)模擬以及改進(jìn)的遺傳算法解文中模型。然后，利用算例來(lái)驗(yàn)證模型與算法的有效性。

關(guān)鍵詞：生產(chǎn)分銷決策；雙層規(guī)劃；機(jī)會(huì)約束規(guī)劃；Monte Carlo模擬；遺傳算法

中圖分類號(hào)：F273.7 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： Production and distribution decisions are very crucial in the supply chain. Many companies in the decision-making of production and distribution do not take into account the connection between the two and the uncertainty in supply chain presently. In this paper， we focus on how to make the decision of production and distribution jointly under the condition of uncertain production and stochastic demand. A bilevel chance-constrained programming model with random variables is established to minimize the cost， which includes upper-level distribution decision and lower-level production decision. Then solve the model by deterministic equivalent method， Monte Carlo method and improved genetic algorithm. An example is given to validate the validity of the model and algorithm in this paper.

Key words： production and distribution decision；bilevel programming； chance-constrained programming；Monte Carlo method；genetic algorithm

0 引 言

大多數(shù)的生產(chǎn)和消費(fèi)者需求都面臨很多不確定因素。一方面，產(chǎn)品的生產(chǎn)是不穩(wěn)定的，當(dāng)原材料、機(jī)器設(shè)備、勞動(dòng)力和廠內(nèi)運(yùn)作等因素發(fā)生變動(dòng)，就會(huì)導(dǎo)致生產(chǎn)不能按原計(jì)劃進(jìn)行；另一方面，市場(chǎng)對(duì)于產(chǎn)品的需求是不確定的，受到消費(fèi)者偏好、競(jìng)爭(zhēng)產(chǎn)品情況、市場(chǎng)變化以及消費(fèi)者收入等因素的影響。由于市場(chǎng)需求和供應(yīng)鏈上游產(chǎn)品生產(chǎn)的不確定性，制定合理的分銷策略是非常重要的。分銷決策受到生產(chǎn)端與需求端的共同影響，市場(chǎng)需求影響到產(chǎn)品生產(chǎn)計(jì)劃的制定，而分銷決策能分配的產(chǎn)品量受到產(chǎn)品總生產(chǎn)量的影響。一個(gè)有效的分銷決策應(yīng)盡可能地與各市場(chǎng)需求相匹配，在不能完全匹配時(shí)，應(yīng)使總損失最小。因此，要制定一個(gè)合理有效的分銷策略，必須考慮到工廠生產(chǎn)量與市場(chǎng)需求量的不確定性。基于以上，本文考慮在不確定生產(chǎn)與隨機(jī)需求的前提下，以費(fèi)用最小為目標(biāo)，將分銷與生產(chǎn)進(jìn)行聯(lián)合決策。

該問(wèn)題可以看成一個(gè)雙層規(guī)劃問(wèn)題（Bilevel Programming Problem， BLPP）。雙層規(guī)劃是包含有主從遞階關(guān)系的優(yōu)化問(wèn)題[1]。在雙層規(guī)劃中，下層決策在已知上層決策結(jié)果來(lái)進(jìn)行自己的決策，而上層決策基于下層決策可能的反應(yīng)來(lái)優(yōu)化自己的目標(biāo)函

數(shù)[2]。斯塔克爾伯格模型是關(guān)于企業(yè)競(jìng)爭(zhēng)的模型，它可以被認(rèn)為是雙層規(guī)劃的雛形，由德國(guó)經(jīng)濟(jì)學(xué)家Stackelberg提出[3]。Bracken[4]等人首次提出雙層規(guī)劃數(shù)學(xué)模型。雙層規(guī)劃比較符合很多現(xiàn)實(shí)問(wèn)題，在現(xiàn)實(shí)中得到很多應(yīng)用，例如交通規(guī)劃領(lǐng)域[5]和供應(yīng)鏈選址[6]。雙層規(guī)劃的求解困難，即便是線性雙層規(guī)劃問(wèn)題，也是強(qiáng)NP難的[7]。國(guó)內(nèi)外已有大量求解雙層規(guī)劃問(wèn)題的方法，如下降方向法[8]、分支定界法[9]和罰函數(shù)法[10]。大多數(shù)的精確算法都針對(duì)具有某些特點(diǎn)的雙層規(guī)劃問(wèn)題，如基于模型目標(biāo)函數(shù)的可微性、凸性等條件進(jìn)行求解。同時(shí)也有一些啟發(fā)式算法，如Mathieu等人提出了解線性雙層規(guī)劃的遺傳算法[11]。

在研究生產(chǎn)與分銷聯(lián)合決策時(shí)，生產(chǎn)端與分銷端都以各自成本最小化作為目標(biāo)函數(shù)，以期做出對(duì)自己最有利的決策。而由于最大生產(chǎn)能力與市場(chǎng)需求的隨機(jī)性，與隨機(jī)量相關(guān)的約束條件不一定能被滿足。由Cooper和Charnes提出的機(jī)會(huì)約束規(guī)劃理論能解決該問(wèn)題，它指在模型含有隨機(jī)變量且必須在確定隨機(jī)變量的實(shí)驗(yàn)值前做出相關(guān)決策，且約束條件有可能不被滿足。因此機(jī)會(huì)約束規(guī)劃模型的意義是，決策者所做出的決策在特定概率內(nèi)不需要滿足約束，但所做出的決策要使得約束在一定概率上成立[12]。求解機(jī)會(huì)約束規(guī)劃主要包含兩種：其一，轉(zhuǎn)換為確定性等價(jià)類，再進(jìn)行求解；其二，利用蒙特卡羅隨機(jī)模擬的方法求解[13]。此外，也有一些關(guān)于機(jī)會(huì)約束規(guī)劃求解的智能算法。

1 問(wèn)題與模型

1.1 問(wèn)題描述

該問(wèn)題考慮的是在某一周期內(nèi)、某一種產(chǎn)品的供應(yīng)鏈中生產(chǎn)分銷決策優(yōu)化問(wèn)題，包括生產(chǎn)與分銷兩端，生產(chǎn)指的是工廠，分銷包括分銷中心和市場(chǎng)。產(chǎn)品從工廠流向分銷中心，又從分銷中心流向市場(chǎng)，其中，各個(gè)工廠所有的生產(chǎn)量全部流向分銷中心。分銷端以分銷中心和市場(chǎng)的總費(fèi)用最小化為目標(biāo)，而生產(chǎn)端以工廠的總費(fèi)用最小化為目標(biāo)。以分銷端為上層，生產(chǎn)端為下層構(gòu)成雙層規(guī)劃問(wèn)題。在計(jì)算費(fèi)用時(shí)，分銷端的費(fèi)用除了實(shí)際成本支出以外還需考慮缺貨成本與多余庫(kù)存成本，而從工廠流向分銷中心的費(fèi)用由兩方分?jǐn)?，同時(shí)假設(shè)分銷中心的相關(guān)運(yùn)作費(fèi)用為零。還有一點(diǎn)值得注意，即各工廠的最大生產(chǎn)能力與各市場(chǎng)的需求量均為隨機(jī)變量。該問(wèn)題中生產(chǎn)與分銷系統(tǒng)結(jié)構(gòu)如圖1所示：endprint

1.2 模型參數(shù)

為了刻畫(huà)和研究該生產(chǎn)與分銷聯(lián)合決策問(wèn)題，設(shè)計(jì)了相關(guān)參數(shù)。本文研究問(wèn)題所涉及的參數(shù)包含集合、一般參數(shù)、隨機(jī)變量和決策變量4種。集合指的是工廠、分銷中心與市場(chǎng)的集合；一般參數(shù)指描述該問(wèn)題特征與性質(zhì)的數(shù)量，如單位可變成本；隨機(jī)變量是指變量的值無(wú)法在實(shí)驗(yàn)之前確定的量，如市場(chǎng)需求；決策變量是指可由決策者調(diào)整數(shù)值使目標(biāo)函數(shù)盡可能優(yōu)的變量，如從分銷中心到各市場(chǎng)的分配量。具體參數(shù)如下：

1.3 模型建立

模型上層是以x為決策變量的分銷決策，下層是以q為決策變量的生產(chǎn)決策；對(duì)于每一個(gè)上層決策x，都有一個(gè)對(duì)應(yīng)的下層決策q，而q的值反過(guò)來(lái)又影響上層決策x的解，進(jìn)而影響目標(biāo)函數(shù)值。模型相關(guān)表達(dá)式含義如表1所示：

2 模型求解

2.1 算法流程

本文模型的求解思路是：對(duì)每一個(gè)給定的上層決策變量x，都要求解下層決策變量q，進(jìn)而求解上層目標(biāo)函數(shù)值，多次調(diào)整x并求解q，使目標(biāo)函數(shù)盡可能大。求解的難度在于對(duì)應(yīng)每一個(gè)x，都要求解一個(gè)q，即需要將下層規(guī)劃求解嵌套在上層規(guī)劃求解中。本文采用改進(jìn)后的遺傳算法求解，并將下層線性規(guī)劃嵌套在上層規(guī)劃求解中。

本文算法與一般遺傳算法主要有兩點(diǎn)區(qū)別：其一，針對(duì)雙層規(guī)劃問(wèn)題，上層計(jì)算個(gè)體適應(yīng)度函數(shù)前，都需要計(jì)算一次下層線性規(guī)劃模型，即將下層規(guī)劃嵌套在上層目標(biāo)函數(shù)求解中；其二，針對(duì)目標(biāo)函數(shù)含有隨機(jī)變量這一特點(diǎn)，采用Monte Carlo隨機(jī)模擬方法計(jì)算個(gè)體適應(yīng)度函數(shù)。算法流程圖見(jiàn)圖2。

2.2 隨機(jī)模擬計(jì)算適應(yīng)度函數(shù)

2.3 算法具體步驟

步驟1：生成初始種群，設(shè)置算法參數(shù)；

步驟2：將上層目標(biāo)函數(shù)設(shè)為適應(yīng)度函數(shù)；

步驟3：對(duì)初始種群個(gè)體求對(duì)應(yīng)的下層生產(chǎn)決策，得到下層決策的最優(yōu)解；

步驟4：進(jìn)而利用隨機(jī)模擬方法，結(jié)合步驟3得到的每一個(gè)個(gè)體對(duì)應(yīng)的下層最優(yōu)解，求得個(gè)體的適應(yīng)度函數(shù)；

步驟5：進(jìn)行選擇、交叉和變異操作；

步驟6：判斷是否達(dá)到算法終止條件，達(dá)到則執(zhí)行步驟7，未達(dá)到則返回步驟3；

步驟7：計(jì)算終止，輸出最優(yōu)的生產(chǎn)分銷決策方案。

3 算例分析

4 結(jié)束語(yǔ)

本文研究了在不確定生產(chǎn)與隨機(jī)需求的條件下，如何將分銷端的決策與生產(chǎn)端的決策進(jìn)行聯(lián)合決策的問(wèn)題。在分銷端，同時(shí)考慮到各個(gè)市場(chǎng)的缺貨成本與多余庫(kù)存成本，使對(duì)問(wèn)題的研究更加貼近現(xiàn)實(shí)。但本文研究也存在一些不夠深入的地方，例如文中對(duì)工廠的選擇進(jìn)行無(wú)差別處理，沒(méi)有考慮到工廠的其它指標(biāo)對(duì)工廠選擇的影響。這在作者后續(xù)研究中會(huì)進(jìn)一步展開(kāi)。

參考文獻(xiàn)：

[1] Dempe S. Foundations of bilevel programming[M]. Dordrecht： Kluwer Academic Publishers， 2002：2-15.

[2] 李相勇，田澎. 雙層規(guī)劃問(wèn)題的粒子群算法研究[J]. 管理科學(xué)學(xué)報(bào)，2008，11（5）：41-52.

[3] Stackelberg H V， Peacock A T. The theory of the market economy[J]. Economica， 1952，80（20）：384.

[4] Bracken J， Falk J E， Mcgill J T. The Equivalence of Two Mathematical Programs with Optimization Problems in the Constraints[J]. Operations Research， 1974，22（5）：1102-1104.

[5] Migdalas A. Bilevel programming in traffic planning： Models， methods and challenge[J]. Journal of Global Optimization， 1995，7（4）：381-405.

[6] 高國(guó)飛，張星臣，徐彬，等. 雙層規(guī)劃模型在供應(yīng)鏈選址中的應(yīng)用[J]. 物流技術(shù)，2008，27（8）：86-88.

[7] Colson B， Marcotte P， Savard G. Bilevel programming： A survey[J]. A Quarterly Journal of Operations Research （4OR）， 2005，3（2）：87-107.

[8] Kolstad C D， Lasdon L S. Derivative evaluation and computational experience with large bilevel mathematical programs[J]. Journal of Optimization Theory & Applications， 1990，65（3）：485-499.

[9] Bard J F， Falk J E. An explicit solution to the multi-level programming problem[J]. Computers & Operations Research， 1982，9（1）：77-100.

[10] Anandalingam G， White D J. A solution method for the linear static Stackelberg problem using penalty functions[J]. Automatic Control IEEE Transactions on， 1990，35（10）：1170-1173.

[11] Mathieu R， Pittard L， Anandalingam G. Genetic algorithm based approach to bi-level linear programming[J]. Rairo Recherche Opérationnelle， 1994，28（1）：1-21.

[12] Charnes A， Cooper W. Chance-Constrained Programming[J]. Management Science， 1959，6（6）：73-79.

[13] Zhang D， Lin G H. Bilevel direct search method for leader-follower problems and application in health insurance[J]. Computers & Operations Research， 2014，41（1）：359-373.

[14] 劉寶碇. 隨機(jī)規(guī)劃與模糊規(guī)劃[M]. 北京：清華大學(xué)出版社，1998：74-83.

[15] 張迅. 遺傳算法解供應(yīng)鏈中二級(jí)分銷網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的隨機(jī)規(guī)劃模型[J]. 科學(xué)技術(shù)與工程，2005，5（23）：1819-1822.endprint