一種基于計算機應用的多周期隨機優(yōu)化問題的求解方法

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

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

0 引 言

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

由于SP問題中的變量和條件的不確定性比任何LP問題都要多。因此,用手工計算解決SP問題是很困難的。為了解決這些大規(guī)模問題,因此使用分解技術更加合適?？梢酝ㄟ^分解子問題和主問題來解決大規(guī)模優(yōu)化問題。本文提出了一種基于分解定價模型來解決SP問題的方法。

在日本,大型市場越來越受歡迎,就像許多其他發(fā)達國家一樣。由于管理體系和產品質量,人們對超市越來越感興趣。東京大約有上百家超市,而且這些超市在日本其他城市也有許多分店。在此基礎上,通過從大型市場中收集數據,建立了一個真實的生活隨機模型。因為用手工計算分析模型是非常困難的。這就是為什么使用數學語言模型分析模型的原因。

1 隨機規(guī)劃問題介紹

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

1.1 SP

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

在本文中,利潤因素cω包含不同場景的不確定性,ω和xω代表相應的隨機決策變量。SP有不同的類型。其中主要介紹基于場景的SP。

1.2 基于場景的SP

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

1.3 分解,子問題和主問題

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

考慮到如下線性問題,最大(最小)函數

z=c1x1+c2x2+…+cnxn

具體分解過程如下:

1) 首先從目標函數中減去復雜的約束條件,然后將整個問題分解成以下的子問題;

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

2) 主問題的生成主要取決于相應的分解技術。本文給出了dantzig-wolfe分解算法的主要問題,以展示分解過程。

3) 當子問題值之和等于主問題值時得到最優(yōu)解,即

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

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

1.4 基于分解的定價方法

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

1) 從原始問題的目標函數中減去約束,把整個問題分解成子問題和主問題。通過刪除不提供原始問題的非負值的變量來解決子問題并生成主問題。

2) 當子問題值和主問題值相等時停止。否則,重復前面的步驟。

2 多周期隨機模型

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

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

3 算法具體過程

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

1) 設置迭代次數k;

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

3) 解決子問題;

其中,j代表復雜約束,ω是場景數量,t是時間周期。

4) 主問題將通過刪除那些沒有非負值的變量來從原來的問題中產生。解決以下受限的主問題。

其中,I是一個非空集,所有變量在子問題中給出非負的值。

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

當子問題的目標值和受限的主問題相等時,停止迭代,即V(Sk)=V(Mk+1)。否則,k=k+1,返回1)。

當沒有新的變量進入受限制的主問題時,停止;否則,返回2)。

4 實 驗

展示了3個不同場景下的不同周期內的利潤比較,如圖1所示。

圖1 利潤比較Fig.1 Profit comparison

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

5 結 論

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