Cómo el doble LP resuelve el primal LP

Question

Cuando oí que alguien me discutiendo LP el otro día, yo le oí decir, "Bueno, podríamos resolver el dual".

Sé que tanto el primal LP y su doble debe tener el mismo valor objetivo óptimo (asumiendo que ambos son factibles y limitado). También entiendo holgura complementaria (el producto de todos los primal variables y doble variables de holgura es 0, ya que es el producto de todos los dual variables primitiva y las variables de holgura).

Para mí, la solución de la doble le da información útil acerca de la solución del primal:

1. El objetivo final de valor, que se restringe a un $n-1$ hyperplane
2. Todas distinto de cero doble variables de holgura requieren primal variables de 0.

Pero aparte de esta información, a mí no me parece que la solución de la doble verdad resuelve el primal LP. Conocer el valor objetivo óptimo puede ayudar (teniendo en cuenta esto, basta con encontrar el primal factible punto con que valor objetivo), como se puede saber que primal variables son 0. Pero el último es LP-específicos: si el problema dual tiene muchos ceros en la solución, entonces no hay información sobre el primal variables.

Mi pregunta es esta: cuando la gente dice "vamos a resolver el dual," ¿eso significa que realmente resuelve el primal o que simplemente nos da información útil que puede ayudar a resolver más rápido los primal?

Gracias por tu ayuda, ninguno de mis colegas podía responder.

EDIT: Mi principal pregunta es equivalente a "¿Cómo podemos demostrar que hay suficientes ecuaciones para determinar todas las variables?" Por favor, véase el comentario a la respuesta a continuación.

Answer 1

Hay dos aspectos de este.

1. Si utiliza el método simplex o alguna variante de que, en realidad, para resolver simultáneamente el primal y el dual. Que es, desde un óptimo tabla simplex se puede leer tanto en la solución óptima del primal y una solución óptima para el dual.
2. A partir de una solución óptima de primal o dual, holgura complementaria reduce el otro (al menos en degenerada de los casos) a una cuestión relativamente sencilla de resolver un sistema de $m$ ecuaciones lineales en $m$ incógnitas.

EDIT: he Aquí un ejemplo típico. Considerar la (primal) problema P:

$$ \eqalign{\text{maximizar } & 2 x_1 +16 x_2 +2 x_3 \cr \text{objeto} &\cr Y 2 x_1 + x_2 - x_3 \le -3 \cr & -3 x_1 + x_2 + 2 x_3 \le 12 \cr y x_1, x_2, x_3 \ge 0 }$$

y supongamos que usted sabe que $x_1 = 0$, $x_2 = 2$, $x_3 = 5$ (y por lo tanto variables de holgura $\xi_1 = 0$, $\xi_2 = 0$) es una solución óptima. El doble problema (con la decisión variables $y_1, y_2$ y variables de holgura $\eta_1, \eta_2, \eta_3$) ha ecuaciones

$$ \eqalign{ 2 y_1 - 3 y_2 - \eta_1 y= 2\cr y_1 + y_2 - \eta_2 &= 16\cr -y_1 + 2 y_2 - \eta_3 y= 2\cr}$$ Pero holgura complementaria le dice $\eta_2 = 0$$\eta_3 = 0$. Poniendo estos en y la resolución de la segunda y tercera ecuaciones $$ \eqalign{ y_1 + y_2 &= 16\cr -y_1 + 2 y_2 y= 2\cr}$$ usted obtener $y_1 = 10$, $y_2 = 6$, y, a continuación, en la primera ecuación $\eta_1 = 0$.

Answer 2

Es tal vez un poco tarde, pero como yo tenía la misma duda, me he decidido a escribir una respuesta para referencia en el futuro.

La clave es entender que uno supone que su solución es un vértice. Si no es uno, no es demasiado difícil encontrar un vértice que es óptimo a partir de la solución óptima.

Voy a usar la notación de Oliver se introdujo en su comentario a la otra respuesta. Es decir, asumir el problema original se ha $n$ variables $k$ restricciones ($k$ variables de holgura), donde $u\le n$ de esas variables son cero y $v\le k$ variables de holgura son cero.

Una vez que usted tiene un vértice, usted sabe que usted tiene las igualdades para, al menos, $n$ de la $k+n$ desigualdades ($k$ "matrix" limitaciones y a las $n$ nonnegativity). Esto es debido a que en un $n$ espacio tridimensional (de las variables originales), un punto es la intersección de (al menos) $n$ hyperplanes.

Esas son exactamente las $k-v$ variables de holgura que son cero y $n-u$ variables que son cero, por lo que tiene:

$$(k-v)+(n-u)\geq n\Rightarrow k\leq u+v$$

Por lo tanto (por Oliver comentario acerca de la doble problema, $k$ variables $n$ restricciones) podemos "garantizar el número de incógnitas en el sistema dual de no exceder el número de ecuaciones en el dual".