Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
pautas-2011
Estudiando Ingenieria
Esta es una vista previa del archivo. Inicie sesión para ver el archivo original
certamen_2_iov-2010.pdf 1 Certamen 2 Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesor: Carlos Obreque Níñez Fecha: viernes 4 de junio de 2010 Profesor Ayudante: Gonzalo Baeza Villa Problema 1 (30 puntos). Una empresa fabrica tres tipos de osos de peluche. Los respectivos precios de venta son: 9, 4 y 7 unidades monetarias [u.m.]. Cada oso requiere de 6, 3 y 5 [u.m.] respectivamente, de materia prima, disponiéndose de un máximo de 25.000 [u.m.] para la adquisición de dicha materia prima. Se dispone de la mano de obra necesario para fabricar (simultáneamente) 2.000 osos de cada tipo. Los osos del segundo tipo necesitan la mitad de mano de obra que los del tipo primero o tercero. Además, el número de osos del primer tipo no puede superar al total del restante. Defina las variables de decisión y formule un modelo de programación lineal. Problema 2 (40 puntos) Se desea alimentar de carbón cuatro centrales térmicas desde tres minas. Las minas producen 750, 350 y 400 unidades de carbón a un costo de 10, 15 y 20 unidades monetarias, respectivamente. Las centrales térmicas deben producir 100, 150, 300 y 200 unidades de potencia. Por cada unidad de carbón se producen 1/2, 1/2, 1/3 y 1/4 unidades de potencia en las respectivas centrales. Los costos unitarios de transporte del carbón a las centrales son: C1 C2 C3 C4 M1 4 3 2 1 M2 3 5 6 2 M3 6 4 3 3 a) Construya la tabla de transporte y encuentre una sbf por la regla de la esquina nor-oeste. b) Obtenga la solución óptima. c) Suponga, además, que el carbón producido en las minas 1 y 2 se puede enviar a las centrales 1, 3 y 4 pasando por la central 2. Los costos unitarios de transporte desde la central 2 a las centrales 1, 3 y 4 son 2, 1 y 3 unidades monetarias, respectivamente. Construya la tabla de transporte apropiada. 2 Problema 3. (30 puntos) Considere el siguiente modelo de programación lineal: El algoritmo Simplex produce la siguiente tabla intermedia: 1x 2x′ 2x′′ 3x 4x 5x 6x b Z 0 4 -4 0 -1 0 1+M 1 3x 0 8 -8 1 -3 0 3 18 1x 1 1 -1 0 -1 0 1 1 5x 0 -7 7 0 4 1 -4 4 a) Indique si la solución básica factible actual es la solución óptima. Si su respuesta es negativa, determine el óptimo. Justifique su respuesta. b) Obtenga la solución óptima del problema dual. c) Suponga que en la tercera restricción, las unidades del recurso son 10 en lugar de 8. Determine la nueva solución óptima. d) Suponga que se tiene que incorporar la siguiente restricción: 22 21 ≤− xx . Determine la nueva solución óptima. Tiempo: 90 minutos Maximizar Z= s.a. 21 3xx − 1553 21 ≤+− xx 121 ≥+ xx 834 21 ≤− xx nrsxx 21 ,0≥ 3 Solución. Problema 1. (30 puntos) 3 2 1 3 2 1 tipopeluchedeosodelproduciraUnidadesx tipopeluchedeosodelproduciraUnidadesx tipopeluchedeosodelproduciraUnidadesx decisióndeVariables = = = a/s xxxZMax 321 23 ++= 0321 ≥x,x,x Problema 2. (40 puntos) a.- Solución por el método de la esquina noroeste. O 14 13 12 11 200 300 250 18 20 21 17 350 26 24 23 23 300 100 0 0 0 0 700 D 200 300 900 800 M3 400 F 700 M1 750 M2 350 C1 C2 C3 C4 b.- Aproximación por el método de Vogel. O 14 13 12 11 2 1 700 50 18 20 21 17 0 2 3 350 26 24 23 23 2 0 -1 400 0 0 0 0 200 300 200 1 D C1 C2 C3 C4 400 M1 M2 F M3 200 300 900 800 700 350 750 0 02 0002 0002 0002 00025536 321 312 3 2 1 321 =−− =−− ≤ ≤ ≤ ≤++ xxx xxx .x .x .x .xxx 4 Solución óptima (1 iteración): O 14 13 12 11 2 1 300 450 18 20 21 17 0 2 3 350 26 24 23 23 3 1 400 1 0 0 0 0 200 300 200 1 D F 700 200 300 900 800 M2 350 M3 400 C1 C2 C3 C4 M1 750 Z = 23.700 unidades monetarias. c.- solución del problema de transbordo. En este problema se debe duplicar la central numero dos, como nodo de transbordo y nodo de destino, esto es por que se debe enviar unidades desde M3 hasta C2. 2200 M1 M2 M3 C´2 C1 C2 C3 C4 14 13 12 11 18 20 21 17 26 24 23 23 F 0 0 0 0 750 350 400 700 200 300 900 800 2200 13 20 1 0 2 3 1100 1100 5 El tableau seria: O 14 13 13 12 11 18 20 20 21 17 26 24 M 23 23 2 0 0 1 3 0 0 M 0 0 D C1 C2 C3 C4C´2 M1 750 M2 350 M3 400 F 700 C´2 1100 200 300 900 8001100 Problema 3. (30 puntos) Considere el siguiente modelo de programación lineal: El algoritmo Simplex produce la siguiente tabla intermedia: Maximizar Z= s.a. 221 33 xxx ′′+′− 8334 1 15553 5221 4221 3221 =+′′+′− =−′′−′+ =+′′−′+− xxxx xxxx xxxx 0,0,,0,0,0 543221 ≥≥≥≥′′≥′≥ xxxxxx Maximizar Z= s.a. 6221 33 Mxxxx −′′+′− 8334 1 15553 5221 64221 3221 =+′′+′− =+−′′−′+ =+′′−′+− xxxx xxxxx xxxx 0,,0,,0,0,0 6543221 ≥≥≥≥′′≥′≥ xxxxxxx 1x 2x′ 2x′′ 3x 4x 5x 6x b Z -1 3 -3 0 0 0 M 0 3x -3 5 -5 1 0 0 0 15 6x 1 1 -1 0 -1 0 1 1 5x 4 -3 3 0 0 1 0 8 Maximizar Z= s.a. 21 3xx − 1553 21 ≤+− xx 121 ≥+ xx 834 21 ≤− xx nrsxx 21 ,0≥ 6 1x 2x′ 2x′′ 3x 4x 5x 6x b Z -1-M 3-M -3+M 0 M 0 0 -M 3x -3 5 -5 1 0 0 0 15 6x 1 1 -1 0 -1 0 1 1 5x 4 -3 3 0 0 1 0 8 1x 2x′ 2x′′ 3x 4x 5x 6x b Z 0 4 -4 0 -1 0 1+M 1 3x 0 8 -8 1 -3 0 3 18 1x 1 1 -1 0 -1 0 1 1 5x 0 -7 7 0 4 1 -4 4 1x 2x′ 2x′′ 3x 4x 5x 6x b Z 0 0 0 0 9/7 4/7 M-9/7 23/7 3x 0 0 0 1 11/7 8/7 -11/7 158/7 1x 1 0 0 0 -3/7 1/7 3/7 11/7 2x′′ 0 -1 1 0 4/7 1/7 -4/7 4/7 b) Solución del problema dual asociado. ( ) ( ) 74 79 0 74710 73710 711781 310 3 2 1 1 321 /y /y y // // // B*cy,y,y * * * t b *** = −= = − − == − c) Agregando el nuevo valor del recurso = − − == − 7/6 7/13 7/174 '' 10 1 15 7/17/40 7/17/30 7/87/111 * 2 1 3 1 x x x bBxB 7 31 7 6 3 7 13 = −×−=Z 7 d) Verificando si la solución optima satisface las condiciones de la nueva restricción. 22 21 ≤− xx ( ) ( ) 27/19 27/427/11 ≤/ ≤−− La solución óptima no satisface las condiciones de la nueva restricción. Entonces se debe ingresar la restricción al tableau óptimo. 1x 2x′ 2x′′ 3x 4x 5x 6x x7 b Z 0 0 0 0 9/7 4/7 M-9/7 0 23/7 3x 0 0 0 1 11/7 8/7 -11/7 0 158/7 1x 1 0 0 0 -3/7 1/7 3/7 0 11/7 2x′′ 0 -1 1 0 4/7 1/7 -4/7 0 4/7 x7 1 -2 2 0 0 0 0 1 2 Canonizamos x1: 1x 2x′ 2x′′ 3x 4x 5x 6x x7 b Z 0 0 0 0 9/7 4/7 M-9/7 0 23/7 3x 0 0 0 1 11/7 8/7 -11/7 0 158/7 1x 1 0 0 0 -3/7 1/7 3/7 0 11/7 2x′′ 0 -1 1 0 4/7 1/7 -4/7 0 4/7 x7 0 -2 2 0 3/7 -1/7 -3/7 1 3/7 Canonizamos x’2 y luego aplicamos simplex dual: 1x 2x′ 2x′′ 3x 4x 5x 6x x7 b Z 0 0 0 0 9/7 4/7 M-9/7 0 23/7 3x 0 0 0 1 11/7 8/7 -11/7 0 158/7 1x 1 0 0 0 -3/7 1/7 3/7 0 11/7 2x′′ 0 -1 1 0 4/7 1/7 -4/7 0 4/7 x7 0 0 0 0 -5/7 -3/7 5/7 1 -5/7 1x 2x′ 2x′′ 3x 4x 5x 6x x7 b Z 0 0 0 0 1/3 0 M-1/3 1 1/3 7/3 3x 0 0 0 1 - 1/3 0 1/3 8/3 62/3 1x 1 0 0 0 - 2/3 0 2/3 1/3 4/3 2x′′ 0 -1 1 0 1/3 0 - 1/3 1/3 1/3 x5 0 0 0 0 5/3 1 -5/3 -7/3 5/3 Certamen-Parte-2+Pauta-2008.doc= Z Maximizar Certamen 2 Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesor: Carlos Obreque Niñez Fecha: Martes 13 de mayo de 2008 Problema 1. (25 puntos) Considere el siguiente modelo de programación lineal: s.a. 3 2 1 3 5 4 x x x + + 120 5 6 2 3 2 1 £ + + x x x 150 10 3 4 3 2 1 £ + + x x x 0 , 0 , 0 3 2 1 ³ ³ ³ x x x Sabiendo que la tabla óptima viene dada por: 1 x 2 x 3 x 4 x 5 x b Z 0 0 7 4/9 7/9 170 2 x 0 1 0 2/9 –1/9 10 1 x 1 0 5/2 –1/6 1/3 30 Responda las siguientes preguntas de manera independiente: a) Suponga que el costo asociado a la variable 2 x es 6 en lugar de 5. Cuál es la nueva solución óptima. b) Si el recurso de la primera restricción aumenta en una unidad, en cuánto aumenta o disminuye el valor de la función objetivo?. Justifique su respuesta. Problema 2. (25 puntos) Una corporación ha decidido producir tres productos nuevos. En este momento, cinco de sus plantas tienen exceso de capacidad de producción. El costo unitario de fabricación del primer producto será de $31, $29, $32, $28 y $29, en las plantas 1, 2, 3, 4 y 5, respectivamente. El costo unitario de producción del segundo producto será de $45, $41, $46, $42 y $43, en las plantas respectivas 1, 2, 3, 4 y 5. El costo unitario de fabricación del tercer producto será de $38, $35 y $40, en las plantas 1, 2 y 3, respectivamente, mientras que las plantas 4 y 5 no pueden fabricar este producto. Los pronósticos de venta indican que la producción diaria de cada uno de los tres productos debe ser 500, 1100 y 800 unidades de los productos 1, 2 y 3, respectivamente. Las plantas 1, 2, 3, 4 y 5 tienen capacidad para producir 400, 600, 400, 600 y 1000 unidades diarias, independientemente del producto o combinación de productos que se quiera. Suponga que cualquier planta que tiene capacidad y puede fabricarlos podrá producir cualquier combinación de productos en cualquier cantidad. La gerencia ha decidido cerrar la planta 3, por tal motivo está dispuesta a producir toda su capacidad de producción pero no está dispuesta a mantener en sus dependencias ninguna cantidad de éstas. La gerencia desea saber cómo asignar los nuevos productos a las plantas con el fin de minimizar el costo total de fabricación. a) Formule este problema como un modelo de transporte, construya la tabla de costos y requerimientos. b) Determine una solución básica factible c) Encuentre la solución óptima d) Si el problema tiene soluciones múltiples entonces encuentre otra solución óptima. En caso contrario, explique porqué no hay otras soluciones. Problema 3. (25 puntos) Una empresa de transportes debe enviar desde las comunas A y B, 75 y 70 toneladas de carga a las comunas X, Y y Z, respectivamente. La comuna X requiere de 35 toneladas de carga, la comuna Y solicita 65 toneladas y la comuna Z de 50 toneladas. Los embarques se pueden realizar a través de puntos intermedios a un costo (dado en $/ton) igual a la suma de los costos de los tramos de la ruta, los cuales se reflejan en la tabla siguiente: A B X Y Z A – 21 56 62 93 B 21 – 17 54 67 X 56 17 – 60 98 Y 62 54 60 – 27 Z 93 67 98 27 – Los representantes de las comunas que esperan recibir toda la carga que están solicitando han establecido una multa equivalente a 2, 3 y 4 pesos por cada tonelada que no sea satisfecha en las comunas X, Y y Z, respectivamente. Construya la tabla de transporte que permita encontrar la solución que minimiza el costo total de transportar toda la carga. (No se pide que resuelva el problema, sólo construir la tabla) Problema 4 (25 puntos) Una estación terminal tiene capacidad para acomodar 4 camiones simultáneamente. El situar cada camión en uno de los cinco lugares implica un costo de distribución y transferencia de cargas que se refleja en la tabla que sigue. Los lugares de carga son A, B, C y D. El camión que no pueda ser asignado a un lugar de carga debe esperar su turno, pero se impone un costo adicional de 90, 85, 95, 87 y 92 para el camión 1, 2, 3, 4 y 5, respectivamente. Determinar el estacionamiento óptimo y el costo total mínimo. Terminales Camiones A B C D 1 70 – 40 80 2 50 30 25 – 3 40 32 90 24 4 – 60 30 20 5 20 25 35 10 Tiempo: 2 horas Problema 1 = Z Maximizar s.a. 3 2 1 3 5 4 x x x + + 120 5 6 2 3 2 1 £ + + x x x 150 10 3 4 3 2 1 £ + + x x x 0 , 0 , 0 3 2 1 ³ ³ ³ x x x 1 x 2 x 3 x 4 x 5 x b Z 0 0 7 4/9 7/9 170 2 x 0 1 0 2/9 –1/9 10 1 x 1 0 5/2 –1/6 1/3 30 a) Ahora 3 2 1 3 6 4 x x x Z + + = y reemplazando en la primera fila, se obtiene 1 x 2 x 3 x 4 x 5 x b Z -4 -6 -3 0 0 0 2 x 0 1 0 2/9 –1/9 10 1 x 1 0 5/2 –1/6 1/3 30 Actualizando la tabla, ya que no está en la forma canónica, se tiene 1 x 2 x 3 x 4 x 5 x b Z 0 0 7 2/3 2/3 180 2 x 0 1 0 2/9 –1/9 10 1 x 1 0 5/2 –1/6 1/3 30 La solución continúa siendo óptima y el nuevo valor de la función objetivo es 180 b) Hay dos maneras de responder esta pregunta i) Hay que utilizar el costo reducido de la variable de holgura asociado a la primera restricción. Dado que la variable de holgura es 4 x , se concluye que la función objetivo se incrementa en 4/9. ii) La otra forma es calculando explícitamente el valor. De la tabla óptima se obtiene: ÷ ÷ ø ö ç ç è æ - - = - 3 1 6 1 9 1 9 2 1 B , ÷ ÷ ø ö ç ç è æ = ÷ ÷ ø ö ç ç è æ = 1 2 2 1 x x x x x B B B , ÷ ÷ ø ö ç ç è æ = 150 121 b b B x B v v 1 - = Þ ÷ ÷ ø ö ç ç è æ = ÷ ÷ ø ö ç ç è æ ÷ ÷ ø ö ç ç è æ - - = ÷ ÷ ø ö ç ç è æ 9 179 9 92 3 1 6 1 9 1 9 2 150 121 2 1 B B x x v v EMBED Equation.3 Þ EMBED Equation.3 ÷ ÷ ø ö ç ç è æ = ÷ ÷ ø ö ç ç è æ 9 179 9 92 1 2 x x ( ) ( ) 9 4 170 9 1534 4 5 ) ( 9 179 9 92 1 2 1 2 2 1 2 1 + = = ÷ ÷ ø ö ç ç è æ = ÷ ÷ ø ö ç ç è æ = ÷ ÷ ø ö ç ç è æ = = x x c c x x c c x c Z B B B B B t B v v v v v Problema 2 Producto 1 Producto 2 Producto 3 Ficticio Oferta Planta 1 31 45 38 0 400 41 4 4 3 400 Planta 2 29 41 35 0 600 41 2 0 400 200 Planta 3 32 46 40 M 400 46 0 0 400 M-5 Planta 4 28 42 M 0 600 42 500 100 4 -1 Planta 5 29 43 M 0 1000 43 0 1000 M-37 -2 Demanda 500 1100 800 600 -14 0 -6 -41 Producto 1 Producto 2 Producto 3 Ficticio Oferta Planta 1 31 45 38 0 400 43 4 2 1 400 Planta 2 29 41 35 0 600 41 2 0 600 2 Planta 3 32 46 40 M 400 46 0 200 200 M-3 Planta 4 28 42 M 0 600 42 500 100 M-36 1 Planta 5 29 43 M 0 1000 43 0 800 M-37 200 Demanda 500 1100 800 600 -14 0 -6 -43 Costo Total = 90.800 Otra solución óptima Producto 1 Producto 2 Producto 3 Ficticio Oferta Planta 1 31 45 38 0 400 43 4 2 1 400 Planta 2 29 41 35 0 600 41 200 400 2 Planta 3 32 46 40 M 400 46 2 0 400 M-3 Planta 4 28 42 M 0 600 42 500 100 M-36 1 Planta 5 29 43 M 0 1000 43 0 800 M-37 200 Demanda 500 1100 800 600 -14 0 -6 -43 Costo Total = 90.800 Problema 3 A B X Y Z Oferta A 0 21 56 62 93 225 B 21 0 17 54 67 220 X 56 17 0 60 98 150 Y 62 54 60 0 27 150 Z 93 67 98 27 0 150 F M M 2 3 4 5 Demanda 150 150 185 215 200 Problema 4 A B C D F 1 70 M 40 80 90 2 50 30 25 M 85 3 40 32 90 24 95 4 M 60 30 20 87 5 20 25 35 10 92 A B C D F 1 30 M-40 0 40 50 2 25 5 0 M-25 60 3 16 8 66 0 71 4 M-20 40 10 0 67 5 10 15 25 0 82 A B C D F 1 20 M-45 0 40 0 2 15 0 0 M-25 10 3 6 3 66 0 21 4 M-30 35 10 0 17 5 0 10 25 0 32 A B C D F 1 23 M-45 0 43 0 2 18 0 0 M-22 10 3 6 0 63 0 18 4 M-30 32 7 0 14 5 0 7 22 0 29 1 ( F 2 ( C 3 ( B 4 ( D 5 (A Costo = 187 600 800 11000 500 1000 600 400 600 400 Ficticio Producto 3 Producto 2 P5 P4 + P3 P2 Producto 1 P1 - - + - + + + – – _1272291738.unknown _1272291988.unknown _1272292549.unknown _1278745875.unknown _1278745725.unknown _1272292152.unknown _1272291834.unknown _1272291878.unknown _1272278634.unknown _1272278641.unknown _1272273112.unknown _1272182277.unknown _1272182543.unknown _1272182633.unknown _1272182658.unknown _1272182665.unknown _1272182553.unknown _1272182524.unknown _1272182533.unknown _1272182376.unknown _1272182201.unknown _1272182244.unknown _1272182175.unknown Examen_Repeticin+Pauta-2010.doc2 1 2 x x + - Examen de Repetición Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesor: Carlos Obreque Níñez Fecha: jueves 24 de junio de 2010 Profesor Ayudante: Gonzalo Baeza Villa Problema 1. (25 puntos) El departamento de marketing de una prestigiosa marca de zapatos ha estimado las siguientes demandas, en pares de zapatos, para el primer semestre del año 2011: Enero, 2000; Febrero, 2600; Marzo, 2400; Abril, 3400; mayo, 1900; junio, 1500. La producción de un par de zapatos, con tiempo normal, cuesta 5000 pesos y con tiempo extra, 8000 pesos. En cada mes, la producción normal se limita a 2000 pares de zapatos y la producción de tiempo extra se limita a 1000 pares de zapatos. Cuesta 500 pesos al mes, mantener un par de zapatos en inventario. Plantee un modelo de transporte balanceado para minimizar el costo total de satisfacer, a tiempo, las demandas de los siguientes seis meses. Encuentre, además, una solución básica factible mediante el método de la esquina Nor-Oeste. Problema 2. (25 puntos) Considere el siguiente modelo de programación lineal: Maximizar Z = ' ' x 2 ''x 2 s/a 54 9 6 2 1 £ + - x x 56 16 7 2 1 £ + x x 24 6 4 2 1 £ - - x x s . r . n x , x 2 1 0 £ Asumiendo que 3 x , 4 x y 5 x son las variables de holgura asociadas a las tres restricciones y que la tabla siguiente muestra los resultados de una iteración intermedia del algoritmo Simplex. 1 x ¢ 2 x ¢ 2 x ¢ ¢ 3 x 4 x 5 x b Z -15/8 0 0 0 1/8 0 7 3 x 159/16 0 0 1 - 9/16 0 45/2 2 x ¢ -7/16 1 -1 0 1/16 0 7/2 5 x 11/8 0 0 0 3/8 1 45 a) Determine si la solución básica factible actual es la solución óptima. Si su respuesta no es afirmativa, encuentre la solución óptima. b) Obtenga la nueva solución óptima si el valor del lado derecho de la segunda restricción es 60 en lugar de 56. Problema 3. (25 puntos) El administrador de un supermercado necesita 16 cajas de naranjas, 5 cajas de plátanos y 20 cajas de manzanas, para ponerlos a la venta durante el fin de semana que viene. En el mercado de la fruta, hay dos mayoristas, A y B, que pueden suministrar esta mercadería, pero ellos sólo venden la fruta en contenedores completos. El mayorista A despacha en cada contenedor 8 cajas de naranjas, 1 caja de plátanos y 2 cajas de manzanas. En cambio, el mayorista B incluye en cada contenedor 2 cajas de naranjas, una caja de plátanos y 7 cajas de manzanas. Sabiendo que el mayorista A se encuentra a 150 kilómetros de distancia y el mayorista B a 300 kilómetros, determinar cuántos contenedores habrá de comprar a cada mayorista, con objeto de ahorrar tiempo y dinero, reduciendo al mínimo la distancia de lo solicitado. a) Defina las variables de decisión y formule un modelo de programación lineal que permita resolver este problema. b) Encuentre la solución óptima por el método gráfico Problema 4. (25 puntos) La figura que sigue representa una red de oleoducto. Los diferentes nodos representan estaciones de bombeo y/o de recepción. Las longitudes en Kilómetros de los diversos segmentos de la red se muestran en los arcos respectivos. Las estaciones de origen son 1 y 3, con una capacidad de bombeo de 50.000 y 60.000 m3, respectivamente. Las estaciones receptoras son 5 y 6, con una demanda de 80.000 y 20.000 m3, respectivamente. 5 x 5 x ' x 2 'x 2 ' x 1 'x 1 5 x 5 x 4 x 4 x 3 x ' ' x 2 ''x 2 ' x 2 'x 2 ' x 1 'x 1 5 x 5 x ' x 2 'x 2 3 x 3 x 5 x 5 x 4 x 4 x 3 x ' x 1 'x 1 5 x 5 x 4 x 4 x 3 x 3 x 5 x 5 x 4 x 4 x 3 x ' x 1 'x 1 3 x 3 x 4 x 4 x 5 x 5 x Suponiendo que el costo es proporcional a la longitud recorrida, construya la tabla de transporte que permita resolver este problema al mínimo costo. Tiempo, 90 minutos Problema 1 Enero Febrero Marzo Abril Mayo Junio Fictico Oferta Enero Tiempo Normal 3 x 5000 5500 6000 6500 7000 7500 0 2000 2000 Tiempo Extra ' x 1 'x 1 8000 ' x 2 'x 2 8500 9000 9500 10000 10500 0 1000 0 1000 Febrero Tiempo Normal M 5000 5500 6000 6500 7000 0 2000 1600 400 Tiempo Extra M 8000 8500 9000 9500 10000 0 1000 1000 Marzo Tiempo Normal M M 5000 5500 6000 6500 0 2000 1000 1000 Tiempo Extra M M 8000 8500 9000 9500 0 1000 1000 Abril Tiempo Normal M M M 5000 5500 6000 0 2000 1400 600 Tiempo Extra M M M 8000 8500 9000 0 1000 1000 Mayo Tiempo Normal M M M M 5000 5500 0 2000 300 1500 200 Tiempo Extra M M M M 8000 8500 0 1000 1000 Junio Tiempo Normal M M M M M 5000 0 2000 2000 Tiempo Extra M M M M M 8000 0 1000 1000 Demanda 2000 2600 2400 3400 1900 1500 4200 18000 Problema 2 Realizamos el siguiente cambio de variable: 0 2 2 1 2 2 2 1 1 ³ - = - = ' ' x , ' x , ' x ' ' x ' x x ' x x Reemplazando en el problema original resulta: MAX Z = ( ) ( ) ' ' x ' x ' x 2 2 1 2 - + - - MAX Z = ' ' x ' x ' x 2 2 1 2 2 - + s/a ( ) ( ) 54 9 6 3 2 2 1 = + - + - - x ' ' x ' x ' x ( ) ( ) 56 16 7 4 2 2 1 = + - + - x ' ' x ' x ' x ( ) ( ) 24 6 4 5 2 2 1 = + - - - - x ' ' x ' x ' x 0 2 2 1 ³ ' ' x , ' x , ' x s/a 54 9 9 6 3 2 2 1 = + - + x ' ' x ' x ' x 56 16 16 7 4 2 2 1 = + - + - x ' ' x ' x ' x 24 6 6 4 5 2 2 1 = + + - x ' ' x ' x ' x 0 2 2 1 ³ ' ' x , ' x , ' x 2 x ¢ 2 x ¢ ¢ b Z -1 -2 2 0 0 0 0 6 9 -9 1 0 0 54 -7 16 -16 0 1 0 56 4 -6 6 0 0 1 24 2 x ¢ 2 x ¢ ¢ b Z -15/8 0 0 0 1/8 0 7 159/16 0 0 1 - 9/16 0 45/2 -7/16 1 -1 0 1/16 0 7/2 11/8 0 0 0 3/8 1 45 b Z 0 0 0 10/53 1/53 0 596/53 1 0 0 16/159 - 3/53 0 120/53 0 1 -1 7/159 2/53 0 238/53 0 0 0 - 22/159 24/53 1 2220/53 Solución óptima. 53 120 1 * 1 - = ¢ - = x x , 53 238 0 53 238 2 2 * 2 = - = ¢ ¢ - ¢ = x x x , 53 596 * = Z b).- Aplicamos la formula: b B X X B B D ´ + = - 1 * ÷ ÷ ÷ ø ö ç ç ç è æ = ÷ ÷ ÷ ø ö ç ç ç è æ ´ ÷ ÷ ÷ ø ö ç ç ç è æ - - + ÷ ÷ ÷ ø ö ç ç ç è æ = ÷ ÷ ÷ ø ö ç ç ç è æ ¢ ¢ = ÷ ÷ ÷ ø ö ç ç ç è æ = 53 / 2316 53 / 246 53 / 108 0 4 0 1 53 / 24 159 / 22 0 53 / 2 159 / 7 0 53 / 3 159 / 16 53 2220 53 238 53 120 5 2 1 3 2 1 x x x x x x X B B B B ( ) ( ) 53 600 53 / 2316 53 / 246 53 / 108 0 2 1 3 2 1 3 2 1 = ÷ ÷ ÷ ø ö ç ç ç è æ ´ = ÷ ÷ ÷ ø ö ç ç ç è æ ´ = B B B B B B x x x c c c Z Problema 3 Definimos las variables de decisión: xA = Número de contenedores a comprar al mayorista A. xB = Número de contenedores a comprar al mayorista B. MIN Z = B A x x 300 150 + s/a 16 2 8 ³ + B A x x 5 ³ + B A x x 20 7 2 ³ + B A x x 0 0 ³ ³ B A x , x Resolviendo Gráficamente. Problema 4 2 4 5 6 7 Ficticio Oferta 1 20 M M M 4 0 50 2 0 M M 5 9 0 110 3 M 30 M M 9 0 60 4 M 0 2 M 5 0 110 6 M M 4 0 M 0 110 7 9 5 10 13 0 0 110 Demanda 110 110 80 20 + 110 110 10 � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� � EMBED Equation.3 ��� R.S.F xA=10 xB=0 Z=1500 xA=3 xB=2 Z=1050 xA=0 xB=8 Z=2400 xA=1 xB=4 Z=1350 xB � EMBED Equation.3 ��� � EMBED Equation.3 ��� xA 1 � EMBED Equation.3 ��� 2 3 4 5 6 7 5 4 10 9 2 20 4 9 30 13 5 4 puntos 4 puntos 2 puntos 5 puntos Tabla óptima:15 puntos Solución: 5 puntos Tabla: 20 puntos Solución básica factible inicial: 5 puntos 4 puntos 4 puntos 2 puntos Tabla: 5 puntos Tabla: 15 puntos Tabla: 5 puntos PAGE 6 _1338907423.unknown _1338994010.unknown _1339063526.unknown _1339066130.unknown _1339066161.unknown _1339066177.unknown _1339065656.unknown _1339065842.unknown _1339066018.unknown _1339063588.unknown _1338994522.unknown _1338994583.unknown _1338994100.unknown _1338907514.unknown _1338993952.unknown _1338907466.unknown _1338740642.unknown _1338823235.unknown _1338905013.unknown _1338905030.unknown _1338825876.unknown _1338904998.unknown _1338825877.unknown _1338825878.unknown _1338825871.unknown _1338825874.unknown _1338825875.unknown _1338825872.unknown _1338825870.unknown _1338825869.unknown _1338822972.unknown _1338823185.unknown _1338823208.unknown _1338823040.unknown _1338821569.unknown _1338822048.unknown _1338822066.unknown _1338822041.unknown _1338821778.unknown _1338740682.unknown _1338740557.unknown _1338740579.unknown _1338740457.unknown Examen+Pauta-2009-Problemas-1y2.doc Examen Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesor: Carlos Obreque N. Fecha: martes 26 de mayo de 2009 Problema 1. (25 puntos) Cuatro automóviles llegaron al taller de reparación de don Lalo para varios tipos de trabajos, que van desde una reparación general de la transmisión hasta un recambio de frenos. El nivel de experiencia de los mecánicos es muy variado y don Lalo desea minimizar el tiempo requerido para completar todos los trabajos. Estimó un tiempo en minutos para que cada mecánico complete cada trabajo. Willy puede hacer el trabajo 1 en 400 minutos, el 2 en 90 minutos, el 3 en 60 minutos y el 4 en 120 minutos. Taylor puede terminar el trabajo 1 en 650 minutos, el 2 en 120 minutos, el 3 en 90 minutos y el 4 en 180 minutos. Mark realizará el trabajo 1 en 480 minutos, el 2 en 120 minutos, el 3 en 80 minutos y el 4 en 180 minutos. John puede completar el trabajo 1 en 500 minutos, el 2 en 110 minutos, el 3 en 90 minutos y el 4 en 150 minutos. a) Si a cada mecánico se le tiene que asignar sólo uno de estos trabajos, ¿cuál es el tiempo total mínimo requerido para terminar los cuatro trabajos. ¿quién deberá ser asignado a cada trabajo?. (15 puntos) b) Si cualquier mecánico puede realizar hasta dos trabajos, es posible encontrar una mejor solución que la dada en la parte (a). Construya la tabla de asignación que sirva para resolver esta pregunta. (10 puntos) Problema 2. (25 puntos) Una industria que posee tres fábricas de discos situadas en París, Roma y Zurich, tiene que suministrarlos a tres puntos de venta-distribución situados en Madrid, Barcelona y Sevilla. Las cantidades y costos unitarios de producción para las tres fábricas son: París Roma Zurich Oferta (en miles) 40 40 30 Costo ( $/Unidad) 10 12 15 Los costos de transporte ($/Unidad), las demandas y los precios de ventas en los tres centros de venta vienen dados en la siguiente tabla: Madrid Barcelona Sevilla París 10 7 15 Roma 14 6 5 Zurich 12 8 16 Demanda (en miles) 40 40 20 Precio de Venta ($/Unidad) 80 70 75 a) Construya la tabla de transporte y determine la solución óptima. (15 puntos) b) Suponga que se admite la posibilidad que haya transbordo. En tal caso, es posible enviar unidades desde París hacia Zurich y desde Madrid hacia Sevilla con costos unitarios de 5 y 4 pesos, respectivamente. Construya la tabla de transporte apropiada que permita resolver este problema. (10 puntos) Problema 1 a) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Willy 400 90 60 120 (60) Taylor 650 120 90 180 (90) Mark 480 120 80 180 (80) John 500 110 90 150 (90) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Willy 340 30 0 60 Taylor 560 30 0 90 Mark 400 40 0 100 John 410 20 0 60 (340) (20) (0) (60) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Willy 0 10 0 0 Taylor 220 10 0 30 Mark 60 20 0 40 John 70 0 0 0 Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Willy 0 10 10 0 Taylor 210 0 0 20 Mark 50 10 0 30 John 70 0 10 0 Willy ( Trabajo 1 = 400 Taylor ( Trabajo 2 = 120 Mark ( Trabajo 3 = 80 John ( Trabajo 4 = 150 Total = 750 b) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Ficticio 1 Ficticio 2 Ficticio 3 Ficticio 4 Willy-1 400 90 60 120 0 0 0 0 Willy-2 400 90 60 120 0 0 0 0 Taylor-1 650 120 90 180 0 0 0 0 Taylor-2 650 120 90 180 0 0 0 0 Mark-1 480 120 80 180 0 0 0 0 Mark-2 480 120 80 180 0 0 0 0 John-1 500 110 90 150 0 0 0 0 John-2 500 110 90 150 0 0 0 0 Problema 2 a) Utilidad (i,j) = Precio de venta en j – Costo de producción en i – Costo de transporte Cij Madrid Barcelona Sevilla Ficticio Oferta París 60 53 50 0 40 Roma 54 52 58 0 40 Zurich 53 47 44 0 30 Demanda 40 40 20 10 Madrid Barcelona Sevilla Ficticio Oferta Ui París 60 53 50 0 40 7 40 -1 -10 -7 Roma 54 52 58 0 40 5 -4 20 20 -5 Zurich 53 47 44 0 30 0 0 20 -9 10 Demanda 40 40 20 10 Vj 53 47 53 0 Z = 60*40 + 52*20 + 58*20 + 53*0 + 47*20 + 0*10 = 5540 b) Es necesario construir nodos ficticios para distinguir las unidades que se producen en Zurich de las unidades que provienen y se producen en París y de las unidades que se venden en Madrid de las que van a Sevilla y pasan por Madrid. Zurich-2 Madrid-2 Madrid Barcelona Sevilla Ficticio Oferta Zurich-2 0 -12 68 62 59 -M 110 Madrid-2 -M 0 -M -M 71 -M 110 París -15 -20 60 53 50 0 40 Roma -M -26 54 52 58 0 40 Zurich -M -27 53 47 44 0 30 Demanda 110 110 40 40 20 10 50 53 60 10 20 40 40 30 40 40 Ficticio Sevilla Barcelona Madrid Zurich Roma París 70-15-8 75-12-5 70-12-6 75-15-16 80-15-12 80-12-14 0 0 0 75-10-15 70-10-7 80-10-10 10 20 40 40 30 40 40 Ficticio Sevilla Barcelona Madrid Zurich Roma París 0 0 0 54 53 44 52 58 47 Zurich-2 -10-5 80-12 70-8 75-16 Madrid-2 -12 -10-10 -12-14 -15-12 75-4 Examen+Pauta-2010.doc24 7 2 2 1 £ + x x Examen Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesor: Carlos Obreque Níñez Fecha: martes 15 de junio de 2010 Profesor Ayudante: Gonzalo Baeza Villa Problema 1. (30 puntos) Una determinada compañía produce dos productos. La empresa puede adquirir hasta 90 Kg. de materia prima a un costo de 10 $/Kg. Necesita utilizar 1 kg de materia prima y 10 horas de mano de obra para producir un kilo de producto tipo A, mientras que con ese kilo de materia prima y 7 horas de mano de obra permiten producir 0.5 kg de producto B. Sabiendo que la empresa dispone de 70 horas de mano de obra a la semana, que el precio de venta del producto A es de 14 $/kg y el del B de 33 $/kg, y que la producción máxima del producto B es de 30 kg a la semana: a) Defina las variables de decisión y formule un modelo de programación lineal. b) Utilice el método Simplex para encontrar la solución óptima. c) Determine solución óptima si se agrega la siguiente restricción: Problema 2. (30 puntos) Una compañía posee secciones de control de calidad en cuatro ciudades. Para la puesta en marcha de un nuevo proyecto es necesario distribuir a los técnicos entre ellas. El número de técnicos necesarios y disponibles, así como los costos de desplazamiento se dan en la siguiente tabla. Técnicos Disponibles Técnicos Requeridos Costos C1 C2 C3 C4 C1 13 2 0 80 100 210 C2 4 4 145 0 111 110 C3 5 1 105 115 0 113 C4 1 14 210 117 - 0 a) Construya la tabla de transporte que permita resolver el problema del desplazamiento admitiendo que se puede utilizar como punto intermedio del viaje cualquier ciudad. b) El sindicato de técnicos alega que durante los viajes se deteriora la calidad de vida de los empleados, admitiendo únicamente que 3 de los técnicos tengan que transbordar en cada ciudad. Indique los cambios que habría que hacer en la tabla construida en la parte (a) para resolver este nuevo problema. Problema 3. (40 puntos) Conocida la gran catástrofe del 27 de febrero en nuestro país, la séptima y octava región fueron las más devastadas por el terremoto y posterior tsunami. Dos de las ciudades más damnificadas, fueron Constitución y Talcahuano, por lo que se hizo extremadamente necesario enviar víveres a dichas ciudades durante los primeros días. Por otra parte, las ciudades de Chillán, Temuco y Longaví no fueron tan afectadas por esta catástrofe y se encontraban en condiciones de brindar apoyo a sus compatriotas que habían caído en desgracia. En estas tres ciudades se organizaron campañas solidarias llegándose a recolectar las siguientes cantidades de víveres: Víveres (toneladas) Ciudad Perecibles No Perecibles Chillán 40 10 Temuco --- 80 Longaví --- 50 Los víveres perecibles debían ser despachados obligatoriamente, ya que las autoridades querían evitar que estos alimentos se descompusieran en sus bodegas. En cambio, los víveres no perecibles no necesariamente debían ser despachados, ya que éstos podían quedar guardados en las bodegas por un largo periodo de tiempo y redistribuidos ante la eventualidad de que se registrara otra emergencia. En Talcahuano se había manifestado que se necesitaba urgentemente de 60 toneladas de víveres y en la ciudad de Constitución se solicitaban 90 toneladas. A los damnificados de estas ciudades les era indiferente si los víveres enviados eran perecibles o no. Las distancias que existen entre las ciudades se muestran en la tabla siguiente: Distancias entre ciudades (kilómetros) Origen / Destino Talcahuano Constitución Chillán 100 200 Temuco 300 480 Longaví 190 120 Una empresa de transportes se ofreció para realizar el traslado de los víveres al menor costo, puesto que posee camiones de gran capacidad. La empresa estableció una tarifa de 1500 pesos por tonelada y por kilómetro recorrido. Usted, como estudiante de ingeniería civil industrial, ¿qué alternativa de transporte habría propuesto? y, ¿cuál hubiese sido su costo? . Determine la solución óptima. ¿Existen más soluciones óptimas? En caso de que su respuesta sea afirmativa encuentre una solución óptima alternativa. Tiempo: 90 minutos Problema 1 Producto A Producto B Disponibilidad Costo Materia Prima 1 [kg A / kg MP] 0.5 [kg B / kg MP] 90 [kg MP] 10 [$/kg MP] Tiempo 10 [hr/ kg A] 7 [hr/ 0.5kg B] 70 [hr] Precio de venta 14 [$/kg A] 33 [$/kg B] Producción máxima 30 [kg B] ( ) 0 , 30 70 14 10 90 2 / 2 10 33 14 . . 2 1 2 2 1 2 1 2 1 2 1 2 1 ³ £ £ + £ + + - + = = = x x x x x x x a s x x x x Z Max producir a B producto del kilógramos x producir a A producto del kilógramos x decisión de Variables b).- La tabla inicial será: x1 x2 h1 h2 h3 b Z -4 -13 0 0 0 0 h1 1 2 1 0 0 90 h2 10 14 0 1 0 70 h3 0 1 0 0 1 30 Iterando se obtiene la solución óptima: x1 x2 h1 h2 h3 b Z 37/7 0 0 1/1 0 65 h1 - 3/7 0 1 - 1/7 0 80 x2 5/7 1 0 0 0 5 h3 - 5/7 0 0 -0 1 25 c).- La nueva restricción no se satisface con los valores del óptimo, luego, para poder resolver, ingresamos la nueva restricción a la tabla óptima con su respectiva variable de holgura, canonizamos y aplicamos simples-dual x1 x2 h1 h2 h3 h4 b Z 102/7 0 0 13/7 0 0 65 h1 - 13/7 0 1 - 2/7 0 0 80 x2 10/7 1 0 1/7 0 0 5 h3 - 10/7 0 0 - 1/7 1 0 25 h4 2 7 0 0 0 1 24 Canonizando x2 se tiene: x1 x2 h1 h2 h3 h4 b Z 102/7 0 0 13/7 0 0 130 h1 - 13/7 0 1 - 2/7 0 0 70 x2 10/7 1 0 1/7 0 0 5 h3 - 10/7 0 0 - 1/7 1 0 20 h4 -8 0 0 -1 0 1 -11 x1 x2 h1 h2 h3 h4 b Z -0 0 0 0 0 1 5/6 110 h1 0 0 1 -0 0 - 1/4 653/9 x2 0 1 0 -0 0 1/6 3 h3 0 0 0 0 1 - 1/6 22 x1 1 0 0 1/8 0 - 1/8 11/8 Problema 2 Técnicos Disponibles Técnicos Requeridos Oferta Demanda C1 13 2 11 0 C2 4 4 0 0 C3 5 1 4 0 C4 1 14 0 13 a) C1 C2 C3 C4 Ficticio Oferta C1 0 80 100 210 0 11+15 C2 145 0 111 110 0 0+15 C3 105 115 0 113 0 4+15 C4 210 117 M 0 0 0+15 Demanda 0+15 0+15 0+15 13+15 2 b) C1 C2 C3 C4 Ficticio Oferta C1 0 80 100 210 0 11+3 C2 145 0 111 110 0 0+3 C3 105 115 0 113 0 4+3 C4 210 117 M 0 0 0+3 Demanda 0+3 0+3 0+3 13+3 2 Problema 3 Encontramos una solución inicial mediante el método de aproximación de Vogel, como todos los valores de las variables no básicas son mayores o iguales a cero, estamos en la solución óptima y no es necesario más iteraciones. Talcahuano Constitución Ficticio Oferta Ui Longaví 285 180 0 50 180 255 50 420 Chillán No perecibles 150 300 0 10 300 0 10 300 Chillán perecibles 150 300 M 40 300 10 30 M-300 Temuco 450 720 0 80 600 50 420 30 Demanda 60 90 30 Vj -150 0 -600 Origen Destino Toneladas de Víveres Longaví Constitución 50 Chillán (Víveres no perecibles) Constitución 10 Chillán (Víveres perecibles) Talcahuano 10 Chillán (Víveres perecibles) Constitución 30 Temuco Talcahuano 50 Temuco En Bodega 30 Costo Total [$] 45.000.000 b.- Si existen soluciones óptimas alternativas por que uno de los valores de las variables no básicas es igual a cero, luego este entra a la base. Talcahuano Constitución Ficticio Oferta Longaví 285 180 0 50 255 50 420 Chillán (víveres no perecible) 150 300 0 10 0 + 10 - 300 Chillán (víveres perecible) 150 300 M 40 10 - 30 + M-300 Temuco 450 720 0 80 50 420 30 Demanda 60 90 30 180 Iterando resulta: Talcahuano Constitución Ficticio Oferta ui Longaví 285 180 0 50 180 255 50 420 Chillán (víveres no perecible) 150 300 0 10 300 10 0 300 Chillán (víveres perecible) 150 300 M 40 300 0 40 M-300 Temuco 450 720 0 80 600 50 120 30 Demanda 60 90 30 180 vj -150 0 -600 Plan óptimo alternativo: Origen Destino Toneladas de Víveres Longaví Constitución 50 Chillán (Víveres no perecibles) Talcahuano 10 Chillán (Víveres no perecibles) Constitución 0 Chillán (Víveres perecibles) Constitución 40 Temuco Talcahuano 50 Temuco En Bodega 30 Costo Total [$] 45.000.000 M 450 300 720 300 0 0 150 180 285 0 10 puntos 90 60 Constitución Talcahuano 180 30 40 10 80 50 Ficticio Temuco Chillán (Víveres Perecibles) Chillán (Víveres No Perecibles) Longaví 180 10 puntos 5 puntos 5 puntos 150 10 puntos 10 puntos 10 puntos 10 puntos 10 puntos 5 puntos 10 puntos 5 puntos PAGE 2 _1338121673.unknown _1338312890.unknown Examen+Repeticion-2009+pauta-3.doc Examen de Repetición Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesor: Carlos Obreque N. Fecha: martes 9 de junio de 2009 Iván Santelices M. Problema 1. (25 puntos) Una compañía abastece a 3 clientes cuyas demandas son de 30 unidades cada una. Existen dos depósitos con 40 y 30 unidades disponibles, respectivamente. El costo unitario de envío aparece en la tabla que sigue. Por cada unidad no enviada a un cliente, existe un costo de “no cumplimiento”. Cliente 1 Cliente 2 Cliente 3 Depósito 1 15 35 25 Depósito 2 10 50 40 Costo de no cumplimiento 50 80 90 a) Formular un modelo de transporte para minimizar costos. Encuentre la solución óptima. (15 puntos) b) Suponga que se admite la posibilidad que haya transbordo. En tal caso, se pueden enviar unidades desde el cliente 1 hacia el cliente 2, con un costo unitario de envío de 10. Construya la tabla de transporte que permita encontrar la solución óptima. (10 puntos) Problema 2. (25 puntos) En una institución educacional, tres profesores deben ser asignados a 6 asignaturas. Cada profesor entregó un puntaje de cada asignatura que indica su preferencia para dictarla. La ponderación se presenta en la tabla que sigue. A1 A2 A3 A4 A5 A6 Profesor 1 3 5 6 2 8 9 Profesor 2 2 7 3 9 6 6 Profesor 3 1 4 4 3 8 8 Determinar qué profesor debe dictar cada asignatura tratando de maximizar la “satisfacción global” si: a) Cada profesor debe dictar dos asignaturas. (15 puntos) b) Un profesor puede dictar hasta tres asignaturas. (10 puntos) Problema 3. (50 puntos) Una cierta fábrica elabora dos tipos de telas usando lana de tres colores distintos. Se necesita la siguiente materia prima: Para fabricar 1 metro de tela del tipo Lana disponible para la fabricación/semana A B 180 g. de lana amarilla 480 g. de lana amarilla 72.000 gramos 240 g. de lana roja 300 g. de lana roja 60.000 gramos 300 g. de lana verde 120 g. de lana verde 60.000 gramos El cuadro indica también cuánta lana de cada color hay disponible. El fabricante quiere saber de qué manera usar este material, bajo el supuesto de que puede obtener un beneficio de $ 300 por un metro del tipo A, y de $ 180 por un metro del tipo B. Desea, naturalmente, maximizar su beneficio total. Se definió que el Modelo de Programación Lineal asociado es: Optimizar Z = 300 X1 + 180 X2 sujeto a 180 X1 + 480 X2 <= 72.000 240 X1 + 300 X2 <= 60.000 300 X1 + 120 X2 <= 60.000 1 X1 + 0 X2 >= 0 0 X1 + 1 X2 >= 0 a) Explique claramente la definición de las variables de decisión, función objetivo y restricciones utilizadas en el modelo matemático de dicha fábrica. (5 puntos) b) Explique detalladamente como saber en una iteración cualquiera del Simplex, en su forma tabular, que el problema es: (1) no acotado y (2) infactible. (5 puntos) c) Determine el tableau óptimo asociado, y explicite la solución asociada. (5 puntos) Para las siguientes preguntas usar alguno de los métodos optimizantes o de sensibilidad en PPL, en su forma tabular (tableau) no se evaluará otro. Las preguntas son independientes entre si: d) Explique claramente como determinar una Solución Factible Sub-optima, distinta de la solución óptima encontrada en (c). (5 puntos) e) Tomar el mismo problema anterior, pero supongamos ahora que el beneficio que se obtiene de un metro de tela del tipo B es $ 120 (en lugar de $ 180, como antes). Resolver y explicar detalladamente la nueva solución óptima. (5 puntos) f) Tomemos el problema original, con la diferencia de que se invierte el signo de la desigualdad de la restricción asociada a la lana roja. (5 puntos) g) Considerando el problema original, con la diferencia de que se invierte el signo de la desigualdad de la restricción asociada a la lana verde y amarilla. (5 puntos) h) Ahora resolver invirtiendo el signo de las tres restricciones asociadas a las lanas. Realice solo una iteración y explique. (5 puntos) i) A partir de la respuesta de (c) encuentre el nuevo óptimo si se adiciona la restricción de que el total de metros de tela a fabricar no puede superar los 3000/17 metros por semana. (5 puntos) j) La fábrica estaría evaluando el comprar a terceros más lana, cuál y a qué costo usted recomendaría adquirirla. Justifique. (5 puntos) Tiempo: 90 minutos Problema 1 a) Cliente 1 Cliente 2 Cliente 3 Oferta Ui Depósito 1 15 35 25 40 0 10 10 30 Depósito 2 10 50 40 30 5 30 10 10 Ficticio 50 80 90 20 45 0 20 20 Demanda 30 30 30 Vj 5 35 25 b) Cliente 1 Cliente 2 Cliente 3 Cliente 1´ Oferta Depósito 1 15 35 25 15 40 Depósito 2 10 50 40 10 30 Ficticio 50 80 90 M 20 Cliente 1´ M 10 M 0 90 Demanda 30 30 30 90 Problema 2 a) A1 A2 A3 A4 A5 A6 P1 3 5 6 2 8 9 (9) P1´ 3 5 6 2 8 9 (9) P2 2 7 3 9 6 6 (9) P2´ 2 7 3 9 6 6 (9) P3 1 4 4 3 8 8 (8) P3´ 1 4 4 3 8 8 (8) A1 A2 A3 A4 A5 A6 P1 -6 -4 -3 -7 -1 0 P1´ -6 -4 -3 -7 -1 0 P2 -7 -2 -6 0 -3 -3 P2´ -7 -2 -6 0 -3 -3 P3 -7 -4 -4 -5 0 0 P3´ -7 -4 -4 -5 0 0 (-6) (-2) (-3) (0) (0) (0) A1 A2 A3 A4 A5 A6 P1 0 -2 0 -7 -1 0 P1´ 0 -2 0 -7 -1 0 P2 -1 0 -3 0 -3 -3 P2´ -1 0 -3 0 -3 -3 P3 -1 -2 -1 -5 0 0 P3´ -1 -2 -1 -5 0 0 b) A1 A2 A3 A4 A5 A6 F1 F2 F3 P1 3 5 6 2 8 9 -M -M -M P1´ 3 5 6 2 8 9 0 0 0 P1” 3 5 6 2 8 9 0 0 0 P2 2 7 3 9 6 6 -M -M -M P2´ 2 7 3 9 6 6 0 0 0 P2” 2 7 3 9 6 6 0 0 0 P3 1 4 4 3 8 8 -M -M -M P3´ 1 4 4 3 8 8 0 0 0 P3” 1 4 4 3 8 8 0 0 0 D1 10 10 15 C1´ 90 D2 90 80 50 40 50 10 25 35 15 30 30 30 20 30 40 C3 C2 F C1 D2 D1 80 50 40 50 10 25 35 15 30 30 30 20 30 40 C3 C2 C1 F Examen-Parte-2+Pauta.doc Examen Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesores: Carlos Obreque N. Fecha: Lunes 26 de mayo de 2008 Iván Santelices M. Pregunta 1. (15 puntos) Incredible Indelible Ink Company mezcla tres aditivos, A1, A2 y A3 a una base en diferentes proporciones para obtener distintos colores de tinta. La tinta roja se obtiene mezclando A1, A2 y A3 en la proporción 3:1:2, la tinta azul en la proporción 2:3:4 y la tinta verde en la proporción 1:2:3. Después de mezclar estos aditivos, se añade una cantidad igual de base para cada color. La compañía actualmente tiene 1000 galones de A1, 1500 de A2, 2000 de A3 y 4000 de base. Dado que el precio de venta por galón de cada tipo de tinta es el mismo, desarrolle un modelo para determinar cómo deberían usarse estos recursos para obtener los máximos ingresos. Pregunta 2. (15 puntos) Suponga que el gobierno pretende hacer inversiones cuantiosas, en una cierta región, en el cultivo de las frutas A, B, C, y D. Se persiguen dos objetivos, uno el de reducir el desempleo rural y otro el de aumentar las exportaciones que vendrán a equilibrar la balanza de pagos de la nación. Se sabe que la producción promedio de cada árbol está dada por la tabla que sigue. El precio promedio en el Mercado mundial fue de 10,00 u.m. para el kg de la fruta A, 4,00 u.m. para la B, 15,00 u.m. para la C y 7,00 u.m. para la D. Existe una extensión de 250.000 m2 de tierra fiscal propicia para el cultivo de dichos productos. Supóngase que los técnicos del área correspondiente del gobierno han determinado que las extensiones mínimas necesarias para el cultivo de esos productos, son las que se indican en la tabla siguiente: Tipo de árbol Producción promedio anual (una vez por año) Extensión mínima de cultivo por árbol A 350 u./a 150 kg / árbol 4 m2 B 230 u./a 200 kg / árbol 5 m2 C 150 u./a 50 kg / árbol 3 m2 D 400 u./a 150 kg / árbol 6 m2 Afortunadamente no existe problema de agua, pues hay varios manantiales dentro de la propiedad, que aseguran la existencia de ese preciado líquido por los próximos 20 años. El costo por sembrar un árbol de fruta A es de 2,00 u.m., 0,50 u.m. para el tipo B, 1,00 u.m. para el C y 1,5 u.m. para el D. Estos costos ya incluyen la compra del árbol más su cuidado y mantenimiento. Cada árbol empieza a ser productivo, aproximadamente a los 3 años de ser plantado. Cada árbol de fruta A requiere de cuidados equivalentes a 36 horas-hombre/año, 72 horas-hombre/año en el caso del árbol de la fruta B, 52 horas-hombre/año en el caso de la fruta C y 10 horas-hombre/año en el caso de la D. El estado pretende hacer una inversión de 20 millones de u.m., pensando exportar toda su producción a partir del tercer año. El desempleo en la región en estudio se ha calculado en 500 personas, y el gobierno ha delineado que este proyecto emplee al menos 200 personas en forma continua. Bajo estas circunstancias, formule un modelo para resolver el problema. Pregunta 3. (20 puntos) Cada semana, Florida Citrus, Inc., usa una sola máquina durante 150 horas para destilar jugo de naranja y de pomelo en concentrados almacenados en dos tanques separados de 1000 galones antes de congelarlos. La máquina puede procesar 25 galones de jugo de naranja por hora, pero sólo 20 galones de jugo de pomelo. Cada galón de jugo de naranja cuesta $1,50 y pierde 30% de contenido de agua al destilarse en concentrado. El concentrado de jugo de naranja se vende después en $6,00 por galón. Cada galón de jugo de pomelo cuesta $2,00 y pierde 25% de contenido de agua al destilarse en concentrado. El concentrado de jugo de pomelo se vende después en $8,00 por galón. a) Formular un modelo de PL para determinar el plan de producción que maximice la ganancia para la siguiente semana, usando como variables el número de galones de naranja y pomelo por utilizar en dicha semana. b) Obtener la solución mediante el Método Símplex. c) Obtener la solución mediante el Método Gráfico. e) Si se pudiera cambiar la capacidad del tanque de almacenamiento de pomelo desde 1000 hasta 1500 galones, cómo se afecta el plan de producción? Justifique la respuesta. Problema 4. (25 puntos) Una empresa que dispone de dos plantas de fabricación diferentes sirve un determinado producto a dos clientes. Las necesidades de ambos clientes en los dos próximos meses, supóngase agosto y septiembre, vienen dadas en la tabla 1: Agosto Septiembre Cliente I Cliente II Cliente I 420 550 Planta I 10 13 Cliente II 350 480 Planta II 12 6 Tabla 1 Tabla 2 El costo de enviar una unidad de cada una de las plantas a cada uno de los consumidores es dado en la Tabla 2. Los costos de producción de cada unidad, así como la capacidad de producción de cada una de las plantas para los dos meses considerados, son: Costos de producción Capacidad Agosto Septiembre Agosto Septiembre Planta I 3 3.6 500 600 Planta II 3.2 2.9 300 500 Es posible fabricar unidades durante un mes, almacenarlas y enviarlas al mes siguiente. Los costos unitarios de almacenamiento mensuales son de 0.5 en la planta I y 0.6 en la planta II. Encontrar la producción y distribución óptima de cada planta formulando el problema como un modelo de transporte. Construya la tabla de transporte y obtenga la solución óptima utilizando el método de Vogel para encontrar la solución básica factible inicial. Problema 5 (25 puntos) Un sistema de procesamiento compartido tiene seis procesadores diferentes Pi, i=1;…;6 y debe procesar seis tareas Tj ; j =1;…;6 que pueden realizarse en cualquiera de estos seis procesadores, pero con la condición de que tendrían que completarse en el procesador en el que se iniciaron. Los costos de procesamiento cij de las tareas variarían según el procesador, tal como se muestra en la siguiente tabla. Tareas Procesador T1 T2 T3 T4 T5 T6 P1 8 4 10 2 1 6 P2 6 6 12 4 3 5 P3 2 4 8 1 1 6 P4 10 8 15 6 2 3 P5 5 7 20 4 4 1 P6 8 2 10 4 2 4 a) Determinar qué procesador se asignará a cada trabajo de modo que el costo total sea mínimo. b) Suponga que el procesador 4 puede realizar dos tareas en forma simultánea. Explique de que manera se puede formular este problema como un modelo de asignación y usar el método Húngaro para resolverlo. Tiempo: 2 horas Problema 4 Requerimientos Producción Cliente I Agosto Cliente I Septiembre Cliente II Agosto Cliente II Septiembre Ficticio Oferta Planta I Agosto 13 13.5 16 16.5 0 500 Planta I Septiembre M 13.6 M 16.6 0 600 Planta II Agosto 15.2 15.8 9.2 9.8 0 300 Planta II Septiembre M 14.9 M 8.9 0 500 Demanda 420 550 350 480 100 Requerimientos Ui Producción Cliente I Agosto Cliente I Septiembre Cliente II Agosto Cliente II Septiembre Ficticio Oferta Planta I Agosto 13 13.5 16 16.5 0 500 13.5 420 30 50 9.0 0.1 Planta I Septiembre M 13.6 M 16.6 0 600 13.6 M 500 + M 9.0 100 – Planta II Agosto 15.2 15.8 9.2 9.8 0 300 6.7 9.0 9.1 300 9.1 6.9 Planta II Septiembre M 14.9 M 8.9 0 500 14.9 M 20 – M 480 -1.3 + Demanda 420 550 350 480 100 Vj -0.5 0 2.5 -6.0 -13.6 Requerimientos Producción Cliente I Agosto Cliente I Septiembre Cliente II Agosto Cliente II Septiembre Ficticio Oferta Planta I Agosto 13 13.5 16 16.5 0 500 0 420 30 50 7.7 0.1 Planta I Septiembre M 13.6 M 16.6 0 600 0.1 M 520 M 7.7 80 Planta II Agosto 15.2 15.8 9.2 9.8 0 300 -6.8 9.0 9.1 300 7.8 6.9 Planta II Septiembre M 14.9 M 8.9 0 500 0.1 M 1.3 M 480 20 Demanda 420 550 350 480 100 13 13.5 16 8.8 -0.1 Problema 5 a) Tareas Procesador T1 T2 T3 T4 T5 T6 P1 8 4 10 2 1 6 P2 6 6 12 4 3 5 P3 2 4 8 1 1 6 P4 10 8 15 6 2 3 P5 5 7 20 4 4 1 P6 8 2 10 4 2 4 Tareas Procesador T1 T2 T3 T4 T5 T6 P1 7 3 9 1 0 5 P2 3 3 9 1 0 2 P3 1 3 7 0 0 5 P4 8 6 13 4 0 1 P5 4 6 19 3 3 0 P6 6 0 8 2 0 2 Tareas Procesador T1 T2 T3 T4 T5 T6 P1 6 3 2 1 0 5 P2 2 3 2 1 0 2 P3 0 3 0 0 0 5 P4 7 6 6 4 0 1 P5 3 6 12 3 3 0 P6 5 0 1 2 0 2 Tareas Procesador T1 T2 T3 T4 T5 T6 P1 5 3 1 0 0 5 P2 1 3 1 0 0 2 P3 0 4 0 0 1 6 P4 6 6 5 3 0 1 P5 2 6 11 2 3 0 P6 4 0 0 1 0 2 Tareas Procesador T1 T2 T3 T4 T5 T6 P1 4 2 0 0 0 5 P2 0 2 0 0 0 2 P3 0 4 0 1 2 7 P4 5 5 4 3 0 1 P5 1 5 10 2 3 0 P6 4 0 0 2 1 3 P1 ( T3 P2 ( T4 P3 ( T1 P4 ( T5 P5 ( T6 P6 ( T2 Costo = 10 + 4 + 2 + 2 + 1 + 2 = 21 b) Duplicar el procesador 4 y balancear la tabla Tareas Procesador T1 T2 T3 T4 T5 T6 F P1 8 4 10 2 1 6 0 P2 6 6 12 4 3 5 0 P3 2 4 8 1 1 6 0 P4 10 8 15 6 2 3 0 P5 5 7 20 4 4 1 0 P6 8 2 10 4 2 4 0 P44 10 8 15 6 2 3 0 Tareas Procesador T1 T2 T3 T4 T5 T6 F P1 6 2 2 1 0 5 0 P2 4 4 4 3 2 4 0 P3 0 2 0 0 0 5 0 P4 8 6 7 5 1 2 0 P5 3 5 12 3 3 0 0 P6 6 0 2 3 1 3 0 P44 8 6 7 5 1 2 0 Tareas Procesador T1 T2 T3 T4 T5 T6 F P1 5 2 1 0 0 5 0 P2 3 4 3 2 2 4 0 P3 0 3 0 0 1 6 1 P4 7 6 6 4 1 2 0 P5 2 5 11 2 3 0 0 P6 5 0 1 2 1 3 0 P44 7 6 6 4 1 2 0 Tareas Procesador T1 T2 T3 T4 T5 T6 F P1 5 3 1 0 0 6 1 P2 2 4 2 1 1 4 0 P3 0 4 0 0 1 7 2 P4 6 6 5 3 0 2 0 P5 1 5 10 1 2 0 0 P6 4 0 0 1 0 3 0 P44 6 6 5 3 0 2 0 Tareas Procesador T1 T2 T3 T4 T5 T6 F P1 5 3 1 0 1 7 2 P2 1 3 1 0 1 4 0 P3 0 4 0 0 2 8 3 P4 5 5 4 2 0 2 0 P5 0 4 9 0 2 0 0 P6 4 0 0 1 1 4 1 P44 5 5 4 2 0 2 0 Tareas Procesador T1 T2 T3 T4 T5 T6 F P1 4 2 0 0 1 6 2 P2 0 2 0 0 1 3 0 P3 0 4 0 1 3 8 4 P4 4 4 3 2 0 1 0 P5 0 4 9 1 3 0 1 P6 4 0 0 2 2 4 2 P44 4 4 3 2 0 1 0 Examen-Repeticion-2008+Pauta.doc Examen de Repetición Investigación de Operaciones I Ingeniería Civil Industrial mención Gestión de Operaciones (ICIV) Profesores: Iván Santelices M. Fecha: Lunes 09 de junio de 2008 Carlos Obreque N. Pregunta 1. (15 puntos) Un fabricante de whisky importa tres tipos de licores A, B y C. Los mezcla de acuerdo con especificaciones que limitan el máximo y el mínimo de A y C en cada mezcla: Mezcla Especificaciones Precio Unitario Blue Dot No más de 60% de A No menos de 20% de C $6.80 Highland Fling No más de 60% de C No menos de 15% de A $5.70 Old Freny No más de 50% de C $4.50 Las cantidades disponibles de cada uno y sus precios son: Clase Cantidad máxima en unidades/día Costo unitario A 2000 $7.00 B 2500 $5.00 C 1200 $4.00 Establezca claramente un modelo matemático que permita determinar el programa de producción que maximiza las utilidades. Pregunta 2 (15 puntos). La Constructora Casas Ltda., se ha adjudicado la construcción de 100 casas. El contrato la obliga a construir dos tipos de casas. Para los beneficiarios las casas tienen el mismo costo, pero para Constructora Casas, éstas tienen un margen de utilidad diferente, así las casas tipo campo arrojan 5.100 K$ y las de tipo rancho 5.000 K$. El contrato obliga a entregar las casas dentro de los nueve meses de firmado el contrato. Otra información relevante se resume en la siguiente tabla: Recurso por tipo de casa Disponibilidad Campo Rancho de horas 200 100 12000 Carpintero 50 120 13000 Albañil a) Formule el problema de programación lineal. b) Encuentre la solución óptima gráficamente. c) Suponga que se desea agregar un nuevo tipo de casa denominada “Española” que da un margen de utilidad de 4900 K$/casa y que requiere de 150 hr-carpintero/casa y 80 hr-albañil/casa. Explique si conviene o no fabricar las casas. Pregunta 3 (20 puntos). Una empresa se dedica al montaje de motocicletas de 50, 125 y 250 cc. Posee para ello una planta que esta estructurada en 3 departamentos: fabricación de los chasis, pintura y montaje. El departamento de fabricación de chasis dispone de 50 trabajadores, el de pintura de 30 trabajadores, y el de montaje de 60. Todos los trabajadores realizan una jornada laboral de 8 horas. Para fabricar una motocicleta del modelo de 50 cc, es necesaria la utilización de 2 horas del primer departamento, 1 hora del segundo y 2 horas del tercero. El beneficio obtenido con la venta de una unidad de este modelo asciende a $ 60.000. En la fabricación del modelo de 125 cc, se emplean 4, 2 y 3 horas de cada uno de los departamentos respectivamente. El beneficio unitario asciende, para este caso a $ 120.000. Para fabricar una unidad del modelo más grande (250 cc) se precisan 6 horas del departamento de chasis, 3 horas en el de pintura y 8 horas en el de montaje. El beneficio obtenido con la venta de una unidad de este modelo se eleva a $ 210.000. Suponiendo que la empresa vende toda su producción (se admite la posibilidad de fabricar motocicletas no completas) se desea conocer: a) Entre que limites puede variar el beneficio unitario del modelo de 50 cc para que la base de la solución óptima continúe siendo óptima. b) Entre que limites puede variar el beneficio unitario del modelo de 125 cc para que la base de la solución óptima continúe siendo óptima. c) Entre que limites puede variar el tiempo disponible en el departamento de pintura para que la solución óptima continúe siendo la misma. d) Determine la nueva solución óptima si el número de trabajadores disponible en el departamento de chasis baja a 25. Designando por Xi el número de elementos a fabricar de cada modelo tenemos que: 2 x1 + 4 x2 + 6 x3 ( 400 (400 = 50 trabajadores * 8 horas) x1 + 2 x2 + 3 x3 ( 240 (240 = 30 trabajadores * 8 horas) 2 x1 + 3 x2 + 8 x3 ( 480 (480 = 60 trabajadores * 8 horas) xi ( 0 Max Z = 60.000 x1 + 120.000 x2 + 210.000 x3 Añadiendo las variables de holgura y resolviendo por el algoritmo de simplex se tiene: X1 X2 X3 X4 X5 X6 Zj- Cj -60 -120 -210 0 0 0 0 X4 2 4 6 1 0 0 400 X5 1 2 3 0 1 0 240 X6 2 3 8 0 0 1 480 X1 X2 X3 X4 X5 X6 Zj- Cj - 15/2 - 165/4 0 0 0 105/4 12.600 X4 1/2 7/4 0 1 0 3/4 40 X5 1/4 7/8 0 0 1 - 3/8 60 X3 1/4 3/8 1 0 0 1/8 60 X1 X2 X3 X4 X5 X6 Zj- Cj 30/7 0 0 165/7 0 60/7 94800/7 X2 2/7 1 0 4/7 0 - 3/7 160/7 X5 0 0 0 - 1/2 1 0 40 X3 1/7 0 1 - 3/14 0 2/7 360/7 Pregunta 4 (25 puntos) La siguiente tabla muestra el grado de interés de cada uno de los seis alumnos por tres proyectos: Proyecto Sincronización de semáforos de un barrio de la ciudad Modelo de Simulación para prevenir accidentes en cruces peligrosos Control de Medicamentos en Hospitales Alumno A 9 9 2 Alumno B 8 7 6 Alumno C 5 3 4 Alumno D 6 5 8 Alumno E 8 6 7 Alumno F 6 6 4 Se pide asignar a cada proyecto un grupo de dos alumnos que sea máximo el interés total de dicha asignación. Resolverlo como un Problema de Asignación utilizando el método Húngaro. Pregunta 5 (25 puntos) Una empresa dedicada a la venta de computadores tiene tres tiendas, T1, T2 y T3. Las disponibilidades de computadores de cada tienda son de 50, 60 y 40, respectivamente. Tres clientes, C1, C2 y C3, necesitan 80, 40 y 40 computadores, respectivamente. Los beneficios obtenidos por la venta de un computador a cada cliente depende de la tienda y el cliente, y son los que aparecen en la siguiente tabla: C1 C2 C3 T1 100.000 120.000 110.000 T2 120.000 - 130.000 T3 - 110.000 100.000 Además, por cada computador que no reciban los clientes, C1, C2 y C3, la empresa tiene que pagarles 10.000, 20.000 y 30.000 pesos, respectivamente. La empresa desea maximizar los beneficios en la venta de sus computadores satisfaciendo la demanda. (b) Obtener una solución básica factible inicial con el método de Vogel. (c) Encontrar la solución óptima e interpretarla. Tiempo: 120 minutos Pregunta 4 En este problema se tienen 6 alumnos para 3 trabajos. Por lo tanto, se deben formar grupos de 2 alumnos para los 3 trabajos. Entonces, se debe adecuar la tabla de datos a un problema de asignación, duplicando el número de proyectos, con los mismos valores de grado de interés: Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 9 9 9 9 2 2 Alumno B 8 8 7 7 6 6 Alumno C 5 5 3 3 4 4 Alumno D 6 6 5 5 8 8 Alumno E 8 8 6 6 7 7 Alumno F 6 6 6 6 4 4 Paso 1: Reducción por filas (se eligen los valores mayores debido a que es un problema de maximización). Se restan todos los números con el número mayor, y la tabla queda como sigue: Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 0 0 0 0 -7 -7 Alumno B 0 0 -1 -1 -2 -2 Alumno C 0 0 -2 -2 -1 -1 Alumno D -2 -2 -3 -3 0 0 Alumno E 0 0 -2 -2 -1 -1 Alumno F 0 0 0 0 -2 -2 Paso 2: Reducción por columnas Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 0 0 0 0 -7 -7 Alumno B 0 0 -1 -1 -2 -2 Alumno C 0 0 -2 -2 -1 -1 Alumno D -2 -2 -3 -3 0 0 Alumno E 0 0 -2 -2 -1 -1 Alumno F 0 0 0 0 -2 -2 Notar que en todas las columnas el número mayor es el cero. Al hacer la reducción con el número mayor por columnas, y tarjando todos los “0” con el menor número de líneas posible, la tabla queda así: Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 0 0 0 0 -7 -7 Alumno B 0 0 -1 -1 -2 -2 Alumno C 0 0 -2 -2 -1 -1 Alumno D -2 -2 -3 -3 0 0 Alumno E 0 0 -2 -2 -1 -1 Alumno F 0 0 0 0 -2 -2 Se tienen 5 líneas que es distinto al número de filas ó columnas, por lo tanto, se debe iterar para obtener la solución óptima: Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 0 0 0 0 -6 -6 Alumno B 0 0 -1 -1 -1 -1 Alumno C 0 0 -2 -2 0 0 Alumno D -3 -3 -4 -4 0 0 Alumno E 0 0 -2 -2 0 0 Alumno F 0 0 0 0 -1 -1 En esta iteración se obtiene la solución óptima, ya que el número de filas ó columnas es igual al número de líneas que cubren todos los ceros. Por lo tanto, se debe realizar la asignación respectiva, de manera que 2 alumnos sean asignados a un proyecto. Entonces la asignación óptima que maximiza el interés de los estudiantes es la siguiente: Alumnos A y F ( Proyecto de Simulación para accidentes Alumnos B y C ( Proyecto de Sincronización de semáforos Alumnos D y F ( Proyecto de Control de medicamentos. El interés Total Máximo es: 9 + 6 + 8 + 5 + 8 + 7 = 43. Otra forma de resolverlo consiste en transforma el problema de maximización a uno de minimización. Para ello todos los costos se multiplican por menos 1 y se resuelve con el método Húngaro para el caso de Minimización Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A -9 -9 -9 -9 -2 -2 Alumno B -8 -8 -7 -7 -6 -6 Alumno C -5 -5 -3 -3 -4 -4 Alumno D -6 -6 -5 -5 -8 -8 Alumno E -8 -8 -6 -6 -7 -7 Alumno F -6 -6 -6 -6 -4 -4 Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 0 0 0 0 7 7 Alumno B 0 0 1 1 2 2 Alumno C 0 0 2 2 1 1 Alumno D 2 2 3 3 0 0 Alumno E 0 0 2 2 1 1 Alumno F 0 0 0 0 2 2 Sincr-1 Sincr-2 Simul-1 Simul-2 Control-1 Control-2 Alumno A 0 0 0 0 6 6 Alumno B 0 0 1 1 1 1 Alumno C 0 0 2 2 0 0 Alumno D 3 3 4 4 0 0 Alumno E 0 0 2 2 0 0 Alumno F 0 0 0 0 1 1 Pregunta 5 TABLA INICIAL (MAXIMIZAR) Oferta 10012011050 120-M13060 -M11010040 -10-20-3010 Demanda804040 TABLA INICIAL (MINIMIZAR) OfertaCopui -100-1200-11050 100 20 0 20(-)30(+)- -120MM0-13060 10-20 60-- MM-110-10040 1010101010 -10(-)30(+) -3010020301010 101010140 -(+)-10(-) Demanda804040 20 1020 110 100 100 130 130 vj-100-120-110 Iteración 1 Ofertaui -100-1200-11050 0 1040- -120MM0-13060 -20 60-- MM-110-10040 10 -040 103020303010 110 10-- Demanda804040 vj-100-120-110 La solución obtenida en la iteración 1 es óptima debido a que todos los costos reducidos son menores o iguales a 0. Es importante observar que el costo reducido T2-->C3 es 0 por lo tanto, el problema tendrá múltiples soluciones, esto es, se podrá encontrar una nueva combinación de envíos de tal forma que el Beneficio sea el Mismo Además, el valor de la variable básica T3-->C2 = 0, por lo tanto la solución es degenerada EN RESUMEN: Desde AUnidades T1C110 T1C240 T2C160 T3C340 BENEFICIO (min)-16900 BENEFICIO16900(miles de pesetas) Existen 10 unidades que no llegan al destino C1 (demanda insatisfecha), y el costo por unidad es de $10 que está incluido en el beneficio neto obtenido. T1 T1 T2 T3 C1C2C3 FICT. C1C2C3 FICT. T3 C3 T1 T2 C1C2 T2 T3 FICT. La Solución Inicial Factible obtenida con el método Vogel es la siguiente: TABLA INICIAL (MAXIMIZAR) Oferta 10012011050 120-M13060 -M11010040 -10-20-3010 Demanda804040 TABLA INICIAL (MINIMIZAR) OfertaCopui -100-1200-11050 100 20 0 20(-)30(+)- -120MM0-13060 10-20 60-- MM-110-10040 1010101010 -10(-)30(+) -3010020301010 101010140 -(+)-10(-) Demanda804040 20 1020 110 100 100 130 130 vj-100-120-110 Iteración 1 Ofertaui -100-1200-11050 0 1040- -120MM0-13060 -20 60-- MM-110-10040 10 -040 103020303010 110 10-- Demanda804040 vj-100-120-110 La solución obtenida en la iteración 1 es óptima debido a que todos los costos reducidos son menores o iguales a 0. Es importante observar que el costo reducido T2-->C3 es 0 por lo tanto, el problema tendrá múltiples soluciones, esto es, se podrá encontrar una nueva combinación de envíos de tal forma que el Beneficio sea el Mismo Además, el valor de la variable básica T3-->C2 = 0, por lo tanto la solución es degenerada EN RESUMEN: Desde AUnidades T1C110 T1C240 T2C160 T3C340 BENEFICIO (min)-16900 BENEFICIO16900(miles de pesetas) Existen 10 unidades que no llegan al destino C1 (demanda insatisfecha), y el costo por unidad es de $10 que está incluido en el beneficio neto obtenido. T1 T1 T2 T3 C1C2C3 FICT. C1C2C3 FICT. T3 C3 T1 T2 C1C2 T2 T3 FICT. TABLA INICIAL (MAXIMIZAR) Oferta 10012011050 120-M13060 -M11010040 -10-20-3010 Demanda804040 TABLA INICIAL (MINIMIZAR) OfertaCopui -100-1200-11050 100 20 0 20(-)30(+)- -120MM0-13060 10-20 60-- MM-110-10040 1010101010 -10(-)30(+) -3010020301010 101010140 -(+)-10(-) Demanda804040 20 1020 110 100 100 130 130 vj-100-120-110 Iteración 1 Ofertaui -100-1200-11050 0 1040- -120MM0-13060 -20 60-- MM-110-10040 10 -040 103020303010 110 10-- Demanda804040 vj-100-120-110 La solución obtenida en la iteración 1 es óptima debido a que todos los costos reducidos son menores o iguales a 0. Es importante observar que el costo reducido T2-->C3 es 0 por lo tanto, el problema tendrá múltiples soluciones, esto es, se podrá encontrar una nueva combinación de envíos de tal forma que el Beneficio sea el Mismo Además, el valor de la variable básica T3-->C2 = 0, por lo tanto la solución es degenerada EN RESUMEN: Desde AUnidades T1C110 T1C240 T2C160 T3C340 BENEFICIO (min)-16900 BENEFICIO16900(miles de pesetas) Existen 10 unidades que no llegan al destino C1 (demanda insatisfecha), y el costo por unidad es de $10 que está incluido en el beneficio neto obtenido. T1 T1 T2 T3 C1C2C3 FICT. C1C2C3 FICT. T3 C3 T1 T2 C1C2 T2 T3 FICT. La solución obtenida en la iteración 1 es óptima debido a que todos los costos reducidos son menores o iguales a 0. Es importante observar que el costo reducido T2( C3 es 0, y por lo tanto, el problema tiene múltiples soluciones. Además, el valor de la variable básica T3 ( C2 es 0, por lo tanto, la solución es degenerada. Además se observa que existen 10 unidades que no llegan al destino C1. El costo de esta demanda insatisfecha por unidad es de 10 (miles de pesos). En Resumen: Desde A Unidades T1 C1 10 T1 C2 40 T2 C1 60 T3 C3 40 El Beneficio Neto es 16.900 (miles de pesos) formulacion.pdf Formulación Capítulo 2 Formulación Max ó Min Z = C X C.S.R. A X < B XJ > 0 ; j = 1, 2, ..., n Objetivo El presente trabajo es una recopilación de algunos problemas representativos de programación lineal, en donde se muestra al lector la solución a diferentes modelos, buscando desarrollar la capacidad inventiva para formular problemas de optimización de recursos. Programación Lineal - Problema General La Programación Lineal resuelve un tipo muy especial de problema, uno en el cual todas las relaciones entre las variables son lineales, tanto en las restricciones como en la Función Objetivo. Definición: Dado un conjunto de m desigualdades lineales ó ecuaciones lineales, con n variables, se requiere hallar valores no negativos de éstas variables que satisfagan las restricciones y maximicen ó minimicen alguna función lineal de las variables llamada Función Objetivo. Matemáticamente: Hallar XJ , J = 1, 2, . . . . . n Para: 15 Formulación Maximizar ó Z = C1X1 + C2X2 + . . . . . . + CnXn Minimizar Con las siguientes restricciones: a11X1 + . . . . . . + a1jXj + . . . . . . + a1nXn ≤ ó ≥ b1 . . . . . . . . . . ai1X1 + . . . . . . + aijXj + . . . . . + ainXn ≤ ó ≥ bi . . . . . . . . . . am1X1 + . . . . . . + amjXj+ . . . . . . + amnXn ≤ ó ≥ bm Xj ≥ 0 ; j = 1, 2, . . . . . . n Características de la Programación Lineal 1. Linealidad asume que no pueden haber términos así: X1X2 X32 a14Log X4 2. Asume las propiedades aditivas y multiplicativas. • Si una unidad tipo 1 necesita 2 horas en la Máquina A y una unidad tipo 2 necesita 2½ horas, entonces ambas necesitan 4½ horas. • Si una unidad tipo 3 necesita 1 hora en la máquina B, entonces 10 unidades necesitan 10 horas. 3. La función que se va a optimizar (maximizar ó minimizar) se llama función objetiva, fíjese que no aparece ningún término independiente ó constante. Los valores de las Xj son independientes de cualquier constante. 4. Cuando se dice que hay m restricciones, no están incluidas las condiciones Xj ≥ 0 (condición de no negatividad). 5. a) Cualquier conjunto de Xj que satisface las m restricciones se llama una solución al problema. 16 Formulación b) Si la solución satisface la condición de no negatividad Xj ≥ 0 , se llama una solución factible c) Una solución factible que optimiza la función objetiva se llama una solución factible óptima Usualmente hay un número infinito de soluciones factibles al
Compartir
Continuar navegando
Preguntas relacionadas
Compartir