• Author / Uploaded
• Aldo Noe Giron Adame

Citation preview

CAPÍTULO 5

Modelo de transporte y sus variantes

Aplicación de la vida real. Programación de citas en eventos comerciales australianos La Comisión de Turismo Australiana (ATC, por sus siglas en inglés) organiza eventos comerciales alrededor del mundo para que sirvan de foro donde se puedan reunir los vendedores australianos con los compradores internacionales de productos turísticos. Durante estos eventos los vendedores se sitúan en cubículos y los compradores los visitan de acuerdo con citas programadas. Debido a la limitación de tiempo disponible en cada evento y al hecho de que la cantidad de compradores y vendedores puede ser muy grande, la ATC procura programar las citas entre vendedor y comprador con anticipación para maximizar las preferencias. El modelo ha resultado muy satisfactorio tanto para los compradores como para los vendedores. (El caso 3 del capítulo 26, en inglés, del sitio web contiene los detalles del estudio). 5.1

DEFINICIÓN DEL MODELO DE TRANSPORTE La red que aparece en la figura 5.1 representa el problema. Hay m orígenes y n destinos, cada uno representado por un nodo. Los arcos representan las rutas que unen los orígenes con los destinos. El arco (i, j) que une el origen i con el destino j transporta dos piezas de información: el costo de transporte por unidad, cij y la cantidad transportada, xij. La cantidad de la oferta en el origen i es ai y la cantidad de la demanda en el destino j es bj. El objetivo del modelo es minimizar el costo de transporte total al mismo tiempo que se satisfacen las restricciones de la oferta y la demanda. Ejemplo 5.1-1 MG Auto cuenta con tres plantas en Los Ángeles, Detroit y Nueva Orleáns, y dos importantes centros de distribución en Denver y Miami. Las capacidades trimestrales de las tres plantas son 1000, 1500 y 1200 automóviles, y las demandas de los dos centros de distribución durante el mismo periodo son de 2300 y 1400 automóviles. La distancia en millas entre las plantas y los centros de distribución aparece en la tabla 5.1. 175

176

Capítulo 5

Modelo de transporte y sus variantes Orígenes a1

1

Unidades a ofertadas 2

am

c11 : x11

Destinos 1

b1

2

2

b2

· · ·

· · · bn

n

m

Unidades demandadas

cmn : xmn

FIGURA 5.1 Representación del modelo de transporte con nodos y arcos TABLA 5.1 Gráfica de distancia en millas

Los Ángeles Detroit Nueva Orleáns

Denver

Miami

1000 1250 1275

2690 1350 850

La compañía transportista cobra 8 centavos por milla por automóvil. En la tabla 5.2 se dan los costos de transporte por automóvil en las diferentes rutas, redondeados al dólar más cercano. El modelo de PL del problema es Minimizar z = 80x11 + 215x12 + 100x21 + 108x22 + 102x31 + 68x32 sujeto a x11 + x12

= 1000 (Los Ángeles) x21 + x22

= 1500 (Detroit) + x31 + x32 = 1200 (Nueva Orléans)

+ x21

x11 x12

+ x31 + x22

= 2300 (Denver) + x32 = 1400 (Miami)

xij Ú 0, i = 1, 2, 3, j = 1, 2 Todas estas restricciones son ecuaciones porque la oferta total desde los tres orígenes (5 1000 1 1500 1 1200 5 3700 automóviles) es igual a la demanda total en los dos destinos (5 2300 1 1400 5 3700 automóviles). TABLA 5.2 Costo de transporte por automóvil

Los Ángeles (1) Detroit (2) Nueva Orleáns (3)

Denver (1)

Miami (2)

$80 $100 $102

$215 $108 $68

5.1 Definición del modelo de transporte

177

TABLA 5.3 Modelo de transporte de MG Denver Los Ángeles

Miami

80 x11

Detroit x21

Demanda

1000

x12 100

Nueva Orleáns

Oferta

215 108 1500

x22 102

68

x31

x32

2300

1400

1200

