INDICE:

Introducción.

Dualidad en programación lineal.

Reglas de obtención del dual.

Interpretación de la variables duales.

Obtención de las solución dual.

Dual simétrico y asimétrico.

Características de la solución del dual y del primai.

Relaciones dual primal.

Tabla tucker (tabla - defunción - interpretación).

Tablas de condiciones de kunh-tucker.

Teoremas de la dualidad( de existencia, de dualidad y de holgura complementaria).

Importancia de la dualidad en programación lineal.

Ventajas y desventajas de la dualidad.

Análisis de sensibilidad.

INTRODUCCIÓN

       Encontrar el óptimo de un problema de optimización, es solo una parte del proceso de

solución. Muchas veces nos interesara saber como varía la solución si varía alguno de los

parámetros del problema que frecuentemente se asumen como determinísticos, pero que

tienen un carácter intrínsecamente aleatorio. Mas específicamente nos interesar´a saber para

que rango de los parámetros que determinan el problema sigue siendo valida la solución

encontrada.

Otro aspecto interesante es el tema de dualidad. Dualidad resulta de buscar relaciones que

permitan obtener información adicional de un problema de optimización general. Esto, traducido a progamación lineal nos conduce a relaciones primal-dual. Ademas veremos algunos teoremas útiles

de dualidad y el concepto de precio sombra.

DUALIDAD EN PROGRAMACIÓN LINEAL

       El dual es un problema de programación lineal (PL) que se obtiene matemáticamente de un modelo primal de programación lineal dado. Los problemas dual y primal están relacionados a tal grado, que la solución símplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro. 

       El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.

• La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades.
• Aporta elementos que aumentan sustancialmente la compresión de la PL.
• El análisis de dualidad es una herramienta útil en la solución de problemas de PL,  por ejemplo: más restricciones que variables.
• El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL. 

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

            xj ≥ 0                                                   ui  ≥    0      

INTERPRETACIÓN DE LA VARIABLES DUALES

       Cada variable del dual está asociada a una restricción del programa primal, y su valor óptimo representa el incremento de la función objetivo del primal por cada unidad que aumente el término independiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Es, por tanto, el precio adicional máximo que estamos dispuestos a pagar por el incremento del recurso. Los valores de estas variables se denominan precios sombra.

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.

DUAL SIMÉTRICO Y ASIMÉTRICO

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) = ct 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) = ct 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 LA SOLUCIÓN 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:

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

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

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

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

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

f) 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:

TABLA DE KUNH-TUCKER:

       Las condiciones de Kuhn-Tucker para el problemaDefinición

máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m

se

L i '( x )	= 0 para i = 1 ,..., n
0 λ ≥ j, j g (x) y c ≤ λ j j [j g (x) - c j]	= 0 para j = 1, ..., m,

donde

