Vague指派問題的求解方法研究

崔春生

(1.河南財經政法大學 計算機與信息工程學院,河南 鄭州 450002; 2.中國社會科學院 數量經濟與技術經濟研究所,北京 100010)

?

Vague指派問題的求解方法研究

崔春生1，2

(1.河南財經政法大學 計算機與信息工程學院,河南 鄭州 450002; 2.中國社會科學院 數量經濟與技術經濟研究所,北京 100010)

Vague指派問題的特殊性在于用Vague值表述效益矩陣，進而反映了指派問題中存在的諸多不確定性和模糊性。論文根據Vague值的特點，提出了Vague指派問題的求解轉化為經典指派問題思想，進而借助“馬太效應”函數、特征值向量和Pareto三種方法實現問題的求解。最后，論文以參考文獻中的一組數據為例，采用以上方法進行計算，得到了理想的結果。

運籌學；Vague指派；記分函數；特征值；Pareto

0 引言

指派問題是運籌學中一類特殊的線性規劃問題，用于解決如何分派n個人去完成企業中n個不同的任務，以獲得最佳的工作效率。指派問題中的效益矩陣代表每個人完成不同工作花費的時間，屬于極小化問題，如果效益矩陣的含義有所變化，變成每個人完成不同工作得到的收益，指派問題就變成求目標函數極大的問題。

一般的，指派問題的數學模型可以表示為[1]：

(1)

其中，目標函數的系數cij≥0(i,j=1,2,…,n)。

通常，把這些數寫成矩陣形式：

C稱為系數矩陣或效益矩陣。

指派問題的形式很多，平衡指派問題研究人數與任務數相等，一人一事且一事一人。這種問題可以借助于匈牙利法[1]、削高排除法[2]、縮陣分析法[3]和差額法[4]等進行求解。廣義指派問題也有很多形式，如人數大于事數，一人一事且一事多人；事數大于人數，一事一人且一人多事[5]；實際分配任務數不超過總人數也不超過總任務數的C指派間題[6]。這些問題一般需要轉換成平衡指派問題進行求解。

運籌學教材中的指派問題一般是在Canter集上求解，效益矩陣用實數來表示；模糊數學中運用Fuzzy集解決指派問題，效益矩陣中用模糊數刻畫每個工作人員完成每項任務的熟練程度或滿意程度[7]。吳祈宗等人[8]提出了Vague指派的思想，借助于記分函數方法實現了Vague值向實數值的轉化。但是，記分函數在處理指派問題時并不能完全表達指派目標函數中的最小值的思想，因此有必要進一步探討Vague指派的方法。

1 Vague指派問題的描述

Vague指派是指效益矩陣中的每一個數均為Vague值，表征了每個人完成每項工作花費時間(或取得收益)的不確定性。不確定程度的大小反映在Vague值之間的差異。

Vague集來源于Fuzzy集，在Fuzzy集基礎上，通過真隸屬度和假隸屬度引入，給出以區間形式表示的隸屬程度——該區間能夠同時給出支持證據和反對證據的程度，并且能夠表示中立的程度，從而提出Vague集的概念。Vague集較模糊集在描述客觀事物時更貼近現實，更加形象[9,10]。

一個實數值Vague集A是由真隸屬函數tA和假隸屬函數fA描述的：

tA:U→[0,1]，fA:U→[0,1]

對于x∈U,tA(x)是從支持的x∈A證據所導出的x∈A的肯定隸屬度的下界，fA(x)是從反對x∈A的證據所導出的x∈A的否定隸屬度的下界，并且tA(x)+fA(x)≤1。x關A的隸屬度可由[0,1]上的子區間[tA(x),1-fA(x)]表示，或者稱[tA(x),1-fA(x)]是在Vague集A中的Vague值。πA=1-tA(x)-fA(x)為關于A的未知度，也稱為猶豫度或躊躇度。πA是相對于的未知信息的度量，πA的值越大，說明x相對于A的未知信息越多。當tA=1-fA時，πA=0，即tA+fA=1時，Vague值x退化為普通模糊值。

在Vague指派當中，肯定隸屬度是樂觀工作效率的表征，否定隸屬度是悲觀工作時間的表征，而未知度反映了工作效率的確定性程度。進而Vague指派的數學模型可以表示為：

(2)

2 Vague指派的轉化

通常來講，Vague指派問題的求解可以有三種思路：

第一，指派問題的本質是求解最小化的線性規劃問題，同時也是特殊的整數規劃、0-1規劃，還是需求量和供應量均為1的特殊運輸問題，所以，可以采用Vague線性規劃以及Vague運輸問題的求解方法[11]。

第二，Vague值的核心是一種概率的思想，其表現形式類似于區間數，因而可以將其看成是一種特殊的區間數，采用區間數指派問題[12]的求解方法。

第三，Vague指派問題求解的一般思路是將Vague值轉化為一般的實數值進行求解。

鑒于第一和第二種情況已有論述此，論文采用第三種思路探討Vague指派問題。

2.1 基于“馬太效應”的Vague值轉化

