Metodo de asignacion. PROCEDIMIENTO

METODO DE ASIGNACION

PROCEDIMIENTO

Los pasos para realizar un problema de asignación se dividen en dos fases, existen ejercicios que se resuelven al aplicar solo la primera fase, pero existen otros que necesitan de las dos fases, las cuales se describen a continuación:

Primera fase:

Paso 1

Hay que verificar que la tabla contenga igual número de trabajos y màquinas, de no ser asi, agregaremos trabajos o maquinas tantas como sean necesarias para que cumpla con la condición de igualdad, se le asigna en cada nueva celda un costo de cero.

Paso 2

Restaremos la cantidad mas pequeña de cada renglón a cada cantidad que esta en ese renglón, con lo cual tendremos al menos, un cero por renglón (si se tiene algo que restar se hace una nueva tabla si lo que vamos a restar son solo “ceros” no tenemos para que hacer una nueva tabla), una vez hecho lo anterior, se resta ahora el valor mas pequeño de cada columna a cada cantidad que esta en dicha columna (si se tiene algo que restar se hace una nueva tabla si lo que vamos a restar son solo “ceros” no tenemos para que hacer una nueva tabla).

Paso 3

Observaremos los renglones de arriba hacia abajo buscando un renglón que tenga solo un cero, si encontramos un renglón que tiene solo un cero, se hace la asignación de esa casilla en ese cero, al mismo tiempo, se eliminaran (tacharan) los ceros que estén en la columna y en el renglón que corresponde a la casilla del cero que estemos asignando.

En caso de no existir renglones que solo tengan un cero, buscaremos renglones que tengan dos ceros si tampoco tenemos renglones con 2 ceros entonces buscamos renglones que tengan tres ceros, etc. En este caso que no se tienen renglones con un solo cero (solo tenemos renglones con 2 o mas ceros) se busca de arriba hacia abajo el renglón que tenga menos ceros, y se asigna el cero que este mas a la izquierda y se tachan los ceros que están en su renglón y en su columna. Despues de hacer esta asignación se vuelven con un cero disponible (no tachado ni asignado).

El paso anterior se realizara hasta que todas las casilas con cero aparezcan asignadas o eliminadas (tachadas) y esto es a la primera fase.

Al aplicar la primera fase pueden suceder dos cosas:

1. Que todas las maquinas y todos los trabajos ya estén asignados, entonces ya tenemos la solución a nuestro ejercicio. El costo de la asignación se obtiene de la primera tabla, tomando los valores de las casillas que quedaron asignadas.
2. Que no todas las maquina estén asignadas, por lo tanto, se aplicara la segunda fase.

Segunda fase:

Tomando la tabla que se generó en la primera fase, se realizan los siguientes pasos:

1. Se marcará (con un asterisco) el renglón o renglones que no hayan quedado asignados.
2. Se busca en ese renglón el cero o los ceros que aparezcan tachados y se marca la columna en la que se encuentra cada cero tachado.
3. Se busca en la columna del cero tachado (paso anterior b) el cero asignado y se marca el renglón en donde se encuentre.
4. Repetimos este procedimiento (incisos b) y c)) hasta que sea truncado, es decir, no aparezcan ceros tachados o asignados en el recorrido.
5. Se dibuja una línea en cada renglón no marcado (con asterisco) y en cada columna si marcada (con asterisco), en base a lo cual haremos una nueva tabla.

Para hacer la nueva tabla, que utilizaremos para volver a intentar la asignación, se siguen los siguientes pasos:

1. De la tabla anterior, se checan todas las casillas por las que no pasa ninguna línea, y observamos que cantidad es las mas pequeña en esas casillas, esa cantidad se la restaremos a cada una de esas casillas por las que no pasa ninguna línea.
2. Todas las casillas por las que pase una sola línea, la cantidad que tiene dicha casilla pasa igual.
3. A las casillas que estén cruzadas (por 2 lineas), se le sumara a la cantidad que tiene la casilla, la cantidad que se resto en el paso 1 de este procedimiento.

Con esta nueva tabla se repite el proceso de asignación desde el paso 3 de la primera fase, tantas veces como sean necesarias hasta que todas las maquinas y todos los trabajos estén asigandos.

...