L (x) = f (x) - Σ j = 1 λ mj (j g (x) - c j

  

   Estas condiciones se nombran en honor de Harold W. Kuhn, miembro emérito del Departamento de Matemáticas de Princeton, y Albert W. Tucker, quien formuló por primera vez y estudió las condiciones. Por consiguiente, también son utilizados para optimizar sistemas aplicando estas condiciones para determinar las desigualdades estableciendo restricciones dentro de los problemas y representar su máximo tomando en cuenta n variables permitiendo analizar el problema tomando en cuenta todos los aspectos que intervienen dentro del mismo así como sus limitaciones. Por ejemplo tenemos un repartidor el cual presenta limitaciones como tiempo para realizar la entrega en el lapso estipulado por el destinatario.

Importancia del teorema de Khun-Tucker en la tarea de toma de decisiones organizacionales.

TEOREMAS DE LA DUALIDAD:

            

Teorema de existencia.

       La condición necesaria y suficiente para que un problema de programación lineal tenga solución es que, tanto el conjunto de oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos problemas sean factibles.

                                    ∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅

       Una vez analizadas las condiciones que han de cumplirse para que exista solución óptima se muestra.

v  S ≠ ∅ ∧ S’ ≠ ∅     Ambos problemas tienen solución optima finita.

v  S = ∅ ∧ S’ ≠ ∅     El programa primal es infactible, y el programa dual es    no acotado.

v  S ≠ ∅ ∧ S’ = ∅     El programa dual es infactible, y el programa primal es no acotado.

v  S = ∅ ∧ S’ = ∅     Ambos problemas son infactibles.

Teorema de la Dualidad.

La condición necesaria y suficiente para que exista solución optima del primal ( x* ), es que exista una solución óptima para el dual ( λ* ) y que valor de la función objetivo de ambos programas sea igual, es decir Z(x*) = G(λ*).

                                   ∃ x* ←→ ∃ λ* / Z(x*) = G(λ*)

Teorema del Holgura complementaria.

La condición necesaria y suficiente para que (x*, λ*) sean soluciones óptimas del programa primal y dual, es que satisfagan las condiciones de holgura complementaria:

                                            ( c - λ* A ) x* = 0

                                            λ* ( b - A x* ) = 0

IMPORTANCIA DE DUALIDAD DE PROGRAMACIÓN LINEAL

      La dualidad es importante por el hecho de que es equivalente resolver un problema a resolver su dual. Ello es debido a que los precios sombra de dual son las soluciones de problemas y viceversa. Así, en ocasiones, puede resultar conveniente obtener las soluciones de problemas a partir de los precios sombra de dual en vez de resolver problemas directamente. 

La resolución de los problemas duales respecto a los primales se justifica dada la facilidad que se presenta dados problemas donde el número de restricciones supere al número de variables. Además de tener gran aplicación en el análisis económico del problema. 

VENTAJAS Y DESVENTAJAS DE LA DUALIDAD:

Ventajas:

       Una de las ventajas de la existencia del programa dual es la posibilidad de reducir el esfuerzo computacional  al resolver ciertos modelos de programación lineal.

• Permite resolver problemas de programación lineal de forma más rápida y sencilla.
• Es otra vía para resolver un problema de programación lineal.
• Facilita profundizar en el contenido económico del problema original (primal).
• Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener que resolver completamente el problema.
• Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

Desventajas:

• Una desventaja de este método, es que se requiere para empezar a iterar la condición de factibilidad dual.

ANÁLISIS DE SENSIBILIDAD

            Es una herramienta útil cuando no tenemos una certeza absoluta sobre los valores que se han dado a los términos independientes de las restricciones o los coeficientes de la función objetivo, en este sentido el análisis de sensibilidad consiste en estudiar cómo evoluciona el optimo y el valor de la función objetivo del optimo ante variaciones de dichos términos independientes y coeficientes.

            Estudia los intervalos para los cuales la modificación de un valor en el programa lineal de forma individualizada, no cambia las variables que componen la base de nuestra solución, hallando para el rango de valores definido en el intervalo, la evolución de la función objetivo expresado a través de los precios sombra. 

OBJETIVO DEL ANÁLISIS DE SENSIBILIDAD

       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 óptimo siempre que el dato pertenezca a dicho intervalo.

          Investigar el cambio en la solución óptima del problema, cuando se producen cambios en los parámetros del modelo.

CARACTERÍSTICAS DEL ANÁLISIS DE SENSIBILIDAD

            El análisis de sensibilidad es una herramienta efectiva por dos razones fundamentales.

• Los modelos de programación lineal son frecuencias grandes y costosas por lo tanto no es recomendable para usarlos en un solo caso.
• Los elementos que se dan como datos para un problema de programación lineal la mayoría de las veces son estimaciones; por lo tanto es necesario investigar o tener en cuenta más de un conjunto de casos posibles. 

ANÁLISIS DE SENSIBILIDAD: RESOLUCIÓN GRÁFICA

            Para ilustrar de forma clara y sencilla en qué consiste el análisis de sensibilidad se utiliza nuevamente la metodología gráfica. Ejemplo de ello.

            Una compañía forestal tiene un predio de 100 hectáreas de bosques para explotar. Talar y dejar el suelo para uso agrícola tiene un costo inmediato de M$10 por hectárea y un retorno posterior de M$50 por hectárea. Una alternativa es talar y plantar pino que tiene un costo inmediato de M$50 por hectárea y un retorno posterior de M$120 por hectárea. De aquí que los beneficios netos de ambos planes sean de M$40 y M$70 por hectárea, respectivamente. Desafortunadamente, el segundo plan no puede ser aplicado a todo el terreno ya que sólo se dispone de recursos inmediatos por M$4.000.

• Formule y resuelva gráficamente un modelo de Programación Lineal que provea el plan más eficiente de explotación, indicando claramente la solución óptima y valor óptimo.
• Suponga que usted puede solicitar un préstamo por M$1.000 por el cual deberá retornar con posterioridad el monto de M$1.400 (una vez concluidos los proyectos). Sin reoptimizar, ¿tomaría usted estos recursos adicionales?

       El Análisis de Sensibilidad para la parte b) y c) se puede hacer gráficamente siguiendo algunos criterios detallados. En cuanto a este caso particular se tiene:

