Modelo de transporte PDF

Preview

Summary

En este trabajo se explica lo que es el modelo de transporte y ejemplos....

Description

FACULTAD DE INGENIERÍA ESCUELA PROFESIONAL DE INGENIERÍA EMPRESARIAL Curso: Investigación de operaciones I Docente: Panta Medina, Esteban

Tema: Modelo de transporte

Alumnas: Anaya Meza, Ivonne Chafloque Santisteban, Mirella Granados De la Cruz, Yenni Patazca Silva, Meylin

Lima, Perú 2020 - I

ÍNDICE Pág. INTRODUCCIÓN

DESARROLLO 2.1 Modelo de PL: 2.2 Técnicas para la solución Básica Inicial de modelos de transporte: 2.2.1 Método de la esquina noroeste: Algoritmo de la solución de la esquina noroeste: 2.2.2 Método de la mínima matriz: Algoritmo de la mínima matriz: 2.2.3 Método vogel: Algoritmo de Vogel: 2.2.4 Método de los flujos mutuamente preferibles: 2.2.5 Método de cost preprocessing:

2.3 Casos especiales de transporte 2.3.1 Localizaciones artificiales(celdas artificiales): 2.3.2. Degeneración: 2.3.3. Método de asignación:

2.4 Técnica para la solución óptima de modelos de transporte: Método U-V 2.5 Uso de software Excel o INVOP CONCLUSIONES

2

4 4 6 9 9 12 13 17 17 23 23

23 23 24 25

25 26 28

2

MODELO DE TRANSPORTE

1

I.

INTRODUCCIÓN

Desde hace mucho tiempo, el transporte comenzó a tener un gran posicionamiento en la sociedad debido al desarrollo de grandes sistemas de transporte, el mismo que ha generado ingresos significativos a los países de todo el mundo ya que las personas tienen la necesidad de movilizarse ya sea por modo de transporte terrestre, aéreo y marítimo. Es así como el transporte es de suma importancia en la economía de un país, por tanto, influye en las decisiones que se da en el área administrativa de un gobierno. .El problema de transporte está relacionado principalmente con determinar la manera óptima de transportar bienes, mientras que en el problema de asignación se persigue realizar la asignación óptima de personas a ciertas tareas; además, se verá que el problema de asignación es en realidad un caso especial del modelo de transporte. En ese contexto mencionado, en cualquier industria, empresa o negocio, podemos llegar a la conclusión de que en alguna actividad se encuentra presente el transporte de bienes o productos desde los centros de producción denominados orígenes a los centros de consumo llamados destinos: por lo que el llevar a cabo esta actividad de manera óptima, es decir, al menor costo posible, nos representará ventajas económicas y competitivas. El transporte de bienes o productos, materia prima, equipos, etc., está inmerso en la tendencia actual de la globalización, por ejemplo, los productos textiles que se manufacturan en un país, se etiquetan en otro y tienen una distribución a nivel internacional como productos terminados. Debido al desarrollo y su gran relevancia del transporte, es que hay una contraparte, siendo los problemas en tiempos, infraestructura y costos. Por ello, es que mediante el uso de modelos de transporte, se resolverá los problemas causados por el mismo transporte, utilizando los diversos modelos que hay en los programas adecuados que posteriormente se explicarán. El informe consta de cuatro partes, las cuales son; la primera, trata de el uso de la programación lineal para la resolución de modelos de transporte; la segunda, sobre 2

las técnicas para la solución básica inicial de modelos de transporte; tercero, los casos especiales de transporte, y finalmente, el uso de software INVOP. El objetivo del presente trabajo es comprender los diferentes métodos existentes para la solución de problemas que se presentan al momento de transportar las unidades o productos para optimizar recursos. Ya que al aplicar estos métodos actuaremos minimizando los costos de envío de transporte de mercancías, determinando tarifas convenientes.

3

II.

DESARROLLO

Modelo de transporte 2.1 Modelo de PL: La programación lineal puede ser utilizada para la resolución de modelos de transporte, aunque no sea sensato resolver los modelos mediante el Método Simplex, si puede ser de gran utilidad la fase de modelización, la programación carece de la practicidad de los métodos de asignación, pero puede ser de gran importancia dependiendo de la complejidad de las restricciones adicionales que puede presentar un problema particular. El método del transporte de la programación lineal, no es como la metodología de tablas y gráficos (de ensayo y error), proporciona un plan óptimo para minimizar los costes. Este método fue formulado por E. H. Bowman en 1956, es un caso especial de programación lineal especialmente eficaz porque incluye a todas las alternativas reactivas más las variables relacionadas con las contrataciones y despidos. El método del transporte es una aplicación singular de la programación lineal cuyo objetivo es determinar el esquema de transporte que minimice el coste total de este, conocidos los costes unitarios desde el origen i hasta el destino j. Además, se sabe que el producto está disponible en una determinada cantidad bi en cada uno de los m orígenes, y es necesario que sea llevado a cada uno de los n destinos posibles en una cantidad demandada dj. La formulación de un problema de transporte, siguiendo un modelo de programación lineal será:

4

