• Author / Uploaded
• Juan Carlos Mar Paz

Citation preview

ALUMNA: MARTHA ELENA FLORES PARRA TAREA: 3 MATERIA: INVESTIGACIÓN DE OPERACIONES MATRICULA: 315775 MAESTRA: SANDRA SÁNCHEZ FECHA: 09/NOVIEMBRE/2016 CCU: CUAUHTEMOC CARRERA: LIC. ADMINISTRACIÓN DE EMPRESAS

TAREA 3 INVESTIGACION DE OPERACIONES Desarrolla los siguientes temas: TEORÍA DE LA DUALIDAD Y ANÁLISIS DE SENSIBILIDAD TEORÍA DE LA DUALIDAD Y ANÁLISIS DE LA SENSIBILIDAD Son aplicaciones que se la hacen al método simplex con el objetivo de garantizar la optimización de un problema y a su vez para un mejor manejo del mismo método.

DUALIDAD resulta de buscar relaciones que permitan obtener información adicional de un problema de optimización general. Esto en programación lineal nos conduce a relaciones primal-dual. Esta relación consiste en que todo problema de optimización primal tiene un problema asociado dual. DUALIDAD La teoría de la dualidad es importante, tanto desde el punto de vista teórico como del práctico. Para cada modelo lineal se puede escribir el modelo dual asociado. RELACIÓN (PRIMAL –DUAL) La relación entre el problema Dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades: o Aporta elementos que aumentan sustancialmente la comprensión de la PL. O El análisis de la dualidad es una herramienta útil en la solución de problemas de PL. O El problema Dual tiene interpretaciones e informaciones importantes. EJEMPLO A RESOLVER EJEMPLO RESUELTO OTRO EJEMPLO ANÁLISIS DE SENSIBILIDAD Consiste en determinar cual es el rango de variación de los parámetros del problema de modo que la base optima encontrada siga siendo óptimo. Buscar el intervalo en que estos parámetros son permisibles en su variación sin que se afecte la solución optima del problema. PARÁMETROS SENSIBLES El objetivo fundamental del análisis de sensibilidad es identificar los parámetros sensibles. Por ejemplo los parámetros cuyos valores no pueden cambiar sin que cambie la solución óptima. IMPORTANCIA DEL ANÁLISIS DE SENSIBILIDAD Es importante porque nos permite investigar el efecto que tendría la solución optima proporcionada por el método simplex en el hecho de que los parámetros (datos de entrada) tomaran otros valores posibles. (CAMBIOS) ANÁLISIS DE SENSIBILIDAD • Intervalo de optimalidad: es el intervalo de variabilidad de un coeficiente de la función objetivo. • Intervalo de factibilidad. Es el intervalo de variabilidad de un lado derecho de una restricción. • Precio Sombra. Cambio en el valor de la función objetivo por aumento unitario en el valor del lado derecho de una restricción.

PROCEDIMIENTO PARA EL ANÁLISIS DE SENSIBILIDAD • Revisión del modelo. • Revisión de la tabla simplex final. • Conversión a la forma apropiada. • Prueba de factibilidad. • Prueba de optimalidad. • Re optimización. http://es.slideshare.net/jorgeandresaceroalmonacid/teora-de-la-dualidad-y-anlisis-de-la-sensibilidad -FORMULACIÓN DE UN PROBLEMA DUAL. FORMULACIÓN DEL PROBLEMA DUAL (Teoría de Dualidad) Hemos visto como la programación lineal puede ser usada para resolver una extensa variedad de problemas propios de los negocios, ya sea para maximizar utilidades o minimizar costos. Las variables de decisión en tales problemas fueron, por ejemplo, el número de productos a producir, la cantidad de pesos a emplear, etc. En cada caso la solución óptima no explicó cómo podrían ser asignados los recursos (ejemplo: materia prima, capacidad de las máquinas, el dinero, etc.) para obtener un objetivo establecido.

En este capítulo veremos que a cada problema de programación lineal se le asocia otro problema de programación lineal, llamado el problema de programación dual. La solución óptima del problema de programación dual, proporciona la siguiente información respecto del problema de programación original:

