10_ind2209_alumno_15

7/23/2019 10_IND2209_Alumno_15

http://slidepdf.com/reader/full/10ind2209alumno15 1/30

Investigación

de

OperacionesIND2209

Profesor: Pamela Álvarez M.

Facultad de Ingeniería

Departamento de Ciencias de la Ingeniería

Unidad Nº 6

7/23/2019 10_IND2209_Alumno_15


• Clase pasada:

• Problema de Transporte

• Métodos para encontrar SBF:

• Método de la esquina noroeste

• Método del costo mínimo

• Método de Vogel

• Lo que sigue:

• Método Simplex en Redes

• Problema de transbordo

• Problema de Asignación

• Métodos Húngaro

2

Programación en redes

IND2209. Prof.: Pamela Álvarez M.

7/23/2019 10_IND2209_Alumno_15


1. Si el problema no está balanceado, balancearlo y construir el Tableau de

transporte.

2. Encontrar una SBF. Verificar las m+n‐1 VB y completarlas si es necesario.

3. Plantear y resolver el sistema que se obtiene a través de:

i. Definir para cada fila del tableau la variable ui (i=1,…,m)

ii. Definir para cada columna del tableau la variable v j ( j=1,…,n)

iii. Plantear para cada casilla asignada la ecuación ui + v j = cij. Donde cij

es el costo unitario asociado a la casilla i-j.

iv. Asignar un valor arbitrario a una de las variables, por ejemplo u1 = 0.

3

Programación en redes – Simplex en redes (transporte)


7/23/2019 10_IND2209_Alumno_15


4. Calcular en todas las casillas no asignadas (no básicas) eij = cij - ui ‐ v j. Si

todos los eij ≥ 0 se ha encontrado el óptimo. Si existe algún eij < 0 ,

incorporar la variable con menor siempre y cuando se pueda formar un

loop, en dicho caso asignar el mayor valor posible de modo de mantener

las VB mayores o iguales a cero.

5. Si la solución no es óptima, emplear la solución del paso anterior para

volver a plantear y resolver el paso 3 y seguir al 4.

4

Programación en redes – Simplex en redes (transporte)


7/23/2019 10_IND2209_Alumno_15


• Simplex de Transporte ‐ Ejemplo:

• Se dispone de la siguiente SBF:

5

Programación en redes


PlantasCiudades

OFERTA1 2 3 4

18 6 10 9

35

35

29 12 13 7

5010 20 20

314 9 16 5

4010 30

DEMANDA 45 20 30 30 125/125

7/23/2019 10_IND2209_Alumno_15


6

Programación en redes - Simplex de Transporte

Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3535

u 2

9 12 13 750

10 20 20

u 3

14 9 16 540

10 30

45 20 30 30

1 1

2 1

2 2

2 3

3 3

3 4

8

9

12

13

16

5

u v

u v

u v

u v

u v

u v

1 2 3

1 2 3 4

0 1 4

8 11 12 1

u u u

v v v v

12

13

14

24

31

32

6 0 11 5

10 0 12 2

9 0 1 87 1 1 5

14 4 8 2

9 4 11 6

e

e

e

e

e

e

7/23/2019 10_IND2209_Alumno_15


7


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3535

u 2

9 12 13 750

10 20‐g 20+g

u 3

14 9 16 540

g 10‐g 30

45 20 30 30

g = 10

7/23/2019 10_IND2209_Alumno_15


8


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3535

u 2

9 12 13 750

10 10 30

u 3

14 9 16 540

10 30

45 20 30 30

7/23/2019 10_IND2209_Alumno_15


9


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3535

u 2

9 12 13 750

10 10 30

u 3

14 9 16 540

10 30

45 20 30 30

1 1

2 1

2 2

2 3

3 2

3 4

8

9

12

13

9

5

u v

u v

u v

u v

u v

u v

1 2 3

1 2 3 4

0 1 2

8 11 12 7

u u u

v v v v

12

13

14

24

31

33

6 0 11 5

10 0 12 2

9 0 7 27 1 7 1

14 ( 2) 8 8

16 ( 2) 12 6

e

e

ee

e

e

7/23/2019 10_IND2209_Alumno_15


10


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3535‐g g

u 2

9 12 13 750

10+g 10‐g 30

u 3

14 9 16 540

10 30

45 20 30 30

g = 10

7/23/2019 10_IND2209_Alumno_15


11


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3525 10

