含區(qū)間的生產(chǎn)與運輸模型及算法研究

張 　 峰

(安徽交通職業(yè)技術學院 水運工程系，安徽 合肥 230051)

?

含區(qū)間的生產(chǎn)與運輸模型及算法研究

張 峰

(安徽交通職業(yè)技術學院 水運工程系，安徽 合肥 230051)

摘要：不確定規(guī)劃問題在日常生產(chǎn)、管理科學及基礎工程技術中有廣泛的應用。本文研究了含區(qū)間的生產(chǎn)和運輸?shù)膯栴}，其中運輸費用、生產(chǎn)能力、需求量均為區(qū)間數(shù)，通過引入“滿意度”參量并用理論知識將含區(qū)間規(guī)劃問題轉化成確定的規(guī)劃問題，在此基礎上，進一步研究了隨機成本和區(qū)間容量下的生產(chǎn)和運輸問題，在假設運輸費用為隨機變量且服從正態(tài)分布前提下，利用求期望值的方法將成本轉化為確定數(shù)值，并將區(qū)間容量約束化為確定約束，建立模型并求解。

關鍵詞：生產(chǎn)與運輸；區(qū)間；滿意度

隨機規(guī)劃在存儲生產(chǎn)過程、網(wǎng)絡系統(tǒng)優(yōu)化、存儲系統(tǒng)的研究、水庫調度規(guī)劃、車輛調度規(guī)劃、資金預算分析、作業(yè)安排等行業(yè)都有重要應用。隨機優(yōu)化的重點是對其模型的研究，數(shù)學模型的主要目的是對事物的根本屬性和本質規(guī)律的一種具體數(shù)字化的描述，是從整體上、本質上動態(tài)地把握一個系統(tǒng)[1]。利用過去、現(xiàn)在的樣本和信息，對某種變量在未來的可能性進行定量估計[2]。線性創(chuàng)始人之一的G.Dnaztgi開拓了隨機規(guī)劃問題的研究，在航線班機次數(shù)的問題中運用該知識進行優(yōu)化，通過將客流量定義為隨機變量這種形式建立了隨機規(guī)劃的二階段帶補償問題。D.Walkup和R.Wets證明出“主動法”在解決實際問題的模型中與二階段補償問題是相當?shù)摹６鴮τ陔S機機會約束規(guī)劃，由Charns和Cooper于1959年第一次提出，主要針對隨機變量存在約束條件且決策要在隨機變量被觀測到之前做出的情況。相關機會規(guī)劃是由Liu等學者在最近這些年研究出的一種不確定規(guī)劃模型[3]。

David L. Olson于1987年提出決策環(huán)境涉及需要解決不同程度的不確定性以及潛在的多樣性沖突的目標問題。機會約束考慮遇到的不確定性。如果將此類問題放到一個機會約束的數(shù)學規(guī)劃模型上，由于機會約束的非線性形式，所以是不能實現(xiàn)的[4]。萬中(2007)探討了多產(chǎn)品和單產(chǎn)品的生產(chǎn)運輸成本問題，其中隨機變量為單位運輸成本及銷售地的需求量等因素[5]。

生產(chǎn)運輸問題是運籌學中一類重要的隨機規(guī)劃問題，所以本文主要研究含區(qū)間的生產(chǎn)運輸模型，同時研究含區(qū)間和隨機參數(shù)的生產(chǎn)運輸模型，其中生產(chǎn)能力、需求量均為區(qū)間數(shù)，但是運費為隨機變量，且假設服從正態(tài)分布。通過求期望值的方法建立模型，并給出實例。

1含區(qū)間生產(chǎn)與運輸模型

1.1問題的提出

跨國公司、跨省公司或是連鎖分公司由于需求量及經(jīng)濟效益的增加，如何更好地為公司在不同地區(qū)的工廠作生產(chǎn)規(guī)劃成為管理人員的工作重點。在生產(chǎn)運輸中經(jīng)常會遇到這樣一類問題[6]：

1.2模型的建立

(1) 模型假設

在實際生產(chǎn)生活中，有多種多樣的不確定因素存在于企業(yè)生產(chǎn)經(jīng)營過程中，如中間產(chǎn)品穩(wěn)定存放時期、原材料供應量及價錢、每一道生產(chǎn)工序中產(chǎn)品處理時間和處理量、產(chǎn)品產(chǎn)量、中間存儲單元存儲量、勞動力因素等均有發(fā)生變化的可能。同時，能源和原材料短缺、一些事先無法預料的事情如儀器表故障、生產(chǎn)設備毀壞等都會產(chǎn)生不確定因素。不可忽略的是，一些不確定因素也存在于運輸階段中，如汽油價格、天氣及運輸?shù)臅r間段、道路狀況等[7]。這里，我們假設在工廠的生產(chǎn)費用計算時是包括了這些不確定因素在內的，所得到的花費是公司在長期的生產(chǎn)中統(tǒng)計出來的平均花費。交通運輸成本也為長期統(tǒng)計中得出的結果，這樣使得模型更加接近現(xiàn)實。

