孫 可, 劉 杰, 王 戰(zhàn)

(1. 沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034; 2. 沈陽(yáng)農(nóng)業(yè)大學(xué) 信息與電氣工程學(xué)院, 沈陽(yáng) 110866)

0 引 言

隨機(jī)規(guī)劃[1-2](SP)是一種處理不確定性的特殊數(shù)學(xué)規(guī)劃,它與線性規(guī)劃(LP)問(wèn)題密切相關(guān)[3]。LP是一個(gè)確定性問(wèn)題,當(dāng)一些或全部的LP參數(shù)包含不確定性時(shí),它就被稱(chēng)為隨機(jī)規(guī)劃。 Dantzig首先用不確定的數(shù)據(jù)[4]闡明了LP的一般問(wèn)題,因此他被認(rèn)為是建立SP作為數(shù)學(xué)分支的先驅(qū)。SP的主要優(yōu)點(diǎn)是,它可以估計(jì)不同情況下出現(xiàn)不同的不確定性的概率[5-6]。它擴(kuò)展了線性和非線性規(guī)劃問(wèn)題的范圍,包括不同參數(shù)的概率性或統(tǒng)計(jì)信息。在現(xiàn)實(shí)生活中,SP有很多應(yīng)用,如生產(chǎn)、供應(yīng)鏈、調(diào)度、游戲、環(huán)境等方面都有很好的實(shí)現(xiàn)。其中,b.Powell和h.Topaloglu[7]的船隊(duì)管理模式,Julia l.Higle和Suvrajeet Sen[8]的網(wǎng)絡(luò)資源利用模型是SP的最典型的應(yīng)用。

由于SP問(wèn)題中的變量和條件的不確定性比任何LP問(wèn)題都要多。因此,用手工計(jì)算解決SP問(wèn)題是很困難的。為了解決這些大規(guī)模問(wèn)題,因此使用分解技術(shù)更加合適。可以通過(guò)分解子問(wèn)題和主問(wèn)題來(lái)解決大規(guī)模優(yōu)化問(wèn)題。本文提出了一種基于分解定價(jià)模型來(lái)解決SP問(wèn)題的方法。

在日本,大型市場(chǎng)越來(lái)越受歡迎,就像許多其他發(fā)達(dá)國(guó)家一樣。由于管理體系和產(chǎn)品質(zhì)量,人們對(duì)超市越來(lái)越感興趣。東京大約有上百家超市,而且這些超市在日本其他城市也有許多分店。在此基礎(chǔ)上,通過(guò)從大型市場(chǎng)中收集數(shù)據(jù),建立了一個(gè)真實(shí)的生活隨機(jī)模型。因?yàn)橛檬止び?jì)算分析模型是非常困難的。這就是為什么使用數(shù)學(xué)語(yǔ)言模型分析模型的原因。

1 隨機(jī)規(guī)劃問(wèn)題介紹

在本節(jié)中,主要從以下幾個(gè)方面闡述:定義隨機(jī)規(guī)劃問(wèn)題,基于場(chǎng)景的SP,分解技術(shù)。并闡明了子問(wèn)題的含義,以及分解中使用的主問(wèn)題,基于分解的技術(shù)和步驟。

1.1 SP

首先給出一個(gè)線性規(guī)劃問(wèn)題,最大(最小)函數(shù)z=cTx服從Ax=b,x≥0。m×n維的矩陣A=(aok)i=1,m;j=1,n是等式Ax=b約束的系數(shù)矩陣,b=(b1,b2,…,bm)T是等式約束的右向量,c的分量是利潤(rùn)因素,x=(x1,x2,…,xn)T是變量向量,被稱(chēng)為決策變量,且x≥0被稱(chēng)為非負(fù)約束。當(dāng)一些或者所有的LP問(wèn)題包含不確定性時(shí),即為SP問(wèn)題。因此,SP問(wèn)題的數(shù)學(xué)公式如下:

在本文中,利潤(rùn)因素cω包含不同場(chǎng)景的不確定性,ω和xω代表相應(yīng)的隨機(jī)決策變量。SP有不同的類(lèi)型。其中主要介紹基于場(chǎng)景的SP。

1.2 基于場(chǎng)景的SP

