Investigacion de operaciones

UNIDAD IV: TRANSPORTE Y ASIGNACION
4.3.- METODO MODI
El algoritmo 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. En general, supone ahorros en tiempo respecto a la utilización del 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.
El método MODI o u-v utiliza el dual del problema de transporte y viene dado por:
Para aplicar el algoritmo correspondiente aeste método, se introducen los llamados números MODI, definidos así:
Ri = –uj (número MODI correspondiente a la fila i-ésima)
Kj = –vj (número MODI correspondiente a la columna j-ésima)
Estos valores se sitúan en sus respectivas filas y columnas a la derecha y en la parte inferior de la tabla de transporte. El valor indicador _ij de cada variable xij es: _ij = Rj + Kj + cij

4.4.- PROCEDIIMIENTODE OPTIMIZACION

Se trata de desarrollar la Fase C del algoritmo de transporte una vez finalizada la Fase B, que ha proporcionado una solución básica factible no degenerada.
Esta fase trata de determinar si dicha solución es óptima y, en caso de no serlo, obtener una nueva solución con menor coste que la solución actual.
Una solución óptima puede ser degenerada, pero no puede serlo lasolución a partir de la cual se vaya a obtener otra mejor.
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, entre los que cabe citar el método de STEPPING-STONE[9], el método MODI (Modified-Distribution-Method llamado método u-v)[10], el método de Ford-Fulkerson[11], el método de Separación en Estrella de B. Zimmern[12], elmétodo de las Matrices Reducidas de Dwyer y Galler, el método de A. N. Gleyzal y el método gráfico de M. L. Vidale[13].
El algoritmo de Stepping-Stone conocido también con el nombre del método del paso a paso, consiste en calcular cuál sería la variación del coste al enviar una unidad de producto por una ruta no utilizada, es decir, calcula los costes marginales de cada ruta no utilizada.

4.5.-Definición del problema de asignación

La formulación del problema general de asignación es:
[pic]
Sujeta a:
[pic]
Corresponde a un caso especial del problema del transporte en el cual las variables Xij sólo pueden tomar el valor 0 ó 1; tomar el valor 1 si el origen i se hace corresponder al destino j y 0 en caso contrario.
El algoritmo para resolverproblemas de asignación se denomina Húngaro, ya que fueron dos matemáticos Húngaros, König (1916) y Egervary (1931), los que aportaron las teorías que sirven de base a este método.
Este problema se presenta en diversos casos de toma de decisiones. Los problemas típicos de asignación implican asignar tareas a máquinas, trabajadores a tareas y proyectos, personal de ventas a territorios deventas, contratos a licitaciones, horarios de aulas disponibles a horarios de maestros disponibles, enfermos a camas disponibles del hospital, cierto número de empleados a cierta cantidad de puestos en una empresa, aviones a destinos aéreos, entre otros.
Una característica importante de los problemas de asignación es que se asigna un trabajador, una tarea,..., a una sola máquina, proyecto,....Enparticular se busca el conjunto de asignaciones que optimice el objetivo planteado, tal como minimizar costos, minimizar tiempo o maximizar utilidad.

4.6.- El método húngaro
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación....