Programación lineal - condiciones de optimalidad

Question

Del libro de introducción a la optimización lineal de Bertsimas: ejercicio 3.7:

Considera una solución factible x a un programa lineal estándar:

$$\begin{align*} \min\quad & \textbf{c'x} \\ \text{sujeto a } & \textbf{Ax=b} \\ & x \geq 0 \ \\ \\ \text{Y sea } & Z = \{i | x_i=0\} & & \end{align*}$$

Demuestra que x es una solución óptima si y solo si el programa lineal:

$$\begin{align*} \min\quad & \textbf{c'd} \\ \text{sujeto a } & \textbf{Ad=0} \\ & d_i \geq 0, \ i \in \{Z\} \\ \\ \ & & \end{align*}$$ Tiene un valor óptimo de cero.

Entiendo que para dos soluciones del programa original, x y y, podemos definir d=y-x. Entonces Ad=0 y probablemente esté relacionado con la condición óptima de c'd>=0. Pero aún no entiendo cómo se relaciona con el conjunto Z y cómo probar la dirección de 2->1

Answer 1

Escribe $$c'x = c'y + c'(x-y),$$ donde $y$ también es una solución del LP. Sea $$d = y - x.$$ Claramente, $Ad = 0$, y $d_i \geq 0, \ i \in \{Z\}$.

Ahora, si el segundo LP tiene un valor mínimo de $0$, esto significa que $$c'd \geq 0.$$ Por lo tanto, $$c'x \leq c'y,$$ y el resultado está demostrado.

Recíprocamente, tomamos $d$ como solución del segundo LP. Definimos, $$y = x + \epsilon d.$$ Claramente, $Ay = b$, y es posible encontrar $\epsilon$ tal que $y \geq 0$. Como $x$ es óptimo, esto implica que $c'd \geq 0$, y obviamente se alcanza $0$ cuando $d = 0$.