Donde: — Z: función de costes totales que se desea minimizar. — cij: coste de transportar una unidad de producto desde el origen i (i=1, 2,..., m) hasta el destino j (j=1, 2,..., n). — xij: cantidad transportada de producto desde el origen i hasta el destino j. — bi: cantidad disponible de producto en cada origen i. — dj: cantidad demandada de producto en cada destino j. Los problemas de transporte pueden ser resueltos mediante el Algoritmo del Simplex. Sin embargo, dadas las peculiaridades de este problema han aparecido otros algoritmos específicos que facilitan el proceso. Para su implementación se representa el problema en una tabla de doble entrada:

Como premisa de partida se supone que la demanda total de un producto es igual a su disponibilidad:

Para que un problema pueda ser solucionado por el método de transporte, este debe reunir tres condiciones: 1) La función objetivo y las restricciones deben de ser lineales. 2) Los artículos deben de ser uniformes e intercambiables, los coeficientes de todas las variables en la ecuación deben de ser 0 o 1. 3) La suma de las capacidades de las fuentes debe ser igual a la suma de los requerimientos de los destinos, si alguna desigualdad existe una variable de holgura deberá ser añadida. 5

2.2 Técnicas para la solución Básica Inicial de modelos de transporte: Como el caso de método SimpleX, el algoritmo de transporte consiste en empezar con una solución inicial y moverse de una solución básica a otra en un número de finito de iteraciones. En el método de transporte, sin embargo, la solución inicial no es solución factible cero, (Z = 0, todas las variables reales son iguales a cero) si no una de las posibles soluciones. Un caso particular es el método de transportes, por lo cual se han propuestos diferentes método a los ya estudiados, los cuales son: Método de la esquina noroeste, Método Mínima matriz y Método de aproximación de Vogel, que servirán para resolver los modelos asociados. El método Nor-Oeste y el método vogel, son alternativas que se pueden utilizar para encontrar una solución inicial factible con una alta probabilidad de ser la que optimiza el objetivo. Construcción de la tabla inicial: 1. Verificar que la oferta total y demanda total sean iguales. 2. Construir una tabla con “n” filas y columnas, en donde se coloca en las filas el número de orígenes y en las columnas el destino. 3. En la primera fila, comenzando por la segunda columna se escribe los nombres de destino y en la última fila estará la oferta. 4. En la primera columna, a partir de la segunda fila se escribirá los nombres del origen y en la última fila estará la demanda. 5. Dentro de las intersecciones, se escribe el costo de la transportación desde el origen asociado a la fila hacia el destino asociado a la columna. 6. En la columna oferta se coloca esta asociada al origen de la fila. 7. En la fila demanda se coloca lo requerido asociado al destino de la columna. Pasos para resolver el método de transporte: El método general de resolución del problema de transporte consta de tres fases que conforman el algoritmo de transporte. Fase A. Paso 1.-Escribir el problema de transporte en la forma matricial. Si el problema es no equilibrado, transformarlo en equilibrado. A continuación, ir al paso 6

Fase B. Paso 2.-Determinar una solución básica factible inicial. A continuación, ir al paso 3. Fase C. Paso 3.-Si la solución obtenida en el paso 2 es óptima, detener el proceso. En otro caso, ir al paso 4. Paso 4.-Obtener una nueva solución que mejore la anterior. Ir al paso 3 -

Determinación de una solución inicial:

Dentro de la fase B, existen diferentes métodos para determinar una solución básica factible inicial, entre los que cabe citar: Northwest Corner Method (NWC) o Método de la Esquina Noroeste (MEN); Vogel‘s Approximation Method (VAM) o Método de Aproximación de Vogel; Matrix Minimum (MM). -

Optimalidad y mejora de una solución:

Una vez finalizada la Fase B que ha proporcionado una solución básica inicial factible no degenerada, es necesario desarrollar la Fase C del algoritmo de transporte, que consiste en determinar si la citada solución es óptima y, en caso de no serlo, obtener una nueva solución con menor coste que la solución actual. Si la solución básica obtenida no es óptima, la mejora es posible y ésta se puede llevar a cabo mediante diferentes métodos o algoritmos, entre los que cabe citar el de Stepping-Stone, Dantzig (1951); el método de los multiplicadores u-v, Dorfman et al. (1964); el de Ford-Fulkerson (1962); el de Separación en Estrella de Zimmern (1957) y el método gráfico de Vidale (1958). En la mayoría de ocasiones, la utilización del algoritmo u-v, supone ahorros en tiempo con respecto al algoritmo de Stepping-Stone en la resolución de problemas de transporte debido a su rapidez y el fácil tratamiento de las soluciones degeneradas. Este método, u-v utiliza el dual del problema de transporte. -

Resolución del problema del transporte:

El algoritmo de transporte consta de tres fases: A, B y C. Como se ha indicado anteriormente, dentro de la Fase B para la determinación de una solución básica factible inicial, existen diferentes métodos o algoritmos. El objetivo de este artículo, es aportar un algoritmo para determinar una solución básica factible inicial próxima a la solución óptima de forma sencilla y sin apenas realizar cálculos, de manera que 7

