Problema de asignación en la programación lineal: Introducción y modelo de asignación
El problema de asignación es un tipo especial de problema de programación lineal que se ocupa de la asignación de los diversos recursos a las diversas actividades de forma individualizada. Lo hace de tal manera que el costo o el tiempo involucrado en el proceso es mínimo y la ganancia o venta es máxima. Aunque los problemas se pueden resolver con el método símplex o con el método de transporte, el modelo de asignación proporciona un enfoque más simple para estos problemas.
En una fábrica, un supervisor puede tener seis trabajadores disponibles y seis trabajos para despedir. Tendrá que tomar una decisión sobre qué trabajo debe asignarse a cada trabajador. El problema se forma uno a uno. Este es un problema de asignación.
1. Modelo de asignación:
Supongamos que hay n facilidades y n trabajos, está claro que, en este caso, habrá n asignaciones. Cada instalación o dicho trabajador puede realizar cada trabajo, uno a la vez. Pero debe haber cierto procedimiento mediante el cual se debe realizar la asignación para maximizar la ganancia o minimizar el costo o el tiempo.
En la tabla, Co ij se define como el costo cuando se asigna j trabajo a i th trabajador. Tal vez se indique aquí que este es un caso especial de problema de transporte cuando el número de filas es igual al número de columnas.
Formulación matemática:
Cualquier solución básica factible de un problema de asignación consiste en (2n - 1) variables de las cuales las variables (n - 1) son cero, n es el número de trabajos o el número de instalaciones. Debido a esta alta degeneración, si resolvemos el problema mediante el método de transporte habitual, será un trabajo complejo y que requiere mucho tiempo. Así se deriva una técnica separada para ello. Antes de pasar al método absoluto es muy importante formular el problema.
Supongamos que x jj es una variable que se define como
1 si el trabajo se asigna a una máquina o instalación j
0 si el trabajo no está asignado a la máquina o instalación.
Ahora que el problema se forma de uno a uno o un trabajo se asignará a una instalación o máquina.
El costo total de la asignación será dado por
La definición anterior se puede desarrollar en un modelo matemático de la siguiente manera:
Determine x ij > 0 (i, j = 1, 2, 3… n) para
Sometido a restricciones
y x ij es cero o uno.
Método para resolver el problema (técnica húngara):
Considere la función objetivo del tipo de minimización. Los siguientes pasos están involucrados en la solución de este problema de asignación,
1. Localice el elemento de costo más pequeño en cada fila de la tabla de costos dada comenzando con la primera fila. Ahora, este elemento más pequeño se resta de cada elemento de esa fila. Por lo tanto, obtendremos al menos un cero en cada fila de esta nueva tabla.
2. Una vez que haya construido la tabla (como en el paso 1), tome las columnas de la tabla. A partir de la primera columna, ubique el elemento de menor costo en cada columna. Ahora resta este elemento más pequeño de cada elemento de esa columna. Habiendo realizado el paso 1 y el paso 2, obtendremos al menos un cero en cada columna en la tabla de costos reducidos.
3. Ahora, las asignaciones se realizan para la tabla reducida de la siguiente manera.
(i) Las filas se examinan sucesivamente, hasta que se encuentra la fila con exactamente un cero (uno). La asignación se realiza a este cero único colocando el cuadrado □ a su alrededor y en la columna correspondiente, todos los demás ceros están tachados (x) porque no se utilizarán para realizar ninguna otra asignación en esta columna. Paso se lleva a cabo para cada fila.
(ii) El Paso 3 (i) se realiza ahora en las columnas de la siguiente manera: - las columnas se examinan sucesivamente hasta que se encuentra una columna con exactamente un cero. Ahora, la asignación se realiza a este solo cero colocando el cuadrado a su alrededor y, al mismo tiempo, todos los demás ceros en las filas correspondientes se cruzan (x) se realiza un paso para cada columna.
(iii) Los pasos 3, (i) y 3 (ii) se repiten hasta que todos los ceros estén marcados o tachados. Ahora, si el número de ceros marcados o las asignaciones realizadas son iguales al número de filas o columnas, se ha logrado una solución óptima. Habrá exactamente una sola asignación en cada columna o sin ninguna asignación. En este caso, vamos al paso 4.
4. En esta etapa, dibuje el número mínimo de líneas (horizontal y vertical) necesarias para cubrir todos los ceros en la matriz obtenida en el paso 3, se adopta el siguiente procedimiento:
(i) Marca de verificación (
(ii) Ahora marca de verificación (
(iii) Ahora marque todas las filas que aún no están marcadas y que tienen asignación en las columnas marcadas.
(iv) Todos los pasos, es decir, (4 (i), 4 (ii), 4 (iii) se repiten hasta que no se puedan marcar más filas o columnas.
(v) Ahora dibuje líneas rectas que pasen a través de todas las filas no marcadas y columnas marcadas. También se puede notar que en una matriz nxn, siempre menos de 'n' líneas cubrirán todos los ceros si no hay solución entre ellos.
5. En el paso 4, si el número de líneas dibujadas es igual a n o el número de filas, entonces, si no, es la solución óptima, luego vaya al paso 6.
6. Seleccione el elemento más pequeño entre todos los elementos descubiertos. Ahora, este elemento se resta de todos los elementos descubiertos y se agrega al elemento que se encuentra en la intersección de dos líneas. Esta es la matriz para tareas nuevas.
7. Repita el procedimiento desde el paso (3) hasta que el número de asignaciones sea igual al número de filas o el número de columnas.
