This video presents a tutorial on the assignment model, a special case of the transportation problem in linear programming. The main objective is to explain how to find the optimal solution for assigning resources, covering model formulation, solving steps, and practical application with examples.
[Música] bienvenidos a esta presentación hoy vamos a desarrollar el tema de el modelo de asignación este es un caso especial del problema de transporte el objetivo a lograr entonces es encontrar la solución óptima de un problema de asignación de recursos la agenda que vamos a desarrollar es la siguiente en el modelo de asignación la formulación en programación lineal la forma general del modelo además los pasos para obtener la solución óptima de un problema de asignación y vamos a hacer la aplicación de este procedimiento en unos ejemplos de aplicación iniciemos el modelo de asignación decimos que es un caso especial del problema de transporte es una variante del problema de transporte el objetivo es asignar m trabajos o trabajadores a n máquinas o tareas en una forma de 1 a 1 un trabajo o un trabajador por máquina y lo que se busca es al menor costo total en este caso tiene la variante con respecto al modelo de transporte en que la asignación es de 1 a 1 bien los trabajos son los orígenes y las máquinas son los destinos similar a la tabla de transporte que ya habíamos utilizado la oferta de que se dispone en cada origen es 1 y la demanda requerida en cada destino también es 1 el costo de asignar el trabajo a la máquina j lo vamos a indicar por sexo y j en el caso que un trabajo no pueda asignarse a una máquina ese elemento de costos es su hijo está le vamos a asignar un valor de m similar al que utilizábamos en el método simple es decir un costo muy grande la formulación en programación lineal lo podemos ver aquí en el tablero el costo total es igual a minimizar z que igual a la sumatoria desde igual a uno hasta m y de tj igual a uno hasta n de todos los es su hijo por los x su hijo está sujeto a las restricciones desde j igual a uno hasta n de los x sub y para todo igual a 123 hasta m y la sumatoria desde e igual 1 hasta m de todos los aquí subí igual a 1 para j igual a 12 hasta m tenemos entonces restricciones de origen y de destino la forma general del modelo es similar a la que hemos utilizado en el problema de transporte con una diferencia que ya teníamos diferentes ofertas y diferentes demandas y en este caso solamente cada origen es uno y cada demanda es uno lo podemos ver en el siguiente tablero observemos que arriba tenemos máquinas que van desde 1 hasta m en la columna de la izquierda tenemos los trabajos que van desde 1 hasta m en la columna de la derecha está la oferta o la disponibilidad y en la última fila las demandas observemos lo que mencionaba anteriormente que la oferta es 1 y la demanda es 1 en los cuadros de en medio de la tabla están todos los costos de asignar un trabajo a una máquina una tarea a un trabajador etcétera por ejemplo en la fila 1 tenemos el c1 1 es el costo de asignar el trabajo 1 a la máquina 1 y así sucesivamente hasta llegar a la n c 1 n en donde decidimos el costo de asignar el trabajo 1 a la máquina n esta tabla es la que vamos a utilizar para hacer los cálculos y aplicar el método de solución para un problema de asignación en el caso que m sea menor que n vamos a agregar n m trabajos ficticios y generalmente le colocamos un valor hace su hijo está de 0 en el caso contrario si m es mayor que n entonces vamos a agregar m n máquinas ficticias también con un costo igual a cero esto es por lo siguiente el problema para resolverlo de asignación debe ser un problema balanceado es decir que las ofertas deben ser igual a las demandas o dicho de otra manera los orígenes deben ser iguales los destinos si no es así lo primero es balancearlo el modelo entonces lo podemos expresar de manera matemática de la siguiente forma x su hijo está va a ser igual a 1 siegel y decimos trabajo se le asigna a la jota décima máxima lo que a esto le hemos llamado variable básica y su hijo está va a ser igual a cero si el décimo trabajo no se asigna a la j décima máquina esto es a lo que le hemos llamado variable no básica bien procedamos ahora a establecer cuál es la metodología de solución los pasos que vamos a seguir son los siguientes quiero mencionar que esta metodología es bastante sencilla comencemos con el paso 1 formar una matriz de costos a partir de la original restando el menor elemento de cada fila de los elementos correspondientes para generar valores iguales a 0 en cada fila en pocas palabras en el primer paso seleccionamos el elemento que tiene menor costo en cada fila y a esa fila le restamos ese elemento siguiente si en la nueva matriz formada hay columnas que no tengan ningún elemento igual a 0 restar el menor elemento de cada una de ellas de los elementos correspondientes similar al paso anterior sólo que ahora en las columnas restamos el menor elemento en cada columna en donde no haya 0 porque en donde ya sea a 0 ya no vamos a hacer esa operación porque estaríamos restando 0 y no cambiaría en nada la columna vemos aquí si es posible hacer la asignación y si no lo es entonces pasamos al siguiente paso número 3 si en la nueva matriz generada los valores iguales a 0 por fila están ubicados en columnas diferentes la asignación es factible y óptima y allí hacemos la asignación y termina el problema de no ser así continuamos con el paso 4 vamos a trazar un número mínimo de líneas a través de algunas de las filas y columnas la idea es tachar todos los ceros vamos buscando hacerlo con el menor número de líneas posibles para tachar todos los ceros que tenga el tablero luego el siguiente paso seleccionar el menor elemento no tachado y se va a restar de todos los no tachados y se va a sumar a todos los elementos que estén situados en las intersecciones de las dos líneas y con eso obtenemos una nueva matriz si esto no se cumple que nos dé una solución óptima regresamos al paso 3 y lo estamos repitiendo interactivamente hasta que éste se cumpla y podamos hacer la asignación óptima procedamos a aplicar estos pasos a la solución de problemas hagamos las aplicaciones encontrar la asignación óptima de los siguientes modelos número 1 una empresa tiene que asignar tres trabajos vamos a llamar 123 a tres máquinas la disponibilidad en cada trabajo que ya dijimos que es uno los requerimientos en cada máquina que también es uno y los costos unitarios de asignación los tenemos en la siguiente tabla acá tenemos toda la información tres trabajos tres máquinas las disponibilidades y los requerimientos y en estos cuadros tenemos los costos de asignación de un trabajo a una máquina tenemos los valores para los tres trabajos y las tres máquinas teniendo todos los datos en esta tabla vamos a proceder a aplicar el procedimiento que acabamos de mencionar bien iniciemos con la solución tenemos la tabla inicial que nos han dado con todos los datos y el primer paso que vamos a realizar es determinar el menor elemento de costo en cada una de las filas por ejemplo en la fila 1 tenemos el primer elemento de costo menor es 5 observemos toda la fila 5 7 9 este es el menor elemento de costo buscamos también el elemento de costo menor para la fila 2 y tenemos que es 10 y para la fila 3 el menor elemento de costo es 3 y acá se los hemos indicado de esta manera para la explicación pero también podemos colocarlo en el tablero en una columna a la derecha luego vamos a restar el este menor elemento de costo de cada fila se lo vamos a restar a todos los elementos de esa fila y procedemos a formar un nuevo tablero observemos el menor elemento de costo de la fila 15 entonces a toda la fila le restamos 55 507 menos 52 y 9 menos 54 hacemos lo mismo con la fila 2 a toda la fila le restamos el menor que 10 y tenemos 40 que lo podemos ir viendo aquí en la fila 2 40 y 12 menos 10 2 y por último la fila 3 su menor elemento de costo es 13 restamos 3 entonces y acá tenemos 2 13 menos 13 0 y 16 menos 13 3 cuando ya hemos realizado estas operaciones vemos si podemos hacer ya la asignación las asignaciones se realizan en aquellas casillas que tienen valor cero veamos la fila 1 tiene este valor de 0 por lo tanto podemos asignarle el origen 1 al destino 1 la fila 2 tiene este valor de 0 entonces podemos aquí asignar el trabajo a la máquina de la 2a lados y la fila 3 tiene este valor de 0 único y la única posibilidad de asignar el 3 qué es el 2 que en este caso nos queda si observamos la columna 2 tiene dos asignaciones y la máquina 3 no tiene asignado ningún trabajo por lo tanto esta asignación no se puede realizar porque la asignación es de 1 a 1 es decir el trabajo no a la máquina 1 el trabajo de la máquina 2 y el trabajo 3 tendría que ser asignado a otro cuando esto sucede desarrollamos el siguiente paso observamos si todavía tenemos columnas que no tengan valor de 0 y realizamos el mismo procedimiento anterior sólo que ahora en la columna buscamos el menor elemento de costo en este caso sólo es en la columna 3 porque en esta ya hay 0 y el menor elemento de costa en la columna 32 ese es el menor y procedemos a restarle a la columna este valor acá tenemos ya la operación realizada a esta columna le hemos restado el valor 2 veamos 4 2 2 2 2 y 0 y 3 - 2 dijimos que las otras columnas ya no realizamos la operación porque estas columnas ya contienen al menos un valor de cero cuando hemos realizado este siguiente paso nuevamente vemos la posibilidad de poder hacer la asignación óptima en la que las casillas que tengan valor cero podemos asignarle a comenzamos con las filas que solamente tienen una casilla con cero porque es la única posibilidad veamos la fila 1 se le puede asignar al destino 1 la fila 30 se le puede asignar al destino 2 dg para después la fila 2 o el origen 2 porque éste tiene dos posibilidades que pueden ser asignadas se puede asignar el 2 al 2 o al 3 entonces pero como ya el 2 ha sido hace perdón el 3 se le asignó al 2 entonces podemos tomar esta casilla y hacer la asignación correspondiente como vemos ya tenemos en este caso la asignación de 1 a 1 de 2 a 3 y de 3 a 2 por lo tanto hemos llegado a la solución óptima para colocar la solución óptima vamos a utilizar para el cálculo de su costo los datos originales del problema es decir en donde nos estaban dando los costos de asignar un trabajo a una máquina por lo tanto la solución óptima es la siguiente asignar el trabajo uno al destino uno en este caso es la máquina 1 el trabajo 2 a la máquina 3 y el trabajo 3 a la máquina 2 el costo mínimo lo vamos a sacar sumando los costos que teníamos en el tablero anterior en estas casillas veamos en la 1 1 el valor del costo es 5 entonces sumamos 5 más el costo de la segunda asignación que es la 2 3 12 + 12 y el de la 32 13 entonces 3 sumamos esto y nos da 30 unidades monetarias hemos llegado entonces al final del problema hemos hecho las asignaciones una a una y determinado el costo mínimo de asignación en este caso sólo fue necesario restar los menores elementos de cada fila y el menor elemento de cada columna que no tenía ceros [Música] bien [Música]
