Modelos de Transporte: Modelos de Transporte: Problemas de Problemas de transbordotransbordo y y

problema del vendedor problema del vendedor viajeroviajero

M. En C. Eduardo Bustos FarM. En C. Eduardo Bustos Farííasas

2

ProblemasProblemas de de TransbordoTransbordo

3

ProblemasProblemas de de TransbordoTransbordo

Son Son problemasproblemas de de transportetransporte en en loslos quequese se agreganagregan puntospuntos de de transbordotransbordo. . Los Los puntospuntos de de transbordotransbordo son son puntospuntosqueque puedenpueden tantotanto recibirrecibir mercadermercaderííaa de de otrosotros puntospuntos comocomo enviarenviar mercadermercaderííaa a a otrosotros puntospuntos..

4

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

5

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

6

EjemploEjemplo

7

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.

8

SOLUCISOLUCIÓÓNN

9

1. Variables de decisi1. Variables de decisióón: n: xijxij = n= núúmero de unidades mero de unidades embarcadas del origen i al destino j, pasando por embarcadas del origen i al destino j, pasando por los nodos de trasbordo que se especifican.los nodos de trasbordo que se especifican.

i = 1, 2, 3, 4i = 1, 2, 3, 4j = 5,.., 8j = 5,.., 8

2. Funci2. Funcióón objetivo:n objetivo:MMíínn 484746453837363524231413 56446362332 xxxxxxxxxxxxZ +++++++++++=

Oferta

600

400

Plantas(origen)

1

8

7

6

5

4

3

2

2

3

3

1

Almacenes(transbordo)

2

6

3

6

44

6

5

Distribuidores(destino) Demanda

200

150

350

300

10

3. Restricciones3. Restriccionesa) De los nodos origen:a) De los nodos origen:

b) De los nodos de b) De los nodos de transbordotransbordo::

400600

2423

1413

≤+≤+

xxxx

00

484746452414

383736352313

=++++−−=++++−−

xxxxxxxxxxxx

Oferta

600

400

Plantas(origen)

1

8

7

6

5

4

3

2

2

3

3

1

Almacenes(transbordo)

2

6

3

6

44

6

5

Distribuidores(destino) Demanda

200

150

350

300

11

c) De los nodos destino:c) De los nodos destino:

ij

x

xxxxxxxx

ij

∀

≥

=+=+=+=+

0

300350150200

4838

4737

4636

4535Oferta

600

400

Plantas(origen)

1

8

7

6

5

4

3

2

2

3

3

1

Almacenes(transbordo)

2

6

3

6

44

6

5

Distribuidores(destino) Demanda

200

150

350

300

12

Variantes del problema de Variantes del problema de trasbordotrasbordo

13

Igual que en los problemas de transporte Igual que en los problemas de transporte se pueden formular problemas de se pueden formular problemas de trasbordo con varias variantes:trasbordo con varias variantes:Suministro total no igual a la demanda Suministro total no igual a la demanda totaltotalMaximizaciMaximizacióón de la funcin de la funcióón objetivon objetivoRutas con capacidad limitadaRutas con capacidad limitadaRutas inaceptablesRutas inaceptables

14

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

15

Variantes al problema de Variantes al problema de transportetransporte

Oferta no igual a la demanda total: Se agrega Oferta no igual a la demanda total: Se agrega una columna de holgura en la tabla de una columna de holgura en la tabla de transporte y se le asignan ceros en los transporte y se le asignan ceros en los costos.costos.

Rutas con capacidad limitada: En la formulaciRutas con capacidad limitada: En la formulacióón n de programacide programacióón lineal del problema de n lineal del problema de transporte tambitransporte tambiéén puede tomar en n puede tomar en consideraciconsideracióón capacidades o cantidades n capacidades o cantidades mmíínimas para una ruta. Asnimas para una ruta. Asíí ::

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

16

Rutas no aceptables: QuizRutas no aceptables: Quizáás no pueda ser posible s no pueda ser posible establecer una ruta desde cualquiera de los establecer una ruta desde cualquiera de los ororíígenes hasta cualquiera de los destinos. genes hasta cualquiera de los destinos.

A fin de manejar esta situaciA fin de manejar esta situacióón, hacemos n, hacemos desaparecer el arco correspondiente en la desaparecer el arco correspondiente en la formulaciformulacióón de la programacin de la programacióón lineal.n lineal.

MaximizaciMaximizacióón de la funcin de la funcióón objetivo: En algunos n objetivo: En algunos problemas de transporte, el objetivo es problemas de transporte, el objetivo es encontrar una soluciencontrar una solucióón que maximice la n que maximice la utilidad o los ingresos.utilidad o los ingresos.

17

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

18

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

19

EJEMPLO 1EJEMPLO 1

MaximizaciMaximizacióónn

20

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

21

SOLUCISOLUCIÓÓNN

22

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

01

23

24

Los valores de las variables en la tabla Los valores de las variables en la tabla óóptima se ptima se multiplican por las utilidades de la tabla original y se multiplican por las utilidades de la tabla original y se suman para calcular la utilidad total.suman para calcular la utilidad total.

x11 = 200 * 5 = 1000x11 = 200 * 5 = 1000x12 = 50 * 3 = 150x12 = 50 * 3 = 150x22 = 200 * 2 = 400x22 = 200 * 2 = 400x23 = 150 * 4 = 600x23 = 150 * 4 = 600

Z= 2150Z= 2150

25

Problema para resolverProblema para resolver

TransbordoTransbordo

26

4 5 6 7 8 9

45

27

Problema del vendedor viajeroProblema del vendedor viajero

28

Problema del vendedor viajeroProblema del vendedor viajero

Se trata de un tour es un recorrido que comienza en Se trata de un tour es un recorrido que comienza en una ciudad de partida visitando cada ciudad (nodo) una ciudad de partida visitando cada ciudad (nodo) de una cierta red, exactamente una vez y volviendo de una cierta red, exactamente una vez y volviendo al punto de partida.al punto de partida.

El objetivo es minimizar el viaje, ya sea desde los El objetivo es minimizar el viaje, ya sea desde los puntos de vista de tiempo y distancia.puntos de vista de tiempo y distancia.

Definición del problema

– Existen m nodos– Un costo unitario Cij es asociado al arco (i,j).– El objetivo es encontrar el ciclo que minimice el costo

total al visitar todos los nodos exactamente una vez.

29

ImportanciaImportancia

-- Diversas aplicaciones pueden ser resueltas como un problema Diversas aplicaciones pueden ser resueltas como un problema de vendedor viajerode vendedor viajero

-- EjemploEjemplo* Rutas a seguir por buses escolares* Rutas a seguir por buses escolares* Distribuci* Distribucióón de bombas militaresn de bombas militares

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

ComplejidadEscribir el modelo matemático y

resolverlo resulta muchas veces incómodo, ya que un problema de 20 ciudades requiere de 500,000 restricciones.

30

31

EJEMPLO 1EJEMPLO 1

JonesJones CigarCigar CompanyCompanyProblema del vendedor viajeroProblema del vendedor viajero

32

33

34

Con n ciudades. Se presenta esta Con n ciudades. Se presenta esta diferencia porque la solucidiferencia porque la solucióón debe n debe comenzar en la misma ciudad de comenzar en la misma ciudad de origen.origen.

Para el problema de Para el problema de DaveDave RenfroRenfro, habr, habráá(5(5--1)! = 24 soluciones posibles.1)! = 24 soluciones posibles.

35

SOLUCISOLUCIÓÓN CON WINQSBN CON WINQSB

36

37

38

39