Parciales Resueltos IngEscalante-1

Investigación Operativa I SIS-2209 ______________________________________________________________________________________________________________________________________

_____________________________________________________________________________________________________________________ Aux. Fernando Cortez Hino

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.

321 6x7x9xZ MAX

Identificar restricciones.

1800.5x1x1x 321 Capacidad del Cepillado (horas)

2801x1x1x 321 Capacidad del Fresado (horas)

3001x1x0.5x 321 Capacidad del Taladrado (horas)

6003x2x1x 321 Capacidad del Ensamble (horas)

60x1 Requerimiento mínimo del producto A

50x2 Requerimiento mínimo del producto B

40x3 Requerimiento mínimo del producto C

Identificar restricciones de no negatividad.

0x,x,x 321

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


X1 = número de sillas producidos

X2 = número de marcos producidos


21 x50-60-80-200x100-30-80-300Z MAX 21 10x90xZ MAX


364x4x 21 Disponibilidad de la Madera (listones)



2

486x3x 21 Disponibilidad de las horas de mano de obra

705x10x 21 Disponibilidad de las horas de la cepilladora


0x,x 21

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

Nutritivo

Kilogramo

de Maíz

Kilogramo

de Residuos de grasa

Kilogramo

de Alfalfa

Requerimiento

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


X1 = cantidad de kilogramos de maíz

X2 = cantidad de kilogramos de residuos de grasa

X3 = cantidad de kilogramos de alfalfa


321 15x18x21xZ MIN


20040x20x90x 321 Requerimiento de Carbohidratos

18060x80x30x 321 Requerimiento de Proteínas

15060x20x10x 321 Requerimiento de Vitaminas


0x,x,x 321

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.



3

Petróleo Gasolina Kerosén Combustible para

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


X1 = número de petróleo crudo ligero comprado

X2 = número de petróleo crudo pesado comprado


21 9x11xZ MIN


10000000.40x0.40x 21 Demanda de la Gasolina

4000000.40x0.20x 21 Demanda del Kerosén

2500000.20x0.40x 21 Demanda del Combustible para reactores


0x,x 21

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


X1 = cantidad de sacos que confecciona el sastre

X2 = cantidad de pantalones que confecciona el sastre

X3 = cantidad de abrigos que confecciona el sastre


321 x20-100-400x5-50-150x10-100-300Z MAX

321 280x95x190xZ MAX


4001x2x 21 Disponibilidad del Casimir (m2)

1002.5x3 Disponibilidad del Paño (m2)

4002x1/2x1x 321 Disponibilidad de la Tela para Forros (m2)

121/9x1/45x1/15x 321 Rendimiento de los 3 trabajadores (semanas)

101/9x3 Demanda de los abrigos.


0x,x,x 321



4

PROBLEMA DE LOS METODOS DE SOLUCION

1)

Considere el siguiente PL:

MAX Z = 2X1 + 3X2 + 1X3

s.a.

X1 + 2X2 + 3X3 ≤ 18

2X1 + 3X2 + 2X3 ≤ 30

2X1 + 2X2 + 1X3 ≤ 36

X1, X2, X3 ≥ 0

MAX Z = 2X1 + 3X2 + 1X3

s.a.

X1 + 2X2 + 3X3 + X4 = 18

2X1 + 3X2 + 2X3 + X5 = 30

2X1 + 2X2 + 1X3 + X6 = 36

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 1B

(Gauss-Jordan)

122

023

012

B

12-2

023-

01-2

B 1

Segundo se calcula las columnas de las VNB en el reglón 1, 2 y 3.

3

5

4

1

2

3

12-2

023-

01-2

aB 31

2

3

2

0

0

1

12-2

023-

01-2

aB 41

2-

2

1-

0

1

0

12-2

023-

01-2

aB 51

Tercero se calcula los coeficientes de las VNB en el reglón 0 (función objetivo).

1121

3

5

4

0231

1

2

3

12-2

023-

01-2

023CaBCC 331

B3

_

0000

2

3

2

0230

0

0

1

12-2

023-

01-2

023CaBCC 441

B4

_

1010

2-

2

1-

0230

0

1

0

12-2

023-

01-2

023CaBCC 551

B5

_

Cuarto se calcula el lado derecho del tablero optimo.

12

6

6

36

30

18

12-2

023-

01-2

bB 1

Quinto se calcula el lado derecho del reglón 0 (función objetivo).

30

12

6

6

023

36

30

18

12-2

023-

01-2

023bBC 1B



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 X1 X2 X3 X4 X5 X6 b

X2 0 1 4 2 -1 0 6

X1 1 0 -5 -3 2 0 6

X6 0 0 3 2 -2 1 12

Zj-Cj 0 0 1 0 1 0 30

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

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

Sea: X4, X5 y X6 las variables de holgura para las restricciones respectivas. Luego de aplicar el procedimiento del

simplex se llega a la tabla final siguiente.

XB X1 X2 X3 X4 X5 X6 b

X2 5 1 0 1 3 0 14

X6 2 0 0 0 1 1 5

X3 4 0 1 1 2 0 11

Zj-Cj 2 0 0 1 1 0 8

Solución

Primero se calcula 1B

(Gauss-Jordan)

021

110

031

B 1

Segundo se calcula las columnas de las VNB en el reglón 1.

4

2

5

1

1

2

021

110

031

aB 11

Tercero se calcula los coeficientes de las VNB en el reglón 0 (función objetivo).

2131

4

2

5

201-1

1

1

2

021

110

031

201-CaBCC 111

B1

_

Cuarto se calcula el lado derecho del tablero optimo.

11

5

14

2

3

5

021

110

031

bB 1



6

Quinto se calcula el lado derecho del reglón 0 (función objetivo).

8

11

5

14

201-

2

3

5

021

110

031

201-bBC 1B

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

15

15X1

R1

R2

O

A

B

10

5

X2

Puntos Criticos:

Z(A) = Z(15 ; 0) = 30 MIN

Z(B) = Z(0 ; 15) = 45

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



7

6)

A partir del Tablero siguiente obtenido en el transcurso de la resolución de un Pl de variables de decisión (no-

negativas) X1, X2, X3 y 2 restricciones de desigualdad. En el cual fueron incluidas 2 variables de holgura no-

negativas (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 1 3 c

X1 1 -1 3 0 -5 3

Zj-Cj 0 a b 0 4 82

i) La solución básica es una Solución Básica Factible (BF).

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

s.a.

X1 + 2X2 + 3X3 ≤ 18

2X1 + 3X2 + 2X3 ≤ 27

2X1 + 2X2 + 1X3 ≤ 54

X1, X2, X3 ≥ 0

MAX Z = 3X1 + 4X2 + 3X3

