El documento describe un modelo de transporte para encontrar la mejor distribución de bienes desde puntos de suministro a puntos de demanda minimizando los costos de transporte. Se debe satisfacer la oferta y demanda en cada punto y solo enviar bienes por rutas válidas. El documento explica cómo construir el modelo matemático de programación lineal y presenta diferentes algoritmos para encontrar una solución óptima como la regla de la esquina noroeste y el método de aproximación de Vogel.
0 calificaciones0% encontró este documento útil (0 votos)
73 vistas75 páginas
El documento describe un modelo de transporte para encontrar la mejor distribución de bienes desde puntos de suministro a puntos de demanda minimizando los costos de transporte. Se debe satisfacer la oferta y demanda en cada punto y solo enviar bienes por rutas válidas. El documento explica cómo construir el modelo matemático de programación lineal y presenta diferentes algoritmos para encontrar una solución óptima como la regla de la esquina noroeste y el método de aproximación de Vogel.
El documento describe un modelo de transporte para encontrar la mejor distribución de bienes desde puntos de suministro a puntos de demanda minimizando los costos de transporte. Se debe satisfacer la oferta y demanda en cada punto y solo enviar bienes por rutas válidas. El documento explica cómo construir el modelo matemático de programación lineal y presenta diferentes algoritmos para encontrar una solución óptima como la regla de la esquina noroeste y el método de aproximación de Vogel.
El documento describe un modelo de transporte para encontrar la mejor distribución de bienes desde puntos de suministro a puntos de demanda minimizando los costos de transporte. Se debe satisfacer la oferta y demanda en cada punto y solo enviar bienes por rutas válidas. El documento explica cómo construir el modelo matemático de programación lineal y presenta diferentes algoritmos para encontrar una solución óptima como la regla de la esquina noroeste y el método de aproximación de Vogel.
Descargue como PPT, PDF, TXT o lea en línea desde Scribd
Descargar como ppt, pdf o txt
Está en la página 1/ 75
Modelo de Transporte
El objetivo general es encontrar el mejor plan de distribucin, es
decir, la cantidad que se debe enviar por cada una de las rutas desde los puntos de suministro hasta los puntos de demanda. El mejor plan es aquel que minimiza los costos totales de envo, produzca la mayor ganancia u optimice algn objetivo corporativo. Se debe contar con:
i) Nivel de oferta en cada fuente y la cantidad de demanda
en cada destino. ii) Costo de transporte unitario de mercadera desde cada fuente a cada destino. 1
Tambin es necesario satisfacer ciertas restricciones:
1. No enviar ms de la capacidad especificada desde cada punto de suministro (oferta). 2. Enviar bienes solamente por las rutas vlidas. 3. Cumplir (o exceder) los requerimientos de bienes en los puntos de demanda.
Grficamente: Para m fuentes y n destinos
Unidades de oferta
C11, X11
s1
d1
s2
d2
sm
dn
donde
Cmn, Xmn
Unidades de demanda
Esquemticamente se podra ver como se muestra en la siguiente
figura Fuentes Destinos
Xij: cantidad transportada desde la fuente i al destino j
Cij: Costo del transporte unitario desde la fuente i al destino j 3
Modelo general de PL que representa al modelo de Transporte
minimizar
Z cij xij i 1 j 1
sa
x j 1
ij
x i 1
ij
si
i=1,2,...,m
dj
j=1,2,...,n
xij o
para toda i y j
El modelo implica que al menos la oferta debe ser igual a la demanda
4
Modelo general de PL que representa al modelo de Transporte
Modelo de transporte equilibrado: Oferta = Demanda
x j 1
ij
x i 1
ij
Si
i=1, 2, 3,....,m
Dj
j=1, 2, 3,....,n
xij 0
para toda i y j 5
Aplicaciones del modelo de Transporte
El Modelo de Transporte no slo es aplicable al movimiento de
productos, sino que tambin, como modelo se puede aplicar a otras reas tales como: Planificacin de la Produccin Control de Inventarios Control de Proveedores Otras
Ejemplo: RPG tiene cuatro plantas ensambladoras en Europa. Estn ubicadas en Leipzig, Alemania (1);Nancy, Francia (2); Lieja, Blgica (3), y Tilburgo, Holanda (4). Las mquinas ensambladoras usadas en estas plantas se producen en Estados Unidos y se embarcan a Europa. Llegaron a los puertos de Amsterdan (1), Amberes (2) y El Havre (3). Los planes de produccin del tercer trimestre (julio a septiembre) ya han sido formulados. Los requerimientos (la demanda en destinos) de motores diesel E-4 son los siguientes:
Planta Cantidad de Motores (1) Leipzig 400 (2) Nancy 900 (3) Lieja 200 (4) Tilburgo 500 Total 2000 La cantidad disponible de mquinas E-4 en los puertos(oferta en orgenes) son: Puerto Cantidad de Motores (1) Amsterdan 500 (2) Amberes 700 (3) El Hevre 800 Total 2000
Los costos ($) de transporte de un motor
desde un origen a un destino son: Al destino Desde el origen
12
13
10
11
10
12
Construccin del modelo de PL
1. Variables de decisin Xij = nmero de motores enviados del puerto i a la planta j i = 1, 2, 3 j = 1, 2, 3, 4 2. Funcin Objetivo Minimizar Z = 12 X11 + 13 X12 + 4X13 + 6X14 + 6X21 + 4X22 + 10X23 + 11X24 + 10X31 + 9X32 + 12X34 + 4X14
10
3. Restricciones: 1) Oferta: La cantidad de elementos enviados no puede exceder la cantidad disponible X11 + X12 + X13 + X14 500 X21 + X22 + X23 + X24
700
X31 + X32 + X33 + X34
800
2) Demanda: Debe satisfacerse la demanda de cada planta
X11 + X21 + X31 400 X12 + X22 + X32 900 X13 + X23 + X33 200 X14 + X24 + X34 500 y de no negatividad Xij 0 para i=1, 2, 3; j= 1, 2, 3, 4 11
Solucin del Modelo de
Transporte
Algoritmos Especficos 2.1.1 Regla de la esquina noroeste (MEN) 2.1.2 Mtodo por aproximacin de Vogel (MAV) 2.1.3 Mtodo del costo mnimo (MCM) 2.1.4 Mtodo del paso secuencial y 2.1.5 DIMO (mtodo de distribucin modificada)
13
Descripcin de los algoritmos
La regla de la esquina noroeste, el mtodo de aproximacin de Vogel y el mtodo del costo mnimo son alternativas para encontrar una solucin inicial factible.
El mtodo del escaln y el DIMO son alternativas para
proceder de una solucin inicial factible a la ptima.
Por tanto, el primer paso es encontrar una solucin inicial
factible, que por definicin es cualquier distribucin de ofertas que satisfaga todas las demandas 14
Descripcin de los algoritmos
Una vez obtenida una solucin bsica factible, el algoritmo procede paso a paso para encontrar un mejor valor para la funcin objetivo. La solucin ptima es una solucin factible de costo mnimo
Para aplicar los algoritmos, primero hay que construir una
tabla de transporte.
15
Tabla Inicial Origen 1
1 C11
Destinos 2 3 C12 C13
4 C14
....
n C1n
C21
C22
C23
C24
....
C2n
C31
C32
C33
C34
....
C3n
...
....
.....
....
....
....
Cm1
Cm2
Cm3
Cm4
....
Cmn
Ofertas
Demanda
16
Tabla Inicial del Ejemplo
Plantas Puertos 1
2 12
3 13
4 4
Oferta 6 500
10
11 700
3 Demanda
10 400
9 900
12 200
4 500
800 2000
17
2.1.1 Regla de la esquina Noroeste
Se inicia el proceso desde la esquina izquierda superior Se ubican tantas unidades como sea posible en la ruta Cantidad de Unidades = Mnimo(disponibilidad, demanda) Las siguientes asignaciones se hacen o bien recorriendo hacia la derecha o bien hacia abajo. Las demandas se satisfacen recorriendo sucesivamente de izquierda a derecha y las ofertas se destinan recorriendo de arriba hacia abajo. 18
Primera asignacin Plantas Puertos 1
2 12
3 13
4 4
Oferta 6
400 2
100 6
10
500
11 700
3 Demanda
10 0 400
9 900
12 200
4 500
800 2000
19
Hasta cuarta asignacin
Plantas Puertos 1
2 12
400 2
3 13
4 4
Oferta 6
100 6
10
Demanda
10
100 0 400 0 900
12 200
500
700
700
800 2000
11
700 3
100
4 500
20
Esquina Noroeste: Solucin final factible
Plantas Puertos 1
2 12
400 2
3 13
4 4
Oferta 6
100 6
10
Demanda
10
12
500
700
800 2000
11
700 3
100
100 200 500 0 400 0 900 200 500
Valor FO: 400*12+100*13+700*4+100*9+200*12+500*4= $14.200
21
2.1.2 Mtodo de aproximacin de
Vogel (MAV) MAV usa informacin de costos mediante el concepto de costo de oportunidad para determinar una solucin inicial factible. Seleccionar en una fila la ruta ms barata y la que le sigue. Hacer su diferencia (penalidad), que es el costo adicional por enviar una unidad desde el origen actual al segundo destino y no al primero. En nuestro caso, para el puerto1, C13 y C14; Penalidad = 6 - 4 MAV asigna un costo de penalidad por no usar la mejor ruta en esta fila. 22
2.1.2 Mtodo de aproximacin de Vogel
Lo anterior se repite para cada fila y cada columna, esto es, determinar todas las penalidades Los pasos iterativos de MAV son los siguientes: 1. Identificar la fila o columna con la mxima penalidad. 2.Colocar la mxima asignacin posible a la ruta no usada que tenga menor costo en la fila o columna seleccionada en el punto 1 (los empates se resuelven arbitrariamente) 3. Reajustar la oferta y demanda en vista de esta asignacin. 4. Eliminar la columna en la que haya quedado una demanda 0 (o la fila con oferta 0), de consideraciones posteriores. 5. Calcular los nuevos costos de penalidad.
23
2.1.2 Mtodo de aproximacin de Vogel
El MAV contina aplicando este proceso en forma sucesiva
hasta que se haya obtenido una solucin factible.
Los resultados obtenidos se muestran en las siguientes tablas
24
2.1.2 Mtodo de aproximacin de Vogel
Paso 0: Clculo de penalidades Plantas Puertos 1
2 12
3 13
Oferta
Penalidades 2
6 500
10
11
2 700
3 Demanda Penalidades
10
12
400
900
200
500
5 800 2000
Paso 1: Identificar mxima penalidad (fila o columna)
Calculadas todas las penalidades, la mayor corresponde a la columna 3 (penalidad = 6) 25
2.1.2 Mtodo de aproximacin de Vogel
Paso 2: Asignacin de unidades (MIN(oferta,demanda)) Paso 3:Reajuste de oferta y demanda Plantas Puertos 1
Paso 5: Calcular los nuevos costos de penalidad Plantas Puertos 1
2 12
3 13
4 4
Oferta 6
200 2
300 10
Penalidades 6 500
11
2 700
3 Demanda Penalidades
10
400
900
12 0 200
4 500
5 800 2000
28
2.1.2 Mtodo de aproximacin de Vogel
Repitiendo los pasos anteriores, finalmente se llega a la siguiente solucin Plantas Puertos 1
2 12
3 13
4 4
200 2
Oferta 6
300 10
300
500
700
11
700 3
10 400
Demanda
9 200
400
900
12
200 600 800 0 200 200 500 2000
Es solucin factible? m + n - 1 = 6? SI Costo: 200*4+300*6+700*4+400*10+200*9+200*4 = $12.000 29
2.1.3. Mtodo del Costo Mnimo
Fundamento Asignar la mayor cantidad de unidades a una ruta disponible de costo mnimo Algoritmo 1. Dada una tabla de transporte 2. Asignar la mayor cantidad de unidades a la variable (ruta) con el menor costo unitario de toda la tabla. 3. Tachar la fila o columna satisfecha. 4. Ajustar oferta y demanda de todas las filas y columnas 5. Si hay ms de una fila o columna no tachada repetir los puntos 2, 3 y 4 30
2.1.3. Mtodo del Costo Mnimo (cont.)
Ejemplo: Aplicar MCM a la tabla de transporte Plantas Puertos 1
An quedan ms de una fila o columna sin tachar. Ir a paso 2
33
2.1.3. Mtodo del Costo Mnimo (cont.)
Paso 2: Ruta de costo menor -> 2_2 Unidades = MIN(700,900) = 300 Paso 3: Tachar fila2 Paso 4: Tachar ajustar fila 2 y columna 2 Puertos 1
2 12
3 13
4 4
Oferta 6
200
10
10
12
Paso 5
400 200 900
0 200
700
4 500
Demanda
500
700
300
0 500
300
800 2000
An quedan ms de una fila o columna sin tachar. Ir a paso 2
34
2.1.3. Mtodo del Costo Mnimo (cont.)
Paso 2: Ruta de costo menor -> 3_2 Unidades = MIN(200,300) = 200 Paso 3: Tachar columna 2 Paso 4: Tachar ajustar fila 3 y columna 2 Puertos 1
2 12
3 13
4 4
Oferta 6
200
10
10
12
200
Demanda
Paso 5
400 200 900
700
4 100 500
0 200
500
700
300
0 500
300
800 2000
An quedan ms de una fila o columna sin tachar. Ir a paso 2
35
2.1.3. Mtodo del Costo Mnimo (cont.)
Paso 2: Ruta de costo menor -> 3_1 Unidades = MIN(400,100) = 100 Paso 3: Tachar fila 3 Paso 4: Tachar ajustar fila 3 y columna 1 Puertos 1
2 12
3 13
4 4
Oferta 6
200
10
10
Demanda
Paso 5
100
200
300 400
200 900
12
700
4 100 500
0 200
500
700
300
0 500
300
800 2000
An quedan ms de una fila o columna sin tachar. Ir a paso 2
36
2.1.3. Mtodo del Costo Mnimo (cont.)
Paso 2: Ruta de costo menor -> 1_1 Unidades = MIN(300,300) = 300 Paso 3: Tachar fila 1 columna 1 (slo una de ellas) Paso 4: Tachar ajustar fila 1 y columna 1 Puertos 1
2 12
3 13
300
4 4
Oferta 6 0
200
10
10
Demanda
Paso 5
100
200
300 400
200 900
500
700
700
300
12
4 100 500
0 200
0 500
300
800 2000
Queda slo una fila sin tachar. Terminar
37
2.1.3. Mtodo del Costo Mnimo (cont.)
Es solucin factible? m + n - 1 = 6? SI Costo: 300*12+200*4+700*4+100*10+200*9+500*4 = $12.000 Comparacin de los resultados Mtodo MEN MAV MCM
Rutas 6 6 6
Costo $14.200 $12.000 $12.000
Conclusin Los tres mtodos entregan soluciones bsicas factibles, pero ninguno asegura que la solucin sea ptima. 38
2.1.4. Mtodo de Pasos Secuenciales
Fundamento Este mtodo comienza con una solucin inicial factible. En cada paso se intenta enviar artculos por una ruta que no se haya usado en la solucin factible actual, en tanto se elimina una ruta usada actualmente. En cada cambio de ruta debe cumplirse que: 1. La solucin siga siendo factible y 2. Que mejore el valor de la funcin objetivo El procedimiento termina cuando no hay cambio de rutas que mejoren el valor de la funcin. 39
2.1.4. Mtodo de pasos secuenciales (cont..)
Algoritmo
1 2
Usar la solucin actual (MEN, MAV o MCM) para crear una trayectoria nica del paso secuencial. Usar estas trayectorias para calcular el costo marginal de introducir a la solucin cada ruta no usada. Si todos los costos marginales son iguales o mayores que cero, terminar; se tendr la solucin ptima. Si no, elegir la celda que tenga el costo marginal ms negativo (empates se resuelven arbitrariamente)
Usando la trayectoria del paso secuencial, determine el mximo nmero
de artculos que se pueden asignar a la ruta elegida en el punto 2 y ajustar la distribucin adecuadamente.
Regrese al paso 1 40
2.1.4. Mtodo de pasos secuenciales (cont..)
Algoritmo
Paso 1
a) Ponga un signo + en la celda de inters no ocupada
b) Ponga un signo - en una celda usada de la misma fila c) Ponga un + en una celda usada de la misma columna El proceso contina alternando los signos + y - tanto en las filas como en las columnas hasta que se obtenga una sucesin de celdas (trayectoria) que satisfagan dos condiciones 1. Hay un signo + en la celda desocupada original de inters, y 2. Cualquier fila o columna que tenga un signo + debe tener tambin un signo - y viceversa. 41
2.1.4. Mtodo de pasos secuenciales (cont..)
Paso 1
Algoritmo
Plantas Puertos 1
2 12
400 2
3 13
4 4
Oferta 6
100 6
10
Demanda
10
12
500
700
800 2000
11
700 3
100
100 200 500 0 400 0 900 200 500
Solucin bsica factible obtenida aplicando el mtodo de la Esquina Noroeste
42
2.1.4. Mtodo de pasos secuenciales (cont..)
Paso 1
Algoritmo
Plantas Puertos 1
2 12
400 2
100 6
3 13 4
4 4 + 10
Oferta 6
Demanda
10
500
700
800 2000
11
700 3
100
12 4 100 + 200 - 500 0 400 0 900 0 200 0 500
Trayectoria 1: +C13-C12+C32-C33 43
2.1.4. Mtodo de pasos secuenciales (cont..)
Algoritmo Paso 1 Plantas Puertos 1
2 12
400
100
3 13 4
4 4 + 10
Oferta 6
Demanda
10
500
700
800 2000
11
700 3
100
12 4 100 + 200 - 500 0 400 0 900 0 200 0 500
Costos de las Trayectorias
1: +(4)-(13)+(9)-(12)= -12
2: +(6)-(13)+(9)-(4) = -2
3: +(6)-(4)+(13)-(12)=
4: +(10)-(4)+(9)-(12) = 3
5: +(11)-(4)+(9)-(4) = 12
6: +(10)-(9)+(13)-(12)= 2 44
2.1.4. Mtodo de pasos secuenciales (cont..)
Algoritmo
Paso 2
1: +(4)-(13)+(9)-(12)= -12
2: +(6)-(13)+(9)-(4) = -2
3: +(6)-(4)+(13)-(12)=
4: +(10)-(4)+(9)-(12) = 3
5: +(11)-(4)+(9)-(4) = 2
6: +(10)-(9)+(13)-(12)= 2
La solucin factible NO es ptima !!
Se selecciona la trayectoria 1 (costo marginal ms negativo)
45
2.1.4. Mtodo de pasos secuenciales (cont..)
Algoritmo
Paso 3 (Generacin de la nueva tabla)
Cuntas unidades se pueden asignar a la ruta elegida?
Accin
Ruta
Aumentar 1 unidad
1_3
Disminuir 1 unidad
1_2
Aumentar 1 unidad
3_2
Disminuir 1 unidad
3_3
Unidades disponibles en celdas decrecientes 100 200
Solucin factible ptima!!! $12.000 Compare esta solucin con la obtenida con MAV y MCM ...? 53
2.1.5. Mtodo de Distribucin Modificada (DIMO)
Algoritmo 1. Usar la solucin actual (NE, MAV o MCM) y las siguientes operaciones (a) y (b) para determinar el costo marginal de enviar material para cada una de las rutas no usadas.
Asociar a cada fila un ndice ui y a cada columna un ndice vj
a) Hacer u1 = 0. Encuntrese los ndices de las filas u2, ..., um y los ndices de las columnas v1, ...., vn tales que cij = ui + vj para cada celda usada. b) Sea eij = cij - (ui+vj) para cada celda no usada; eij ser el costo marginal de introducir la celda (ruta) i, j a la solucin. Los pasos 2 a 4 son los mismos que en el mtodo secuencial.
54
2.1.5. Mtodo de Distribucin Modificada (DIMO)
Aplicar el algoritmo al problema en estudio y comparar resultados obtenidos con los mtodos anteriores Comentar resultados Qu explica que existan dos soluciones ptimas factibles?
55
2.1.5. Mtodo de Distribucin Modificada (DIMO)
Aplicacin
vj Plantas
Puertos 1
2 12
400
13
Oferta
100
ui
10
Demanda
10
12 200 200
100 0 400 0 900
Paso 0: Asociar ndices
Costo por Ruta en uso motor ($) 11 12
500
700
11
700 3
100
4 500 700 800 500 2000
Ecuacin u1 + v1 = 12
12
13
u1 + v2 = 13
22
u2 + v2 = 4
32
u3 + v2 = 9
33
12
34
u3 + v3 = 12 u3 + v4 = 4
56
2.1.5. Mtodo de Distribucin Modificada (DIMO)
Paso1.a) Solucionar la ecuacin Existen 6 ecuaciones y siete variables entonces se hace u 1 = 0 (puede ser cualquiera) y se determina el resto de los ndices
v1 = 12
v2 = 13
u2 = - 9
u3 = -4
v3 = 16 v4 = 8
Paso 1.b) Calcular los costos marginales para cada celda no usada. eij = cij - (ui + vj)
No hay costos negativos por lo tanto es ptima VO = 300*12+200*4+700*4+100*10+200*9+500*4=$12.000 67
2.1.6. Modelo de Transporte: Situaciones
Especiales 1. Solucin en problemas de maximizacin de transporte 2. El caso en que la oferta excede a la demanda. 3. Eliminacin de rutas inaceptables. 4. Degeneracin en problemas de transporte. 5. Propiedades especiales del modelo de transporte
68
2.1.6. Modelo de Transporte: Situaciones
Especiales 1. Solucin en problemas de maximizacin de transporte.
a) Se utilizan los beneficios marginales en lugar de los costos.
Se asignar unidades a la celda que tenga el mayor valor marginal y el procedimiento concluir cuando todas las rutas tengan valores marginales negativos. b) Convertir la tabla de beneficios en una tabla de costo: Se busca el beneficio mayor, en cada celda se le resta al mayor el beneficio de la celda. Ejemplo: 69
2.1.6. Modelo de Transporte: Situaciones
Especiales Tabla de beneficios Destinos 2
1 Fuentes
1 2 3
Tabla de costo
14
19
12
17
19
15
16
20
11
Destinos 2
1 Fuentes
1 2 3
Mayor = 20
70
2.1.6. Modelo de Transporte: Situaciones
Especiales 2. El caso en que la oferta excede a la demanda. Se utiliza un destino ficticio en la tabla de transporte. Se considera como nulo el costo de enviar una unidad a dicho destino desde cada una de las fuentes (orgenes). Si la demanda es mayor que la oferta el problema no tiene solucin factible, sin embargo el administrador podra abastecer toda la demanda que sea posible a un costo mnimo. Se utiliza un origen ficticio. El costo de abastecer cualquier destino desde dicho origen ser cero. Sin embargo podra haber un cargo por orden no cubierta. 71
2.1.6. Modelo de Transporte: Situaciones
Especiales 3. Eliminacin de rutas inaceptables. Se asocia a una ruta no aceptable un costo lo suficientemente alto para que no sea atrayente la ruta en cuestin. El costo M Por ejemplo: producir en abril para vender en febrero del mismo ao. 4. Degeneracin en problemas de transporte. Se dice que un problema se degenera cuando hay menos de m + n - 1 rutas ocupadas. Esto puede ocurrir cuando simultneamente se satisface una demanda y se agota una oferta. 72
2.1.6. Modelo de Transporte: Situaciones
Especiales 5. Propiedades especiales del modelo de transporte
Todo problema de transporte es posible resolverlo mediante
algoritmos que usan slo la adicin y la sustraccin.
Si todas las ofertas y demandas tienen valores enteros en un
problema de transporte, los valores ptimos de las variables de decisin sern tambin enteros. 73
Ejercicios 1 Suponer que se tienen tres fbricas M1, M2 y M3 que producen 39, 48 y 33 toneladas respectivamente, de un cierto producto que debe llevarse a cuatro destinos, D1, D2, D3 y D4, los cuales requieren 40, 37, 18 y 25 toneladas. Los costos estn dados por la siguiente tabla: D1
D2
D3
D4
M1
M2
M3
5 74
2 Planificacin de la produccin:
Cunto hay que producir en cada periodo para satisfacer la
demanda al mnimo costo (tanto de produccin como de almacenaje)?. Supuesto: No existe inventario inicial ni final. Plantear el problema usando el modelo de transporte. Encuentre las respuestas usando Solver. 75
