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

崔春生

(1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,河南 鄭州 450002; 2.中國社會(huì)科學(xué)院 數(shù)量經(jīng)濟(jì)與技術(shù)經(jīng)濟(jì)研究所,北京 100010)

?

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

崔春生1，2

(1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,河南 鄭州 450002; 2.中國社會(huì)科學(xué)院 數(shù)量經(jīng)濟(jì)與技術(shù)經(jīng)濟(jì)研究所,北京 100010)

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

運(yùn)籌學(xué)；Vague指派；記分函數(shù)；特征值；Pareto

0 引言

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

一般的，指派問題的數(shù)學(xué)模型可以表示為[1]：

(1)

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

通常，把這些數(shù)寫成矩陣形式：

C稱為系數(shù)矩陣或效益矩陣。

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

運(yùn)籌學(xué)教材中的指派問題一般是在Canter集上求解，效益矩陣用實(shí)數(shù)來表示；模糊數(shù)學(xué)中運(yùn)用Fuzzy集解決指派問題，效益矩陣中用模糊數(shù)刻畫每個(gè)工作人員完成每項(xiàng)任務(wù)的熟練程度或滿意程度[7]。吳祈宗等人[8]提出了Vague指派的思想，借助于記分函數(shù)方法實(shí)現(xiàn)了Vague值向?qū)崝?shù)值的轉(zhuǎn)化。但是，記分函數(shù)在處理指派問題時(shí)并不能完全表達(dá)指派目標(biāo)函數(shù)中的最小值的思想，因此有必要進(jìn)一步探討Vague指派的方法。

1 Vague指派問題的描述

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

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

一個(gè)實(shí)數(shù)值Vague集A是由真隸屬函數(shù)tA和假隸屬函數(shù)fA描述的：

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

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

在Vague指派當(dāng)中，肯定隸屬度是樂觀工作效率的表征，否定隸屬度是悲觀工作時(shí)間的表征，而未知度反映了工作效率的確定性程度。進(jìn)而Vague指派的數(shù)學(xué)模型可以表示為：

(2)

2 Vague指派的轉(zhuǎn)化

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

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

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

第三，Vague指派問題求解的一般思路是將Vague值轉(zhuǎn)化為一般的實(shí)數(shù)值進(jìn)行求解。

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

2.1 基于“馬太效應(yīng)”的Vague值轉(zhuǎn)化

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

可見當(dāng)支持證據(jù)占優(yōu)時(shí)，記分函數(shù)滿足：S(x)>S(Ex)，容易采取風(fēng)險(xiǎn)追求型(Risk Proneness)記分函數(shù)[14]：

(3)

這種情況往往高估其真實(shí)值。

當(dāng)反對(duì)證據(jù)占優(yōu)時(shí)，記分函數(shù)滿足：S(x)

(4)

這種情況往往低估其真實(shí)值。

當(dāng)反對(duì)證據(jù)和支持證據(jù)無法平衡時(shí)，記分函數(shù)滿足S(x)=S(Ex)，容易采取風(fēng)險(xiǎn)中立型(Risk Neutralness)記分函數(shù)，風(fēng)險(xiǎn)中立的記分函數(shù)就是Chen[13]提出的普通記分函數(shù)S(x)=tij-fij。

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

(5)

顯然，“馬太效應(yīng)”中，tij>fij時(shí)是風(fēng)險(xiǎn)追求型的，在tij≤fij時(shí)是風(fēng)險(xiǎn)厭惡的。

2.2 基于特征向量的Vague值轉(zhuǎn)化

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

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

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

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

目前，對(duì)于“一帶一路”的傳播思考仍然沒能擺脫傳統(tǒng)的思維框架，不少研究仍集中于“搶奪國際話語權(quán)”“講好中國故事”等“自我中心論”。必須認(rèn)識(shí)到，受歡迎的中國故事是能與當(dāng)?shù)厥鼙娊⑵鹇?lián)系的故事。

對(duì)Vague集A={c11,c12,…,c1n,…,cnn}，構(gòu)造如下矩陣

