Esencia de la teoría de dualidad (I)

Al usar nuestra forma estándar para el problema primal, que se muestra a la izquierda (tal vez después de hacer la conversión de una a otra forma), su problema dual tiene la forma que se muestra a la derecha.

Teoría de dualidad y análisis de sensibilidad

Uno de los descubrimientos más importantes durante el desarrollo inicial de la programación lineal fue el concepto de dualidad y sus muchas e importantes ramificaciones. Este descubrimiento reveló que, asociado a todo problema de programación línea, existe otro problema lineal llamado dual. Las relaciones entre el problema dual y el original (llamado primal) son extremadamente útiles en una gran variedad de situaciones. Por ejemplo,se verá que de hecho la solución óptima del problema dual es la que proporciona los precios sombra que se describieron en la seccion 4.7. En este capítulo se presentarán muchas otras aplicaciones valiosas.

Uno de los papeles clave que juega la teoría de dualidad es la interpretación y realización del análisis de sensibilidad. Como ya se mencionó en las secciones 2.3, 3.3 y 4.7, el análisis de sensibilidad consitituye una parte muy importante en casi todos los estudios de programación lineal. Dado que algunos o todos los valores de los parámetros que se emplean en el modelo original son sólo estimaciones de condiciones futuras, es necesario investigar el efecto que se tendría sobre la solución óptima en caso de que prevalecieran otras condiciones. Aún más, ciertos valores de estos parámetros (como la cantidad de recursos) pueden representar decisiones de la gerencia, en cuyo caso su elección debe ser el punto más importante de la investigación y, por supuesto, se estudia a través del análisis de sensibilidad.

Para mayor claridad de exposición, las tres primeras secciones presentan la teoría de dualidad bajo la suposición de que el problema primal de programación líneal está en nuestra forma estándar (pero sin restricción de que las bi deben ser positivas). Más adelante, en la sección 6.4 se analizan otras formas. El capítulo comienza con una introducción de la esencia de la teoría de dualidad y sus aplicaciones. Después se describe la interpretación económica del problema dual (Sec. 6.2) y se profundiza en las relaciones entre el problema primal y el dual (Sec. 6.3). La sección 6.5 hace hincapié en la importancia de la teoría de dualidad para el análisis de sensibilidad. El procedimiento básico para el análisis de sensibilidad (que se basa en la idea fundamental de la sección 5.3) se resume en la sección 6.6 y se ejemplifica en la sección 6.7.

Conclusiones de la Teoría del método símplex

Aunque el método símplex es un procedimiento algebraico, está basado en algunos conceptos geométricos bastante sencillos. Estos conceptos permiten al algoritmo examinar un número relativamente pequeño de soluciones básicas factibles antes de alcanzar e identificar la solución óptima.

El método símplex revisado, proporciona una manera efectiva de adaptar el método símplex para programarlo en una computadora.

La tabla símplex final incluye la información completa para poderla reconstruir algebraicamente a partir de la tabla símplex inicial. Esta idea fundamental tiene aplicaciones muy importantes, en especial en el análisis de posoptimalidad.

Aplicaciones de la idea fundamental (III)

(Si cualquiera de estos nuevos valores fuera negativo y, por lo tanto no factible, entonces se aplicaría la técnica de reoptimización descrita en la sección 4.7, comenzando con esta tabla final revisada.) Al aplicar el análisis incremental a la ecuación anterior de Z* también se obtiene.

La idea fundamental también se puede aplicar a la investigación de otro tipo de cambios en el modelo original de una manera muy parecida; ésta es la parte medular del procedimiento para el análisis de sensibilidad que se describirá en el capítulo 6.

También se podrá observar en el siguiente capítulo que la idea fundamental juega un papel clave en la útil teoría de dualidad par aun problema de programación lineal.

Aplicaciones de la idea fundamental (III)

Pro ejemplo, considérese el cambio de b2=12 a b2=13, tal y como se ilustra en la figura 4.3 para el problema de la Wyndor Glass Co. No es necesario resolver todo el problema para obtener la nueva solución óptima (x1, x2) = (5/3, 13/2) porque la idea fundamental proporciona en seguida los valores de las variables básicas (b*) en la tabla símplex final.

Aplicaciones de la idea fundamental (II)

Otro grupo de aplicaciones en extremo importantes incluye varios de las tareas de posoptimalidad (la técnica de reoptimización, el análisis de sensibilidad y la programación lineal parámetria, descritas en la sección 4.7) que investigan el efecto que causan uno o más cambios en el modelo original. En particular, supóngase que ya se aplicó el método símplex para obtener una solución óptima (inclusive y* y S*)para el modelo original y que estos cambios se hacen después. Cuáles serián los cambios resultantes en la tabla final si se aplicara exactamente la misma secuencia de operaciones algebraicas a la tabla inicial revisada? Como y* y S* no cambian, la idea fundamental revela de inmediato la respuesta.

Aplicaciones de la idea fundamental (I)

La idea fundamental tiene una gran variedad de aplicaciones en programación lineal. Una de ellas influye el método símplex revisado. Según se describió en la sección anterior (véase la tabla 5.7), este método utiliza S* = B^-1 y la tabla símplex inicial para calcular todos los números relevantes de la tabla símplex actual en cada iteración. Va aun más lejos que la idea fundamental al utilizar B^-1 para calcular el mismo y* como y* = cBB^-1

Otra aplicación incluye la interpretación de los precios sombra (y1*, y2*,....,y*m) descritos en la sección 4.7. La idea fundamental revela que Z* (el valor de Z para la solución óptima) es

en el problema de la Wyndor Glass Co. Esta ecuación conduce inmediato a la interpretación de las yi* dada en la sección 4.7.