Teorema
de existencia.
La condición necesaria y suficiente para que un
problema de programación lineal tenga solución es que, tanto el conjunto de
oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no
sean vacíos, es decir, que ambos problemas sean factibles.
∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅
Una vez analizadas las condiciones que han de
cumplirse para que exista solución óptima se muestra.
v S ≠ ∅ ∧ S’ ≠ ∅ Ambos
problemas tienen solución optima finita.
v S = ∅ ∧ S’ ≠ ∅ El
programa primal es infactible, y el programa dual es no
acotado.
v S ≠ ∅ ∧ S’ = ∅ El
programa dual es infactible, y el programa primal es no acotado.
v S = ∅ ∧ S’ = ∅ Ambos
problemas son infactibles.
Teorema de la Dualidad.
La condición necesaria y suficiente para que exista
solución optima del primal ( x* ), es que exista una solución óptima para el
dual ( λ* ) y que valor de la función objetivo de ambos programas sea igual, es
decir Z(x*) = G(λ*).
∃ x* ←→ ∃ λ* / Z(x*) =
G(λ*)
Teorema del Holgura complementaria.
La condición necesaria y suficiente para que (x*,
λ*) sean soluciones óptimas del programa primal y dual, es que satisfagan las
condiciones de holgura complementaria:
(
c - λ* A ) x* = 0
λ*
( b - A x* ) = 0
No hay comentarios:
Publicar un comentario