Vague集中記分函數[13]表示了支持證據和反對證據之間的力量對比，主要用于相似度的計算?，F實中，根據問題的不同性質，人們往往采取不同風險偏好的記分函數。即使是面對同一種事物，在不同的條件下，人們也會有不同的心態。例如，當支持證據占優時，更多采取激進樂觀的策略；而當反對證據占優時，則盡可能地采取保守悲觀的策略。

可見當支持證據占優時，記分函數滿足：S(x)>S(Ex)，容易采取風險追求型(Risk Proneness)記分函數[14]：

(3)

這種情況往往高估其真實值。

當反對證據占優時，記分函數滿足：S(x)

(4)

這種情況往往低估其真實值。

當反對證據和支持證據無法平衡時，記分函數滿足S(x)=S(Ex)，容易采取風險中立型(Risk Neutralness)記分函數，風險中立的記分函數就是Chen[13]提出的普通記分函數S(x)=tij-fij。

在指派問題的決策中，類似于其他社會現象，存在一種“馬太效應”。所謂的“馬太效應”(Matthew Effect)正是人們某種心理的反映——1968年，美國科學史研究者羅伯特·莫頓(Robert K. Merton)首次用“馬太效應”來描述這種社會心理現象，“對已有相當聲譽的科學家做出的貢獻給予的榮譽越來越多，而對于那些還沒有出名的科學家則不肯承認他們的成績”。Vague集中的記分函數SME(x)則反映了這種價值取向[14]。

(5)

顯然，“馬太效應”中，tij>fij時是風險追求型的，在tij≤fij時是風險厭惡的。

2.2 基于特征向量的Vague值轉化

從一般問題出發，考慮效益矩陣中Vague值的大小比較。顯然，對Vague值比較，下列假設是合理的[15]：

①從肯定隸屬度角度分析，tij越大，Vague值越大；

②從否定隸屬度角度分析，1-fij越大(fij越小)，Vague值越大；

③從未知度(也稱猶豫度)角度分析，πi越小(1-πi越大)，Vague值越大；

目前，對于“一帶一路”的傳播思考仍然沒能擺脫傳統的思維框架，不少研究仍集中于“搶奪國際話語權”“講好中國故事”等“自我中心論”。必須認識到，受歡迎的中國故事是能與當地受眾建立起聯系的故事。

對Vague集A={c11,c12,…,c1n,…,cnn}，構造如下矩陣

(6)

其中Yl是含有m=n×n個分量的一維列向量，l=1,2,3。

設對應Vague集A={c11,c12,…,c1n,…,cnn}Vague值胡排序向量為O={O1,O2,…,Om}T,O>0。在上面給出的3個合理假設條件下，排序向量應該是所有的，具有m個分量的一維列向量中與矩陣Y的兩個列向量的夾角之和最小的向量。因此如下定義Vague值的排序向量：

將Vague值的排序向量表示為O={O1,O2,…,Om}T,O>0，且不失一般性，令OOT=1。

定義2 令Z=YYT，稱矩陣Z為Vague值排序矩陣。

定理2 排序矩陣是正矩陣，即Z>0。

定理3 Vague值排序矩陣Z的最大特征值對應的特征向量即為排序向量。

證明 令O∈Rm,O={O1,O2,…,Om}T,O>0且OOT=1。令

為求出f的最大值，建立輔助函數：g(O1,O2,…,Om,λ)OTYYTO-λ(OTO-1)

令

可知，如果f取最大值，則λ是Z的特征值，且O是Z的一個特征向量。

下面證明λ是Z的最大特征值[18]。

由定理2可知Z>0。由Perron定理知Z有最大特征值λ和λ對應的唯一特征向量O*滿足O*TO*=1。令λ′是Z的另一個特征值，且λ≠λ′。

令對應于λ′的特征向量為O′，且O′TO′=1。有

λ≠λ′;ZO*=λO*,ZO′=λ′O′,O*TO*=1,O′TO′=1

用O*T左乘ZO*=λO*,用O′T左乘ZO′=λ′O′，有

O*TZO*=λO*TO*=λ,O′TZO′=λ′O′TO′λ′

2.3 基于Pareto的Vague轉化

Vague指派問題的線性規劃模型(2)進一步表示為：

(7)

可以證明，問題(7)的每一個Pareto解都是原問題(2)的一個有效解[19]。

引入參數λ,將問題(7)轉化為參數規劃問題:

(8)

可以證明，對應于λ的最優解都是問題(7)的Pareto最優解[19]。

進而可以用目標區間的λ水平最優解作為原問題的滿意解，其中λ可根據決策者的風險態度及當時的決策環境而定，當λ=1時，屬于樂觀型決策，風險較大；當λ=0時，屬于悲觀型決策，其追求的目標較低，往往會失去很多良機。

3 案例計算

以論文[8]中RP1的為例，從新的研究內容出發，采用后兩種方法進行計算。

3.1 基于特征向量

借助Matlab計算可得：

采用Matlab中的eig函數，得最大特征值為：λ=6.1510。

對應的特征向量為：

