Investigación Operativa I SIS-2209 1 _________________________________________________________________________________
Views 64 Downloads 0 File size 2MB
Investigación Operativa I SIS-2209
1
______________________________________________________________________________________________________________________________________
EXAMENES RESUELTOS PRIMER PARCIAL PROBLEMAS DE MODELACION 1) Una fábrica produce 3 productos A, B y C, los mismos que pasan por los siguientes talleres: cepillado, fresado, taladrado y ensamble. Los requerimientos por unidad de producto en horas y contribución son los siguientes: Producto Cepillado Fresado Taladrado Ensamble Contri/Unid A 1 1 0.5 1 $9 B 1 1 1 2 $7 C 0.5 1 1 3 $6 Las capacidades disponibles en el mes para los productos así como los requerimientos mínimos de ventas son: Capacidad (horas) Requerimiento Mínimo de Ventas Cepillado 180 Producto A 60 Fresado 280 Producto B 50 Taladrado 300 Producto C 40 Ensamble 600 Solución Identificar las variables. X1 = cantidad producida del producto A X2 = cantidad producida del producto B X3 = cantidad producida del producto C Identificar la función objetivo.
MAX Z 9x 1 7x2 6x 3 Identificar restricciones. 1x 1 1x 2 0.5x 3 180
1x 1 1x 2 1x 3 280 0.5x 1 1x 2 1x 3 300
Capacidad del Cepillado (horas) Capacidad del Fresado (horas) Capacidad del Taladrado (horas)
Capacidad del Ensamble (horas) 1x 1 2x 2 3x 3 600 Requerimiento mínimo del producto A x 1 60 Requerimiento mínimo del producto B x 2 50 Requerimiento mínimo del producto C x 3 40 Identificar restricciones de no negatividad. x1 , x2 , x3 0 2) Un carpintero fabrica dos productos: sillas y marcos. Su producción esta limitada por las disponibilidades en listones de madera (36 semanales), por las horas de mano de obra contratada (48 semanales) y por las horas de trabajo disponibles en la maquina cepilladora automática (70 semanales). Cada silla requiere 4 listones de madera, 3 horas de mano de obra y 10 horas de cepilladora. Cada marco requiere 4 listones, 6 horas de mano de obra y 5 horas de cepilladora. El carpintero vende cada silla a 300 Bs. Y cada marco a 200 Bs. Compra los listones a 20 Bs c/u. paga la hora de mano de obra a 10 Bs y alquila la cepilladora a 10 Bs la hora. Formule el programa de fabricación que haga máximas las utilidades. Resolver el problema por el método grafico. Cuanto incrementaran las utilidades del carpintero si no tiene que pagar nada por los recursos necesarios? Solución Identificar las variables. X1 = número de sillas producidos X2 = número de marcos producidos Identificar la función objetivo. MAX Z 300 - 80 - 30 - 100x 1 200 - 80 - 60 - 50x 2 MAX Z 90x 1 10x 2 Identificar restricciones. Disponibilidad de la Madera (listones) 4x1 4x2 36 _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
2
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ Disponibilidad de las horas de mano de obra 3x 1 6x 2 48
Disponibilidad de las horas de la cepilladora 10x 1 5x 2 70 Identificar restricciones de no negatividad. x1 , x2 0 Solución por el Método Grafico MAX Z = 90X1 + 10X2 s.a. 4X1 + 4X2 ≤ 36 3X1 + 6X2 ≤ 48 10X1 + 5X2 ≤ 70 X1, X2 ≥ 0 Puntos Criticos: Z(A) = Z(7,0) = 630 MAX Z(B) = Z(5,4) = 490 Z(C) = Z(2,7) = 250 Z(D) = Z(0,8) = 80
Solución: Z=630; X1=7; X2=0 Si el carpintero no pagara por los recursos la función seria: MAX Z = 300X1 + 200X2 Solución: Z=2300; X1=5; X2=4 3) Un granjero esta engordando cerdos para el mercado y desea determinar las cantidades de los tipos de alimentos disponibles que debe darse a cada cerdo para satisfacer ciertos requerimientos de nutrición a costo mínimo. En la tabla siguiente se da el número de unidades de cada tipo de ingrediente nutritivo básico contenido en un kilogramo de cada tipo de alimento, junto con los requerimientos diarios respecto a la nutrición y los costos de alimento: Ingrediente Kilogramo Kilogramo Kilogramo Requerimiento Nutritivo de Maíz de Residuos de grasa de Alfalfa Diario Mínimo Carbohidratos 90 20 40 200 Proteínas 30 80 60 180 Vitaminas 10 20 60 150 Costo (u.m.) 21 18 15 Formule el modelo de programación lineal para este problema. Solución Identificar las variables. X1 = cantidad de kilogramos de maíz X2 = cantidad de kilogramos de residuos de grasa X3 = cantidad de kilogramos de alfalfa Identificar la función objetivo.
MIN Z 21x 1 18x 2 15x3 Identificar restricciones. 90x 1 20x 2 40x 3 200
30x 1 80x 2 60x 3 180 10x 1 20x 2 60x 3 150 Identificar restricciones de no negatividad.
Requerimiento de Carbohidratos Requerimiento de Proteínas Requerimiento de Vitaminas
x1 , x2 , x3 0 4) Una refinería puede comprar dos tipos de petróleo: petróleo crudo ligero y petróleo crudo pesado. El costo por barril de estos tipos de petróleo es $11 y $9 respectivamente. De cada tipo de petróleo se producen por barril las siguientes cantidades de gasolina, kerosén y combustible para reactores. _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
3
______________________________________________________________________________________________________________________________________ Combustible para Petróleo Gasolina Kerosén Reactores Crudo Ligero 0.40 0.20 0.40 Crudo Pesado 0.40 0.40 0.20 La refinería tiene un contrato para entregar 1 millón de barriles de gasolina, 400.000 barriles de kerosén, y 250.000 barriles de combustible para reactores. Formular como un programa lineal el problema de encontrar el número de barriles de cada tipo de petróleo crudo que satisfacen la demanda y que minimizan el costo total. Solución Identificar las variables. X1 = número de petróleo crudo ligero comprado X2 = número de petróleo crudo pesado comprado Identificar la función objetivo.
MIN Z 11x 1 9x 2 Identificar restricciones. 0.40x 1 0.40x 2 1000000
0.20x 1 0.40x 2 400000
Demanda de la Gasolina Demanda del Kerosén
Demanda del Combustible para reactores 0.40x 1 0.20x 2 250000 Identificar restricciones de no negatividad. x1 , x2 0 5) Un sastre confecciona sacos, pantalones y abrigos en su taller donde además de el trabajan 2 operarios adicionales. Cuenta con 400 m2 de casimir, 100 m2 de paño y 400 m2 de tela para forros. En cada saco se utilizan 2 m2 de casimir y 1 m2 de tela para forros. Cada pantalón consume 1 m2 de casimir y ½ m2 de tela para forros, y cada abrigo se confecciona con 2.5 m2 de paño y 2 m2 de tela para forros. Los sacos, pantalones y abrigos se venden respectivamente a Bs. 300, 150 y 400. Tanto el sastre como los operarios tienen cada uno, un rendimiento de 5 (sacos/semana), 15 (pantalones/semana) y 3 (abrigos/semana). Además el sastre conoce por experiencia que a lo sumo se venden 10 (abrigos/mes) y los sacos siempre combinados con pantalón (terno completo), aunque se venden también pantalones sueltos. El costo del m2 de casimir es de Bs 50, el m2 de paño Bs 40 y el m2 de tela para forros de Bs 10. Formule un PL que permita obtener las máximas ganancias durante 3 meses (asuma que 1 mes = 4 semanas). Solución Identificar las variables. X1 = cantidad de sacos que confecciona el sastre X2 = cantidad de pantalones que confecciona el sastre X3 = cantidad de abrigos que confecciona el sastre Identificar la función objetivo.
MAX Z 300 - 100 - 10x 1 150 - 50 - 5 x 2 400 - 100 - 20x 3
MAX Z 190x 1 95x 2 280x 3 Identificar restricciones. 2x 1 1x 2 400
Disponibilidad del Casimir (m2)
2.5x 3 100 1x 1 1/2x2 2x 3 400
Disponibilidad del Paño (m2) Disponibilidad de la Tela para Forros (m2)
1/15x1 1/45x2 1/9x 3 12 Rendimiento de los 3 trabajadores (semanas) Demanda de los abrigos. 1/9x 3 10 Identificar restricciones de no negatividad. x1 , x2 , x3 0
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
4
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ PROBLEMA DE LOS METODOS DE SOLUCION 1) Considere el siguiente PL: MAX Z = 2X1 + 3X2 + 1X3 MAX Z = 2X1 + 3X2 + 1X3 s.a. s.a. X1 + 2X2 + 3X3 ≤ 18 X1 + 2X2 + 3X3 + X4 = 18 2X1 + 3X2 + 2X3 ≤ 30 2X1 + 3X2 + 2X3 + X5 = 30 2X1 + 2X2 + 1X3 ≤ 36 2X1 + 2X2 + 1X3 + X6 = 36 X1, X2, X3 ≥ 0 X1, X2, X3, X4, X5, X6 ≥ 0 La solución base esta formada por el vector: XB = {X2; X1; X6} Tomando en cuenta esta información, encontrar la solución optima. Solución
Primero se calcula B 1 (Gauss-Jordan)
2 1 0 B 3 2 0 2 2 1
B
1
2 - 1 0 - 3 2 0 2 - 2 1
Segundo se calcula las columnas de las VNB en el reglón 1, 2 y 3.
2 - 1 0 3 4 2 - 1 0 1 2 2 - 1 0 0 - 1 1 1 B a3 - 3 2 0 2 5 B a4 - 3 2 0 0 3 B a5 - 3 2 0 1 2 2 - 2 1 1 3 2 - 2 1 0 2 2 - 2 1 0 - 2 1
Tercero se calcula los coeficientes de las VNB en el reglón 0 (función objetivo).
2 - 1 0 3 4 C 3 C B B a3 C 3 3 2 0 - 3 2 0 2 1 3 2 0 5 1 2 1 1 2 - 2 1 1 3 2 - 1 0 1 2 _ 1 C 4 C B B a4 C 4 3 2 0 - 3 2 0 0 0 3 2 0 3 0 0 0 0 2 - 2 1 0 2 2 - 1 0 0 - 1 _ 1 C 5 C B B a5 C 5 3 2 0 - 3 2 0 1 0 3 2 0 2 0 1 0 1 2 - 2 1 0 - 2 _
1
Cuarto se calcula el lado derecho del tablero optimo.
2 - 1 0 18 6 B b - 3 2 0 30 6 2 - 2 1 36 12 1
Quinto se calcula el lado derecho del reglón 0 (función objetivo).
2 - 1 0 18 6 C B B b 3 2 0 - 3 2 0 30 3 2 0 6 30 2 - 2 1 36 12 1
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
5
______________________________________________________________________________________________________________________________________ El tablero óptimo completo es el siguiente: X2 + 4X3 + 2X4 – 1X5 =6 X1 – 5X3 – 3X4 + 2X5 =6 + 3X3 + 2X4 – 2X5 + X6 = 12 Z + 1X3 + 1X5 =30
XB X2 X1 X6 Zj-Cj
X1 0 1 0 0
2) Considere el siguiente PL: MAX Z = X1 – X2 + 2X3 s.a. 2X1 – 2X2 + 3X3 ≤ 5 X1 + X2 – X3 ≤ 3 X1 – X2 + X3 ≤ 2 X1, X2, X3 ≥ 0 Sea: X4, X5 y X6 las variables de holgura para simplex se llega a la tabla final siguiente. XB X1 X2 5 X6 2 X3 4 Zj-Cj 2 Solución
X2 1 0 0 0
X3 4 -5 3 1
X4 2 -3 2 0
X5 -1 2 -2 1
X6 0 0 1 0
b 6 6 12 30
MAX Z = X1 – X2 + 2X3 s.a. 2X1 – 2X2 + 3X3 +X4 =5 X1 + X2 – X3 + X5 =3 X1 – X2 + X3 +X6 = 2 X1, X2, X3, X4, X5, X6 ≥ 0 las restricciones respectivas. Luego de aplicar el procedimiento del X2 1 0 0
X3 0 0 1
X4 1 0 1
X5 3 1 2
X6 0 1 0
b 14 5 11
0
0
1
1
0
8
Primero se calcula B 1 (Gauss-Jordan)
B
1
1 3 0 0 1 1 1 2 0
Segundo se calcula las columnas de las VNB en el reglón 1.
1 3 0 2 5 B a1 0 1 1 1 2 1 2 0 1 4 1
Tercero se calcula los coeficientes de las VNB en el reglón 0 (función objetivo).
1 3 0 2 5 C 1 C B B a1 C 1 - 1 0 2 0 1 1 1 1 - 1 0 2 2 1 3 1 2 1 2 0 1 4 _
1
Cuarto se calcula el lado derecho del tablero optimo.
1 3 0 5 14 B b 0 1 1 3 5 1 2 0 2 11 1
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
6
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________
Quinto se calcula el lado derecho del reglón 0 (función objetivo).
1 3 0 5 14 C B B b - 1 0 2 0 1 1 3 - 1 0 2 5 8 1 2 0 2 11 1
3) Resolver gráficamente el siguiente PL. MIN Z = 3X1 + 6X2 s.a. 1X1 + 3X2 ≥ 10 2X1 – 3X2 ≤ 5 6X1 + 1X2 ≤ 10 X1, X2 ≥ 0 Puntos Criticos: Z(O) = Z(0 ; 0) = 0 Z(A) = Z(0 ; 10/3) = 20 MIN Z(B) = Z(20/17 ; 50/17) = 21.18 Z(C) = Z(0 ; 10) = 60
Solución: Z=20; X1=0; X2=10/3 4) Resolver el siguiente PL. MIN Z =2X1 + 3X2 s.a. 2X1 + 2X2 = 30 X1 + 2X2 ≥ 10 X1, X2 ≥ 0
X2 15
Puntos Criticos: Z(A) = Z(15 ; 0) = 30 MIN Z(B) = Z(0 ; 15) = 45
B
R1
5
R2 O
A 10
X1
15
Solución: Z=30; X1=15; X2=0 5) Resolver gráficamente el siguiente PL. MIN Z = 2X1 + 8X2 s.a. 2X1 + 4X2 ≥ 8 2X1 – 5X2 ≤ 0 -1X1 + 5X2 ≤ 5 X1, X2 ≥ 0 Puntos Criticos: Z(A) = Z(10/7 ; 9/7) = 13.14 Z(B) = Z(5 ; 2) = 26 Z(C) = Z(20/9 ; 8/9) = 11.55 MIN Solución: Z=11.55; X1=20/9; X2=8/9 _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
7
______________________________________________________________________________________________________________________________________ 6) A partir del Tablero siguiente obtenido en el transcurso de la resolución de un Pl de variables de decisión (nonegativas) X1, X2, X3 y 2 restricciones de desigualdad. En el cual fueron incluidas 2 variables de holgura nonegativas (S1, S2) identificar las condiciones para a, b y c, para que las afirmaciones siguientes sean verdaderas: i) La solución básica es una Solución Básica Factible (BF). ii) La solución básica (BF) es óptima. iii) El Pl tiene una solución no-acotada (asumiendo en (iii) que b>0). iv) La Solución Básica es optima y existen soluciones optimas alternativas (asumiendo en (iv) que a>0). 4° X1 X2 X3 S1 S2 b
S1 0 -2 2 X1 1 -1 3 Zj-Cj 0 a b i) La solución básica es una Solución Básica Factible (BF).
1 0
3 -5
c 3
0
4
82
ii) La solución básica (BF) es óptima. Si la función es: MAX entonces a ≥ 0; b ≥ 0 y c ≥ 0 MIN entonces a ≤ 0; b ≤ 0 y c ≥ 0 iii) El Pl tiene una solución no-acotada (asumiendo en (iii) que b>0). Si la función es: MAX entonces a ≤ 0; b > 0 y c ≥ 0 MIN entonces a ≥ 0; b > 0 y c ≥ 0 iv) La Solución Básica es optima y existen soluciones optimas alternativas (asumiendo en (iv) que a>0). Si la función es: MAX entonces a > 0; b = 0 y c ≥ 0 MIN entonces a > 0; b = 0 y c ≥ 0 7) Resolver el siguiente PL MAX Z = 3X1 + 4X2 + 3X3 MAX Z = 3X1 + 4X2 + 3X3 s.a. s.a. X1 + 2X2 + 3X3 ≤ 18 X1 + 2X2 + 3X3 +s1 = 18 2X1 + 3X2 + 2X3 ≤ 27 2X1 + 3X2 + 2X3 +s2 = 27 2X1 + 2X2 + 1X3 ≤ 54 2X1 + 2X2 + 1X3 +s3 = 54 X1, X2, X3 ≥ 0 X1, X2, X3, s1, s2, s3 ≥ 0 Solución 1° X1 X2 X3 S1 S2 S1 1 2 3 1 0 S2 2 3 2 0 1 S3 2 2 1 0 0 Zj-Cj -3 -4 -3 0 0 Entra el más negativo de Zj-Cj (-4) Sale Min {18/2; 27/3; 54/2} = {S1} 2° X1 X2 X3 S1 S2 X2 1/2 1 3/2 1/2 0 -5/2 -3/2 S2 1/2 0 1 S3 1 0 -2 -1 0 Zj-Cj -1 0 3 2 0 Entra el más negativo de Zj-Cj (-1) Sale Min {9/1/2; 0/1/2; 36/1} = {S2}
S3 0 0 1 0
b 18 27 54 0
3° X1 X2 X3 S1 S2 X2 0 1 4 2 -1 X1 1 0 -5 -3 2 S3 0 0 3 2 -2 Zj-Cj 0 0 -2 -1 2 Entra el más negativo de Zj-Cj (-2) Sale Min {9/4; 0/-5; 36/3} = {X2}
S3 0 0 1 0
S3 0 0 1
b 9 0 36
0
36
4° X1 X2 X3 S1 S2 S3 b X3 0 1/4 1 1/2 -1/4 0 9/4 -1/2 X1 1 5/4 0 3/4 0 45/4 -3/4 S3 0 0 1/2 -5/4 1 117/4 Zj-Cj 0 1/2 0 0 3/2 0 81/2 Solución: Z=81/2; X1=45/4; X2=0; X3=9/4
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
b 9 0 36 36
8
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ 6) Resolver el siguiente PL MAX Z = 2X1 + 1X2 MAX Z = 2X1 + 1X2 s.a. s.a. –X1 + X2 ≤ 1 –X1 + X2 +s1 =1 X1 – 2X2 ≤ 2 X1 – 2X2 +s2 = 2 X1, X2 ≥ 0 X1, X2, s1, s2 ≥ 0
Solución 1° X1 X2 S1 S2 S1 -1 1 1 0 S2 1 -2 0 1 Zj-Cj -2 -1 0 0 Entra el más negativo de Zj-Cj (-2) Sale Min {1/-1; 2/1} = {S2}
b 1 2
2° X1 X2 S1 S2 b S1 0 -1 1 1 3 X1 1 -2 0 1 2 Zj-Cj 0 -5 0 2 4 Entra el más negativo de Zj-Cj (-5) No existe un vector de salida por lo tanto es no acotado.
0
7) MAX Z = 2X1 + X2 - 3X3 + 5X4 s.a. X1 + 7X2 + 3X3 + 7X4 ≤ 46 3X1 - X2 + X3 + 2X4 ≤ 8 2X1 + 3X2 - X3 + X4 ≤ 10 X1, X2, X3, X4 ≥ 0 1° X1 X2 S1 1 7 S2 3 -1 S3 2 3 Zj-Cj -2 -1 Entra el más negativo de Zj-Cj (-5) Sale Min {46/7; 8/2; 10/1} = {S2}
MAX Z = 2X1 + X2 - 3X3 + 5X4 s.a. X1 + 7X2 + 3X3 + 7X4 +s1 = 46 3X1 - X2 + X3 + 2X4 +s2 =8 2X1 + 3X2 - X3 + X4 +s3 = 10 X1, X2, X3, X4, s1, s2, s3 ≥ 0 X3 3 1 -1 3
X4 7 2 1 -5
S1 1 0 0 0
S2 0 1 0 0
S3 0 0 1 0
b 46 8 10 0
2° X1 X2 X3 S1 -19/2 21/2 -1/2 X4 3/2 -1/2 1/2 S3 ½ 7/2 -3/2 Zj-Cj 11/2 -7/2 11/2 Entra el más negativo de Zj-Cj (-7/2) Sale Min {18/21/2; 4/-1/2; 6/7/2} = {S1}
X4 0 1 0
S1 1 0 0
S2 -7/2 1/2 -1/2
S3 0 0 1
b 18 4 6
0
0
5/2
0
20
3° X1 X2 X3 X2 -19/21 1 -1/21 X4 22/21 0 10/21 S3 11/3 0 -4/3 Zj-Cj 7/3 0 16/3 Solución: Z=26; X1=0; X2=12/7; X3=0; X4=34/7
X4 0 1 0 0
S1 2/21 1/21 -1/3 1/3
S2 -1/3 1/3 2/3 4/3
S3 0 0 1 0
b 12/7 34/7 0 26
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
9
______________________________________________________________________________________________________________________________________
EXAMENES RESUELTOS SEGUNDO PARCIAL PROBLEMAS DE ANALISIS DE SENSIBILIDAD 1) Un taller utiliza sierras, tornos y taladros para producir 4 tipos de partes de maquinas. La tabla a continuación resume los datos de la situación: Tiempo de trabajo en maquina [min/parte] Capacidad Maquina Parte 1 Parte 2 Parte 3 Parte 4 (minutos) Sierra 5 3 4 4 1200 Tornos 2 5 3 4 1200 Taladros 3 4 6 4 1200 Utilidad (Bs) 3 6 10 4 La situación óptima encontrada es la siguiente: Xi A1 A2 A3
A4
A5
A6
A7
X5 3 1/3 0 4/3 1 0 -2/3 X6 1/2 3 0 2 0 1 -1/2 X3 1/2 2/3 1 2/3 0 0 1/6 Zj-Cj 2 2/3 0 8/3 0 0 5/3 Se puede observar que en el óptimo solo se deben fabricar piezas de la parte 3. Responder a las siguientes preguntas mostrando las operaciones realizadas, en todos del problema inicial indicado.
b 400 600 200 2000 los casos respecto a la solución
a) Aplicando holgura complementaria, determine que recursos se consumen completamente. Solución Z = 2000; X1 = 0; X2 = 0; X3 = 200; X4 = 0; X5 = 400; X6 = 600; X7 = 0 Como X5 y X6 > 0 Y1 = 0 y Y2 = 0 Como solo X3 > 0 la tercera restricción debe ser activa. MAX Z = 3X1 + 6X2 + 10X3 + 4X4 s.a. 5X1 + 3X2 + 4X3 + 4x4 ≤ 1200 2X1 + 5X2 + 3X3 + 4x4 ≤ 1200 3X1 + 4X2 + 6X3 + 4x4 ≤ 1200 X1, X2, X3, x4 ≥ 0 (Y1 = 0 y Y2 = 0) 4Y1 + 3Y2 + 6Y3 = 10 Y3 = 10/6 = 5/3 Z = 2000; Y1 = 0; Y2 = 0; Y3 = 5/3 Por lo tanto como solamente Y3 > 0 el tercer recurso o el recurso del taladro se consume completamente. b) Para los recursos que se consumen completamente, determine en que cantidad máxima se pueden incrementar los mismos, de tal forma que la solución base permanezca optima. Solución
1 0 - 2 3 1200 1 B b 0 1 - 1 2 1200 0 0 0 1 6 Δ
1200 - 2 3Δ 0
Δ 1800
1200 - 1 2 Δ 0
Δ 2400
1 6Δ 0
Δ0
El rango de factibilidad para el recurso que se consume completamente es: 0 Δ 1800 Por lo tanto lo máximo que se puede incrementar este recurso (recurso 3 de taladros) es a 1800 minutos para que la solución base permanezca optima. _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
10
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ c) Suponga que el alquiler de uso de cualquiera de las maquinas es de Bs. 25 la hora. Hasta cuanto se podría disminuir el uso del torno y cuanto ahorraría manteniendo la solución base? Solución
1 0 - 2 3 1200 1 B b 0 1 - 1 2 Δ 0 0 0
1200 - 800 0 Δ 600
Δ - 600 0
1 6 1200 200 0 El rango de factibilidad para el recurso del torno es: 600 Δ Por lo tanto lo máximo que se puede disminuir el uso del torno es a 600 minutos y ahorraría otros 600 minutos o 10 horas lo que nos daría un ahorro total de (10*25=250) 250 Bs. Manteniendo la solución base.
d) Suponga que el taller necesita cumplir con un contrato donde debe necesariamente tener que fabricar las 4 partes. Cuanto perdería por unidad de pieza respecto al optimo? Solución Zj-Cj 2 2/3 0 8/3 0 0 5/3 2000 Llevando los coeficientes de las variables del tablero óptimo a la función objetivo nos da: MAX Z = – 2X1 + – 2/3X2 – 0X3 – 8/3X4 Por lo tanto por cada pieza fabricada de la parte 1 se perdería 2 Bs, de la parte 2 se perdería 2/3 Bs. Y de la parte 4 se perdería 8 Bs. e) Hasta cuanto se podría pagar por recurso adicional para incrementar la utilidad? Solución Se pagaría 5/3 Bs. Por minuto adicional del taladro para incrementar nuestra utilidad ya que es el único recurso que se consume completamente. f) Suponga que el taller trata de mejorar sus ganancias, elevando el precio unitario para mejorar el rendimiento de las partes 1 y 4 a 5 Bs. Y 6 Bs. Respectivamente. Cual seria el nuevo plan de fabricación optimo? Solución MAX Z = 5X1 + 6X2 + 10X3 + 6X4 C B VB X 5 C VNB j
X1
X6 X2
X3
0
X4
X7
0 10
5
5 3 4 0 5 4 0 Son las VNB de las restricciones. 4 4 1
a 2 j 3
6 6 0
1 0 - 2 3 5 3 4 0
a C 0 0 10 0 1 - 1 2 2 5 4 0 5 6 6 0 5 20 3 20 3 5 3 5 6 6 0 0 2 3 2 3 5 3 j j X1 X X4 X7 2 0 0 1 6 3 4 4 1 El tablero óptimo es: Xi A1 A2 A3 A4 A5 A6 A7 b C BB
1
X5 X6 X3 Zj-Cj
3 1/2 1/2
1/3 3 2/3
0 0 1
4/3 2 2/3
1 0 0
0 1 0
-2/3 -1/2 1/6
400 600 200
0
2/3
0
2/3
0
0
5/3
2000
Solución alternativa Xi A1 A2 A3 A4 A5 A6 A7 b X1 1 1/9 0 4/9 1/3 0 -2/9 400/3 X6 0 53/18 0 16/9 -1/6 1 -7/18 1600/3 X3 0 11/18 1 4/9 -1/6 0 5/18 400/3 Zj-Cj 0 2/3 0 2/3 0 0 5/3 2000 Z = 2000; X1 = 400/3; X2 = 0; X3 = 400/3; X4 = 0; X5 = 0; X6 = 1600/3; X7 = 0
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
11
______________________________________________________________________________________________________________________________________ g) Debido a reservas en el taller, se tienen disponibles 2 maquinas taladradoras, por lo cual la disponibilidad de minutos de taladradora es ahora 2400. Encontrar la nueva solución optima. Solución
1 0 - 2 3 1200 - 400 1 0 - 2 3 1200 1 1 X B B b 0 1 - 1 2 1200 0 C B B b 0 0 10 0 1 - 1 2 1200 4000 0 0 1 6 0 0 1 6 2400 400 2400 El tablero óptimo es: Xi A1 A2 A3 A4 A5 A6 A7 b X5 X6 X3 Zj-Cj
3 1/2 1/2 2
1/3 3 2/3 2/3
0 0 1 0
4/3 2 2/3 8/3
1 0 0 0
0 1 0 0
-2/3 -1/2 1/6 5/3
-400 0 400 4000
Xi A1 A2 A3 A4 A5 A6 A7 b X7 -9/2 -1/2 0 -2 -3/2 0 1 600 X6 -7/4 11/4 0 1 -3/4 1 0 300 X3 5/4 3/4 1 1 1/4 0 0 300 Zj-Cj 19/2 3/2 0 6 5/2 0 0 3000 Z = 3000; X1 = 0; X2 = 0; X3 = 300/3; X4 = 0; X5 = 0; X6 = 300/3; X7 = 600 h) Suponga que debido a restricciones en el mercado, se deben fabricar máximo 100 piezas de la parte 3. Cual seria la nueva solución optima? Solución Adición de una nueva restricción: X3 ≤ 100 Xi X5 X6 X3 X8 Zj-Cj
A1 3 1/2 1/2 0 2
A2 1/3 3 2/3 0 2/3
A3 0 0 1 1 0
A4 4/3 2 2/3 0 8/3
A5 1 0 0 0 0
A6 0 1 0 0 0
A7 -2/3 -1/2 1/6 0 5/3
A8 0 0 0 1 0
X3 no es vector unitario en forma de columna por lo tanto debemos transformarlo. Xi A1 A2 A3 A4 A5 A6 A7 A8 X5 X6 X3 X8 Zj-Cj
3 1/2 1/2 -1/2 2
1/3 3 2/3 -2/3 2/3
0 0 1 0 0
4/3 2 2/3 -2/3 8/3
1 0 0 0 0
0 1 0 0 0
-2/3 -1/2 1/6 -1/6 5/3
0 0 0 1 0
b 400 600 200 100 2000
b 400 600 200 -100 2000
Xi A1 A2 A3 A4 A5 A6 A7 A8 b X5 11/4 0 0 1 1 0 -3/4 1/2 350 X6 -7/4 0 0 -1 0 1 -5/4 9/2 150 X3 0 0 1 0 0 0 0 1 100 X2 3/4 1 0 1 0 0 1/4 -3/2 150 Zj-Cj 3/2 0 0 2 0 0 3/2 1 1900 Z = 1900; X1 = 0; X2 = 150; X3 = 100; X4 = 0; X5 = 350; X6 = 150; X7 = 0; X8 = 0
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
12
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ 2) Un taller utiliza tornos y taladros para producir 4 tipos de partes de maquinas. La tabla a continuación resume los datos de la situación: Tiempo de trabajo en maquina [min/parte] Capacidad Maquina Parte 1 Parte 2 Parte 3 Parte 4 (minutos) Tornos 2 5 3 4 1200 Taladros 3 4 6 4 1200 Utilidad (Bs) 3 6 10 4
a) Determine la solución óptima primal y deducir la solución dual. Solución Xi X1 X2 X3 X4 X5 X6 X5 1/2 3 0 2 1 -1/2 X3 1/2 2/3 1 2/3 0 1/6 Zj-Cj 2 2/3 0 8/3 0 5/3 Sol. Primal MAX Z = 2000; X1 = 0; X2 = 0; X3 = 200; X4 = 0; X5 = 600; X6 = 0 Sol. Dual MIN Z = 2000; Y1 = 0; Y2 = 5/3; e1 = 2; e2 = 2/3; e3 = 0; e4 = 8/3
b 600 200 2000
b) Que partes no se fabricarían de acuerdo a la solución optima y cual seria el índice de deterioro en la utilidad optima por incremento unitario de cada una de esas partes. Solución Zj-Cj 2 2/3 0 8/3 0 5/3 2000 Llevando los coeficientes de las variables del tablero óptimo a la función objetivo nos da: MAX Z = – 2X1 + – 2/3X2 – 0X3 – 8/3X4 Las partes que no se fabricaran son las partes 1, 2 y 4. Por lo tanto por cada pieza fabricada de la parte 1 se perdería 2 Bs, de la parte 2 se perdería 2/3 Bs. Y de la parte 4 se perdería 8 Bs. c) Determine que recursos (tiempos de las maquinas) son utilizados completamente. Solución (Holgura complementaria) Z = 2000; X1 = 0; X2 = 0; X3 = 200; X4 = 0; X5 = 600; X6 = 0 Como X5 > 0 Y1 = 0 Como solo X3 > 0 la tercera restricción debe ser activa. MAX Z = 3X1 + 6X2 + 10X3 + 4X4 s.a. 2X1 + 5X2 + 3X3 + 4x4 ≤ 1200 3X1 + 4X2 + 6X3 + 4x4 ≤ 1200 X1, X2, X3, x4 ≥ 0 (Y1 = 0) 3Y1 + 6Y2 = 10 Y2 = 10/6 = 5/3 Z = 2000; Y1 = 0; Y2 = 5/3 Por lo tanto como solamente Y2 > 0 el segundo recurso o el recurso del taladro se consume completamente. d) En base a los criterios anteriores, determine una posible reducción en el tiempo de trabajo de las maquinas (para alguna de las partes), para fabricar la parte que menos deteriora la utilidad, haciendo que la misma incremente la utilidad (sea parte de la base). _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
13
______________________________________________________________________________________________________________________________________ Solución Se reducirá en un minuto el consumo de recurso de la segunda variable porque esta es la que menos deteriora la utilidad.
4 a2 3
1 1 2 4 5 2 0 1 6 3 1 2 1 1 2 4 4 1 C B B a2 C 2 0 10 3 6 0 10 6 3 6 5 - 6 -1 0 1 6 B
1
Xi X5 X3 Zj-Cj
a2
X1 1/2 1/2 2
X2 3 2/3 -1
X3 0 1 0
X4 2 2/3 8/3
X5 1 0 0
Xi X1 X2 X3 X4 X5 X2 1/5 1 0 4/5 2/5 X3 2/5 0 1 4/15 -1/5 Zj-Cj 11/5 0 0 52/15 2/5 Z = 2240; X1 = 0; X2 = 240; X3 = 80; X4 = 0; X5 = 0; X6 = 0
X6 -1/2 1/6 5/3
b 600 200 2000
X6 -1/5 4/15
b 240 80
22/15
2240
e) Hasta cuanto se pueden incrementar los recursos para que la solución base optima inicial, siga siendo optima?, y en este caso cual será el valor optimo de la utilidad?. Solución 1 1 1 2 B b 0 0 1 6 1200
Δ - 600 0 200 0
Δ 600
El rango de factibilidad para el primer recurso del torno es: 600 Δ Por lo tanto no existe un valor máximo para incrementar este recurso (recurso 1 de tornos), podemos tomar cualquier valor que tienda a infinito. Manteniendo la solución base optima. 1 1 1 2 1200 B b 0 0 1 6
1200 - 1 2 Δ 0
Δ 2400
1 6Δ 0
Δ0
El rango de factibilidad para el segundo recurso del taladro es: 0 Δ 2400 Por lo tanto lo máximo que se puede incrementar este recurso (recurso 2 de taladros) es 2400 minutos para que la solución base permanezca optima. En caso de que se incremente lo máximo cada recurso: b1=∞ pero se tomara un valor de 6000 y b 2=2400.
6000 2400
1 1 1 2 6000 4800 B b 0 1 6 2400 400
b
1 1 2 6000 1 C B B b 0 10 4000 0 1 6 2400
El tablero óptimo es: Xi X1 X2 X3 X4 X5 X6 X5 1/2 3 0 2 1 -1/2 X3 1/2 2/3 1 2/3 0 1/6 Zj-Cj 2 2/3 0 8/3 0 5/3 Z = 4000; X1 = 0; X2 = 0; X3 = 400; X4 = 0; X5 = 4800; X6 = 0
b 4800 400 4000
f) Cuanto debe ser el coeficiente mínimo (c1) para que la fabricación de la parte 1 produzca una solución optima? C B VB X 5 C VNB j
X 1
X3
0
X2
X4
10 X6
3
6 4 0
2 5 4 0 Son las VNB de las restricciones. a j 3 4 4 1
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
14
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________
CBB
1
1 - 1 2 2 5 4 0 a C 0 10 Δ 6 4 0 5 20 3 20 3 5 3 Δ 6 4 0 5 - Δ 2 3 8 3 5 3 0 j j X1 X X4 X6 0 1 6 3 4 4 1 2 5 -Δ 0 Δ 5
Por lo tanto lo mínimo para el coeficiente uno es -∞ ósea que no existe un valor mínimo.
g) Cuanto se pagaría por recurso adicional para incrementar la utilidad? Solución Se pagaría 5/3 Bs. Por minuto adicional del taladro para incrementar nuestra utilidad ya que es el único recurso que se consume completamente. h) Que cantidad mínima de minutos de torno deberán mantenerse para que la solución optima se mantenga?. Solución 1 1 1 2 B b 0 0 1 6 1200
Δ - 600 0
Δ 600
200 0
El rango de factibilidad para el primer recurso del torno es: 600 Δ Por lo tanto el valor mínimo de minutos de torno es de 600. Manteniendo la solución base optima. 3) Un taller artesanal fabrica bolsos, estuches y mochilas. La fabricación de los tres productos requiere cuero y material sintético. El cuero es la materia prima limitante. Se utilizan dos tipos de mano de obra: costura y acabado. La siguiente tabla proporciona la disponibilidad de recursos, su utilización y las utilidades por unidad: Requerimiento de recursos/unid Disponibilidad Recurso Bolso Mochila Estuche Diaria 2 Cuero (pies ) 2 1 3 42 Costura (Hrs) 2 1 2 40 Acabado (Hrs) 1 1 1 45 Precio de Venta (Bs) 24 22 45 a) Formular el programa lineal y encontrar la solución optima. MAX Z = 24X1 + 22X2 + 45X3 s.a. 2X1 + 1X2 + 3X3 ≤ 42 2X1 + 1X2 + 2X3 ≤ 40 1X1 + 1X2 + 1X3 ≤ 45 X1, X2, X3 ≥ 0 Tablero inicial: Xi X1 X2 X3 X4 X5 X4 X5 X6 Zj-Cj
X6
b
2 2 1
1 1 1
3 2 1
1 0 0
0 1 0
0 0 1
42 40 45
-24
-22
-45
0
0
0
0
X1 2/3 2/3 1/3
X2 1/3 1/3 2/3
X3 1 0 0
X4 1/3 -2/3 -1/3
X5 0 1 0
X6 0 0 1
b 14 12 31
6
-7
0
15
0
0
630
Primera iteración: Xi X3 X5 X6 Zj-Cj Tablero optimo final: _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
15
______________________________________________________________________________________________________________________________________ Xi X1 X2 X3 X4 X5 X6 b
X3 0 0 1 1 -1 0 2 X2 2 1 0 -2 3 0 36 X6 -1 0 0 1 -2 1 7 Zj-Cj 20 0 0 1 21 0 882 Z = 882; X1 = 0; X2 = 36; X3 = 2; X4 = 0; X5 = 0; X6 = 7 Se puede observar que en el óptimo solo se fabricaran mochilas y estuches. b) En base a la solución optima, encontrar la nueva solución cuando el cuero se incrementa a 45 pies2. Solución
1 1 B b -2 1
El tablero óptimo es:
0 45 5 0 40 30 - 2 1 45 10 -1 3
1 C B B b 45
1 - 1 0 45 22 0 - 2 3 0 40 885 1 - 2 1 45
Xi X1 X2 X3 X4 X5 X6 b X3 0 0 1 1 -1 0 5 X2 2 1 0 -2 3 0 30 X6 -1 0 0 1 -2 1 10 Zj-Cj 20 0 0 1 21 0 885 Z = 885; X1 = 0; X2 = 30; X3 = 5; X4 = 0; X5 = 0; X6 = 10 c) Cual es la solución optima cuando las horas de acabado disponibles se incrementan a 50 hrs. Solución
1 1 B b -2 1
El tablero óptimo es:
0 42 2 0 40 36 - 2 1 50 12 -1 3
1 C B B b 45
1 - 1 0 42 22 0 - 2 3 0 40 882 1 - 2 1 50
Xi X1 X2 X3 X4 X5 X3 0 0 1 1 -1 X2 2 1 0 -2 3 X6 -1 0 0 1 -2 Zj-Cj 20 0 0 1 21 Z = 882; X1 = 0; X2 = 36; X3 = 2; X4 = 0; X5 = 0; X6 = 12
X6 0 0 1
b 2 36 12
0
882
d) ¿Recomendaría la contratación de un trabajador adicional de costura a 15 Bs. la hora?. Solución
1 1 B b -2 1
0 42 1 0 41 39 - 2 1 45 5 -1 3
1 C B B b 45
1 - 1 0 42 22 0 - 2 3 0 41 903 1 - 2 1 45
El tablero óptimo es: Xi X1 X2 X3 X4 X5 X6 b X3 0 0 1 1 -1 0 1 X2 2 1 0 -2 3 0 39 X6 -1 0 0 1 -2 1 5 Zj-Cj 20 0 0 1 21 0 903 Z = 903; X1 = 0; X2 = 39; X3 = 1; X4 = 0; X5 = 0; X6 = 5 Por lo tanto por cada hora adicional de costura se tiene una ganancia de (903 – 882 =21 Bs.) y si la hora de costura nos cuesta 15 Bs. tendremos una ganancia neta de (21 – 15 = 6 Bs.) _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
16
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ e) ¿Qué recursos se agotan completamente? Solución Primal Z = 882; X1 = 0; X2 = 36; X3 = 2; X4 = 0; X5 = 0; X6 = 7 Dual Z = 2000; Y1 = 1; Y2 = 21; Y3 = 0; Como Y1 y Y2 son ≥ 0; las restricciones R1 y R2 se agotan completamente, R3 no se agota.
Por lo tanto solamente el cuero y las horas de costura se consumen completamente. Y nos sobra 7 horas de acabado. 4) Se tiene el siguiente P.L. y su correspondiente tabla optima. MAX Z = 2X1 + 3X2 + X3 Xi A1 s.a. X2 0 X1 + 2X2 + 3X3 ≤ 18 X1 1 2X1 + 3X2 + 2X3 ≤ 30 X6 0 2X1 + 2X2 + X3 ≤ 36 Zj-Cj 0 X1, X2, X3 ≥ 0
A2 1 0 0 0
A3 4 -5 3 1
A4 2 -3 2 0
A5 -1 2 -2 1
A6 0 0 1 0
b 6 6 12 30
a) Resuelva el problema si (c1, c2, c3) cambia a: (4, 3, 1) Solución MAX Z = 4X1 + 3X2 + X3 C B VB X 2
3 4 0 X 5 1 0 0
3 1 0 a 2 0 1 Son las VNB de las restricciones. j C VNB X 3 X 4 1 0 0 j 2 - 1 0 3 1 0 1 C B B a C 3 4 0 - 3 2 0 2 0 1 1 0 0 - 8 - 6 5 1 0 0 - 9 - 6 5 j j X X4 X5 3 2 - 2 1 1 0 0 2 - 1 0 18 18 1 C B B b 3 4 0 - 3 2 0 30 - 6 5 0 30 42 2 - 2 1 36 36 X1
X6
El tablero óptimo es:
Xi
A1
A2
A3
A4
A5
A6
b
X2 X1 X6 Zj-Cj
0 1 0 0
1 0 0 0
4 -5 3 -9
2 -3 2 -6
-1 2 -2 5
0 0 1 0
6 6 12 42
A2 1/4 5/4 -3/4 9/4
A3 1 0 0 0
A4 1/2 -1/2 1/2 -3/2
A5 -1/4 3/4 -5/4 11/4
A6 0 0 1 0
b 3/2 27/2 15/2 111/2
Xi A1 A2 A3 A4 A5 X4 0 1/2 2 1 -1/2 X1 1 3/2 1 0 1/2 X6 0 -1 -1 0 -1 Zj-Cj 0 3 3 0 2 Z = 60; X1 = 15; X2 = 0; X3 = 0; X4 = 3; X5 = 0; X6 = 6
A6 0 0 1
b 3 15 6
0
60
Xi X3 X1 X6 Zj-Cj
A1 0 1 0 0
b) Resuelva el problema con la nueva restricción 2X2 + X3 ≤ 20 _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
17
______________________________________________________________________________________________________________________________________ Solución Restricción Estandarizada: 2X2 + X3 + X7 = 20 Xi A1 A2 A3 A4 A5 A6 A7 b
X2 0 1 4 2 -1 0 0 X1 1 0 -5 -3 2 0 0 X6 0 0 3 2 -2 1 0 X7 0 2 1 0 0 0 1 Zj-Cj 0 0 1 0 1 0 0 X2 no es vector unitario en forma de columna por lo tanto debemos transformarlo. Xi A1 A2 A3 A4 A5 A6 A7 X2 0 1 4 2 -1 0 0 X1 1 0 -5 -3 2 0 0 X6 0 0 3 2 -2 1 0 X7 0 0 -7 -4 2 0 1 Zj-Cj 0 0 1 0 1 0 0 Z = 30; X1 = 6; X2 = 6; X3 = 0; X4 = 0; X5 = 0; X6 = 12; X7 = 8 5) Considere el siguiente programa lineal: MAX Z = 5X1 + 2X2 + 3X3 s.a. X1 + 5X2 + 2X3 = 30 X1 – 5X2 – 6X3 ≤ 40 X1, X2, X3 ≥ 0
XB X1 X5 Zj-Cj
6 6 12 20 30 b 6 6 12 8 30
A1 1 0
A2 5 -10
A3 2 -8
A4 1 -1
A5 0 1
b 30 10
0
23
7
5+M
0
150
a) Encuentre la solución óptima cuando la función objetivo cambia a: MAX Z = 5X1 + 5X2 + 30X3 – Ma1 Solución C B VB X 1 C VNB j
CBB
1
X 2
X5 X3
5 X4
0
5
5 a j 5
30 0
2
1
Son las VNB de las restricciones.
6 0
1 0 5 2 1 a C 5 0 5 30 - M 25 10 5 5 30 - M 20 - 20 5 M j j X4 1 1 5 6 0 X2 X 3
1 0 30 30 1 C B B b 5 0 5 0 150 1 1 40 10 El tablero óptimo es: XB A1 X1 X5 Zj-Cj
1 0
A2 5 -10
A3 2 -8
A4 1 -1
A5 0 1
b 30 10
0
20
-20
5+M
0
150
A5 0 1 0
b 15 130 450
XB A1 A2 A3 A4 X3 1/2 5/2 1 1/2 X5 4 10 0 3 Zj-Cj 10 70 0 15+M Z = 450; X1 = 0; X2 = 0; X3 = 15; X4 = 0; X5 = 130
b) Suponga que las restricciones se transforman en: (30 + α; 40 – 2α) Donde α > 0. Determine los valores de α para los cuales la solución básica se mantiene factible y determine la expresión general de Z en función de α. _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
18
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ Solución
Primera Forma
1 δ K 2
X BK B
30 1 b 10
B
1 0 1 1 1 δ K - 1 1 2 3
(X ) 1 10 10 α* Min 1BK /B δ k 0 Min 3.33 3 3 B δ k
Solo negativos (-3)
La solución es óptima para: 0 α 3.33
Segunda Forma
30 α Aplicar δ K 40 2α
B
1 0 30 α 1 δ K - 1 1 40 2α
La solución es óptima para:
0 α 10 3
30 α 10 3α
30 α 0
α 30
10 - 3α 0
α 10 3
Expresión General Z* C B B
1 δ K 5
1 0 30 α 30 α 5 0 150 5α - 1 1 40 2α 10 3α
0
b) Suponga que las restricciones se transforman en: (30 + 2α; 40 – 2α) donde α > 0. Determine los valores de α para los cuales la solución básica se mantiene factible y determine la expresión general de Z en función de α. En el caso de que α llegue a su valor critico, que variable abandonaría la base y que variable ingresaría? Solución
30 2α δ K 40 2α
B
1 0 30 2α 1 δ K - 1 1 40 2α
1 δ K 5
30 2α 0
α 30 2
10 - 4α 0
α 10 4
0 α 10 4
La solución es óptima para: Z* C B B
30 2α 10 4α
1 0 30 2α 30 2α 40 2α 5 0 10 4α 150 10α 1 1
0
En el caso de que α=3 la variable que abandonaría la base seria X5 y la variable que ingresaría seria X3 α=3
30 2(3) 36 10 4(3) - 2
Z* 150 10α 150 10(3) 180
XB X1 X5 Zj-Cj
A1 1 0 0
A2 5 -10 23
A3 2 -8 7
A4 1 -1 5+M
A5 0 1 0
b 36 -2 180
Solución Optima: XB
A1
A2
A3
A4
X1 1 5/2 0 3/4 X3 0 5/4 1 1/8 Zj-Cj 0 57/4 0 33/8+M Z = 713/4; X1 = 71/2; X2 = 0; X3 = 1/4; X4 = 0; X5 = 0
A5
b
1/4 -1/8
71/2 1/4
7/8
713/4
6) Considere el siguiente programa: MAX Z = 5X1 + 2X2 + 3X3 XB A1 A2 A3 A4 A5 b s.a. X1 1 5 2 1 0 30 X1 + 5X2 + 2X3 ≤ 30 X5 0 -10 -8 -1 1 10 X1 – 5X2 – 6X3 ≤ 40 Z -C 0 23 7 5 0 150 j j X1, X2, X3 ≥ 0 Cuya solución óptima se da en la tabla: Resolver el P.N. con los siguientes cambios: _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
19
______________________________________________________________________________________________________________________________________ a) La función objetivo cambia a: MAX Z = 5X1 + 2X2 + 12X3 Solución
C B VB X 1 C VNB j
C BB
1
X 2
X5 X3
5 X4
0
2
5 a j 5
12 0
2
1
Son las VNB de las restricciones.
6 0
1 0 5 2 1 a C 5 0 -2 5 6 0 2 12 0 25 10 5 2 12 0 23 j j 1 1 X2 X3
1 0 30 30 1 C B B b 5 0 5 0 150 1 1 40 10 El tablero óptimo es: XB A1 X1 X5 Zj-Cj
1 0
A2 5 -10
A3 2 -8
A4 1 -1
A5 0 1
b 30 10
0
23
-2
5
0
150
XB A1 A2 A3 X3 1/2 5/2 1 X5 4 10 0 Zj-Cj 1 28 0 Z = 180; X1 = 0; X2 = 0; X3 = 15; X4 = 0; X5 = 130 b) Se duplica la disponibilidad del recurso b 1 (b1=60) 1 1 0 60 60 B b 1 1 40 20
C BB
1
b 5
A4 1/2 3 6
A5 0 1 0
5
X4
b 15 130 180
1 0 60 300 1 1 40
0
XB A1 A2 A3 A4 A5 b X1 1 5 2 1 0 60 X5 0 -10 -8 -1 1 -20 Zj-Cj 0 23 7 5 0 300 Como existe un valor negativo en el vector b se aplica dual simplex para optimizar. XB A1 A2 A3 A4 A5 b X1 1 5/2 0 3/4 1/4 55 X3 0 5/4 1 1/8 -1/8 5/2 Zj-Cj 0 57/4 0 33/8 7/8 565/2 Z = 565/2; X1 = 55; X2 = 0; X3 = 5/2; X4 = 0; X5 = 0 c) Se añade una nueva actividad x6 con c6=2 y a6T=(4,4) Datos: C4 2
4 4
C B VB S1
a4
X 3 0 20
Solución:
1 0 4 4 a6 1 1 4 0 El tablero óptimo es: B
1
C BB
XB X1 X5 Zj-Cj
1
1 0 4 4 a6 C6 5 0 2 5 0 2 20 2 18 1 1 4 0
A1 1 0 0
A2 5 -10 23
A3 2 -8 7
A6 4 0 18
A4 1 -1 5
A5 0 1 0
b 30 10 150
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
20
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________
d) Se añade la nueva restricción: 2X2 + 6X3 ≤ 10 XB A1 A2 A3 A4 A5 X1 1 5 2 1 0 X5 0 -10 -8 -1 1 X6 0 2 6 0 0 Zj-Cj 0 23 7 5 0 Z = 150; X1 = 30; X2 = 0; X3 = 0; X4 = 0; X5 = 10; X6 = 10
A6 0 0 1 0
b 30 10 10 150
7) Una fábrica produce chamarras y bolsas de cuero. La chamarra necesita 8 m2 de cuero y la bolsa solo 3. El tiempo de confección es de 12 y 4 hrs. Respectivamente. El precio de compra del cuero es de $8 por m2 y el costo de la hora de trabajo se estima en $15. Se dispone de 1200 m2 y 1800 hrs. Se venden las chamarras a $350 y los bolsos a $120. La fábrica tiene un sobrante de capital. ¿Cómo podría invertir la fabrica este capital para obtener óptimamente ganancias adicionales?. ¿Qué representan las variables duales en este caso?. Suponga que la fábrica tiene un contrato para entregar al menos 50 bolsas. Cuanto llegaría a perder la fabrica con respecto al optimo? Solución X1 = Numero de chamarras a producir X2 = Numero de bolsas de cuero a producir Programa lineal: MAX Z = (350 – 64 – 180)X1 + (120 – 24 – 60)X2 MAX Z = 106X1 + 36X2 XB A1 A2 A3 A4 b s.a. X1 1 3/8 1/8 0 150 8X1 + 3X2 ≤ 1200 (Cuero) X4 0 19/2 -3/2 1 0 12X1 + 14X2 ≤ 1800 (Confección) Zj-Cj 0 15/4 53/4 0 15900 X1, X2 ≥ 0 Z = 15900; X1 = 150; X2 = 0; X3 = 0; X4 = 0 La fábrica no tiene capital sobrante o recursos sobrantes se consume todos los recursos. Las variables duales representan X1 = Precio a pagar por cuero ($ / m2) X2 = Precio a pagar por confección ($ / hora) Por unidad producida de una bolsa se pierde 15/4 $. Si produce las 50 bolsas perdería un total de: 15/4(50) = 375/2 $. MAX Z = 0X1 – 15/4X2 – 53/4X3 – 0X4 8) Una empresa produce dos tipos de sillas (S1, S2). El proceso de fabricación consta de dos tareas básicas: ensamble y terminado. Una silla S1 requiere de 1 ½ hora de ensamble y 1 hora de terminado dejando un beneficio de 20$. Una silla S2 requiere de ½ hora de ensamble y ½ hora de terminado dejando un beneficio de 12$. Actualmente se dispone de 100 horas de ensamblado y 80 horas de terminado. La compañía se encuentra realizando negociaciones salariales. Si usted fuera consultado: ¿Qué aconsejaría respecto al aumento en el valor de la hora hombre de ensamble y de terminado? Solución X1 = Numero de sillas S1 a producir X2 = Numero de sillas S2 a producir Programa lineal: Tablero Optimo: MAX Z =20X1 + 12X2 XB A1 A2 A3 A4 b s.a. X3 1/2 0 1 -1 20 1½X1 + ½X2 ≤ 100 (Ensamble) X2 2 1 0 2 160 1X1 + ½X2 ≤ 80 (Terminado) Z -C 4 0 0 24 1920 j j X1, X2 ≥ 0 Z = 1920; X1 = 0; X2 = 160; X3 = 20; X4 = 0 _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
21
______________________________________________________________________________________________________________________________________ Solución
1 1 1 Δ B b 0 0 2 80
Δ - 80 0
Δ 80
160 0
El rango de factibilidad para el recurso del ensamble es: 80 Δ Por lo tanto no existe un valor máximo para incrementar este recurso (recurso 1 de ensamble), podemos tomar cualquier valor que tienda a infinito. Manteniendo la solución base optima. 1 1 1 100 B b 0 0 2 Δ
100 - Δ 0
Δ 100
2Δ 0
Δ 0
El rango de factibilidad para el recurso del terminado es: 0 Δ 100 Por lo tanto lo máximo que se puede incrementar este recurso (recurso 2 de terminado) es 100 horas para que la solución base permanezca optima. TRANSPORTE 1) Una compañía tiene una división compuesta por 5 fábricas. Desea transportar las materias primas desde sus proveedores. Tres compañías de camiones han hecho proposiciones para transportar esas materias primas. Las capacidades de acarreo de estas empresas es de 2000, 1800 y 2000 ton/sem respectivamente. Los requerimientos por semana de las fabricas son 800, 1000, 900, 1200 y 1900 ton. Respectivamente. Determínese el programa de menor costo, teniendo las tarifas por ton. De las empresas 1, 2 y 3 a las fábricas A, B, C, D y E en la siguiente tabla: A 8 6 7
1 2 3
B 4 5 3
C 7 8 9
D 3 4 5
E 8 9 8
Solución 1 1 2 3
2
4 1200
800 8
4
7
6
5
7
3
5
3
8
8
4
9
9
5
8
800
100
1000
Para todas las VB ui v j cij 0 U1 = 0 U2 = 1 U3 = 0
2000 900
1000 800
U1 + V 3 – 7 = 0 U1 + V 4 – 3 = 0 U2 + V 1 – 6 = 0 U2 + V 3 – 8 = 0 U2 + V 5 – 9 = 0 U3 + V 2 – 3 = 0 U3 + V 5 – 8 = 0
3
1000 900
1200
1800 2000
1900
Para todas las VNB MIN zij c ij ui v j c ij V1 = 5 V2 = 3 V3 = 7 V4 = 3 V5 = 8
Z11–C11= U1 + V1 – C11 = (0+5) – 8 = –3 Z12–C12= U1 + V2 – C12 = (0+3) – 4 = –1 Z15–C15= U1 + V5 – C15 = (0+8) – 8 = 0 Z22–C22= U2 + V2 – C22 = (1+3) – 5 = –1 Z24–C24= U2 + V4 – C24 = (1+3) – 4 = 0 Z31–C31= U3 + V1 – C31 = (0+5) – 7 = –2 Z33–C33= U3 + V3 – C33 = (0+7) – 9 = –2 Z34–C34= U3 + V4 – C34 = (0+3) – 5 = –2 Como todas las VNB son negativas el tablero es óptimo y factible. Z = (7*800) + (3*1200) + (6*800) + (8*100) + (9*900) + (3*1000) + (8*100g0) Z = 33900 [u.m.]
2) En el siguiente modelo de transporte obtenga la solución inicial y luego la solución optima. _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
22
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ 13 9 12 8 20 4 15 7 9 30 14 7 1 0 40 3 12 5 19 50 60 60 10 10 Solución 1
2
3
1
13
9
12
8
4
15
7
9
14
7
20
30
2
20
3
30
4
3
30
10
10
1
0
5
19
20 12
60
60
Para todas las VB ui v j cij 0 U1 + V 2 – 9 = 0 U2 + V 1 – 4 = 0 U3 + V 2 – 7 = 0 U3 + V 3 – 1 = 0 U3 + V 4 – 0 = 0 U4 + V 1 – 3 = 0 U4 + V2 – 12 = 0
4
20
10
40 50
10
Para todas las VNB MIN zij c ij ui v j c ij
U1 = 0 U2 = 4 U3 = –2 U4 = 3
V1 = 0 V2 = 9 V3 = 3 V4 = 2
Z11–C11= U1 + V1 – C11 = (0+0) – 13 = –13 Z13–C13= U1 + V3 – C13 = (0+3) – 12 = –9 Z14–C14= U1 + V4 – C14 = (0+2) – 8 = –6 Z22–C22= U2 + V2 – C22 = (4+9) – 15 = –2 Z23–C23= U2 + V3 – C23 = (4+3) – 7 = 0 Z24–C24= U2 + V4 – C24 = (4+2) – 9 = –3 Z31–C31= U3 + V1 – C31 = (–2+0) – 14 = –16 Z43–C43= U4 + V3 – C43 = (3+3) – 5 = 1 Z44–C44= U4 + V4 – C44 = (3+2) – 19 = –14 Como tenemos valores positivos en VNB escogemos el más positivo para que entre a la base. (C43) Circuito: 1 1 2 3 4
2
3
4
20 13
9
12
8
15
7
9
20
30 4
20+ θ 14
7
3
10– θ 1
12 60
θ 5
60
10 0
20– θ
30
30
50
19 10
10
θ = MIN {VB (–θ)} = {20, 10} = 10 Para todas las VB ui v j cij 0 U1 + V 2 – 9 = 0 U2 + V 1 – 4 = 0 U3 + V 2 – 7 = 0 U3 + V 4 – 0 = 0 U4 + V 1 – 3 = 0 U4 + V2 – 12 = 0 U4 + V 3 – 5 = 0
U1 = 0 U2 = 4 U3 = –2 U4 = 3
40
1 1 2 3 4
2
3
4
20 13
9
12
8
4
15
7
9
14
7
1
0
20
30
30
30 30 3
10 12
60
10 10 5
60
50
19 10
40
10
Para todas las VNB MIN zij c ij ui v j c ij V1 = 0 V2 = 9 V3 = 2 V4 = 2
Z11–C11= U1 + V1 – C11 = (0+0) – 13 = –13 Z13–C13= U1 + V3 – C13 = (0+2) – 12 = –10 Z14–C14= U1 + V4 – C14 = (0+2) – 8 = –6 Z22–C22= U2 + V2 – C22 = (4+9) – 15 = –2 Z23–C23= U2 + V3 – C23 = (4+2) – 7 = –1 Z24–C24= U2 + V4 – C24 = (4+2) – 9 = –3 Z31–C31= U3 + V1 – C31 = (–2+0) – 14 = –16 Z33–C33= U3 + V3 – C33 = (–2+2) – 5 = –5 Z44–C44= U4 + V4 – C44 = (3+2) – 19 = –14
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
23
______________________________________________________________________________________________________________________________________ Como todas las VNB son negativas el tablero es óptimo y factible. Z = (9*20) + (4*30) + (7*30) + (0*10) + (3*30) + (12*10) + (5*10) Z = 770 [u.m.]
3) En el siguiente modelo de transporte obtenga la solución inicial mediante el método: i) Intuitivo y de ii) Voguel 10 20 5 7 10 13 9 12 8 20 4 15 7 9 30 14 7 1 0 40 3 12 5 19 50 60 60 10 10 Solución i) Intuitivo ii) Voguel A 1 2 3 4 5
B
C
D
E
A
10 10
20
13
9
5
7
0
12
8
0
7
9
0
20 10
10
10
4
15
14
7
1
0
0
12
5
19
0
20
10
10
50 3 60
60
10
10
10
1
20
2
30
3
40
4
50
5
10
DUALIDAD 1) Formular los problemas duales de los siguientes PL: a) MAX Z = X1 + 2X2 + 3X3 s.a. 5X1 + 2X2 + 3X3 ≤ 100 4X1 + X2 + 2X3 = 60 X2 + X3 ≤ 5 10X1 + X2 + 2X3 ≤ 80 X1, X2, X3 ≥ 0
B
C
D
E
10 10
20
5
7
0
13
9
12
8
0
4
15
7
9
0
14
7
10
10 10
30 20 20 3
30
10 0
0
5
19
0
40
30 12
60
10 1
60
10
10
50 10
b) MAX Z = X1 – 2X2 + 3X3 s.a. 5X1 + 2X2 + 3X3 ≤ 100 4X1 + X2 + 2X3 ≤ 60 4X1 – X2 + 6X3 = 9 X2 + X3 ≥ 5 10X1 + X2 + 2X3 ≤ 80 X1, X2 ≥ 0 X3 irrestricta
Solución a) MIN W = 100Y1 + 60Y 2 + 5Y 3 + 80Y 4 s.a. 5Y1 + 4Y 2 + 0Y 3 + 10Y 4 ≥ 1 2Y1 + 1Y 2 + 1Y 3 + 1Y 4 ≥ 2 3Y1 + 2Y 2 + 1Y 3 + 2Y 4 ≥ 3 Y1, Y3, Y4 ≥ 0 Y2 irrestricta
b) MIN W = 100Y1 + 60Y 2 + 5Y 3 + 80Y 4 + Y5 s.a. 5Y1 + 4Y 2 + 4Y 3 + 0Y 4 + 10Y5 ≥ 1 2Y1 + 1Y 2 – 1Y 3 + 1Y 4 + 1Y5 ≥ –2 3Y1 + 2Y 2 + 6Y 3 + 1Y 4 + 2Y5 = 3 Y1, Y2, Y5 ≥ 0 Y3 irrestricta Y4 ≤ 0
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
20
24
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ EXAMENES RESUELTOS TERCER PARCIAL ARBOL DE EXPANSIÓN MINIMO 1) Encontrar el árbol de expansión mínimo de la fig.
C
F
3
C
F
3
8 3
A
2
7 7 8
A
5
6
O
3
9
5
2
7
D
6
G
7
9
8
I
8
6
O
D
6
G
I
6
B
B
8
8
4
4
E
H
6
E
H
6
MIN Z = 7+6+2+3+3+6+4+6+8 = 45 2) Encontrar el árbol de expansión mínimo de la red siguiente: 60
3 45
3 9
20
50
30
4
6
45
1
40
5
10
35
1 5 30
25
7
35
6
45
20
15
25
2
30
4
35
40
30
9
20
20
15
25
30
10
25
7
2 8
50
8
MIN Z = 30+25+15+20+25+35+30+45+20 = 245 RUTA MÁS CORTA 3) Encontrar las rutas mas cortas entre los nodos 1 y restantes de la fig. (se sugiere aplicar dijkstra) * [3 , 3] [5 , 1] [16 , 6]
6
2
6
7
1
4
4
7
6
*[0,_]
1
2
2
* [7 , 3] [8 , 5] [10 , 2]
4
7
6
* [11 , 6] [13 , 4] [14 , 5]
6 3
7
3
1
9
7
3
4
7
6 1
* [11 , 4] [9 , 2]
6
7
5
2
7
2
2 2
2 5
6
* [1 , 1] [14 , 4]
5
9
7
3
7
5
* [8 , 3] [5 , 2]
Solución Nodo Inicial 1 1 1 1 1 1
Nodo Final 2 3 4 5 6 7
Ruta
Distancia
1-3-2 1-3 1-3-4 1-3-2-5 1-3-2-6 1-3-2-6-7
3 1 7 5 9 11
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
25
______________________________________________________________________________________________________________________________________
4) Aplicar el algoritmo de FLOYD para encontrar las rutas mas cortas entre cada par de nodos de la red que se muestra en la figura: * [3 , 1]
2
6
5 1
4
Matriz de distancias Do 1 2 3 1 – 3 4 2 ∞ – 1 3 ∞ ∞ – 4 ∞ ∞ ∞ 5 ∞ ∞ ∞
3
4 ∞ 4 2 – ∞
1
* [9 , 2] [6 , 3] [8 , 4]
2 2
1
Matriz de secuencia So 1 2 3 4 5 1 – 2 3 4 5 2 1 – 3 4 5 3 1 2 – 4 5 4 1 2 3 – 5 5 1 2 3 4 –
3
4
*[0,_]
4
2
5 ∞ 6 2 2 –
4
3
2 2
1
6
5
4
3
2
Dijkstra
* [4 , 1] [4 , 2]
2
4 * [7 , 2] [6 , 3]
K=3 (tachar la 3 fila y columna). D3 1 2 3 4 5 S3 1 – 3 4 6 6 1 2 ∞ – 1 3 3 2 3 ∞ ∞ – 2 2 3 4 ∞ ∞ ∞ – 2 4 5 ∞ ∞ ∞ ∞ – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 3 3 – 3 3
4 3 3 4 – 4
5 3 3 5 5 –
K=1 (tachar la 1 fila y columna). D1 1 2 3 4 5 S1 1 – 3 4 ∞ ∞ 1 2 ∞ – 1 4 6 2 3 ∞ ∞ – 2 2 3 4 ∞ ∞ ∞ – 2 4 5 ∞ ∞ ∞ ∞ – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 3 3 – 3 3
4 4 4 4 – 4
5 5 5 5 5 –
K=4 (tachar la 4 fila y columna). D4 1 2 3 4 5 S4 1 – 3 4 6 6 1 2 ∞ – 1 3 3 2 3 ∞ ∞ – 2 2 3 4 ∞ ∞ ∞ – 2 4 5 ∞ ∞ ∞ ∞ – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 3 3 – 3 3
4 3 3 4 – 4
5 3 3 5 5 –
K=2 (tachar la 2 fila y columna). D2 1 2 3 4 5 S2 1 – 3 4 7 9 1 2 ∞ – 1 4 6 2 3 ∞ ∞ – 2 2 3 4 ∞ ∞ ∞ – 2 4 5 ∞ ∞ ∞ ∞ – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 3 3 – 3 3
4 2 4 4 – 4
5 2 5 5 5 –
K=5 (tachar la 5 fila y columna). D5 1 2 3 4 5 S5 1 – 3 4 6 6 1 2 ∞ – 1 3 3 2 3 ∞ ∞ – 2 2 3 4 ∞ ∞ ∞ – 2 4 5 ∞ ∞ ∞ ∞ – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 3 3 – 3 3
4 3 3 4 – 4
5 3 3 5 5 –
Las distancias mínimas son: Nodo Inicial 1 1 1 1 2 2 2 3 3 4
Nodo Final 2 3 4 5 3 4 5 4 5 5
Ruta
Distancia
1-2 1-3 1-3-4 1-3-5 2-3 2-3-4 2-3-5 3-4 3-5 4-5
3 4 6 6 1 3 3 2 2 2
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
26
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________
5) Aplicar el método de FLOYD para encontrar las rutas mas cortas entre pares de nodos de la figura:
3
1
3
5
2 1
1
3
1
2 Matriz de distancias Do 1 2 3 1 – 1 3 2 1 – 1 3 ∞ ∞ – 4 ∞ ∞ ∞ 5 ∞ ∞ ∞
4 ∞ 5 2 – 1
5 ∞ 3 1 1 –
5
Matriz de secuencia So 1 2 3 4 5 1 – 2 3 4 5 2 1 – 3 4 5 3 1 2 – 4 5 4 1 2 3 – 5 5 1 2 3 4 –
1
4
K=3 (tachar la 3 fila y columna). Do 1 2 3 4 5 So 1 – 1 2 4 3 1 2 1 – 1 3 2 2 3 ∞ ∞ – 2 1 3 4 ∞ ∞ ∞ – 1 4 5 ∞ ∞ ∞ 1 – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 2 3 – 3 3
4 3 3 4 – 4
5 3 3 5 5 –
K=1 (tachar la 1 fila y columna). Do 1 2 3 4 5 So 1 – 1 3 ∞ ∞ 1 2 1 – 1 5 3 2 3 ∞ ∞ – 2 1 3 4 ∞ ∞ ∞ – 1 4 5 ∞ ∞ ∞ 1 – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 3 3 – 3 3
4 4 4 4 – 4
5 5 5 5 5 –
K=4 (tachar la 4 fila y columna). Do 1 2 3 4 5 So 1 – 1 2 4 3 1 2 1 – 1 3 2 2 3 ∞ ∞ – 2 1 3 4 ∞ ∞ ∞ – 1 4 5 ∞ ∞ ∞ 1 – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 2 3 – 3 3
4 3 3 4 – 4
5 3 3 5 5 –
K=2 (tachar la 2 fila y columna). Do 1 2 3 4 5 So 1 – 1 2 6 4 1 2 1 – 1 5 3 2 3 ∞ ∞ – 2 1 3 4 ∞ ∞ ∞ – 1 4 5 ∞ ∞ ∞ 1 – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 2 3 – 3 3
4 2 4 4 – 4
5 2 5 5 5 –
K=5 (tachar la 5 fila y columna). Do 1 2 3 4 5 So 1 – 1 2 4 3 1 2 1 – 1 3 2 2 3 ∞ ∞ – 2 1 3 4 ∞ ∞ ∞ – 1 4 5 ∞ ∞ ∞ 1 – 5
1 – 1 1 1 1
2 2 – 2 2 2
3 2 3 – 3 3
4 3 3 4 – 4
5 3 3 5 5 –
Las distancias mínimas son: Nodo Inicial 1 1
Nodo Final 2 3
1
4
1
5
2 2 2 3 3 4
3 4 5 4 5 5
Ruta
Distancia
1-2 1-2-3 1-3-4 1-2-3-4 1-3-5 1-2-3-5 2-3 2-3-4 2-3-5 3-4 3-5 4-5
1 2 4 3 1 3 2 2 1 1
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
27
______________________________________________________________________________________________________________________________________ 6) Encontrar la ruta mas corta entre el nodo 1 hacia los otros nodos de la red.
2 4
1
3
Matriz de distancias 1 2 3 4 5 6 – 4 7 5 ∞ ∞ 4 – 3 ∞ 5 ∞ 7 3 – 1 2 6 5 ∞ 1 – ∞ 8 ∞ 5 2 ∞ – 3 ∞ ∞ 3 8 3 – ∞ ∞ ∞ ∞ 6 2
7
3
1
4 Do 1 2 3 4 5 6 7
6
2
3
7
5
5
5
6
2
6
8
7 ∞ ∞ ∞ ∞ 6 2 –
So 1 2 3 4 5 6 7
K=1 (tachar la 1 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 – 4 7 5 ∞ ∞ ∞ 1 2 4 – 3 9 5 ∞ ∞ 2 3 7 3 – 1 2 6 ∞ 3 4 5 9 1 – ∞ 8 ∞ 4 5 ∞ 5 2 ∞ – 3 6 5 6 ∞ ∞ 6 8 3 – 2 6 7 ∞ ∞ ∞ ∞ 6 2 – 7
Matriz de secuencia 1 2 3 4 5 6 – 2 3 4 5 6 1 – 3 4 5 6 1 2 – 4 5 6 1 2 3 – 5 6 1 2 3 4 – 6 1 2 3 4 5 – 1 2 3 4 5 6
7 7 7 7 7 7 7 –
1 – 1 1 1 1 1 1
7 7 7 7 7 7 7 –
2 2 – 2 1 2 2 2
3 3 3 – 3 3 3 3
4 4 1 4 – 4 4 4
5 5 5 5 5 – 5 5
6 6 6 6 6 6 – 6
K=2 (tachar la 2 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 – 4 7 5 9 ∞ ∞ 1 2 4 – 3 9 5 ∞ ∞ 2 3 7 3 – 1 2 6 ∞ 3 4 5 9 1 – 14 8 ∞ 4 5 9 5 2 14 – 3 6 5 6 ∞ ∞ 6 8 3 – 2 6 7 ∞ ∞ ∞ ∞ 6 2 – 7
1 – 1 1 1 2 1 1
2 2 – 2 1 2 2 2
3 3 3 – 3 3 3 3
4 4 1 4 – 2 4 4
5 2 5 5 2 – 5 5
6 6 6 6 6 6 – 6
7 7 7 7 7 7 7 –
K=3 (tachar la 3 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 – 4 7 5 9 13 ∞ 1 2 4 – 3 4 5 9 ∞ 2 3 7 3 – 1 2 6 ∞ 3 4 5 4 1 – 3 7 ∞ 4 5 9 5 2 3 – 3 6 5 6 13 9 6 7 3 – 2 6 7 ∞ ∞ ∞ ∞ 6 2 – 7
1 – 1 1 1 2 3 1
2 2 – 2 3 2 3 2
3 3 3 – 3 3 3 3
4 4 3 4 – 3 3 4
5 2 5 5 3 – 5 5
6 3 3 6 3 6 – 6
7 7 7 7 7 7 7 –
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
28
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ K=4 (tachar la 4 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7 1 – 4 6 5 8 12 ∞ 1 – 2 4 4 4 4 7 2 4 – 3 4 5 9 ∞ 2 1 – 3 3 5 3 7 3 6 3 – 1 2 6 ∞ 3 4 2 – 4 5 6 7 4 5 4 1 – 3 7 ∞ 4 1 3 3 – 3 3 7 5 8 5 2 3 – 3 6 5 4 2 3 3 – 6 7 6 12 9 6 7 3 – 2 6 4 3 3 3 5 – 7 7 ∞ ∞ ∞ ∞ 6 2 – 7 1 2 3 4 5 6 –
K=5 (tachar la 5 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 – 4 6 5 8 11 14 1 2 4 – 3 4 5 8 11 2 3 6 3 – 1 2 5 8 3 4 5 4 1 – 3 6 9 4 5 8 5 2 3 – 3 6 5 6 11 8 5 6 3 – 2 6 7 14 11 8 9 6 2 – 7
1 – 1 4 1 4 5 5
2 2 – 2 3 2 5 5
3 4 3 – 3 3 5 5
4 4 3 4 – 3 5 5
5 4 5 5 3 – 5 5
6 5 5 5 5 6 – 6
7 5 5 5 5 7 7 –
K=6 (tachar la 6 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 – 4 6 5 8 11 13 1 2 4 – 3 4 5 8 10 2 3 6 3 – 1 2 5 7 3 4 5 4 1 – 3 6 8 4 5 8 5 2 3 – 3 5 5 6 11 8 5 6 3 – 2 6 7 13 10 7 8 5 2 – 7
1 – 1 4 1 4 5 6
2 2 – 2 3 2 5 6
3 4 3 – 3 3 5 6
4 4 3 4 – 3 5 6
5 4 5 5 3 – 5 6
6 5 5 5 5 6 – 6
7 6 6 6 6 6 7 –
K=7 (tachar la 7 fila y columna) y buscar distancias menores. Do 1 2 3 4 5 6 7 So 1 – 4 6 5 8 11 13 1 2 4 – 3 4 5 8 10 2 3 6 3 – 1 2 5 7 3 4 5 4 1 – 3 6 8 4 5 8 5 2 3 – 3 5 5 6 11 8 5 6 3 – 2 6 7 13 10 7 8 5 2 – 7
1 – 1 4 1 4 5 6
2 2 – 2 3 2 5 6
3 4 3 – 3 3 5 6
4 4 3 4 – 3 5 6
5 4 5 5 3 – 5 6
6 5 5 5 5 6 – 6
7 6 6 6 6 6 7 –
Las distancias mínimas son: Nodo Nodo Ruta Inicial Final 1 2 1-2 1 3 1-4-3 1 4 1-4 1-4-5 1 5 1-4-3-5
Distancia
Nodo Inicial
Nodo Final
4 6 5
1
6
1
7
8
Ruta 1-5-6 1-4-5-6 1-4-3-5-6 1-6-7 1-5-6-7 1-4-5-6-7 1-4-3-5-6-7
Distancia 11
13
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
29
______________________________________________________________________________________________________________________________________ FLUJO MAXIMO
7) Encontrar el flujo máximo y los flujos óptimos en los arcos de la red de la siguiente figura: 0
3
10
10 9 14
1
4 5
2
0
0 4
0
8
2
6 7
6
4
5
8
2
4
0
3 6 2
11
4
5
1 3
2
0
4 9 5
2
11
f5 = {(1,2); (2,5)} = {3, 2} = 2
11
4
5
4
5 5
0
f4 = {(1,5)} = {4} = 4
3
0 9
10
0
1
5
7 2 2
2 2
6 4
10
7
9
14
3
0
4
YA NO HAY CAMINO
9
1
3
4
5
0
5
0
0
0
6
4
0
f3 = {(1,3); (3,2); (2,5)} = {4, 10, 6} = 4
3
6
9
10
5
7
14
6 7
5 0
7
5
6 0
2
0
f2 = {(1,2); (2,4); (4,5)} = {8, 7, 5} = 5
9
5
4
0
4
5
1
10
0
0
10
0 9
14
3
3
4
5
f1 = {(1,3); (3,5)} = {14, 10} = 10
1
5
4
0
0
7
10
6
10
9
0
6 7
10
14
5
0
7
10
3
10
1
5
0
8
0
0
0
4 0
6
1 9
0 7
2
11
4
5 5
7 0 2
10
0
fmax = f1 + f2 + f3 + f4 + f5 = 10 + 5 + 4 + 4 + 2 = 25
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
30
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ Capacidad del arco inicial – Capacidad del Arco Flujo Dirección arco final (1, 2) (8, 0) – (1, 7) = (7, –7) 7 12 (1, 3) (14, 0) – (0, 14) = (14, –14) 14 13 (1, 5) (4, 0) – (0, 4) = (4, –4) 4 15 (2, 3) (5, 10) – (9, 6) = (–4, 4) 4 23 (2, 4) (7, 6) – (2, 11) = (5, –5) 5 24 (2, 5) (6, 0) – (0, 6) = (6, –6) 6 25 (3, 4) (9, 7) – (9, 7) = (0, 0) 0 – (3, 5) (10, 0) – (0, 10) = (10, –10) 10 35 (4, 5) (5, 0) – (0, 5) = (5, –5) 5 45
8) Encontrar el flujo máximo entre los nodos 1 y 5 de la figura: 0
3
5
10
20 10
1
30
0
5
30
0
10 10 30
10
4
0
5 0
10
2
3
5
0
2
0
10
0
10
10
10 30
2
10
4
10
3
4
5
0
1
30 0
10
0
0 10
0 10
f3 = {(1,2); (2,4); (4,3) ; (3,5)} = {10, 30, 20, 10} = 10
0
20
0
10
20 10
5
0
5
0
0
1
0
30
10
10
10
20
10
30
10 30
3
10
0
10
10
10
f2 = {(1,3); (3,4); (4,5)} = {10, 20, 10} = 10
0
1
4
10
f1 = {(1,5)} = {30} = 30 10
10
5 0
0
10 30
0
20
10
2
10
10
1
0
10
10
3
5
0
10
0
0
0
2
10
10 10 20
20
4
5
0
fmax = f1 + f2 + f3 = 30 + 10 + 10 = 50
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
31
______________________________________________________________________________________________________________________________________ 9) Encontrar el flujo máximo entre los nodos 1 y 5 de la figura:
0
3
16
10
15 20
1
0 20
0
20 20
2
0 0
3
16
20
0
20
0
2
4
5
5
1
3
11
20 35
15
0
10
2
4
5
3
11
1
0
10 25
20
10
20
4
4
0
5
0
10
10
15
5 26
3
11
0
6 5
26
5 15
5 16 5
10
f4 = {(1,2); (2,5)} = {10, 16} = 10
20
2
2
10
15
25
0
0
0
0
20
0
5
1
0
5
f3 = {(1,5)} = {20} = 20 15
4
15
10
15
5 26
3
11
20
10
26
5 15
5 16 5
0
f2 = {(1,2); (2,3); (3,5)} = {20, 35, 10} = 10
0
0
16 5
2
0
15
25
0
15
5
1
0 20
f1 = {(1,3); (3,2); (2,4) ; (4,5)} = {20, 16, 20, 15} = 15 15
10
15
0
0
5 11
3
1 0
16 20
15
15
20
20
4
10
15
1
11
5 0
5 16 20
0
0
1
20 0
15
0 25
0 20
2
21
4
0
f5 = {(1,3); (3,4); (4,2) ; (2,5)} = {5, 15, 26, 6} = 5 fmax = f1 + f2 + f3 + f4 + f5 = 15 + 10 + 20 + 10 + 5 = 60 _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
5 15
10 1 10
10
32
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ Capacidad del arco inicial – Capacidad del Arco Flujo Dirección arco final (1, 2) (8, 0) – (1, 7) = (7, –7) 7 12 (1, 3) (14, 0) – (0, 14) = (14, –14) 14 13 (1, 5) (4, 0) – (0, 4) = (4, –4) 4 15 (2, 3) (5, 10) – (9, 6) = (–4, 4) 4 23 (2, 4) (7, 6) – (2, 11) = (5, –5) 5 24 (2, 5) (6, 0) – (0, 6) = (6, –6) 6 25 (3, 4) (9, 7) – (9, 7) = (0, 0) 0 – (3, 5) (10, 0) – (0, 10) = (10, –10) 10 35 (4, 5) (5, 0) – (0, 5) = (5, –5) 5 45
ASIGNACION 10) Resolver el siguiente problema de asignación:
5 5 3 3 9 1
0 2 4 9 8 8
6 3 4 7 7 7
8 0 3 2 8 4
7 6 5 7 4 2
4 7 2 6 5 3
A B C D E F 1 5 0 4 8 7 4 2 5 2 1 0 6 7 3 1 2 0 1 3 0 4 1 7 3 0 5 4 5 5 4 1 4 0 1 6 0 7 4 3 1 2 (# Líneas) 5 ≠ 6 (orden de matriz) K= menor no tachado = 1
1 2 3 4 5 6
A 5 5 3 3 9 1
B 0 2 4 9 8 8
C 6 3 4 7 7 7
D 8 0 3 2 8 4
E 7 6 5 7 4 2
F 4 7 2 6 5 3
0 0 2 2 4 1
A B C D E F 1 6 0 4 9 7 4 2 5 1 0 0 5 6 3 2 2 0 2 3 0 4 1 6 2 0 4 3 5 6 4 1 5 0 1 6 0 6 3 3 0 1 (# Líneas) 6 = 6 (orden de matriz) Asignar
1 2 3 4 5 6
1 2 3 4 5 6
A 5 5 1 1 5 0 0
B 0 2 2 7 4 7 0
C 6 3 2 5 3 6 2
D 8 0 1 0 4 3 0
E 7 6 3 5 0 1 0
F 4 7 0 4 1 2 0
A 6 5 2 1 6 0
B 0 1 2 6 4 6
C 4 0 0 2 1 3
D 9 0 2 0 5 3
E 7 5 3 4 0 0
F 4 6 0 3 1 1
X1B=1; X2C=1; X3F=1; X4D=1; X5E=1; X6A=1 Zoptimo = 0 + 3 + 2 + 2 + 4 + 1 = 12 11) un centro de enseñanza desea contratar profesores para las asignaturas de Algebra, Calculo, Física, Química y Programación. Se presentan 5 postulantes, cada uno de los cuales podrá acceder solamente a una asignatura. No todos los profesores pueden dictar todas las asignaturas. La siguiente tabla muestra las materias que puede dictar cada uno y la remuneración solicitada en Bs/hr. Sin embargo el centro tiene la política de pagar solamente Bs. 30/hr. A cualquier docente de las materias de Algebra y Calculo. Determine un programa de asignación optimo y el gasto total/hr, para el centro de enseñanza. Profesor Materias que puede dictar Remuneración Profesor 1 Algebra, Física 40 Profesor 2 Calculo, Física, Química 45 Profesor 3 Calculo, Programación 60 Profesor 4 Algebra, Calculo, Física 50 Profesor 5 Física, Química 35 _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
33
______________________________________________________________________________________________________________________________________ Solución Al Ca Fi Qu Pr Al Ca Fi Qu Pr P1 0 – 5 – – Al Ca Fi Qu Pr P1 40 – 40 – – P2 – 0 10 10 – P1 0 – 5 – – 0 P2 – 45 45 45 – P3 – 15 – – 0 P2 – 0 10 10 – 0 P3 – 60 – – 60 P4 5 0 10 – – P3 – 15 – – 0 0 P4 50 50 50 – – P5 – – 0 0 – P4 10 5 15 – – 5 P5 – – 35 35 – (# Líneas) 4 ≠ 5 (orden de matriz) P5 – – 0 0 – 0 40 45 35 35 60 K= menor no tachado = 5
Al Ca Fi Qu Pr P1 0 – 5 – – P2 – 0 5 5 – P3 – 15 – – 0 P4 0 0 5 – – P5 – – 0 0 – (# Líneas) 4 ≠ 5 (orden de matriz) K= menor no tachado = 5
Al Ca Fi Qu Pr P1 0 – 0 – – P2 – 0 0 0 – P3 – 15 – – 0 P4 0 0 0 – – P5 – – 0 0 – (# Líneas) 4 ≠ 5 (orden de matriz) Asignar
Al 0 – – 0 –
P1 P2 P3 P4 P5
Ca – 0 15 0 –
Fi 0 0 – 0 0
Qu – 0 – – 0
Pr – – 0 – –
XP1-Fi=1; XP2-Ca=1; XP3-Pr=1; XP4-Al=1; XP5-Qu=1 Zoptimo = 40 + 45 + 60 + 50 + 35 = 230 Pero como el centro tiene la política de solo pagar 30 Bs/hr. A las materias de Algebra y Calculo. Zoptimo = 40 + 30 + 60 + 30 + 35 = 195 TRANSPORTE 12) Armar la tabla de transporte a partir de la siguiente red: 100
1
3
1 4
1
3
6
5
5
1
8
6
150
3
2
ORIGENES
Solución: Orígenes: 1, 2, 3, 4, 5 Destinos: 3, 4, 5, 6 Nodos de Transbordo: 3, 4, 5 Nodos de Oferta Pura: 1, 2 Nodos de Demanda Pura: 6 Uno 3 4 5 1 1 4 M 2 3 2 M 3 0 3 6 4 1 0 5 5 M M 0 Dem 150+ θ θ θ
4
2
150
Dos 6 M M M 8 1 150
Oferta 100 200 θ θ θ
ORIGENES
100
1 2 3 4 5 Dem
3 1 3 0 1 M 300
4 4 2 3 0 M 300
5 M M 6 5 0 450
6 M M M 8 1 150
Oferta 100 200 300 300 300
(θ=100+200=150+150) (θ=300=300) (θ=300) _____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
34
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ Solución Inicial Voguel: 3 4 5 6 100 1 100 1 4 M M 200 2 200 3 2 M M 200 100 3 300 0 3 6 M 100 200 4 300 1 0 5 8 150 150 5 300 M M 0 1 300 300 450 150
Para todas las VB ui v j cij U1 + V 3 = 1 U2 + V 4 = 2 U3 + V 3 = 0 U3 + V 4 = 6 U4 + V 4 = 0 U4 + V 5 = 5 U5 + V 5 = 0 U5 + V 6 = 1
U1 = 0 U2 = 0 U3 = –1 U4 = –2 U5 = –7
V3 = 1 V4 = 2 V5 = 7 V6 = 8
Para todas las VNB MIN cij ui v j cij C14 = (0+2) – 4 = –2 C15 = (0+7) – M = 7–M C16 = (0+8) – M = 8–M C23 = (0+1) – 3 = –2 C25 = (0+7) – M = 7–M C26 = (0+8) – M = 8–M
C34 = (–1+2) – 3 = –2 C36 = (–1+8) – M = 7–M C43 = (–2+1) – 1 = –2 C46 = (–2+8) – 8 = –2 C53 = (–7+1) – M = –6–M C54 = (–7+2) – M = –5–M
Como todas las VNB son negativas el tablero es óptimo y factible. Z = (1*100) + (2*200) + (0*200) + (6*100) + (0*100) + (5*200) + (0*150) + (1*150) Z = 2250 [u.m.] 2) Una empresa de producción tiene 4 plantas desde las cuales debe distribuir sus productos a 3 centros de distribución, los costos de envió son los que se muestran en la siguiente tabla. Determine cual seria la mejor forma de transportar los productos. (Para la solución utilizar el método de Vogel y la optimización por variables duales). C. Distr. 1 C. Distr. 2 C. Distr. 3 Ofertas Planta 1 5 1 0 20 Planta 2 2 2 4 10 Planta 3 7 5 2 15 Planta 4 9 6 0 15 Demandas 25 10 15 Solución 1 2 3 4 10 10 0 1 20 5 1 0 0 10 2 10 2 2 4 0 5 10 3 15 7 5 2 0 15 4 15 9 6 0 0 25 10 15 10
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
35
______________________________________________________________________________________________________________________________________
Para todas las VB ui v j cij 0 U1 + V 1 – 5 = 0 U1 + V 2 – 1 = 0 U1 + V 3 – 0 = 0 U2 + V 1 – 2 = 0 U3 + V 1 – 7 = 0 U3 + V 4 – 0 = 0 U4 + V 3 – 0 = 0
Para todas las VNB MIN zij c ij ui v j c ij
U1 = 0 U2 = –3 U3 = 2 U4 = 0
V1 = 5 V2 = 1 V3 = 0 V4 = –2
Z14–C14= U1 + V4 – C14 = (0–2) – 0 = –2 Z22–C22= U2 + V2 – C22 = (–3+1) – 2 = –4 Z23–C23= U2 + V3 – C23 = (–3+0) – 4 = –7 Z24–C24= U2 + V4 – C24 = (–3–2) – 0 = –5 Z33–C33= U3 + V3 – C33 = (2+0) – 5 = –3 Z34–C34= U3 + V4 – C34 = (2–2) – 2 = –2 Z41–C41= U4 + V1 – C41 = (0+5) – 9 = –4 Z42–C42= U4 + V2 – C42 = (0+1) – 6 = –5 Z44–C44= U4 + V4 – C44 = (0–2) – 0 = –2 Como todas las VNB son negativas el tablero es óptimo y factible. Z = (5*10) + (1*10) + (0*0) + (2*10) + (7*5) + (0*10) + (0*15) Z = 115 [u.m.]
EXAMENES RESUELTOS FINAL 1) Resolver el siguiente problema de transbordo:
E
10
100
4 100
A
5
C 6
3
2
10 120
B
F
50
G
100
10 8
D
Orígenes: A, B, C, D Destinos: C, D, E, F, G Nodos de Transbordo: C, D Nodos de Oferta Pura: A, B Nodos de Demanda Pura: E, F, G
4 6
Solución: E F G Oferta C D E F 10 M M 100 A 5 3 10 M M M 6 120 B 10 8 M M 4 6 M C 0 2 4 6 θ M 10 4 D M 0 M 10 θ 0 0 0 30 Y 0 0 0 0 100 50 100 Dem 250 250 100 50 (θ=100+120+30=100+50+100) (θ=250=250) (θ=250) a) Encontrar una solución Inicial (Voguel). C D E F G 100 0 A 100 5 3 10 M M 20 100 B 120 10 8 M M 6 150 100 C 250 0 2 4 6 M 230 20 D 250 M 0 M 10 4 30 Y 30 0 0 0 0 0 250 250 100 50 100 A B C D Y Dem
C 5 10 0 M 0 θ
D 3 8 2 0 0 θ
G M 6 M 4 0 100
Oferta 100 120 250 250 30
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
36
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________ b) Encontrar la solución optima.
Para todas las VB ui v j cij U1 + V 1 = 5 U1 + V 2 = 3 U2 + V 2 = 8 U2 + V 5 = 6 U3 + V 1 = 0 U3 + V 3 = 4 U4 + V 2 = 0 U4 + V4 = 10 U5 + V 4 = 0
A B C D Y
U1 = 0 U2 = 5 U3 = –5 U4 = –3 U5 = –13
Para todas las VNB MIN cij ui v j cij
V1 = 5 V2 = 3 V3 = 9 V4 = 13 V5 = 1
C 100+θ
D 0–θ
5
3
10
8
E
C35 = (–5+1) – M = –4–M C41 = (–3+5) – M = 2–M C43 = (–3+9) – M = 6–M C45 = (–3+1) – 4 = –6 C51 = (–13+5) – 0 = –8 C52 = (–13+3) – 0 = –10 C53 = (–13+9) – 0 = –4 C55 = (–13+1) – 0 = –12
F
G
10
M
M
M
M
6
100
20
100 100
150–θ 0
2
M 0
θ
4
6
0
M
10
0
0
0
20–θ
250
4 30
C A B C D Y
30
0
250 100 50 θ = MIN {VB (–θ)} = {20, 0, 150} = 0 D E F
100 G
100 5
3
10
10
M
M
8
M
M
6
0
2
4
6
M
0
M
10
0
0
0
0
20
100 100
150
100
0
230
250
20
Para todas las VB ui v j cij U1 = 0 U2 = 7 U3 = –5 U4 = –1 U5 = –11
V1 = 5 V2 = 1 V3 = 9 V4 = 11 V5 = –1
100
250
4
30
0 50
120 250
M
30 250
120 250
M
230+θ
250
U1 + V 1 = 5 U2 + V 2 = 8 U2 + V 5 = 6 U3 + V 1 = 0 U3 + V 3 = 4 U3 + V 4 = 6 U4 + V 2 = 0 U4 + V4 = 10 U5 + V 4 = 0
C13 = (0+9) – 10 = –1 C14 = (0+13) – M = 13–M C15 = (0+1) – M = 1–M C21 = (5+5) – 10 = 0 C23 = (5+9) – M = 14–M C24 = (5+13) – M = 18–M C32 = (–5+3) – 2 = –4 C34 = (–5+13) – 6 = 2
100
Para todas las VNB MIN cij ui v j cij C12 = (0+1) – 3 = –2 C13 = (0+9) – 10 = –1 C14 = (0+11) – M = 11–M C15 = (0–1) – M = –1–M C21 = (7+5) – 10 = 2 C23 = (7+9) – M = 16–M C24 = (7+11) – M = 18–M C32 = (–5+1) – 2 = –6
C35 = (–5–1) – M = –6–M C41 = (–1+5) – M = 4–M C43 = (–1+9) – M = 8–M C45 = (–1–1) – 4 = –6 C51 = (–11+5) – 0 = –6 C52 = (–11+1) – 0 = –10 C53 = (–11+9) – 0 = –2 C55 = (–11–1) – 0 = –13
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
Investigación Operativa I SIS-2209
37
______________________________________________________________________________________________________________________________________ C D E F G 100 A 100 5 3 10 M M 100 20–θ θ B 120 10 8 M M 6 100 150–θ 0+θ C 250 0 2 4 6 M 230+θ 20–θ D 250 M 0 M 10 4 30 Y 30 0 0 0 0 0 250 250 100 50 100 θ = MIN {VB (–θ)} = {20, 20, 150} = 20 C D E F G 100 A 100 5 3 10 M M 20 100 B 120 10 8 M M 6 130 100 20 C 250 0 2 4 6 M 250 0 D 250 M 0 M 10 4 30 Y 30 0 0 0 0 0 250 250 100 50 100
Para todas las VB ui v j cij
Para todas las VNB MIN cij ui v j cij
U1 + V 1 = 5 U1 = 0 V1 = 5 C12 = (0+1) – 3 = –2 C35 = (–5+1) – M = –4–M U2 + V1 = 10 U2 = 5 V2 = 1 C13 = (0+9) – 10 = –1 C41 = (–1+5) – M = 4–M U2 + V 5 = 6 U3 = –5 V3 = 9 C14 = (0+11) – M = 11–M C43 = (–1+9) – M = 8–M U3 + V 1 = 0 U4 = –1 V4 = 11 C15 = (0+1) – M = 1–M C45 = (–1+1) – 4 = –4 U3 + V 3 = 4 U5 = –11 V5 = 1 C22 = (5+1) – 8 = –2 C51 = (–11+5) – 0 = –6 U3 + V 4 = 6 C23 = (5+9) – M = 14–M C52 = (–11+1) – 0 = –10 U4 + V 2 = 0 C24 = (5+11) – M = 16–M C53 = (–11+9) – 0 = –2 U4 + V4 = 10 C32 = (–5+1) – 2 = –6 C55 = (–11+1) – 0 = –10 U5 + V 4 = 0 Como todas las VNB son negativas el tablero es óptimo y factible. Z = (5*100) + (10*20) + (6*100) + (0*130) + (4*100) + (6*20) + (0*250) + (10*0) + (0*30) Z = 1820 [u.m.] c) Que destinos no son satisfechos o son satisfechos parcialmente? Los destinos E y G son satisfechos completamente. El destino F es satisfecho parcialmente solo con 20 unidades. d) Para realizar una asignación completa suponga que la demanda en el destino F es 20. ¿La solución anterior es óptima con este cambio?
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino
38
Investigación Operativa I SIS-2209
______________________________________________________________________________________________________________________________________
E
10
100
4
A
100
5
C 6
3
2
10
B
120
F
20
G
100
10 8
D
Orígenes: A, B, C, D Destinos: C, D, E, F, G Nodos de Transbordo: C, D Nodos de Oferta Pura: A, B Nodos de Demanda Pura: E, F, G
4 6
Solución: E F G Oferta C D E 10 M M 100 A 5 3 10 M M 6 120 B 10 8 M 4 6 M C 0 2 4 θ M 10 4 D M 0 M θ 100 20 100 Dem 220 220 100 (θ=100+120=100+20+100) (θ=220=220) (θ=220) Solución Inicial (Voguel). C D E F G 100+θ 0–θ A 5 3 10 M M 20 100 B 10 8 M M 6 100 120–θ θ C 0 2 4 6 M 200+ θ 20–θ D M 0 M 10 4 220 220 100 20 100 A B C D Dem
C 5 10 0 M θ
D 3 8 2 0 θ
F M M 6 10 20
G M 6 M 4 100
Oferta 100 120 220 220
100 120 220 220
Encontrar la solución optima. Para todas las VB ui v j cij U1 + V 1 = 5 U1 + V 2 = 3 U2 + V 2 = 8 U2 + V 5 = 6 U3 + V 1 = 0 U3 + V 3 = 4 U4 + V 2 = 0 U4 + V4 = 10
U1 = 0 U2 = 5 U3 = –5 U4 = –3
V1 = 5 V2 = 3 V3 = 9 V4 = 13 V5 = 1
Para todas las VNB MIN cij ui v j cij C13 = (0+9) – 10 = –1 C14 = (0+13) – M = 13–M C15 = (0+1) – M = 1–M C21 = (5+5) – 10 = 0 C23 = (5+9) – M = 14–M C24 = (5+13) – M = 18–M
C32 = (–5+3) – 2 = –4 C34 = (–5+13) – 6 = 2 C35 = (–5+1) – M = –4–M C41 = (–3+5) – M = 2–M C43 = (–3+9) – M = 6–M C45 = (–3+1) – 4 = –6
_____________________________________________________________________________________________________________________
Aux. Fernando Cortez Hino