陶 杰，盧 超

(1.上海理工大學管理學院，上海 200093；2.上海大學管理學院，上海 200444)

?

整數(shù)DEA問題的求解方法與改進

陶 杰1，盧 超2

(1.上海理工大學管理學院，上海 200093；2.上海大學管理學院，上海 200444)

整數(shù)數(shù)據(jù)包絡(luò)分析(IDEA)是一種用于當投入產(chǎn)出指標為整數(shù)時，分析決策單元(DMU)相對效率的評價方法。我們針對傳統(tǒng)LV模型和KKM模型存在無法得到最優(yōu)改進點和高估效率值的不足，提出RKKM模型和RDI模型?；赗KKM模型和RDI模型我們進一步提出“三步法”來解決IDEA問題?！叭椒ā钡牡谝徊胶偷诙椒謩e求解RKKM模型和RDI模型來得到各自的最優(yōu)值，第三步通過對比這兩個模型的最優(yōu)值來得到每個DMU最終的最優(yōu)投影點。為了驗證“三步法”的先進性，以伊朗42所高校效率評價的經(jīng)典算例測算、對比上述各模型的數(shù)值效果，發(fā)現(xiàn)“三步法”有效解決了傳統(tǒng)IDEA模型的不足。“三步法”不僅擁有堅實的理論基礎(chǔ)，而且計算上容易實現(xiàn)，因此它可以作為解決IDEA問題的一個重要的工具。

整數(shù)數(shù)據(jù)包絡(luò)分析；效率評價；混合整數(shù)線性規(guī)劃；“三步法”

1 引言

數(shù)據(jù)包絡(luò)分析(簡稱DEA)是一種評價和衡量一組多投入和多產(chǎn)出的決策單元的相對效率的方法[3]，目前已經(jīng)有加法模型、混合模型、交叉效率模型以及置信域模型等[16-19]，用以解決各種實際問題。然而，現(xiàn)實生活中，有一些情形會涉及到輸入變量或輸出變量是整數(shù)的情形。由于把目標值(實數(shù))四舍五入后得到最近的整數(shù)點并不能作為決策單元的效率改進點[10]，因此當用傳統(tǒng)DEA模型求解出的目標值不是整數(shù)的時候，這些目標值就變得沒有實際意義。

隨著越來越多的研究者們逐漸意識到傳統(tǒng)DEA模型在解決整數(shù)數(shù)據(jù)包絡(luò)分析(IDEA)問題方面存在局限性后，出現(xiàn)了很多新的IDEA模型和理論。總體來看，IDEA的發(fā)展過程可以分為三個階段：①第一個階段是IDEA問題的提出，研究者們主要聚焦于分類變量問題的解決，通過在原始模型中引入二進制的分類啞變量，將原始模型轉(zhuǎn)化成一個混合整數(shù)線性規(guī)劃模型(簡稱MILP)，詳見Banker和Morey[2]。②第二個階段是IDEA的發(fā)展期，方法探索日漸增多并逐步拓展應(yīng)用，以Lozano和Villa[12]提出的LV模型(取兩位作者姓名的前兩個字母)為代表。LV模型同時考慮分類變量和所有屬性為整數(shù)的變量，相對第一階段的模型有了顯著進步，但由于研究脫離了IDEA問題的經(jīng)濟背景、無法獲得合適的最優(yōu)解等缺陷而受到批評。③第三個階段是IDEA的完善，以Kuosmanen和Matin[10]、Martin和Kuosmanen[13]為代表。他們提出了一套完整的IDEA公理體系、構(gòu)建了整數(shù)數(shù)據(jù)包絡(luò)生產(chǎn)可能集，并基于Farrell的投入效率測量方法提出了新的MILP模型，即著名的KKM(Kuosmanen Kazemi Martin，簡稱KKM)模型。在KKM模型的基礎(chǔ)上，研究者們進一步提出了魯棒混合IDEA模型[5]、雙向投影IDEA模型[20]等，推動了IDEA理論的發(fā)展。同時KKM模型還被廣泛應(yīng)用于許多行業(yè)，比如衡量第29屆奧運會參與國的績效[15]、賓館的投入產(chǎn)出效率[14]以及希臘體育事業(yè)的資本預(yù)算[12]等等。

