具有直覺模糊信息的任務(wù)指派問題研究

孫曉雅

（遼寧師范大學(xué) 管理學(xué)院，遼寧 大連 116029）

指派問題是運(yùn)籌學(xué)中的一類經(jīng)典問題，屬于特殊的0-1整數(shù)規(guī)劃問題，它在工作安排，車輛調(diào)度、機(jī)器配置等生產(chǎn)與經(jīng)營活動中都有重要應(yīng)用。標(biāo)準(zhǔn)的指派問題是指在效益矩陣精確已知的條件下，確定n個人完成n項(xiàng)工作的最佳指派方案。在指派問題的求解方法中，匈牙利法因其求解的精確性和高效性被廣為采用。

在實(shí)際問題中，指派問題的效益矩陣往往不能精確得到，更多的時候效益矩陣具有模糊性和不確定性，因此，近年來這類模糊指派問題得到了國內(nèi)外學(xué)者的關(guān)注。Lin和Wen[1]提出了一種效益矩陣為區(qū)間模糊數(shù)的指派問題的標(biāo)記算法。Yaakob和Watada[2]針對模糊方法求解指派問題，探討了社會和心理因素的工人配置模型。張肅[3]等人提出出了一種區(qū)間數(shù)型的多因素指派模型的求解方法，并應(yīng)用于多傳感器的優(yōu)化分配中。樊治平等人[4]和王堅(jiān)強(qiáng)等人[5]將語言評價信息轉(zhuǎn)換為模糊數(shù)，求解了效益矩陣為語言評價信息的群指派問題。

19世紀(jì)80年代Atanassov[6-7]對 Zadeh的模糊集理論進(jìn)行了拓展，提出了直覺模糊集理論。直覺模糊集考慮了隸屬度、非隸屬度和猶豫度三方面信息，它比傳統(tǒng)的模糊集更細(xì)膩地描述和刻畫了客觀世界模糊的本質(zhì)[8]。關(guān)于具有直覺信息的指派問題的研究目前還不多見。在人員選拔和員工錄用等指派情形下，企業(yè)常會采用投票或表決的方式來對員工是否適合擔(dān)任某項(xiàng)工作進(jìn)行評價選拔。這種情況下，指派問題的效益矩陣就需要用直覺模糊數(shù)矩陣的形式表達(dá)，本文將對這類具有直覺模糊信息的指派問題進(jìn)行探討。

1 直覺模糊的概念和比較排序方法

1.1 直覺模糊的定義

定義 1[6-7]設(shè)X是一個非空集合，則稱A={＜x，uA（x），vA（x）＞|x∈X}為直覺模糊數(shù)，其中uA（x）和vA（x）分別為X中，元素x屬于A的隸屬度和非隸屬度，即

vA：X→[0，1]，x∈X→vA（x）∈[0，1]，且滿足條件 0≤uA（x）+vA（x）≤1，x∈X。

此外 πA（x）=1-uA（x）-vA（x），x∈X表示X中，元素x屬于A的猶豫度或不確定度。

定義2[9]X中的元素x屬于A的隸屬度與非隸屬度組成的有序數(shù)對 α=（uα（x），vα（x））稱為直覺模糊數(shù)。 其中uα∈[0，1]，vα∈[0，1]，uα+vα≤1， 且設(shè) Θ 為全體直覺模糊數(shù)的集合。

1.2 直覺模糊的比較排序方法

定義 3[9-10]設(shè) α1=（uα1（x），vα1（x））和 α2=（uα2（x），vα2（x））為 直 覺 模 糊 數(shù) ，s（α1）=uα1（x）-vα1（x）和s（α2）=uα2（x）-vα2（x） 分別 為 α1和 α2的得 分值 ，h（α1）=uα1+vα1h（α2）=uα2+vα2分別為 α1和 α2的精確度，則

若s（α1）＜s（α2），則 α1小于 α2，記為 α1＜α2；

若s（α1）=s（α2），則

（1）若h（α1）=h（α2），則 α1和 α2相等 ，即uα1=uα2和vα1=vα2，記為 α1=α2；

（2）若h（α1）＜h（α2），則 α1小于 α2，記為 α1＜α2；

（3）若h（α1）＞h（α2），則 α1大于 α2，記為 α1＞α2。

2 直覺模糊指派問題建模與求解

2.1 標(biāo)準(zhǔn)指派問題的描述

指派問題的標(biāo)準(zhǔn)形式（以人和任務(wù)為例）：設(shè)有n個人和n項(xiàng)任務(wù)，已知第i人完成第j任務(wù)的費(fèi)用為Cij（i，j=1，2，…，n），要求一個人和任務(wù)之間一一對應(yīng)的指派方案，使完成這n項(xiàng)任務(wù)的總費(fèi)用最少。

一般稱矩陣

為指派問題的系數(shù)矩陣，或效益矩陣。

為了建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入n2個0-1變量

（i，j=1，2，…，n）

這樣，問題的數(shù)學(xué)模型可寫成Model1的形式。

對于非標(biāo)準(zhǔn)指派問題，通常是先將非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型，然后就可以按標(biāo)準(zhǔn)指派問題進(jìn)行求解。

2.2 直覺模糊指派問題

