Parciales Resueltos IngEscalante-1

Investigación Operativa I SIS-2209 1 _________________________________________________________________________________

Views 64 Downloads 0 File size 2MB

Report DMCA / Copyright

DOWNLOAD FILE

Recommend stories

Citation preview

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 - 100x 1  200 - 80 - 60 - 50x 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 - 10x 1  150 - 50 - 5 x 2  400 - 100 - 20x 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 12 (1, 3) (14, 0) – (0, 14) = (14, –14) 14 13 (1, 5) (4, 0) – (0, 4) = (4, –4) 4 15 (2, 3) (5, 10) – (9, 6) = (–4, 4) 4 23 (2, 4) (7, 6) – (2, 11) = (5, –5) 5 24 (2, 5) (6, 0) – (0, 6) = (6, –6) 6 25 (3, 4) (9, 7) – (9, 7) = (0, 0) 0 – (3, 5) (10, 0) – (0, 10) = (10, –10) 10 35 (4, 5) (5, 0) – (0, 5) = (5, –5) 5 45

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 12 (1, 3) (14, 0) – (0, 14) = (14, –14) 14 13 (1, 5) (4, 0) – (0, 4) = (4, –4) 4 15 (2, 3) (5, 10) – (9, 6) = (–4, 4) 4 23 (2, 4) (7, 6) – (2, 11) = (5, –5) 5 24 (2, 5) (6, 0) – (0, 6) = (6, –6) 6 25 (3, 4) (9, 7) – (9, 7) = (0, 0) 0 – (3, 5) (10, 0) – (0, 10) = (10, –10) 10 35 (4, 5) (5, 0) – (0, 5) = (5, –5) 5 45

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