然而，當前主流的KKM模型求解IDEA問題的有效性受到了越來越多的質(zhì)疑。如Khezrimotlagh等[6,8]對Kuosmanen和Matin[10]以及Martin和Kuosmanen[13]中提出的模型作出評論，并用一個反例證明了KKM模型得到的最優(yōu)點并不一定總是優(yōu)于LV模型得到的最優(yōu)點。同時，Kuosmanen在比較LV模型和KKM模型時候存在不一致性，即KKM的輸出目標值假定是實數(shù)，而LV的輸出目標值假定是整數(shù)，基于這種不一致性的模型比較并無實際意義。

基于此，本文將針對解決IDEA問題的傳統(tǒng)模型的不足，構(gòu)建RKKM模型(Rectified KKM, 修正KKM模型)和RDI模型(Radial Distance-based Integer-valued, 基于徑向距離的IDEA模型)進行修正，并綜合二者優(yōu)勢提出“三步法”。進一步，從理論和算例兩方面對比“三步法”與傳統(tǒng)模型在解決IDEA問題方面的異同，從而驗證“三步法”的先進性。

本文主體內(nèi)容結(jié)構(gòu)安排如下：第二節(jié)闡述解決IDEA問題的傳統(tǒng)LV模型和KKM模型及其存在的不足；第三節(jié)構(gòu)建RKKM模型和RDI模型對傳統(tǒng)模型進行修正(RDI是RKKM的補充)，并提出基于RKKM和RDI的“三步法”用以解決IDEA問題；第四節(jié)沿用Kuosmanen和Matin[10]中42所大學的典型算例進行實證研究，驗證“三步法”的優(yōu)勢。

2 解決IDEA問題的傳統(tǒng)模型

解決IDEA問題的傳統(tǒng)模型主要包括Lozano和Villa[11]提出的LV模型以及Kuosmanen和Martin[10]提出的KKM模型。本節(jié)分成兩個部分論述，第一部分簡要介紹LV模型及其缺陷，并據(jù)此引出KKM模型；第二部分介紹KKM模型，并分析其不足。DEA模型提出的基本邏輯思路是從公理性的假設(shè)條件出發(fā)，構(gòu)建生產(chǎn)可能集，再選擇效率測量方式，最后構(gòu)建模型，本節(jié)亦按此思路進行分析。IDEA公理性的假設(shè)條件可以參見Kuosmanen和Martin[10]。

2.1LV模型及其缺陷

LV模型由Lozano和Villa[11]提出，其基于的生產(chǎn)可能集為：

(1)

(2)

這里θ為徑向改進距離，即通常所說的Farrell測度。據(jù)此LV-I模型(由于這里投入變量和產(chǎn)出變量的目標值都要求為整數(shù)，為了區(qū)分某些只要求投入變量為整數(shù)的情形，我們稱此LV模型為LV-I模型)可以表述為：

(3)

2.2KKM模型及其缺陷

基于LV模型的缺陷，Kuosmanen和Matin[10]提出了KKM模型，其生產(chǎn)可能集和效率測量方式為：

(4)

其中，

(5)

(6)

當然，實際應(yīng)用中也存在只要求投入變量為整數(shù)而產(chǎn)出變量不要求為整數(shù)的情形，Kuosamen和Martin[10]指出也可以構(gòu)建此種情形下的KKM模型(稱為KKM-R模型)：

(7)

由于KKM-I和KKM-R的性質(zhì)是相同的，為了論述方便，在分析KKM模型缺陷的時候僅以KKM-R模型為例，并將KKM-R簡稱為KKM。

KKM模型的提出是為了彌補LV模型在高估效率值和無法得到最優(yōu)改進點兩方面缺陷而提出的，但遺憾的是KKM模型并沒有解決這兩個缺陷。對于高估效率值的缺陷，我們在后文詳細論述；對于無法得到最優(yōu)改進點的缺陷，Khezrimotlagh等[6,8]進行了論述并提出了一個反例。該反例說明某些情形下KKM模型得到的最優(yōu)點要差于LV模型得到的最優(yōu)點。因此，我們有必要對KKM模型進行改進。

