Dualidad

Después de sustituir la expresión anterior para Z j, la condición de optimalidad dice que el método simplex se puede interpretar como la búsqueda de los valores de y1, y2,…, ym tales que

my0 = ∑ biyi,i=1 sujeta a m ∑ aijyi ≥ cj, para j = 1,2,…, n i=1 y yi ≥ 0,para i = 1,2,…, m. |

Pero, excepto por la falta de un objetivo para la función y0, ¡este problema es precisamente el problema dual! Para completar la formulación, se explorara cual se debe ser ese objetivo que falta.
Como y0 es sencillamente el valor de Z, y como el objetivo del problema primal es maximizar Z, una reacción natural seriaque y0 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 mas la solución optima para el problema primal corresponde a la solución factible para este nuevo problema. En consecuencia, el valor óptimo de Z enel problema primal es el valor mínimo factible de y0 en el nuevo problema, de manera que y0 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 y0 se obtiene el problema dual completo.
De este modo, el problema dual se puede ver como otra forma de establecer, entérminos de programación lineal, la meta del método simplex, a saber, alcanzar una solución para el problema primal que cumpla con la prueba de optimalidad. Antes de alcanzar esta meta, la y corresponde en el renglón 0 (los coeficientes de las variables de holgura) de la tabla simplex final debe ser no factible para el problema dual. No obstante cuando ya se alcanzo la meta, la y correspondiente debeser una solución optima (indicada con y*) para el problema dual, ya que se trata de una solución factible que adquiere el valor factible más pequeño de y0. La solución optima (y1*,y2*,…,ym*) proporciona los precios sombras para el problema primal que se describieron en la sec. 4.7. Aun mas, esta y0 optima no es otra cosa que el valor optimo de Z, de manera que los valores de la función objetivoson iguales para los dos problemas. Este hecho también se significa que cx ≤ y para cualesquiera x y y factibles para el problema prima y dual, respectivamente.
A manera ilustrado, la tabla 6.5. Muestra el renglón 0 para las interacciones respectivas al aplicar el método simplex, al ejemplo de la Wyndor Glass Co. En cada caso, se dividió el renglón 0 en 3 partes: los coeficientes delas variables originales (x1, x2), los coeficientes de las variables de holgura (x3, x4, x5).

Tabla 6.4 Notación para los elementos del renglón 0 en la tabla simplex

interacción | Variable básica | Ec. Núm. | | Coeficiente de | | Lado derecho |
| | | Z | X1 X2 … Xn xn+1 xn+2 | … xn+m | |
Cualquiera | Z | (0) | 1| (z1- c1) (z2 – c2) … (zn – cn) y1 y2 … ym | Y0 |

Y el lado derecho (valor de Z). Cada renglón 0 identifica una solución al problema dual, que se muestra en la columna de la derecha. Usando la expresión dada para zj el lado derecho de la tabla también incluye los valores calculados dez1 – c1 = y1 +3y3 – 3,
z2 – c2 = 2y2 + 2y3 – 5,

Esto es, 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. En la columna de la derecha de la tabla también se incluye el valor de la función objetivo...