u 2

9 12 13 750

20 30

u 3

14 9 16 540

10 30

45 20 30 30

7/23/2019 10_IND2209_Alumno_15


12


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3525 10

u 2

9 12 13 750

20 30

u 3

14 9 16 540

10 30

45 20 30 30

1 1

2 2

2 1

2 3

3 2

3 4

8

6

9

13

9

5

u v

u v

u v

u v

u v

u v

1 2 3

1 2 3 4

0 1 4

8 5 12 1

u u u

v v v v

13

14

22

24

31

33

10 0 12 2

9 0 1 8

12 1 5 67 1 1 5

14 4 8 2

16 4 12 0

e

e

ee

e

e

7/23/2019 10_IND2209_Alumno_15


13


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3525‐g 10 g

u 2

9 12 13 750

20+g 30‐g

u 3

14 9 16 540

10 30

45 20 30 30

g = 25

7/23/2019 10_IND2209_Alumno_15


14


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3510 25

u 2

9 12 13 750

45 5

u 3

14 9 16 540

10 30

45 20 30 30

7/23/2019 10_IND2209_Alumno_15


15


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 9

3510 25

u 2

9 12 13 750

45 5

u 3

14 9 16 540

10 30

45 20 30 30

1 2

1 3

2 1

2 3

3 2

3 4

6

10

9

13

9

5

u v

u v

u v

u v

u v

u v

1 2 3

1 2 3 4

0 3 3

6 6 10 2

u u u

v v v v

11

14

22

24

31

33

8 0 6 2

9 0 2 7

12 3 6 37 3 2 2

14 3 6 5

16 3 10 3

e

e

ee

e

e

7/23/2019 10_IND2209_Alumno_15


16


Ejemplo


v1 v 2 v 3 v 4

u1

8 6 10 935

10 25

u 2

9 12 13 750

45 5

u 3

14 9 16 540

10 30

45 20 30 30

11 12 13 14

21 22 23 24

31 32 33 34

0 10 25 0

45 0 5 0

0 10 0 30

x x x x

x x x x

x x x x

6(10) 10(25) 9(45) 13(5) 9(10) 5(30) 1.020 z

7/23/2019 10_IND2209_Alumno_15


• Problema de Transporte:

Origen Destino

• Problema de Transbordo:

Origen Puntos de Transbordo Destino

• Sin embargo, es posible resolverlo como un problema de transporte.

• Definiciones:

• Punto de oferta: puntos desde donde sólo se puede despachar unidades.

• Punto de demanda: puntos donde sólo se pueden recibir unidades.

• Punto de transbordo: puntos que pueden recibir y enviar unidades a otros

puntos.

17

Programación en redes – Problema de Transbordo


7/23/2019 10_IND2209_Alumno_15


• Una fábrica posee 2 plantas de manufactura, una en Memphis y otra en

Denver. La plantas de Memphis puede producir hasta 150 unidades al día,

la de Denver hasta 200 unidades al día. Los productos son enviados por

avión a Los Ángeles y Boston, en ambas ciudades, se requieren 130

unidades diarias. Existe una posibilidad de reducir los costos enviando

algunos productos en primer lugar a Nueva York o a Chicago, y luego a sus

destinos finales. La fábrica desea satisfacer la demanda al mínimo costo.

• La información de costos unitarios es la siguiente:

18


Ejemplo


7/23/2019 10_IND2209_Alumno_15


19


Ejemplo


Desde Hacia

Memphis Denver N.Y. Chicago L.A. Boston

Memphis 0 ‐ 8 13 25 28Denver ‐ 0 15 12 26 25

N.Y. ‐ ‐ 0 6 16 17

Chicago ‐ ‐ 6 0 14 16

L.A. ‐ ‐ ‐ ‐ 0 ‐

Boston ‐ ‐ ‐ ‐ ‐ 0

Memphis

Denver

Los Angeles

Boston

Nueva York

Chicago

7/23/2019 10_IND2209_Alumno_15


20


Ejemplo


Memphis

Denver

Los Angeles

Boston

Nueva York

Chicago

150

200

130

130

• ¿Está equilibrado?

• ¿Cómo equilibrarlo?

7/23/2019 10_IND2209_Alumno_15


• Seguir los siguientes pasos:

1. Si es necesario se debe agregar un punto de demanda dummy (con oferta 0 y

demanda igual al excedente) para balancear el problema. Los costos de envío al

