1 1
2 RECORDAR: La solución óptima obtenida para un PPL está basada en los coeficientes de las restricciones y función objetivo. El Análisis de Sensibilidad indica cuál es el efecto sobre las decisiones y resultados asociados a ciertos cambios que pueden ocurrir en el PPL original. ¿Qué sucede con la solución óptima si los precios caen?¿Si suben los costos de mano de obra?¿Si se contratan trabajadores adicionales?etc. 2
3 DEFINICIÓN DE ANÁLISIS DE SENSIBILIDAD Determinar qué tan sensibles son la solución óptima y el valor de la función objetivo con respecto a cambios en los datos del problema. 3
4 Ejemplo: Una industria fabrica tres productos (productos 1, 2 y 3). Se emplean tres recursos para producirlos (Servicio Técnico, Mano de Obra, Administración) cada uno de ellos medidos en horas hombre (HH).
5 Producto Recursos empleados en HH Beneficio Unitario Precio Unitario Servicio TécnicoMano de ObraAdministración 11102 28 2142618 3156425 Recurso Disponible (Hrs) 100600300 Costo Unitario 412 X 1, X 2, X 3 : Cantidades a producir de los productos 1, 2 y 3 respectivamente.
6 CBCB XBXB 1064000 bibi X1X1 X2X2 X3X3 X4X4 X5X5 X6X6 6X2X2 015/610/6-1/60400/6S.T. 10X1X1 101/6-4/61/60200/6 M.O. 0X6X6 004-201100Adm CJCJ 00-16/6-20/6-4/60 Solución óptima
7 7 a)Se cree que la estimación de horas hombre disponible para servicio técnico podría ser corregida. La estimación corregida es 100+10λ, donde λ es un parámetro desconocido. Encuentre el rango de valores de λ que entrega como mezcla óptima de productos la solución actual. b)Cuánto estaría dispuesto a pagar (en forma adicional) por una unidad extra de cada recurso de diferente tipo. c)Me cobran $7 por una unidad adicional de recurso de Servicio Técnico, ¿estaremos dispuesto a contratarlo? Por qué. d)Me cobran $9 por una unidad adicional del recurso servicio técnico, ¿estaremos dispuestos a contratarlo? Por qué e)Hasta cuánto estaremos dispuestos a pagar por una unidad adicional de recurso mano de obra.
8 8 f)Si se desea mantener esta base óptima, ¿Hasta qué nivel de Mano de Obra conviene contratar en forma adicional a las 600 hrs actuales? g)El departamento de manufactura de la industria, propone producir un nuevo producto que requiere 1 hrs de Servicio Técnico, 4 horas de Mano de Obra y 3 hros de Administración. El departamento de ventas predice que el producto puede ser vendido a $8. ¿Cuál debería ser la decisión de la alta administración? h)Suponga que la compañía decide producir al menos 10 unidades del producto 3, determine la mezcla óptima de productos.
9 Cambios en los Datos del PPL: 1.Cambios en los Coeficientes de Costos (C j ). 1.a) Cambios de Coef. FO de variables no Básicas. 1.b) Cambios de Coef. FO de variables Básicas. 2.Cambios en las constantes del lado derecho (b j ). 3.Cambios en restricciones o matriz de coeficientes (A). 3.a) Agregar nuevas variables. 3.b) Cambiar columnas existentes. 3.c) Agregar nuevas restricciones. 9
10 Ejemplo Maximizar Sujeto a X1, X2, X3 representan las cantidades a producir de ciertos tipos de materiales A, B y C respectivamente. Mano de obra Material Anotar Este Problema 10
11 1º Tableau Tableau Óptimo Producción óptima: 1 del producto A y 2 del producto B. Ésta combinación produce una utilidad total de $8. 11
12 I VARIACIONES EN LA FUNCIÓN OBJETIVO CASO 1.a: Cambios en Coeficientes de FO de Variables no Básicas. En el ejemplo es interesante el caso de la variable X 3: ¿Qué pasa con la solución óptima frente a cambios en el coeficiente C 3 ? Cuando C3 cambia, el valor de la ganancia relativa asociada también cambia. Cuando C3 decrece no hay efecto en la solución óptima. Cuando aumenta, la solución puede verse afectada. ¿Hasta dónde puede aumentar sin afectar la solución óptima? 12
13 La solución sigue siendo óptima mientras se cumpla que: Pero Luego debe cumplirse que: Es decir, mientras el beneficio unitario asociado al producto C sea menor que $4, seguirá siendo inconveniente producirlo. Suponer que el beneficio unitario asociado al producto C aumenta a $6. Luego Entonces la solución actual no es óptima, ya que X 3 debe entrar a la base. 13
14 Luego la búsqueda de la solución óptima continúa. La producción óptima consiste en 2 unidades de A y una de C. 14
15 CASO 1.b: Cambios en Coeficientes de FO de Variables Básicas. Por ejemplo se quiere determinar el efecto de cambios en los beneficios unitarios de A (C 1 ). -Podría bajar hasta un nivel en el que ya no sea conveniente producir el material. - Podría aumentar hasta un nivel en el que convendría sólo producir este material (A). Existe un rango a determinar, dentro del cual la solución óptima no cambia. 15
16 Si C 1 cambia, entonces C B cambia, luego: también cambian, pero mientras se mantengan
17 II VARIACIÓN EN LAS CONSTANTES DEL LADO DERECHO b j Suponer que se aumenta la mano de obra disponible de 1 unidad a 2. Entonces si después del cambio las constantes actualizadas siguen siendo positivas, entonces la combinación óptima de materiales no cambia, pero sí cambia la cantidad de cada uno y el valor de la FO. Para el problema actual se tiene que: Recordar que además son las columnas correspondientes a la base inicial. 17
18 Luego ante el cambio en la cantidad disponible de mano de obra: La combinación A-B aún es óptima, pero las cantidades cambiaron: X 1 = 5, X 2 = 1, X 3 = 0, Z = $13 Suponer que el costo de obtener esa mano de obra adicional es de $4. La pregunta es: ¿CONVIENE? $13 - $8 = $5 > $4 >= Sí conviene. $5 es el precio sombra de la restricción de mano de obra. 18
19 Recordar que los precios sombra se pueden obtener como: Es decir, los precios sombra coinciden con lo obtenido a través del análisis de sensibilidad. Para calcular el rango de variación de las constantes del lado derecho que no hace variar la mezcla de producción, sea:...el nuevo vector de constantes del tableau inicial. 19
20 Para que el último tableau siga siendo óptimo y factible debe cumplirse que: Es decir: X1 y X2 permanecen en la base óptima siempre que la disponibilidad de mano de obra esté entre 3/4 y 3. Pero la solución óptima y el valor de la FO varían. 20
21 Según el valor que tenga b 1 entre ¾ y 3 la solución óptima estará dada por: Ejemplo: Suponer que la disponibilidad de mano de obra aumenta a 4 unidades. Luego: 21
22 Así se llega al tableau óptimo siguiente (infactible): Este problema, que es dual factible, se resuelve por el método dual simplex, y se obtiene la siguiente solución óptima: 22
23 III VARIACIONES EN LA MATRIZ DE RESTRICCIONES CASO 3.a: Agregar Nueva Variable (Actividad) - Suponer el caso en que se crea un producto D que requiere 1 unidad de MO y 1 unidad de material. Puede ser vendido con un beneficio unitario de $3. Es necesario saber si conviene fabricarlo. Se agrega la variable X 6. La solución actual sigue siendo óptima si: 23
24 Luego: Es decir, el nuevo producto no mejora la situación actual. ¿Qué pasaría si la ganancia relativa calculada resulta mayor que cero? 24
25 CASO 3.b: Variación en el Requerimiento de Recursos de las Actividades Existentes -Si el cambio se produce en una variable no básica (producto C), el efecto se estudia de la misma forma que en el Caso 1.a. - Si el cambio se produce en las variables básicas (producto A y/o B), entonces la misma matriz base es afectada, por lo que resulta más conveniente resolver el problema desde el principio. 25
26 CASO 3.c: Agregar una Nueva Restricción Si se agrega una restricción de servicios administrativos donde los productos A, B y C requieren 1, 2 y 1 horas de éstos servicios, siendo la disponibilidad de 10 horas, se agrega la siguiente restricción: Para que la actual solución óptima se mantenga, debe satisfacer la nueva restricción. ¿Qué sucede en este caso en particular? 26
27 Por otra parte, si las horas administrativas disponibles fueran sólo 4, la restricción queda: La solución actual X 1 = 1, X 2 = 2, X 3 = 0 no la satisface. Luego, el último tableau incluyendo la nueva restricción queda:...éste no se encuentra en forma canónica. 27
28 El tableau anterior en forma canónica queda: Dual-factible, luego se resuelve por Dual Simplex. Solución óptima. Razón Mínima (explicación en diapositiva siguiente) 28
29 ¿Por qué en este caso se eligió la razón mínima? Porque en TEORÍA DE DUALIDAD, en los problemas de maximización se utiliza la regla de la razón mínima mientras que en problemas de minimización se utiliza la regla de la razón máxima. En general, siempre se debe elegir la razón más cercana a cero. Ante un empate, se debe usar la regla de Bland. 29
30 OBSERVACION: -Cada vez que se agrega una restricción a un PPL, el nuevo valor óptimo es menor o igual que el antiguo. Es decir, no es posible mejorar la solución óptima agregando restricciones. -Esto se debe a que el espacio de soluciones factibles sólo se acotaría más y no se ampliaría. 30
31 31 Con rubíes y zafiros, Zales Jewelers producen dos tipos de anillos. Un anillo tipo 1 requiere 2 rubíes, 3 zafiros, y 1 hora de trabajo de un joyero. Un anillo tipo 2 requiere 3 rubíes, 2 zafiros, y 2 horas de trabajo de un joyero. Cada anillo tipo 1 se vende a 400 dólares, y cada anillo tipo 2, a 500 dólares. Se pueden vender todos los anillos producidos. Actualmente Zales dispone de 100 rubíes, 120 zafiros y 70 horas de trabajo de un joyero. Se pueden comprar rubíes a un costo de 100 dólares el rubí. La demanda del mercado requiere una producción de por lo menos 20 anillos tipo 1, y por lo menos 25 anillos tipo 2.
32 32 ABRAN EL PROGRAMA LINGO
33 33 Modelo: ◦X 1, X 2 : Anillos tipo 1 y tipo 2 producidos; ◦R: Número de rubíes comprados. Max Z = 400X 1 + 500X 2 – 100R s.a2X 1 + 3X 2 – R ≤ 100…..Rubíes disponibles 3X 1 + 2X 2 ≤ 120…..zafiros disponibles X 1 + 2X 2 ≤ 70 ….HH disponibles X 1 ≥ 20 …. Prod Minima X 2 ≥ 25….. Prod Minima X 1, X 2 ≥ 0
34 34 Salida de Lindo: LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION VALUE 1)19000.00 VARIABLEVALUEREDUCED COST X120.000000.000000 X225.000000.000000 R15.000000.000000 ROWSLACK OR SURPLUSDUAL PRICES 2)0.000000100.0000 3)10.000000.000000 4)0.000000200.0000 5)0.0000000.000000 6)0.000000-200.0000 NO. ITERACIONS=5
35 35 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLECURRENTALLOWABLEALLOWABLE COEF INCREASE DECREASE X1400.00000 INFINITY 100.0000 X2 500.0000 200.00000 INFINITY R-100.0000 100.00000 100.00000 RIGHTHAND SIDE RANGES ROWCURRENTALLOWABLEALLOWABLE RHS INCREASE DECREASE 2100.0000 15.00000 INFINITY 3120.0000 INFINITY 10.00000 4 70.0000 3.333333 0.00000 520.0000 0.000000 INFINITY 625.0000 0.000000 2.50000
36 36 a)Suponga que cada rubí cuesta 190 dólares, en lugar de 100 ¿Todavía compraría Zales Rubíes? ¿Cuál sería la nueva solución óptima? b)Suponga que Zales solamente tuviera que producir 23 anillos tipo 2. ¿Cuál sería la utilidad de Zales ahora? c)Cuál es la máxima cantidad que tendría que estar dispuesto a pagar Zales por otra hora de trabajo de un joyero? d)¿Cuál es la máxima cantidad que tendría que estra dispuesto a pagar Zales por otro Zafiro? e)Zales considera producir anillos tipo 3. Cada anillo tipo 3 puede venderse a 550 dólares y requiere 4 rubíes, 2 zafiros y 1 hora de trabajo de joyero. ¿Tendría que producir Zales anillos tipo 3? Preguntas:
37 37 a)Suponga que cada rubí cuesta 190 dólares, en lugar de 100 ¿Todavía compraría Zales Rubíes? ¿Cuál sería la nueva solución óptima? El coeficiente actual -100 puede disminuir hasta -200 (-100), por lo tanto, su precio puede aumentar hasta 200 y la base se mantiene: 100 < 190 < 200, la base sigue siendo la misma; X B = (X 1, X 2, R, S 2, ?) = (20, 25, 15, 10, 0) Z = 400*20 + 500*25 – 190*15 = 17.650 Respuestas:
38 38 b)Suponga que Zales solamente tuviera que producir 23 anillos tipo 2. ¿Cuál sería la utilidad de Zales ahora? X 2 * = 25X 2 ≥ 25 Row (6) PD (6) = π 6 = -200 Δb (6): (-2,5, 0) Puede disminuir hasta 22,5 y la base se mantiene 22,5 < 23 < 25, por lo tanto, se mantiene la base ΔZ = π 6 * Δb(6) = -200*(-2) = 400 Z * = Z 0 + 400 = 19.400
39 39 c)Cuál es la máxima cantidad que tendría que estar dispuesto a pagar Zales por otra hora de trabajo de un joyero? Row (4) π 4 = 200 Sin embargo, esto es válido mientras: b 4 ≤ 70 + 3,33333. Por lo tanto, estaríamos dispuestos a pagar 200 adicionales a lo que ya se le paga. d)¿Cuál es la máxima cantidad que tendría que estar dispuesto a pagar Zales por otro Zafiro? Row (3) Zafiro No estaría dispuesto a pagar nada, ya que sobran 10 Zafiros y π 3 = 0.
40 40 e)Zales considera producir anillos tipo 3. Cada anillo tipo 3 puede venderse a 550 dólares y requiere 4 rubíes, 2 zafiros y 1 hora de trabajo de joyero. ¿Tendría que producir Zales anillos tipo 3? X 3 : Cantidad de anillos tipo 3 Π = C B *B -1 = (100, 0, 200, 0, -200) C 3 = C 3 – Π*A 3 = 550 – Π*A 3 = -50 Como es de maximización X 3 no entra a la base, por lo tanto, se mantiene la base con X 3 * = 0
41 41 Indiana Jones, el aventurero más famoso de todos los tiempos, se encontraba explorando en las antiguas Ruinas de Teotihuacán (actual México) cuando de pronto fue tomado cautivo por la supuestamente extinta civilización azteca. Nuestro héroe, por su entrometida irrupción en los dominios, fue condenado a muerte por esta civilización guerrera, como sacrificio a los dioses. Sin embargo, en el último momento, el emperador le propone un trato a Jones: “Te daré una oportunidad de redimir tu insolencia de pisar nuestro suelo sagrado; para esto tendrás que pasar la siguiente prueba: Te daré hierro, cuero y diez artesanos para que construyas escudos y espadas para mí. Por cada escudo terminado, te daré tres monedas de oro, y por cada espada, cuatro monedas. Sin embargo, tendrás hasta la puesta de sol para cumplir tu misión. Si logras reunir para entonces más de trescientos cincuenta monedas vivirás; de lo contrario tu cabeza rodará desde la cima de nuestro templo esta misma noche. Por último, ten en cuenta que estos materiales que te doy son un regalo de nuestras divinidades, por lo que deberás usar al menos cuatro unidades de cuero y otras cuatro de hierro, en señal de agradecimiento. Que los dioses se apiaden de ti”. Los artesanos estiman que para cada espada se necesita un artesano, dos unidades de hierro, una de cuero y una hora de trabajo; mientras que para cada escudo son necesarias dos unidades de cuero, una de hierro, un artesano y dos horas de trabajo. Considere que a partir de este momento quedan ocho horas para la puesta de sol.
42 42 a)Formule un PPL que permita determinar si existe la posibilidad de que Indiana Jones se salve. b)Estandarice el problema. c)Formule un PPL que permita la resolución del modelo mediante el algoritmo Simplex. d)¿Es posible que Indiana Jones salga vivo de esta encrucijada? Si su respuesta es afirmativa, ¿cómo debería proceder? e)¿Afecta su respuesta en d) si se aumenta en una unidad los recursos entregados por el emperador azteca? Realice este análisis para la cantidad de artesanos. f)¿Afecta su respuesta en d) si relaja en una unidad los recursos entregados por el emperador azteca? Realice este análisis para el cuero y el hierro. g)¿Cómo debería cambiar la oferta hecha por el emperador en cuanto al artículo que no planea fabricar Indiana Jones en d), para que ahora decida fabricar dicho artículo? h)Si ahora el emperador le rebaja a Jones la meta a diez monedas, pero le rebaja el tiempo a una hora y le da tres artesanos. ¿Cree usted que Indiana Jones podrá salvarse? Justifique.
43 43 PROBLEMA (Resolver por método gráfico y simplex [revisado]) Panchito vende quequitos y rosquillas fuera de la UCN a las 13:00 hrs, cuando los estudiantes regresan a sus casas a almorzar o están llegando a clases. Panchito vende cada quequito a $400 y cada rosquilla a $150. Como buen trabajador, comienza sus labores a las 06:00 hrs para dedicar toda la mañana a su proceso de producción. Panchito demora 6 minutos en producir un quequito y 3 minutos en una rosquilla. Panchito cuenta con 1 L de aceite diario para producir sus quequitos y rosquillas, por lo que se vio obligado a calcular las cantidades que consume cada producto durante su preparación, llegando a la conclusión que cada quequito consume 20 mL y cada rosquilla 10 mL. Además, sabe que gasta entre 3 y 5 kg de harina, y que un quequito y rosquilla requiere 50 y 35 g de harina respectivamente. Los costos totales de producir un quequito y rosquilla son $100 y $50 respectivamente. Panchito vive en La Serena y por los múltiples tacos que hay en la ciudad demora 1 hora y media en llegar a la universidad.
44 44 a) Modele el problema. b) ¿Cuál es el supuesto principal que involucra este modelo? c) Estandarizar el modelo. d) Formule un PPL que permita la resolución del modelo mediante el algoritmo Simplex. e) Resolver el modelo.
45 45 f) ¿Existe alguna posibilidad de mejorar las utilidades si se aumenta el mínimo de harina necesario en medio kilogramo? Argumente su respuesta. g) Un estudiante de ingeniería, cliente habitual del Sr. Llado, asegura que puede reducir los costos de producción, si éste le compra un invento, el cual le permitiría reducir el consumo de aceite a un máximo de medio litro por día. La maquina, según el estudiante, al aumentar la presión durante la cocción de los alimentos, puede reducir en un 50% y 30% el consumo de aceite de los Arrollados y Wantanes, respectivamente. Por esta razón Aldo Llado pide a los estudiantes de Investigación de Operaciones I, su ayuda en la toma de la decisión. ¿Es posible la afirmación del estudiante inventor?, ¿Por qué? Interprete sus resultados EN EL CONTEXTO DEL PROBLEMA. h) Juan Pérez, un vecino de Aldo, es dueño de un Taxi que conduce a diario, pero de vez en cuando, especialmente en momentos en el que el negocio no anda muy bien, ofrece al Sr. Llado trasladar a él y su mercancía a la Universidad por la módica suma de $5.000. Pero últimamente, con el alza en los precios de lo combustibles, Juan se ve en la obligación de subir su tarifa general, y por consiguiente, la del traslado de su vecino y sus productos, quedando la nueva tarifa en $6.000. ¿Es conveniente para Aldo seguir utilizando este medio de transporte a pesar del alza en la tarifa?, ¿Por qué? Considere que si se utiliza el taxi, solo se tarda 30 minutos en llegar a su destino.