雙重不確定環(huán)境下指派模型的研究及應(yīng)用

肖繼先，寇春蕾

(華北理工大學(xué) 理學(xué)院，河北 唐山 063009)

?

雙重不確定環(huán)境下指派模型的研究及應(yīng)用

肖繼先，寇春蕾

(華北理工大學(xué) 理學(xué)院，河北 唐山 063009)

隨機(jī)模糊變量；指派問題；期望值；等價變換

在指派問題中加入了對資源量限制的考慮，給出一種含有雙重不確定變量的多目標(biāo)指派問題模型。設(shè)計了一種等價轉(zhuǎn)換方法對該模型進(jìn)行求解，即將隨機(jī)模糊變量的密度函數(shù)轉(zhuǎn)化成為具有概率密度性質(zhì)的函數(shù)，以此計算隨機(jī)模糊變量的期望值，并采用數(shù)值算例對方法進(jìn)行了驗證。說明該方法的合理性和可行性。

引言

指派問題(Assignment Problem)是運籌學(xué)里的一類經(jīng)典問題，屬于0-1規(guī)劃的特例。此類問題最早出現(xiàn)在Votaw和Orden的文獻(xiàn)中，真正得到發(fā)展是在1955年Kuhn給出求解這類問題的匈牙利算法以后。在實際的生產(chǎn)管理中，指派問題有著廣泛的應(yīng)用，如在生產(chǎn)服務(wù)系統(tǒng)、資源優(yōu)化、項目選擇、軍事作戰(zhàn)等領(lǐng)域中都有重要應(yīng)用[1,2]。

傳統(tǒng)的指派問題是指在效益矩陣(或費用矩陣、時間矩陣)精確已知的條件下，確定m個人完成m項任務(wù)的最優(yōu)指派方案，這類問題可以用匈牙利法、隱枚舉、分支定界法等很好地解決[3,4]。但是在實際問題中，由于各人的專長與能力不同，完成各項任務(wù)的效益(或費用、時間等)也就各不相同。更多的時候效益矩陣(或費用矩陣、時間矩陣等)不能精確得到，因此在做決策時經(jīng)常會遇到不確定的效益矩陣(或費用矩陣、時間矩陣等)。這樣就有必要在做決策時對矩陣中的數(shù)據(jù)進(jìn)行統(tǒng)計或粗略統(tǒng)計，從而產(chǎn)生了不確定環(huán)境中的指派問題[5,6]。這種不確定性不再是單一的呈現(xiàn)出隨機(jī)性和模糊性，而是相互滲透的結(jié)果——隨機(jī)模糊性和模糊隨機(jī)性。

基于上述原因，提出了一種雙重不確定環(huán)境中的指派問題，并給出了一種等價變換計算方法，該算法不但簡便，而且有良好的運算效率和近似效果。

1 數(shù)學(xué)模型

1.1 問題描述

傳統(tǒng)的指派問題中只有一個目標(biāo)函數(shù)，但一般情況下指派在追求一定利潤的同時，還可能考慮工作成本、工作時間等。因此在實際問題中，目標(biāo)往往不止一個，這樣就形成了含有多個目標(biāo)的指派問題。另外，傳統(tǒng)的指派問題不考慮資源約束，但實際中，每個人擁有的資源量是有限的，所以在該研究中加入了資源限制。多目標(biāo)指派問題的具體描述如下：

設(shè)將n項任務(wù)分配給m個人，指派方案滿足如下要求：

(1)每個人可以獨立地完成任何一項任務(wù)。

(2)每項任務(wù)只能由一個人來完成，且所有的任務(wù)都必須完成。

為表示方便，將建模過程中用到的若干符號列在下表。

表1 符號列表

1.2 隨機(jī)模糊指派問題的期望值模型

在建模過程中，由于很多因素是不確定的，因此常常考慮目標(biāo)函數(shù)的期望值，追求能夠使期望值達(dá)到最優(yōu)的可行解x。其期望值模型如下：

(1)

2 模型求解

(2)

為隨機(jī)變量ξ的期望值[7]。

定義2設(shè)ξ為模糊變量，則稱

(3)

為模糊變量ξ的期望值。

(4)

為隨機(jī)模糊變量ξ的期望值[7]。