s.a.

X1 + 2X2 + 3X3 +s1 = 18

2X1 + 3X2 + 2X3 +s2 = 27

2X1 + 2X2 + 1X3 +s3 = 54

X1, X2, X3, s1, s2, s3 ≥ 0

Solución

1° X1 X2 X3 S1 S2 S3 b

S1 1 2 3 1 0 0 18

S2 2 3 2 0 1 0 27

S3 2 2 1 0 0 1 54

Zj-Cj -3 -4 -3 0 0 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 S3 b

X2 1/2 1 3/2 1/2 0 0 9

S2 1/2 0 -5/2 -3/2 1 0 0

S3 1 0 -2 -1 0 1 36

Zj-Cj -1 0 3 2 0 0 36


Sale Min {9/1/2; 0/1/2; 36/1} = {S2}

3° X1 X2 X3 S1 S2 S3 b

X2 0 1 4 2 -1 0 9

X1 1 0 -5 -3 2 0 0

S3 0 0 3 2 -2 1 36

Zj-Cj 0 0 -2 -1 2 0 36


Sale Min {9/4; 0/-5; 36/3} = {X2}

4° X1 X2 X3 S1 S2 S3 b

X3 0 1/4 1 1/2 -1/4 0 9/4

X1 1 5/4 0 -1/2 3/4 0 45/4

S3 0 -3/4 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



8

6)

Resolver el siguiente PL

MAX Z = 2X1 + 1X2

s.a.

–X1 + X2 ≤ 1

X1 – 2X2 ≤ 2

X1, X2 ≥ 0

MAX Z = 2X1 + 1X2

s.a.

–X1 + X2 +s1 = 1

X1 – 2X2 +s2 = 2

X1, X2, s1, s2 ≥ 0

Solución

1° X1 X2 S1 S2 b

S1 -1 1 1 0 1

S2 1 -2 0 1 2

Zj-Cj -2 -1 0 0 0


Sale Min {1/-1; 2/1} = {S2}

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


No existe un vector de salida por lo tanto es no acotado.

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

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

1° X1 X2 X3 X4 S1 S2 S3 b

S1 1 7 3 7 1 0 0 46

S2 3 -1 1 2 0 1 0 8

S3 2 3 -1 1 0 0 1 10

Zj-Cj -2 -1 3 -5 0 0 0 0


Sale Min {46/7; 8/2; 10/1} = {S2}

2° X1 X2 X3 X4 S1 S2 S3 b

S1 -19/2 21/2 -1/2 0 1 -7/2 0 18

X4 3/2 -1/2 1/2 1 0 1/2 0 4

S3 ½ 7/2 -3/2 0 0 -1/2 1 6

Zj-Cj 11/2 -7/2 11/2 0 0 5/2 0 20

Entra el más negativo de Zj-Cj (-7/2)

Sale Min {18/21/2; 4/-1/2; 6/7/2} = {S1}

3° X1 X2 X3 X4 S1 S2 S3 b

X2 -19/21 1 -1/21 0 2/21 -1/3 0 12/7

X4 22/21 0 10/21 1 1/21 1/3 0 34/7

S3 11/3 0 -4/3 0 -1/3 2/3 1 0

Zj-Cj 7/3 0 16/3 0 1/3 4/3 0 26

Solución: Z=26; X1=0; X2=12/7; X3=0; X4=34/7



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]

Maquina Parte 1 Parte 2 Parte 3 Parte 4 Capacidad

(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 b

X5 3 1/3 0 4/3 1 0 -2/3 400

X6 1/2 3 0 2 0 1 -1/2 600

X3 1/2 2/3 1 2/3 0 0 1/6 200

Zj-Cj 2 2/3 0 8/3 0 0 5/3 2000

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 los casos respecto a la solución

del problema inicial indicado.

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

01200

1200

6100

21-10

32-01

b1

B

Δ

0Δ61

0Δ21-1200

0Δ32-1200

0

2400

1800

Δ

Δ

Δ

El rango de factibilidad para el recurso que se consume completamente es: 1800Δ0

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.



10

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

0

1200

1200

6100

21-10

32-01

b1

B

Δ

0200

0600-Δ

0800-1200

600Δ

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

0665VNBj

C

1000VBBC

7X4X2X1X

3X6X5X

1443

0452

0435

ja Son las VNB de las restricciones.

7X4X2X1X353232006653532032050665

1443

0452

0435

6100

21-10

32-01

1000j

Cj

a1

BBC

El tablero óptimo es:


X5 3 1/3 0 4/3 1 0 -2/3 400

X6 1/2 3 0 2 0 1 -1/2 600

X3 1/2 2/3 1 2/3 0 0 1/6 200

Zj-Cj 0 2/3 0 2/3 0 0 5/3 2000

Solución alternativa


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



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

400

0

400-

2400

1200

1200

6100

21-10

32-01

b1

BBX 4000

2400

1200

1200

6100

21-10

32-01

1000b1

BBC



X5 3 1/3 0 4/3 1 0 -2/3 -400

X6 1/2 3 0 2 0 1 -1/2 0

X3 1/2 2/3 1 2/3 0 0 1/6 400

Zj-Cj 2 2/3 0 8/3 0 0 5/3 4000


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 A1 A2 A3 A4 A5 A6 A7 A8 b

X5 3 1/3 0 4/3 1 0 -2/3 0 400

X6 1/2 3 0 2 0 1 -1/2 0 600

X3 1/2 2/3 1 2/3 0 0 1/6 0 200

X8 0 0 1 0 0 0 0 1 100

Zj-Cj 2 2/3 0 8/3 0 0 5/3 0 2000

X3 no es vector unitario en forma de columna por lo tanto debemos transformarlo.

Xi A1 A2 A3 A4 A5 A6 A7 A8 b

X5 3 1/3 0 4/3 1 0 -2/3 0 400

X6 1/2 3 0 2 0 1 -1/2 0 600

X3 1/2 2/3 1 2/3 0 0 1/6 0 200

X8 -1/2 -2/3 0 -2/3 0 0 -1/6 1 -100

Zj-Cj 2 2/3 0 8/3 0 0 5/3 0 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



12

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]

Maquina Parte 1 Parte 2 Parte 3 Parte 4 Capacidad

(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 b

X5 1/2 3 0 2 1 -1/2 600

X3 1/2 2/3 1 2/3 0 1/6 200

Zj-Cj 2 2/3 0 8/3 0 5/3 2000

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) 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).



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.

3

4a2

21

25

3

4

610

2112a

1B

-16-563

461006

3

4

610

2111002C2a

1BBC


X5 1/2 3 0 2 1 -1/2 600

X3 1/2 2/3 1 2/3 0 1/6 200

