王慧
(榆林市第三中學(xué),陜西榆林 719000)
系統(tǒng)由若干部件組成,只要一個(gè)部件出現(xiàn)故障,系統(tǒng)就不能正常工作。為提高系統(tǒng)可靠性,每個(gè)部件都裝有備件,一旦原部件出現(xiàn)故障,備件就自動(dòng)進(jìn)入系統(tǒng)。顯然,備件越多系統(tǒng)可靠性越大,但費(fèi)用也越高。問題是在一定的費(fèi)用下,如何配置各部件的備件使系統(tǒng)的可靠性最大。
問題一:由N個(gè)部件串接的系統(tǒng),當(dāng)部件k
配置j
個(gè)備件時(shí),該部件正常工作的概率及費(fèi)用已知,在總費(fèi)用不超過定值的條件下,建立使系統(tǒng)的可靠性最大的模型。問題二:先設(shè)定總費(fèi)用為10,若n=
3且每個(gè)部件至多配置3個(gè)備件,部件k
配置j
個(gè)備件時(shí)正常工作的概率p
及費(fèi)用c
如表1,求證如何配置各部件的備件系數(shù)使系統(tǒng)的可靠性最大。串聯(lián)系統(tǒng)是所有部件均可使用時(shí)才運(yùn)轉(zhuǎn)正常的系統(tǒng),它的可靠性為各部件可靠性的乘積。求系統(tǒng)的最大可靠性是一個(gè)典型的多階段決策問題。動(dòng)態(tài)規(guī)劃是解決這樣一類最優(yōu)化問題的專門計(jì)算方法,這類問題允許把它的過程(求解)分解為一系列的單級(jí)過程(步驟)。
而適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。于是,我們有必要考察一下所求問題是否具有這兩點(diǎn)性質(zhì):
(1)最優(yōu)化原理(最優(yōu)子結(jié)構(gòu)性質(zhì)):不論過去狀態(tài)和決策如何,對(duì)前面的決策所形成的狀態(tài)而言,余下的諸決策必須構(gòu)成最優(yōu)策略。
這里,系統(tǒng)可靠性取決于各部件可靠性的乘積,可將系統(tǒng)配置的最優(yōu)化問題轉(zhuǎn)化為各部件配置的優(yōu)化問題。
表1 給定費(fèi)用和配件數(shù)后各部件正常工作的概率及費(fèi)用表
(2)無后效性:某給定的階段狀態(tài),它之前各階段的狀態(tài)無法直接影響它未來的決策,而只能通過當(dāng)前的狀態(tài)。
該題表現(xiàn)為各部件的最優(yōu)效率不影響下一部件的效率性能。
綜上所述,該系統(tǒng)可靠性優(yōu)化問題完全可以用動(dòng)態(tài)規(guī)劃的方法來解決。
經(jīng)分析,該問題滿足動(dòng)態(tài)規(guī)劃的諸要素,故可按以下步驟來建立動(dòng)態(tài)規(guī)劃模型:
(1)把問題的過程劃分為恰當(dāng)?shù)娜舾蓚€(gè)階段,引入階段變量;(2)正確選擇狀態(tài)變量,使它既能描述過程的演變,又能滿足無后效性;(3)確定決策變量及每個(gè)階段的允許決策集;(4)寫出狀態(tài)轉(zhuǎn)移方程;(5)指出階段指標(biāo)及指標(biāo)函數(shù);(6)寫出最優(yōu)函數(shù)。
在問題一的模型基礎(chǔ)上,結(jié)合必要數(shù)據(jù),采用逆序解法進(jìn)行求解即可。
(1)系統(tǒng)的正常運(yùn)作只取決于題給的部件;(2)備件配置后即發(fā)揮可靠性作用,不因意外因素停止運(yùn)轉(zhuǎn);(3)題給數(shù)據(jù)精確可靠。
k
:階段變量(k
=1,2,…,n
);x
:狀態(tài)變量;c
:決策變量;D
(x
):允許決策集合;M
:總費(fèi)用;p
(x
,c
):階段指標(biāo);n
:部件號(hào);f
(x
):最優(yōu)值函數(shù)。由問題分析可知,該問題可用動(dòng)態(tài)規(guī)劃的方法來求解。
n
階段決策問題。把系統(tǒng)第k
個(gè)部件看作k
個(gè)階段(k
=1,2,…,n
),每個(gè)階段初可用于支配的費(fèi)用是前面階段決策的結(jié)果,也是本階段決策的依據(jù)(示意圖如圖1)。圖1 系統(tǒng)正態(tài)化圖
針對(duì)問題一,在總費(fèi)用為M
時(shí),為使系統(tǒng)的可靠性最大,建立動(dòng)態(tài)規(guī)劃模型:(1)階段變量k
:按部件號(hào)將問題分為k
個(gè)階段(k
=1,2,…,n
);(2)狀態(tài)變量x
:表示第k
個(gè)階段可用于支配的費(fèi)用,其中x
=M
;(3)決策變量c
:表示部件k
配置j
個(gè)備件時(shí)的費(fèi)用;p
(x
,c
):表示當(dāng)部件k
配置j
個(gè)部件時(shí)該部件可正常工作的概率;(7)動(dòng)態(tài)規(guī)劃基本方程:
n=
3且每個(gè)部件最多配置3個(gè)備件,總費(fèi)用M
=10。動(dòng)態(tài)規(guī)劃基本方程為:結(jié)合表1數(shù)據(jù),對(duì)基本方程求解:
當(dāng)k
=1時(shí),k
=2時(shí),k
=3時(shí),按上面的順序反推算,可以得到:
由以上求解可知,當(dāng)總費(fèi)用為10,部件1的備件數(shù)量為3,部件2的備件數(shù)量為1,部件3的備件數(shù)量為2時(shí),系統(tǒng)的可靠性達(dá)最大,此時(shí),系統(tǒng)正常工作的概率為0.504。
對(duì)于模型的準(zhǔn)確性驗(yàn)證,可利用程序證明(見附錄程序6—1)。將動(dòng)態(tài)規(guī)劃函數(shù)的程序錄入并計(jì)算后發(fā)現(xiàn)結(jié)果與我們的逆序解法完全一致,充分證明了模型的準(zhǔn)確性和科學(xué)性。
本文運(yùn)用動(dòng)態(tài)規(guī)劃的重要思想,建立了給定費(fèi)用下,系統(tǒng)配置的最優(yōu)化模型。
優(yōu)點(diǎn):(1)原理簡(jiǎn)單,適用性廣;(2)在模型檢驗(yàn)方面,針對(duì)該題數(shù)據(jù)少的實(shí)際情況,引入了遍歷搜索的辦法,更加精準(zhǔn)的驗(yàn)證了模型的科學(xué)性;(3)由于動(dòng)態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動(dòng)態(tài)特征,在計(jì)算中可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解效率。
缺點(diǎn):(1)用數(shù)值方法求解時(shí)存在維數(shù)災(zāi);(2)對(duì)于較復(fù)雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉(zhuǎn)移規(guī)律等方面缺乏靈活性,這就帶來了應(yīng)用上的局限性。
當(dāng)系統(tǒng)部件數(shù)目較大時(shí),可借助計(jì)算機(jī)求取最優(yōu)解。
本模型適用性較廣,可用于解決實(shí)際生活中的問題,例如,人員分配問題,最大受益問題以及最短路徑問題。