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

Квадратична задача про призначення — одна з фундаментальних задач комбінаторної оптимізації в галузі оптимізації і дослідження операцій, що належить до категорії задач про розміщення об'єктів.

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

Постановка задачі

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

Інтуїтивно зрозуміло, що підприємства з більшим потоком слід розміщувати ближче одне до одного.

Формулювання задачі схоже на формулювання задачі про призначення, відрізняються вони цільовою функцією — в квадратичній задачі вона квадратична, що й відбито в назві.

Математичне подання

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

$\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. Матриця потоків має вигляд $A=a_{ij}$, матриця відстаней має вигляд $B=b_{kl}$. Функція квадратичної задачі про призначення матиме такий вигляд:

$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}. Кожен випадок $a_{\pi \left(i\right)\pi \left(j\right)}b_{i,j}$ — це ціна призначення об'єкту р(і) на місце і та об'єкту р(j) на місце j. Якщо хоча б одна з коефіціентних матриць A та B є симетричною, то й задача є симетричною. В іншому випадку задача є асиметричною.

Деякі автори пропонують розширений варіант задачі. Крім двох матриць коефіцієнтів A та B задається ще третя матриця $C=(c_{ij})$, де $c_{ij}$ — це вартість розміщення об'єкта (і) на місце (j). Тоді задача матиме вигляд: $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}$

Ця функція називається узагальненим формулюванням квадратичної задачі про призначення. У випадку, коли $c_{ij}=0$ для всіх $1\leq i,j\leq n$, функція являє собою спрощений варіант задачі, розглянутий вище.

Задачу комівояжера можна розглядати як частковий випадок квадратичної задачі про призначення, якщо припустити, що потік зв'язує всі об'єкти послідовно по кільцю і всі потоки мають однакове ненульове значення.

Обчислювальна складність

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

Практичне застосування

За допомогою квадратичної задачі про призначення можна розв'язати безліч різноманітних задач. Наприклад, вона знайшла застосування у розв'язанні задачі розташування будівель у роботі Дікі і Гопкінса 1972 року (модель планування університетського кампусу). Завдання полягало у плануванні розміщення n будівель на території кампусу, де $b_{kl}$ — це відстань від місця розташування k до місця розташування l, а $a_{ij}$ — інтенсивність руху між будівлями і та j. Мета оптимізації розміщення полягала в тому, щоб мінімізувати загальну тижневу відстань, яку долають студенти та викладачі, переходячи між будівлями.

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

Методи розв'язування

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

Точні методи

Існує три точних методи, які можна використати для знаходження оптимального розв'язку квадратичної задачі про призначення: динамічне програмування, алгоритм Гоморі та метод гілок і меж. Дослідження показують, що останній є найбільш підхожим для розв'язання поставленої задачі. Втім, через високу складність квадратичних задач про призначення, більшість задач з N > 30 майже не піддаються обчисленню точними методами.

Метод гілок та меж

Оскільки метод гілок та меж вважають найкращим з точних методів для обчислення цієї задачі, слід зупинитись на ньому детальніше.

При застосуванні методу гілок і меж спочатку використовують один з евристичних методів для знаходження приблизного, але підхожого розв'язку. Назвемо його початковим значенням. Потім, на кожній з вершин (початок гілкування) дерева знаходять «межу», тобто найкраще можливе значення, яке можна очікувати від подальшого обчислення цієї секції гілок. До методів визначення «межі» ставиться вимога, щоб вони були не надто обчислювально складними, могли бути переобчислені для піднаборів даних після кількох етапів гілкування і були достатньо точними. Ефективного методу відшукання межі не знайдено донині. Нині найкращим методом відшукання «нижньої межі» є метод Гілмора — Лоулера. Метод лінійного програмування також дає дуже точне значення, але через високу складність і довгий час обчислень не може вважатись ефективним за великого розміру задачі. Значення «межі» порівнюється з отриманим початковим значенням. Якщо початкове значення краще за «межу», тобто краще за можливе очікуване значення в цій секції дерева, можна закінчити гілкування цієї секції і відкинути її. У іншому випадку необхідно шукати нове покращене початкове значення і за допомогою послідовних ітерацій знайти оптимальне. Коли отримане покращене значення дорівнює попередньому, вважається, що знайдений розв'язок є оптимальним.

Евристичні методи

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

Локальний пошук

Локальний пошук починається із задання початкової схеми призначень і полягає в поступовому її покращенні шляхом локальних змін. Якщо по сусідству з поточним призначенням знайдено краще призначення, він замінює поточне призначення і пошук продовжується. При розв'язуванні квадратичної задачі про призначення множина сусідніх призначень складається з можливих варіантів, які можна отримати перестановкою двох об'єктів. Цей метод належить до найпростіших методів ітеративної евристики 2-opt.

Метод симуляції відпалювання

Метод симуляції відпалювання належить до метаевристичних методів і був одним з перших, застосованих до розв'язання квадратичної задачі про призначення. Нині найточнішим алгоритмом є алгоритм, запропонований Коноллі 1990 року. 1994 року Тонеман і Бьольт запропонували дещо покращений алгоритм симуляції відпалювання для квадратичної задачі про призначення.

Табуйований пошук

Найвідомішим табуйованим пошуком розв'язку квадратичної задачі про призначення є алгоритм Таярда (1991 рік). Цей алгоритм базується на 2-opt методі локального пошуку. Табуювальним атрибутом у цьому випадку виступає неможливість призначення певних елементів на певні позиції. Так, табуювальний атрибут t(i, j) означає, що неможливо призначити об'єкт і на місце j.

Генетичні алгоритми

Генетичні алгоритми отримали свою назву від інтуїтивного пояснення принципу їх дії на основі теорії природного добору Дарвіна. На початку їх виконання виробляється набір розв'язків із призначення певних об'єктів на певні місця з подальшою їх заміною кращими на основі критерію ефективності, яким зазвичай виступає значення цільової функції. Нині генетичний алгоритм Дрезнера з включеним у нього табуйованого пошуку є одним з найкращих евристичних методів розв'язування квадратичної задачі про призначення.

Див. також

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

Література

• The Quadratic Assignment Problem: Theory and Algorithms / E. Çela // Combinatorial Optimization. — 1998. —Vol. 1. — 304 p.
• 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.