Zj-Cj 2 -1 0 8/3 0 5/3 2000


X2 1/5 1 0 4/5 2/5 -1/5 240

X3 2/5 0 1 4/15 -1/5 4/15 80

Zj-Cj 11/5 0 0 52/15 2/5 22/15 2240

Z = 2240; X1 = 0; X2 = 240; X3 = 80; X4 = 0; X5 = 0; X6 = 0

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

01200610

211b

1B

0200

0600-

Δ 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.

01200

610

211b

1B

061

021-1200

Δ

Δ

0

2400

Δ

Δ

El rango de factibilidad para el segundo recurso del taladro es: 24000 Δ

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 b2=2400.

2400

6000b

400

4800

2400

6000

610

211b

1B 4000

2400

6000

610

211100b

1BBC



X5 1/2 3 0 2 1 -1/2 4800

X3 1/2 2/3 1 2/3 0 1/6 400

Zj-Cj 2 2/3 0 8/3 0 5/3 4000

Z = 4000; X1 = 0; X2 = 0; X3 = 400; X4 = 0; X5 = 4800; X6 = 0

f) Cuanto debe ser el coeficiente mínimo (c1) para que la fabricación de la parte 1 produzca una solución optima?

0463VNBj

C

100VBBC

6X4X2X1X

3X5X

1443

0452




14

0353832Δ-5046Δ353203205046Δ1443

0452

610

21-1100

jC

ja

1BBC

6X4X2X1X

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

01200610

211b

1B

0200

0600-

Δ 600Δ

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

Recurso Bolso Mochila Estuche Disponibilidad

Diaria

Cuero (pies2) 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:


X4 2 1 3 1 0 0 42

X5 2 1 2 0 1 0 40

X6 1 1 1 0 0 1 45

Zj-Cj -24 -22 -45 0 0 0 0

Primera iteración:


X3 2/3 1/3 1 1/3 0 0 14

X5 2/3 1/3 0 -2/3 1 0 12

X6 1/3 2/3 0 -1/3 0 1 31

Zj-Cj 6 -7 0 15 0 0 630

Tablero optimo final:



15


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

10

30

5

45

40

45

2-1

32-

1-1

b1

B

1

0

0 885

45

40

45

2-1

32-

1-1

02245b1

BBC

1

0

0



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

12

36

2

50

40

42

2-1

32-

1-1

b1

B

1

0

0 882

50

40

42

2-1

32-

1-1

02245b1

BBC

1

0

0



X3 0 0 1 1 -1 0 2

X2 2 1 0 -2 3 0 36

X6 -1 0 0 1 -2 1 12

Zj-Cj 20 0 0 1 21 0 882

Z = 882; X1 = 0; X2 = 36; X3 = 2; X4 = 0; X5 = 0; X6 = 12

d) ¿Recomendaría la contratación de un trabajador adicional de costura a 15 Bs. la hora?.

Solución

5

39

1

45

41

42

2-1

32-

1-1

b1

B

1

0

0

903

45

41

42

2-1

32-

1-1

02245b1

BBC

1

0

0



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.)



16

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

s.a.

X1 + 2X2 + 3X3 ≤ 18

2X1 + 3X2 + 2X3 ≤ 30

2X1 + 2X2 + X3 ≤ 36

X1, X2, X3 ≥ 0

Xi A1 A2 A3 A4 A5 A6 b

X2 0 1 4 2 -1 0 6

X1 1 0 -5 -3 2 0 6

X6 0 0 3 2 -2 1 12

Zj-Cj 0 0 1 0 1 0 30

a) Resuelva el problema si (c1, c2, c3) cambia a: (4, 3, 1)

Solución

MAX Z = 4X1 + 3X2 + X3

001VNBj

C

043VBBC

5X4X3X

6X1X2X

001

102

013


5X4X3X

56-9-00156-8-001

001

102

013

12-2

23-

1-2

043j

Cj

a1

BBC 0

0

42

36

30

18

056-

36

30

18

12-2

23-

1-2

043b1

BBC 0

0



X2 0 1 4 2 -1 0 6

X1 1 0 -5 -3 2 0 6

X6 0 0 3 2 -2 1 12

Zj-Cj 0 0 -9 -6 5 0 42


X3 0 1/4 1 1/2 -1/4 0 3/2

X1 1 5/4 0 -1/2 3/4 0 27/2

X6 0 -3/4 0 1/2 -5/4 1 15/2

Zj-Cj 0 9/4 0 -3/2 11/4 0 111/2


X4 0 1/2 2 1 -1/2 0 3

X1 1 3/2 1 0 1/2 0 15

X6 0 -1 -1 0 -1 1 6

Zj-Cj 0 3 3 0 2 0 60

Z = 60; X1 = 15; X2 = 0; X3 = 0; X4 = 3; X5 = 0; X6 = 6

b) Resuelva el problema con la nueva restricción 2X2 + X3 ≤ 20



17

Solución

Restricción Estandarizada: 2X2 + X3 + X7 = 20


X2 0 1 4 2 -1 0 0 6

X1 1 0 -5 -3 2 0 0 6

X6 0 0 3 2 -2 1 0 12

X7 0 2 1 0 0 0 1 20

Zj-Cj 0 0 1 0 1 0 0 30

X2 no es vector unitario en forma de columna por lo tanto debemos transformarlo.


X2 0 1 4 2 -1 0 0 6

X1 1 0 -5 -3 2 0 0 6

X6 0 0 3 2 -2 1 0 12

X7 0 0 -7 -4 2 0 1 8

Zj-Cj 0 0 1 0 1 0 0 30

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 A1 A2 A3 A4 A5 b

X1 1 5 2 1 0 30

X5 0 -10 -8 -1 1 10

Zj-Cj 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

0305VNBj

C

05VBBC

4X3X2X

5X1X

065

125


4X3X2XM520-20M-30551025M-305

065

125

11

0105

jC

ja

1BBC

15010

3005

40

30

11

0105b

1BBC


XB A1 A2 A3 A4 A5 b

X1 1 5 2 1 0 30

X5 0 -10 -8 -1 1 10

Zj-Cj 0 20 -20 5+M 0 150

XB A1 A2 A3 A4 A5 b

X3 1/2 5/2 1 1/2 0 15

X5 4 10 0 3 1 130

Zj-Cj 10 70 0 15+M 0 450

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 α.



18

Solución

Primera Forma

2

1Kδ

10

30b

1BBKX

3

1

2

1

11-

01Kδ1B Solo negativos (-3)

3.333

10

3

10Min0kδ1/B

