關(guān)于求解DEA原始CCR模型中最優(yōu)輸入輸出權(quán)重的方法_晏華輝

1、第12卷 第6期運 籌 與 管 理Vol.12,No.62003年12月OPERAT IO NS RESEARCH AN D M ANA GEM EN T SCI EN CEDec.,2003收稿日期:2003-04-04項金項目:中國科學院管理、決策與信息系統(tǒng)重點實驗室資助項目(3501600作者簡介:晏華輝(1979-,女,湖南人,碩士;崔晉川(1955-,男,北京人,研究員,主要從事最優(yōu)化方法,信息與決策科學的研究。關(guān)于求解DEA 原始CCR 模型中最優(yōu)輸入輸出權(quán)重的方法晏華輝, 崔晉川(中國科學院數(shù)學與系統(tǒng)科學研究院應(yīng)用數(shù)學研究所,北京100080摘 要:本文給出了求解D EA 原始C

2、CR 模型1中最優(yōu)輸入輸出權(quán)重的簡便方法:首先將原始CCR 模型化為線性規(guī)劃模型,然后從該線性規(guī)劃模型的對偶模型入手,運用單純形法,在得到?jīng)Q策單元最優(yōu)效率評價指數(shù)時,根據(jù)線性規(guī)劃的對偶理論,得到?jīng)Q策單元最優(yōu)輸入輸出權(quán)重。該權(quán)重可用在逆DEA 新算法23中。關(guān)鍵詞:運籌學;權(quán)重;檢驗數(shù);松弛變量中圖分類號:O22 文章標識碼:A 文章編號:1007-3221(200306-0007-04A Method for Solving Optimal Input -Ou tpu t Weight in OriginalCCR Model of DEAYAN H ua -hui,CU I Jin -chu

3、an(I nstitute of Ap p lied Mathematics,Academy o f M athematics and System Sciences ,Chinese Academy o f Sciences ,Beij ing 100080,Chinaw eight can be used in a new algorithm of inverse DEA model 23.Key words:operations research;w eight;check number;slack variable0 引言在DEA 原始CCR 模型中,人們一般考慮求解決策單元的最優(yōu)效率

4、評價指數(shù)H *,很少考慮H *所對應(yīng)的決策單元的輸入輸出權(quán)重即決策單元最優(yōu)輸入輸出權(quán)重。隨著研究的進一步深入,發(fā)現(xiàn)原始CCR 模型中H *所對應(yīng)的輸入輸出權(quán)重在逆DEA 算法的改進中起著重要的作用。已有的逆DEA 算法涉及到了所有的決策單元,由于決策單元個數(shù)偏大,造成計算量偏大,計算效率較低。然而,若從逆DEA 的思想出發(fā),可知逆DEA 只是對選定的決策單元的輸入項目或輸出項目值做擾動,并不改變其他決策單元的相對有效值。于是從該決策單元入手來考慮,得到比已有逆DEA 算法簡潔、計算效率更高的新算法,但前提是已知這些決策單元的最優(yōu)效率評價指數(shù)H *及H *對應(yīng)的輸入輸出權(quán)重(參見文獻23。本文給

5、出了一種求解H *對應(yīng)的決策單元輸入輸出權(quán)重的簡便方法:首先對原始CCR 模型做Charnes -Cooper 變換,將分式規(guī)劃化為與之等價的線性規(guī)劃問題,然后通過解該線性規(guī)劃問題的對偶模型,在得到?jīng)Q策單元最優(yōu)效率評價指數(shù)H *的同時,運用線性規(guī)劃的對偶理論,得到H *所對應(yīng)的決策單元輸入輸出權(quán)重。1模型的變換設(shè)有n個決策單元(DM U,m個輸入指標,s個輸出指標。DM U j對應(yīng)的輸入輸出向量分別為x j= (x1j,x mjT,y j=(y1j,y sjT。n個DM U對應(yīng)的輸入輸出向量構(gòu)成的矩陣分別為X=(x1, x n,Y=(y1,y n。輸入輸出權(quán)重的行向量分別v=(v1,v m,u

6、=(u1,u s。對于DM U jo(以下記j o為o,可構(gòu)造CCR分式規(guī)劃模型max uy o vx os.t.u YvX1u0(1此模型經(jīng)過Charnes-Cooper變換后為如下線性規(guī)劃模型4max uy os.t.vx o=1-vX+u Y0v0v0,u0(2根據(jù)線性規(guī)劃對偶理論知,(2的對偶規(guī)劃模型為max Hs.t.H x o-X K0Y Ky0K0(3給(3的約束條件中加入松弛變量s-=(s-1,s-m,s+=(s+1,s+s,令H=H1-H2,H10,H2 0,得到標準型m in H1-H2s.t.H1x o-H2x0-X K-s-=0Y K-s+=y0K,H1,H2,s+,s

7、-0(4令A=x o-x o-X-I000Y0-Ib=y ox=(H1,H2,K T,s-T,s+TC=(1,-1,0,0I R2+n+m+s y=(v,u線性規(guī)劃模型(4即為線性規(guī)劃模型min cxs.t.A x=bx0(5(5的對偶規(guī)劃模型(6即為線性規(guī)劃模型(2max by,yAc(6線性規(guī)劃模型(2與線性規(guī)劃模型(4為標準的原始對偶模型。2算法在線性規(guī)劃模型(4中引入人工變量,構(gòu)成人造基,再用兩階段法并結(jié)合修正單純形法求解,在第二階8運籌與管理2003年第12卷段最優(yōu)表中松弛變量的檢驗數(shù)即為線性規(guī)劃模型(2的最優(yōu)解。令B 為線性規(guī)劃(4的基,最優(yōu)基記為B *,C B 表示B 中的列對應(yīng)

8、于C 中的元素構(gòu)成的向量。由對偶理論,已知(4的最優(yōu)基本可行解B *-1b =(H *,K T *,s-T *,s+T *T時,其對偶規(guī)劃(2的最優(yōu)解為C B *B -1*=(v *,u *。由于(4的特殊性,在運用單純形法求解得到(4的最優(yōu)基本可行解時,松弛變量的檢驗數(shù)恰為(2的最優(yōu)解。令P j 為A 第j 列,檢驗數(shù)為R j =C j -C B B-1P j 。注意到(4中松弛變量s -、s +對應(yīng)的C j 全為零,j =n +2+1,n +2+m +s 。P j 為第j -n -2個分量為-1的負單位向量,j =n +2+1,n +2+m +s 。所以s -j 對應(yīng)的檢驗數(shù)R n +2+

9、j=C B B -1j ,B -1j表示B -1的第j 列,j =1,2,m ,s +j -m 對應(yīng)的檢驗數(shù)R n +2+j =C B B -1j ,j =m +1,m +2,m +s 。因此(2的最優(yōu)解C B *B-1*=(v *1,v *2,v *m ,u *1,u *2,u *s =(C B *B -1*1,C B *B -1*m +s =(R *n +2+1,R *n +2+m +s ,這說明松弛變量的檢驗數(shù)為(2的最優(yōu)解。具體算法如下:第一步:引入人工變量t -=(t -1,t -m ,t +=(t +1,t +s ,構(gòu)造輔助問題(7。其目標函數(shù)為求e T m t -+e T s t

10、 +的最小值,e T m =(1,1I R m ,e T s =(1,1I R s。約束條件是在線性規(guī)劃模型(4的約束方程等號左端分別加上t -1,t -m ,t +1,t +s 得到的,即min z =e T m t -+e T s t+s.t.H 1x o -H 2x o -X K -s -+t -=0Y K -s +t +=y oH 1,H 2,K,s -,s +,t -,t +0(7第二步:用修正單純形法5求解輔助問題(7。當所有非基變量的檢驗數(shù)全為非負數(shù)時,若(Ñz >0,表明線性規(guī)劃模型(4無可行解,停止計算;(Òz =0且所有的人工變量都換成非基變量,(

11、7的最優(yōu)基可作為(4的初始可行基 B 0,轉(zhuǎn)第三步;(Óz =0但存在人工變量為基變量,不妨設(shè)其中一個為t ,t =0,表明有退化解。這時取t 所在行任一系數(shù)不為0的非基變量進基¹,讓t 出基,進行換基迭代。由于t 對應(yīng)的常數(shù)項為0,所以迭代后常數(shù)項不變,全為非負數(shù)。利用修正單純形法介紹的方法計算出迭代后基的逆陣,對其他為基變量的人工變量都做同樣的變換,直到所有人工變量全部退基。以此時的基作為(4的初始可行基 B 0,轉(zhuǎn)第三步。第三步:去掉所有的人工變量,將目標函數(shù)行換為(4的目標函數(shù)行的數(shù)字,以 B 0為初始可行基,計算此時非基變量的檢驗數(shù),繼續(xù)用修正單純形法求解。當所有

12、非基變量的檢驗數(shù)全為非負數(shù)時,(4的目標值H 1-H 2=H 達到最優(yōu),此時松弛變量的檢驗數(shù)對應(yīng)為線性規(guī)劃模型(2的最優(yōu)解(v *,u *。為了求出v *及u *,采用的方法是:通過修正單純形法求出H *之后,根據(jù)對偶理論可得到前m 個松弛變量的檢驗數(shù)對應(yīng)于v *,后s 個松弛變量的檢驗數(shù)對應(yīng)于u *。由H *得到v *及u *這一過程計算量很小,不超過o(m +s 。3 算例設(shè)有7個決策單元(DM UA 、B 、C 、D 、E 、F 、G ,兩個輸入指標,一個輸出指標。AB C D E F G 輸入147842103輸入23312417輸出1111111以DM UA 為例,對其原始CCR 模

13、型做Charnes -Cooper 變換得到線性規(guī)劃模型,將該線性規(guī)劃模型的對偶模型化為標準型(89第6期 晏華輝,等:關(guān)于求解DEA 原始CCR 模型中最優(yōu)輸入輸出權(quán)重的方法¹注:這樣的非基變量一定存在,若不然,即所有非基變量的系數(shù)全為0,則該方程是線性規(guī)劃模型(7的多余方程,這與(7的系數(shù)矩陣的秩為m+s 矛盾。min H1-H2s.t.4H1-4H2+4K+7K+8K+4K+2K+10K+3K-s-1=04H1-4H2+3K+3K+K+2K+4K+K+7K-s-2=0K+K+K+K+K+K+K-s+=1(8首先構(gòu)造(8的輔助問題(9min t-1+t-2+t+s.t.4H1-4

14、H2+4K+7K+8K+4K+2K+10K+3K-s-1+t-1=03H1-3H2+3K+3K+K+2K+4K+K+7K-s-2+t-2=0K+K+K+K+K+K+K-s+t+=1(9用修正單純形法求解(9,記N為非基變量的系數(shù)矩陣,B為基變量的系數(shù)矩陣,P為系數(shù)列向量。初始基B0=(P t-1,P t-2,P t+是單位陣,基變量X B=(t-1,t-2,t+,C B=(1,1,1,X N=(H1,H2,K A,K B,K C,K D,K E,K F,K G,s-1,s-2,s+,CN0=(0,0I R12。計算非基變量檢驗數(shù)R N=C N-C BB-10N0=(-7,7,6,9,8,3,5

15、,10,9,1,1,1,由此確定H1為換入變量。計算,min (B-10biB-10P H1|B-10P H1>0=min1 4,13,-=14,換出變量為t-1,可確定,E1=1400-3410001B-11=E1B-10,按照上面的順序進行,可確定下一步的換出換入變量,進行迭代運算。經(jīng)過三步迭代后,非基變量的檢驗數(shù)全為0,此時基變量為x3=(H1,K F,K G,人工變量已全部退基?；仃?B3的逆矩陣為,(B-13=-126513-326213326-2131,去掉人工變量t-1、t-2和t+,將目標函數(shù)行的數(shù)字換成(8目標函數(shù)行的數(shù)字,以x3為第二階段的初始可行基,以B-13為初

16、始可行基的逆陣,開始第二階段的迭代運算。經(jīng)過兩步迭代后,非基變量的檢驗數(shù)全為非負數(shù),得到了DM UA的最優(yōu)效率評價指數(shù),此時基變量為(H1,K D,K E,松弛變量的檢驗數(shù)為(17,17,67分別對應(yīng)的于所要求的輸入1、輸入2和輸出的權(quán)重v*1、v*2、u*。4結(jié)束語本文將原始CCR模型變換為與之等價的線性規(guī)劃模型,從該線性規(guī)劃模型的對偶模型入手,利用對偶理論,給出了一種求解原始CCR模型中決策單元最優(yōu)輸入輸出權(quán)重的方法。已有的逆DEA算法不需要知道權(quán)重,但它涉及所有的決策單元,計算量大。根據(jù)逆DEA的思想,可以從選定的決策單元入手,得到比已有逆DEA算法更簡潔、計算效率更高的算法,但是改進的新算法依賴于該權(quán)重。因此該權(quán)重對改進逆DEA算法有著重要意義。參考文獻1魏權(quán)齡.評價相對有效性的DEA方法M.北京:中國人民大學出版社,1988.2Zhang Xiang-sun,Cui Jin-chuan.A project evaluation system in the state economic i nformation system of Ch i na-An operations research practicein public sectorsJ.International T ra