Actualmente estoy estudiando la teoría de la dualidad (para la programación lineal) y me he encontrado con una confusión. La teoría de la dualidad proporciona una herramienta útil para comprobar si una solución primaria dada es óptima. Una solución primaria dada es óptima si la solución dual correspondiente es factible. Ahora, quiero comprobar si la solución de mi primal es óptima sin tener que resolverla mediante el método simplex. Puedo escribir la formulación dual correspondiente, pero no veo cómo obtener las variables duales correspondientes a partir de una solución primal para comprobar si se viola una restricción dual.
Respuesta
¿Demasiados anuncios?
Teniendo en cuenta el primario: \begin{equation*} \begin{array}{lll} \textrm{maximize } & \sum\limits_{j=1}^n c_j x_j&\\ \textrm{subject to} & \sum\limits_{j=1}^n a_{ij} x_j \leq b_i & \textrm{ for } i=1,2\ldots,m\\ & x_j \geq 0 & \textrm{ for } j=1,2\ldots,n \end{array} \end{equation*}
El doble es: \begin{equation*} \begin{array}{lll} \textrm{minimize } & \sum\limits_{i=1}^m b_i y_i&\\ \textrm{subject to} & \sum\limits_{i=1}^m a_{ij} y_i \geq c_j & \textrm{ for } j=1,2\ldots,n\\ & y_i \geq 0 & \textrm{ for } i=1,2\ldots,m \end{array} \end{equation*}
Ahora, dada una solución $x^*$ Utiliza el teorema de la holgura complementaria.
O bien la variable principal es cero, o la restricción dual asociada es estricta: \begin{equation} {x^*_j = 0 \textrm{ or } \sum_{i=1}^m a_{ij}y^*_i = c_j \textrm{ (or both) for } j=1,2,\ldots,n} \end{equation} O bien la restricción primaria es estricta, o la variable dual asociada es cero: \begin{equation} \label{eq:CSC:2} {\sum_{j=1}^n a_{ij}x^*_j = b_i \textrm{ or } y^*_i = 0 \textrm{ (or both) for } i=1,2,\ldots,m} \end{equation}
Si su solución $x^*$ es básico, deberías encontrarte con un sistema de ecuaciones con $n$ ecuaciones y $n$ incógnitas. Al resolverla se obtiene una solución dual. Si es factible en el dual, $x^*$ es óptima.
