Problema De Asignacion

2.6 Problema de asignación.

El modelo de asignación en realidad es un caso especial del modelo de transporte, en el cual los asignados representan los puntos de origen y las tareas representan los puntos de destino. La cantidad de la oferta en cada punto origen y la cantidad de la demanda en cada punto destino son exactamente iguales a 1. El costo de “transportar” al asignado i a la tarea j escij. El modelo de asignación se puede resolver directamente como un modelo regular de transporte. Sin embargo, el hecho de que todas las cantidades de la oferta y la demanda igualan 1 ha llevado al desarrollo de un algoritmo de solución simple, llamado el método húngaro.


Pasos del método húngaro:
1. Para la matriz del costo original, identifique el mínimo de cada renglón y réstelo de todas lasentradas en el renglón.
2. Para la matriz resultante del paso 1, identifique el mínimo de cada columna y réstelo de todas las entradas de la columna.
3. Identifique la asignación óptima como la asociada con los cero elementos de la matriz obtenida del paso 2.






Ejemplo:
Los tres hijos de Joe Klyne, John, Karen y Terri, quieren ganar dinero para cubrir sus gastos personales durante un viajeorganizado por la escuela al zoológico local. El señor Klyne eligió tres tareas para sus hijos: podar el césped, pintar la cochera y lavar los automóviles de la familia. Para evitar las competencias anticipadas entre hermanos, les pidió que presentaran licitaciones (secretas) para lo que ellos creían que era un pago justo para cada una de las tres tareas. Quedaba entendido que los tres hijosaceptarían la decisión de su padre en lo concerniente a quién desempeñaría cada tarea. La siguiente tabla resume las licitaciones recibidas.


Podar
Pintar
Lavar
John
$ 15
$ 10
$ 9
Karen
$ 9
$ 15
$ 10
Terri
$ 10
$ 12
$ 8











Basándose en esta información, ¿cómo debe asignar las tareas el señor Klyne?.

Procedimiento:
Si pi y qj son los costos mínimos del renglón i y la columna j, como se definen enlos pasos 1 y 2, respectivamente. Los mínimos del renglón del paso 1 se calculan de la matriz original de la siguiente manera.






Podar
Pintar
Lavar
Mínimo del renglón
John
15
10
9
p1 = 9
Karen
9
15
10
p2 = 9
Terri
10
12
8
p3 = 8

Se resta el mínimo del renglón de cada renglón respectivo, para obtener la siguiente matriz reducida.















Podar
Pintar
Lavar
John
6
1
0
Karen
0
6
1
Terri
24
0
Mínimo de la columna
q1=0
q2=1
q3=0

La aplicación del paso 2 proporciona los mínimos de la columna, restando estos valores de las columnas respectivas, se obtiene la nueva matriz reducida.












Podar
Pintar
Lavar
John
6
0
0
Karen
0
5
1
Terri
2
3
0






Resultado:
Los cuadros con las entradas cero subrayadas proporcionan la solución óptima. Esto quiere decir que John pintará lacochera, Karen podará el césped y Terri lavará los automóviles de la familia. El costo total para el señor Klyne es 9 + 10 + 8 = 27 dólares. Además, esta cantidad siempre igualará (p1+p2+p3) + (q1+q2+q3) = (9+9+8) + (0+1+0) = 27 dólares.











Los pasos dados del método húngaro funcionan bien para el ejemplo anterior porque sucede que las entradas cero en la matriz final producen una asignaciónfactible, en el sentido de que cada niño es asignado exactamente a una tarea. En algunos casos, los ceros creados por los pasos 1 y 2 quizá no den directamente una solución factible. En este caso, se necesitan algunos pasos adicionales para encontrar la asignación óptima (factible). Mediante el siguiente ejemplo se ilustra esta situación.






Ejemplo:
Suponga que la situación que se expuso en elejemplo anterior se extiende a cuatro niños y cuatro tareas. La tabla siguiente resume los elementos de costo del problema.


Tarea

1
2
3
4
1
$ 1
$ 4
$ 6
$ 3
Niño 2
$ 9
$ 7
$ 10
$ 9
3
$ 4
$ 5
$ 11
$ 7
4
$ 8
$ 7
$ 8
$ 5










Aplicando a estos datos los pasos 1 y 2 se obtiene la siguiente matriz reducida.

Paso 1
Tarea

1
2
3
4
Mínimo del renglón
1
1
4
6
3
p1 = 1
Niño 2
9
7
10
9
p2 = 7
3
4...