Квадратична задача про призначення

Квадратична задача про призначення вперше була сформульована Копмансом та Бекманом у 1957 р. як математична модель для ефективного розміщення взаємозв’язаних об’єктів і по сьогодні залишається однією з найбільш складних задач комбінаторної оптимізації. Задача моделює наступну проблему з реального життя: дано множину з N об'єктів та множину з N місцеположень. Для кожної пари місцеположень задана відстань і для кожної пари об’єктів задана вага або потік між ними (наприклад, кількість поставок, що транспортуються між двома об’єктами). Задача полягає в розташуванні всіх об’єктів у різних місцеположеннях з метою мінімізації суми відстаней, помножених на відповідні потоки.

Формальна постановка задачі наступна: дано дві множини – P (об’єкти) та L (місцеположення) однакового розміру, на яких визначена функція ваги (потік) w : P × P → R та функція відстані d : L × L → R. Необхідно знайти таке відображення f : P → F (призначення), що мінімізує цільову функцію ціни:

${\displaystyle \sum _{a,b\in P=1}w\left(a,b\right)*d\left(f\left(a\right),f\left(b\right)\right)}$

Зазвичай, функції ваги та відстані зображаються у вигляді матриць формату N x N. Матриця потоку має вигляд ${\displaystyle A=a_{ij}}$, матриця відстаней має вигляд ${\displaystyle B=b_{kl}}$. Функція квадратичної задачі про призначення виглядатаме наступним чином:

${\displaystyle min\sum _{i=1}^{n}\sum _{i=1}^{n}a_{\pi \left(i\right)\pi \left(j\right)}b_{i,j}}$

де Sn – це набір перестановок на проміжку {1, 2, . . . , n}. Кожен випадок ap(i)p(j)bi j – це ціна, яку коштує призначення об’єкту р(і) на місце і та об’єкту р(j) на місце j. Якщо хоча б одна з коефіціентних матриць A та B є симетричною, тоді і задача є симетричною. У противному випадку задача є асиметричною. Деякі автори пропонують розширений варіант задачі. Крім двох матриць коефіцієнтів A та B задається ще третя матриця C = (cij), де cij – це вартість розміщення об’єкту (і) на місце (j). Тоді задача матиме вигляд: ${\displaystyle min\sum _{i=1}^{n}\sum _{i=1}^{n}a_{\pi \left(i\right)\pi \left(j\right)}b_{i,j}+\sum _{i=1}^{n}a_{\pi \left(i\right)i}}$

Ця функція називається узагальненим формулюванням квадратичної задачі про призначення. У випадку, коли cij = 0 для всіх 1<=i, j<=n, функція являє собою спрощений варіант задачі, розглянутий вище. Задача комівояжера може розглядатись як частковий випадок квадратичної задачі про призначення, якщо припустити, що потік зв’язує усі об’єкти послідовно по кільцю і всі потоки мають однакове ненульове значення.

На противагу лінійним задачам про призначення квадратична задача є набагато складнішим випадком комбінаторної оптимізації. Задача є NP-складною. Наразі не існує точного алгоритму розв’язання задач розмірності N > 30 і навіть при невеликій кількості об’єктів розрахунок може зайняти досить тривалий час. Алгоритмічна складність задачі становить ${\displaystyle N^{2}N}$.

За допомогою квадратичної задачі про призначення може бути вирішено безліч різноманітних проблем. Наприклад, вона знайшла застосування у вирішенні проблеми розташування будівель у роботі Дікі і Хопкінса у 1972 році (модель планування університетського кампусу). Завдання полягало у плануванні розміщення n будівель на території кампусу, де ${\displaystyle b_{kl}}$ - це відстань від місця розміщення k до місця розміщення l, а ${\displaystyle a_{ij}}$ - інтенсивність руху між будівлями і та j. Мета оптимізації розміщення полягала в тому, щоб мінімізувати загальну тижневу відстань, що долають студенти та викладачі, переходячи між будівлями. Крім задач з розміщення будівель даний метод також може бути використаний при розміщенні окремих компонентів на схемі (при проектуванні мікросхем, компонуванні дротів у електричному щиті тощо), складанні розкладу для уникнення «вікон», плануванні зв’язків при паралельному виконання кількох взаємозв’язаних видів діяльності. У 1977 році Беркард і Оферман продемонстрували, що квадратична задача про призначення може бути використана для ергономічного розміщення клавіш на друкарській машинці. Завдання полягало в тому, щоб розмістити клавіші таким чином, щоб час написання тексту був мінімальним. При вирішенні проблеми кожному з символів, розміщення яких мало бути впорядкованим на клавіатурі, було надано порядковий номер N = {1, 2,. . . , n}. Таким чином ${\displaystyle a_{ij}}$ відображало частоту появи пари символів і та j. Значення з матриці відстаней ${\displaystyle b_{kl}}$ показувало час, що необхідний щоб натиснути клавішу в позиції k після того, як було натиснуто клавішу в позиції l. Схоже застосування в галузі ергономічного розміщення було використано при створенні контрольної панелі, щоб мінімізувати втому очей оператора. Було запропоновано навіть використання квадратичної задачі про призначення у спорті для визначення порядку розміщення членів команди у естафеті, та на виробництві, для планування паралельних взаємопов’язаних виробничих процесів.

Відомі методи розв'язання поділяють на дві групи, що можна комбінувати. Точні методи знаходять, маючи достатньо часу, гарантовано оптимальний шлях. Евристичні методи знаходять, часто за коротший час, гарні розв'язки, що, в загальному випадку, можуть бути гіршими за оптимальні.

• Задача про призначення
• Узагальнена задача про призначення
• Задача про призначення найменшого числа виконавців

1. The Quadratic Assignment Problem : Theory and Algorithms / E. Çela // Combinatorial Optimization. — 1998. —Vol. 1. — 304 p.
2. Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.5: ND43, pg.218.