(2)含區(qū)間生產(chǎn)運輸模型

通過對問題的分析，知道總的花費包括兩部分，即生產(chǎn)費用和運輸費用。對生產(chǎn)量和需求量進行約束得到符合問題的含區(qū)間生產(chǎn)運輸模型[8]：

(1)

目標函數(shù)中第一個公式為運輸成本，第二個公式為生產(chǎn)成本。當然，對于此模型也可以運用到其他問題中，比如求利益最大化，或是銷售商的需求量為一定量時，因此根據(jù)問題的不同，對模型可作如下說明：(1)對maxZ型的規(guī)劃可通過minZ′=-Z進行轉化；

(2)對≤型的約束，可通過同乘-1變成≥型的約束；

1.3模型的求解

對于模型的求解，首先要了解一定的理論知識。由于生產(chǎn)的規(guī)劃實際上包含管理者的意愿，因此對管理者的滿意度要進行分析。其次要將帶區(qū)間的規(guī)劃問題通過理論知識轉化為確定熟悉的規(guī)劃問題[9]。

(1)一種反映決策者滿意度的區(qū)間數(shù)序關系

定義(1)對于A≤wB且A≠B的情況，則稱A弱小于B，記為A

定義(3)對于A≤sB且A≠B的情況，則稱A強小于B，記為A

有些定義的序數(shù)關系沒有辦法比較，例如A?B的情況，區(qū)間數(shù)間弱序關系不符合傳遞性并且不能將A≤B的程度表現(xiàn)出來，強序關系的條件又過高，因此對于求解區(qū)間線性規(guī)劃問題均不合適。故為了求解此類問題，需要定義一種可以反映決策者滿意度的區(qū)間數(shù)序關系。

其中對于λ的取值，有如下情況：

(2)基于滿意度序關系的區(qū)間不等式進行化解。在λ′滿意度水平下，

由定義1可轉化為確定型約束：

(3)區(qū)間等式的化解。對于含區(qū)間的等式，

(4)目標函數(shù)的化解。一般從兩個角度衡量一個區(qū)間目標函數(shù)值的優(yōu)劣，即區(qū)間目標值Z的柔性系數(shù)w(Z)和位置系數(shù)m(Z)。其中區(qū)間數(shù)信息的不確定性是由柔性系數(shù)來體現(xiàn)的，而區(qū)間數(shù)的大小則由位置系數(shù)反映[9]。

因此將原來區(qū)間規(guī)劃問題轉化為min(m(Z),w(Z))的兩個目標規(guī)劃情況，并在該情況下得到兩個Pareto解，x1≠x2且m(Z1)0，得到最佳解為x1。

依照給出的區(qū)間數(shù)序關系，可簡單的將一般情況下規(guī)劃問題中的含區(qū)間目標函數(shù)轉變?yōu)槟繕撕瘮?shù)為確定型的情況：

(5)轉化后的模型

綜合上述所得結論，在給定滿意度水平λ′的情況下，上述含區(qū)間生產(chǎn)運輸線性規(guī)劃可化為如下確定規(guī)劃的形式：

(2)

2區(qū)間容量下的生產(chǎn)運輸模型

現(xiàn)實中存在這樣一種生產(chǎn)運輸問題，即有多個具有不同生產(chǎn)能力的公司，向多個具有不同需求能力的銷售商提供產(chǎn)品，管理者們所關心的是在滿足需求和生產(chǎn)能力的情況下使得總的花費最少[10]。因此，對于此類產(chǎn)品的生產(chǎn)運輸問題，給出其一般模型如下：

(3)

其中，m是生產(chǎn)供應商個數(shù)，n是銷售地個數(shù)，ai是供應商的生產(chǎn)或供應能力，bj是銷售地j的需求量，cij是供應廠商i到銷售地j的單位運輸成本，wi是供應商i需要生產(chǎn)的產(chǎn)量，gi(wi)為供應商i生產(chǎn)所需的生產(chǎn)成本，xij是供應商i給銷售地j的送貨量。

對于現(xiàn)實生產(chǎn)運輸問題，其生產(chǎn)能力和需求能力根據(jù)長期積累統(tǒng)計數(shù)據(jù)得知是區(qū)間數(shù)，即

