数据包络分析（DEA）——CCR模型

写在前面：

博主本人大学期间参加数学建模竞赛十多余次，获奖等级均在二等奖以上。为了让更多学生在数学建模这条路上少走弯路，故将数学建模常用数学模型算法汇聚于此专栏，希望能够对要参加数学建模比赛的同学们有所帮助。

目录

• 1. 模型原理
• • 1.1 模型介绍
  • 1.2 数据包络分析的CCR模型
  • • 1.2.1 投入导向的CCR模型
    • 1.2.2 产出导向的CCR模型
    • 2. 案例分析

      ---

      1. 模型原理

      1.1 模型介绍

        数据包络分析是以“相对效率”概念为基础，根据多指标投入和多指标产出对相同类型的单位进行相对有效性或效益评价的一种系统分析方法。

        DEA特别适用于具有多输入多输出的复杂系统，这主要体现在以下几点:

        (1)DEA以决策单位各输人/输出的权重为变量，从最有利于决策单元的角度进行评价，从而避免了确定各指标在优先意义下的权重。

        (2)假定每个输人都关联到一个或者多个输出，而且输入/输出之间确实存在某种关系，使用DEA方法则不必确定这种关系的显示表达式。

        DEA最突出的优点是无须任何权重假设，每一个输入/输出的权重不是根据评价者的主观认定，而是由决策单元的实际数据求得的最优权重。因此，DEA方法排除了很多主观因素，具有很强的客观性。

      1.2 数据包络分析的CCR模型

      DMU	m个投入	q个产出
      1	x 11 , ⋯   , x 1 m x_{11}, \cdots, x_{1 m} x11​,⋯,x1m​	y 11 , ⋯   , y 1 q y_{11}, \cdots, y_{1 q} y11​,⋯,y1q​
      ⋮ \vdots ⋮	⋮ \vdots ⋮	⋮ \vdots ⋮
      n	x n 1 , ⋯   , x n m x_{n1}, \cdots, x_{n m} xn1​,⋯,xnm​	y n 1 , ⋯   , y n q y_{n1}, \cdots, y_{n q} yn1​,⋯,ynq​

        设有n个决策单元（DMC），每个决策单元都有 m 种投入和 q 种产出，设 x i j ( i = 1 , ⋯   , n ; j = 1 , ⋯   , m ) x_{i j}(i=1, \cdots, n ; j=1, \cdots, m) xij​(i=1,⋯,n;j=1,⋯,m)表示第i个决策单元的第i种投入量， y i j ( i = 1 , ⋯   , n ; r = 1 , ⋯   , q ) y_{i j}(i=1, \cdots, n ; r=1, \cdots, q) yij​(i=1,⋯,n;r=1,⋯,q)表示第 j 个决策单元的第 r 种产出量； v j ( j = 1 , ⋯   , m ) v_{j}(j=1, \cdots, m) vj​(j=1,⋯,m)表示第i 种投入的权值， u r ( r = 1 , ⋯   , q ) u_{r}(r=1, \cdots, q) ur​(r=1,⋯,q)表示第 r 种产出的权值；向量 X i , Y i ( i = 1 , ⋯   , n ) X_{i}, Y_{i}(i=1, \cdots, n) Xi​,Yi​(i=1,⋯,n)分别表示决策单元j的输入和输出向量，则 X i = ( x i 1 , ⋯   , x i m ) X_{i}=\left(x_{i 1}, \cdots, x_{i m}\right) Xi​=(xi1​,⋯,xim​)， Y i = ( y i 1 , ⋯   , y i q ) Y_{i}=\left(y_{i 1}, \cdots, y_{i q}\right) Yi​=(yi1​,⋯,yiq​)。

        决策单元 i 的评价效率指数可以使用产出和投入的比例衡量，则第 k 个决策单元的产出投入比为 h k = u 1 y k 1 + u 2 y k 2 + ⋯ + u q y k r v 1 x k 1 + v 2 x k 2 + ⋯ + v m x k j = u r Y k T v j X k T h_{k}=\frac{u_{1} y_{k 1}+u_{2} y_{k 2}+\cdots+u_{q} y_{k r}}{v_{1} x_{k 1}+v_{2} x_{k 2}+\cdots+v_{m} x_{k j}}=\frac{ u_{r} Y_{k}^{T}}{ v_{j} X_{k}^{T}} hk​=v1​xk1​+v2​xk2​+⋯+vm​xkj​u1​yk1​+u2​yk2​+⋯+uq​ykr​​=vj​XkT​ur​YkT​​

      1.2.1 投入导向的CCR模型

        投入导向的CCR模型，是在给定投入的条件下最大化产出。评价决策单元k效率的数学模型为

      max ⁡ u Y k T v X k T \max \frac{u Y_{k}^{T}}{v X_{k}^{T}} maxvXkT​uYkT​​ s . t . { u r Y k T v j X k T ⩽ 1 v j ⩾ 0 , u r ⩾ 0 , j = 1 , ⋯   , m ; r = 1 , ⋯   , q s.t.\left\{\begin{array}{c}\frac{u_{r} Y_{k}^{T}}{v_{j} X_{k}^{T}} \leqslant 1 \\ v_{j} \geqslant 0, u_{r} \geqslant 0, j=1, \cdots, m ; r=1, \cdots, q\end{array}\right. s.t.{vj​XkT​ur​YkT​​⩽1vj​⩾0,ur​⩾0,j=1,⋯,m;r=1,⋯,q​

        由于该形式是非线性规划，因此将其转化为线性规划形式为

      max ⁡ u r Y k T \max u_{r} Y_{k}^{T} maxur​YkT​ s . t . { u r Y k T − v j X k T ⩽ 0 v j X k T = 1 v j ⩾ 0 , u r ⩾ 0 , j = 1 , ⋯   , m ; r = 1 , ⋯   , q s.t. \left\{\begin{array}{c}u_{r} Y_{k}^{T}-v_{j} X_{k}^{T} \leqslant 0 \\ v_{j} X_{k}^{T}=1 \\ v_{j} \geqslant 0, u_{r} \geqslant 0, j=1, \cdots, m ; r=1, \cdots, q\end{array}\right. s.t.⎩ ⎨ ⎧​ur​YkT​−vj​XkT​⩽0vj​XkT​=1vj​⩾0,ur​⩾0,j=1,⋯,m;r=1,⋯,q​

        由于对偶模型的决策变量中包含效率值，因此将上述模型转化为对偶形式为：

      min ⁡ θ \min \theta minθ s . t . { ∑ i = 1 n λ i x i j ⩽ θ x i j ∑ i = 1 n λ i y i r ⩽ y k r λ i ⩾ 0 , j = 1 , ⋯   , m ; r = 1 , ⋯   , q s.t. \left\{\begin{array}{c}\sum_{i=1}^{n} \lambda_{i} x_{i j} \leqslant \theta x_{i j} \\ \sum_{i=1}^{n} \lambda_{i} y_{i r} \leqslant y_{k r} \\ \lambda_{i} \geqslant 0, j=1, \cdots, m ; r=1, \cdots, q\end{array}\right. s.t.⎩ ⎨ ⎧​∑i=1n​λi​xij​⩽θxij​∑i=1n​λi​yir​⩽ykr​λi​⩾0,j=1,⋯,m;r=1,⋯,q​ 其中， k = 1 , ⋯   , n k=1, \cdots, n k=1,⋯,n

        在对偶规划中， λ \lambda λ表示DMU的线性组合系数，参数 θ \theta θ即为效率值，其范围在0到1之间。

      1.2.2 产出导向的CCR模型

      产出导向的CCR模型，是在给定产出条件下最小化投入，其最终的对偶模型如下：

      max ⁡ ϕ \max \phi maxϕ s . t . { ∑ i = 1 n λ i x i j ⩽ x i j ∑ i = 1 n λ i y i r ⩾ ϕ y k r λ i ⩾ 0 , j = 1 , ⋯   , m ; r = 1 , ⋯   , q s.t.\left\{\begin{array}{c}\sum_{i=1}^{n} \lambda_{i} x_{i j} \leqslant x_{i j} \\ \sum_{i=1}^{n} \lambda_{i} y_{i r} \geqslant \phi y_{k r} \\ \lambda_{i} \geqslant 0, j=1, \cdots, m ; r=1, \cdots, q\end{array}\right. s.t.⎩ ⎨ ⎧​∑i=1n​λi​xij​⩽xij​∑i=1n​λi​yir​⩾ϕykr​λi​⩾0,j=1,⋯,m;r=1,⋯,q​ 其中， k = 1 , ⋯   , n k=1, \cdots, n k=1,⋯,n

      2. 案例分析

        （多指标评价问题） 某市教委需要对六所重点中学进行评价，其相应的指标如表所示。表中的生均投入和非低收入家庭百分比是输入指标，生均写作得分和生均科技得分是输出指标。请根据这些指标，评价哪些学校是相对有效的。

      

        该案例中，决策单元数量为6，投入指标数和产出指标数均为2。

      根据投入导向的CCR对偶模型，利用Matlab编程求解得到6个最优目标值分别为：

      1，0.9096，0.9635，0.9143，1，1

      根据产出导向的CCR对偶模型，利用Matlab编程求解得到6个最优目标值也是：

      1，0.9096，0.9635，0.9143，1，1

      可见决策单元1，5，6的投入产出最有效率，均为1，因此学校A，E，F是DEA有效的。

      投入导向的CCR模型Matlab程序如下：

      clc,clear
      X=[89.39 86.25 108.13 106.38 62.4 47.19;
          64.3 99 99.6 96 96.2 79.9];
      Y=[25.2 28.2 29.4 26.4 27.2 25.2;
          223 287 317 291 295 222];
      n=size(X,2)     % 决策单元数
      m=size(X,1)     % 投入指标数
      q=size(Y,1)     % 产出指标数
      %投入导向的CCR模型
      w = [];
      for i = 1:n
          f = [zeros(1,n) 1];   % 定义目标函数
          Aeq = [];             % 没有等式约束
          beq = [];
          LB = zeros(n+1,1);    % 指定下界
          UB = [];
          A = [X -X(:,i);-Y zeros(q,1)];         % 设定不等式约束
          b = [zeros(m,1);-Y(:,i)];
          w(:,i) = linprog(f,A,b,Aeq,beq,LB,UB); % 模型求解
      end    
      CCR_IN = w(n+1,:)'             % 结果输出
      

      产出导向的CCR模型Matlab程序如下：

      clc,clear
      X=[89.39 86.25 108.13 106.38 62.4 47.19;
          64.3 99 99.6 96 96.2 79.9];
      Y=[25.2 28.2 29.4 26.4 27.2 25.2;
          223 287 317 291 295 222];
      n=size(X,2)     % 决策单元数
      m=size(X,1)     % 投入指标数
      q=size(Y,1)     % 产出指标数
      %产出导向的CCR模型
      w = [];
      for i = 1:n
          f = [zeros(1,n) -1];   % 定义目标函数
          Aeq = [];             % 没有等式约束
          beq = [];
          LB = zeros(n+1,1);    % 指定下界
          UB = [];
          A = [X zeros(m,1);-Y Y(:,i)];         % 设定不等式约束
          b = [X(:,i)' zeros(1,q)]';
          w(:,i) = linprog(f,A,b,Aeq,beq,LB,UB); % 模型求解
      end    
      CCR_OUT = 1./w(n+1,:)'             % 结果输出