Problema de asignación
Pero no es hasta 1955 cuando Harold W. Kuhn plantea el método húngaro, que fue posteriormente revisado por James Munkres en 1957.
Dicho método está basado fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes Köning y Jenö Egervary.
4 Demanda: Cantidad de artículos que necesita recibir el destino para cumplir sus necesidades.
Implica asignar números a las celdas para satisfacer las restricciones de oferta y demanda.
Una vez creada la matriz se demuestra el valor económico para la realización del producto o servicio correspondiente.
Para alcanzar esta meta, simplemente asigna un costo arbitrariamente grande representado mediante la letra M. M es un número tan grande que si se le resta un número finito cualquiera, queda todavía un valor mayor que los demás.
Para lograr que el modelo este balanceado se pueden agregar trabajadores/tareas ficticias con costos de cero.
El método simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.
La definición formal del problema de asignación (o problema asignación lineal) es Normalmente la función peso es vista como una matriz cuadrada de valores reales C, con lo que el coste de la función queda así: El problema es "lineal" porque la función coste a optimizar así como todas las restricciones contienen solo términos lineales.
Machineco desea reducir el tiempo de preparación total necesario para completar las cuatro tareas.
Se hace mediante la determinación del número mínimo de líneas necesarias para cubrir todos los ceros.
Los números cruzados pero que no se encuentran en intersección de líneas permanece igual.
Dichas restricciones son que cada trabajador debe ser asignado a una sola máquina y no debe quedar ninguna máquina sin un trabajador asignado a ella: Cada trabajador debe estar asignado a una sola máquina o a ninguna si no se selecciona: En cada máquina debe haber un trabajador: Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores...
El costo asociado refleja la velocidad de la secretaria y la exactitud del trabajo.
Hágalo mediante la determinación del número mínimo de líneas necesarias para cubrir todos los ceros (horizontales y verticales).
c) Los números cruzados pero que no se encuentren en intersección de líneas permanecen igual.
En la empresa de computo llamada “El Lago Azul” se tienen 6 circuitos lógicos para ser colocados en 5 equipos.
Se requiere saber cuál es el costo mínimo en la adaptación de los circuitos a las computadoras.
Para resolver el problema es necesario balancearlo; la tabla resulta de la siguiente forma: Resta por renglón.
Elegimos las columnas que tengan un cero y esa será la asignación de cada circuito a computadora.
Si recordamos anteriormente agregamos una columna ficticia para balancear el problema; por lo tanto sobrara un circuito.
En este caso, las condiciones son que cada tripulación debe descansar al menos 8 horas, pero no más de 24.
Los tres hijos de Joe Klyne, John, Karen y Terri, quieren ganar algún dinero para cubrir sus gastos personales durante un viaje organizado por la escuela al zoológico local.
Quedaba entendido que los tres hijos aceptarían la decisión de su padre en lo concerniente a quién desempeñaría cada tarea.
La siguiente tabla resume las licitaciones recibidas: Basándose en esta información, ¿Cómo debe asignar las tareas el señor Klyne?
Si restamos estos valores de las columnas respectivas obtenemos las matriz reducida: Los cuadros con las entradas cero en negritas proporcionan la solución óptima.
Eso quiere decir que John pintará la cochera, Karen podará el césped y Terri lavará los automóviles de la familia.
Como tampoco obtenemos al menos un cero en las filas se vuelve a realizar la operación anterior.
Luego se tacha los ceros que podrían existir en las filas y columnas correspondientes al número tomado.
Como la matriz no está balanceada, es necesario incluir un empleado ficticio: (esto es fundamental para asegurar que haya una respuesta.