La estructura especial del problema de transporte permite una representación compacta del problema utilizando el formato tabla de transporte que aparece en la tabla 5.3. Este formato permite modelar muchas situaciones que no tienen que ver con bienes de transporte, como se demuestra con los ejemplos de la sección 5.2. La solución óptima en la figura 5.2 (obtenida por TORA1) envía 1000 automóviles de Los Ángeles a Denver (x11 5 1000), 1300 de Detroit a Denver (x21 5 1300), 200 de Detroit a Miami (x22 5 200) y 1200 de Nueva Orleáns a Miami (x32 5 1000). El costo de transporte mínimo asociado se calcula como 1000 3 $80 1 1300 3 $100 1 200 3 $108 1 1200 3 $68 5 $313.200.

Balanceo del modelo de transporte. La representación de la tabla de transporte asume que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total. Si el modelo está desbalanceado, podemos agregar un origen o un destino ficticios para restaurar el balance. Ejemplo 5.1-2 En el modelo de MG, suponga que la capacidad de la planta de Detroit es de 1300 automóviles (en lugar de 1500). La oferta total (5 3500) es menor que la demanda total (5 3700), lo que significa que no se satisfará una parte de la demanda en Denver y Miami. Como la demanda excede la oferta, se agrega un origen (planta) ficticio con una capacidad de 200 automóviles (5 3700 2 3500) para balancear el modelo de transporte. El costo de transporte por unidad de la planta ficticia a los destinos es cero porque la planta no existe. 1000

1 Los Ángeles

1000

1300 1500

2 Detroit 3 Nueva Orleáns

1

2300

200 1200

1200

1 Denver 2 Miami

1400 FIGURA 5.2 Solución óptima del modelo de MG Auto

Para utilizar TORA, en el comando Main Menu seleccione la opción Transportation Model . En el menú SOLVE/MODIFY seleccione las opciones Solve Q Final solution para obtener un resumen de la solución óptima. En la sección 5.3.3 se da una descripción detallada de la solución iterativa del modelo de transporte.

178

Capítulo 5

Modelo de transporte y sus variantes TABLA 5.4 Modelo de MG con una planta ficticia Denver

Miami

80

215

100

108

102

68

Oferta

Los Ángeles 1000

1000

Detroit 1300

1300

Nueva Orleáns 1200 0

1200 0

Planta ficticia 200 1400

2300

Demanda

200

TABLA 5.5 Modelo de MG con un destino ficticio Denver

Miami

Ficticio

80

215

0

100

108

0

Los Ángeles 1000

1000

Detroit 900

200 102

400 68

1500 0

Nueva Orleáns Demanda

1900

1200 1400

1200 400

La tabla 5.4 da el modelo balanceado junto con su solución óptima. La solución muestra que la planta ficticia envía 200 automóviles a Miami, es decir que a Miami le faltarán 200 automóviles para satisfacer su demanda de 1400 automóviles. Podemos estar seguros de que un destino específico no experimente escasez al asignar un costo de transporte por unidad muy alto desde el origen ficticio a dicho destino. Por ejemplo, una penalización de $1000 en la celda ficticia de Miami evitará que haya escasez en Miami. Desde luego, no podemos utilizar este “artificio” con todos los destinos, porque debe haber escasez en alguna parte. El caso en que la oferta excede la demanda se puede demostrar asumiendo que la demanda en Denver es de sólo 1900 automóviles. Entonces, tenemos que agregar un centro de distribución ficticio para que “reciba” la oferta excedente. De nuevo, el costo de transporte por unidad al centro de distribución ficticio es cero, a menos que una fábrica “envíe todas sus existencias”. En este caso, se asigna un costo alto de transporte por unidad de la fábrica designada al destino ficticio. La tabla 5.5 da el nuevo modelo y su solución óptima (obtenida por TORA). La solución muestra que la planta de Detroit tendrá un excedente de 400 automóviles.

5.1 Definición del modelo de transporte

179

