Dual y dualidad programacion lineal

Dual
Dado un modelo lineal determinado, podemos definir otro modelo lineal que nos permitirá obtener propiedades interesantes del primero y que será su dual. La solución del modelo dual permite obtener interesantes resultados, relativos al análisis de sensibilidad de los términos independientes. Más concretamente, para los rangos de valores de los términos independientes para los que se mantienela base óptima (que podemos conocer mediante el análisis de sensibilidad), la solución del dual nos permite conocer el precio sombra de la restricción, que será la variación de la función objetivo por unidad incrementada del término independiente de la restricción.
En la primera parte de esta sección, encontramos cómo hallar el dual de un modelo lineal. En las siguientes, se define con másprecisión el concepto de precio sombra, cómo obtener la solución del dual a partir de la del primal, y su aplicación al análisis de sensibilidad. Finalmente, se enuncian algunas propiedades de interés, como el teorema de la holgura complementaria y las relaciones entre las soluciones del primal con las soluciones del dual.

Teoremas de Dualidad
Teorema de Dualidad Débil
Sean dos problemasrecíprocamente duales en forma canónica:
P: minimizar cx
Sujeto a Ax ≥ b
x ≥ 0
D: maximizar wb
Sujeto a wA ≤ c
w≥ 0
Entonces, el valor de la función objetivo para cualquier solución factible x0 del problema P, el valor de la función objetivo es mayor o igual que el de cualquier solución factible w0 del problema D.
Es decir: cx0 ≤ w0b, siendo x0, w0 soluciones factibles de los problemas primal ydual.
Corolario
Si x0 y w0son soluciones factibles de los problemas primal y dual y cumplen cx0 = w0b, entonces x0 y w0 son óptimas en sus respectivos problemas.

Teorema de dualidad fuerte
Si uno de los problemas primal o dual tiene solución óptima, entonces ambos problemas tienen solución óptima y sus valores objetivos óptimos coinciden.

Teorema fundamental de dualidad
Dados dos problemasrecíprocamente duales se cumple una y sólo una de las siguientes situaciones:
1. Ambos tienen soluciones óptimas.
2. Uno de los problemas tiene solución no acotada y el otro no tiene solución factible.
3. Ambos problemas son no factibles.

Teorema de holgura complementaria
Sean x0 y w0 soluciones factibles de los problemas primal y dual en forma canónica. X0 y w0 son soluciones optimas si ysolo si
(cj – w0aj)x0j = 0 j = 1,………,n
W0i(aix0 – bi) = 0 i = 1,……….,m
Donde aj es la columna j-ésima y aies la fila i-ésima de la matriz A.
Corolario
Si x0 y w0 son soluciones óptimas de sus respectivos problemas, se tienen las siguientes implicaciones:
x0j> 0 ==> w0aj = cj
aix0>bi==> w0i = 0
w0i> 0 ==> aix0 = bi
w0aj<cj==> x0j = 0

Análisis deSensibilidad

Es el estudio de posibles cambios en la solución óptima disponible como resultado de hacer cambios en el modelo original.
Consiste en establecer un intervalo de números reales en el cual el dato que se analiza puede estar contenido, de tal manera que la solución sigue siendo óptima siempre que el dato pertenezca a dicho intervalo.

1. Cambio en el "lado derecho4. Inclusión de una nuevarestricción: Para saber si la actual solución y valor óptimo se mantendrá luego de incorporar una nueva restricción al problema se debe evaluar la solución actual y verificar si satisface la nueva restricción. En caso afirmativo, la actual solución también lo será del problema con la nueva restricción, en caso contrario se incorpora la nueva restricción a la tabla final del Simplex del escenariobase." de las restricciones: Lo que se busca identificar si las actuales variables básicas se mantienen luego de la modificación de uno o más parámetros asociados al "lado derecho" del modelo. Si calculamos:
y se cumple , Las mismas variables básicas lo son también de la nueva solución óptima, calculada con el nuevo. Si lo anterior no se cumple, se puede aplicar el Método Simplex Dual.

2....