Origen del problema dual (IV)

A manera de ilustración, la tabla 6.5 muestra el renglón 0 para las iteraciones respectivas al aplicar el método símplex al ejemplo de la Wyndor Glass Co. En cada caso, se dividió el renglón en tres partes: los coeficientes de las variables originales (x1, x2), los coeficientes de las variables de holgura (x3, x4, x5) y el lado derecho (valor de Z). Cada renglón 0 identifica una solución para el problema dual, que se muestra en la columna de la derecha. Se incluyen los valores de:

las variables de superávit para las restricciones funcionales del problema dual, y1 + 3y3 ≥ 3 y 2y2 + 2y3 ≥ 5. Así, un valor negativo para cualquier variable de superávit indica que se está violando la restricción correspondiente. También se incluye el valor de la función objetivo dual yo = 4y1 + 12y2 + 18y3. Tal y como se mostró en la tabla 6.4 todas etas cantidades se identifican en el renglón 0.

Origen del problema dual (III)

Pero, excepto porque no se ha establecido un objetivo para la función yo, este problema es precisamente el problema dual! Para completar la formulación, se explorará cuál debe ser ese objetivo que falta.

Como yo es sencillamente el valor de Z, y como el objetivo del problema primal es maximizar Z, una reacción natural sería que yo se maximizara también. Sin embargo, esto no es correcto debido a una razón bastante sutil: las únicas soluciones factibles para este nuevo problema son aquellas que satisfacen la condición de optimalidad para el problema primal. Por tanto, nada más la solución óptima para el problema primal corresponde a la solución factible para este nuevo problema. En consecuencia, el valor óptima de Z en el problema primal es el valor mínimo factible de yo en el nuevo problema, de manera que yo debe minimizarse. (Las relaciones que se desarrollan en la sección 6.3 proporcionan la justificación completa para esta conclusión.) Si se agrega este objetivo de minimizar yo, se obtiene el problema dual completo.

De este modo, el problema dual se puede ver como otra forma de establecer, en términos de programación lineal, la meta del método símplex, a saber, alcanzar una solución para el problema primal que cumpla con la prueba de optimalidad. Antes de alcanzar esta meta, la y correspondiente en el renglón 0 (los coeficientes de las variables de holgura) de la tabla símplex final debe ser no factible para el problema dual. No obstante, cuando ya se alcanzó la meta, la y correspondiente debe ser una solución óptima (indicada por y*) para el problema dual, ya que se trata de una solución factible que adquiere el valor factible más pequeño de yo. La solución óptima (y1*, y2*,....., ym*) proporciona los precios sombra para el problema primal que se describieron en la sección 4.7. Aún más, esta yo óptima no es otra cosa que el valor óptimo de Z, de manera que los valores de la función objetivo son iguales para los dos problemas. Este hecho también significa que cx ≤ yb para cualquier x y y factibles para los problemas primal y dual, respectivamente.

Origen del problema dual (II)

La clave ahora, estriba en expresar lo que el método símplex trata de lograr (según la prueba de optimalidad) en términos de estos símbolos. En particular, busca un conjunto de variables básicas y la solución básica factible correspondiente, tal que todos los coeficientes en el renglón 0 sean no negativos. Cuando esta condición se cumple, se detiene con esta solución óptima. Esto se expresa simbólicamente como sigue.

Origen del problema dual (I)

La teoría de dualidad se basa directamente en la idea fundamental (en particular con respecto al renglón 0) que se presentó en la sección 5.3. Para ver por qué, se seguirá usando la notación, que se introdujo en la tabla 5.9 para el renglón 0 de la tabla símplex final, pero se reemplazará Z* por yo y se quitarán los asteriscos de z* y y* al hacer referencia a cualquier tabla símplex. Entonces, en cualquier iteración dada del método símplex para el problema primal los números actuales del renglón 0 se denotan como se muestra en la tabla (parcial) dada en la tabla 6.4. Recuérdese que la idea fundamental conducía a la siguientes relaciones entre las cantidades y los parámetros del modelo original:

Esencia de la teoría de dualidad (IV)

Notese en particular que en la tabla 6.2: 1) los parámetros para una restricción en cualquier problema son los coeficientes de una variable en el otro y 2) los coeficientes de la función objetivo en un problema son los valores del lado derecho del otro. Entonces, existe una correspondencia directa entre los elementos de los dos problemas, tal y como se resume en la tabla 6.3. Esta correspondencia es la clave de algunas implicaciones de la teoría de dualidad entre las que se encuentra el análisis de sensiblidad.

Esencia de la teoría de dualidad (III)

A manera de ilustración, en la tabla 6.1 se muestran los problemas primal y dual para el ejemplo de la Wyndor Glass Co. de la sección 3.1, en forma matricial.

La tabla primal-dual para programación líneal ayuda también a subrayar la correspondencia entre los dos problemas. Muestra todos los parámetros de programación lineal (las aij, bi y cj) y cómo se usan para construir los dos problemas. Todos los encabezados de problema primal están en posición horizontal, mientras que para leer los del problema dual se necesita dar un cuarto de vuelta al libro. Se sugiere comenzar a observar cada problema.

en forma individual tapando con la mano los encabezados del otro. Una vez que se haya visto lo que dice la tabla para cada uno, deberán comparse.

Esencia de la teoría de dualidad (II)

Entonces, el problema dual usa exactamente los mismos parámetros que el problema primal, pero en diferentes lugares. Para recalcar esta comparación, obsérvese ahora estos mismos problemas en la notación matricial (tal y como se introdujo al principio de la sección 5.2), en donde e y y = [y1, y2,.............ym] son vectores renglón, pero b y x son vectores columna.