3 解決IDEA問題的改進方法

前述分析發(fā)現(xiàn)，LV模型存在高估效率值以及模型得到的改進點不是最優(yōu)改進點的不足，但“致力于”對此進行改進的KKM模型卻沒能有效解決。為此，本節(jié)擬提出一種新的方法——“三步法”來彌補LV模型的兩個缺陷，從而有效解決IDEA問題?！叭椒ā钡幕A(chǔ)是RKKM模型和RDI模型；其中，RKKM模型是對KKM模型的修正，可以解決LV模型的第一個方面的不足，RDI模型是對RKKM模型的補充，可以解決LV模型的第二個不足。因此，綜合使用RKKM模型和RDI模型可以解決LV模型的兩方面不足，進而解決IDEA問題。本節(jié)分成三個部分進行論述，第一部分闡述RKKM模型的原理、優(yōu)勢和不足，第二部分闡述RDI模型的原理及其可以作為RKKM模型補充的原因，第三部分基于RKKM模型和RDI模型構(gòu)建“三步法”，解決IDEA問題。

3.1RKKM模型

由2.2節(jié)可知，Kuosamen和Martin[10]試圖通過構(gòu)建KKM模型來彌補LV模型的兩方面不足，盡管提供了很好的思路，但效果仍有待改進。鑒于此，本文通過對KKM模型進行修正得到RKKM模型，從而解決LV模型的第一個方面的不足。

圖1顯示的KKM模型(左圖)和RKKM模型(右圖)在該算例下尋求最優(yōu)點的示意圖。圖中折線ABN由DMU A 和DMU B組成，代表規(guī)模報酬不變(CRS)情形下的DEA生產(chǎn)前沿面。KKM模型尋找最優(yōu)點的過程如下：第一步，找到一組準最優(yōu)點集合，用S1來表示。在圖1(左)中假設(shè)被評價單元是DMU C，則MBCN區(qū)域內(nèi)所有的整數(shù)點都是準最優(yōu)點。第二步，將第一步中得到的所有準最優(yōu)點都投影到徑向射線上(即圖1(左)中的虛線)，并選擇投影點距離原點最近的點，將其集合標記為S2，這里S2由B點和B’點組成。第三步，在集合S2中找到生產(chǎn)前沿面和徑向射線的l1范數(shù)最大的點，并將其作為最終選定的點。可見，圖1(左)中最終選取的點為B和B’。

基于此，我們提出改進后的KKM模型，即RKKM模型如下(當產(chǎn)出的目標值假定為實數(shù)，記為RKKM-R)：

圖1 KKM和RKKM模型尋求最優(yōu)點示意圖(雙投入—單產(chǎn)出算例)

(8)

另外，由于有時候產(chǎn)出的目標值也要求是整數(shù)，因此還可以在RKKM-R模型的基礎(chǔ)上對產(chǎn)出再增添一些約束，使其變?yōu)镽KKM-I模型：

(9)

下面我們來討論各模型之間的關(guān)系。2.2節(jié)的分析可知，KKM模型本是致力于解決LV模型的不足，但其改進過程本身并不正確。因此，本文僅討論RKKM模型和LV模型之間的關(guān)系。

首先我們討論LV-R與RKKM-R之間的關(guān)系?？紤]如下兩個集合：

(10)

(11)

或

定理1. RKKM-R模型的最優(yōu)解和LV-R模型的最優(yōu)解是相等的。

由引理1有

因此RKKM-R模型的最優(yōu)解與LV-R模型的最優(yōu)解相等。證畢。

從定理1可以看出，當產(chǎn)出的目標值假定為實數(shù)的時候，RKKM-R模型得到的最優(yōu)點和LV-R模型得到的最優(yōu)點是相同的。

接下來，我們討論RKKM-I模型和LV-I模型的關(guān)系?？紤]如下2個集合：

(12)

(13)

定理2LV-I模型得到的最優(yōu)點要不會優(yōu)于RKKM-I模型得到的最優(yōu)點。

基于以上分析和對Khezrimotlaghet al.(2013)反例的測算，我們發(fā)現(xiàn)RKKM模型完全解決了反例中的問題。

3.2RDI模型