La solución óptima del problema dual proporciona los precios en el mercado o los beneficios de los recursos escasos asignados en el problema original. La solución óptima del problema dual aporta la solución óptima del problema original y viceversa. EJEMPLO: Una compañía produce y vende 2 tipos de máquinas de escribir: manual y eléctrica. Cada máquina de escribir manual es vendida por un ingreso de 40 dls. y cada máquina de escribir eléctrica produce un ingreso de 60 dls. Ambas máquinas tienen que ser procesadas (ensambladas y empacadas) a través de 2 operaciones diferentes (O1 y O2).

La compañía tiene una capacidad de 2000 hrs. Mensuales para la operación O1 y 1000 hrs. Mensuales de la operación O2. El número de horas requeridas de O1 y O2 para producir un modelo terminado se da en la siguiente tabla.

OPERACIÓN

HORAS

REQUERIDAS

CAPACIDAD

MANUAL

ELECTRICA

(HRS MENSUALES)

O1

3

2

2000

O2

1

2

1000

Encuentre el número óptimo de unidades de cada tipo de máquina de escribir que se debe producir mensualmente para maximizar el ingreso.

OBJETIVO: Maximizar el ingreso total RESTRICCIONES: horas mensuales de las operaciones VARIABLE DE DECISION: número de máquinas de escribir a producir X1 = número de máquinas de escribir manuales X2 = número de máquinas de escribir eléctricas

Maximizar Z= 40 X1 + 60X2 Sujeto a:

Minimizar Z=2000 W1 + 1000 W2

Sujeto a:

V. Básica

Z

W1

W2

S1

S2

Solución

Z

1

0

0

5

25

35000

S1

0

1

0

1/ 2

-1/2

500

W1

0

0

1

-1/ 4

3/ 4

250

Las relaciones de dualidad se pueden resumir en el siguiente cuadro:

La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda.

http://normelisrojas3449.blogspot.mx/2011/05/formulacion-del-problema-dual-teoria-de.html

-CONDICIONES KHUN-TUCKER. Las condiciones de optimalidad establecidas en el Teorema de Karush Kuhn Tucker (KKT) permiten abordar la resolución de modelos de Programación No Lineal que consideran tanto restricciones de igualdad (ecuaciones) como desigualdad (inecuaciones). En términos comparativos las condiciones de KKT son más generales que el Método de Lagrange el cual se puede aplicar a problemas no lineales que consideran exclusivamente restricciones de igualdad. En el siguiente artículo mostraremos cómo utilizar el Teorema de Karush Kuhn Tucker para resolver un problema de Programación No Lineal con 2 variables de decisión.

Sin pérdida de generalidad un modelo de Programación No Lineal se puede representar a través del siguiente formato:

Luego podemos reescribir cualquier problema en dicha estructura manteniendo la equivalencia de la representación matemática. Para ejemplificar lo anterior consideremos el siguiente modelo de optimización no lineal que resulta de interés su resolución.

El problema anterior se puede representar gráficamente a través del software Geogebra de modo de encontrar su solución óptima (x1=2 y x2=1) en el par ordenado etiquetado con la letra “C” en el gráfico a continuación, con valor óptimo V(P)=2. El conjunto de factibilidad corresponde al área achurada. Adicionalmente se puede observar que en la solución óptima se encuentran activas las restricciones 1 y 3 (el resto de las restricciones por cierto se cumple pero no en igualdad).

Por supuesto la resolución mediante el Método Gráfico es sólo referencial y se ha utilizado en este caso para corroborar los resultados a obtener en la aplicación del teorema. En este contexto el problema en su forma estándar es simplemente:

Notar que sólo fue necesario cambiar la forma de las restricciones de no negatividad (esto se puede hacer multiplicando por -1 cada una de ellas). Cabe destacar que en este caso en particular el problema no considera restricciones de igualdad. Luego las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT) están dadas por:

Por ejemplo, si en las condiciones generales anteriores consideramos el problema no restringido (asumiendo que todas las restricciones son inactivas) la solución óptima por simple inspección es x1=3 y x2=2, que corresponde a la coordenada “E” de la gráfica anterior y que se puede observar no es una solución factible para el problema. De este modo la circunferencia de menor radio que intercepta el conjunto de factibilidad es precisamente aquella que pasa por la coordenada “C” donde las restricciones 1 y 3 se cumplen en igualdad, razón por la cual las cuales activaremos de forma simultánea:

Al calcular los gradientes respectivos se obtiene:

Lo cual da origen al siguiente sistema de ecuaciones:

