This video demonstrates how to solve an assignment problem using a specific methodology. The example involves assigning four machines to five tasks, with a constraint that machine 4 cannot be assigned to task 4. The video details a step-by-step process to find the optimal assignment.
[Música] vamos a continuar con un tercer ejemplo es el siguiente considere el problema de asignar cuatro máquinas a cinco tareas la máquina 4 no puede asignarse a la tarea 4 para los costos unitarios dados en el siguiente cuadro encontrar la asignación óptima bien aquí tenemos dos situaciones que es precisamente por lo cual se ha seleccionado este ejemplo dice considera el problema de asignar cuatro máquinas a cinco tareas es decir el número de orígenes no es igual al número de distintos segundos dice que la máquina 4 no puede asignarse a la tarea 4 por lo tanto cuando no podemos hacer una asignación lo que hacemos es que le colocamos un costo bastante grande y utilizamos la misma letra que utilizamos en el método simple para indicar una cantidad bastante grande le colocamos el valor de m los datos son los siguientes los 4 máquinas las cinco tareas y acá el origen 4 y el destino 4 no puede ser asignado es decir por eso es que no tiene costo porque no se puede asignar esto a nivel de información que el problema nos proporciona ahora vamos a continuar con el proceso de solución en donde vamos a aplicar la misma metodología que acabamos de realizar en el ejercicio anterior con estas dos consideraciones la de los orígenes y destinos que no son iguales y la de esta cantidad que no puede ser asignado el origen 4 al destino 4 procedamos a resolver el problema lo primero que hacemos es ver cuántos orígenes y cuántos destinos tenemos tenemos cuatro máquinas y cinco tareas para resolver el problema este tiene que ser balanceado es decir el número de orígenes deben de ser igual al número de destinos por lo tanto es necesario agregarle origen ficticio en este caso agregamos el origen 5 para que se nos balance con el número de destinos que son 5 si se observa en el tablero a la fila 5 le hemos puesto costos 0 y además en la casilla 4 columna 4 no podemos asignar por lo tanto ahí no le hemos puesto un costo ahora que ya hemos balanceado el problema y el número de origen es igual al número de destinos iniciamos con el procedimiento lo primero es determinar el menor valor de cada una de las filas para la fila 1 si observamos el menor valor es 2 para la fila 2 también el menor valor de 2 para la fila 3 el menor valor es 5 y para la fila 4 el menor valor es 8 en la fila número 5 pues todos son 0 vamos a restar entonces 0 el menor valor es 0 va a quedar igual una vez que hemos determinado todos los menores valores procedemos a restar serlo para su correspondiente fila y obtenemos la siguiente tabla como ejemplo en la fila 1 el menor valor es 2 restamos 2 a toda la fila 0 8 10 281 22 03 21 15 22 13 y 4 menos 22 de la misma manera procedemos con el resto de filas a la fila 2 le restamos 2 a toda la fila a la fila 3 le restamos 5 también a toda la fila y a la fila 4 le vamos a restar 8 pero observemos que cuando hacemos esta operación 20 - 8 es 12 15 - 87 13 85 y aquí tenemos que no puede haber asignación dijimos que íbamos a poner un valor grande y a ese valor grande le vamos a restar 8 nos va a quedar ese valor grande usamos el mismo que ya se utiliza en el método simple para indicar una cantidad bastante grande entonces decimos que el valor de este es m y 880 lo mismo entonces la fila 5 pues queda igual porque se le resta 0 de esta manera hemos ya ha restado el menor valor a cada una de las filas veamos si es posible hacer ya una asignación óptima la fila 1 solamente tiene un 0 que es fila 1 columna 2 ahí hacemos la asignación la fila 2 también solo tiene un cero en la fila 2 columna 4 observemos la fila 3 también sólo tiene un 0 sólo podemos asignarle las tres a las dos la fila 4 sólo puede ser asignada a las 5 y la 5 puede ser asignada a cualesquiera de ellas asignemos en la una en este caso en el origen 1 si observamos él destino 3 no tiene asignación además si el origen 1 se le asigna al destino 2 el 3 ya no puede ser asignado al destino 2 por lo tanto esta no es una solución óptima procedemos al siguiente paso y es el de restar el menor elemento en cada columna que no contenga ceros observemos el tablero la columna 1 tiene 0 lados también la 3 que no tiene asignación también tiene 0 entonces significa que si yo le restó 0 me va a quedar igual por lo tanto no podemos ya hacer la operación de restar el menor elemento en cada columna y no podemos asignar así como este el tablero entonces procedemos con el paso siguiente que es tachar todos los ceros usando el menor número de líneas posible procedamos aquí en el tablero para determinar de qué manera usamos el menor número de líneas para tachar los ceros de todo el tablero lógico que la fila 5 contiene una cantidad de ceros desde el destino 1 al 5 que podemos nosotros tacharlo y con eso quitamos todos los ceros de la fila 5 ahí comenzamos a buscar por ejemplo la columna 2 tiene dos ceros la columna 4 tiene uno de los que no están tachados las cinco tiene uno la uno ya está tacha del que corresponde y la columna dos mismos tiene dos entonces podemos proceder y tachamos la columna 2 con eso hemos tachado estos dos ceros todavía tenemos un 0 acá y otro acá podemos proceder entonces y tachar la columna 4 y la columna 5 una vez que hemos tratado todos los ceros vamos a determinar el menor valor en todas las casillas no talladas observemos el menor valor de todos los notas chance que es la columna 1 y la columna 3 excepto los de abajo de la fila número 5 el menor es 1 por lo tanto vamos a restar 1 a todos los no tachados y a sumar 1 en aquellas casillas donde se intersectan las filas que hemos utilizado para tachar los ceros y con eso vamos a generar el siguiente tablero restemos 1 que es el menor a la columna 1 y tenemos 8 menos 173 menos 12 10 - 19 y 12m 111 en la columna 31 10 13 - 112 9 18 y 5 14 ahora observemos aquellas casillas donde se interceptan las líneas que hemos usado para tachar a cada una de ellas le sumamos el valor que hemos restado en este caso 10 + 11 0 11 y 0 11 y hemos obtenido una nueva solución veamos ahora la posibilidad de poder hacer la asignación comencemos la fila uno tiene dos ceros la fila dos solo tiene un cero la fila tres también un cero la 41 y las 51 repitiendo la fila uno tiene uno la fila dos tiene la fila uno tiene dos quiere decir que tiene dos posibilidades podemos asignar sólo al 2 o al 3 pero asignamos primero al valor de 3 al destino 3 la razón es que el origen 3 solamente puede ser asignado al origen 2 si asignamos el 1 al 2 entonces ya no podríamos hacer la asignación acá entonces seleccionamos asignarlo al 3 siguiente la fila 2 el origen 2 sólo puede ser asignado al destino 4 el origen 3 solamente lo podemos asignar al destino 2 y de esta manera ya tenemos tres asignaciones la número cuatro el origen 4 sólo puede ser asignado al destino 5 y tenemos la cuarta asignación y por último el destino 5 podría ser asignado al 3 o al 0 perdón al 1 en este caso lo asignamos alumno porque es la que tenemos sin asignación si observamos ya todos los orígenes están asignados a todos los destinos uno a uno por lo tanto hemos llegado a la solución óptima procedamos a de terminar entonces la solución y tenemos la siguiente vamos a asignar el origen uno al destino 3 el origen 2 al destino 4 el origen 3 al destino 2 el 4 al destino 5 y el 5 al destino 1 para determinar el costo mínimo procedemos a buscar los costos que teníamos en el problema original y vemos que del 1 al 3 el costo es 3 del 2 al 4 el costo es 2 del origen 3 al destino 2 el costo es 5 del 4 al 5 al 5 el costo es 8 y del 5 al 1 el costo es cero entonces sumamos tres más dos más 5 más 8 +0 eso nos da un costo mínimo de 18 unidades monetarias con la asignación que hemos realizado similar al ejercicio anterior en este caso si no hubiésemos encontrado la solución óptima procedemos a volver a tachar con filas con líneas las filas y las columnas que tengan cero usando el menor número de líneas posible y seguimos esperando hasta que podamos tener la asignación óptima bien hemos entonces he encontrado la asignación óptima haciendo un resumen de los pasos que se siguen para resolver un problema de asignación lo primero que hay que tomar en cuenta es que el número de orígenes debe ser igual al número de destinos si no lo es tenemos que agregar un origen ficticio o lo que se necesiten y destinos ficticios y le vamos a asignar costos cero y luego aplicar el procedimiento de restar el menor de las filas el menor de las columnas tachar todos los ceros en el tablero con líneas usando el menor número de líneas posibles para llegar a determinar la solución óptima repitiendo ese procedimiento de tachar los ceros con líneas las veces que sea necesario hasta que podamos hacer la asignación óptima con esto concluimos hemos llegado al final de la unidad 5 de transporte y su caso especial que es el problema de asignación y nos vemos en la próxima gracias por la atención [Música] bien [Música]