一個(gè)隨機(jī)模型的場(chǎng)景是模型中發(fā)生的所有隨機(jī)事件的結(jié)果,以及發(fā)生概率的集合。Khan和Weiner[9]是第一個(gè)提出源自場(chǎng)景的分析,將場(chǎng)景定義為一個(gè)假想的事件序列,將重點(diǎn)放在臨時(shí)過(guò)程和決策點(diǎn)上。有不同類(lèi)型的SP問(wèn)題,預(yù)期值問(wèn)題等。在本文中,使用了基于場(chǎng)景的SP 。SP與在任何或所有參數(shù)中插入的不確定性的場(chǎng)景相關(guān)聯(lián),稱(chēng)為基于場(chǎng)景的SP。這種類(lèi)型的SP問(wèn)題定義為:

1.3 分解,子問(wèn)題和主問(wèn)題

分解是求解大規(guī)模LP問(wèn)題的一種方法。它將整個(gè)問(wèn)題分解成子問(wèn)題和主問(wèn)題。有幾種類(lèi)型的分解技術(shù),dantzig-wolfe分解,Bender的分解,三角分解等[10-12]。下面簡(jiǎn)單地討論分解技術(shù)、子問(wèn)題和主問(wèn)題。

考慮到如下線性問(wèn)題,最大(最小)函數(shù)

z=c1x1+c2x2+…+cnxn

具體分解過(guò)程如下:

1) 首先從目標(biāo)函數(shù)中減去復(fù)雜的約束條件,然后將整個(gè)問(wèn)題分解成以下的子問(wèn)題;

其中,λ1,λ2,…,λn代表非負(fù)的拉格朗日乘數(shù),整個(gè)問(wèn)題就被分解為n個(gè)子問(wèn)題,分別由S1,S2,…,Sn表示。

2) 主問(wèn)題的生成主要取決于相應(yīng)的分解技術(shù)。本文給出了dantzig-wolfe分解算法的主要問(wèn)題,以展示分解過(guò)程。

3) 當(dāng)子問(wèn)題值之和等于主問(wèn)題值時(shí)得到最優(yōu)解,即

V(S1)+V(S2)+…+V(Sn)=V(M)

其中,V(S1),V(S2),…,V(Sn)代表子問(wèn)題的值,V(M)代表主問(wèn)題的值。

1.4 基于分解的定價(jià)方法

這項(xiàng)技術(shù)由Mamer和McBride提出。在本節(jié)中,簡(jiǎn)要討論了基于分解的定價(jià)算法。

1) 從原始問(wèn)題的目標(biāo)函數(shù)中減去約束,把整個(gè)問(wèn)題分解成子問(wèn)題和主問(wèn)題。通過(guò)刪除不提供原始問(wèn)題的非負(fù)值的變量來(lái)解決子問(wèn)題并生成主問(wèn)題。

2) 當(dāng)子問(wèn)題值和主問(wèn)題值相等時(shí)停止。否則,重復(fù)前面的步驟。

2 多周期隨機(jī)模型

在日本,市場(chǎng)管理委員會(huì)必須從國(guó)家不同的地方收集各種各樣的貨物,并制定一個(gè)預(yù)算和一個(gè)計(jì)劃來(lái)最大化利潤(rùn)。他們必須為所有商品和其他行業(yè)制定預(yù)算,有自己的庫(kù)存和運(yùn)輸設(shè)施且必須在不同的時(shí)間進(jìn)行幾次外出采購(gòu)來(lái)收集貨物,但他們的利潤(rùn)一直都不確定。由于一些不確定的事件,如政治條件、商品價(jià)格、客戶(hù)需求等,可能會(huì)發(fā)生變化。文章已經(jīng)收集了2014年的數(shù)據(jù)。一年分為4次,每段時(shí)間包括3個(gè)月。將“一月至三月”為第一期,“四月至六月”為第二期,“七月至九月”為第三期,“十月至十二月”為第四期。收集了12種不同產(chǎn)品的數(shù)據(jù),包括大米,小麥,豌豆,糖,蝦,魷魚(yú),香蕉,雞肉,雞蛋,牛肉和羊肉等?？紤]了他們的運(yùn)輸成本,包裝成本,采購(gòu)成本,人事成本,持有成本?？紤]了3種不同情況下的不確定局勢(shì)“政治條件”。這種不確定的因素妨礙了收集貨物,造成運(yùn)輸問(wèn)題,缺乏客戶(hù)安全等。所考慮的情形是“良好的政治條件”,“正常的政治條件”和“惡劣的政治條件”。在良好的政治條件下,沒(méi)有政治障礙和安全的客戶(hù),在正常的政治條件下,沒(méi)有政治障礙,但仍然缺乏安全的客戶(hù),以及在惡劣的政治條件下,政治障礙和客戶(hù)缺乏安全。成本單位是100噸。

