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\ C^tx \\ Subject\ to \\ Ax \leq b \\\\ x\geq 0 \\ A \in M_{mxn}, \ rank(A)=m \\ b\in \mathbb{R}^m, \ C \in \mathbb{R}^n, x \in \mathbb{R}^n \)

Lleva asociado otro problema que llamaremos Dual, de la forma

Problema Dual

\( max\ b^tw \\ Subject\ to \\ A^tw \geq C \\\\ w\geq 0 \\ A \in M_{mxn}, \ rank(A)=m \\ b\in \mathbb{R}^m, \ C \in \mathbb{R}^n, w \in \mathbb{R}^m \)


Es decir, lo que es vector de costes en el primal, es vector de restricciones en el dual 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 para obtener 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íaa en extensión

Más generalmente, si tenemos un problema de la forma

\( max\ C^tx \\ Subject\ to \\ \sum_{j=1}^{n} a_{ij}x_j \leq b_i,\ i \in M_1\\ \sum_{j=1}^{n} a_{ij}x_j = b_i,\ i \in M-M_1\\ x_j\geq 0 , \ j\in N_1 \)

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:

\( max\ b^tw \\ Subject\ to \\ \sum_{i=1}^{m} a_{ji}w_i \geq C_i,\ j \in N_1\\ \sum_{i=1}^{m} a_{ji}w_i = C_i,\ j \in N - N_1\\ w_i\geq 0 , \ i\in M_1 \)

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

daniel:

2020-05-26 17:52:40
No demostraron nada. No es util.

Carlos:

2020-05-29 15:42:31
Hola Daniel

Tienes Razón, incluiré las demostración de estos teoremas en breve.
Gracias por el comentario.

Carlos




Deja tu post