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.