從3.1節(jié)的分析中可以看出，RKKM模型解決了LV模型的第一個缺陷，即RKKM模型可以得到最優(yōu)改進點。但是它依然存在兩方面的問題：①高估效率值；②丟失潛在最優(yōu)改進點。具體來說(如圖2所示)。

圖2 高估效率值和丟失潛在最優(yōu)點示意圖

基于此，仍需要對RKKM模型進行修正或補充，解決RKKM模型的兩個不足。本文構(gòu)建一種新的模型—基于徑向距離的IDEA模型(簡稱RDI模型)，作為RKKM模型的有效補充。RDI模型表述如下(RDI模型也可以分為只要求投入變量目標值為整數(shù)情形RDI-R和同時要求投入產(chǎn)出變量目標值均為整數(shù)情形RDI-I兩種；由于第二種情形應(yīng)用范圍更廣，本文僅考慮RDI-I模型，并用RDI代替RDI-I。本小節(jié)后面分析中的RKKM和RDI分別指的是RKKM-I和RDI-I，由于RKKM-R和RDI-R的分析與此類似，所以不再重復(fù)討論)：

(14)

從上述分析中可以看出RDI模型可以彌補RKKM模型的兩個缺陷。然而，RDI模型只可以作為RKKM模型的補充，并不可以替代RKKM模型。我們將通過討論RKKM模型和RDI模型最優(yōu)解之間的關(guān)系來說明這個問題。

該最優(yōu)解要優(yōu)于

從定理3中我們可以知道RKKM模型得到的最優(yōu)點總是不差于RDI模型的最優(yōu)解。也就是說RDI模型求得的最優(yōu)改進點只能是RKKM模型求出的最優(yōu)改進點的補充，不能作為其替代。

3.3基于RKKM和RDI的“三步法”

從3.2節(jié)的分析中可以看出，RKKM模型和RDI模型的結(jié)合可以找到所有最優(yōu)改進點?；诖?，本文提出用以解決IDEA問題的“三步法”：

“三步法”的操作過程可以簡單描述為先用RKKM模型求解找到最優(yōu)改進點；再用RDI模型對其進行檢驗，判斷是否存在丟失最優(yōu)改進點的情形。如果不存在丟失情形，那么最終的最優(yōu)改進點只有1個，即RKKM模型的解；如果存在丟失情形，RDI模型的解即為丟失的最優(yōu)改進點，則最終的最優(yōu)改進點有2個，即RKKM模型的解和RDI模型的解。至此，IDEA問題得以解決。

4 應(yīng)用

本文以經(jīng)典算例—評價伊朗的42所大學效率(該算例取自Kuosmanen和Martin[10]，是一個得到大多數(shù)IDEA研究者認可并使用其驗證模型優(yōu)劣的成熟算例)來闡述IDEA模型的應(yīng)用。模型中，輸入變量為博士生的人數(shù)(x1)、本科生的人數(shù)(x2)、碩士的人數(shù)(x3)，輸出變量有畢業(yè)生的人數(shù)(y1)、獲得獎學金的人數(shù)(y2)、科研成果的數(shù)量(y3)以及管理滿意度水平(y4)。算例的數(shù)據(jù)讀者可以參閱Kuosmanen和Martin[10]。①首先，對RKKM-R模型以及LV-R模型求得的最優(yōu)解進行了對比，發(fā)現(xiàn)二者的解是相等的，這和定理1的結(jié)論是一致的。②接下來，對RKKM-I模型以及LV-I模型求得的最優(yōu)解進行了對比，發(fā)現(xiàn)有17個決策單元的徑向效率值在RKKM-I模型和LV-I模型下是一樣的，在這17個決策單元中，有12個決策單元的最優(yōu)解也是完全相同的。其余的30個決策單元在RKKM-I模型下的最優(yōu)解不次于LV-I模型的最優(yōu)解，這與定理2的結(jié)論一致。③進一步，運用第3.3節(jié)中提出的“三步法”來比較RKKM-I模型的最優(yōu)解和RDI模型的最優(yōu)解。有17個決策單元，他們在上述兩個模型下的最優(yōu)解(效率值和最優(yōu)點均是一樣的)是一樣的；有13個決策單元的RKKM-I模型的最優(yōu)點(僅僅指的是最優(yōu)投影點)要優(yōu)于RDI模型；有一個決策單元，RKKM模型和RDI模型求得的最優(yōu)點是無法比較的，即為丟失的潛在最優(yōu)點。④最后，基于“三步法”給出每個決策單元的最終最優(yōu)投影點，可以發(fā)現(xiàn)，相比傳統(tǒng)的IDEA模型，“三步法”得出的最優(yōu)解更為優(yōu)秀，更為全面(由于篇幅原因，算例結(jié)果我們沒有在文中一一列出，有興趣的讀者可以郵件聯(lián)系作者)。

