萬 中，陽彩霞，江 衛(wèi)

(中南大學(xué)數(shù)學(xué)科學(xué)與計(jì)算技術(shù)學(xué)院， 中國 長沙 410083)

一個復(fù)雜的決策系統(tǒng)通常具有多維性、多樣性、多功能性和多準(zhǔn)則性，并有時帶有隨機(jī)參數(shù).含有隨機(jī)參數(shù)的數(shù)學(xué)規(guī)劃稱為隨機(jī)規(guī)劃(SP).隨機(jī)規(guī)劃為解決帶有隨機(jī)參數(shù)的優(yōu)化問題提供了有力的工具.對隨機(jī)優(yōu)化問題中所出現(xiàn)的隨機(jī)參數(shù)，根據(jù)不同的管理目的和技術(shù)要求，所采用的處理方法也不盡相同[1-2].

目前處理隨機(jī)規(guī)劃問題最常用的重要方法有2種：第1種是期望值(EM)方法[3]，該方法通過取隨機(jī)變量的數(shù)學(xué)期望，把隨機(jī)規(guī)劃問題轉(zhuǎn)化為確定性數(shù)學(xué)規(guī)劃問題.第2種方法是機(jī)會約束規(guī)劃方法(簡稱CCPM)，該方法由Charnes和Cooper率先提出，它考慮到了在不利情況發(fā)生時所作出的決策可能不滿足約束條件，因此采取一種原則：要求所作的決策在一定置信水平內(nèi)滿足約束條件[4].

CCPM方法自60年代提出以來，發(fā)展迅速.近年來的相關(guān)研究成果可參閱文獻(xiàn)[5]～[11]，以及其后所列的參考文獻(xiàn).他們利用CCPM成功地解決了來自不同領(lǐng)域(如工業(yè)過程和經(jīng)濟(jì)管理)中的許多問題，諸如水庫管理，電力生產(chǎn)，主板生產(chǎn)，化學(xué)工程，電信及財(cái)經(jīng)等方面的實(shí)際問題.

本文作者的目的是研究典型的生產(chǎn)和運(yùn)輸成本問題.針對該類問題,最近文獻(xiàn)[12]在建立其優(yōu)化模型的基礎(chǔ)上,通過引進(jìn)0-1整數(shù)變量,提出了分段線性逼近法求解產(chǎn)品成本為凹函數(shù)的大型產(chǎn)品運(yùn)輸問題.其不足在于所建立的模型視廠家的生產(chǎn)能力和商家的需求量為確定常數(shù).在文獻(xiàn)[11]中,萬中等人利用機(jī)會約束規(guī)劃方法研究了生產(chǎn)廠家的生產(chǎn)能力,商家的需求量和單位運(yùn)輸成本等因素都是隨機(jī)變量情況下的多產(chǎn)品生產(chǎn)和運(yùn)輸問題.該論文中建立的模型和求解方法雖然具有一般性,但得到的原問題的確定型等價式卻是非線性模型.針對此類問題求解的復(fù)雜性,萬中等人在文獻(xiàn)[10]中還進(jìn)一步研究了線性逼近方法.

與已有工作不同,本文考慮生產(chǎn)廠家的生產(chǎn)能力和商家的需求量是隨機(jī)變量情況下的多產(chǎn)品生產(chǎn)和運(yùn)輸問題.我們將證實(shí)與原問題對應(yīng)的確定型等價式是一個含0-1變量的線性規(guī)劃問題,不僅比文獻(xiàn)[11]中建立的模型要容易求解,而且保證了文獻(xiàn)[12]中的設(shè)計(jì)方法可以應(yīng)用于隨機(jī)環(huán)境.

1 問題描述和模型

典型的生產(chǎn)和運(yùn)輸成本問題可描述如下:假設(shè)某種物資由A、B、C……若干生產(chǎn)商或供應(yīng)商生產(chǎn)或供應(yīng)，該種物資需要運(yùn)送給1、2、3……等銷售地或需求點(diǎn).我們的目標(biāo)是在保證供需平衡的條件下如何確定最佳的生產(chǎn)和運(yùn)輸方案.用數(shù)學(xué)方式表述就是，設(shè)m是生產(chǎn)廠家個數(shù)，n是銷售點(diǎn)個數(shù)，ai,i=1,2,…,m,是第i個廠家的生產(chǎn)能力，bj,j=1,2,…,n,是第j個商家的需求量，wi是第i個廠家需要生產(chǎn)的產(chǎn)量，gi(wi)為第i個廠家生產(chǎn)wi所需的生產(chǎn)成本，xij是廠家i給銷售點(diǎn)j的送貨量，cij為廠家i到銷售點(diǎn)j的單位運(yùn)輸成本.以wi,xij為決策變量，確定最佳生產(chǎn)和運(yùn)輸方案問題可寫成如下優(yōu)化模型：

