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

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

2、CR 模型1中最優(yōu)輸入輸出權(quán)重的簡(jiǎn)便方法:首先將原始CCR 模型化為線性規(guī)劃模型,然后從該線性規(guī)劃模型的對(duì)偶模型入手,運(yùn)用單純形法,在得到?jīng)Q策單元最優(yōu)效率評(píng)價(jià)指數(shù)時(shí),根據(jù)線性規(guī)劃的對(duì)偶理論,得到?jīng)Q策單元最優(yōu)輸入輸出權(quán)重。該權(quán)重可用在逆DEA 新算法23中。關(guān)鍵詞:運(yùn)籌學(xué);權(quán)重;檢驗(yàn)數(shù);松弛變量中圖分類(lèi)號(hào):O22 文章標(biāo)識(shí)碼:A 文章編號(hào):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、評(píng)價(jià)指數(shù)H *,很少考慮H *所對(duì)應(yīng)的決策單元的輸入輸出權(quán)重即決策單元最優(yōu)輸入輸出權(quán)重。隨著研究的進(jìn)一步深入,發(fā)現(xiàn)原始CCR 模型中H *所對(duì)應(yīng)的輸入輸出權(quán)重在逆DEA 算法的改進(jìn)中起著重要的作用。已有的逆DEA 算法涉及到了所有的決策單元,由于決策單元個(gè)數(shù)偏大,造成計(jì)算量偏大,計(jì)算效率較低。然而,若從逆DEA 的思想出發(fā),可知逆DEA 只是對(duì)選定的決策單元的輸入項(xiàng)目或輸出項(xiàng)目值做擾動(dòng),并不改變其他決策單元的相對(duì)有效值。于是從該決策單元入手來(lái)考慮,得到比已有逆DEA 算法簡(jiǎn)潔、計(jì)算效率更高的新算法,但前提是已知這些決策單元的最優(yōu)效率評(píng)價(jià)指數(shù)H *及H *對(duì)應(yīng)的輸入輸出權(quán)重(參見(jiàn)文獻(xiàn)23。本文給

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

6、=(u1,u s。對(duì)于DM U jo(以下記j o為o,可構(gòu)造CCR分式規(guī)劃模型max uy o vx os.t.u YvX1u0(1此模型經(jīng)過(guò)Charnes-Cooper變換后為如下線性規(guī)劃模型4max uy os.t.vx o=1-vX+u Y0v0v0,u0(2根據(jù)線性規(guī)劃對(duì)偶理論知,(2的對(duì)偶規(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,得到標(biāo)準(zhǔn)型m in H1-H2s.t.H1x o-H2x0-X K-s-=0Y K-s+=y0K,H1,H2,s+,s

7、-0(4令A(yù)=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的對(duì)偶規(guī)劃模型(6即為線性規(guī)劃模型(2max by,yAc(6線性規(guī)劃模型(2與線性規(guī)劃模型(4為標(biāo)準(zhǔn)的原始對(duì)偶模型。2算法在線性規(guī)劃模型(4中引入人工變量,構(gòu)成人造基,再用兩階段法并結(jié)合修正單純形法求解,在第二階8運(yùn)籌與管理2003年第12卷段最優(yōu)表中松弛變量的檢驗(yàn)數(shù)即為線性規(guī)劃模型(2的最優(yōu)解。令B 為線性規(guī)劃(4的基,最優(yōu)基記為B *,C B 表示B 中的列對(duì)應(yīng)

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

9、j=C B B -1j ,B -1j表示B -1的第j 列,j =1,2,m ,s +j -m 對(duì)應(yīng)的檢驗(yàn)數(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 ,這說(shuō)明松弛變量的檢驗(yàn)數(shù)為(2的最優(yōu)解。具體算法如下:第一步:引入人工變量t -=(t -1,t -m ,t +=(t +1,t +s ,構(gòu)造輔助問(wèn)題(7。其目標(biāo)函數(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的約束方程等號(hào)左端分別加上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求解輔助問(wèn)題(7。當(dāng)所有非基變量的檢驗(yàn)數(shù)全為非負(fù)數(shù)時(shí),若(Ñz >0,表明線性規(guī)劃模型(4無(wú)可行解,停止計(jì)算;(Òz =0且所有的人工變量都換成非基變量,(

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

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

13、型做Charnes -Cooper 變換得到線性規(guī)劃模型,將該線性規(guī)劃模型的對(duì)偶模型化為標(biāo)準(zhǔn)型(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的輔助問(wèn)題(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。計(jì)算非基變量檢驗(yàn)數(shù)R N=C N-C BB-10N0=(-7,7,6,9,8,3,5

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

16、始可行基的逆陣,開(kāi)始第二階段的迭代運(yùn)算。經(jīng)過(guò)兩步迭代后,非基變量的檢驗(yàn)數(shù)全為非負(fù)數(shù),得到了DM UA的最優(yōu)效率評(píng)價(jià)指數(shù),此時(shí)基變量為(H1,K D,K E,松弛變量的檢驗(yàn)數(shù)為(17,17,67分別對(duì)應(yīng)的于所要求的輸入1、輸入2和輸出的權(quán)重v*1、v*2、u*。4結(jié)束語(yǔ)本文將原始CCR模型變換為與之等價(jià)的線性規(guī)劃模型,從該線性規(guī)劃模型的對(duì)偶模型入手,利用對(duì)偶理論,給出了一種求解原始CCR模型中決策單元最優(yōu)輸入輸出權(quán)重的方法。已有的逆DEA算法不需要知道權(quán)重,但它涉及所有的決策單元,計(jì)算量大。根據(jù)逆DEA的思想,可以從選定的決策單元入手,得到比已有逆DEA算法更簡(jiǎn)潔、計(jì)算效率更高的算法,但是改進(jìn)的新算法依賴(lài)于該權(quán)重。因此該權(quán)重對(duì)改進(jìn)逆DEA算法有著重要意義。參考文獻(xiàn)1魏權(quán)齡.評(píng)價(jià)相對(duì)有效性的DEA方法M.北京:中國(guó)人民大學(xué)出版社,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