kδ1B

)BK(XMinα*

La solución es óptima para: 3.33α0

Segunda Forma

Aplicar

2α40

α30Kδ

3α10

α30

2α40

α30

11-

01Kδ1B

03α-10

0α30

310α

30α

La solución es óptima para: 310α0

Expresión General

5α1503α10

α3005

2α40

α30

11-

0105Kδ1BBCZ*

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

2α40

2α30Kδ

4α10

2α30

2α40

2α30

11-

01Kδ1B

04α-10

02α30

410α

230α

La solución es óptima para: 410α0

10α1504α10

2α3005

2α40

2α30

11-

0105Kδ1BBCZ*

En el caso de que α=3 la variable que abandonaría la base seria X5 y la variable que ingresaría seria X3

α=3

2-

36

4(3)10

2(3)30 18010(3)15010α150Z*

XB A1 A2 A3 A4 A5 b

X1 1 5 2 1 0 36

X5 0 -10 -8 -1 1 -2

Zj-Cj 0 23 7 5+M 0 180

Solución Optima:

XB A1 A2 A3 A4 A5 b

X1 1 5/2 0 3/4 1/4 71/2

X3 0 5/4 1 1/8 -1/8 1/4

Zj-Cj 0 57/4 0 33/8+M 7/8 713/4

Z = 713/4; X1 = 71/2; X2 = 0; X3 = 1/4; X4 = 0; X5 = 0

6) Considere el siguiente programa:

MAX Z = 5X1 + 2X2 + 3X3

s.a.

X1 + 5X2 + 2X3 ≤ 30

X1 – 5X2 – 6X3 ≤ 40

X1, X2, X3 ≥ 0

XB A1 A2 A3 A4 A5 b

X1 1 5 2 1 0 30

X5 0 -10 -8 -1 1 10

Zj-Cj 0 23 7 5 0 150

Cuya solución óptima se da en la tabla:

Resolver el P.N. con los siguientes cambios:



19

a) La función objetivo cambia a: MAX Z = 5X1 + 2X2 + 12X3

Solución

0122VNBj

C

05VBBC

4X3X2X

5X1X

065

125


4X3X2X52-230122510250122

065

125

11

0105

jC

ja

1BBC

15010

3005

40

30

11

0105b

1BBC


XB A1 A2 A3 A4 A5 b

X1 1 5 2 1 0 30

X5 0 -10 -8 -1 1 10

Zj-Cj 0 23 -2 5 0 150

XB A1 A2 A3 A4 A5 b

X3 1/2 5/2 1 1/2 0 15

X5 4 10 0 3 1 130

Zj-Cj 1 28 0 6 0 180

Z = 180; X1 = 0; X2 = 0; X3 = 15; X4 = 0; X5 = 130

b) Se duplica la disponibilidad del recurso b1 (b1=60)

20

60

40

60

11

01b

1B 300

40

60

11

0105b

1BBC

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:

24C

4

44a 2003X1SVBBC

Solución:

0

4

4

4

11

016a

1B 182202

0

4052

4

4

11

01056C6a

1BBC


XB A1 A2 A3 A6 A4 A5 b

X1 1 5 2 4 1 0 30

X5 0 -10 -8 0 -1 1 10

Zj-Cj 0 23 7 18 5 0 150



20

d) Se añade la nueva restricción: 2X2 + 6X3 ≤ 10

XB A1 A2 A3 A4 A5 A6 b

X1 1 5 2 1 0 0 30

X5 0 -10 -8 -1 1 0 10

X6 0 2 6 0 0 1 10

Zj-Cj 0 23 7 5 0 0 150

Z = 150; X1 = 30; X2 = 0; X3 = 0; X4 = 0; X5 = 10; X6 = 10

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

s.a.

8X1 + 3X2 ≤ 1200 (Cuero)

12X1 + 14X2 ≤ 1800 (Confección)

X1, X2 ≥ 0

XB A1 A2 A3 A4 b

X1 1 3/8 1/8 0 150

X4 0 19/2 -3/2 1 0

Zj-Cj 0 15/4 53/4 0 15900

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

s.a.

1½X1 + ½X2 ≤ 100 (Ensamble)

1X1 + ½X2 ≤ 80 (Terminado)

X1, X2 ≥ 0

XB A1 A2 A3 A4 b

X3 1/2 0 1 -1 20

X2 2 1 0 2 160

Zj-Cj 4 0 0 24 1920

Z = 1920; X1 = 0; X2 = 160; X3 = 20; X4 = 0



21

Solución

080

Δ

20

11b

1B

0160

080-Δ

80Δ

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.

0Δ

100

20

11b

1B

02Δ

0Δ-100

0Δ

100Δ

El rango de factibilidad para el recurso del terminado es: 100Δ0

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 B C D E

1 8 4 7 3 8

2 6 5 8 4 9

3 7 3 9 5 8

Solución

1 2 3 4 5

1 800 1200

2000 8 4 7 3 8

2 800 100 900

1800 6 5 8 4 9

3 1000 1000

2000 7 3 9 5 8

800 1000 900 1200 1900

Para todas las VB 0cvu ijji

U1 + V3 – 7 = 0 U1 = 0 V1 = 5

U1 + V4 – 3 = 0 U2 = 1 V2 = 3

U2 + V1 – 6 = 0 U3 = 0 V3 = 7

U2 + V3 – 8 = 0 V4 = 3

U2 + V5 – 9 = 0 V5 = 8

U3 + V2 – 3 = 0

U3 + V5 – 8 = 0

Para todas las VNB ijjiijij cvucz MIN

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.



22

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 4

1 20

20 13 9 12 8

2 30

30 4 15 7 9

3 20 10 10

40 14 7 1 0

4 30 20

50 3 12 5 19

60 60 10 10


U1 + V2 – 9 = 0 U1 = 0 V1 = 0

U2 + V1 – 4 = 0 U2 = 4 V2 = 9

U3 + V2 – 7 = 0 U3 = –2 V3 = 3

U3 + V3 – 1 = 0 U4 = 3 V4 = 2

U3 + V4 – 0 = 0

U4 + V1 – 3 = 0

U4 + V2 – 12 = 0


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 2 3 4

1 20

20 13 9 12 8

2 30

30 4 15 7 9

3 20+ θ 10– θ 10

40 14 7 1 0

4 30 20– θ θ

50 3 12 5 19

60 60 10 10

θ = MIN {VB (–θ)} = {20, 10} = 10

1 2 3 4

1 20

20 13 9 12 8

2 30

30 4 15 7 9

3 30 10

40 14 7 1 0

4 30 10 10

50 3 12 5 19

60 60 10 10


U1 + V2 – 9 = 0 U1 = 0 V1 = 0

U2 + V1 – 4 = 0 U2 = 4 V2 = 9

