• Author / Uploaded
• Rodrigo Huelitl Xochitecatl

• Categories
• Investigación de operaciones
• Transporte
• Programación lineal
• Inventario
• Economías

Citation preview

1

Tema No. 4 ALGORITMO DE TRANSPORTE 1.- DEFINICIÓN.El modelo de transporte es un caso particular de los problemas referidos a la programación lineal. Trata situaciones de envío de productos de lugares llamados puntos origen (fuentes de abastecimiento) a los puntos destino (fuentes de consumo), siendo su objetivo, determinar las cantidades óptimas de envío de las fuentes de abastecimiento a las fuentes de consumo que minimicen el costo total del transporte, al mismo tiempo que satisfagan tanto los límites de la oferta como los requerimientos de la demanda. Es decir, si tenemos: Fuentes de Abastecimiento

Fuentes de Consumo

Unidades de oferta ORIGEN

Unidades de demanda DESTINO

Se considera que las unidades de oferta y demanda total son iguales, esto es:

Cuando no se cumple con la igualdad anterior, tenemos: a > b, entonces, se crea un Centro de consumo ficticio C1. Donde C1 = a - b a < b, entonces, se crea un Centro de abastecimiento ficticio C2. Donde C2 = b - a Sea Xij el número (desconocido) de unidades del origen i al destino j. Entonces el modelo matemático para este problema es:

Este modelo es estrictamente para MINIMIZAR FUNCIONES OBJETIVO; pero, recurriendo a los artificios matemáticos podemos MAXIMIZAR CANTIDADES NEGATIVAS. MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

2

2.- PROCESO DE SOLUCIÓN.- Implica: a) b) c) d)

Encontrar una Solución básica inicial Probar la solución para determinar si es la óptima Mejorar la solución cuando no es óptima, y Repetir los dos pasos anteriores hasta que se obtenga la solución óptima

3.- MÉTODOS DE RESOLUCIÓN.a) b) c) d)

Esquina Nor Occidental Matriz de Costo Mínimo Russel Vogel

4.- PROCEDIMIENTO DE RESOLUCION POR EL MÉTODO ESQUINA NOR OCCIDENTAL.4.1.- Se trabaja con la ESQUINA NOR OCCIDENTAL, asignando a ésta casilla, todo lo que sea posible asignar (Solución básica inicial).

D1

O1

O2

D2

7

2

8

4

DT

OT

10 5

8

7

15

4.2.- Determinar si El SISTEMA ES: a) NO DEGENERADO Número de Variables Básicas = Número de puntos origen MAS Número de puntos destino MENOS 1. En el ejemplo del inciso 4.1., tenemos:

b) DEGENERADO Número de Variables Básicas = Número de puntos origen MAS Número de puntos destino MENOS 1 Con este último sistema (DEGENERADO) no se puede trabajar. Se debe evitar añadiendo un "CERO" con carácter de Variable básica en la casilla de MENOR COSTO, y que además, NO FORME CIRCUITO con las Variables básicas existentes, con éste artificio, el Sistema se convierte en NO DEGENERADO.

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

3

Existencia de un circuito con las variables básicas:

D1

D2

7

O1

D3

2

3

10

2 8

O2

2

O3

4

1

7

2

8

8

3

Inexistencia de un circuito con las variables básicas:

D1

D2

7

O1

D3

2

3

10

2 8

O2

4

2

O3

2

1

7 8

8

3

4.3.- Asígnese a la variable Ui el valor de cero en la fila que tenga el mayor número de asignaciones. En caso de empate cualquiera.

D1

O1

7

D2 2

8 O2

8

2 4

5 DT

MSc. Javier Avila Vera Investigación Operativa

8

7

OT

Ui

10 5

15

Administración de empresas U.M.S.A

4

4.4.- Calcular el valor de las variables Ui y Vj en base al valor de Ui asignado y a los valores del costo que estén relacionadas a través de variables básicas de acuerdo a la siguiente fórmula: Cu = Ui + Vj