Reemplazando x1=2 y x2=1 podemos despejar los valores de los multiplicadores los cuales cumplen con las condiciones de no negatividad:

Adicionalmente se puede verificar que x1=2 y x2=1 satisface las restricciones omitidas (2, 4 y 5) por lo cual se puede afirmar que dicha solución cumple las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT). http://www.gestiondeoperaciones.net/programacion-no-lineal/teorema-de-karush-kuhn-tucker-aplicado-a-unproblema-de-programacion-no-lineal/

-DUAL-SIMPLEX. El método simplex dual resulta ser una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases. Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetiva de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero. Ejemplo Simplex Dual Considere el siguiente modelo de Programación Lineal:

Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra agregando variables de exceso en cada una de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada

fila de las restricciones por -1 de modo de disponer una solución básica inicial (infactible) en las variables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial. A

B

C

S1

S2

S3

-15

-2

-1

1

0

0

-200

-7,5

-3

-1

0

1

0

-150

-5

-2

-1

0

0

1

-120

315

110

50

0

0

0

0

Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las actuales variables básicas deberá abandonar la base. En el ejemplo el lado derecho más negativo se encuentra en la primera fila, por tanto S1 deja la base. Para determinar cuál de las actuales variables no básicas (A, B, C) entrará a la base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no básica en la fija i (del lado derecho más negativo, marcado en verde) y donde Yj es el costo reducido de la respectiva variable no básica. De esta forma se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo) se encuentra al hacer el primer cociente, por tanto A entra a la base. Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado en el Método Simplex. En el ejemplo se debe dejar a la variable A como básica y S1 como no básica. La tabla que resulta es la siguiente: A

B

C

1

2/15

1/15

0

-2

-1/2

0

-4/3

0

68

S1

S2

S3

0

0

40/3

-1/2

1

0

-50

-2/3

-1/3

0

1

29

21

0

0

1/15

160/3 4.200

Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta disponer de una solución básica factible. Luego de unas iteraciones se obtiene la siguiente tabla final: A

B

C

1

0

0

0

1

0

0

0

0

0

S1

S2

S3

0

1/10

8

¼

-1

3/4

10

1

0

2

-3

60

0

4

10

36

1/10

6.620

La solución óptima es A=8, B=10, C=60 (marcado en verde) con valor óptimo V(P)=6.620 (marcado en rojo - se obtiene con signo cambiado). También es interesante notar que los costos reducidos de las variables artificiales S1, S2 y S3 (marcado en amarillo), corresponde a la solución óptima del modelo presentado en el tutorial de solver, esto dado que dicho modelo resulta ser el problema dual de nuestro ejemplo. http://www.investigaciondeoperaciones.net/metodo_simplex_dual.html

-CAMBIOS EN EL VECTOR DE COSTOS. Cambios en el vector C de coeficientes de la función objetivo. Este cambio se analiza mediante la fórmula: Zj - Cj = CBB-1 A - C = YA - C y da lugar a que se pueda perder la optimalidad de la solución ya obtenida. Debe hacerse la diferencia de cambios en el coeficiente de una variable Xj que no está en la base, en cuyo caso hay cambios en su columna y en los precios sombra; también el caso de cambio al coeficiente de una variable básica, puede resultar en pérdida de factibilidad y/u optimalidad. Se muestran los ejemplos siguientes: Se recurre al siguiente problema muy pequeño, pues contiene tres variables que representan la actividad del problema y sólo dos restricciones. Ejemplo. Cambio en el vector C de costos en MINSENC1. Dado el modelo de PL siguiente y su correspondiente tabla simplex óptima:

http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/Investigacion_de_Operaciones_Ca reaga/Common/IO-modulo3-sensibvectorc.htm

-CAMBIOS EN LOS COEFICIENTES. Cambios en la matriz A de coeficientes tecnológicos de restricciones en variables no básicas. Los cambios en A para variables básicas resultan en cálculos muy complicados, siendo mejor re calcular con el simplex. Para cambio de coeficientes interesa manejar los

de la matriz A de restricciones, en variables no básicas, sólo

de ellas, pues el resto queda igual.