xij≥0,i=1,2,…,m,j=1,2, …,n,

(1)

其中運(yùn)輸成本由目標(biāo)函數(shù)中的第1個和式(線性部分)確定，生產(chǎn)成本由目標(biāo)函數(shù)中的第2個和式(可分離線性或非線性部分)確定.當(dāng)且僅當(dāng)廠家所能生產(chǎn)的產(chǎn)品量大于商家的需求量時，問題(1)的可行解存在.

一般地，當(dāng)假設(shè)模型(1)中的所有參數(shù)為確定常數(shù)時，問題(1)是一個線性約束的非線性規(guī)劃問題.通過引入0-1變量，文獻(xiàn)[12]在假設(shè)生產(chǎn)成本函數(shù)為凹函數(shù)的條件下，利用分段線性逼近法將原問題歸結(jié)為一系列的帶0-1變量的線性規(guī)劃問題求解.但實(shí)際中，ai和bj,i=1,2,…,m,j=1,2,…,n,常為隨機(jī)變量.這時，問題(1)一般不再是線性約束的非線性規(guī)劃問題.因此，文獻(xiàn)[12]提出的線性化方法不再合適.不過，即使是在隨機(jī)情況下，當(dāng)采取獨(dú)立機(jī)會約束方法處理原問題時，(1)仍是線性約束的非線性規(guī)劃問題，從而保證[12]中的方法能夠推廣到求解隨機(jī)情況下的生產(chǎn)和運(yùn)輸計(jì)劃問題.

假設(shè)ai和bj均為服從正態(tài)分布的隨機(jī)變量,

則約束條件

(2)

和

(3)

可分別松弛為

(4)

和

(5)

其中αi,βj∈[0,1]叫做約束滿足的置信水平.

若αi=βj=1,則條件(4)即為條件(2)，條件(5)即為條件(3).只是ai和bj為隨機(jī)變量時，其解集的測度可能為零.

而

是服從標(biāo)準(zhǔn)正態(tài)分布N(0，1)的隨機(jī)變量，其概率分布函數(shù)形式為

所以，機(jī)會約束(4)等價于

(6)

同理，機(jī)會約束(5)可寫成

(7)

通常把(6)和(7)分別稱為(4)和(5)的確定型等價類.顯然，約束條件(6)和(7)仍是線性約束.

下面我們說明在假設(shè)gi為凹函數(shù)時，如何線性化目標(biāo)函數(shù).

將區(qū)間[0，ai],i=1,2,…,s,分割成k個相等的子區(qū)間，0≡zi0

(8)

其中

λil≥0,l=0,1,…,k,

λi0≤yi0,

λil≤yil-1+yil,l=1,2,…,k,

yil∈{0,1},l=0,1,…,k.

這樣，原問題就轉(zhuǎn)化為如下含0-1變量的線性規(guī)劃問題：

xij≥0,i=1,2,…,m,j=1,2,…,n,

λi0≤yi0,i=1,2,…,s,

λil≤yil-1+yil,,i=1,2,…,s,l=1,2,…,k,

λil≥0,i=1,2,…,s,l=1,2,…,k,

yil∈{0,1},i=1,2,…,s,l=1,2,…,k.

(9)

2 數(shù)值算例

下面把本文建立的模型和求解方法應(yīng)用于一個實(shí)際問題.假設(shè)有4個工廠：工廠1，工廠2，工廠3，工廠4；3個商場：商場A，商場B，商場C.把工廠與商場之間的物理距離看成單位運(yùn)輸成本，各個工廠與商場之間的物理距離由如下矩陣給定：

minf(x,w)=(12x11+21x12+21x13)+(13x21+20x22+23x23)+(15x31+17x32+27x33)+

(17x41+19x42+31x43)+250[(x11+x12+x13)0.6+(x21+x22+x23)0.6+(x31+x32+x33)0.6+

(x41+x42+x43)0.6]