: Ui = Cu - Vj Vj = Cu - Ui

D1

O1

7

D2 2

8 O2

8

2 4

5 DT

8

7

Vj

OT

Ui

10

0

5

15

-----------

-----------

-----------

4.5.- Calcular el valor de las Variables No básicas (VNB), a través de la siguiente fórmula: VALOR (VNB) = Cu - Ui - Vj

D1

O1

7

D2 2

8 O2

8

2 4

5

OT

Ui

10

0

5

2

DT

8

7

15

-----------

Vj

7

2

-----------

-----------

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

5

4.6.- Analizar: a) Si el Valor de las VNB son cero ó mayores a cero, se tendrá la SOLUCION BASICA FINAL, es decir la solución de COSTO MINIMO. b) Si NO OCURRE LO ANTERIOR, se debe hacer una reasignación, para lo cual se efectuará la REGLA DE LA ESCALERA. 4.7.- REGLA DE LA ESCALERA: a) De las Variables No Básicas, elíjase la más negativa y a partir de ella fórmese un circuito moviéndose de izquierda a derecha, hasta encontrar una variable básica, luego hacia arriba o abajo hasta encontrar otra variable básica; y, así sucesivamente hasta retornar al punto origen. b) A partir del punto origen márquese alternativamente con (+) y (-) a lo largo del circuito. c) De las variables básicas marcadas con signo negativo, ELIJASE LA MENOR y súmese éste valor a las que estén marcadas con (+) y réstese a las marcadas con (-), esto será la asignación óptima Si aún continuase existiendo Variables No básica con signo negativo, se vuelve aplicar la REGLA DE LA ESCALERA, hasta encontrar en definitiva la SOLUCION BASICA FINAL. En ejemplo inicial: D1

O1

7

D2

(-)

2

8 O2

8

(+)

2 (+)

4

(-)

OT

Ui

10

0

5

2

(-1)

5

DT

8

7

15

-----------

Vj

7

2

-----------

-----------

D1

D2

OT

Ui

Reasignando:

O1

7

2

3 O2

8

7 4

5

5 DT

Vj

MSc. Javier Avila Vera Investigación Operativa

8

10

7

15

-----------

-----------

-----------

Administración de empresas U.M.S.A

6

Por lo tanto el resultado será:

EJEMPLO No.1 Una Compañía de renta de Autos tiene problemas de distribución, debido a que los acuerdos de renta permiten que los autos se entreguen en lugares diferentes a aquellos en que originalmente fueron rentados. Por el momento, hay dos lugares (fuentes) con 15 y 13 autos en exceso; y, cuatro lugares (destinos) en los que se requieren 9, 6, 7 y 9 autos, respectivamente. Los costos unitarios de transporte (en dólares) entre los lugares son los siguientes:

D1

D2

D3

D4

O1

45

17

21

30

O2

14

18

19

31

Establecer un programa de costo mínimo, por el método esquina Nor Occidental.

SOLUCION

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

7

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

8

5.- PROCEDIMIENTO DE RESOLUCION POR EL MÉTODO VOGEL.5.1.- En cada fila y columna de trabajo encontrar los dos menores costos, de los cuales obtener su diferencia. 5.2.- Señalar la mayor diferencia encontrada, lo que determinará una fila o columna de trabajo; en caso de empate se seleccionará la fila o columna que contenga el menor costo. 5.3.- Seleccionada la fila o columna, se elegirá la casilla de menor costo y se asignará a ésta la cantidad que sea posible asignar, lo cual permitirá, además, eliminar la fila y/o columna cuya condición se haya satisfecho. 5.4.- Retornar al paso 5.1. hasta terminar las asignaciones. 5.5.- Aplicar el procedimiento desde el paso 4.2.-, del método ESQUINA NOR-OCCIDENTAL. EJEMPLO No. 2 Una Compañía de renta de Autos tiene problemas de distribución, debido a que los acuerdos de renta permiten que los autos se entreguen en lugares diferentes a aquellos en que originalmente fueron rentados. Por el momento, hay dos lugares (fuentes) con 15 y 13 autos en exceso; y, cuatro lugares (destinos) en los que se requieren 9, 6, 7 y 9 autos, respectivamente. Los costos unitarios de transporte (en dólares) entre los lugares son los siguientes:

O1 O2

D1 45 14

D2 17 18

D3 21 19

D4 30 31

Establecer un programa de costo mínimo, por el método vógel. SOLUCION

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

9

EJEMPLO No. 3 Sea D1 = 100.000 Galones D2 = 180.000 Galones D3 = 350.000 Galones Los costos por transporte son:

P1 P2 P3

D1 92 91 87

P1 = 320.000 Galones P2 = 270.000 Galones P3 = 190.000 Galones (Expresados en Ctvos. de dólar) D2 D3 89 90 91 95 90 92

Establecer un programa de Costo mínimo, por el Método VOGEL Y ESQUINA NOR OCCIDENTAL MÉTODO VOGEL

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

10

METODO ESQUINA NOR - OCCIDENTAL

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

11

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

12

6.- PROBLEMAS DE MAXIMIZACIÓN.El modelo de transporte no es estrictamente para minimizar funciones objetivo; sino, también podemos MAXIMIZARLOS. Así, el cambio que se plantea en este tipo de problemas, es que, en vez de contar con COSTOS DE TRANSPORTE se tiene PRECIOS DE TRANSPORTE. Los criterios para resolver este tipo de modelos es el siguiente: a) Cuando trasladamos los "precios" al modelo, éste se incluye con SIGNO NEGATIVO. b) El procedimiento de resolución es el mismo que para los métodos ESQUINA NOR OCCIDENTAL o VOGEL. EJEMPLO No. 4 Una empresa internacional dispone de 30 barcos cargueros que se encuentran en los puertos de Liverpool, Tokio y Nueva York en número de 10 en cada puerto. La empresa puede enviar esos barcos a los puertos del Callao, Guayaquil, Hamburgo y Lisboa cuyas necesidades son: Callao 2 Hamburgo 4 Guayaquil 12 Lisboa 12 Las utilidades que reportaría la asignación de un Barco a determinado puerto de destino aparecen en la tabla siguiente: Utilidades por barco en miles de dólares Americanos Liverpool

Callao 10

Guayaquil 8

Hamburgo 6

Lisboa 4

Tokio

20

16

8

4

Nueva York

18

18

16

8

Determinar por Vogel un plan de distribución que proporcione el máximo beneficio a la empresa. SOLUCION

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

13

7.- PROBLEMA DE LOCALIZACION El método de transporte también apoya a resolver problemas de localización de instalaciones múltiples, en este caso determinaremos la pauta de asignación que minimice el costo de embarcar productos desde dos o más plantas hasta dos o más almacenes. EJEMPLO No.5 Una empresa está estudiando la posibilidad de comprar una nueva planta con capacidad de 500 unidades al mes, ahora que sus negocios están en crecimiento. Una posible localización para esa nueva planta está en la zona de Villa Fátima. La Tabla No. 3 muestra la capacidad de las plantas, sus requisitos de almacén y sus costos de transporte a los diferentes almacenes distribuidos en la ciudad de La Paz. Hallar la distribución óptima y el costo total de transporte que asumiría la empresa con esta adquisición. Tabla No. 3

ALMACENES 1 EL TEJAR

2

3

5

6.0

5.4

7

4.6

6.6

400

VILLA FATIMA

REQUISITOS

CAPACIDAD

500

200

400

300

900

SOLUCION

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

14

8.- PROBLEMA DE TRANSBORDO Un problema de transbordo también incluye orígenes, en los que se tiene "fuentes de abastecimiento" y destinos que tienen "fuentes de consumo"; sin embargo, incluye EMPALMES a través de los cuales se puede embarcar productos. Los empalmes pueden ser diferentes a los orígenes y destinos, o bien, un origen o un destino pueden también funcionar como empalme. Normalmente, se dan los costos unitarios de embarque entre todos los sitios con acceso directo y el objetivo es desarrollar un programa de transporte que cumpla todas las demandas a un COSTO MINIMO TOTAL.

