• Author / Uploaded
• Franklin Landeta

• Categories
• Transporte
• Matemáticas Aplicadas
• Física y matemáticas
• Matemáticas
• Informática y tecnología de la información

Citation preview

ICM02246 Investigación de Operaciones (Audit.) Ingeniería en Auditoría y Contaduría Pública Autorizada Periodo Académico 2016 - 1° Semestre Instructor: Alfredo Armijos, PMP®, PMI-RMP®, M.Sc.

Agenda de Inducción • Definición del Modelo de Transporte • Modelos No Tradicionales de Transporte • Determinación de Solución de Inicio • Cálculos Iterativos del Algoritmo de Transporte • Próxima Semana

El Modelo de Transporte Es una clase especial de programación lineal que tiene que ver con transportar un artículo desde sus fuentes (es decir, fábricas) hasta sus destinos (es decir, bodegas). El objetivo es determinar el programa de transporte que minimice el costo total del transporte y que al mismo tiempo satisfaga los límites de la oferta y la demanda.

En el modelo se supone de que el costo de transporte es proporcional a la cantidad de las unidades transportadas en determinada ruta. En general, se puede ampliar el modelo de transporte a otras áreas de operación, entre otras el control de inventarios, programación de empleos y asignación de personal.

El Modelo de Transporte Hay m fuentes y n destinos, cada fuente y cada destino representados por un nodo. Los arcos representan las rutas que enlazan las fuentes y los destinos. El arco (i,j) que une a la fuente i con el destino j conduce dos clases de información: el costo de transporte cij por unidad, y la cantidad transportada xij.

La cantidad de oferta en la fuente i es ai y la cantidad de demanda en el destino j es bj. El objetivo del modelo es determinar las incógnitas xij que minimicen el costo total de transporte, y que al mismo tiempo satisfagan las restricciones de oferta y demanda del problema en análisis.

El Modelo de Transporte

El Modelo de Transporte MG Auto dispone de tres plantas en Los Ángeles, Detroit y New Orleans; y dos centros principales de distribución en Denver y Miami. Las capacidades de las tres plantas durante el próximo trimestre serán 1000, 1500 y 2000 autos. Las demandas trimestrales en los dos centros de distribución son 2300 y 1400 autos. El kilometraje entre fábricas y los centros de distribución se observan a continuación:

La empresa transportista cobra 8 centavos por milla y por auto. El costo de transporte por auto, en las distintas rutas y redondeando hasta el $ más próximo, se calcula como se observa en la tabla detallada a continuación:

El Modelo de Transporte La representación gráfica del problema adoptando nodos y arcos es la siguiente:

El Modelo de Transporte El modelo de programación lineal para el problema es el siguiente:

El Modelo de Transporte El modelo de programación lineal se puede resolver con el Método Símplex. Sin embargo, la estructura especial de las restricciones permite resolverlo con más comodidad usando la tabla de transporte siguiente:

Este formato permite modelar muchas situaciones que no tienen que ver con bienes de transporte, como se lo demostrará en ejercicios futuros acerca del presente modelo de investigación operativa.

El Modelo de Transporte

El Modelo de Transporte Aplicando el Método Símplex (Dos Fases), la solución final para el presente problema quedaría expresada como:

Indica que se manden 1000 autos de Los Ángeles a Denver, 1300 de Detroit a Denver, 200 de Detroit a Miami y 1200 de New Orleans a Miami. El costo mínimo del transporte asociado es 1000 x $80 + 1300 x $100 + 200 x $108 + 1200 x $68 = $313,200.

El Modelo de Transporte La solución óptima del problema adoptando nodos y arcos es la siguiente:

Indica que se manden 1000 autos de Los Ángeles a Denver, 1300 de Detroit a Denver, 200 de Detroit a Miami y 1200 de New Orleans a Miami. El costo mínimo del transporte asociado es 1000 x $80 + 1300 x $100 + 200 x $108 + 1200 x $68 = $313,200.

El 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 ficticio para restaurar el equilibrio o balance del modelo.

El Modelo de Transporte En el modelo de MG Auto, suponga que la capacidad de la planta de Detroit es de 1300 automóviles (en lugar de 1500). La oferta total (=3500) es menor que la demanda total (=3700), lo que significa que no se satisface 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 (= 3700 - 3500) para balancear el modelo de transporte. El costo por unidad de la planta ficticia a los destinos es cero porque la planta no existe.

El Modelo de Transporte

El Modelo de Transporte La siguiente tabla detalla 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.

El Modelo de Transporte La solución óptima del problema adoptando nodos y arcos es la siguiente:

El Modelo de Transporte El caso en que la oferta excede la demanda se puede demostrar asumiendo que la demanda en Denver es solo de 1900 automóviles. Entonces, se tiene 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.

El Modelo de Transporte BiciQuito es una empresa local que alquila bicicletas para promover movilidad sostenible en la capital. Su modelo de negocio funciona como sigue: El cliente paga una tarifa por el derecho a utilizar una bicicleta de la empresa durante el día. El cliente puede tomar una bicicleta de cualquiera de las nueve estaciones de la empresa y está en la libertad de devolver la bicicleta en cualquiera de las estaciones.

Dado que cada mañana la empresa abre sus estaciones con 10 bicicletas cada una, el derecho del cliente a devolver su bicicleta en cualquier estación implica que casi todas las noches hay que re-balancear las estaciones (i.e., hay que sacar biciletas de las estaciones con más de diez unidades y llevarlas a las estaciones con menos de diez unidades. Más aún, suponga que ésta noche la distribución de biciletas en las estaciones es como sigue:

Bicicletas

E1

E2

E3

E4

E5

E6

E7

E8

E9

9

15

12

13

9

5

14

8

5

El Modelo de Transporte Las distancias (en km.) entre las estaciones están dadas en la siguiente tabla:

Finalmente, suponiendo que el costo de llevar una bicicleta de una estación a otra es proporcional a la distancia entre las estaciones, modele y resuelva el problema de rebalancear las estaciones como un problema de transporte.

El Modelo de Transporte Las estaciones (representados como nodos de oferta y demanda) se encuentra detallada a continuación:

El Modelo de Transporte La tabla de costos de los arcos en función del kilometraje de las distancias entre cada estación es detallada a continuación:

El Modelo de Transporte La solución óptima del problema adoptando nodos y arcos es la siguiente:

El costo mínimo del transporte asociado es 1 x $4 + 4 x $7 + 1 x $7 + 1 x $7 + 1 x $8 + 2 x $5 + 1 x $9 + 3 x $8 = $97.

Modelos No Tradicionales de Transporte Control de Producción e Inventarios La aplicación del modelo de transporte no se limita a transportar artículos entre fuentes y destinos geográficos. La tabla detallada a continuación resume los paralelismos entre los elementos del problema de producción e inventario y el modelo de transporte.

Modelos No Tradicionales de Transporte Control de Producción e Inventarios Totto fabrica mochilas para ciclistas. La demanda de su product durante el periodo pico de Marzo a Junio de cada año es de 100, 200, 180 y 300 unidades, respectivamente. La compañía utiliza mano de obra de tiempo parcial para acomodarse a las fluctuaciones de la demanda. Se estima que Totto puede producer 50, 180, y 270 unidades de Marzo a Junio. La demanda del mes en curso se puede satisfacer de tres maneras: 1. La producción del mes en curso al costo de $40 por mochila. 2. La producción excedente de un mes anterior a un costo de retención adicional de $0.50 por mochila. 3. La producción excedente de un mes posterior (pedido en espera) a un costo de penalización adicional de $2.00 por mochila por mes. Totto desea determiner el programa de producción óptimo durante los cuatro meses de trabajo.

Modelos No Tradicionales de Transporte Control de Producción e Inventarios El “costo de transporte” por unidad, desde el periodo i hasta el periodo j se calcula de la siguiente manera:

Por ejemplo:

Modelos No Tradicionales de Transporte Control de Producción e Inventarios Finalmente el costo de “transporte” para cada periodo quedaría determinado, considerando la demanda y capacidad del problema quedaría como sigue:

Modelos No Tradicionales de Transporte Control de Producción e Inventarios La solución óptima del modelo de producción e inventario del problema en estudio queda detallada gráficamente a continuación:

Las líneas interrumpidas indican abastecimiento retrasado, las líneas de puntos indican producción para período futuro y las líneas llenas muestran la producción en un periodo, para la demanda de ese periodo.

Ejercicios de Práctica

Investigación de Operaciones Hamdy A. Taha Novena Edición • Conjunto de Problemas 5.1A (13 Ejercicios) Pd. Pueden resolver sus problemas con: • PHP|Simplex • GAMS

Algoritmo de Transporte Los pasos básicos del algoritmo de transporte son exactamente iguales a los del Método Simplex. Sin embargo, en lugar de utilizar la tabla simplex regular, se aprovecha la estructura especial del modelo de transporte para organizar los cálculos en una forma más conveniente: 1. Determine una solución factible básica inicial y vaya al paso 2 2. Use la condición de optimalidad del Método Simplex para determinar la variable de entrada de entre todas las variables no básicas. Si se satisfacen las condiciones de optimalidad, deténgase. De lo contrario, avance al paso 3 3. Use la condición de factibilidad del Método Simplex para determinar la variable de entrada de entre todas las variables básicas actuales, y halle la nueva solución básica. Regrese al paso 2. Los detalles del algoritmo se explican en secciones futuras por medio del siguiente ejemplo:

Algoritmo de Transporte Asegensa S.A. transporta granos de tres plantas de silos a cuatro centros de acopio. La oferta (en camiones cargados) y la demanda (también en camiones cargados) junto con los costos de transporte por unidad por camión cargado en las diferentes rutas, se resumen en la siguiente tabla. Los costos de transporte por unidad, cij (que se muestran en la esquina de cada casilla) están en cientos de dólares. El modelo busca el programa de envíos a un costo mínimo entre las plantas y los centros de acopio.

Determinación de la Solución de Inicio Un modelo de transporte general con m orígenes y n destinos tiene m + n ecuaciones de restricción, una por cada origen y cada destino. No obstante, como el presente modelo de transporte siempre está balanceado (oferta = demanda) una de las ecuaciones es redundante, por lo que el modelo se reduce a m + n 1 ecuaciones independientes y m + n – 1 variables básicas.

En el presente ejemplo, la solución inicial tendrá 3 + 4 – 1 variables básicas. La estructura especial del problema de transporte permite asegurar una solución básica inicial no artificial siguiendo uno de los métodos enunciados a continuación: • Método de la Esquina Noroeste • Método del Costo Mínimo • Método de Aproximación de Vogel

Método de la Esquina Noroeste Este primer método es de naturaleza “mecánica”, y los dos restantes son heurísticos que buscan una solución inicial de mejor calidad que dé un valor objetivo más pequeño. Por lo general, el método heurístico de Vogel es mejor que el heurístico de costo mínimo. Por otra parte, el método de esquina noroeste implica la cantidad mínima de cálculos.

El método se inicia en la celda de la esquina noroeste (ruta) de la tabla (variable x11) 1. Asigne todo lo que más se pueda a la celda seleccionada, y ajuste las cantidades asociadas de oferta y demanda restando la cantidad asignada. 2. Tache la columna o fila con oferta o demanda cero para indicar que no se hagan más asignaciones en esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tache sólo una, y deje una oferta (demanda) cero en la fila (columna) 3. Si se deja sin tachar exactamente una fila o columna, deténgase. De lo contrario, muévase a la celda a la derecha si acaba de tachar una columna, o abajo si acaba de tachar una fila. Vaya al paso 1.

Método del Costo Mínimo • Este método determina una mejor solución inicial al algoritmo al concentrarse en las rutas más económicas. • Asigna lo más posible a la celda con el costo unitario mínimo (los empates se rompen arbitrariamente). • Luego se tacha la fila o columna satisfecha y se ajustan las cantidades de oferta y demanda como corresponda. • Si una fila o columna se satisfacen al mismo tiempo, sólo se tacha una, igual que en el método de la esquina noroeste. • A continuación, se selecciona la celda no tachada con el costo unitario mínimo y se repite el proceso hasta que se deje sin tachar exactamente una fila o columna.

Método de Aproximación de Vogel Este método es una versión mejorada del método del costo mínimo que por lo general, pero no siempre, produce mejores soluciones iniciales para el algoritmo de transporte.

1.

2.

3.

Para cada fila (columna) determine una medida de penalización restando el elemento de costo unitario mínimo en la fila (columna) del siguiente elemento de costo mínimo en la misma fila (columna). Identifique la fila o columna con la penalización máxima, que rompa los empates arbitrariamente. Asigne lo más posible a la variable con el costo unitario mínimo en la fila o columna seleccionada. Ajuste la oferte y la demanda, y tache la fila o columna satisfecha. Si una fila y una columna se satisfacen al mismo tiempo, sólo se tacha una de las dos, y a la fila restante (columna) se le asigna una oferta (demanda) cero. Finalmente: 1. Si exactamente una fila o columna con oferta o demanda cero permanece sin tachar, deténgase 2. Si una fila (columna) con oferta (demanda) positiva permanece sin tachar, determine las variables básicas en la fila (columna) mediante el método del costo mínimo. Deténgase. 3. Si todas las filas o columnas no tachadas tienen oferta y demanda cero (restantes), determine las variables básicas cero por el método del costo mínimo. Deténgase. 4. De lo contrario, vaya al paso 1.

Taller de Práctica Determine la solución inicial factible con los métodos de esquina noroeste, de costo mínimo y de aproximación de Vogel para cada uno de los siguientes modelos.

Determine el costo total de cada uno de los métodos y comenté cuál es el más eficiente en términos iterativos.

Un Excelente Fin de Semana!!! Todo por hoy futuros IACPA!

Próxima Clase: 1. 2. 3.

Método de los Multiplicadores Modelo de Transbordo Modelo de Asignación

“Vive como si fueras a morir mañana. Aprende como si fueras a vivir siempre.” Mahatma Gandhi