Read Capítulo 4 text version

Modelos de Transporte: Problemas de transbordo y

problema del vendedor viajero

M. En C. Eduardo Bustos Farías

Problemas de Transbordo

2

Problemas de Transbordo

Son problemas de transporte en los que se agregan puntos de transbordo. Los puntos de transbordo son puntos que pueden tanto recibir mercadería de otros puntos como enviar mercadería a otros puntos.

3

Es una extensión al problema de transporte en el cual se agregan nodos intermedios (nodos de transbordo), para tomar en consideración localizaciones, como por ejemplo almacenes. En este tipo más general del problema de transporte de distribución, los embarques pueden ser efectuados entre cualquier par de tres tipos generales de nodos: de origen, de transbordo o de 4 destino.

Características

La oferta o suministro disponible en cada origen es limitada. En cada destino la demanda está definida o especificada. El objetivo en el problema de transbordo es de determinar cuantas unidades deberán embarcarse por cada uno de los arcos de la red, de manera que todas las demandas-destino se satisfagan al costo de transporte mínimo posible.

5

Ejemplo

6

Encontrar la formulación de programación lineal para el problema de transbordo planteado en el modelo de redes, tal que minimice los costos de transporte.

7

SOLUCIÓN

8

Oferta

Plantas (origen)

Almacenes (transbordo)

Distribuidores (destino)

5

Demanda

2 600

1 3

2 6 3 6

200

3

6

150

3 400

2 4

4

4 6 5

7

350

1

8

300

1. Variables de decisión: xij = número de unidades embarcadas del origen i al destino j, pasando por los nodos de trasbordo que se especifican. i = 1, 2, 3, 4 j = 5,.., 8 2. Función objetivo: Z = 2 x13 + 3 x14 + 3 x23 + x24 + 2 x35 + 6 x36 + 3 x37 + 6 x38 + 4 x45 + 4 x46 + 6 x479+ 5 x48 Mín

Oferta

Plantas (origen)

Almacenes (transbordo)

Distribuidores (destino)

5

Demanda

2 600

1 3

2 6 3 6

200

3

6

150

3 400

2 4

4

4 6 5

7

350

1

8

300

3. Restricciones a) De los nodos origen:

x13 + x14 600 x23 + x24 400

b) De los nodos de transbordo:

- x13 - x23 + x35 + x36 + x37 + x38 = 0 - x14 - x24 + x45 + x46 + x47 + x48 = 0

10

c) De los nodos destino:

x35 + x45 = 200 x36 + x46 = 150 x37 + x47 = 350 x38 + x48 = 300

400

2

Oferta

Plantas (origen)

Almacenes (transbordo)

Distribuidores (destino)

5

Demanda

2 600

1 3

2 6 3 6

200

3

6

150

3

4

4

4 6 5

7

350

1

8

300

xij 0 ij

11

Variantes del problema de trasbordo

12

Igual que en los problemas de transporte se pueden formular problemas de trasbordo con varias variantes: Suministro total no igual a la demanda total Maximización de la función objetivo Rutas con capacidad limitada Rutas inaceptables

13

Las modificaciones a los modelos de programación lineal requeridas para aceptar estas variaciones son idénticas a las que se mencionaron para el problema de transporte.

14

Variantes al problema de transporte

Oferta no igual a la demanda total: Se agrega una columna de holgura en la tabla de transporte y se le asignan ceros en los costos. Rutas con capacidad limitada: En la formulación de programación lineal del problema de transporte también puede tomar en consideración capacidades o cantidades mínimas para una ruta. Así :

Para capacidad xij <= 1000 Para montos mínimos de ruta xij >= 2000

15

Rutas no aceptables: Quizás no pueda ser posible establecer una ruta desde cualquiera de los orígenes hasta cualquiera de los destinos. A fin de manejar esta situación, hacemos desaparecer el arco correspondiente en la formulación de la programación lineal. Maximización de la función objetivo: En algunos problemas de transporte, el objetivo es encontrar una solución que maximice la utilidad o los ingresos.

16

Empleando valores de la utilidad o de ingresos unitarios como coeficientes de la función objetivo, resolvemos un problema lineal de maximización en vez de uno de minimización. Este cambio no afecta a las restricciones. Otro método empleando la tabla de transporte es construir la matriz de costos de oportunidad. Costo de oportunidad es el costo en que se incurre por no haber tomado la mejor decisión o por no haber hecho la mejor elección posible.

17

En el contexto de un problema de transporte que impide maximización, el costo de oportunidad para una celda es la diferencia entre su utilidad y la utilidad de la celda de esa columna que sea mayor. El costo de oportunidad es el costo en que se incurre al no transportar todo por la ruta que arroje las mayores utilidades.

18

EJEMPLO 1

Maximización

19

Maximizar las utilidades totales de la ruta de transporte que se muestra. Aquí los valores de los recuadros son utilidades (dólares por unidad).

20

SOLUCIÓN

21

Se construye la tabla de transporte con los costos de oportunidad, se encuentra una SBFI y se procede con el cálculo de los índices de mejoramiento.

0 1

22

23

Los valores de las variables en la tabla óptima se multiplican por las utilidades de la tabla original y se suman para calcular la utilidad total. x11 = 200 * 5 = 1000 x12 = 50 * 3 = 150 x22 = 200 * 2 = 400 x23 = 150 * 4 = 600 Z= 2150

24

Problema para resolver

Transbordo

25

4

5

6

7

8

9

4 5

26

Problema del vendedor viajero

27

Problema del vendedor viajero

Se trata de un problema Definición del tour es un recorrido que comienza en una ciudad de partida visitando cada ciudad (nodo) de una cierta red, exactamente una vez y volviendo punto m partida. ­alExisten de nodos

­ Un costo unitario Cij es asociado al arco (i,j). El objetivo es minimizar el viaje, ya sea desde los ­puntos de vistaencontrar el y distancia. El objetivo es de tiempo ciclo que minimice el costo total al visitar todos los nodos exactamente una vez.

28

Importancia

- Diversas aplicaciones pueden ser resueltas como un problema de vendedor viajero matemático y Escribir el modelo

Complejidad

resolverlo resulta muchas veces incómodo, - Ejemplo ya que un problema de 20 ciudades * Rutas a seguir por buses escolares requiereDistribución derestricciones. * de 500,000 bombas militares

- El problema tiene importancia teórica porque este representa una clase de problemas llamados NP-completos.

29

30

EJEMPLO 1

Jones Cigar Company Problema del vendedor viajero

31

32

33

Con n ciudades. Se presenta esta diferencia porque la solución debe comenzar en la misma ciudad de origen. Para el problema de Dave Renfro, habrá (5-1)! = 24 soluciones posibles.

34

SOLUCIÓN CON WINQSB

35

36

37

38

39

Information

Capítulo 4

39 pages

Find more like this

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

438216