Многостадийная задача размещения

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

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

Исторически первым методом решения многостадийной задачи размещения был метод ветвей и границ [1], который строился по аналогии с методом для простейшей задачи размещения. Идеи тупиковых матриц были развиты на случай более общей постановки задачи и позволили получать нижние оценки существенно более точные, чем примитивные оценки линейного программирования [2]. Решающим обстоятельством в данном случае явился удачный выбор записи ограничений задачи. Так называемые сильные и слабые формулировки задачи давали одно и тоже целочисленное решение, но разные линейные релаксации [3]. Совершенствование этих идей привело в конечном итоге к работоспособной версии точного алгоритма [4, 5], позволяющей решать задачи средней размерности J100,  I50, L100.

Лагранжевы релаксации для данной задачи рассматривались в работах [3, 6], причем в  [6] математическая модель была более подробной и содержала ограничения на объемы производства. Сравнение различных релаксаций позволило выявить преимущества каждой из них и разработать быстрые приближенные алгоритмы с апостериорной оценкой точности.

Вероятностные жадные алгоритмы рассматривались в работах [7, 8]. Приведено описание двух схем, построенных на идеях координатного спуска. С помощью численных экспериментов было показано, что вероятностные жадные алгоритмы позволяют получать приближенные решения с меньшей погрешностью чем их детерминированные аналоги. Особенно эффективны такие алгоритмы в схеме ветвей и границ, где они заметно сокращают время нахождения оптимума.

Из алгоритмов локального поиска на сегодняшний день исследовался только алгоритм поиска с запретами [9]. Он показал высокую работоспособность и, по-видимому, является наиболее мощным средством решения данной задачи. Поведение этого алгоритма наводит на мысль, что локальные оптимумы и решения с небольшой погрешностью распределены неравномерно по допустимой области. Они концентрируются в каком-то одном месте, получившем название большой долины [10]. Эта гипотеза объясняет высокую эффективность алгоритмов локального поиска и дает стимул для новых предположений и исследований.

Литература

1. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск. Наука, 1978.

2. Гимади Э.Х., Глебов Н.И., Дементьев В.Т. Об одном методе построения нижней оценки и приближенного решения с апостериорной оценкой точности для задачи стандартизации. Управляемые системы. Вып.13 (1974), с. 26-31.

3. Barros A.I., Labbe M. A general model for the uncapacitated facility and depot location problem. Location Science. v2 (1994), N4, c. 173-191.

4. Гончаров Е.Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий. Дискретный анализ и исследование операций. Сер.2, т5 (1998), №1, с.19-39.

5. Береснев В.Л., Гончаров Е.Н. Приближенный алгоритм для задачи минимизации полиномов от булевых переменных. Дискретный анализ и исследование операций. Сер.2, т5 (1998), №2, с.3-19.

6. Кочетов Ю.А., Пащенко М.Г. Нижние границы в задаче выбора состава
   двухуровневой системы технических средств. Дискретный анализ и
   исследование операций. Сер.2,  т2 (1995), № 4, с.32-41.

7. Гончаров Е.Н., Кочетов Ю.А.  Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1 (1998), Иркутск, с. 121-124.

8. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер.2, т6 (1999), №1, с.12-32. 

9. E.Goncharov and Yu.Kochetov. Probabilistic Tabu Search Algorithm for the Multi-Stage Uncapacitated Facility Location Problem. Operations Research Proceedings 2000, Springer. (to appear).

10. Кочетов Ю.А. Алгоритмы локального поиска для задач дискретной оптимизации (принято к печати)

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