s.t.x11+x12+x13≤200-Φ-1(0.95)×10,

x21+x22+x23≤300-Φ-1(0.95)×10,

x31+x32+x33≤400-Φ-1(0.95)×10,

x41+x42+x43≤200-Φ-1(0.95)×10,

x11+x21+x31+x41≥100+Φ-1(0.95)×10,

x12+x22+x32+x42≥300+Φ-1(0.95)×10,

x13+x23+x33+x43≥400+Φ-1(0.95)×10,

xij≥0,i=1,2,…,4;j=1,2,…,3.

(10)

該模型的約束條件都是線性的，目標(biāo)函數(shù)是線性函數(shù)與冪函數(shù)的和.因此可以利用上一節(jié)提出的轉(zhuǎn)化方法，把此類非線性優(yōu)化問題直接轉(zhuǎn)化為含0-1變量的線性規(guī)劃問題.我們在Lingo 7.0 平臺上得到原問題最優(yōu)解是

w*=(0.000 0,25.325 0,158.225 0)T,f*=4 713.4.

從上述實(shí)例的求解過程可以看出，雖然本文建立的多產(chǎn)品生產(chǎn)和運(yùn)輸問題的數(shù)學(xué)模型不如文獻(xiàn)[10]中的模型具有一般性，但利用本文提出的方法處理隨機(jī)環(huán)境下多產(chǎn)品生產(chǎn)和運(yùn)輸問題，比[10]中的線性逼近方法效率更高.

3 結(jié)論

本文利用機(jī)會約束規(guī)劃方法，把隨機(jī)環(huán)境下的產(chǎn)品生產(chǎn)和運(yùn)輸成本問題轉(zhuǎn)化為含0-1變量的線性規(guī)劃問題來求解.數(shù)值算例表明了本文所建立的模型和求解方法的有效性.

參考文獻(xiàn)：

[1]BIRGEJR，LOUVEAUXFV,Introductiontostochasticprogramming[M].NewYork:Springer, 1997.

[2] 劉寶碇，趙瑞清.隨機(jī)規(guī)劃與模糊規(guī)劃[M].北京：清華大學(xué)出版社，2001.

[3]DANTZIGGB.Linerprogrammingunderuncertainty[J].ManagementScience, 2004, 50(12):1 764-1 769.

[4]CHARNESA,COOPERWW.Chance-constrainedprogramming[J].ManagementScience, 1962,6(1):73-79.

[5]FREDRICKS,HILLIERFS.Chance-constrainedprogrammingwith0-1orboundedcontinuousdecisionvariables[J].ManagementScience, 1967,11(1):34-57.

[6]OLSONDL,SWENSETHSR.Alinearapproximationforchanceconstrainedprogramming[J].JournaloftheOperationalResearchSociety, 1987, 38(3):261-267.

[7]PANNEVD,POPPW.Minimumcostcattlefeedunderprobabilisticproteinconstraints[J].ManagementScience, 1963,9(3):405-430.

[8]SEPPALAY.Constructingsetsofuniformlytighterlinearapproximationsforachance-constraint[J].ManagementScience, 1971, 17(11):736-749.

[9]YAHIAZM,AHMADD.Alinearapproximationmethodforsolvingaspecialclassofthechancecongstrainedprogrammingproblem[J].EuropeanJournalofOperationalResearch, 1995, 80(1):213-225.

[10] 萬 中，江 衛(wèi)，陽彩霞，等.一類求解帶隨機(jī)成本的生產(chǎn)運(yùn)輸問題的線性逼近方法[J].工程數(shù)學(xué)學(xué)報，2010，27(3)：381-388.

[11] 萬 中，陽彩霞，江 衛(wèi)，等.生產(chǎn)運(yùn)輸成本問題的隨機(jī)優(yōu)化模型及新的求解途徑[J].模糊系統(tǒng)與數(shù)學(xué)，2009，23(3)：145-151.

[12]HIROSHIK，TAKAAKIE.Computationalstudiesonlargescaleconcavecosttransportationproblems[J].PacificJournalofOptimization, 2006, 2(2):327-339

[13]WEINTRAUBA,VERAJ.Acuttingplaneapproachforchanceconstrainedlinearprograms[J].OperationResearch, 1991, 39(5):770-776.