U3 + V2 – 7 = 0 U3 = –2 V3 = 2

U3 + V4 – 0 = 0 U4 = 3 V4 = 2

U4 + V1 – 3 = 0

U4 + V2 – 12 = 0

U4 + V3 – 5 = 0


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



23


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

A B C D E

1 10

10 10 20 5 7 0

2 20

20 13 9 12 8 0

3 10 10 10

30 4 15 7 9 0

4 20 10 10

40 14 7 1 0 0

5 50

50 3 12 5 19 0

60 60 10 10 10

ii) Voguel

A B C D E

1 10

10 10 20 5 7 0

2 10 10

20 13 9 12 8 0

3 30

30 4 15 7 9 0

4 20 10 10

40 14 7 1 0 0

5 20 30

50 3 12 5 19 0

60 60 10 10 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)

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



24

EXAMENES RESUELTOS

TERCER PARCIAL

ARBOL DE EXPANSIÓN MINIMO

1) Encontrar el árbol de expansión mínimo de la fig.

O

A

B

C

D

E

F

G

H

I

7

8

7

8

4

6

6

2

7

3

6

5

8

6

9

8

8

5

3

9

O

A

B

C

D

E

F

G

H

I

7

4

6

6

2

3

6

8

3

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:

1

3

2

64

7

9

5

8

10

45

30

20

50

50

25

45

30

30

40

25

20

40

15

35

60

35

1

3

2

64

7

9

5

8

10

30

20

25

45

30

25

2015

35

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)

2

1

3

6

4

5

7

5

1

7

7

4

36

2

9

62

7

7

6

2

2

1

3

6

4

5

7

5

1

7

7

4

36

2

9

62

7

7

6

2

* [1 , 1]

[14 , 4]

* [ 0 , _ ]

* [3 , 3]

[5 , 1]

[16 , 6]

* [7 , 3]

[8 , 5]

[10 , 2]

* [8 , 3]

[5 , 2]

* [11 , 4]

[9 , 2]

* [11 , 6]

[13 , 4]

[14 , 5]

Solución

Nodo

Inicial

Nodo

Final Ruta Distancia

1 2 1-3-2 3

1 3 1-3 1

1 4 1-3-4 7

1 5 1-3-2-5 5

1 6 1-3-2-6 9

1 7 1-3-2-6-7 11



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:

1 3

2

44 2

4

2

6

31 2

5

1 3

2

4

5

4 2

4

2

6

31 2

* [3 , 1]

* [4 , 1]

[4 , 2]

* [7 , 2]

[6 , 3]

* [ 0 , _ ]

* [9 , 2]

[6 , 3]

[8 , 4]

Dijkstra

Matriz de distancias Matriz de secuencia

Do 1 2 3 4 5 So 1 2 3 4 5

1 – 3 4 ∞ ∞ 1 – 2 3 4 5

2 ∞ – 1 4 6 2 1 – 3 4 5

3 ∞ ∞ – 2 2 3 1 2 – 4 5

4 ∞ ∞ ∞ – 2 4 1 2 3 – 5

5 ∞ ∞ ∞ ∞ – 5 1 2 3 4 –

K=3 (tachar la 3 fila y columna).

D3 1 2 3 4 5 S3 1 2 3 4 5

1 – 3 4 6 6 1 – 2 3 3 3

2 ∞ – 1 3 3 2 1 – 3 3 3

3 ∞ ∞ – 2 2 3 1 2 – 4 5

4 ∞ ∞ ∞ – 2 4 1 2 3 – 5

5 ∞ ∞ ∞ ∞ – 5 1 2 3 4 –


D1 1 2 3 4 5 S1 1 2 3 4 5

1 – 3 4 ∞ ∞ 1 – 2 3 4 5

2 ∞ – 1 4 6 2 1 – 3 4 5

3 ∞ ∞ – 2 2 3 1 2 – 4 5

4 ∞ ∞ ∞ – 2 4 1 2 3 – 5

5 ∞ ∞ ∞ ∞ – 5 1 2 3 4 –


D4 1 2 3 4 5 S4 1 2 3 4 5

1 – 3 4 6 6 1 – 2 3 3 3

2 ∞ – 1 3 3 2 1 – 3 3 3

3 ∞ ∞ – 2 2 3 1 2 – 4 5

4 ∞ ∞ ∞ – 2 4 1 2 3 – 5

5 ∞ ∞ ∞ ∞ – 5 1 2 3 4 –


D2 1 2 3 4 5 S2 1 2 3 4 5

1 – 3 4 7 9 1 – 2 3 2 2

2 ∞ – 1 4 6 2 1 – 3 4 5

3 ∞ ∞ – 2 2 3 1 2 – 4 5

4 ∞ ∞ ∞ – 2 4 1 2 3 – 5

5 ∞ ∞ ∞ ∞ – 5 1 2 3 4 –


D5 1 2 3 4 5 S5 1 2 3 4 5

1 – 3 4 6 6 1 – 2 3 3 3

2 ∞ – 1 3 3 2 1 – 3 3 3

3 ∞ ∞ – 2 2 3 1 2 – 4 5

4 ∞ ∞ ∞ – 2 4 1 2 3 – 5

5 ∞ ∞ ∞ ∞ – 5 1 2 3 4 –

Las distancias mínimas son:

Nodo

Inicial

Nodo


1 2 1-2 3

1 3 1-3 4

1 4 1-3-4 6

1 5 1-3-5 6

2 3 2-3 1

2 4 2-3-4 3

2 5 2-3-5 3

3 4 3-4 2

3 5 3-5 2

4 5 4-5 2



26

5) Aplicar el método de FLOYD para encontrar las rutas mas cortas entre pares de nodos de la figura:

1

2

3

4

5

1

5

2

1

13

1

3


Do 1 2 3 4 5 So 1 2 3 4 5

1 – 1 3 ∞ ∞ 1 – 2 3 4 5

2 1 – 1 5 3 2 1 – 3 4 5

3 ∞ ∞ – 2 1 3 1 2 – 4 5

4 ∞ ∞ ∞ – 1 4 1 2 3 – 5

5 ∞ ∞ ∞ 1 – 5 1 2 3 4 –


Do 1 2 3 4 5 So 1 2 3 4 5

1 – 1 2 4 3 1 – 2 2 3 3

2 1 – 1 3 2 2 1 – 3 3 3

3 ∞ ∞ – 2 1 3 1 2 – 4 5

4 ∞ ∞ ∞ – 1 4 1 2 3 – 5

5 ∞ ∞ ∞ 1 – 5 1 2 3 4 –


Do 1 2 3 4 5 So 1 2 3 4 5

1 – 1 3 ∞ ∞ 1 – 2 3 4 5

