Економічна інтерпретаціязадачі про призначення

Задача про призначення є однією з базових задач комбінаторної оптимізації в галузі оптимізації або дослідження операцій в математиці. Вона полягає в знаходженні парування мінімальної (або максимальної) ваги між елементами двох скінчених множин. Вона може бути подана як знаходження парування у зваженому дводольному графі.

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

Уперше задача про призначення булла розглянута в геометричній формі Гаспаром Монжем у 1784 році. Проте на початку ХХ століття булла встановлена некоректність розв’язку Монжа. Наступні кроки в розв’язанні задачі про призначення зроблені Кенігом і Егерварі в першій третині XX століття. Кеніг і Егерварі розглядали цю задачу як задачу пошуку досконалого паросполучення мінімальної ваги у зваженому дводольному графі. Їх роботи стали основою для угорського методу, розробленого Куном у 50-х роках минулого століття. У 1947 році Данциг запропонував симплекс-метод для розв’язання загальної задачі лінійного програмування, до якої легко зводиться задача про призначення. Задача про призначення, поставлена Данцигом і Фалкерсоном, може також розглядатися як задача про максимальний потік мінімальної вартості. У 1961 році Басакер і Гоуен опублікували алгоритм для її розв’язання. Цей алгоритм для загальної задачі, як і алгоритм симплекс-методу, має експоненціальну складність, а для задачі про призначення? поліноміальну. Поліноміальний алгоритм для задачі про максимальний потік мінімальної вартості, заснований на алгоритмі Клейна, що був опублікований у 1967 році, вперше запропонований у 1987 році Гольбергом і Тар’яном[10].

У таблиці 1.1 представлені можливі варіанти практичного застосування задачі про призначення.

Таблиця 1.1