Máxima variación: (0,100)

Mínima variación: (100,0)

Z(Max Var) = 40*0 + 70*100 = 7.000
Z(Min Var) = 40*100 + 70*0 = 4.000
R1(Max Var) = 10*0 + 50*100 = 5.000
R1(Min Var) = 10*100 + 50*0 = 1.000

Precio Sombra R1 = (7.000 – 4.000) / (5.000 – 1.000) = ¾

       El aumento del lado derecho (1.000) se encuentra en el rango donde el precio sombra es válido (hasta 5.000)

Por tanto el aumento en el beneficio total es:
1000 * Precio Sombra = 1000 * 3/4 = 750

Es decir, nuevo V(P) =6.250 + 750 = 7.000

       Donde el aumento (M$750) es claramente inferior al costo adicional (M$1.400) por tanto no se tomarían estos recursos adicionales.

Sin resolver nuevamente el problema, obtener la solución óptima de inversión que resulta al aumentar los retornos posteriores de la primera alternativa de M$50 a M$60.

Esta variación es equivalente a cambiar el coeficiente de X en la función objetivo de M$40 a M$50.

      Luego, analizamos si esta variación está contenida en el intervalo de C1 que garantiza la actual solución óptima: (Para C2=70)

- 1 <= -C1/C2 <= -1/5

C1 puede variar entre {14, 70} y se conserva la actual solución óptima. Luego la variación propuesta no produce un cambio en la actual solución óptima.

ANÁLISIS DE SENSIBILIDAD MEDIANTE PROGRAMAS INFORMÁTICOS

            Los programas informáticos que resuelven modelos de programación lineal, como el LINDO, suelen incorporar la posibilidad de realizar el análisis de sensibilidad de los coeficientes de coste c y de los términos independientes de las restricciones b, el resultado de este análisis es el intervalo de valores de los parámetros para el que se mantiene la base.

CASOS DE ANÁLISIS DE SENSIBILIDAD (CASOS 1,2,3,4)

       Este análisis casi siempre comienza con la investigación de los cambios en los valores de las bi, la cantidad del recurso i (i = 1, 2,. . . , m) que se encuentra disponible para las actividades bajo consideración. La razón es que en general existe mayor flexibilidad al establecer y ajustar estos valores que los otros parámetros del modelo. La interpretación económica de las variables duales las yi, como precios sombra es extremadamente útil para decidir cuáles son los cambios que se deben estudiar.

        Primer caso: Cambios en las b i (columna lado derecho)

Supongamos que los únicos cambios al modelo actual consisten en el cambio de uno o más de los parámetros bi (i = 1, 2, . . . , m). En este caso, los únicos cambios que resultan en la tabla simplex final se encuentran en la columna del lado derecho, por lo cual, se pueden omitir del procedimiento general tanto la conversión a la forma apropiada de eliminación de Gauss como la prueba optimalidad.

       Segundo caso:

A)    Cambios en los coeficientes de una variable no básica

Considere una variable específica xj (j fija) que sea no básica en la solución óptima dada en la tabla simplex final. El caso 2 a es aquel en el que los únicos cambios al modelo actual ocurren en uno o más de los coeficientes de esta variable, cj, a1j, a2j........, amj. Entonces, si cj y aij, denotan los nuevos valores de estos parámetros con Aj, columna j de la matriz A, como el vector que contiene a aij, se tiene para el modelo revisado.