具有直覺模糊信息的指派問題是指效益矩陣為直覺模糊數(shù)矩陣。對于有n個人和n項(xiàng)任務(wù)的指派問題，效益矩陣=（）n×n，（i，j=1，2，…，n）。（uij，vij）表示第i人做第j任務(wù)的直覺模糊數(shù)，其中uij代表第i人做第j項(xiàng)任務(wù)的贊成率，vij代表第i人做第j項(xiàng)任務(wù)的反對率。如一個指派問題，有10個人投票表決，其中23=（0.6，0.3），則表示對于第2個人做第3項(xiàng)工作有6人贊成，3人反對，1人棄權(quán)。

具有直覺模糊信息的指派優(yōu)化目標(biāo)是完成各項(xiàng)工作支持票越多越好，反對票越少越好?；谶@一思想可以得到一個多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型，如Model2所示。

將上面多目標(biāo)數(shù)學(xué)模型中將贊成和反對按相等的權(quán)重進(jìn)行考慮，則轉(zhuǎn)化為單目標(biāo)0-1優(yōu)化問題，如Model3所示。

可以看出，Model3已經(jīng)轉(zhuǎn)化為效益矩陣為直覺模糊數(shù)的得分矩陣的最大化指派問題。

2.3 具有直覺模糊信息的指派問題求解步驟

具有直覺模糊信息的指派問題求解分為如下步驟：

（3）如果將矩陣分為非標(biāo)準(zhǔn)指派矩陣，并將非標(biāo)準(zhǔn)問題轉(zhuǎn)化為標(biāo)準(zhǔn)指派問題，利用匈牙利方法求解效益矩陣為直覺模糊數(shù)的得分矩陣的指派問題Model3。Model3的最優(yōu)解即最優(yōu)指派方案。

3 實(shí)例研究

某一員工選拔的問題中，有6項(xiàng)重要任務(wù)，需要在10名員工中選拔6人分別完成其中一項(xiàng)任務(wù)。員工選拔通過專家投贊同和反對票的形式來決定，得到直覺模糊矩陣如表1所示。

由表1直覺模糊矩陣，求得得分值矩陣如表2所示。

表1 員工完成各項(xiàng)任務(wù)的直覺模糊數(shù)矩陣

本問題是一個人多任務(wù)、目標(biāo)函數(shù)最大化的非標(biāo)準(zhǔn)指派問題，將得分矩陣做為效益矩陣，求解該非標(biāo)準(zhǔn)指派問題得到的最優(yōu)指派方案如表3所示。

結(jié)合模糊直覺數(shù)矩陣，可以看出通過表3的指派方案選拔出的6名員工，分別去執(zhí)行各自的任務(wù)將會是大家贊同率最高，反對率最低的最優(yōu)化指派結(jié)果。另外，員工3、7、8、9由于支持率不高，反對率較大，不安排執(zhí)行任務(wù)。

表2 員工完成各項(xiàng)任務(wù)的直覺模糊數(shù)得分值矩陣

表3 最優(yōu)指派方案

具有直覺模糊信息的指派問題是一類常見的真實(shí)指派問題，本文建立了的直覺模糊指派問題的數(shù)學(xué)模型，并探討了數(shù)學(xué)模型的求解方法。得到以下兩點(diǎn)結(jié)論：（1）在人員選拔，任務(wù)安排和機(jī)器資源等配置的指派問題中，采用直覺模糊數(shù)的進(jìn)行決策的方法更具客觀性，它反映了隸屬度，非隸屬度和猶豫度三方面的信息，使得指派方案的評價更細(xì)致、更科學(xué)。（2）實(shí)例計(jì)算表明，本文將直覺模糊的指派問題轉(zhuǎn)化為以得分值矩陣為效益矩陣的最大化指派問題進(jìn)行求解，該方法簡單、有效、易于操作。綜上，本文所提出的直覺模糊指派問題符合實(shí)際需求且簡便易行，適合在指派決策中推廣應(yīng)用。

[1]LIN C J，WEN U P.A labeling algorithm for the fuzzy assignment problem[J].Fuzzy Sets and Systems， 2004，142：373-391.

[2]YAAKOB S B，WATADA J.Fuzzy approach for assignment problem[C].IEEE International Conference on Fuzzy Systems，2009.

[3]張肅，程啟月，申卯興.基于區(qū)間數(shù)型多因素指派模型的多傳感器優(yōu)化分配方法 [J].自動化學(xué)報，2008，34（2）：240-245.

[4]樊治平，王欣榮.具有語言評價信息的指派問題求解方法[J].系統(tǒng)工程學(xué)報，2004，19（1）：14-19.

[5]王堅(jiān)強(qiáng)，孫超.不完全確定信息的群體語言指派問題的求解方法[J].中國管理科學(xué)，2007，15（1）：74-79.

[6]ATANASSOV K.Intuitionistic fuzzy sets[C].In：Sgurev V ed.VII ITKR′s Session， Sofia， 1983.

[7]ATANASSOV K.Intuitionistic fuzzy sets[J].Fuzzy Sets and Systems， 1986（20）： 87-96.

[8]BUSTINCE H，BURILLO P.Vague sets are intuitionistic fuzzy sets[J].Fuzzy Sets and Systems， 1996， 79： 403-405.

[9]XU Z S，YAGER R R.Some geometric aggregation operators based on intuitionistic fuzzy sets[J].International Journal of General Systems， 2006， 35（4）： 417-433.

[10]XU Z S.Intuitionistic fuzzy aggregation operators[J].IEEE Transactions on Fuzzy Systems， 2007，15（6）：1179-1187.