CONJUNTO DE PROBLEMAS 5.1A2 1. ¿Cierto o falso? (a) Para balancear un modelo de transporte, puede ser necesario agregar tanto un origen como un destino ficticios. (b) Las cantidades enviadas a un destino ficticio representan un excedente en el origen que hace el envío. (c) Las cantidades enviadas por un origen ficticio representan faltantes en los destinos que reciben el envío. 2. En cada uno de los siguientes casos, determine si debe agregarse un origen ficticio o un destino ficticio para balancear el modelo. (a) Oferta: a1 = 10, a2 = 5, a3 = 4, a4 = 6 Demanda: b1 = 10, b2 = 5, b3 = 7, b4 = 9 (b) Oferta: a1 = 30, a2 = 44 Demanda: b1 = 25, b2 = 30, b3 = 10 3. En la tabla 5.4 del ejemplo 5.1-2, donde se agrega una planta ficticia, ¿qué significa la solución cuando la planta ficticia “envía” 150 automóviles a Denver y 50 a Miami? *4. En la tabla 5.5 del ejemplo 5.1-2, donde se agrega un destino ficticio, suponga que la planta de Detroit debe enviar toda su producción. ¿Cómo se puede implementar esta restricción en el modelo? 5. En el ejemplo 5.1-2, suponga que en el caso en que la demanda excede la oferta (tabla 5.4), se aplica una penalización a razón de $200 y $300 por cada automóvil no entregado en Denver y Miami, respectivamente. Además, no se hacen envíos de Los Ángeles al centro de distribución de Miami. Elabore el modelo, y determine el programa de envíos óptimo para el problema. *6. Tres plantas de energía eléctrica de 25, 40 y 30 millones de kWh abastecen electricidad a tres ciudades. Las demandas máximas en las tres ciudades se estiman en 30, 35 y 25 millones de kWh. El precio por millón de kWh en las tres ciudades se da en la tabla 5.6. Durante el mes de agosto la demanda se incrementa 20% en cada una de las tres ciudades, la cual puede satisfacerse adquiriendo electricidad de otra red a un precio más elevado de $1000 por millón de kWh. La red no está enlazada a la ciudad 3. La compañía eléctrica desea determinar el plan más económico para la distribución y compra de energía adicional. (a) Formule el problema como un modelo de transporte. (b) Determine un plan de distribución óptimo para la compañía eléctrica. (c) Determine el costo de la energía adicional adquirida por cada una de las tres ciudades. 7. Resuelva el problema 6, suponiendo que se pierde 10% de la energía que se transmite a través de la red. 8. Tres refinerías con capacidades diarias de 6, 5 y 8 millones de galones, respectivamente, abastecen a su vez a tres áreas de distribución con demandas diarias de 4, 8 y 7 millones TABLA 5.6 Precio/millón de kWh para el problema 6 Ciudad

1 Planta 2 3

2

1

2

3

$600 $320 $500

$700 $300 $480

$400 $350 $450

En este conjunto puede utilizar TORA para determinar la solución óptima. Los modelos del problema de transporte obtenidos con AMPL y Solver se presentarán al final de la sección 5.3.2.

180

Capítulo 5

Modelo de transporte y sus variantes TABLA 5.7 Distancia en millas para el problema 8 Área de distribución

1 Refinería 2 3

*9.

10.

11.

12.

1

2

3

120 300 200

180 100 250

— 80 120

