王慧

(榆林市第三中學(xué)，陜西榆林 719000)

1 問題重述

系統(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)的可靠性最大。

2 問題分析

串聯(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ī)劃的方法來解決。

2.1 問題一分析

經(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ù)。

2.2 問題二分析

在問題一的模型基礎(chǔ)上，結(jié)合必要數(shù)據(jù)，采用逆序解法進(jìn)行求解即可。

3 模型假設(shè)

(1)系統(tǒng)的正常運(yùn)作只取決于題給的部件；(2)備件配置后即發(fā)揮可靠性作用，不因意外因素停止運(yùn)轉(zhuǎn)；(3)題給數(shù)據(jù)精確可靠。

4 定義與符號(hào)說明

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ù)。

5 模型建立與求解

由問題分析可知，該問題可用動(dòng)態(tài)規(guī)劃的方法來求解。

5.1 模型建立

按部件劃分階段，將它看做一個(gè)

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)用；

(6)階段指標(biāo)

p

(

x

,

c

):表示當(dāng)部件

k

配置

j

個(gè)部件時(shí)該部件可正常工作的概率；

(7)動(dòng)態(tài)規(guī)劃基本方程:

5.2 模型的實(shí)際應(yīng)用

在問題一建立的模型中，取

n=

3且每個(gè)部件最多配置3個(gè)備件，總費(fèi)用

M

=10。動(dòng)態(tài)規(guī)劃基本方程為:

結(jié)合表1數(shù)據(jù)，對(duì)基本方程求解:

當(dāng)

k

=1時(shí)，

當(dāng)

k

=2時(shí)，

當(dāng)

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。

6 結(jié)果分析與檢驗(yàn)

6.1 結(jié)果的程序驗(yàn)算

對(duì)于模型的準(zhǔn)確性驗(yàn)證，可利用程序證明(見附錄程序6—1)。將動(dòng)態(tài)規(guī)劃函數(shù)的程序錄入并計(jì)算后發(fā)現(xiàn)結(jié)果與我們的逆序解法完全一致，充分證明了模型的準(zhǔn)確性和科學(xué)性。

6.2 模型合理性驗(yàn)證

7 模型評(píng)價(jià)與推廣

本文運(yùn)用動(dòng)態(tài)規(guī)劃的重要思想，建立了給定費(fèi)用下，系統(tǒng)配置的最優(yōu)化模型。

7.1 模型評(píng)價(jià)

優(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)用上的局限性。

7.2 模型改進(jìn)

當(dāng)系統(tǒng)部件數(shù)目較大時(shí)，可借助計(jì)算機(jī)求取最優(yōu)解。

7.3 模型推廣

本模型適用性較廣，可用于解決實(shí)際生活中的問題，例如，人員分配問題，最大受益問題以及最短路徑問題。