Problemas de asignacion
Páginas: 9 (2069 palabras)
Publicado: 25 de noviembre de 2010
* Problema de asignación.
Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.
El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos (o trabajos amáquinas), con la condición de que cada hombre puede ser asignado a un trabajo y que cada trabajo tendrá asignada una persona.
La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir, que los recursos totales sean iguales a las demandas totales.
El modelo de asignación tiene sus principales aplicaciones en: Trabajadores,Oficinas al personal, Vehículos a rutas, Máquinas, Vendedores a regiones, productos a fabricar, etc.
* Formulación del problema de asignación.
La definición formal del problema del asignamiento (o problema linear del asignamiento) es
Dados dos conjuntos, A y T. de igual tamaño, juntos con una función peso C: A × T → R. Encuentra una biyección f : A → T como la función de coste:
Estáminimizada.
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 "linear" porque la función coste a optimizar así como todas las restricciones contiene solo términos lineales.
* Casos especiales del modelo de asignación
1. Oferta y demanda desiguales.
Cuando la oferta y la demanda sondesiguales, se asigna una actividad ficticia con un costo de cero para mantener la condición de método que debe ser igual número de ofertas y demandas
2. Problemas de maximización.
Considere un problema de asignación en el que la respuesta a cada asignación es una utilidad en vez de un costo. Considere la matriz de utilidades del problema como la característica nueva la cual consiste en que elnúmero que aparece en cada celdilla representa un beneficio en lugar de un costo.
3. Problemas con asignación inaceptable.
Supóngase que se está resolviendo un problema de asignación y que se sabe que ciertas asignaciones son inaceptables. 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 leresta un número finito cualquiera, queda todavía un valor mayor que los demás.
Cuando la oferta y la demanda son desiguales, se asigna una actividad ficticia con un costo de cero para mantener la condición de método que debe ser igual número de ofertas y demandas
* Ejemplo de problema de asignación.
Una empresa dedicada a la compra-venta de equipo de cómputo adquirió cuatro máquinas paraser vendidas; sin embargo, el cliente pide una prórroga de 1 mes para que le entreguen las máquinas. La empresa tiene que almacenar las cuatro durante este tiempo. Se cotizan los precios de cuatro bodegas que pueden almacenar las máquinas, los cuales se muestran en la siguiente tabla:
| Bodega 1 | Bodega 2 | Bodega 3 | Bodega 4 |
Máquina 1 | 5 | 15 | 20 | 10 |
Máquina 2 | 2 |12 | 17 | 7 |
Máquina 3 | 15 | 25 | 30 | 20 |
Máquina 4 | 10 | 20 | 25 | 15 |
Determine la forma de asignar una máquina a cada bodega, de tal manera que se minimice el costo total.
Solución:
Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo número de máquinas y tareas.
Ahora construimos la tabla de asignación, después identificamos elcosto menor de cada una de las filas y se lo restamos a los costos de la misma fila:
| 1 | 2 | 3 | 4 |
1 | 5
0 | 15
10 | 20
15 | 10
5 |
2 | 2
0 | 12
10 | 17
15 | 7
5 |
3 | 15
0 | 25
10 | 30
15 | 20
5 |
4 | 10
0 | 20
10 | 25
15 | 15
5 |
Posteriormente se identifica el costo menor de cada una de las columnas y se lo restamos a los costos de la misma...
Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.
El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos (o trabajos amáquinas), con la condición de que cada hombre puede ser asignado a un trabajo y que cada trabajo tendrá asignada una persona.
La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir, que los recursos totales sean iguales a las demandas totales.
El modelo de asignación tiene sus principales aplicaciones en: Trabajadores,Oficinas al personal, Vehículos a rutas, Máquinas, Vendedores a regiones, productos a fabricar, etc.
* Formulación del problema de asignación.
La definición formal del problema del asignamiento (o problema linear del asignamiento) es
Dados dos conjuntos, A y T. de igual tamaño, juntos con una función peso C: A × T → R. Encuentra una biyección f : A → T como la función de coste:
Estáminimizada.
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 "linear" porque la función coste a optimizar así como todas las restricciones contiene solo términos lineales.
* Casos especiales del modelo de asignación
1. Oferta y demanda desiguales.
Cuando la oferta y la demanda sondesiguales, se asigna una actividad ficticia con un costo de cero para mantener la condición de método que debe ser igual número de ofertas y demandas
2. Problemas de maximización.
Considere un problema de asignación en el que la respuesta a cada asignación es una utilidad en vez de un costo. Considere la matriz de utilidades del problema como la característica nueva la cual consiste en que elnúmero que aparece en cada celdilla representa un beneficio en lugar de un costo.
3. Problemas con asignación inaceptable.
Supóngase que se está resolviendo un problema de asignación y que se sabe que ciertas asignaciones son inaceptables. 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 leresta un número finito cualquiera, queda todavía un valor mayor que los demás.
Cuando la oferta y la demanda son desiguales, se asigna una actividad ficticia con un costo de cero para mantener la condición de método que debe ser igual número de ofertas y demandas
* Ejemplo de problema de asignación.
Una empresa dedicada a la compra-venta de equipo de cómputo adquirió cuatro máquinas paraser vendidas; sin embargo, el cliente pide una prórroga de 1 mes para que le entreguen las máquinas. La empresa tiene que almacenar las cuatro durante este tiempo. Se cotizan los precios de cuatro bodegas que pueden almacenar las máquinas, los cuales se muestran en la siguiente tabla:
| Bodega 1 | Bodega 2 | Bodega 3 | Bodega 4 |
Máquina 1 | 5 | 15 | 20 | 10 |
Máquina 2 | 2 |12 | 17 | 7 |
Máquina 3 | 15 | 25 | 30 | 20 |
Máquina 4 | 10 | 20 | 25 | 15 |
Determine la forma de asignar una máquina a cada bodega, de tal manera que se minimice el costo total.
Solución:
Como se puede observar, se tiene un problema balanceado, ya que se cuenta con el mismo número de máquinas y tareas.
Ahora construimos la tabla de asignación, después identificamos elcosto menor de cada una de las filas y se lo restamos a los costos de la misma fila:
| 1 | 2 | 3 | 4 |
1 | 5
0 | 15
10 | 20
15 | 10
5 |
2 | 2
0 | 12
10 | 17
15 | 7
5 |
3 | 15
0 | 25
10 | 30
15 | 20
5 |
4 | 10
0 | 20
10 | 25
15 | 15
5 |
Posteriormente se identifica el costo menor de cada una de las columnas y se lo restamos a los costos de la misma...
Leer documento completo
Regístrate para leer el documento completo.