OT=(0.2088 0.3309 0.3192 0.2844 0.1655 0.1248 0.2758 0.3106 0.2903)T

3.2 基于Pareto求解

4 結論

Vague集在解決不確定性問題時具有自身的優點，可以更加形象的描述問題的本質，使得問題處理更加貼近實際，但是這一優點給問題的求解帶來了諸多不便之處，因而論文著重探討Vague值的轉化問題。

在Vague指派問題中，論文中提出了三種方法?！榜R太效用”記分函數方法比較簡單，并且具有一定的靈活性，一方面可以根據問題的不同性質采用風險追逐的記分函數和風險厭惡型函數進行數據處理；另一方面即使在同一個問題當中，可以根據不同的問題性質采用不同的記分函數，以取得更加科學的指派結果?；谔卣飨蛄康霓D換方法理論嚴謹，思路清晰，但是這種方法的基礎是將Vague值看成區間數，如果將Vague值看成一種概率的思想則無法采用這種方法?；赑areto的方法強調的是得到一個Pareto解而非最優解，實際上在不確定性信息環境下是不存在最優解的，因此這種方法的結果可能更加適合于解釋Vague指派的思想。

[1] 吳祈宗,李光,崔春生.運籌學[M].廣州:暨南大學出版社,2009.

[2] 周良澤.削高排除法求解指派問題[J].系統工程學報,1992,7(2): 97-105.

[3] 丁文仁.縮陣分析法—求解指派問題的新方法[J].系統工程理論與實踐,1988,8(3):83- 86.

[4] 周素琴.指派間題的新算法[J].上海師范大學學報(自然科學版),1997,26(2):38- 42.

[5] 余英姿,張強.一類廣義指派問題的有效解法[J].數學的實踐與認識,2008,38(4): 86-92.

[6] 白國仲,毛經中.C指派問題[J].系統工程理論與實踐,2003,23(3):107-111.

[7] 崔春生,吳祈宗.基于模糊數學的員工工作分配問題研究[C].南京:中國運籌學會第九屆學術交流會,2008:603- 609.

[8] 崔春生,吳祈宗.調劑問題的Vague指派方法研究[J].數學的實踐與認識,2010,40(5):72-78.

[9] Gau W L, Buehrer D J. Vague sets[J]. IEEE Transactions on Systems Man and Cybernetics, 1993, 23(2): 610- 614.

[10] Atanassov K, Gargov G. Interval valued intuitionistic fuzzy sets[J]. Fuzzy Sets and Systems. 1989, 31(3): 341-349.

[11] 蘇白云.一種運用Vague集理論轉化區間運輸規劃的方法[J].數學的實踐與認識,2013,43(4):97-99.

[12] 劉小冬,張明海,臧振宇.區間指派問題的研究[J].西安財經學院學報,2011,24(1):19-22.

[13] Chen S. Measure of similarity between vague sets[J]. Fuzzy sets and systems. 1995, 74(2): 217-223.

[14] 王偉平,吳祈宗.關于Vague集理論中記分函數的分析[J].北京理工大學學報(自然科學版),2008,28(4):372-376.

[15] 崔春生.基于集團序方法的推薦系統輸出[J].系統工程理論與實踐,2013,33(7)：1845-1851.

[16] 侯福均,廖愛紅,吳祈宗.判斷信息為偏好序的社會選擇：特征向量法[J].南京理工大學學報(自然科學版),2008,32(12):80- 83.

[17] 侯福均,吳祈宗.判斷信息為偏好序的群決策方案排序:互補判斷矩陣法[J].北京理工大學學報,2009,29(1):80- 83.

[18] 侯福均,吳祈宗.Eigenvector mMethod for ranking alternatives with vague value measurements[J].北京理工大學學報(英文版),2009,18(2): 247-252.

[19] 高峰記,張培龍,馬浩靜,雷紅. 基于區間數的運輸問題[C].西安:西部開發與系統工程——中國系統工程學會第12屆年會論文集,2002:596- 600.

Research on Solving Method of Vague Assignment Problem

CUI Chun-sheng1，2

(1.CollegeofComputer&InformationEngineering,HenanUniversityofEconomicsandLaw,Zhengzhou450002,China; 2.InstituteofQuantitative&TechnicalEconomics,ChineseAcademyofSocialSciences,Beijing100010,China)

The particularity of vague assignment problem is effective matrix expressed by vague values, which reflects the uncertainty and ambiguity of assignment problem. On the characteristics of vague value， vague assignment problem should be transformed into classlcs asslgnment problem. Thereof, with the “Matthew effect” function, the eigenvalues vector and Pareto, vague assignment problem can be solved. Finally, a group of data which comes from reference are calculated. Meanwhile, we get a desired result.

operations research; vague assignment problem; score function; eigenvalue; pareto

2013- 09- 06

國家社科基金資助項目(12BTQ011);河南省高等學校青年骨干教師資助計劃聯合資助

崔春生(1974-),男,河南南陽人,副教授,博士后,研究方向:電子商務智能推薦,決策理論與方法。

O224

A

1007-3221(2015)02- 0058- 06