張 　 峰

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

?

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

張 峰

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

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

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

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

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

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

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

1.1問(wèn)題的提出

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

1.2模型的建立

(1) 模型假設(shè)

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

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

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

(1)

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

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

1.3模型的求解

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

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

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

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

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

其中對(duì)于λ的取值，有如下情況：

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

由定義1可轉(zhuǎn)化為確定型約束：

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

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

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

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

(5)轉(zhuǎn)化后的模型

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

(2)

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

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

(3)

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

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

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

2.1模型的建立

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

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

(4)

2.2模型的求解

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

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

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

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

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

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

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

(5)

3算法步驟總結(jié)描述

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

對(duì)于上面提到的非線性規(guī)劃問(wèn)題，除了將其用線性逼近等方法轉(zhuǎn)化為線性規(guī)劃問(wèn)題求解外，也可用相應(yīng)的算法來(lái)進(jìn)行求解。如以下形式的非線性最優(yōu)化問(wèn)題(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)化問(wèn)題的間接法有兩種,一種是通過(guò)運(yùn)用約束條件和目標(biāo)函數(shù)組成增廣目標(biāo)函數(shù)，用此方法將有約束的最優(yōu)化問(wèn)題轉(zhuǎn)變?yōu)闊o(wú)約束的最優(yōu)化問(wèn)題，并間接的利用求無(wú)約束最優(yōu)化問(wèn)題方法來(lái)得到新目標(biāo)函數(shù)的穩(wěn)定點(diǎn)或局部最佳解，如大家熟知的乘子法和懲罰函數(shù)法；另外一種方法是在可行區(qū)域內(nèi)用迭代法使得目標(biāo)函數(shù)下降，比如可行點(diǎn)法。

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

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

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

minf(x)

記此問(wèn)題的可行域?yàn)镈L={x|gi(x)≥0,

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

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

步1，minf(x(k))Td

步3， 由線性搜索

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

4結(jié)論

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

參考文獻(xiàn):

[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] 陽(yáng)彩霞,萬(wàn) 中,江 衛(wèi).生產(chǎn)和運(yùn)輸成本問(wèn)題的機(jī)會(huì)約束規(guī)劃方法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011,41(4):90-98.

[4] 萬(wàn) 中,陽(yáng)彩霞,江 衛(wèi).隨機(jī)環(huán)境下生產(chǎn)和運(yùn)輸成本問(wèn)題的線性規(guī)劃方法[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報(bào), 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] 李董輝，童小嬌，萬(wàn)中. 數(shù)值最優(yōu)化[M].北京：科學(xué)出版社，2005.

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

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

[9] 徐玖平.運(yùn)籌學(xué)[M].北京:科學(xué)出版社,2004.

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

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

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

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

[14] 姜啟源.數(shù)學(xué)模型[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

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

中圖分類號(hào)：G642.0

文獻(xiàn)標(biāo)識(shí)碼：A

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

收稿日期：2014-10-28