2

I am studying Data Envelopment Analysis and the CCR model from Cooper, W. W., Seiford, L. M., Tone, K., & Cooper, W. W. (2006). Introduction to data envelopment analysis and its uses : With DEA-solver software and references. Springer.

I struggle to understand how we move from the $LP_o$ to its dual $DLP_o$.

Here is the primal :

\begin{align} \max_{v,u} & uy_o \\ & \text{s.t. } vx_o = 1 \\ & -vX + uY \leq 0 \\ & v \geq 0, u \geq 0 \end{align} And its dual :

\begin{align} \min_{\theta,\lambda} & \theta & \\ & \text{s.t. } \theta x_o - X\lambda \geq 0 \\ & Y\lambda \geq y_o \\ & \lambda \geq 0 \end{align}

I tried to apply the general definition of a dual to its primal to this specific case but could not get the proper answer.

Any thoughts ?

Thanks

MattTct
  • 23

1 Answers1

1

With the corresponding dual variables the primal program is

\begin{align*}{} & \max_{v,u} \ \ \ \color{orange}{ y_o}u+ \color{red}{ 0}v \\ & \qquad \quad \color{orange}{ 0}u+\color{red}{ x_o}v = \color{limegreen}1 \quad (\theta)\\ & \ \ \ \qquad \color{orange}{ Y}u- \color{red}{ X}v \leq \color{limegreen}0 \quad (\lambda) \\ & \qquad \quad v \geq 0, u \geq 0\end{align*}

I assume, that all variables and coefficients are no vectors. To formulate the constraints of the dual program you focus on the coefficients which are in one column.

\begin{align*}{} & \min_{\lambda, \theta} \ \ \ \color{limegreen}{ 1}\theta+ \color{limegreen}{ 0}\lambda \\ & \qquad \quad \color{orange}{ 0}\theta+\color{orange}{ Y}\lambda \ \square{\ } \color{orange}{y_0} \quad (u)\\ & \ \ \qquad \color{red}{ x_0}\theta- \color{red}{ X}\lambda \ \square{\ } \color{red}0 \ \ \quad (v) \\ & \qquad \quad \theta \ \square{\ } 0, \lambda \ \square{\ } 0\end{align*}

I've left some blanks for the relation signs. To decide which one is the right one you can use a table. For instance this one.

callculus42
  • 30,550
  • Thanks, the color code and the table help a lot. Lower case variables are actually vectors and upper case variables are matrices. I guess it doesn't have much incidence on the results, we just can't reorder the terms, right ? I am still a little confuse regarding the signs, in particular how we move from an = (in the theta constraint in PL) to a >= ? – MattTct Dec 15 '23 at 12:42
  • Yes, then we cannot reorder the factors. // It's a little bit different with the signs. The equality constraints in the primal program creates the free variable $\theta$ in the dual program. – callculus42 Dec 15 '23 at 13:23