关于求解DEA原始CCR模型中最优输入输出权重的方法_晏华辉

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项金项目:中国科学院管理、决策与信息系统重点实验室资助项目(3501600作者简介:晏华辉(1979-,女,湖南人,硕士;崔晋川(1955-,男,北京人,研究员,主要从事最优化方法,信息与决策科学的研究。关于求解DEA 原始CCR 模型中最优输入输出权重的方法晏华辉, 崔晋川(中国科学院数学与系统科学研究院应用数学研究所,北京100080摘 要:本文给出了求解D EA 原始C

2、CR 模型1中最优输入输出权重的简便方法:首先将原始CCR 模型化为线性规划模型,然后从该线性规划模型的对偶模型入手,运用单纯形法,在得到决策单元最优效率评价指数时,根据线性规划的对偶理论,得到决策单元最优输入输出权重。该权重可用在逆DEA 新算法23中。关键词:运筹学;权重;检验数;松弛变量中图分类号: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 模型中,人们一般考虑求解决策单元的最优效率

4、评价指数H *,很少考虑H *所对应的决策单元的输入输出权重即决策单元最优输入输出权重。随着研究的进一步深入,发现原始CCR 模型中H *所对应的输入输出权重在逆DEA 算法的改进中起着重要的作用。已有的逆DEA 算法涉及到了所有的决策单元,由于决策单元个数偏大,造成计算量偏大,计算效率较低。然而,若从逆DEA 的思想出发,可知逆DEA 只是对选定的决策单元的输入项目或输出项目值做扰动,并不改变其他决策单元的相对有效值。于是从该决策单元入手来考虑,得到比已有逆DEA 算法简洁、计算效率更高的新算法,但前提是已知这些决策单元的最优效率评价指数H *及H *对应的输入输出权重(参见文献23。本文给

5、出了一种求解H *对应的决策单元输入输出权重的简便方法:首先对原始CCR 模型做Charnes -Cooper 变换,将分式规划化为与之等价的线性规划问题,然后通过解该线性规划问题的对偶模型,在得到决策单元最优效率评价指数H *的同时,运用线性规划的对偶理论,得到H *所对应的决策单元输入输出权重。1模型的变换设有n个决策单元(DM U,m个输入指标,s个输出指标。DM U j对应的输入输出向量分别为x j= (x1j,x mjT,y j=(y1j,y sjT。n个DM U对应的输入输出向量构成的矩阵分别为X=(x1, x n,Y=(y1,y n。输入输出权重的行向量分别v=(v1,v m,u

6、=(u1,u s。对于DM U jo(以下记j o为o,可构造CCR分式规划模型max uy o vx os.t.u YvX1u0(1此模型经过Charnes-Cooper变换后为如下线性规划模型4max uy os.t.vx o=1-vX+u Y0v0v0,u0(2根据线性规划对偶理论知,(2的对偶规划模型为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线性规划模型(4即为线性规划模型min cxs.t.A x=bx0(5(5的对偶规划模型(6即为线性规划模型(2max by,yAc(6线性规划模型(2与线性规划模型(4为标准的原始对偶模型。2算法在线性规划模型(4中引入人工变量,构成人造基,再用两阶段法并结合修正单纯形法求解,在第二阶8运筹与管理2003年第12卷段最优表中松弛变量的检验数即为线性规划模型(2的最优解。令B 为线性规划(4的基,最优基记为B *,C B 表示B 中的列对应

8、于C 中的元素构成的向量。由对偶理论,已知(4的最优基本可行解B *-1b =(H *,K T *,s-T *,s+T *T时,其对偶规划(2的最优解为C B *B -1*=(v *,u *。由于(4的特殊性,在运用单纯形法求解得到(4的最优基本可行解时,松弛变量的检验数恰为(2的最优解。令P j 为A 第j 列,检验数为R j =C j -C B B-1P j 。注意到(4中松弛变量s -、s +对应的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 对应的检验数R n +2+

9、j=C B B -1j ,B -1j表示B -1的第j 列,j =1,2,m ,s +j -m 对应的检验数R n +2+j =C B B -1j ,j =m +1,m +2,m +s 。因此(2的最优解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 ,这说明松弛变量的检验数为(2的最优解。具体算法如下:第一步:引入人工变量t -=(t -1,t -m ,t +=(t +1,t +s ,构造辅助问题(7。其目标函数为求e T m t -+e T s t

10、 +的最小值,e T m =(1,1I R m ,e T s =(1,1I R s。约束条件是在线性规划模型(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。当所有非基变量的检验数全为非负数时,若(Ñz >0,表明线性规划模型(4无可行解,停止计算;(Òz =0且所有的人工变量都换成非基变量,(

11、7的最优基可作为(4的初始可行基 B 0,转第三步;(Óz =0但存在人工变量为基变量,不妨设其中一个为t ,t =0,表明有退化解。这时取t 所在行任一系数不为0的非基变量进基¹,让t 出基,进行换基迭代。由于t 对应的常数项为0,所以迭代后常数项不变,全为非负数。利用修正单纯形法介绍的方法计算出迭代后基的逆阵,对其他为基变量的人工变量都做同样的变换,直到所有人工变量全部退基。以此时的基作为(4的初始可行基 B 0,转第三步。第三步:去掉所有的人工变量,将目标函数行换为(4的目标函数行的数字,以 B 0为初始可行基,计算此时非基变量的检验数,继续用修正单纯形法求解。当所有

12、非基变量的检验数全为非负数时,(4的目标值H 1-H 2=H 达到最优,此时松弛变量的检验数对应为线性规划模型(2的最优解(v *,u *。为了求出v *及u *,采用的方法是:通过修正单纯形法求出H *之后,根据对偶理论可得到前m 个松弛变量的检验数对应于v *,后s 个松弛变量的检验数对应于u *。由H *得到v *及u *这一过程计算量很小,不超过o(m +s 。3 算例设有7个决策单元(DM UA 、B 、C 、D 、E 、F 、G ,两个输入指标,一个输出指标。AB C D E F G 输入147842103输入23312417输出1111111以DM UA 为例,对其原始CCR 模

13、型做Charnes -Cooper 变换得到线性规划模型,将该线性规划模型的对偶模型化为标准型(89第6期 晏华辉,等:关于求解DEA 原始CCR 模型中最优输入输出权重的方法¹注:这样的非基变量一定存在,若不然,即所有非基变量的系数全为0,则该方程是线性规划模型(7的多余方程,这与(7的系数矩阵的秩为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首先构造(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为非基变量的系数矩阵,B为基变量的系数矩阵,P为系数列向量。初始基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。计算非基变量检验数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,按照上面的顺序进行,可确定下一步的换出换入变量,进行迭代运算。经过三步迭代后,非基变量的检验数全为0,此时基变量为x3=(H1,K F,K G,人工变量已全部退基。基矩阵(B3的逆矩阵为,(B-13=-126513-326213326-2131,去掉人工变量t-1、t-2和t+,将目标函数行的数字换成(8目标函数行的数字,以x3为第二阶段的初始可行基,以B-13为初

16、始可行基的逆阵,开始第二阶段的迭代运算。经过两步迭代后,非基变量的检验数全为非负数,得到了DM UA的最优效率评价指数,此时基变量为(H1,K D,K E,松弛变量的检验数为(17,17,67分别对应的于所要求的输入1、输入2和输出的权重v*1、v*2、u*。4结束语本文将原始CCR模型变换为与之等价的线性规划模型,从该线性规划模型的对偶模型入手,利用对偶理论,给出了一种求解原始CCR模型中决策单元最优输入输出权重的方法。已有的逆DEA算法不需要知道权重,但它涉及所有的决策单元,计算量大。根据逆DEA的思想,可以从选定的决策单元入手,得到比已有逆DEA算法更简洁、计算效率更高的算法,但是改进的新算法依赖于该权重。因此该权重对改进逆DEA算法有着重要意义。参考文献1魏权龄.评价相对有效性的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