M.C. Ing. Julio Rito Vargas Avilés.
Universidad Nacional de Ingeniería
Sede: UNI-Norte
II Semestre 2008
Investigación de Operaciones I
martes, 21 de octubre de 2008
El Problema del Transporte
El Problema de Transporte
• Un tipo particular de problema en la ProgramaciónLineal, es el denominado problema del transporte.
• En muchas aplicaciones se debe determinar lamanera óptima de transportar bienes.
• Sin embargo, algunas de sus aplicaciones más importantes (como la programación de la producción) no tienen que ver nada con el transporte.
El Problema de Transporte
• Los problemas de asignación incluye aplicacionescomo las asignaciones de personas (o recursos) atareas. Aunque sus usos parece diferir de los delproblema de transporte, se verá que los asuntos deasignación se pueden considerar un caso especial delproblema de transporte.
• Después de presentar un problema modelo detransporte, se presentará la estructura especial de esemodelo y se resolverán ejemplos adicionales de susaplicaciones así como el simplex de transporte.
El Problema de Transporte
• Los problemas de asignación incluye aplicacionescomo las asignaciones de personas (o recursos) atareas. Aunque sus usos parece diferir de los delproblema de transporte, se verá que los asuntos deasignación se pueden considerar un caso especial delproblema de transporte.
• Después de presentar un problema modelo detransporte, se presentará la estructura especial de esemodelo y se resolverán ejemplos adicionales de susaplicaciones así como el simplex de transporte.
El Problema de Transporte
• El problema del transporte trata que un ciertoproducto debe enviarse en determinadascantidades
u1, . . . , um, desde cada uno de m orígenes, y debe recibirse en cantidades v1, . . . , vn, en cada uno de n destinos.
El problema consiste en determinar las cantidades
Xij , que deben enviarse desde el origen i aldestino j, para conseguir minimizar el coste delenvío.
El Problema de Transporte
Los cuatro elementos principales de este problema son:
Datos
m: el número de orígenes
n: el número de destinos
Ui: la cantidad que debe enviarse desde el origen i
Vj : la cantidad que debe ser recibida en el destino j
Cij : el coste de envío de una unidad de producto desde el origen i al destino j
El Problema de Transporte
Variables
Xij : la cantidad que se envía desde el origen i al destino j.
Xij ≥ 0; i = 1, . . . , m; j = 1, . . . , n
Esto implica que la dirección de envío del producto está prefijada
desde los distintos orígenes hasta los destinos. No obstante, otras
hipótesis podrían tenerse en cuenta. Por ejemplo, podría no limitarse
el signo de las variables Xij € R, si no se quiere predeterminar cuáles
son los puntos de partida y llegada.
Restricciones. Las restricciones de este problema son:
0
ij
jij
iij
x
dx
sx
Ejemplo: Problema de Transporte
• Uno de los productos más de la P & T Company
es chícharo enlatado. Los chícharos se
preparan en tres enlatadoras cercanas a
Bellingham en Washington; a Eugene en
Oregon; y Albert Lea en Minnesota y después
se envián por camión a cuatro almacenes de
distribución. Sacramento – California; Salt Lake
City – Utah; Rapid City – South Dakota; y
Albuquerque – Nuevo México en el oeste de los
Estados Unidos, como se muestra en el mapa.
Almacenes
Enlatadores
Ejemplo: Problema de Transporte
• Debido a que los costos de embarque constituyen un
gasto importante, la administración ha iniciado un
estudio para reducirlos a su mínima expresión. Se ha
estimado la producción de cada enlatadora durante la
próxima temporada y se asignado a cada almacén
cierta cantidad de la producción total de chícharos. En la
tabla siguiente se muestra la información en unidades
de carga de camión, junto con el costo de transporte de
camión por camión cargado de cada combinación
enlatadora-almacén.
.
Datos de transporte de P & T Co.
Coste de Embarque $ por carga Producción
Almacén
1 2 3 4
Enlatadora 1 464 513 654 867 75
Enlatadora 2 352 416 690 791 125
Enlatadora 3 995 682 388 685 100
Asignación 80 65 70 85
Representación de Red del
problema
E3
E2
E1A1
A2
A3
A4
464
654
513
867
352
416
690
791685
682
995
388
75
100
125
80
65
70
85
Optimizando
Min
s. a:
m
i
n
j
ijij xcZ1 1
85
70
65
80
100
125
75
342414
332313
322212
312111
34333231
24232221
14131211
xxx
xxx
xxx
xxx
xxxx
xxxx
xxxx
3433
3231242322
2114131211
685388
682995791690416
352867654513464
xx
xxxxx
xxxxxZ
Matriz
Solución
Solución Gráfica
2. Constructora. ¿Qué cantidad de grava enviarde cada distribuidor a cada proyectocon el objeto de minimizar los costos totales?
Sujeto a:
• No enviar más de; 150 tons. del distribuidor 1,175 tons. del distribuidor 2 y 275 tons. deldistribuidor 3.
• Enviar 200 tons. al proyecto 1, 100 tons. alproyecto 2 y 300 tons. al proyecto 3.
Distribución de grava a Proyectos
• Los costos de envío del distribuidor i al proyecto j son los siguientes:
• Costo del distribuidor 1 al proyecto 1, C11=$6
• Costo del distribuidor 1 al proyecto 2, C12=$8• Costo del distribuidor 1 al proyecto 3, C13=$10
• Costo del distribuidor 2 al proyecto 1, C21 =$7• Costo del distribuidor 2 al proyecto 2, C22=$11• Costo del distribuidor 2 al proyecto 3, C23=$11• Costo del distribuidor 3 al proyecto 1, C31 =$4• Costo del distribuidor 3 al proyecto 2, C32=$5• Costo del distribuidor 3 al proyecto 3, C33=$12
Distribución de grava a Proyectos
Variables de decisión
XIJ = Número de toneladas a enviar deldistribuidor “I” al proyecto “J”.donde i=1..3(distribuidor) y j=1..3(proyecto)
Función objetivo
Min. Z = 6X11 + 8X12 + 10X13 + 7X21 + 11X22
+ 11X23 + 4X31 + 5X32 + 12X33
Distribución de grava a Proyectos
Restricciones de disponibilidad
X11 + X12 + X13 150
X21 + X22 + X23 175
X31 + X32 + X33 275
Restricciones de requerimientos
X11 + X21 + X31 = 200
X12 + X22 + X32 = 100
X13 + X23 + X33 = 300
Distribución de grava a Proyectos
Min. Z = 6X11 + 8X12 + 10X13 + 7X21 + 11X22
+ 11X23 + 4X31 + 5X32 + 12X33
X11 + X12 + X13 150
X21 + X22 + X23 175
X31 + X32 + X33 275
X11 + X21 + X31 = 200
X12 + X22 + X32 = 100
X13 + X23 + X33 = 300
X11, X12, X13 .... X33 0
Sujeto a:
Distribución de grava a Proyectos
Solución
Solución
Red de Distribución
Ejemplo de Transporte
• Suponga que una empresa posee dos plantas que
elaboran un determinado producto en cantidades de 250
y 450 unidades diarias, respectivamente. Dichas
unidades deben ser trasladadas a tres centros de
distribución con demandas diarias de 200, 200 y 250
unidades, respectivamente. Los costos de transporte (en
$/unidad) son:
C.Dist. 1 C.Dist.2 C.Dist.3 Suplen
Planta 1 $21 $25 $15 250
Planta 2 $28 $13 $19 450
Demanda 200 200 250
Ejemplo de Transporte
• Diagrama:
Planta 1
Planta 2
C.D.2
C.D.1
C.D.3
X11
X12
X21 X22
X13
X23
Orígenes Destinos
Ejemplo de Transporte
Variables de decisión:
xij = Unidades transportadas desde la planta i(i=1,2), hasta el centro de distribución j (j=1,2,3)
Función Objetivo:
Minimizar el costo total de transporte dado por lafunción:
21x11+25x12+15x13+28x21+13x22+19x23
Ejemplo de Transporte
Restricciones del problema:
1) No Negatividad: xij 0
2) Demanda:
CD1 : x11 +x21 = 200
CD2 : x12 +x22 = 200
CD3 : x13 + x23 = 250
Ejemplo de Transporte
3) Oferta :
P1 : x11 + x12 + x13 250
P2 : x21 + x22 + x23 450
Las variables de decisión deben aceptar
soluciones como números reales para tener un
modelo de P.L.
Solución
Resolver el problema de
Transporte
D1 D2 D3 D4 Fuente
F1 2 2 5 4 9
F2 6 3 4 4 16
F3 6 2 7 3 30
F4 2 6 4 3 4
D 10 17 18 14 59
Solución
Ejemplo: Destino Ficticio
• La Northern Airplane Company construye
aviones comerciales para varias líneas áreas de
todo el mundo. La última etapa del proceso de
producción consiste en fabricar los motores de
turbina e instalarlos.-una operación muy rápida-
en la estructura del avión terminado. La
compañía tiene varios contratos de trabajo que
la obligan a entregar un número considerable de
aviones en un futuro cercano y en este
momento debe programar la producción de
motores de turbina para los próximos cuatro
meses.
Ejemplo: Destino Ficticio
• En la segunda columna de la tabla siguiente se
indica la cantidad de motores que deben estar
listos para su instalación a fin de cumplir con las
fechas de entrega contratadas. De ella se
desprende que el número acumulado de
motores que deben producirse al final de los
meses 1,2,3 y 4 deben ser por lo menos de 10,
25, 50 y 70 unidades, respectivamente.
• Las instalaciones disponibles para producir los
motores varían de acuerdo con otros programas
de producción, mantenimiento y renovación
durante el período.
Ejemplo: Destino Ficticio
• Las diferencias
mensuales debidas
al número máximo
que se puede
producir y el costo
unitario de
producción (en
millones $) se
presentan en la
tercera y cuarta
columna.
Mes Instalacio
nes
programa
das
Produc
ción
máxim
a
Costo
unitario
de
produc
ción
Costo
unitario
de
almace
naje
1 10 25 1.08 0.015
2 15 35 1.11 0.015
3 25 30 1.10 0.015
4 20 10 1.13 0.015
Ejemplo: Destino Ficticio
• Dadas las variaciones de los costos de
producción, podría valer la pena fabricar
algunos motores un mes o más antes de su
fecha de instalación; en la actualidad se estudia
esta posibilidad. El inconveniente es que esos
motores deberán almacenarse hasta que sean
instalados – la estructura de los aviones no
estará lista antes .- El costo de almacenamiento
de cada motor es de 15 mil dólares por mes.-
incluye el interés sobre el capital invertido.
Ejemplo: Destino Ficticio
• El gerente de producción quiere
desarrollar la programación del número de
motores que se deben fabricar en cada
uno de los cuatro meses, de manera que
se minimicen los costos totales de
producción y almacenamiento.
Pasos para la solución
ijX
• Origen i = producción de motores de turbina en el
mes i (i=1,2,3,4)
• Destino j = instalación del motor de turbina en el
mes j (j=1,2,3,4)
• número de motores producidos en el mes i
para instalarlos en el mes j. (i ≤ j)
• Si = número de motores producidos en el mes i
• Dj = número de instalaciones programadas en el
mes j.
• Cij = Costo asociado con cada unidad ijX
Tabla de costos
Mes Costo por unidad distribuida
Destino
Recursos
1 2 3 4 5
1
2
3
4
1.080 1.095 1.110 1.125 0 25
M 1.110 1.125 1.140 0 35
M M 1.100 1.115 0 30
M M M 1.130 0 10
Demanda 10 15 25 20 30
Ori
gen
Ingresar los datos siguientes
Solución
RED del Modelo
Ejemplo de Transporte (Origen
Ficticio)
• El Metro Water District es una dependencia que
administra la distribución de agua en cierta región
geográfica grande. La región es bastante árida, por lo
que debe comprar y traer agua del exterior. Las fuentes
de esta agua importada son los ríos Colombo, Sacron y
Calorie. El distrito revende el agua a los usuarios de la
región. Sus clientes principales son los departamentos
de aguas de las ciudades de Berdoo, Los Devils, San
Go y Hollyglass.
Datos de recursos de agua del
Metro Water District
Costo en (en decenas de millones de
dólares ) por unidad distribuida
Recursos
Berdoo Los Devils San Go Hollyglass
Río Colombo 16 13 22 17 50
Río Sacron 14 13 19 15 60
Río Calorie 19 20 23 -- 50
Mínimo
necesario
30 70 0 10 (en
millones
de acres-
pie)Solicitado 50 70 30
• Es posible hacer llegar a cualquiera de estas ciudadesdesde cualquiera de los tres ríos, con excepción de queno hay forma de abastecer a Hollyglass con agua delrío Calorie. Sin embargo, dada la distribución geográficade los acueductos y las ciudades en la región, el costodel abastecimiento del distrito depende tanto de lafuente como de la ciudad a la que abastece.
• La administración del distrito tiene que resolver elproblema de cómo asignar el agua disponible durante elpróximo verano. En la columna del lado derecho de latabla anterior proporciona las cantidades disponibles enlos tres ríos, en unidades de un millón de acres-pie. Eldistrito se compromete a proporcionar una cantidadmínima para cumplir con las necesidades esenciales decada ciudad.
• Con la excepción de San Go, que tiene una fuente
independiente de agua; estas necesidades mínimas se
muestran en el renglón correspondiente de la tabla. El
renglón de solicitado indica que Los Devils no quiere
más agua que la que cubre sus necesidades mínimas,
pero Berdoo compraría hasta 20 más, San Go hasta 30
más y Hollyglass compraría toda la que pudiera obtener.
• La administración desea asignar toda el agua disponible
de los tres ríos de manera que por lo menos se cumpla
con las necesidades mínimas de cada ciudad y al mismo
tiempo se minimice el costo total para el distrito.
• Cantidad mínima= (50+60+50) - (30+70+0)=60
• Demanda (50+70+30+60) – (50+60+50) = 50
Tabla de parámetros sin las necesidades
mínimas del
Metro Water District
Costo en (en decenas de millones de
dólares ) por unidad distribuida
Recursos
Berdoo Los Devils San Go Hollyglass
Río Colombo 160 130 220 17 50
Río Sacron 140 130 190 15 60
Río Calorie 190 200 230 M 50
Ficticio 0 0 0 0 50
Demanda 50 70 30 60
Usando WindQsb (Redes)
Solución
Solución en RED
Top Related