Este documento describe el modelo de programación lineal de transporte, el cual busca encontrar el mejor plan de distribución que minimice los costos totales de envío desde puntos de suministro hasta puntos de demanda. Se presentan los componentes del modelo, como oferta, demanda y costos de transporte, así como restricciones como no exceder la capacidad o satisfacer la demanda. También se explican algoritmos como la regla de la esquina noroeste y el método de aproximación de Vogel para encontrar una solución inicial factible al modelo. Finalmente, se inclu
Copyright:
Attribution Non-Commercial (BY-NC)
Formatos disponibles
Descargue como PPT, PDF, TXT o lea en línea desde Scribd
Este documento describe el modelo de programación lineal de transporte, el cual busca encontrar el mejor plan de distribución que minimice los costos totales de envío desde puntos de suministro hasta puntos de demanda. Se presentan los componentes del modelo, como oferta, demanda y costos de transporte, así como restricciones como no exceder la capacidad o satisfacer la demanda. También se explican algoritmos como la regla de la esquina noroeste y el método de aproximación de Vogel para encontrar una solución inicial factible al modelo. Finalmente, se inclu
Este documento describe el modelo de programación lineal de transporte, el cual busca encontrar el mejor plan de distribución que minimice los costos totales de envío desde puntos de suministro hasta puntos de demanda. Se presentan los componentes del modelo, como oferta, demanda y costos de transporte, así como restricciones como no exceder la capacidad o satisfacer la demanda. También se explican algoritmos como la regla de la esquina noroeste y el método de aproximación de Vogel para encontrar una solución inicial factible al modelo. Finalmente, se inclu
Copyright:
Attribution Non-Commercial (BY-NC)
Formatos disponibles
Descargue como PPT, PDF, TXT o lea en línea desde Scribd
Este documento describe el modelo de programación lineal de transporte, el cual busca encontrar el mejor plan de distribución que minimice los costos totales de envío desde puntos de suministro hasta puntos de demanda. Se presentan los componentes del modelo, como oferta, demanda y costos de transporte, así como restricciones como no exceder la capacidad o satisfacer la demanda. También se explican algoritmos como la regla de la esquina noroeste y el método de aproximación de Vogel para encontrar una solución inicial factible al modelo. Finalmente, se inclu
Copyright:
Attribution Non-Commercial (BY-NC)
Formatos disponibles
Descargue como PPT, PDF, TXT o lea en línea desde Scribd
Descargar como ppt, pdf o txt
Está en la página 1/ 39
Unidad 2 Programacin Lineal Aplicaciones
2.1 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. 2
2.1 Modelo de Transporte
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
Esquemticamente se podra ver como se muestra en la siguiente figura Fuentes Destinos
2.1 Modelo de Transporte
C11, X11 s1 1
d1
s2
2 . . .
2 . . .
d2
sm
m Cmn, Xmn
dn
donde
Xij: cantidad transportada desde la fuente i al destino j Cij: Costo del transporte unitario desde la fuente i al destino j 4
2.1 Modelo de Transporte
Modelo general de PL que representa al modelo de Transporte
minimizar
Z cij xij i 1 j 1
sa
x j 1 m
ij
si dj
i=1,2,...,m
x i 1
ij
j=1,2,...,n para toda i y j
xij o
El modelo implica que al menos la oferta debe ser igual a la demanda
2.1 Modelo de Transporte
Modelo general de PL que representa al modelo de Transporte
Modelo de transporte equilibrado: Oferta = Demanda
xij Si j 1 m
i=1, 2, 3,....,m
xij D j i 1
j=1, 2, 3,....,n
xij 0
para toda i y j
2.1 Modelo de Transporte
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
2.1 Modelo de Transporte
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:
2.1 Modelo de Transporte
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 (1) Amsterdan (2) Amberes (3) El Hevre Total
Cantidad de Motores 500 700 800 2000
Los costos ($) de transporte de un motor desde un origen a un destino son:
Al destino
2.1 Modelo de Transporte
Desde el origen
1 2 3
12 6 10
13 4 9
4 10 12
6 11 4
10
Construccin del modelo de PL
1. Variables de decisin
2.1 Modelo de Transporte
Xij = nmero de motores enviados del puerto i a la planta j i = 1, 2, 3 j = 1, 2, 3, 4
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
12
2.1 Modelo de Transporte
Solucin del Modelo de Transporte
2.1 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)
14
2.1 Modelo de Transporte
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
15
2.1 Modelo de Transporte
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.
Se inicia el proceso desde la esquina izquierda superior
2.1 Modelo de Transporte
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.
Valor FO: 400*12+100*13+700*4+100*9+200*12+500*4= $14.200
22
2.1 Modelo de Transporte
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.
23
2.1.2 Mtodo de aproximacin de Vogel
2.1 Modelo de Transporte
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.
24
2.1.2 Mtodo de aproximacin de Vogel
2.1 Modelo de Transporte
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
Es solucin factible? m + n - 1 = 6? SI Costo: 200*4+300*6+700*4+400*10+200*9+200*4 = $12.000
30
2.1.3. Mtodo del Costo Mnimo
Fundamento
2.1 Modelo de Transporte
Asignar la mayor cantidad de unidades a una ruta disponible de costo mnimo Algoritmo 1. 2. 3. 4. 5. Dada una tabla de transporte Asignar la mayor cantidad de unidades a la variable (ruta) con el menor costo unitario de toda la tabla. Tachar la fila o columna satisfecha. Ajustar oferta y demanda de todas las filas y columnas Si hay ms de una fila o columna no tachada repetir los puntos 2, 3 y 4
31
2.1.3. Mtodo del Costo Mnimo (cont.)
Ejemplo: Aplicar MCM a la tabla de transporte
2.1 Modelo de Transporte
Plantas Puertos 1 2 3 Demanda
Paso 2
1 12 6 10 400
2 13 4 9 900
3 4 10 12 200
4 6
Oferta 500 11 700 4 500 800 2000
Existen tres rutas costo mnimo. Elijamos la 1_3 Unidades a asignar = MIN(200,400) = 200 32
2.1.3. Mtodo del Costo Mnimo (cont.)
Paso 3: Tachar fila o columna (columna 3)
2.1 Modelo de Transporte
Plantas Puertos 1 2 3 Demanda
Paso 4 Paso 5
1 12 6 10 400
2 13
3 4 200
4 6
Oferta 300
500 700
4 9 900
10 12 0 200
11 4 500 800 2000
Ajustar ofertas y demandas (fila 1 y columna 3)
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 -> 3_4 ( 2_2) Unidades = MIN(500,800) = 500 Paso 3: Tachar columna 4 Paso 4: Tachar ajustar fila 3 y columna 4
2.1 Modelo de Transporte
Plantas Puertos 1 2 3 Demanda
Paso 5
1 12 6 10 400
2 13
3 4 200
4 6
Oferta 300
500 700
4 9 900
10 12 500
11 4 300
0 200
0 500
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 -> 2_2 Unidades = MIN(700,900) = 300 Paso 3: Tachar fila2 Paso 4: Tachar ajustar fila 2 y columna 2
2.1 Modelo de Transporte
Puertos 1 2 3 Demanda Paso 5
1 12 6
2 13
3 4 200
4 6
Oferta 300
500 700 800 2000
4 700
10 12 500
0 0
10
4 300
400 200 900
0 200
0 500
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_2 Unidades = MIN(200,300) = 200 Paso 3: Tachar columna 2 Paso 4: Tachar ajustar fila 3 y columna 2
2.1 Modelo de Transporte
Puertos 1 2 3 Demanda Paso 5
1 12 6
2 13
3 4 200
4 6
Oferta 300
500 700 800 2000
4 700
10 12 500
0 0 4 100 300
10 400
9 200 200 900
0 200
0 500
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 -> 3_1 Unidades = MIN(400,100) = 100 Paso 3: Tachar fila 3 Paso 4: Tachar ajustar fila 3 y columna 1
2.1 Modelo de Transporte
Puertos 1 2 3 Demanda Paso 5
1 12 6
2 13
3 4 200
4 6
Oferta 300
500 700 0
4 700
10 12 500
0 0 4 100 300
10 100 300 400
9 200 200 900
0 200
0 500
800 2000
An quedan ms de una fila o columna sin tachar. Ir a paso 2
37
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
2.1 Modelo de Transporte
Puertos 1 2 3 Demanda Paso 5
1 12 300
2 13
3 4 200
Oferta 6 0 300
500 700 0
6 700
4 9 200 200 900
10 12 500
0 0 4 100 300
10 100 300 400
0 200
0 500
800 2000
Queda slo una fila sin tachar. Terminar
38
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
