This video demonstrates how to find the optimal assignment for data presented in a table using a step-by-step process. The example uses four origins and four destinations, illustrating a method for solving assignment problems.
[Música] procedamos ahora a un segundo ejemplo encontrar la asignación óptima para los datos que se presentan en el siguiente cuadro ahora tenemos cuatro orígenes y cuatro destinos lo primero que tenemos que ver es que corresponda el número de orígenes al número de destinos el número de trabajo al número de máquinas el número de tareas al número de personas etcétera como corresponden porque hay cuatro orígenes y cuatro destinos entonces procedemos a su solución lo que vamos a hacer es aplicar nuevamente los pasos anteriores iniciemos para cada una de las filas buscamos el menor valor de la fila 1 vemos que el menor valor es 1 de la fila 2 el menor valor es 7 fila 3 4 y de la fila 4 y el menor valor es 5 luego vamos a restar este menor valor en cada una de las filas correspondientes fila 1 necesitamos 1 a toda la fila y tenemos lo vamos a escribir acá estamos restando 1 a esta fila 1 - 1 04 - 136 menos 153 menos 12 de igual manera le restamos 7 en la fila 2 a todos los números al restarle 7 nos queda esta fila 97 27 70 10 mil 739 72 fila 3 el menor valor es 4 restamos 4 - 405 menos 4 111 menos 4 7 y 7 43 y por último la fila 4 el menor valor de 5 restamos 8 menos 53 75 28 53 y cinco menos 50 como ya realizamos la primera operación revisemos si ya es posible hacer la asignación comencemos siempre con las filas que solamente tienen un valor de 0 fila 1 sólo tiene un 0 significa que sólo podríamos asignarle el origen uno al destino uno la fila 2 también solamente tiene un cero por lo tanto sólo podríamos asignarle el 2 al 2 la fila 3 también solamente tiene un cero es decir esta es la única asignación que podríamos hacer en la 3 pero también en la fila 4 sólo tiene un 0 y por lo tanto la asignación puede ser de 4 a 4 revisemos las asignaciones que nos es posible hacer el 2 asignada al 2 estamos bien el 4 asignado al 4 también es única el 1 sólo puede asignarse al 1 y el 3 sólo puede asignarse al 1 quiere decir que si hemos asignado el 1 al 1 ya no podemos asignar el 3 al 1 por lo tanto el destino 3 aquí no tiene asignación posible aplicamos el siguiente paso es decir vamos a restarle el menor elemento a las columnas que todavía no tienen un valor de 0 en este caso es la columna 3 el menor valor decíamos de esta columna entonces de la columna 33 todos los demás valores del tablero como ya sus columnas tienen cero solamente las trasladamos a la siguiente tabla pero la columna 3 vamos a restarle el menor valor que es 3 entonces restamos 3 a toda la columna 5 - 323 menos 307 menos 3 4 y 3 - 30 con esta nueva operación veamos ahora si ya es posible hacer la asignación óptima la fila 1 sólo puede ser asignada al destino uno el dos tiene dos posibilidades que son el 2 y el 3 el 4 solo tiene dos posibilidades y el 3 solamente tiene una posibilidad por lo tanto si asignamos en la fila 3 al destino 1 que es la única posibilidad que hay la única asignación posible ya podemos observar que allí tenemos dos asignaciones en la misma columna para la origen dos afilados y para la fila cuatro hay para ambos hay dos posibles asignaciones aquí podemos tomar cualesquiera de ellas asignamos del 2 al 2 el 4 al 3 pero vemos que hay una que no puede ser asignada en este caso es si le doy la 1 a la 1 ya la 3 no se puede asignar a la 1 y estas se quedan sin asignación por lo tanto esta asignación no es óptima hemos realizado ya las operaciones de fila y las operaciones de columna y no hemos llegado a establecer cuál es la solución óptima entonces continuamos con el siguiente paso que dice que vamos a tachar en el tablero todos los ceros que éste contenga tratando de utilizar el menor número de líneas posibles comencemos a buscar en el tablero cómo podemos realizar con el menor número de líneas tachar todos los ceros tratamos de buscar aquellas filas o columnas que contengan más ceros por ejemplo la fila 4 contiene 2 la fila 2 contiene 2 la columna 3 contiene 2 la columna 1 contiene 2 por ahí podemos iniciar tachamos la columna 1 con esto hemos eliminado digamos hemos tachado estos dos ceros ahora tachamos la fila 2 con esto eliminamos estos dos ceros y ya prácticamente solo tenemos estos dos entonces podemos tachar la fila 4 observen que ya no tenemos ceros sin tachar se busca utilizar el menor número de líneas posibles porque si no podría darse el caso por ejemplo que digamos tachamos la columna 1 la 2 porque tiene 0 la tres de la cuatro y ya no podemos continuar con el proceso lo que andamos buscando es que haya casillas que no estén tachadas y al hacer el menor número de líneas posibles también estamos acercándonos más a la asignación óptima bien siguiente paso una vez que hemos tachado todos los cerros que contiene el tablero seleccionamos el menor costo que hay de todos los elementos no tachados en este caso tenemos estas tres casillas no tachadas en la fila 1 y tenemos estas tres casillas no tachadas en la fila 3 buscamos el menor elemento de costo en este caso es uno este valor se lo vamos a restar a todos los valores de las casillas no tachadas y se lo vamos a sumar a cada casilla en donde las líneas que hemos utilizado para tachar se cruzan en este caso es fila 2 columna 1 qué fila 4 columna 1 realicemos la operación restamos uno a todos los notas a dos tenemos tres menos uno aquí nos queda 22 menos uno tenemos 1 y 2 menos 11 con los siguientes de esta fila 1 - 10 4 - 1 3 y 3 - 1 2 ahora este valor se lo sumamos a las intersecciones de las líneas que nos han servido para tachar aquí hay un valor de 2 en la casilla 21 le sumamos 1 y nos tenemos 3 en esta otra en la 4 1 su costo es 3 le sumamos el menor que era 1 y tenemos 4 todos los demás valores se dejan tal y como están observemos 0 0 a que se encuentran en esta columna 2 y 0 el 3 y sufrirá alteración porque le restamos 1 por lo tanto hemos encontrado la nueva solución repitiendo tomamos el menor valor y se lo restamos a todas las casillas no tachadas se los sumamos a las intersecciones de las líneas que han servido para tachar y todos los demás valores que no forman parte de ninguno de ellos solo se trasladan a la tabla siguiente veamos ahora si ya es posible hacer la asignación la recomendación es comenzar decíamos con las filas que nada más tienen una casilla con cero el uno con el uno podemos hacer esta asignación el origen 2 tiene dos ceros el 3 tiene dos ceros y el 4 tiene dos ceros veamos la 3 la 3 tiene dos ceros es decir que podríamos asignarle tres a uno o 3 a 2 pero 3 a 1 ya no lo podemos asignar porque ya está asignado 11 entonces procedemos a hacer las siguientes asignaciones al 2 le vamos a asignar el destino 3 también le pude haber asignado el destino 2 pero acabo de explicar de que al 3 no le voy a poder asignar el 1 entonces básicamente solo me queda esta posibilidad de asignar el 3 al 2 por lo tanto el 2 no se lo asignamos al 2 sino que a la siguiente casilla en dónde también se encuentra el valor de cero de esta manera por lo tanto el 1 al 1 el 3 al 2 y el 2 al 3 y por último la 4 también teníamos dos posibilidades en el destino 3 y en el destino 4 pero el destino 3 ya fue asignado al origen 2 entonces solamente nos queda esta posibilidad y hacemos la correspondiente asignación como vemos en el tablero ya cada origen está asignado a cada destino por lo tanto hemos llegado a la solución óptima ahora bien asumamos que en este momento tampoco pudimos hacer la asignación óptima hubo alguno que no podríamos asignarlo en un supuesto a alguna de las en algunos de los destinos en origen a un destino lo que tenemos que hacer es repetir nuevamente este proceso es decir tachar todos los ceros con líneas tratando de utilizar el menor número de líneas posibles y todo el proceso que acabamos de explicar en este paso y eso lo vamos a seguir repitiendo repitiendo hasta que podamos hacer la asignación óptima en este caso ya en particular hemos llegado a la asignación óptima y tenemos la siguiente vamos a asignar el origen uno al destino uno el origen 2 al destino 3 el origen 3 al destino 2 y el origen 4 al destino 4 veamos cuánto nos cuesta esta asignación para poder hacer el cálculo nos tenemos que remitir a los datos originales del problema porque todos estos ya vinieron sufriendo alteraciones al venir haciendo operaciones nos remitimos a los costos originales que nos da el problema de asignación observemos el costo del 1 al 1 es uno entonces sumamos 1 aquí se encuentra más el del 2 al 3 qué es 66 el 2 al 3 perdón el 2 al 3 y 10 entonces más 10 1 10 luego el 3 al 2 el 3 al 2 su costo de 5 sumamos 5 y por último el 4 al 4 el 4 al 4 su valor es 5 y lo sumamos acá por lo tanto nos queda 1 más días 5 5 nos da un costo mínimo de 21 unidades monetarias y con esto hemos encontrado la asignación óptima y resuelto el problema [Música] bien [Música]
