Dualidad

Principios Básicos

Veremos en esta sección los importantes teoremas de Dualidad así como una introducción al algoritmo dual, el cual es la aplicación del algoritmo del Simplex al problema Dual asociado.

Dado problema de programación lineal de la forma

Problema Primal

     Min Ctx
Sujeto a
     Ax ≤ B
     x ≥ 0
Donde
     A∈ Mmxn, con rango(A)=m, b∈Rm, C∈Rn

Lleva asociado otro problema que llamaremos Dual, de la forma

Problema Dual

     Max btw
Sujeto a
     Atw ≥ C
     w ≥ 0
Donde
     A∈ Mmxn, con rango(A)=m, b∈Rm, C∈Rn Pero ahora w ∈Rm


Es decir, lo que antes era vector de costes, ahora es ahora vector de restricciones y viceversa y la matriz de restricciones es transpuesta en el dual. En algunos casos es más fácil resolver uno que otro, o bien, como veremos aquí, es posible dar condiciones para uno que nos den las propiedades de la solución del otro.

En realidad el llamdo algoritmo Dual, no es otra cosa que la aplicación del Algoritmo del Simplex al problema debidamente dualizado.

Teoría en extensión

Más generalmente, si tenemos un problema de la forma
     Max Ctx
     Sujeto a
     ∑nj=1aijxj ≤ bi, i ∈M1
     ∑nj=1aijxj = bi, i ∈M - M1
     xj ≥ 0, j ∈N1

Es decir, solo tenemos restringidas en signo algunas de las variables y solo en algunas de las restricciones tenemos desigualdad. Entonces el problema dual queda de la forma:

     Min btw
     Sujeto a
     ∑mi=1ajiwi ≥ Ci, j ∈N1
     ∑mi=1ajiwi = Ci, j ∈N - N1
     wi ≥ 0, i ∈M1

Es decir, tenemos
1. Una restricción de desigualdad en el primal se traduce en variable restringida en signo en el dual.
2. Restricción de igualdad en el primal, se traduce en una variable no restringida en signo en el dual.

Teorema de existencia
a) Si uno de los dos problemas tiene solución optima finita, entonces el otro también la tiene.
b) Si el problema primal tiene solución no acotada, entonces el dual no tiene solución óptima factible (el recíproco no es cierto).


Corolario 1 Dados un par de problemas duales, solo una de estas condiciones es cierta:
1) Ninguno de los dos tiene solución factible.
2) Uno tiene solución factible pero no acotada y el otro no tiene solución.
3) Los dos tienen soluciones optimas finitas


Corolario 2 (Teorema de la dualidad)
Dado un par de problemas duales, una condición necesaria y suficiente para que el primal tenga solución óptima finita x, es que exista una solución factible del dual w, tal que Cx = bw





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios





Deja tu post