ENLACE PARA VIDEO

http://www.youtube.com/watch?v=tAdaNMoSeVU

ENLACES

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/dualidad-en-programaci%C3%B3n-lineal/
http://miblogdeinvestigaciondeoperaciones.blogspot.com/2013/02/la-dualidad-en-programacion-lineal.html http://www.slideshare.net/eukitaa/dualidad-11256504
http://www.programacionlineal.net/resolucion_grafica.html
https://sites.google.com/site/tfio1joseyu/analisis-de-sensibilidad/importancia-del-analisis-de-sensibilidad

INTRODUCCION

INTRODUCCIÓN

El trabajo del equipo de investigación de operaciones recién se inicia cuando se ha aplicado con éxito el método símplex para identificar una solución óptima. Una suposición de programación lineal es que todos los parámetros del modelo (aij, bi y cj ) son constantes conocidas. En realidad, los valores de los parámetros que se usan en este modelo son sólo estimaciones basadas en una predicción de las condiciones futuras. Los datos obtenidos para desarrollar estas estimaciones con frecuencia son bastante imperfectos o no existen, es por esta razón que los parámetros de la formulación original pueden representar poco más que algunas pequeñas reglas proporcionadas por el personal de línea el que tal vez se sintió presionado para dar su opinión. Los datos pueden incluso representar estimaciones optimistas o pesimistas que protegen los intereses de los estimadores.

Por todo esto, un gerente razonable y el personal de investigación de operaciones mantendrán cierto escepticismo respecto a los valores originales entregados por el computador y, en los muchos casos, los considerarán solamente como un punto de inicio para el análisis posterior del problema. Una solución "óptima" es óptima nada más en lo que se refiere al modelo específico que se está usando para representar el problema real, y tal solución no se convierte en una guía confiable para la acción hasta que se verifica que su comportamiento es bueno para otras representaciones razonables del problema. Aún más, algunas veces los parámetros del modelo (en particular bi) se establecen como resultado de decisiones por políticas gerenciales, y estas decisiones deben revisarse después de detectar sus consecuencias.

DUALIDAD EN PROGRAMACIÓN LINEAL

