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
\\
Sujeto \ a
\\
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
\\
Sujeto\ a
\\
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.
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 \)