2 1 – 1 5 3 2 1 – 3 4 5

3 ∞ ∞ – 2 1 3 1 2 – 4 5

4 ∞ ∞ ∞ – 1 4 1 2 3 – 5

5 ∞ ∞ ∞ 1 – 5 1 2 3 4 –


Do 1 2 3 4 5 So 1 2 3 4 5

1 – 1 2 4 3 1 – 2 2 3 3

2 1 – 1 3 2 2 1 – 3 3 3

3 ∞ ∞ – 2 1 3 1 2 – 4 5

4 ∞ ∞ ∞ – 1 4 1 2 3 – 5

5 ∞ ∞ ∞ 1 – 5 1 2 3 4 –


Do 1 2 3 4 5 So 1 2 3 4 5

1 – 1 2 6 4 1 – 2 2 2 2

2 1 – 1 5 3 2 1 – 3 4 5

3 ∞ ∞ – 2 1 3 1 2 – 4 5

4 ∞ ∞ ∞ – 1 4 1 2 3 – 5

5 ∞ ∞ ∞ 1 – 5 1 2 3 4 –


Do 1 2 3 4 5 So 1 2 3 4 5

1 – 1 2 4 3 1 – 2 2 3 3

2 1 – 1 3 2 2 1 – 3 3 3

3 ∞ ∞ – 2 1 3 1 2 – 4 5

4 ∞ ∞ ∞ – 1 4 1 2 3 – 5

5 ∞ ∞ ∞ 1 – 5 1 2 3 4 –


Nodo

Inicial

Nodo


1 2 1-2 1

1 3 1-2-3 2

1 4 1-3-4

1-2-3-4 4

1 5 1-3-5

1-2-3-5 3

2 3 2-3 1

2 4 2-3-4 3

2 5 2-3-5 2

3 4 3-4 2

3 5 3-5 1

4 5 4-5 1



27

6) Encontrar la ruta mas corta entre el nodo 1 hacia los otros nodos de la red.

1

2

4

5

3

6

7

4

5

5

3

1

26

2

8

7

6

3


Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7

1 – 4 7 5 ∞ ∞ ∞ 1 – 2 3 4 5 6 7

2 4 – 3 ∞ 5 ∞ ∞ 2 1 – 3 4 5 6 7

3 7 3 – 1 2 6 ∞ 3 1 2 – 4 5 6 7

4 5 ∞ 1 – ∞ 8 ∞ 4 1 2 3 – 5 6 7

5 ∞ 5 2 ∞ – 3 6 5 1 2 3 4 – 6 7

6 ∞ ∞ 3 8 3 – 2 6 1 2 3 4 5 – 7

7 ∞ ∞ ∞ ∞ 6 2 – 7 1 2 3 4 5 6 –

K=1 (tachar la 1 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 7 5 ∞ ∞ ∞ 1 – 2 3 4 5 6 7

2 4 – 3 9 5 ∞ ∞ 2 1 – 3 1 5 6 7

3 7 3 – 1 2 6 ∞ 3 1 2 – 4 5 6 7

4 5 9 1 – ∞ 8 ∞ 4 1 1 3 – 5 6 7

5 ∞ 5 2 ∞ – 3 6 5 1 2 3 4 – 6 7

6 ∞ ∞ 6 8 3 – 2 6 1 2 3 4 5 – 7

7 ∞ ∞ ∞ ∞ 6 2 – 7 1 2 3 4 5 6 –


Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7

1 – 4 7 5 9 ∞ ∞ 1 – 2 3 4 2 6 7

2 4 – 3 9 5 ∞ ∞ 2 1 – 3 1 5 6 7

3 7 3 – 1 2 6 ∞ 3 1 2 – 4 5 6 7

4 5 9 1 – 14 8 ∞ 4 1 1 3 – 2 6 7

5 9 5 2 14 – 3 6 5 2 2 3 2 – 6 7

6 ∞ ∞ 6 8 3 – 2 6 1 2 3 4 5 – 7

7 ∞ ∞ ∞ ∞ 6 2 – 7 1 2 3 4 5 6 –


Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7

1 – 4 7 5 9 13 ∞ 1 – 2 3 4 2 3 7

2 4 – 3 4 5 9 ∞ 2 1 – 3 3 5 3 7

3 7 3 – 1 2 6 ∞ 3 1 2 – 4 5 6 7

4 5 4 1 – 3 7 ∞ 4 1 3 3 – 3 3 7

5 9 5 2 3 – 3 6 5 2 2 3 3 – 6 7

6 13 9 6 7 3 – 2 6 3 3 3 3 5 – 7

7 ∞ ∞ ∞ ∞ 6 2 – 7 1 2 3 4 5 6 –



28


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 –


Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7

1 – 4 6 5 8 11 14 1 – 2 4 4 4 5 5

2 4 – 3 4 5 8 11 2 1 – 3 3 5 5 5

3 6 3 – 1 2 5 8 3 4 2 – 4 5 5 5

4 5 4 1 – 3 6 9 4 1 3 3 – 3 5 5

5 8 5 2 3 – 3 6 5 4 2 3 3 – 6 7

6 11 8 5 6 3 – 2 6 5 5 5 5 5 – 7

7 14 11 8 9 6 2 – 7 5 5 5 5 5 6 –


Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7

1 – 4 6 5 8 11 13 1 – 2 4 4 4 5 6

2 4 – 3 4 5 8 10 2 1 – 3 3 5 5 6

3 6 3 – 1 2 5 7 3 4 2 – 4 5 5 6

4 5 4 1 – 3 6 8 4 1 3 3 – 3 5 6

5 8 5 2 3 – 3 5 5 4 2 3 3 – 6 6

6 11 8 5 6 3 – 2 6 5 5 5 5 5 – 7

7 13 10 7 8 5 2 – 7 6 6 6 6 6 6 –


Do 1 2 3 4 5 6 7 So 1 2 3 4 5 6 7

1 – 4 6 5 8 11 13 1 – 2 4 4 4 5 6

2 4 – 3 4 5 8 10 2 1 – 3 3 5 5 6

3 6 3 – 1 2 5 7 3 4 2 – 4 5 5 6

4 5 4 1 – 3 6 8 4 1 3 3 – 3 5 6

5 8 5 2 3 – 3 5 5 4 2 3 3 – 6 6

6 11 8 5 6 3 – 2 6 5 5 5 5 5 – 7

7 13 10 7 8 5 2 – 7 6 6 6 6 6 6 –


Nodo

Inicial

Nodo


1 2 1-2 4

1 3 1-4-3 6

1 4 1-4 5

1 5 1-4-5

1-4-3-5 8

Nodo

Inicial

Nodo


1 6

1-5-6

1-4-5-6

1-4-3-5-6

11

1 7

1-6-7

1-5-6-7

1-4-5-6-7

1-4-3-5-6-7

13



29

FLUJO MAXIMO

7) Encontrar el flujo máximo y los flujos óptimos en los arcos de la red de la siguiente figura:

