Guión de un video de una aplicación de un problema de asignación

	Imágenes a colocar	Texto a colocar	Sonido o Efectos	Segundos
Introducción		Problema de asignación	*Grabación 1  *Muse - Resistance	50seg
Planteamiento		Planteamiento. xij = Persona i hace el trabajo j Min Z = 50x11 + 46x12 + 42x13 + 40x14 + 51x21 +48x22 + 44x23 +47x32 +45x33 +  45x34 Sujeto a  x11 + x12 + x13 + x14 ≤ 2 x21 + x22 + x23 ≤ 2 x32 + x33 + x34 = 1 x11 + x21 = 1 x12 + x22 + x32 = 1 x13 + x23 + x33 = 1 x14 + x34 = 1                 xij ≥ 0	*Grabación 2 *Grabación 3 *Muse - Resistance	80seg.
Resolución		Resolución	*Grabación 4 *Muse - Resistance	1.20seg
Interpretación		Resultados. Min Z = 182	*Grabación 5 *Muse - Neutron Star Collision	20seg
Créditos de imágenes, voces, música y producción		Voces: Jonatan Méndez, Maria Cruz, Fernando López y Saúl Martínez Producción: Jonatan Méndez, Maria Cruz y Saúl Martínez	*Grabación 6 *Muse - Neutron Star Collision	30seg

*Grabación 1: Problema de asignación.

Los Húngaros Denes König y Jeno Egerváry iniciaron con el desarrollo de un método para la solución del problema de asignación. Harold Kuhn creó el método Húngaro con los trabajos de König y Egerváry.

Problema de asignación es un caso especial del problema de transporte en el que lo que se asigna son recursos para realizar tareas. Los asignados no solo pueden ser personas, sino también maquinas, vehículos, plantas, periodos de trabajo, etc.

Debe de cumplir con:

1. El número de asignados debe ser igual al número de tareas, a cada trabajador se le asigna una tarea, cada tarea debe ser realizada por un trabajador, existen costos relacionados C_ij , el objetivo es determinar cómo asignar los trabajadores a las tareas al menor costo. 
2. Es un modelo de programación binario, es decir, que solo toma valores de cero y uno.

*Grabación 2: Se resolverá el siguiente ejercicio:

Una compañía recibe ofertas para cuatro trabajos de construcción. Tres personas realizaron ofertas en relación con los trabajos. Sus ofertas en miles de dólares se dan en la tabla. La persona 1 puede realizar un trabajo pero las personas 2 y 3 pueden llevar a cabo dos tareas. Determinar la asignación de costo mínimo de personas a trabajos.

La tabla es la siguiente.

*Grabación 3: El modelo de programación lineal es este.

La red aparece ya balanceada, puesto que las Personas 2 y 3 pueden ser asignados a dos trabajos, es por eso que colocamos un par de nodos extra que significa la opción de poder asignarle a una persona 2 trabajos, puesto que el problema es de asignación: solo una persona puede ser asignado a un trabajo y viceversa. Entonces ficticiamente tenemos 5 Personas y 4 trabajos, eso implica que el trabajador 2 o 3 realizaran solo un trabajo y el otro 2, por lo tanto debemos añadir un trabajo ficticio.

La tabla de transporte es la siguiente.

Se muestra 5 renglones y 5 columnas por lo antes dicho, en el costo del renglón 1 columna 5 se le colocara M porque el problema dice que la Persona 1 debe forzosamente hacer un trabajo.

Se usará el método Húngaro para la resolución del problema.

*Grabación 4: 

Al comienzo del método debemos de encontrar el costo menor de cada renglón y restárselo respectivamente. En nuestro caso esos números son: en el renglón 1 es el número 40, en el 2, 3, 4 y 5 es el 0;  y el resultado lo anotamos en otra tabla. Después buscamos el costo menor en las columnas de la nueva tablas y se lo restamos respectivamente. En nuestro ejemplo son: en la columna 1 es el 10, en la 2 es el 6, en la 3 es el 2 y en las columnas 4 y 5 es el 0; y volvemos a escribir los resultados en una nueva tabla, a esta se llama Matriz Reducida.

Una vez obtenida esta matriz, a esta le trazamos líneas que cubran la mayor cantidad de ceros con la mínima cantidad de líneas. En nuestro caso trazamos una línea que cubra todo el renglón 1 y toda la columna 5 y con esto cubrimos la mayor cantidad de ceros.

Como todavía el número de líneas hechas no es igual al número de renglones, elegimos el costo menor de toda la tabla discriminando los costos que estén en alguna línea y después se lo restamos a los costos que no estén en las líneas y se los sumamos a los costos que se encuentren en las intercesiones de líneas. En nuestro caso ese valor es el 41.

Una vez haciendo lo anterior volvemos a cubrir con el menor número de líneas el mayor número de ceros. En nuestro caso, ahora quedarían las líneas en el renglón 1 y las columnas 1, 2 y 5. Entonces ahora tenemos 4 líneas, por lo tanto buscamos el costo mas pequeño de la tabla que no esté en las líneas; este es el 1.

Una vez restado el 1 volvemos a trazar las líneas, y ahora nos quedan en los renglones 1, 2 y 3 y en las columnas 2 y 5. Por lo tanto ya tenemos 5 líneas, solo nos queda asignar los trabajos.

Elegimos el única cero que este en la columna o renglón (si hay más de uno elegir indistintamente), en nuestro caso elegimos el que se encuentra en la columna 4 y tachamos los ceros que se encuentren en su renglón y columna. Ahora buscamos otro cero que se encuentre solo, en nuestro caso no hay, entonces elegimos indistintamente; elegimos el que se encuentra en la columna 1 renglón 2 y tachamos los ceros que se encuentren en su renglón y columna.

Otra vez buscamos algún cero que se encuentre solo, entonces elegimos el de la columna 3 renglón 3 y tachamos los que se encuentren en su renglón y columna. Después elegimos un cero que se encuentre solo, y volvemos a encontrar que no hay, entonces elegimos indistintamente, nosotros elegimos el del renglón 4 columna 2. Por ultimo solo nos queda un cero y es el de la columna 5 renglón 5.

*Grabación 5: Viendo la tabla concluimos que a la Persona 1 se le asignara el trabajo 4, a la Persona 2 se le asignara el trabajo 1 y 3, y por ultimo a la Persona 3 se le asignara el trabajo 2. Esta asignación costara 182.

*Grabación 6:

Voces: Jonatan Méndez Lopez, María Cruz Hernandez, Saúl Martínez Chavelas.

Producción: Jonatan Méndez Lopez, María Cruz Hernandez, Saúl Martínez Chavelas.

Música: Neutron Star Collision, Muse. Resistance, Muse.

Facultad de estudios superiores Acatlán. Septiembre del 2011.

Vídeo: