Pregunta sobre la dualidad en la programación lineal

Question

Tengo la pregunta sobre la expresión de la formulación dual de un programa lineal. Creo que es muy simple, pero no entiendo (1) a continuación

$ \min \ c^Tx \\ \text{s.t.} \ \ Ax \le b $

$L(x,\lambda) = c^Tx + \lambda(Ax-b)$

$g(\lambda) = \inf_x ((c + A^T\lambda)^Tx - b^T\lambda) \\ = -b^T\lambda \ \ \text{if} \ \ A^T\lambda + c = 0 \\ = -\infty \ \ \ \ \text{otherwise} $

Se dice que $ g(\lambda) \le c^Tx$ .

(1) ¿Por qué $-b^T\lambda \le c^Tx$ ?

Answer 1

Esta es una prueba estándar para la dualidad débil. Multiplique las restricciones en el primal por $\lambda$ (a $\lambda^T Ax \leq b^T \lambda$ ) y en el dual por $x$ (a $\lambda^TAx + c^T x = 0$ ) para obtener $-c^Tx \leq b^T \lambda$ .