3

1 5

2 4

14

10

6

8

57

4

5 7

0

0

109

6

0

0

0

0

3

1 5

2 4

14

10

6

8

57

4

5 7

0

0

109

6

0

0

0

0

3

1 5

2 4

4

0

6

8

57

4

5 7

0

10

109

6

10

0

0

0

f1 = {(1,3); (3,5)} = {14, 10} = 10 f2 = {(1,2); (2,4); (4,5)} = {8, 7, 5} = 5

3

1 5

2 4

4

0

6

3

02

4

5 7

5

10

109

11

10

5

0

0

3

1 5

2 4

0

0

2

3

02

4

9 7

5

14

69

11

10

5

4

0

f3 = {(1,3); (3,2); (2,5)} = {4, 10, 6} = 4 f4 = {(1,5)} = {4} = 4

3

1 5

2 4

0

0

2

3

02

0

9 7

5

14

69

11

10

5

4

4

3

1 5

2 4

0

0

0

1

02

0

9 7

7

14

69

11

10

5

6

4

YA NO HAY CAMINO

f5 = {(1,2); (2,5)} = {3, 2} = 2 fmax = f1 + f2 + f3 + f4 + f5 = 10 + 5 + 4 + 4 + 2 = 25



30

Arco Capacidad del arco inicial – Capacidad del

arco final Flujo Dirección

(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:

3

1 5

2 4

10

10

10

10

1030

30

10 10

0

0

520

10

0

0

0

0

3

1 5

2 4

10

10

10

10

1030

30

10 10

0

0

520

10

0

0

0

0

3

1 5

2 4

10

10

10

10

1030

0

10 10

0

0

520

10

0

0

0

30

f1 = {(1,5)} = {30} = 30 f2 = {(1,3); (3,4); (4,5)} = {10, 20, 10} = 10

3

1 5

2 4

0

10

10

10

030

0

10 20

0

10

510

10

0

10

0

30

3

1 5

2 4

0

0

10

0

020

0

10 10

10

10

520

20

10

10

0

30

f3 = {(1,2); (2,4); (4,3) ; (3,5)} = {10, 30, 20, 10} = 10 fmax = f1 + f2 + f3 = 30 + 10 + 10 = 50



31

9) Encontrar el flujo máximo entre los nodos 1 y 5 de la figura:

3

1 5

2 4

20

10

16

20

1520

20

20 5

0

0

1615

11

0

0

0

0

3

1 5

2 4

20

10

16

20

1520

20

20 5

0

0

1615

11

0

0

0

0

3

1 5

2 4

5

10

16

20

05

20

35 5

0

15

115

26

0

15

0

0

f1 = {(1,3); (3,2); (2,4) ; (4,5)} = {20, 16, 20, 15} = 15 f2 = {(1,2); (2,3); (3,5)} = {20, 35, 10} = 10

3

1 5

2 4

5

0

16

10

05

20

25 5

10

15

1115

26

10

15

0

0

3

1 5

2 4

5

0

16

10

05

0

25 5

10

15

1115

26

10

15

0

20

f3 = {(1,5)} = {20} = 20 f4 = {(1,2); (2,5)} = {10, 16} = 10

3

1 5

2 4

5

0

6

0

05

0

25 5

20

15

1115

26

10

15

10

20

3

1 5

2 4

0

0

1

0

010

0

25 10

20

20

1110

21

10

15

15

20

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



32

Arco Capacidad del arco inicial – Capacidad del

arco final Flujo Dirección

(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 0 6 8 7 4

5 2 3 0 6 7

3 4 4 3 5 2

3 9 7 2 7 6

9 8 7 8 4 5

1 8 7 4 2 3

A B C D E F

1 5 0 6 8 7 4 0

2 5 2 3 0 6 7 0

3 3 4 4 3 5 2 2

4 3 9 7 2 7 6 2

5 9 8 7 8 4 5 4

6 1 8 7 4 2 3 1

A B C D E F

1 5 0 6 8 7 4

2 5 2 3 0 6 7

3 1 2 2 1 3 0

4 1 7 5 0 5 4

5 5 4 3 4 0 1

6 0 7 6 3 1 2

0 0 2 0 0 0

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

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

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

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



33

Solución

Al Ca Fi Qu Pr

P1 40 – 40 – –

P2 – 45 45 45 –

P3 – 60 – – 60

P4 50 50 50 – –

P5 – – 35 35 –

40 45 35 35 60

Al Ca Fi Qu Pr

P1 0 – 5 – – 0

P2 – 0 10 10 – 0

P3 – 15 – – 0 0

P4 10 5 15 – – 5

P5 – – 0 0 – 0

Al Ca Fi Qu Pr

P1 0 – 5 – –

P2 – 0 10 10 –

P3 – 15 – – 0

P4 5 0 10 – –

P5 – – 0 0 –



Al Ca Fi Qu Pr

P1 0 – 5 – –

P2 – 0 5 5 –

P3 – 15 – – 0

P4 0 0 5 – –

P5 – – 0 0 –



Al Ca Fi Qu Pr

P1 0 – 0 – –

P2 – 0 0 0 –

P3 – 15 – – 0

P4 0 0 0 – –

P5 – – 0 0 –


Asignar

Al Ca Fi Qu Pr

P1 0 – 0 – –

P2 – 0 0 0 –

P3 – 15 – – 0

P4 0 0 0 – –

P5 – – 0 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:

1 31

2 4

5

62

6

8

3

5 113

4

100

100 150

150

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 6 Oferta

OR

IGE

NE

S 1 1 4 M M 100

2 3 2 M M 200

3 0 3 6 M θ 4 1 0 5 8 θ 5 M M 0 1 θ

Dem θ θ 150+ θ 150

Dos

3 4 5 6 Oferta

OR

IGE

NE

S 1 1 4 M M 100

2 3 2 M M 200

3 0 3 6 M 300

4 1 0 5 8 300

5 M M 0 1 300

Dem 300 300 450 150

(θ=100+200=150+150) (θ=300=300) (θ=300)



34

Solución Inicial Voguel:

3 4 5 6

1 100

100 1 4 M M

2 200

200 3 2 M M

3 200 100

300 0 3 6 M

4 100 200

300 1 0 5 8

5 150 150

300 M M 0 1

300 300 450 150

Para todas las VB ijji cvu Para todas las VNB ijjiij cvuc MIN

U1 + V3 = 1

U2 + V4 = 2

U3 + V3 = 0

U3 + V4 = 6

U4 + V4 = 0

U4 + V5 = 5

U5 + V5 = 0

U5 + V6 = 1

U1 = 0

U2 = 0

U3 = –1

U4 = –2

U5 = –7

V3 = 1

V4 = 2

V5 = 7

V6 = 8

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


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

1 10 10 0

20 5 1 0 0

2 10

10 2 2 4 0

3 5 10

15 7 5 2 0

4 15

15 9 6 0 0

25 10 15 10



35


U1 + V1 – 5 = 0 U1 = 0 V1 = 5

U1 + V2 – 1 = 0 U2 = –3 V2 = 1

U1 + V3 – 0 = 0 U3 = 2 V3 = 0

U2 + V1 – 2 = 0 U4 = 0 V4 = –2

U3 + V1 – 7 = 0

U3 + V4 – 0 = 0

U4 + V3 – 0 = 0


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


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:

A C5

B D

E

F

8

4

4

1010

23

100

120

50

100

G

6

100

10

6

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

Solución:

C D E F G Oferta

A 5 3 10 M M 100

B 10 8 M M 6 120

C 0 2 4 6 M θ D M 0 M 10 4 θ Y 0 0 0 0 0 30

Dem θ θ 100 50 100

C D E F G Oferta

A 5 3 10 M M 100

B 10 8 M M 6 120

C 0 2 4 6 M 250

D M 0 M 10 4 250

Y 0 0 0 0 0 30

Dem 250 250 100 50 100

(θ=100+120+30=100+50+100) (θ=250=250) (θ=250)

a) Encontrar una solución Inicial (Voguel).