DUALIDAD EN PROGRAMACIÓN LINEAL

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 mantiene la base optima (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 termino independiente de la restricción. 

REGLAS DE OBTENCIÓN DEL DUAL

Si el modelo está escrito en la forma canónica, el dual resulta singularmente fácil de obtener. Por ejemplo, partiendo de la forma canónica del modelo de máximo:

Primal                                              Dual

[MIN] z= c^’. x                                 [MAX] w= b^’. u

           A . x ≥ b                                               A^’. u  ≤ c

            x_j ≥ 0                                                   u_i  ≥    0      

INTERPRETACIÓN DE LAS VARIABLES DUALES.

El significado de las variables duales es el mismo que en el caso de los multiplicadores de Lagrange, es decir miden la sensibilidad de la función objetivo respecto a cambios (infinitesimales) de los términos independientes de cada restricción.

Max F = ct x

s.a:

A x = b

x ≥ 0

Donde asumimos que x ∈ Rn, c ∈ Rn, b ∈ Rm y A ∈ Μ(n,m).

Si suponemos que x* es una solución factible básica no degenerada y óptima del problema anterior, es decir, verifica que: x* = B-1 b ≥ 0 ; b ≥ 0; A x* = b y que para una variación del vector de términos independientes b, cuando este vector pasa a ser (b+Δb), siendo (b+Δb) ≥ 0, y que esta variación deje inalterada las variables básicas de la solución, es decir que se cumpla que:

x* = B-1 (b + Δb) ≥ 0; (b + Δb) ≥ 0

A x* = (b + Δb)

En estas condiciones la derivada de la función de Lagrange:

L(x,λ) = cx + λ ( b - Ax )

∂ L

- = λ

∂ b este valor de λ nos indica en cuanto varia la función objetivo ante una variación (infinitesimal) de b, y que mantenga la factibilidad de la solución.

OBTENCIÓN  DE LA SOLUCIÓN DEL DUAL

El dual de un modelo lineal es otro modelo lineal, que puede solucionarse (después de las oportunas transformaciones, si algunas de las variables resultantes es no negativa o no restringida en signo) del mismo modo que el primal. Sin embargo, en general puede obtenerse la solución del dual resolviendo el primal.

DUALES SIMÉTRICOS

Son los que se obtienen de un problema primal en forma canónica y “normalizada”, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades menores o igual para los problemas de maximización. Es decir, si el problema original es de la siguiente forma:

Máx Z(x) = c^t x

S.A:

A x ≤ b

x ≥ 0

El problema dual (dual simétrico) es:

Mín G (λ) = λ b

S. A:

λ A ≥ c

λ ≥ 0

DUAL ASIMÉTRICO

 Son los restantes tipos de combinaciones de problema. Como por ejemplo:

Máx Z(x) = c^t x

S. A:

A x = b

X ≥ 0

El problema dual (dual asimétrico) es:

Mín G (λ) = λ b

S. A:

λ A ≥ c

λ >< 0, es decir, variables libres.

CARACTERÍSTICAS DE LAS SOLUCIONES DEL DUAL Y DEL PRIMAL

      Si el primal tiene solución óptima acotada x*, el dual también tendrá solución óptima acotada u*  ambas soluciones darán el mismo valor de la función objetivo.

C’. x^*=b^’. u^*

      Si uno de los dos problemas tiene optimo no acotado, el otro no tendrá solución (la región factible será un conjunto vacío)

      Si uno de los dos problemas no tiene solución, el otro puede tener optimo no acotado o no tener tampoco solución.

RELACIONES PRIMAL-DUAL

Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual que posee importantes propiedades y relaciones notables con respecto al problema lineal original, problema que para diferencia del dual se denomina entonces como problema primal (PP).

Las relaciones las podemos enumerar como siguen:

      El problema dual tiene tantas variables como restricciones tiene el programa primal.

      El problema dual tiene tantas restricciones como variables tiene el programa primal

      Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal.

      Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal.

      La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal.

      El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del sentido de las restricciones del mismo problema.

TABLA DE TUCKER

CONDICIONES DE KUHN-TUCKER

Condiciones de Kuhn-Tucker en los problemas lineales (primales y duales).

Consideremos el siguiente programa lineal, que denominaremos PRIMAL:

Máx Z(x) = ct x

s.a:

A x ≤ b

x ≥ 0

La función lagrangiana de esta programa será:

L(x,λ) = c x + λ ( b - Ax ) donde λ = ( λ1, λ2,....,λm ) representa el vector de los multiplicadores de Lagrange asociados a las restricciones.

Las condiciones de optimalidad de este problema (Condiciones de Kuhn-Tucker) respecto de las variables, son:

∂L

 = c - λ A ≤ 0

∂x

∂L

 x = ( c - λ A ) x = 0

∂x

x ≥ 0

Respecto a los multiplicadores, son:

∂L

 = b - Ax ≥ 0

∂λ

∂L

 λ = λ ( b - Ax ) = 0

∂λ

λ ≥ 0

Asociado a este programa primal tenemos otro problema lineal denominado DUAL (posteriormente explicaremos las relaciones entre ambos):

Mín G(λ) = λ b

s.a:

λ A ≥ c

λ ≥ 0

La función lagrangiana de este programa será:

L(λ,x) = λ b + ( c - λA ) x en donde el vector x = ( x1, x2, ..., xn ) representa los multiplicadores asociados a las restricciones del dual.

Obteniendo las condiciones de Kuhn-Tucker respecto de las variables son:

∂L

 = b - Ax ≥ 0

∂λ

∂L

 λ = λ ( b - Ax ) = 0

∂λ

λ ≥ 0

Respecto a los multiplicadores, son:

∂L

 = c - λ A ≤ 0

∂x

∂L

 x = ( c - λ A ) x = 0

∂x

x ≥ 0

Como puede observarse, ambas condiciones de optimalidad son las mismas para los dos problemas. A la misma consideración se puede llegar sin más que comparar la función de Lagrange de los dos problemas y ver que son iguales:

L(x,λ) = c x + λ ( b - Ax )

L(λ,x) = λ b +( c - λA )x = λ b + cx-λAx = cx + λ( b - Ax )

Por lo tanto, asociado a todo problema de programación lineal existe otro problema de programación lineal denominado programa dual que tiene importantes relaciones con el problema original denominado programa primal. Como acabamos de ver, es evidente, que el programa dual de un programa dual proporciona el programa primal original.

TABLA DE CONDICIONES DE KUNH-TUCKER