View
224
Download
2
Category
Preview:
Citation preview
UNIDAD DOS
MODELOS DE
TRANSPORTE
Ing. César Urquizú
Ing. César Urquizú
Modelos de Transporte
Método de la Esquina Noroeste
Método del Costo Mínimo o Menor
Método de Aproximación de Vogel (MAV)
Método del Banquillo
Método de Multiplicadores
Modelo de ASIGNACION
Modelo de Transporte
• Existen problemas que se distinguen en la estructura especial de sus restricciones cuando se
formulan con programación lineal. Aquellos relacionados con la distribución de bienes, los cuales
deben enviarse desde lugares de suministro: ciudades, fábricas o plantas, conocidos como nodos
origen hasta lugares de demanda: ciudades, estaciones, tiendas, llamados nodos destino; es
posible que se haga a través de lugares intermedios: ciudades, estaciones, almacenes, llamados
transbordos.
• El objetivo general consiste en hallar el mejor plan de distribución de unidades por cada una de
las rutas, desde los orígenes hasta los lugares de demanda con el menor esfuerzo (costo) o bien
con el mayor beneficio (utilidad). El problema de red de distribución se sujeta a las necesarias
restricciones de:
• Los envíos se sujetan al uso de rutas especificadas.
• Una red de distribución se construye con tantos nodos ( i ) como lugares de oferta se tengan y
tantos nodos ( j ) como lugares de demanda. También debe conectarse con ramas, con o sin
flecha, entre los pares de nodos que convenga para las rutas válidas. Cada uno de los nodos y
ramas deben tener los valores que informan (oferta, demanda, capacidad, costo), sobre el estado
de la red estudiada.
• La red de distribución más aplicada se conoce como problema de transporte simple en que se
busca el costo mínimo de transporte directo al llevar mercancías desde lugares origen hasta
lugares destino (sin transbordos); pero el modelo se puede extender de manera que se aplique
en situaciones en que no hay flujos, como el control de inventario en áreas de producción;
también en programación del empleo y asignación de personal a funciones y tareas.
• El problema de transporte simple es un caso especial de la
programación lineal. Es aplicable en la distribución de bienes de
consumo, de servicios eléctrico y de agua, en la asignación de
equipo a la producción; también tiene aplicaciones de otra
naturaleza como es, el inventario industrial o la asignación uno a
uno, de ahí la importancia del modelo.
• Definición: Dada una red de nodos, parte de los cuales son m
orígenes con oferta de algún producto, otra parte de los nodos son
n destinos con demanda b j del mismo bien. Se trata de satisfacer
las demandas aprovechando las ofertas para lo cual se tiene el
respectivo costo unitario C i j de transporte, y el objetivo de que la
suma de costos sea mínimo. La distribución de bienes debe permitir
el cumplimiento de cada demanda con uno o más orígenes,
• Xij
Cij
ai
bj
Número de unidades transportadas
Costo del transporte por unidad en
la ruta (i,j)Número de unidades requeridas en
el destino J
Número de unidades disponibles
para ofrecer
Para usar el Algoritmo de Transporte es necesario que las
cantidades ofrecidas del bien o servicio sean iguales a las
cantidades demandadas. Como esto no ocurre siempre en la
práctica, se hace necesario BALANCEAR el modelo, es decir igualar las
cantidades ofrecidas con las Demandadas.
Cuando la Oferta excede a la Demanda se debe crear un destino ficticio para
que absorba la cantidad en exceso de la oferta. El costo de transporte
unitario en ese destino será de valor cero puesto que realmente no se
transportará ninguna cantidad del bien o servicio. Cualquier cantidad que
quede en ese destino informará la cantidad del bien o servicio que ha
quedado disponible, sin transportar, en el origen respectivo.
Cuando la Demanda excede a la Oferta se debe crear un origen
ficticio para que provea la cantidad en exceso de la demanda. El
costo de transporte unitario en ese origen será de valor cero, ya que
realmente no se transportará ninguna cantidad del bien o servicio desde
ese origen, no existente en la realidad. Cualquier cantidad que quede en
ese origen informará la cantidad del bien o servicio que no se ha
transportado al destino respectivo, es decir, la demanda que ha quedado
insatisfecha en el destino respectivo.
Método de la esquina Noroeste
Es el método más fácil y el menos probable para dar una buena solución inicial y de “bajo costo” porque ignora la magnitud relativa de los costos Cij. Normalmente, en los problemas de programación lineal, se tiene una variable básica para cada restricción. En los problemas de transporte con m recursos y n destinos el número de restricciones funcionales es m + n. Sin embargo, el número de variables básicas = m + n - 1
Pasos
1.- Seleccionar la celda de la esquina noroeste (esquina superior izquierda) para envío.
2.- Efectuar el más grande envío como pueda en la celda de la esquina noroeste. Esta operación agotará completamente la disponibilidad de suministros en un origen o los requerimientos de demanda en un destino.
3.- Corrija los números de suministro y los requerimientos para reflejar lo que va quedando de suministro y requerimiento y regresar al paso 1.
Ejemplo:
• Una empresa cuenta con tres plantas productoras con una producción de 1000 unidades en la planta 1, 1200 unidades en la planta 2 y 600 unidades en la planta 3. Se hará una distribución por medio de camiones a cuatro lugares los cuales tienen una demanda de:
• Destino 1= 800 unidades, Destino 2 = 300 unidades, Destino 3 = 450 unidades y Destino 4 = 1250 unidades se pide que encuentre el costo optimo por medio del metodo de la Esquina Noroeste.
• A continuación los costos por unidad
1 2 4 5
2 3 4 3
4 5 6 8
D1 D 2 D 3 D 4 Oferta
Planta 1 1 2 4 5 1000
Planta 2 2 3 4 3 1200
Planta 3 4 5 6 8 600
Demanda 800 300 450 1250 2800
800 200
000
ESQUEMATIZACIÓN ESQUINA NOROESTE
D1 D2 D3 D4 Oferta
Planta 1 1
800
2 4 5
200
Planta 2 2 3 4 3 1200
Planta 3 4 5 6 8 600
Demand
a 000 300450 1250 2800
200000
100
D1 D2 D3 D4 Oferta
Planta 1 800 12
200
4 5
000
Planta 2 2 3 4 3 1200
Planta 3 4 5 6 8 600
Demanda000 100 450 1250 2800
100 1100
000
D1 D2 D3 D4 Oferta
Planta 1 800 12
200
4 5
000
Planta 2 2 3
100
4 3 1100
Planta 3 4 5 6 8 600
Demanda000 000
450 1250 2800
450 650
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5
000
Planta 2 2 3
100
4
450
3
650
Planta 3 4 5 6 8 600
Demanda000 000 450 1250
2800
650 000
600
D1 D2 D3 D4 Oferta
Planta 1800 1 200 2
4 5
000
Planta 2 2
100 3 450 4 650 3 000
Planta 3 4 5 6 8
600
Demanda000 000 000 600 2800
600 000
000
D1 D2 D3 D4 Oferta
Planta 1 800 1 200 2 4 5 1000
Planta 2 2 100 3 450 4 650 3 1200
Planta 3 4 5 6 600 8 600
Demanda 800 300 450 1250 2800
CT = 800*1 + 200*2 + 100*3 + 450*4 + 650*3 + 600*8 = Q10,050
METODO DE COSTO MÍNIMO
Este es un procedimiento que se utiliza tomando como base a las rutas que tengan el menor costo:
PROCEDIMIENTO
1.- Asígnese el valor más grande posible a la variable con menor costo unitario de toda la tabla. (Los empates se rompen arbitrariamente). Táchese el renglón o columna satisfecho. (Como en el método de la esquina noroeste, si una columna y un renglón se satisfacen de manera simultánea, sólo una puede tacharse).
2.- Después de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repítase el proceso asignando el valor más grande posible a la variable con el costo unitario no tachado más pequeño. El procedimiento esta completo cuando queda exactamente un renglón o una columna sin tachar.
D1 D2 D3 D4 Oferta
Planta 1 1 2 4 5 1000
Planta 2 2 3 4 3 1200
Planta 3 4 5 6 8 600
Demanda 800 300 450 1250 2800
800 200
000
ESQUEMATIZACIÓN COSTO MÍNIMO
D1 D2 D3 D4 Oferta
Planta 1 1
800
2 4 5
200
Planta 2 2 3 4 3 1200
Planta 3 4 5 6 8 600
Demanda 000 300 450 1250 2800
200 000
100
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5 000
Planta 2 2 3 4 3 1200
Planta 3 4 5 6 8 600
Demanda 000 100 450 1250 2800
1200 000
50
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5 000
Planta 2 2 3 4 3
1200000
Planta 3 4 5 6 8 600
Demanda 000 100 450 50 2800
100 500
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5 000
Planta 2 2 3 4 3
1200000
Planta 3 4 5
100
6 8 500
Demanda 000 000 450 50 2800
450 50
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5 000
Planta 2 2 3 4 3
1200000
Planta 3 4 5
100
6
450
8 50
Demanda 000 000 000 50 2800
50 000
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5 1000
Planta 2 2 3 4 3
1200
1200
Planta 3 4 5
100
6
450
8
50
600
Demanda 800 300 450 1250 2800
CT = 800*1 + 200*2 + 100*5 + 450*9 + 1200*3 + 50*8 = Q8,400.00
Este método es heurístico y sueleproducir una mejor solución inicialque los métodos anteriores. Dehecho, suele producir una solucióninicial óptima, o próxima al nivelóptimo a través de penalizaciones
APROXIMACIÓN DE VOGEL
PROCEDIMIENTO
1.- Evalúese una penalización para cada renglón (columna)restando el menor elemento de costo del renglón(columna) del elemento de costo menor siguiente en elmismo renglón (columna).
2.- Identifíquese el renglón o columna con mayorpenalización, rompiendo empates en forma arbitraria.Asigne el mayor valor posible a las variables con el costomás bajo del renglón o columna seleccionado.Ajústese la oferta y la demanda y táchese el renglón ocolumna satisfecho. Si un renglón y una columna sesatisfacen al mismo tiempo, sólo uno de ellos se tacha yal renglón (columna) restante se le asigna unaoferta (demanda) cero. Cualquier renglón o columnacon oferta o demanda cero no debe utilizarse paracalcular penalizaciones futuras (en el paso 3).
3.
a) si sólo hay un renglón o columna sin tachar, deténgase. b) si sólo hay un renglón (columna) con oferta
(demanda) positiva sin tachar, determínese las variables básicas del renglón ( columna) a través
del método de costo mínimo.c) si todos los renglones o columnas sin tachar
tiene oferta y demanda cero asignadas,determínese las variables básicas cero a través del método de costo mínimo. Deténgase.
d) De lo contrario, calcule las penalizaciones de los renglones y columnas no tachados y después diríjase al paso 2. (Obsérvese que los renglones y columnas con oferta y demanda cero asignadas no deben utilizarse para determinar estas penalizaciones).
D1 D2 D3 D4 Oferta I
Planta 1 1 2 4 5 1000 2-1=1
Planta 2 2 3 4 3 1200 3-2=1
Planta 3 4 5 6 8 600 5-4=1
Demand
a
800 300 450 1250 2800
I 2-1=1 3-2=1 6-4=2 5-3=2
1200 000
50
ESQUEMATIZACIÓN APROXIMACIÓN DE VOGEL
D1 D2 D3 D4 Oferta II
Planta 1 1 2 4 5 1000 2-1=1
Planta 2 2 3 4 3
1200 000*****
Planta 3 4 5 6 8 600 5-4=1
Demand
a
800 300 45050
2800
II 4-1=3 5-2=3 6-4=2 8-5=3
800 200
000
D1 D2 D3 D4 Oferta III
Planta 1 1
800
2 4 5 200 2-1=1
Planta 2 2 3 4 3
1200000 *****
Planta 3 4 5 6 8 600 6-5=1
Demanda 000 300 45050
2800
III ***** 5-2=3 6-4=2 8-5=3
200 000
100
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5
000
Planta 2 2 3 4 3
1200000
Planta 3 4 5 6 8 600
Demanda 000 100 450 50 2800
100 500
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5
000
Planta 2 2 3 4 3
1200000
Planta 3 4 5
100
6 8
500
Demanda 000 000 450 50 2800
450 50
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5
000
Planta 2 2 3 4 3
1200000
Planta 3 4 5
100
6
450
8
50
Demand
a000 000 000 50 2800
50 000
000
D1 D2 D3 D4 Oferta
Planta 1 1
800
2
200
4 5 1000
Planta 2 2 3 4 3
12001200
Planta 3 4 5
100
6
450
8
50600
Demanda 800 300 450 1250 2800
CT = 800*1 + 200*2 + 100*5 + 450*6 + 1200*3 + 50*8 = Q 8,400 .00
Recommended