B)     Introducción de una nueva variable

Ya obtenida la solución óptima se puede descubrir que la formulación de programación lineal no tomó en cuenta todas las actividades que pudieran ser atractivas. Considerar una nueva actividad requiere introducir una nueva variable con los coeficientes apropiados, a la función objetivo y a las restricciones del modelo actual, éste es el caso 2 b.

        Tercer caso: Cambios en los coeficientes de una variable básica

       Ahora suponga que la variable xj con j fija, que se está estudiando es una variable básica en la solución óptima que se muestra en la tabla simplex final. El caso 3 supone que los únicos cambios al modelo actual se hacen en los coeficientes de esta variable.

       El caso 3 difiere del 2a debido al requisito de que la tabla simplex debe estar en la forma apropiada de eliminación de Gauss. Esta forma permite que los elementos en la columna de una variable no básica tengan cualquier valor, así que no afecta en el caso 2a. Sin embargo, para el caso 3 la variable básica xj debe tener coeficiente 1 en su renglón de la tabla simplex y coeficiente 0 en todos los demás renglones incluyendo el renglón 0. Por lo tanto, una vez que se han calculado los cambios en la columna xj de la tabla simplex final, es probable que sea necesario aplicar la eliminación de Gauss para restaurar la forma apropiada. Este paso, a su vez, quizá cambie los valores de la solución básica actual, y puede hacerla no factible o no óptima con lo que puede ser necesario reoptimizar.

       Antes de aplicar la eliminación de Gauss, se resumen las fórmulas para revisar que la columna de xj sea la misma que para el caso 2b.

       Cuarto caso: Introducción de una nueva restricción de desigualdad

Este es el último caso en el cual debe introducirse al modelo una nueva restricción, después de que ya se ha resuelto. Este caso puede ocurrir porque se pasó por alto la restricción en un principio o porque surgieron nuevas consideraciones después de formular el modelo. Otra posibilidad es que a propósito se haya eliminado la restricción para disminuir el esfuerzo computacional por parecer menos restrictiva que otras ya planteadas en el modelo, pero ahora es necesario verificar esta impresión con la solución óptima que se obtuvo.

       Para ver si la nueva restricción afecta a la solución óptima actual, todo lo que tiene que hacerse es verificar directamente si esa solución óptima satisface la restricción. Si es así, todavía sería la mejor solución básica factible, es decir, sería la solución óptima, aun cuando se agregara la restricción al modelo. La razón es que una nueva restricción sólo puede eliminar algunas de las soluciones factibles anteriores sin agregar ninguna.

       Si la nueva restricción elimina la solución óptima actual, y si se quiere encontrar la nueva solución, se introduce esta restricción a la tabla simplex final, como un renglón adicional, justo como si fuera la tabla inicial, en la que se designa la variable usual de holgura o artificial, como la variable básica que corresponde a este nuevo renglón. Como éste tal vez tenga coeficientes distintos de cero para algunas otras variables básicas, se debe aplicar la conversión a la forma apropiada de eliminación de Gauss y después el paso de reoptimización en la forma usual.

IMPORTANCIA DEL ANÁLISIS DE SENSIBILIDAD

El análisis de sensibilidad es una de las partes más importantes en la programación lineal, sobre todo para la toma de decisiones; pues permite determinar cuándo una solución sigue siendo óptima, dados algunos cambios ya sea en el entorno del problema, en la empresa o en los datos del problema mismo.

Este análisis consiste en determinar que tan sensible es la respuesta óptima del Método Simplex, al cambio de algunos datos como las ganancias o costos unitarios coeficientes de la función objetivo, o la disponibilidad de los recursos términos independientes de las restricciones.

CONCLUSIONES:

           Hay que considerar que todo problema de programación lineal tiene, asociado a él, un problema dual de programación lineal. Existen ciertas relaciones útiles entre el problema original (primal) y su problema dual que refuerzan la habilidad para analizar el problema original. Por ejemplo, la interpretación económica del problema dual proporciona los precios sombra que miden el valor marginal de los recursos en el problema primal, al igual que permite dar una interpretación del método símplex. Puesto que el método símplex se puede aplicar directamente a cualquiera de los dos problemas para obtener la solución de ambos al mismo tiempo, es posible ahorrar una gran cantidad de esfuerzo computacional si se maneja directamente el problema dual.

            La teoría de dualidad, que incluye el método símplex dual para trabajar con soluciones básicas óptimas, juega un papel de gran importancia en el análisis de sensibilidad.