引理1設(shè)φ是隨機(jī)變量ξ的概率密度函數(shù)，若Lebesgue積分

存在且有限，則

(5)

引理2設(shè)φ是模糊變量ξ的隸屬函數(shù)，若Lebesgue積分

存在且有限，則

(6)

引理3設(shè)φ是隨機(jī)模糊變量ξ的密度函數(shù)，若Lebesgue積分

存在且有限，則

(7)

證明 根據(jù)期望值的定義和Fubini定理，有

證畢[8]。

(8)

通過定理1引入等價概率密度函數(shù)，可以將隨機(jī)模糊變量期望值的計算等價轉(zhuǎn)換成隨機(jī)期望值的計算，并且等價概率密度函數(shù)的分布參數(shù)與隨機(jī)模糊變量的密度函數(shù)和隸屬函數(shù)參數(shù)之間存在解析關(guān)系。

把定理1的式(8) 代入引理3的式(7)中，即可得到期望值的另一種表達(dá)方式如下：

(9)

3 算例

模型有關(guān)數(shù)據(jù)如下：

表2 指派問題的利潤矩陣

表3 指派問題的費用矩陣

表4 指派問題的時間矩陣

表5 指派問題的資源消耗量矩陣

建立上面問題的數(shù)學(xué)模型，并利用定理1及定理2變換為等價形式：

(10)

轉(zhuǎn)換為等價模型為：

(11)

求解，可得最優(yōu)解為：

即x12=x14=x21=x33=x35=1。

代入模型，驗證可得：

滿足要求，所求解為較優(yōu)指派方案。

4 結(jié)論

(1)給出了雙重不確定環(huán)境中的指派問題，并在該問題中加入了資源量限制的考慮，進(jìn)而建立了該問題的期望值模型；

(2)提出了一種將隨機(jī)模糊變量的密度函數(shù)等價轉(zhuǎn)換為具有概率性質(zhì)的密度函數(shù)的方法來求解該模型；

(3)應(yīng)用該算法在實例中進(jìn)行了有效的求解，得到了優(yōu)化方案，說明了算法的有效性和合理性。

[1]馬錦娟, 姚曉鵬, 鄭挺. 非標(biāo)準(zhǔn)形式的指派模型在資源分配問題中的應(yīng)用[J]. 大學(xué)數(shù)學(xué), 2014, 30(06):17-20.

[2]魏陽. 航班計劃中機(jī)型指派問題研究[D]. 成都:西南交通大學(xué), 2014.

[3]李元左, 楊曉段. 指派問題的改進(jìn)算法[J]. 價值工程, 2015, 34(07):303-304.

[4]朱明放, 葉飛躍, 丁小未. 基于GEP的任務(wù)指派問題的求解算法[J]. 計算機(jī)工程與應(yīng)用, 2014, 50(22):50-53.

[5]關(guān)靜, 張曉斌, 張金鳳. 隨機(jī)機(jī)會約束的機(jī)型指派模型及算法[J]. 山東大學(xué)學(xué)報(理學(xué)版), 2015, 50(03):45-51.

[6]肖繼先, 李淑娟, 寇春蕾. 不確定機(jī)會約束規(guī)劃模型及在TPTCL中的應(yīng)用[J]. 物流工程與管理, 2014, 36(02):48-49.

[7]劉寶碇,趙瑞清.不確定規(guī)劃及應(yīng)用[M].北京:清華大學(xué)出版社,2003.

[8]李想.機(jī)會測度及其應(yīng)用[D].北京:清華大學(xué),2008.

Research and Application of Assignment Model under Double Uncertainty Environment

XIAO Ji-xian, KOU Chun-lei

(College of Science, North China University of Science and Technology, Tangshan Hebei 063009, China)

random fuzzy variable; assignment problem; expected value; equivalent transformation

In the assignment problem, the resource limitation was taken into consideration, and multi-objective assignment problem model with double uncertainly variable was built. A kind of equivalent transformation method was designed to solve the model, that is the density function of the random fuzzy variables was transformed into one function in the nature of probability density, and that the expected value of random fuzzy variable was calculated. And in this paper the method was verified by numerical example. The rationality and feasibility of the method were moved.

2095-2716(2016)01-0013-06

2015-09-29

2015-12-10

O221.6

A