Библиотека тестовых задач Простейшая задача размещения

Главная страница библиотеки Простейшая задача размещения Демонстрационная версия

Оптимизационные алгоритмы

Одним из первых точных алгоритмов решения данной задачи является Метод последовательных расчетов, предложенный В.П. Черениным в 1962 [1]. Он основан на свойстве супермодулярности целевой функции

F(S₁) + F(S₂) £ F(S₁ È  S₂) + F(S₁ Ç  S₂),  S₁, S₂ Í I,

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

На сегодняшний день наиболее мощным точным методом решения данной задачи является Метод ветвей и границ. Первый вариант адаптации этого метода  к простейшей задачи размещения был сделан Ефромсоном М.А. и Реем Т.Л. в 1966 [2]. Авторы использовали примитивную нижнюю оценку целевой функции н а подмножествах частичных решений, что в последствии было исправлено независимо в работах [3-6]. Эффективность этого метода особенно высока на задачах, в которых матрица {g_ij} удовлетворяет неравенству треугольника

g_ij + g_jk ³ g_ik ,      i, j, k Î I,      I = J .

Это условие часто выполняется в реальных задачах размещения, но, как правило, не выполняется в задачах унификации и стандартизации.

Продуктивность метода Лагранжевых релаксаций основана на том, что в задачах дискретной оптимизации и, в частности, в данной задаче “зазор” между целочисленным решением и решением соответствующей задачи линейного программирования часто очень мал или вовсе отсутствует. Этот “зазор” принято называть разрывом двойственности. Он является своеобразным мерилом сложности задачи. Первые Лагранжевы эвристики были исследованы в работах Лебедева С.С., Ковалевской М.И. и Джеоффриона А.М., МакБрайда Р. [7, 8]. По своим свойствам этот подход занимает промежуточное положение между точными и приближенными методами, так как при отсутствии разрыва двойственности он позволяет не только найти, но и доказать оптимальность полученного решения.

Среди приближенных методов наибольшую эффективность демонстрируют вероятностные метаэвристики: Поиск с запретами, Имитация отжига и Генетический алгоритм. По сути, эти алгоритмы являются разной реализацией одной и той же идеи: организации стохастического Марковского процесса на подходящем множестве состояний [9]. Каждый из этих алгоритмов устроен таким образом, чтобы соответствующая ему цепь Маркова была конечной, неразложимой и непериодической [10], что гарантирует в асимптотике получение оптимального решения задачи. Несомненным достоинством метаэвристик является получение “хороших” приближенных решений уже на первых итерациях и высокая вероятность получения точного решения за достаточно большое число итераций.

Эффективность указанных методов можно проверить с помощью разработанного программного обеспечения, демонстрационная версия которого может использоваться при подготовки университетских курсов Дискретная математики, Комбинаторная оптимизация и Исследование операций.

 Литература

1. Черенин В.П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов. 1962. М. (Лаб. эконом. мат. методов АН СССР).

2. Efroymson M.A., and Ray T.L. A Branch and Baund Algorithm for Plant Location. Operations Research. v14 (1966), pp 361-368.

3. Erlenkotter D. A Dual-Based Procedure for Uncapacitated Facility Location. Operations Research. v26 (1978), pp 992-1009.

4. Береснев В.Л. Алгоритм неявного перебора для задачи типа размещения и стандартизации. Управляемые системы. Вып.12 (1974). Новосибирск, Институт математики Сиб.отд. АН СССР, с. 24-34.

5. Bilde O., and Krarup J. Sharp Lower Bounds and Efficient Algorithm for the Simple Plant Location Problem. Annals of Discrete Mathematics. v1 (1977), pp 79-99.

6. Трубин В.А. О некоторых задачах типа размещения. Применение математических методов в экономических исследованиях и планировании. Киев: ИК АН УССР. Вып.1 (1969), с. 3-15.

7. Лебедев С.С., Ковалевская М.И. Множители Лагранжа в простейшей задаче размещения. Исследования по дискретной оптимизации. М. Наука, 1976, с. 170-180.

8. Geoffrion A.M., and McBride R. Lagrangian Relaxation Applied to Facility Location Problems. AIIE Transactions. v10 (1978), pp 40-48.

9. Aarts E., and Lenstra J.K. (eds) Local Search in Combinatorial Optimization, John Wiley & Sons, 1997.

10. Боровков А.А. Теория вероятностей: Учебное пособие для Вузов.- 2-е изд. перераб. и доп.  М. Наука. Гл. ред. физ.-мат. лит. 1986.

Главная страница библиотеки Простейшая задача размещения Демонстрационная версия