Se procede así: 1ra. Etapa.- Usando la fórmula de Zj - Cj = CB B-1 A - C = YA - C se revisa si el coeficiente indicador Zj Cj cambia de signo. Si no ocurre el cambio de signo en tal coeficiente no es necesario aplicar la 2ª. Etapa, ya que el cambio propuesto no afecta la optimalidad del problema. Cuando el coeficiente Zj - Cj cambia de signo, se entiende que el cambio propuesto, sí provoca la pérdida de optimalidad de la solución que se está revisando y en tal caso se procede a la siguiente etapa.

2ª. Etapa.- Se aplica utilizando la fórmula A* = B-1 A con la cual se calcula la nueva columna a*j. Se aplica el simplex hasta re optimizar. Ejemplo 3-10. Cambio en la matriz A de coeficientes tecnológicos de restricciones (MINSENA1). Dado el modelo de PL siguiente y su correspondiente tabla simplex óptimo:

http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/Investigacion_de_Operaciones_Ca reaga/Common/IO-modulo3-sensibmatriza.htm

-ADICIÓN DE UNA NUEVA VARIABLE. En el estudio y análisis de modelos matemáticos, como los que se ha visto en la asignatura Investigación de Operaciones, puede ocurrir que después de obtenerse una solución al modelo, sedan cuenta que se dejó de incluir un producto que, por las características que posea, va a originar cambios en los resultados de la solución del problema inicial. Para esto, debemos evaluar si la nueva variable es un aporte significativo a los resultados del modelo original. Se puede observar cómo la introducción de nuevas variables crea nuevos vectores y, por tanto, nuevos Cj – Zj, que pueden ser calculados por: Cj – Zj = Cj – CBtB-1Pj Y nuevas columnas en las tablas del simplex, que pueden ser obtenidas por: J = B-1P j De esta forma, el método a seguir es inmediato, dado que si el nuevo término Cj – Z j es negativo, la variable introducida no modifica la estructura del problema. La nueva variable no ha de entrar en la base, con lo que su nivel de utilización es cero. Pero si Cj – Z j es positivo, entonces se introduce Pj en la base y se obtiene su nivel de utilización. En el caso de Cj – Zj nulo, supone que la introducción de nueva variable no va a suponer cambio alguno en Z0 , y puede considerarse entonces como que no supone cambio en la estructura del problema. La incorporación de una nueva variable al problema original produce un aumento de la dimensionalidad de la tabla por la vía de las columnas. Para ver si esa adición altera la solución actualmente óptima, hay que comprobar la condición de optimalidad de esa variable, ya que el aumento de las columnas no afecta la condición de factibilidad de la tabla. La nueva variable añadida Xk, llevará asociado su coeficiente en la función objetivo (Ck), y su vector de coeficientes técnicos (Pk), y habremos de calcular su rendimiento marginal.

Si este rendimiento marginal es menor que cero, la solución actual se mantiene como óptima. Si se anula el rendimiento marginal, significa que hay soluciones alternativas a la actual, pero con el mismo valor de la función objetivo. En el supuesto que dicho rendimiento marginal sea positivo, hemos de introducir la nueva variable en la tabla como variable básica y seguir iterando hasta encontrar la nueva solución óptima. La tabla es óptima cundo todos los rendimientos marginales de las variables no básicas son negativos. https://es.scribd.com/doc/117150074/Cambio-en-los-Coeficientes-Tecnologicos MARTHA ELENA FLORES PARRA MATRICULA 315775 TAREA 3 INVESTIGACION DE OPERACIONES LICENCIATURA EN ADMINISTRACION DE EMPRESAS 09 DE NOVIEMBRE DE 2016 BIBLIOGRAFIA: http://es.slideshare.net/jorgeandresaceroalmonacid/teora-de-la-dualidad-y-anlisis-de-la-sensibilidad http://normelisrojas3449.blogspot.mx/2011/05/formulacion-del-problema-dual-teoria-de.html http://www.gestiondeoperaciones.net/programacion-no-lineal/teorema-de-karush-kuhn-tucker-aplicado-a-unproblema-de-programacion-no-lineal/

http://www.investigaciondeoperaciones.net/metodo_simplex_dual.html http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/Investigacion_de_Operaciones_Ca reaga/Common/IO-modulo3-sensibvectorc.htm http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/Investigacion_de_Operaciones_Ca reaga/Common/IO-modulo3-sensibmatriza.htm https://es.scribd.com/doc/117150074/Cambio-en-los-Coeficientes-Tecnologicos