一般解決機會約束規(guī)劃的方法有兩種。一種是利用確定性規(guī)劃理論將機會約束規(guī)劃轉化為確定性規(guī)劃，另一種是利用優(yōu)勝劣汰的遺傳算法，通過將機會約束條件用隨機模擬技術處理后，得到?jīng)Q策變量最佳解集和機會約束規(guī)劃目標函數(shù)最佳值。隨機系數(shù)對決策變量最佳解集和機會約束規(guī)劃目標函數(shù)最佳值產(chǎn)生一定的影響，導致其具有隨機性。利用數(shù)理統(tǒng)計的方法，對決策變量最佳解集和隨機目標函數(shù)最佳值進行置信水平區(qū)間估計。通俗地講，在不確定環(huán)境下使事件的機會函數(shù)成為最優(yōu)，即所謂的相關機會規(guī)劃問題。對現(xiàn)實問題建立模型后，由于可行集原則上已經(jīng)定下來，則會導致無法執(zhí)行所給出的最優(yōu)解，這種現(xiàn)象在機會約束規(guī)劃、期望值模型及確定性規(guī)劃中比較常見。

2.1模型的建立

對于上面給出的實際情況，首先建立此問題的模型，設產(chǎn)品有l(wèi)種，xk i j是供應商i向銷售地j供應產(chǎn)品k的單位量。ck i j是產(chǎn)品k從供應商i到銷售地j的單位運輸成本，受各種因素的影響，目標函數(shù)的單位運輸成本ck i j是隨機變量，且ck i j服從標準正態(tài)分布。wki是供應商i生產(chǎn)產(chǎn)品k的產(chǎn)量。gki(wki)為供應商i生產(chǎn)k所需生產(chǎn)成本。aki是供應商i生產(chǎn)或供應產(chǎn)品k的能力。bkj是銷售地j所需產(chǎn)品k的總量。aki和bkj都是區(qū)間數(shù)，且有

根據(jù)條件及一般模型可得到此實際問題的模型為

(4)

2.2模型的求解

定義2對于區(qū)間A和x，不等式A≥x的度的定義如下，

根據(jù)定義1，區(qū)間約束A≥x的可行域可由如下的定理來確定。

定理1對于區(qū)間不等式約束A≥x，給定其成立的度p(0≤p≤1)，原不等式可以轉化為如下清晰的不等式約束

類似的，我們可以給出如下的定義和定理。

定義3對于區(qū)間A和x，不等式A≤x的度的定義如下，

定理2對于區(qū)間不等式約束A≤x，給定其成立的度q(0≤q≤1)，原不等式可以轉化為如下清晰的不等式約束

這樣，在給定p,q滿意度水平的情況下，原約束條件可轉化為：

(5)

3算法步驟總結描述

3.1非線性規(guī)劃算法

對于上面提到的非線性規(guī)劃問題，除了將其用線性逼近等方法轉化為線性規(guī)劃問題求解外，也可用相應的算法來進行求解。如以下形式的非線性最優(yōu)化問題(NLP)

其中，x=(x1,x2,…,xn)T∈Rn，f∶Rn→R，gj∶Rn→R(j∈I∪L)，I={1,2,…,m}，L={m+1,m+2,…,m+p}。一般求解優(yōu)化問題的間接法有兩種,一種是通過運用約束條件和目標函數(shù)組成增廣目標函數(shù)，用此方法將有約束的最優(yōu)化問題轉變?yōu)闊o約束的最優(yōu)化問題，并間接的利用求無約束最優(yōu)化問題方法來得到新目標函數(shù)的穩(wěn)定點或局部最佳解，如大家熟知的乘子法和懲罰函數(shù)法；另外一種方法是在可行區(qū)域內用迭代法使得目標函數(shù)下降，比如可行點法。

3.2約束優(yōu)化問題的可行算法

在求解約束優(yōu)化問題的算法中，可行算法是比較重要的一種。它的迭代過程是從一個可行點迭代到另一個可行點。這樣的迭代過程一般通過兩種策略來實現(xiàn)：由當前可行點產(chǎn)生可行下降方向，求步長，產(chǎn)生下一個可行點，即Zoutendijk可行方向法；還有一種是由當前可行點產(chǎn)生一個中間點，然后通過某種渠道得到一個新的可行點，即投影梯度算法。

下面以Zoutendijk可行方向法為例來說明約束優(yōu)化問題的可行算法?？紤]約束函數(shù)為線性函數(shù)的最優(yōu)化問題：

minf(x)

記此問題的可行域為DL={x|gi(x)≥0,

i∈I,hj(x)=0,j∈E}，d為方向向量，令I(x)表示在點x∈DL處的不等式約束中的有效約束，即I(x)={i∈I|gi(x)=0}。由Zoutendijk算法：

步0，取初始點x(0)∈DL，精度ε>0，令k=0；

步1，minf(x(k))Td

