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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Постановка проблеми[ред.ред. код]

Квадратична задача про призначення вперше була сформульована Копмансом та Бекманом у 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}. Кожен випадок ap(i)p(j)bi j – це ціна, яку коштує призначення об’єкту р(і) на місце і та об’єкту р(j) на місце j. Якщо хоча б одна з коефіціентних матриць A та B є симетричною, тоді і задача є симетричною. У противному випадку задача є асиметричною. Деякі автори пропонують розширений варіант задачі. Крім двох матриць коефіцієнтів A та B задається ще третя матриця C = (cij), де cij – це вартість розміщення об’єкту (і) на місце (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}

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

Розрахункова складність[ред.ред. код]

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

Практичне застосування[ред.ред. код]

За допомогою квадратичної задачі про призначення може бути вирішено безліч різноманітних проблем. Наприклад, вона знайшла застосування у вирішенні проблеми розташування будівель у роботі Дікі і Хопкінса у 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.

Генетичні алгоритми[ред.ред. код]

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

Література[ред.ред. код]

  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.