punto dummy deben ser 0. Sea s la oferta total disponible.

2. Construir un tableau de transporte siguiendo las siguientes reglas:

i. Incluir una fila por cada punto de oferta y de transbordo

ii. Incluir una columna por cada punto de demanda y de transbordo

iii. Cada punto i de oferta debe poseer una oferta igual a su oferta original si. Cada punto j

de demanda debe poseer una oferta igual a su demanda original d j.

iv. Cada punto de transbordo debe tener una oferta igual a su oferta original + s y una

demanda igual a su demanda original + s . Como de ante mano no se conoce la

cantidad que transitará por cada punto de transbordo, la idea es asegurar que no se

exceda su capacidad. Se agrega s a la oferta y a la demanda del punto de transbordo

para no desbalancear el tableau.21



7/23/2019 10_IND2209_Alumno_15


22

Programación en redes - Problema de Transbordo

Ejemplo


N.Y. Chicago L.A. Boston Dummy Oferta

Memphis 8 13 25 28

0 150

Denver 15

12 26 25

0 200

N.Y. 0 6 16 17 0 350

Chicago 6 0 14 16

0 350

Demanda 350 350 130 130 90 1050/1050

7/23/2019 10_IND2209_Alumno_15


• Recordemos la formulación:

23

Programación en redes – Problema de Asignación


1

i

n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1

j

n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7/23/2019 10_IND2209_Alumno_15


• Modelo matemático:

24

Programación en redes – Problema de Asignación


7/23/2019 10_IND2209_Alumno_15


• Paso 1: Hacer reducción de filas, significa restar a cada fila el menor valor

perteneciente a la fila considerada.

• Paso 2: Hacer reducción de columnas.

• Paso 3: Por líneas horizontales y/o verticales se deben cubrir todos los ceros

en la matriz. El numero de líneas debe ser el menor numero de líneas que

cubra todos los ceros. Si el numero de líneas es igual a n=m, la solución óptima

quedará representada por los ceros en la matriz. En caso contrario, se debe

seleccionar el menor número de los no cubiertos por las líneas, el cual se debe

restar a los restantes números no cubiertos y sumar a aquellos números que

están cubiertos por la intersección de dos líneas.

Revisar nuevamente la operación de cubrir la totalidad de los ceros de la

matriz. 25

Programación en redes – Problema de Asignación –

Método Húngaro


7/23/2019 10_IND2209_Alumno_15


• Un determinado trabajo se compone de 4 tareas independientes entre si,

para llevar a cabo estas tareas se dispone de 4 operarios con habilidades

distintas, dependiendo de la tarea que le sea asignada. El cuadro siguiente

muestra los tiempos para realizar las tareas según sea la asignación

hombre trabajo. El problema es determinar la mejor asignación hombre‐

tarea que minimice el tiempo.

26


Método Húngaro - Ejemplo


Tarea

Hombre 1 2 3 4

A 14 18 7 10B 6 22 15 13

C 8 11 12 5

D 10 18 21 15

7/23/2019 10_IND2209_Alumno_15


• Se resta el número menor a cada fila

27




14 18 7 10 7 es el menor

6 22 15 13 6 es el menor

8 11 12 5 5 es el menor

10 18 21 15 10 es el menor

1, si el trabajador es asignado a la tarea

0, si noij

i j x

7 11 0 3

0 16 9 7

3 6 7 0

0 8 11 5

0 es el

menor6 es el

menor0 es el

menor0 es el

menor

7/23/2019 10_IND2209_Alumno_15


• Se resta el número menor a cada columna

28




7 11 0 3

0 16 9 73 6 7 0

0 8 11 5

0 es el

menor6 es el

menor0 es el

menor0 es el

menor

7 5 0 3

0 10 9 7

3 0 7 0

0 2 11 5

7/23/2019 10_IND2209_Alumno_15


• Se cubren los 0 por líneas

29




7 5 0 3

0 10 9 7

3 0 7 0

0 2 11 5

9 5 0 3

0 8 7 5

5 0 7 00 0 9 3

7/23/2019 10_IND2209_Alumno_15


• Solución óptima:

30




9 5 0 3

0 8 7 5

5 0 7 0

0 0 9 3

3 1 4 2 1

* 36

A B C D x x x x

z

9 5 0 3

0 8 7 5

5 0 7 0

0 0 9 3

10_ind2209_alumno_15

Documents