Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Metodo de trasporte y asignacion

No description
by

Ivan Orozco

on 16 July 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Metodo de trasporte y asignacion

MODELO DE TRASPORTE
5.1 INTRODUCCIÓN AL MODELO DE ASIGNACIÓN
5.2 MÉTODOS DE APROXIMACIÓN DE VOGEL.
5.5 EL MÉTODO HÚNGARO.
5.4. DEFINICIÓN DEL PROBLEMA DE ASIGNACIÓN
5.3 MÉTODO MODI.
El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:
1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.

El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.

5.1. Introducción.
5.2. Métodos de aproximación de Vogel.
5.3. Método MODI.
5.4. Definición del problema de asignación.
5.5. El método húngaro.
Metodo de trasporte y asignacion
MODELOS DE ASIGNACIÓN.
Intentar minimizar el coste total de procesamiento y almacenamiento a la vez que intenta reunir ciertas restricciones en el tiempo de respuesta.
El modelo que emplearemos tiene la forma
mín(Coste Total), la cual está sujeta a restricciones del tiempo de respuesta, restricciones de almacenamiento y restricciones de procesamiento.
Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.

El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos (o trabajos a máquinas), con la condición de que cada hombre puede ser asignado a un trabajo y que cada trabajo tendrá asignada una persona.



La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir, que los recursos totales sean iguales a las demandas totales.
El modelo de asignación tiene sus principales aplicaciones en: Trabajadores, Oficinas al personal, Vehículos a rutas, Máquinas, Vendedores a regiones, productos a fabricar, etc.
El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo producen mejores resultados iniciales que los mismos
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
PASO 1.- Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.
PASO2.- Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).
PASO 3.- De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).
PASO 4: DE CICLO Y EXCEPCIONES
- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.
El Método de la distribución modificada (MODI) conocido como el método de los costes ficticios, consiste en añadir a la matriz de costes una fila y una columna que recogen unos costes ficticios determinados arbitrariamente (los números MODI), tal que permite calcular los índices de mejora para las celdas (casillas) no utilizadas sin tener que trazar todos los circuitos (ciclos) que requiere el algoritmo de Stepping-Stone.
Los pasos del método MODI son 5
paso1
Se calculan los coeficientes de renglón y
columna usando celdas llenas: Coeficiente del renglón + coeficiente de la columna = costo en la celda
paso2
Se calcula el costo marginal de usar cada celda vacía: Costo marginal = costo en la celda (coeficiente del renglón + coeficiente de la columna).


Paso3
Se selecciona la celda vacía con el costo marginal más negativo (los empates se rompen arbitrariamente).e usar cada celda vacía: Costo marginal = costo en la celda (coeficiente del renglón + coeficiente de la columna)
Paso 4
Se encuentra la trayectoria de revisión y se llena la celda vacía al máximo que permita la trayectoria.
Paso 5 se repiten los pasos del 1 al 4 hasta que todos los costos marginales sean 0 o positivos.
El problema de asignación es una variación del problema original de transporte, variación en la cual las variables de decisión X solo pueden tomar valores binarios, es decir ser cero (0) o uno (1) en la solución óptima, lo que supone que la oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a uno (1).
Una característica particular del modelo de asignación es que para su resolución no se hace necesario que el número de fuentes sea igual al número de destinos, lo cual es muy común en la vida real teniendo en cuenta su aplicación, pues generalmente la cantidad de aspirantes es exageradamente superior al número de vacantes (lógicamente haciendo referencia a la aplicación del modelo al contexto de oferta y demanda laboral).
El método Húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros. El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente, será entonces cuestión de agregar un paso adicional para abordar ejercicios de maximización.
ALGORITMO HÚNGARO, PASO 1
Antes que nada cabe recordar que el método húngaro trabaja en una matriz de costos n*m
(en este caso conocida como matriz m*m, dado que el número de filas es igual al número de columnas n = m), una vez construida esta se debe encontrar el elemento más pequeño en cada fila de la matriz.

ALGORITMO HÚNGARO, PASO 2
Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso).

ALGORITMO HÚNGARO, PASO 3
Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con la diferencia que este se hall
a de la matriz resultante en el segundo paso, luego se construirá una nueva matriz en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la columna a la cual cada costo corresponde, matriz llamada "Matriz de Costos Reducidos".

ALGORITMO HÚNGARO, PASO 4
A continuación se deben de trazar líneas horizontales o
verticales o ambas (únicamente de esos tipos) con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el menor número de líneas posibles, si el número de lineas es igual al número de filas o columnas se ha logrado obtener la solución óptima (la mejor asignación según el contexto de optimización), si el número de líneas es inferior al número de filas o columnas se debe de proceder con el paso 5.


ALGORITMO HÚNGARO, PASO 5
Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran cubiertos por las lineas del paso 4, ahora se restará del restante de e
lementos que no se encuentran cubiertos por las líneas; a continuación este mismo valor se sumará a los valores que se encuentren en las intersecciones de las lineas horizontales y verticales, una vez finalizado este paso se debe volver al paso 4.
Full transcript