Problema Transporte Jrva

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.


• 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.


• 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 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.


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


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


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


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


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:


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


• Diagrama:

Planta 1

Planta 2

C.D.2

C.D.1

C.D.3

X11

X12

X21 X22

X13

X23

Orígenes Destinos


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


Restricciones del problema:

1) No Negatividad: xij 0

2) Demanda:

CD1 : x11 +x21 = 200

CD2 : x12 +x22 = 200

CD3 : x13 + x23 = 250


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.


• 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.


• 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


• 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.


• 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

Documents

Problema Transporte Jrva