de galones, respectivamente. La gasolina se transporta a las tres áreas de distribución a través de una red de oleoductos. El costo de transporte es de 10 centavos por 1000 galones por milla de oleoducto. La tabla 5.7 presenta la distancia en millas entre las refinerías y las áreas de distribución. La refinería 1 no está conectada al área de distribución 3. (a) Construya el modelo de transporte asociado. (b) Determine el programa de envíos óptimo en la red. En el problema 8, suponga que la capacidad de la refinería 3 es de sólo 6 millones de galones y que el área de distribución debe recibir toda su demanda. Adicionalmente, las cantidades faltantes en las áreas 2 y 3 incurrirán en una penalización de 5 centavos por galón. (a) Formule el problema como un modelo de transporte. (b) Determine el programa de envíos óptimo. En el problema 8, suponga que la demanda diaria en el área 3 disminuye a 4 millones de galones. La producción excedente en las refinerías 1 y 2 se envía a otras áreas de distribución por medio de camiones cisterna. El costo de transporte por 100 galones es de $1.50 desde la refinería 1 y de $2.20 desde la refinería 2. La refinería 3 puede enviar su producción excedente a otros procesos químicos dentro de la planta. (a) Formule el problema como un modelo de transporte. (b) Determine el programa de envíos óptimo. Tres huertas abastecen a cuatro detallistas con cajas de naranjas. La demanda diaria de los cuatro detallistas es de 150, 150, 400 y 100 cajas, respectivamente. Las ofertas en las tres huertas dependen de la mano de obra regular disponible y se estiman en 150, 200 y 250 cajas diarias. Sin embargo, las huertas 1 y 2 indicaron que podrían abastecer más cajas, si es necesario, recurriendo a mano de obra extra. La huerta 3 no ofrece esta opción. Los costos de transporte por caja de las huertas a los detallistas se dan en la tabla 5.8. (a) Formule el problema como un modelo de transporte. (b) Resuelva el problema. (c) ¿Cuántas cajas deben abastecer las huertas 1 y 2 si utilizan tiempo extra? Tres centros de distribución envían automóviles a cinco concesionarios. El costo de envío depende de la distancia en millas entre los orígenes y los destinos, y es independiente de si el camión hace el viaje con cargas parciales o completas. La tabla 5.9 resume la distancia en millas entre los centros de distribución y los concesionarios junto con las cifras de

TABLA 5.8 Costo de transporte/caja para el problema 11 Detallista

Huerta

1 2 3

1

2

3

4

$1 $2 $1

$2 $4 $3

$3 $1 $5

$2 $2 $3

5.1 Definición del modelo de transporte

181

TABLA 5.9 Distancia en millas, y oferta y demanda para el problema 12 Concesionario 3 4

1

2

5

1 Centro 2 3

100 50 40

150 70 90

200 60 100

140 65 150

35 80 130

Demanda

100

200

150

160

140

Oferta 400 200 150

oferta y demanda mensuales dadas en número de automóviles. Una carga completa comprende 18 automóviles. El costo de transporte por milla de camión es de $25. (a) Formule el modelo de transporte asociado. (b) Determine el programa de envíos óptimo. 13. MG Auto, del ejemplo 5.1-1, produce cuatro modelos de automóviles: M1, M2, M3 y M4. La planta de Detroit produce los modelos M1, M2 y M4. Los modelos M1 y M2 también se producen en Nueva Orleáns. La planta de Los Ángeles fabrica los modelos M3 y M4. Las capacidades de las plantas y las demandas en los centros de distribución aparecen en la tabla 5.10. La distancia en millas es la misma que la de la gráfica del ejemplo 5.1-1, y la tarifa de transporte se mantiene en 8 centavos por milla de camión para todos los modelos. Además, es posible satisfacer un porcentaje de la demanda de algunos modelos con la oferta de otros de acuerdo con las especificaciones de la tabla 5.11. (a) Formule el modelo de transporte correspondiente. (b) Determine el programa de envíos óptimo. (Sugerencia: Agregue cuatro nuevos destinos correspondientes a las nuevas combinaciones [M1,M2], [M3,M4], [M1,M2] y [M2,M4]. Las demandas en los destinos nuevos se determinan a partir de los porcentajes dados). TABLA 5.10 Capacidades y demandas para el problema 13 Modelo

O

M1

M2

M3

M4

Totales

— 500 800

— 600 400

700 — —

300 400 —

1000 1500 1200

Centro de distribución Denver 700 Miami 600

500 500

500 200

600 100

2300 1400

Planta Los Ángeles Detroit Nueva Orleáns

TABLA 5.11 Modelos intercambiables para el problema 13 Centro de distribución Denver Miami

Porcentaje de la demanda 10 20 10 5

Modelos intercambiables M1, M2 M3, M4 M1, M2 M2, M4