mediante el posterior proceso de optimización y mejora y tras pocas iteraciones (Fase C), se obtenga la solución óptima. Este algoritmo, proporciona como máximo (m + n -1) posiciones localizadas, siendo las variables asociadas con dichas posiciones las correspondientes a las variables básicas iniciales. El algoritmo propuesto se basa en satisfacer columna a columna la tabla de un problema de transporte, de manera secuencial. No se justifica en forma analítica, sino que está basado en la noción intuitiva de que determinadas posiciones o casillas, tienen una probabilidad más elevada de no estar incluidas en la solución óptima (en concreto, las de mayor coste). A continuación pasamos a exponer los pasos correspondientes al algoritmo propuesto. 2.2.1 Método de la esquina noroeste: El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución, mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes, sin que esto implique que se alcance el costo óptimo total. Este método tiene como ventaja frente a sus similares, la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado. Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método es la esquina Noreste, Sureste o Suroeste. -

Algoritmo de la solución de la esquina noroeste:

Se parte por esbozar en forma matricial el problema, es decir, filas que representan fuentes y columnas que muestren o signifiquen los destinos, luego el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina superior izquierda).

8

Paso 1: En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda. Paso 2: En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del «Paso 1», si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso. Paso 3: Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, «detenerse». La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el «Paso 1» -

Ejercicio:

Es importante mencionar que para entender se debe tomar en cuenta la tabla genérica del problema de transporte, entonces, se comienza por el elemento de la esquina superior izquierda (x11) y se elige entre el menor valor de su disponibilidad (b1) y su demanda (d1), es decir, x11=Min (b1, d1). Se repite este proceso hasta completar el valor de la fila (disponibilidad) o de la columna (demanda), hasta alcanzar una solución inicial factible. 9

Entre las ventajas de su implementación se encuentra la rapidez y comprender la facilidad de este método, siendo su primordial inconveniente que no tiene en cuenta los costes derivados del transporte en la asignación de rutas. Para una mejor comprensión nos vamos a basar en un pequeño ejemplo. Imaginemos que una pequeña empresa textil fabrica su producto en dos centros de trabajo (A, B), de manera que en el primero se elaboran 300 unidades y en el segundo 500 unidades. Dicho producto es vendido en tres mercados, cuyas demandas son 150, 250 y 400 unidades, respectivamente. La matriz de costes unitarios de transporte facilitada por la empresa es la siguiente:

En primer lugar construimos la tabla de transporte del problema:

Comenzamos por determinar el valor de la casilla superior izquierda: x11=Min(b1, d1)=Min(300,150)=150, es decir, se transportan 150 unidades del origen 1 hasta el mercado 1, quedando satisfecha la demanda de dicho mercado.

10

Seguimos el proceso, por lo que tenemos que establecer el valor de la nueva esquina noroeste, en este caso la casilla x12=Min(b1, d2)=Min(300-150,250)=150, quedando agotada la disponibilidad del producto en el primer centro de trabajo.

A continuación proseguimos con el proceso asignando el valor de la siguiente esquina noroeste: x22=Min(b2, d2)=Min(500, 250-150)=100, resultando completada la demanda del segundo destino.

Completamos el proceso de búsqueda de la solución inicial factible asignando el último valor x23=Min(b2, d3)=Min (500-100, 400-0)=400.

Como el número de variables básicas es igual a (m+n-1)=(2+3-1)=4, se trata de una solución no degenerada. Conocidos los costes unitarios de transporte, el coste total generado sería:

11

2.2.2 Método de la mínima matriz: El método del costo mínimo o método de la mínima matriz es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos. Este algoritmo es mucho más sencillo que los anteriores, dado que se trata simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el método. -

Algoritmo de la mínima matriz:

Paso 1: De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda. Paso 2: En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del «Paso 1», si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso. Paso 3: Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, «detenerse». La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el «Paso 1». -

Ejercicio:

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y 12

Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente. Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla:

Cali

Bogotá

Medellín

Barranquilla

Planta 1

5

2

7

3

Planta 2

3

6

6

1

Planta 3

6

1

2

4

Planta 4

4

3

6

6

Y nos dicen que, se formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte. Entonces, seleccionamos la celda con menor valor, es decir la menos costosa, para asignar la mayor cantidad posible Cali

Bogotá

Medellín

Barranquilla

Oferta

Planta 1

5

2

7

3

80

Planta 2

3

6

6

1

30

Planta 3

6

40

2

4

60

Planta 4

4

3

6

6

45

Demanda

70

40

70

35

1

En este caso se presenta un empate, este se rompe de forma arbitraria, así que se le asigna a cualquiera la mayor cantidad posible. Luego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la «Planta 3», en un proceso muy lógico. Dado que Bogotá se queda sin demanda esta columna desaparece, y se repite el primer proceso.

13

Cali

Bogotá

Medellín

Barranquilla

Oferta

3

80

Planta 1

5

7

Planta 2

3

6

Planta 3

6

2

4

60

Planta 4

4

6

6

45

Demanda

70

70

35

Medellín

Barranquilla

Oferta

5

7

3

...