Problema de la asignación cuadrática

Origen

El problema de la asignación cuadrática, que se denota por sus siglas en inglés QAP (Quadratic assignment problem), fue planteado por Koopmans y Beckmann en 1957 como un modelo matemático para un conjunto de actividades económicas indivisibles. Posteriormente Sahni y Gonzales demostraron que QAP pertenece a los problemas no polinomiales duros , lo que sumado a que es un problema aplicable a un sinnúmero de situaciones, lo hacen un problema de gran interés para el estudio.

Definición

QAP es un problema estándar en la teoría de localización. En éste se trata de asignar N instalaciones a una cantidad N de sitios o locaciones en donde se considera un costo asociado a cada una de las asignaciones. Este costo dependerá de las distancias y flujo entre las instalaciones, además de un costo adicional por instalar cierta instalación en cierta locación específica. De este modo se buscará que este costo, en función de la distancia y flujo, sea mínimo.
La versión de Koopmans y Beckmann tenía como entrada tres matrices $F=(f_{ij})$ , $D=(d_{kl})$, $B=(b_{ik})$ del tipo real donde $(f_{ij})$ especifica el flujo entre las instalaciones i y j, $(d_{kl})$ especifica la distancia entre las instalaciones k y l y $(b_{ik})$ el costo de instalar la instalación i en la locación k. Por tanto este problema lo podemos modelar de la siguiente forma:

Sea n el número de instalaciones y locaciones. A su vez denotemos por N al arreglo $N=\lbrace 1,2,...,n\rbrace$ .

$min\Sigma _{i=1}^{n}\Sigma _{j=1}^{n}c_{ij\phi (i)\phi (j)}+\Sigma _{i=1}^{n}b_{i\phi (i)}$

Donde $S_{n}$ es el conjunto de todas las permutaciones $\phi :N\rightarrow N$ y donde cada producto de la sumatoria doble corresponde al costo asociado a la multiplicación de lo que cuesta ir de un punto a otro por la cantidad total de flujo entre ambos puntos, o en otras palabras, el flujo por el costo de tránsito.

Modelo Matemático

$MinZ={1 \over 2}\sum _{i=1}^{n}\sum _{j=1,j\neq i}^{n}\sum _{h=1}^{n}\sum _{k=1,k\neq h}^{n}C_{ihjk}X_{ih}X_{jk}$

Sujeto a :

$\sum _{i=1}^{n}X_{ih}=1\forall h$

$\sum _{h=1}^{n}X_{ih}=1\forall i$

$X_{ih}\in \lbrace 0,1\rbrace$

$C_{ijhk}=a_{ij}f_{ij}d_{hk}$

Donde :

$\lbrace c_{ijhk}\rbrace =a_{ij}f_{ij}d_{hk}$ = Costo de asignar los departamentos i y j a los sitios h y k , respectivamente .

$f_{ij}$ = Flujo entre departamentos i y j.

$d_{hk}$ = Distancian entre sitios h y k.

$a_{ij}$ = Costo de mover una unidad de distancia entre los departamentos i y j.

$X_{ij}=\left\{{\begin{array}{l l}1&{\mbox{Si el departamento }}i{\mbox{ es asignado a la locacion }}j.\\0&{\mbox{Si no}}\\\end{array}}\right.$

Este Modelo matemático cuenta con un Espacio de Búsqueda igual a $2^{n^{2}}$.

Aplicaciones para el Problema de la Asignación Cuadrática

En los siguientes ejemplos de aplicaciones se puede observar que resolver este problema para un gran número de instancias es de vital importancia, y a la vez que tratar de resolver el problema mediante técnicas completas puede resultar infactible por el alto número de instancias.

• Diseño de centros comerciales donde se quiere que el público recorra la menor cantidad de distancia para llegar a tiendas de intereses comunes para un sector del público.
• Diseño de terminales en aeropuertos, en donde se quiere que los pasajeros que deban hacer un transbordo recorran la distancia mínima entre una y otra terminal teniendo en cuenta el flujo de personas entre ellas.
• Procesos de comunicaciones.
• Diseño de teclados de computadora, en donde se quiere por ejemplo ubicar las teclas de una forma tal en que el desplazamientos de los dedos para escribir textos regulares sea el mínimo.
• Diseño de circuitos eléctricos, en donde es de relevante importancia dónde se ubican ciertas partes o chips con el fin de minimizar la distancia entre ellos, ya que las conexiones son de alto costo.

Enlaces externos

• QAPlib últimas noticias referentes al problema de la asignación cuadrática, más instancias y soluciones para QAP.

• Datos: Q7268356