5 結(jié)語

本文基于前人對于IDEA問題的研究成果，從理論和應(yīng)用上對IDEA問題進行了改進，研究結(jié)論主要包括五個方面：

首先，引用Khezrimotlagh等人[8]的反例說明了KKM模型的不足，并從理論上對KKM模型進行改進，提出了RKKM模型，能夠有效解決傳統(tǒng)模型無法得到Pareto最優(yōu)點的問題。

其次，從理論和應(yīng)用上對比了RKKM模型和LV模型的性質(zhì)，發(fā)現(xiàn)RKKM-R模型的最優(yōu)值和LV-R模型的最優(yōu)值是相等的，而RKKM-I模型的最優(yōu)值不會差于LV-I模型的最優(yōu)值。

第三，針對RKKM-I模型存在可能丟失潛在的最優(yōu)點以及會高估效率值的問題，提出了有助于找回丟失的最優(yōu)點以及尋找合適的效率值的RDI模型。另外，通過對比RDI模型和RKKM-I模型的性質(zhì)，發(fā)現(xiàn)RDI模型得到的最優(yōu)點不會優(yōu)于RKKM-I模型的最優(yōu)點。

第四，將RKKM-I模型和RDI模型進行結(jié)合，提出了能夠有效尋找IDEA問題最優(yōu)點的“三步法”。

第五，從計算角度來看，“三步法”主要包括求解兩個混合線性整數(shù)規(guī)劃和比較兩組效率值，其計算復(fù)雜度不會高于統(tǒng)IDEA問題傳處理方法的計算復(fù)雜度。因此，“三步法”易于求解和實現(xiàn)。

最后，引用Kuosmanen和Martin[10]著名的評價42個高校效率的案例，對比本文構(gòu)建的模型、提出“三步法”與傳統(tǒng)模型的計算結(jié)果，從而驗證了本文理論成果的先進性。

[1] Adolphson D L, Cornia G C, Walters L C. A unified framework for classifying DEA models[J]. OperationalResearch, 1991, 90: 647-657.

[2] Banker R D, Morey R C. The use of categorical variables in data envelopment analysis[J]. ManagementScience, 1986, 32(12): 1613-1627.

[3] Charnes A, Cooper W W, Rhodes E. Measuring the efficiency of decision making units[J]. European Journal of Operational Research, 1978, 2(6): 429-444.

[4] Chen C M, Du Juan, Huo Jiazhen, et al. Undesirable factors in integer-valued DEA: Evaluating the operational efficiencies of city bus systems considering safety records[J]. Decision Support Systems, 2012, 54(1): 330-335.

[5] Du Juan, Chen C M, Chen Yao, et al. Additive super-efficiency in integer-valued data envelopment analysis[J]. European Journal of Operational Research, 2012, 218(1): 186-192.

[6] Khezrimotlagh D, Salleh S, Mohsenpour Z. A comment on theory of integer-valued data envelopment analysis[J]. Applied Mathematical Sciences, 2012, 6(116): 5769-5774.

[7] Khezrimotlagh D. Differences between real and integer production possibility sets in data envelopment analysis[J]. arXiv preprint arXiv:1501.07401, 2015.

[8] Khezrimotlagh D, Salleh S, Mohsenpour Z. A note on integer-valued radial model in DEA[J]. Computers & Industrial Engineering, 2013, 66(1): 199-200.

[9] Kuosmanen T, Keshvari A, Matin R K, et al. Discrete and integer valued inputs and outputs in data envelopment analysis[M]//Zhu J.Data envelopment analysis.New Yor R:Springer,2015,67-103.

