¿Cómo cambia la solución dual al multiplicar una restricción primaria por una constante?

Question

Supongamos que tenemos el problema $\min c^T x$ , con la condición de que $Ax=b, x \geq 0$ .

Supongamos que este programa y su dual son factibles. Sea $\lambda$ sea la solución óptima del dual. Si el $k$ La ecuación de la restricción del primal se multiplica por $\mu \neq 0$ ¿cómo podríamos expresar una solución óptima $w$ a la dualidad de este nuevo problema?

Answer 1

La respuesta es $w_k = \lambda_k/\mu$ y $w_i = \lambda_i$ para $i \neq k$ .

Multiplicando el $k$ de la restricción primaria por $\mu$ no cambia la región factible primal y por lo tanto no cambia la solución óptima primal. Por lo tanto, el valor $z^*$ de la solución primaria óptima no cambia.

El único cambio en el problema dual es que el $k$ se sustituye por $\mu$ veces esa variable (en las restricciones y el objetivo). Dado que $z^*$ es el valor de la solución óptima dual original, dejando que $w_i = \lambda_i$ para $i \neq k$ y $w_k = \lambda_k/\mu$ da lugar a una solución que es factible para el nuevo dual y que también tiene valor $z^*$ . Así, por dualidad débil, $w$ debe ser óptima.