首先介紹一些參數(shù)、決策變量和公式。

3 算法具體過(guò)程

在第一步中,初始化參數(shù)的迭代次數(shù),然后討論Lagrangean乘數(shù)的選擇過(guò)程[13-15]。在此之后,將整個(gè)模型分解為子問(wèn)題和主問(wèn)題。

1) 設(shè)置迭代次數(shù)k;

2) 選擇一組初始價(jià)格的集合λk;

3) 解決子問(wèn)題;

其中,j代表復(fù)雜約束,ω是場(chǎng)景數(shù)量,t是時(shí)間周期。

4) 主問(wèn)題將通過(guò)刪除那些沒(méi)有非負(fù)值的變量來(lái)從原來(lái)的問(wèn)題中產(chǎn)生。解決以下受限的主問(wèn)題。

其中,I是一個(gè)非空集,所有變量在子問(wèn)題中給出非負(fù)的值。

5) 迭代停止條件,有2種方法。

當(dāng)子問(wèn)題的目標(biāo)值和受限的主問(wèn)題相等時(shí),停止迭代,即V(Sk)=V(Mk+1)。否則,k=k+1,返回1)。

當(dāng)沒(méi)有新的變量進(jìn)入受限制的主問(wèn)題時(shí),停止;否則,返回2)。

4 實(shí) 驗(yàn)

展示了3個(gè)不同場(chǎng)景下的不同周期內(nèi)的利潤(rùn)比較,如圖1所示。

圖1 利潤(rùn)比較Fig.1 Profit comparison

在圖1中,下面、中間及上面的柱形分別代表了差、良、優(yōu)的政治狀態(tài)的場(chǎng)景,每個(gè)圖表對(duì)應(yīng)的值代表每個(gè)場(chǎng)景的利潤(rùn)。例如,87 254美元的數(shù)額代表了在第一時(shí)期的情況良好的政治狀況和其他情況下所獲得的利潤(rùn)。金額是以美元計(jì)算的。自然的政治條件是企業(yè)組織的一個(gè)關(guān)鍵因素。直接影響到它的損益。從上面的數(shù)字清楚地看到,在每個(gè)時(shí)期,當(dāng)政治狀況保持良好時(shí),利潤(rùn)最高。同時(shí),由于糟糕的政治狀況,利潤(rùn)逐漸減少,如果利潤(rùn)減少,對(duì)公司來(lái)說(shuō)將是非?？膳碌?。從圖中可以看出,對(duì)于正常的政治狀況來(lái)說(shuō),利潤(rùn)的變動(dòng)率并不太高,但這很好,如果政治狀況持續(xù)一年,公司就不會(huì)虧損。通過(guò)對(duì)整體利潤(rùn)的分析,發(fā)現(xiàn)在第4期利潤(rùn)最高的是在10—12月,94 712美元。最后,可以預(yù)測(cè),該公司必須謹(jǐn)慎壞的政治條件,必須采取一些計(jì)劃,比如提前收集商品不生的或增加的庫(kù)存數(shù)量的傳統(tǒng)位置等,因此它們沒(méi)有下跌風(fēng)險(xiǎn)在這種情況下,并沒(méi)有下令遲延交付客戶(hù)。

5 結(jié) 論

本文提出了一種解決多周期SP問(wèn)題的新方法。為了開(kāi)發(fā)這種技術(shù),使用了DBP的概念。建立了一個(gè)模型,分析了日本大型市場(chǎng)的商業(yè)政策。收集了一年的數(shù)據(jù)來(lái)開(kāi)發(fā)這個(gè)模型。在此基礎(chǔ)上,給出了模型的具體表達(dá)式,并給出了算法的求解過(guò)程。通過(guò)對(duì)利潤(rùn)的比較,并預(yù)測(cè),像大型商店這樣的公司必須制定一個(gè)多變量計(jì)劃來(lái)減少風(fēng)險(xiǎn)以避免損失。