b'\n_START_ARTICLE_\nProblema de la asignaci\xc3\xb3n cuadr\xc3\xa1tica\n_START_SECTION_\nOrigen\n_START_PARAGRAPH_\nEl problema de la asignaci\xc3\xb3n cuadr\xc3\xa1tica, que se denota por sus siglas en ingl\xc3\xa9s QAP (Quadratic assignment problem), fue planteado por Koopmans y Beckmann en 1957 como un modelo matem\xc3\xa1tico para un conjunto de actividades econ\xc3\xb3micas 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\xc3\xbamero de situaciones, lo hacen un problema de gran inter\xc3\xa9s para el estudio.\n_START_SECTION_\nDefinici\xc3\xb3n\n_START_PARAGRAPH_\nQAP es un problema est\xc3\xa1ndar en la teor\xc3\xada de locaci\xc3\xb3n. En \xc3\xa9ste 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\xc3\xa1 de las distancias y flujo entre las instalaciones, adem\xc3\xa1s de un costo adicional por instalar cierta instalaci\xc3\xb3n en cierta locaci\xc3\xb3n espec\xc3\xadfica. De este modo se buscar\xc3\xa1 que este costo, en funci\xc3\xb3n de la distancia y flujo, sea m\xc3\xadnimo._NEWLINE__NEWLINE_La versi\xc3\xb3n de Koopmans y Beckmann ten\xc3\xada como entrada tres matrices  , ,  del tipo real donde  especifica el flujo entre las instalaciones i y j,  especifica la distancia entre las instalaciones k y l y  el costo de instalar la instalaci\xc3\xb3n i en la locaci\xc3\xb3n k. Por tanto este problema lo podemos modelar de la siguiente forma:_NEWLINE_Sea n el n\xc3\xbamero de instalaciones y locaciones. A su vez denotemos por N a el arreglo  ._NEWLINE_Donde  es el conjunto de todas las permutaciones  y donde cada producto de la sumatoria doble corresponde al costo asociado a la multiplicaci\xc3\xb3n 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\xc3\xa1nsito.\n_START_SECTION_\nModelo Matem\xc3\xa1tico\n_START_PARAGRAPH_\nSujeto a\xc2\xa0:_NEWLINE_ _NEWLINE_ _NEWLINE_Donde\xc2\xa0:_NEWLINE_ = Costo de asignar los departamentos i y j a los sitios h y k , respectivamente ._NEWLINE_ = Flujo entre departamentos i y j._NEWLINE_ = Distancian entre sitios h y k._NEWLINE_ = Costo de mover una unidad de distancia entre los departamentos i y j._NEWLINE__NEWLINE_Este Modelo matem\xc3\xa1tico cuenta con un Espacio de B\xc3\xbasqueda igual a .'