miércoles, 12 de febrero de 2014

Resumen de las relaciones primal-dual (IV)

Propiedad de soluciones complementarias óptimas: al final de cada iteración, el método símplex identifica simultáneamente una solución óptima x* para el problema primal y una solución óptima complementaria y* para el problema dual (que se encuentra en el renglón 0 como los coeficientes de las variables de holgura), en donde:

cx* = y*b

Los valores de yi*son los precios sombra para el problema primal.

Por ejemplo, la iteración final da x* = [2,6]^T y y* = [0,3/2,1], con cx* = 36 = y*b.

En la sección 6.3 se analizarán con la más detenimiento algunas de estas propiedades. Se verá que la propiedad de soluciones complementarias se puede extender mucho más. En particular, después de introducir las variables de holgura y de superávit en ambos problemas, toda solución básica en el problema primal tiene una solución básica complementaria en el problema dual, en donde el método símplex identifica los valores de las variables de superávit en el problema dual como (zj - cj) en la tabla 6.4. Este resultado conduce después a la propiedad adicional de holgura complementaria que relaciona las variables básicas de un problema con las no básicas del otro (tablas 6.7 y 6.8) pero después se estudiará más al respecto.

En la sección 6.4 después de describir cómo se construye el problema dual cuando el problema primal no se encuentra en nuestra forma estándar, se analizará otra propiedad útil que se resume.

No hay comentarios.:

Publicar un comentario