En este documento se investigara todos los temas relacionados a la unidad III de la materia de Métodos Cuantitativos para la Administración,

INSTITUTO TECNOLOGICO DE CHIHUAHUA II

[pic 1]

TRANSPORTE Y ASIGNACION

*Alan Yair Solis Torres.

*Métodos Cuantitativos.

*Chihuahua Chih.

*17 de Octubre del 2016.

*Oscar H.  Monjaraz  Enrique.

*Trabajo de investigación.

INDICE

                Introducción………………………………………...…………1

                El problema del Transporte…………………..……....……..2

                Método de la esquina Noreste………………………………5

                Método del Costo Mínimo……………………………………8

                Método de Vogel…………………………………………….13

                Modelos de Optimización………………………….………..16

Método de asignación……………………………………….17

Método Húngaro…………………………………………..…23

Interpretación de Resultados………………………….……25

Implementación utilizando software………………….……30

Bibliografía…………………………………………………….34

INTRODUCCION

En este documento se investigara todos los temas relacionados a la unidad III de la materia de Métodos Cuantitativos para la Administración, tales como:

El problema del Transporte, método de la esquina noreste, método del costo mínimo entre otros más, se investigara tanto su concepto (¿Qué es?) así como su procedimiento y  trabajaremos con algunos ejemplos de cada tema.

El problema del Transporte

En este tema se presentan algoritmos para resolver los problemas lineales particulares. El problema de Transporte y El Problema de Asignación

El problema de transporte es una de las primeras aplicaciones importantes de la programación lineal. Se puede representar con un modelo lineal y utilizar el método simplex para resolverlo. Sin embargo, dada la estructura especial de este modelo lineal, se puede construir un método más eficaz para su resolución. En este tema nos ocuparemos del estudio de este método. El problema de transporte trata de enviar unidades de un producto desde m orígenes, O1, . . ., Om, a n destinos, D1, . . ., Dn, en las siguientes condiciones.

• Cada origen Oi , i = 1, . . ., m, dispone de una oferta ai .

• Cada destino Dj , j = 1, . . ., n, realiza una demanda bj .

• cij , i = 1, . . ., m, j = 1, . . ., n, es el coste de enviar una unidad desde el origen Oi al destino Dj ..

El problema es determinar el número de unidades xij que se deben enviar desde cada origen Oi hasta cada destino Dj para realizar el transporte a coste mínimo, teniendo en cuenta que hay que satisfacer las restricciones de oferta y demanda.

La formulación lineal de este problema es la siguiente:

[pic 2]

Las primeras m restricciones están asociadas a las ofertas de los orígenes, que no se deben sobrepasar. Las  siguientes restricciones aseguran que se deben satisfacer las demandas de los destinos. Las variables no pueden tomar valores negativos, ya que representan cantidades de producto que se transportan. La forma estándar del problema de transporte es la siguiente:

[pic 3]

Ejemplo. Supongamos que una empresa productora de barras de pan tiene dos almacenes A1 y A2 desde los cuales debe enviar pan a tres panaderías  P1, P2 y P3. Las ofertas, las demandas y los costes de envío  se dan en el siguiente grafo.

[pic 4]

Para plantear un modelo lineal que represente el problema definimos xij : cantidad de barras de pan que se envían desde cada origen Ai , i = 1, 2, a cada destino Pj , j = 1, 2, 3. El modelo lineal para este problema es el siguiente:

[pic 5]

En este caso las restricciones se pueden escribir con igualdad porque la suma de ofertas es igual a la suma de demandas. Para observar la estructura de la matriz A escribimos el modelo de la siguiente forma:

[pic 6]

En este ejemplo hay 2 orígenes, m = 2, y 3 destinos, n = 3. La matriz A tiene 2 + 3 filas y 2 × 3 columnas. Se puede comprobar que el rango de la matriz es 4. Por otra parte, todos los vectores columna tienen solamente 2 componentes iguales a 1 y las demás son 0. Si denotamos los vectores columna de la matriz A con dos subíndices, es decir, a11, a12, a13, a21, a22, a23, podemos observar en que posiciones aparece un 1 y en que posiciones aparece un 0. Por ejemplo, el vector a11 tiene un 1 en la primera posición y otro 1 en la posición m + 1; el vector a21 tiene un 1 en las posiciones 2 y en la m + 1; el vector a23 tiene un 1 en las posiciones 2 y m + 3. En general, podemos decir que un vector aij de la matriz A tiene un 1 en las posiciones i y m + j.

 En general, la matriz A y su estructura dependen del número de orígenes y destinos. Cualquier problema de transporte de m orígenes y n destinos tiene la misma matriz A. Esta matriz tiene m + n filas y m × n columnas. El rango de A es m + n − 1, es decir, las bases están formadas por m + n − 1 vectores. Los vectores columna de la matriz A tienen solamente 2 componentes con valor 1 y el resto son 0. Para un vector aij de la matriz A los unos están en las posiciones i y m + j. Por tanto, los datos importantes de un problema de transporte son el número de orígenes, el número de destinos, las ofertas, las demandas y los costes de transporte. Esta información es la que se recoge en la que llamaremos forma matricial para el problema de transporte.

METODO DE LA ESQUINA NORESTE

Dado un problema equilibrado, se obtiene una solución factible básica inicial con los siguientes pasos:

Paso 1. Elegir la esquina noroeste (i, j) de la tabla de flujos (inicialmente i = 1, j = 1).

Paso 2. Asignar el mayor flujo posible de transporte, xij , en esa posición. Es decir, xij = min {ai , bj}. Actualizar la oferta ai y la demanda bj . • Si el mínimo es ai , la oferta del origen Oi se actualiza a cero y se prescinde de la fila i para asignaciones posteriores. Se actualiza la demanda a bj − ai . • Si el mínimo es bj , la demanda del destino Dj se actualiza a cero y se prescinde de la columna j en las asignaciones siguientes. Se actualiza la oferta a ai − bj . • Si ai y bj tienen el mismo valor, se actualizan la oferta y la demanda a cero al mismo tiempo. Se prescinde de la fila i y de la columna j en asignaciones posteriores.

...