步3， 由線性搜索

由計算和理論分析表明，該算法可能失效或是出現(xiàn)鋸齒現(xiàn)象，使算法收斂很慢甚至不能收斂到最優(yōu)點，因此對這種方法提出了改進。設想在約束條件的邊界上設置一道“安全帶”，迭代點進入“安全帶”時，只允許它往可行域內部移動，而不許向邊界靠近，即在構造可行方向時，既把通過當前迭代點的約束邊界看作起作用的約束，也把充分靠近當前迭代點的邊界約束考慮在內。

4結論

不確定規(guī)劃問題是現(xiàn)代優(yōu)化理論和方法的重要研究領域之一，在日常生產(chǎn)、管理科學及基礎工程技術中有廣泛的應用價值。本文針對實際生產(chǎn)和運輸中存在的不確定性因素，研究分析了一類含區(qū)間的生產(chǎn)與運輸模型及算法。作為滲透到社會中各個學科領域的隨機規(guī)劃得到了世界各地專家學者的關注，尤其是近些年來，伴隨著社會的發(fā)展和科學的進步，隨機規(guī)劃被人們越來越多的應用到實際問題的解決中來，因此隨機規(guī)劃領域的探索引起人們愈來愈多的興趣和關注，成為現(xiàn)在規(guī)劃領域的閃亮之星。

參考文獻:

[1] Yahia Zare, M., Daneshmand, A. A linear approximation method for solving a special class of the chance constrained programming problem[J]. European Journal of Operational Research, 1995,80(1):213-25.

[2] Rafael A. Melo a, Laurence A. Wolsey. Optimizing production and transportation in a commit-to-delivery business mode[J]. European Journal of Operational Research, 2010,203:614-618.

[3] 陽彩霞,萬 中,江 衛(wèi).生產(chǎn)和運輸成本問題的機會約束規(guī)劃方法[J]. 數(shù)學的實踐與認識，2011,41(4):90-98.

[4] 萬 中,陽彩霞,江 衛(wèi).隨機環(huán)境下生產(chǎn)和運輸成本問題的線性規(guī)劃方法[J]. 湖南師范大學自然科學學報, 2010,33(4):9-13.

[5] Michael Patriksson,Laura Wynter. Stochastic mathematical programs with equilibrium constraints[J]. Operations Research Letters，1999,25:159-167.

[6] 李董輝，童小嬌，萬中. 數(shù)值最優(yōu)化[M].北京：科學出版社，2005.

[7] 萬中. 陽彩霞. 生產(chǎn)運輸成本問題的隨機優(yōu)化模型及新的求解途徑[J]. 模糊系統(tǒng)與數(shù)學, 2009,23(3):145-151.

[8] 汪振鵬,繆銓生.概率與數(shù)理統(tǒng)計[M]. 武漢：華東師范大學出版社，2000.

[9] 徐玖平.運籌學[M].北京:科學出版社,2004.

[10] 劉新旺,達慶利,韓世蓮.區(qū)間數(shù)運輸問題模型及其模糊目標規(guī)劃求解方法[J].管理工程學報, 1999(4): 5-8.

[11] 郭 鵬,曹朝喜.關于運輸問題最優(yōu)解的進一步討論[J].數(shù)學的實踐與認識,2006(5): 140-146.

[12] 楊振明.概率論[M].第2版.北京：科學出版社,2004.

[13] 王志忠，王國富. 數(shù)理統(tǒng)計[M]．長沙：中南大學出版社,2003.

[14] 姜啟源.數(shù)學模型[M].第三版.北京:高等教育出版社，2003.

On Production and Transportation Model with Interval and Algorithm Research

ZHANG Feng

(Water Transport Engineering Dept. Anhui Communications Vocational & Technical College,Hefei 230051,China)

Abstract:Uncertain programming problem has wide application value in the daily production, management science and engineering technology. This paper studies the production and transportation problem with interval, in which transportation costs, production capacity, and demand are interval numbers. With the introduction of satisfaction, parameter and theoretical knowledge, the programming problem with interval is converted into certain programming problem. On this basis, the paper studies the production and transportation problems with stochastic cost and interval capacity. On the assumption that transportation costs obey normal distribution, as random variables, by the method of using expectations for converting the costs to determine the number, changing the interval capacity constraints into certain constraints, the paper builds a model, in which the method of solving is given.

Key words:stochastic programming, production and transportation, interval, satisfaction

文章編號：1007-4260(2015)02-0026-05

中圖分類號：G642.0

文獻標識碼：A

作者簡介：張峰，男，安徽蕭縣人，碩士，安徽交通職業(yè)技術學院講師，主要從事基礎數(shù)學、計算數(shù)學的教學與研究。

收稿日期：2014-10-28