Los valores usados como parámetros de un modelo de programación lineal son sólo estimaciones. Por lo tanto, es necesario llevar a cabo el análisis de sensibilidad para investigar lo que ocurre si las estimaciones están equivocadas. La idea fundamental es proporcionar la clave para realizar esta investigación de manera eficiente.

       Los objetivos generales del análisis de sensibilidad son identificar los parámetros relativamente sensibles que afectan la solución óptima, para tratar de estimarlos con más cuidado y después elegir una solución que se mantenga como buena en un cierto intervalo de valores posibles de estos parámetros sensibles. No hay que olvidar que este análisis constituye una parte muy importante de los estudios de programación lineal.

ANEXOS

Programación lineal, resolución gráfica.

Resolución de ejercicio del modelo primal y dual

PROBLEMA PRIMAL EN FORMA CANONICA:

MAX  Z= CX

Sujeto a:

AX £ b

X ³ 0

PROBLEMA DUAL EN FORMA CANONICA:

MIN  Z= BY

Sujeto a:

AY ³ C

Y ³ 0

Ejemplo.

Si el problema primal es:  MAX  Z= 45X1 + 17X2 + 55X3

                              Sujeto a:

                                        X1   +    X2  +     X3   £ 200

                                       9X1  +  8X2  +  10X3  £ 5000

                                       10X1+  7X2  + 21 X3  £ 4000

Xj ³ 0

 El problema dual será:

          MIN  Z= 200Y1 + 5000Y2 + 4000Y3

          Sujeto a:

                      Y1 +   9Y2 + 10Y3  ³ 45

                      Y1 +   8Y2 +   7Y3  ³ 17

                      Y1 + 10Y2 + 21Y3 ³ 55

Yj ³ 0

FORMA DE PRESENTAR EL PROBLEMA DUAL

MIN  =  2X1 -  3X2                                                            

Sujeto a:                                                                                   

          1X1 +  2X2  £  12                                                                      

          4X1 -   2X2  ³   3

          6X1 -   1X2  = 10                                                                         

X1,2  ³ 0

  1.  Llevar el problema a su equivalente de maximización, multiplicando la función objetivo por –1:

MAX  -2X1 + 3X2

Convertir las restricciones ³ en una restricción equivalente £ multiplicando por –1 ambos lados:

-4x1 + 2x2  £ -3 

Para las restricciones de igualdad, obtener 2 restricciones de desigualdad, una de forma £ y la otra de forma ³; después regresar al punto anterior y cambiar la restricción ³ a la forma £:

6X1 – 1X2 £ 10

6X1 – 1X2 ³ 10

6X1 –  1X2  £   10

-6X1 + 1X2  £  -10

Así el problema primal se ha replanteado en la forma equivalente:

MAX  Z= -2X1 + 3X2

Sujeto a:

1X1 + 2X2  £  12

-4X1 + 2X2  £  - 3

6X1 – 1X2   £  10

-6X1 + 1X2  £ -10

X1,2 ³ 0  

Teniendo el problema primal convertido a la forma canónica de un problema de maximización, es fácil llevarlo al problema dual:

MIN    12Y1 – 3Y2 + 10Y3

Sujeto a:

Y1–4Y2 + 6Y3’–6Y3’’ ³-2          Y’3  y  Y’’3      ambas se refieren a la tercera restricción

2Y1 + 2Y2 – 1Y3’ + 1Y3’’  ³   3                         del problema  primal.

Y1, 2, 3’, 3’’ ³ 0

REFERENCIAS ELECTRONICAS.

http://html.rincondelvago.com/analisis-de-sensibilidad_1.html

http://www.andrew.cmu.edu/user/mgoic/files/documents/optimization/dualidad.pdf
http://dualidadenprogramacionlineal.blogspot.com/

ENLACES:
http://dualidadenprogramacionlineal.blogspot.com/