(6)

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

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

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

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

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

定理3 Vague值排序矩陣Z的最大特征值對(duì)應(yīng)的特征向量即為排序向量。

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

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

令

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

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

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

令對(duì)應(yīng)于λ′的特征向量為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轉(zhuǎn)化

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

(7)

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

引入?yún)?shù)λ,將問題(7)轉(zhuǎn)化為參數(shù)規(guī)劃問題:

(8)

可以證明，對(duì)應(yīng)于λ的最優(yōu)解都是問題(7)的Pareto最優(yōu)解[19]。

進(jìn)而可以用目標(biāo)區(qū)間的λ水平最優(yōu)解作為原問題的滿意解，其中λ可根據(jù)決策者的風(fēng)險(xiǎn)態(tài)度及當(dāng)時(shí)的決策環(huán)境而定，當(dāng)λ=1時(shí)，屬于樂觀型決策，風(fēng)險(xiǎn)較大；當(dāng)λ=0時(shí)，屬于悲觀型決策，其追求的目標(biāo)較低，往往會(huì)失去很多良機(jī)。

3 案例計(jì)算

以論文[8]中RP1的為例，從新的研究內(nèi)容出發(fā)，采用后兩種方法進(jìn)行計(jì)算。

3.1 基于特征向量

借助Matlab計(jì)算可得：

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

對(duì)應(yīng)的特征向量為：

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

3.2 基于Pareto求解

4 結(jié)論

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

在Vague指派問題中，論文中提出了三種方法。“馬太效用”記分函數(shù)方法比較簡單，并且具有一定的靈活性，一方面可以根據(jù)問題的不同性質(zhì)采用風(fēng)險(xiǎn)追逐的記分函數(shù)和風(fēng)險(xiǎn)厭惡型函數(shù)進(jìn)行數(shù)據(jù)處理；另一方面即使在同一個(gè)問題當(dāng)中，可以根據(jù)不同的問題性質(zhì)采用不同的記分函數(shù)，以取得更加科學(xué)的指派結(jié)果?；谔卣飨蛄康霓D(zhuǎn)換方法理論嚴(yán)謹(jǐn)，思路清晰，但是這種方法的基礎(chǔ)是將Vague值看成區(qū)間數(shù)，如果將Vague值看成一種概率的思想則無法采用這種方法?；赑areto的方法強(qiáng)調(diào)的是得到一個(gè)Pareto解而非最優(yōu)解，實(shí)際上在不確定性信息環(huán)境下是不存在最優(yōu)解的，因此這種方法的結(jié)果可能更加適合于解釋Vague指派的思想。

[1] 吳祈宗,李光,崔春生.運(yùn)籌學(xué)[M].廣州:暨南大學(xué)出版社,2009.

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

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

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

[5] 余英姿,張強(qiáng).一類廣義指派問題的有效解法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2008,38(4): 86-92.

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

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

[8] 崔春生,吳祈宗.調(diào)劑問題的Vague指派方法研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),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] 蘇白云.一種運(yùn)用Vague集理論轉(zhuǎn)化區(qū)間運(yùn)輸規(guī)劃的方法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(4):97-99.

[12] 劉小冬,張明海,臧振宇.區(qū)間指派問題的研究[J].西安財(cái)經(jīng)學(xué)院學(xué)報(bào),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] 王偉平,吳祈宗.關(guān)于Vague集理論中記分函數(shù)的分析[J].北京理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,28(4):372-376.

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

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

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

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

[19] 高峰記,張培龍,馬浩靜,雷紅. 基于區(qū)間數(shù)的運(yùn)輸問題[C].西安:西部開發(fā)與系統(tǒng)工程——中國系統(tǒng)工程學(xué)會(huì)第12屆年會(huì)論文集,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

國家社科基金資助項(xiàng)目(12BTQ011);河南省高等學(xué)校青年骨干教師資助計(jì)劃聯(lián)合資助

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

O224

A

1007-3221(2015)02- 0058- 06