Download - 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
http://slidepdf.com/reader/full/10ind2209alumno15 2/30
• 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
http://slidepdf.com/reader/full/10ind2209alumno15 3/30
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)
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 4/30
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)
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 5/30
• Simplex de Transporte ‐ Ejemplo:
• Se dispone de la siguiente SBF:
5
Programación en redes
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 6/30
6
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 7/30
7
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 8/30
8
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 9/30
9
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 10/30
10
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 11/30
11
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 12/30
12
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 13/30
13
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 14/30
14
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 15/30
15
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 16/30
16
Programación en redes - Simplex de Transporte
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 17/30
• 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
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 18/30
• 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
Programación en redes – Problema de Transbordo
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 19/30
19
Programación en redes – Problema de Transbordo
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 20/30
20
Programación en redes – Problema de Transbordo
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
Memphis
Denver
Los Angeles
Boston
Nueva York
Chicago
150
200
130
130
• ¿Está equilibrado?
• ¿Cómo equilibrarlo?
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 21/30
• 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
Programación en redes – Problema de Transbordo
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 22/30
22
Programación en redes - Problema de Transbordo
Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 23/30
• Recordemos la formulación:
23
Programación en redes – Problema de Asignación
IND2209. Prof.: Pamela Álvarez M.
1
i
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
j
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 24/30
• Modelo matemático:
24
Programación en redes – Problema de Asignación
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 25/30
• 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
IND2209. Prof.: Pamela Álvarez M.
7/23/2019 10_IND2209_Alumno_15
http://slidepdf.com/reader/full/10ind2209alumno15 26/30
• 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
Programación en redes – Problema de Asignación –
Método Húngaro - Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 27/30
• Se resta el número menor a cada fila
27
Programación en redes – Problema de Asignación –
Método Húngaro - Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 28/30
• Se resta el número menor a cada columna
28
Programación en redes – Problema de Asignación –
Método Húngaro - Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 29/30
• Se cubren los 0 por líneas
29
Programación en redes – Problema de Asignación –
Método Húngaro - Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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
http://slidepdf.com/reader/full/10ind2209alumno15 30/30
• Solución óptima:
30
Programación en redes – Problema de Asignación –
Método Húngaro - Ejemplo
IND2209. Prof.: Pamela Álvarez M.
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