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

孫曉雅

（遼寧師范大學 管理學院，遼寧 大連 116029）

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

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

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

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

1.1 直覺模糊的定義

定義 1[6-7]設X是一個非空集合，則稱A={＜x，uA（x），vA（x）＞|x∈X}為直覺模糊數，其中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的隸屬度與非隸屬度組成的有序數對 α=（uα（x），vα（x））稱為直覺模糊數。 其中uα∈[0，1]，vα∈[0，1]，uα+vα≤1， 且設 Θ 為全體直覺模糊數的集合。

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

定義 3[9-10]設 α1=（uα1（x），vα1（x））和 α2=（uα2（x），vα2（x））為 直 覺 模 糊 數 ，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 標準指派問題的描述

指派問題的標準形式（以人和任務為例）：設有n個人和n項任務，已知第i人完成第j任務的費用為Cij（i，j=1，2，…，n），要求一個人和任務之間一一對應的指派方案，使完成這n項任務的總費用最少。

一般稱矩陣

為指派問題的系數矩陣，或效益矩陣。

為了建立標準指派問題的數學模型，引入n2個0-1變量

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

這樣，問題的數學模型可寫成Model1的形式。

對于非標準指派問題，通常是先將非標準型轉化為標準型，然后就可以按標準指派問題進行求解。

2.2 直覺模糊指派問題

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

具有直覺模糊信息的指派優化目標是完成各項工作支持票越多越好，反對票越少越好。基于這一思想可以得到一個多目標優化問題的數學模型，如Model2所示。

將上面多目標數學模型中將贊成和反對按相等的權重進行考慮，則轉化為單目標0-1優化問題，如Model3所示。

可以看出，Model3已經轉化為效益矩陣為直覺模糊數的得分矩陣的最大化指派問題。

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

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

（3）如果將矩陣分為非標準指派矩陣，并將非標準問題轉化為標準指派問題，利用匈牙利方法求解效益矩陣為直覺模糊數的得分矩陣的指派問題Model3。Model3的最優解即最優指派方案。

3 實例研究

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

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

表1 員工完成各項任務的直覺模糊數矩陣

本問題是一個人多任務、目標函數最大化的非標準指派問題，將得分矩陣做為效益矩陣，求解該非標準指派問題得到的最優指派方案如表3所示。

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

表2 員工完成各項任務的直覺模糊數得分值矩陣

表3 最優指派方案

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

[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]張肅，程啟月，申卯興.基于區間數型多因素指派模型的多傳感器優化分配方法 [J].自動化學報，2008，34（2）：240-245.

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

[5]王堅強，孫超.不完全確定信息的群體語言指派問題的求解方法[J].中國管理科學，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.