+30 OE

0 +180

O

E

D

-200

DE -15

Procedimiento a) Realizar el listado de nodos, identificando los orígenes puros, orígenes empalmes, empalmes puros, destinos empalmes y destinos puros. b) Encolumnar los orígenes puros y los destinos puros con sus respectivas cantidades ofertadas y demandadas. Por otro lado, incluir en ambas columnas los nodos que contengan la característica de empalme con sus respectivas cantidades, siendo cero cuando sea empalme puro o en su caso no corresponda la clasificación en la columna respectiva. c) Sumar los valores parciales de las columnas orígenes puros y destinos puros. d) Añadir a los nodos con la característica de orígenes empalme, empalmes puros y destinos empalme, el mayor valor ofertado o demandado obtenido en el inciso 3. e) Construir la matriz de transporte tomando en cuenta las ofertas y demandas totales, además, de los costos unitarios de transporte descrito en los esquemas del problema de transbordo. Nota.- Cuando no hay ruta entre dos puntos, entonces se coloca un Cu = 1.000 - Cuando se dirigen así mismo, entonces se coloca un Cu = 0 f) Optimizar el modelo de transporte

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

15

EJEMPLO No. 6 Determínese un programa de embarque de costo mínimo para el siguiente problema de transbordo

SOLUCION

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

16

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

17

9.- PROBLEMA DE PRODUCCION La aplicación del modelo de transporte no se limita al transporte de un bien de un lugar llamado origen a otro llamado destino; sino, también se puede analizar y relacionar con problemas en el área de control de producción - inventario de la siguiente manera: MODELO DE TRANSPORTE

PRODUCCION - INVENTARIO

1.- Puntos ORIGENES "i"

1.- Períodos de PRODUCCION "i"

2.- Puntos DESTINO "j"

2.- Períodos de DEMANDA "j"

3.- CANTIDAD de OFERTA en el punto origen "i"

3.- CAPACIDAD de PRODUCCIÓN del período "i"

4.- CANTIDAD DEMANDADA: Punto destino

4.- CANTIDAD DEMANDADA: Período "j"

"j"

5.- Costo de transporte por unidad del punto de 5.- Costo por unidad (producción + inventario + Origen "i" al punto de destino "j" penalidad) en el período "i" para el período "j" Nota.- a) Si se quiere asegurar la llegada de un producto a un período de demanda "j", se debe asignar a ese período el COSTO CERO. b) Por otro lado, si se quiere asegurar que un producto no llegue a un período de demanda "j", se debe asignar a ese período un COSTO PROHIBITIVAMENTE alto (1.000) EJEMPLO No. 7 BORALIS fábrica mochilas para excursionistas. La demanda de su producto ocurre durante los meses de marzo a junio de cada año. La empresa calcula que la demanda para los 4 meses es de 100, 200, 180 y 300 unidades, respectivamente. La compañía utiliza horas extra de mano de obra para fabricar las mochilas y, debido a eso, su capacidad de producción varía mensualmente. Se calcula que BORALIS puede producir 50, 180, 280 y 270 unidades de marzo a junio, respectivamente. Debido a que la capacidad de producción y la demanda para los diferentes meses no es igual, la demanda del mes actual se satisface en una de tres formas: 1.- Producción del mes actual 2.- Producción excedente de un mes anterior 3.- Producción excedente de un mes posterior En el primer caso, el costo de producción por mochila es de 40 dólares. El segundo caso incurre en un costo adicional de almacenamiento de 0.50 de dólar por mochila, por mes. En el tercer caso, se incurre en un costo adicional de 2 dólares de penalidad por cada mes de demora. Determinar el programa de producción óptima para los 4 meses. SOLUCION

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A

18

MSc. Javier Avila Vera Investigación Operativa

Administración de empresas U.M.S.A