C D E F G

A 100 0

100 5 3 10 M M

B 20 100

120 10 8 M M 6

C 150 100

250 0 2 4 6 M

D 230 20

250 M 0 M 10 4

Y 30

30 0 0 0 0 0

250 250 100 50 100



36

b) Encontrar la solución optima.


U1 + V1 = 5

U1 + V2 = 3

U2 + V2 = 8

U2 + V5 = 6

U3 + V1 = 0

U3 + V3 = 4

U4 + V2 = 0

U4 + V4 = 10

U5 + V4 = 0

U1 = 0

U2 = 5

U3 = –5

U4 = –3

U5 = –13

V1 = 5

V2 = 3

V3 = 9

V4 = 13

V5 = 1

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

C51 = (–13+5) – 0 = –8

C52 = (–13+3) – 0 = –10

C53 = (–13+9) – 0 = –4

C55 = (–13+1) – 0 = –12

C D E F G

A 100+θ 0–θ

100 5 3 10 M M

B 20 100

120 10 8 M M 6

C 150–θ 100 θ

250 0 2 4 6 M

D 230+θ 20–θ

250 M 0 M 10 4

Y 30

30 0 0 0 0 0

250 250 100 50 100

θ = MIN {VB (–θ)} = {20, 0, 150} = 0

C D E F G

A 100

100 5 3 10 M M

B 20 100

120 10 8 M M 6

C 150 100 0

250 0 2 4 6 M

D 230 20

250 M 0 M 10 4

Y 30

30 0 0 0 0 0

250 250 100 50 100


U1 + V1 = 5

U2 + V2 = 8

U2 + V5 = 6

U3 + V1 = 0

U3 + V3 = 4

U3 + V4 = 6

U4 + V2 = 0

U4 + V4 = 10

U5 + V4 = 0

U1 = 0

U2 = 7

U3 = –5

U4 = –1

U5 = –11

V1 = 5

V2 = 1

V3 = 9

V4 = 11

V5 = –1

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



37

C D E F G

A 100

100 5 3 10 M M

B θ 20–θ 100

120 10 8 M M 6

C 150–θ 100 0+θ

250 0 2 4 6 M

D 230+θ 20–θ

250 M 0 M 10 4

Y 30

30 0 0 0 0 0

250 250 100 50 100

θ = MIN {VB (–θ)} = {20, 20, 150} = 20

C D E F G

A 100

100 5 3 10 M M

B 20 100

120 10 8 M M 6

C 130 100 20

250 0 2 4 6 M

D 250 0

250 M 0 M 10 4

Y 30

30 0 0 0 0 0

250 250 100 50 100


U1 + V1 = 5

U2 + V1 = 10

U2 + V5 = 6

U3 + V1 = 0

U3 + V3 = 4

U3 + V4 = 6

U4 + V2 = 0

U4 + V4 = 10

U5 + V4 = 0

U1 = 0

U2 = 5

U3 = –5

U4 = –1

U5 = –11

V1 = 5

V2 = 1

V3 = 9

V4 = 11

V5 = 1

C12 = (0+1) – 3 = –2

C13 = (0+9) – 10 = –1

C14 = (0+11) – M = 11–M

C15 = (0+1) – M = 1–M

C22 = (5+1) – 8 = –2

C23 = (5+9) – M = 14–M

C24 = (5+11) – M = 16–M

C32 = (–5+1) – 2 = –6

C35 = (–5+1) – M = –4–M

C41 = (–1+5) – M = 4–M

C43 = (–1+9) – M = 8–M

C45 = (–1+1) – 4 = –4

C51 = (–11+5) – 0 = –6

C52 = (–11+1) – 0 = –10

C53 = (–11+9) – 0 = –2

C55 = (–11+1) – 0 = –10


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?



38

A C5

B D

E

F

8

4

4

1010

23

100

120

20

100

G

6

100

10

6

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

Solución:

C D E F G Oferta

A 5 3 10 M M 100

B 10 8 M M 6 120

C 0 2 4 6 M θ D M 0 M 10 4 θ

Dem θ θ 100 20 100

C D E F G Oferta

A 5 3 10 M M 100

B 10 8 M M 6 120

C 0 2 4 6 M 220

D M 0 M 10 4 220

Dem 220 220 100 20 100

(θ=100+120=100+20+100) (θ=220=220) (θ=220)

Solución Inicial (Voguel).

C D E F G

A 100+θ 0–θ

100 5 3 10 M M

B 20 100

120 10 8 M M 6

C 120–θ 100 θ

220 0 2 4 6 M

D 200+ θ 20–θ

220 M 0 M 10 4

220 220 100 20 100

Encontrar la solución optima.


U1 + V1 = 5

U1 + V2 = 3

U2 + V2 = 8

U2 + V5 = 6

U3 + V1 = 0

U3 + V3 = 4

U4 + V2 = 0

U4 + V4 = 10

U1 = 0

U2 = 5

U3 = –5

U4 = –3

V1 = 5

V2 = 3

V3 = 9

V4 = 13

V5 = 1

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

Documents

Parciales Resueltos IngEscalante-1