[10] Kuosmanen T, Matin R K. Theory of integer-valued data envelopment analysis[J]. European Journal of Operational Research, 2009, 192(2): 658-667.

[11] Lozano S, Villa G. Data envelopment analysis of integer-valued inputs and outputs[J]. Computers & Operations Research, 2006, 33(10): 3004-3014.

[12] Lozano S, Villa G, Canca D. Application of centralised DEA approach to capital budgeting in Spanish ports[J]. Computers & Industrial Engineering, 2011, 60(3): 455-465.

[13] Matin R K, Kuosmanen T. Theory of integer-valued data envelopment analysis under alternative returns to scale axioms[J]. Omega, 2009, 37(5): 988-995.

[14] Wu Jie, Liang Liang, Song H. Measuring hotel performance using the integer DEA model[J]. Tourism Economics, 2010, 16(4): 867-882.

[15] Wu Jie, Zhou Zhixiang, Liang Liang. Measuring the performance of nations at the Beijing Summer Olympics using an integer-valued DEA model[J]. Journal of Sports Economics, 2009, 11(5): 1-18.

[16] 畢功兵, 梁樑, 楊鋒. 兩階段生產(chǎn)系統(tǒng)的 DEA 效率評價模型[J]. 中國管理科學, 2007, 15(2): 92-96.

[17] 董進全, 邱程程, 馬占新, 等. 擬凹生產(chǎn)函數(shù)的分區(qū)域估計[J]. 中國管理科學, 2015, 23(3): 32-41.

[18] 馬璐, 高李昊. 基于 NOM-Hybrid DEA 和 Meta-frontier 的效率模型研究[J].中國管理科學,2016, 24 (3): 149-158.

[19] 石曉, 謝建輝, 李勇軍, 等. 非合作博弈兩階段生產(chǎn)系統(tǒng) DEA 并購效率評價[J]. 中國管理科學, 2015, 23(7): 60-67.

[20] 周志祥. 整數(shù)DEA理論、方法及其應(yīng)用研究[D]. 合肥：中國科學技術(shù)大學，2014.

Methods Addressing Integer-valued DEA Problems and Improvements

TAOJie1，LUChao2

(1.Business School, University of Shanghai forScience and Technology, Shanghai 200093, China；2.School of Management, Shanghai University, Shanghai 200444,China)

The Integer-valued Data Envelopment Analysis (IDEA) is a common method to evaluate the relative efficiencyamong different Decision Making Units (DMUs) by using integer-valued inputs and outputs. By identifying such deficiencies of two classical IDEA models (e.g. Lozano & Villa’s model (LV), Kuosmanen&Kazemi Martin’s model (KKM)) as the overestimation of efficiencies and the lack of ability to obtain optimal projection points, this paper constructed a rectified KKM model (RKKM) and a radial-based distance integer-valued DEA model (RDI) to address the deficiencies mentioned above. Further, a “three-step method” based on both RDI model and RKKM model was suggested to solve IDEA problems. In the first and second steps, RKKM and RDI were adopted separately to get their respective optimal values, and this was followed by the optimal value comparison to determine the final projection values of each DMU in the third step. To verify the effectiveness of our proposed approach, the famous example of 42 university departments of IAUK was used as study samples. Empirical results show that our “three-step method” outperforms the classical IDEA models and overcomes the two shortcomings mentioned above.Owning a solid theoretical foundation, the easily implemented “three-step method” could be used as a new powerful tool to address IDEA problems.

integer-valued data envelopment analysis; efficiency evaluation; mixed-integer linear programming; “Three-step Method”

1003-207(2017)06-0151-10

10.16381/j.cnki.issn1003-207x.2017.06.016

2016-04-10；

：2016-06-12

國家自然科學基金資助青年項目(71601117)；上海市浦江人才計劃項目(15PJC050)；上海高校青年教師培養(yǎng)計劃項目(ZZSD15096)

盧超(1986-)，男(漢族)，山東泰安人，上海大學管理學院講師、碩士生導(dǎo)師，管理學博士，研究方向：管理科學與工程、創(chuàng)新管理與政策等，E-mail：06luchao@163.com.

F224.0

：A