АННОТАЦИЯ 5
ВВЕДЕНИЕ 8
1 Постановка задачи о P-медиане и обзор алгоритмов решения задач
оптимального размещения 10
1.1 Постановка задачи 10
1.1.1 Исследуемая задача 10
1.1.2 Формулировка задачи 11
1.1.3 Описание практического применения исследуемой задачи .. 12
1.1.4 Пример задачи 12
1.2 Обзор алгоритмов дискретной оптимизации 14
1.2.1 Точные методы 14
1.2.2 Приближенные методы 18
Выводы по главе один 27
2 Алгоритм муравьиной колонии в задаче для P-медианы 28
2.1 Формальное описание алгоритма 28
2.1.1 Элитарная муравьиная система 30
2.1.2 MMAS (Max-Min муравьиная система) 30
2.1.3 Ранговая муравьиная система (ASrank) 31
2.1.4 Длительная ортогональная колония муравьёв (COAC) 31
2.2 Описание конкретного алгоритма для исследуемой задачи 31
2.3 Описание исследования и настройки алгоритма 34
Выводы по главе два 35
3 Алгоритм имитации отжига для задачи о P-медиане 36
3.1 Формальное описание алгоритма 36
3.3 Исследование и настройка алгоритма имитации отжига 38
Выводы по главе три 41
4. Вычислительный эксперимент 42
Выводы по четвертой главе 43
Заключение 47
Библиографический список 48
Приложения 51
Приложение А 52
А1.Код алгоритма муравьиной колонии 52
А2.Алгоритм имитации отжига 59
А3.Алгоритм-тестировщик 63
Приложение Б 64
Многие современные проблемы, связанные с планированием и размещением бизнеса, хорошо описываются и решаются с помощью математических оптимизационных моделей.
Одними из самых важных задача в рассматриваемой области являются задачи оптимального размещения объектов. Такие задачи необходимо решать при проектировании сетей снабжения торговых предприятий, градостроительстве, проектировании микросхем.
Возникновение задач размещения и их первые попытки решения приписывают французским и итальянским математикам 17 века и, в частности, Пьеру Ферма (1601—1665). Он интересовался следующей задачей. Заданы три точки на плоскости. Найти такую четвертую точку, что сумма расстояний от неё до трех заданных точек была бы минимальной. Решением этой задачи занимался ученик Галилея, итальянский математик Евангелиста Торричелли (1608—1647). Считается, что первым, кто сформулировал и решил эту задачу был итальянский математик Батисто Ковальери (1598—1647), но точное первенство установить проблематично. В начале двадцатого века (1909) Альфред Вебер исследовал более общую задачу о нахождении центра тяжести для трех взвешенных точек, а позже (1941) Курант и Роббинс популяризировали так называемую задачу Штейнера (1796—1863) о нахождении кратчайшей остовной сети для трёх точек на плоскости. Бурное развитие задачи размещения получили с появлением вычислительной техники. Различные модели создавались при проектировании размещения газовых, нефтяных станций, что внесло вклад в развития статистических и динамических моделей размещения. Одними из первых ученых кто рассматривал задачи размещения были. Дементьев В.Т [1], Гимадутдинов Э.Х [2], Берсенев Г.Б [3] из зарубежных авторов можно выделить Mirchandani и Francis [4], которые провели широкий анализ различных постановок задач. Так же оптимизационными алгоритмами занимались, В.П.Черенин [5] - Метод последовательных расчетов. Land A.H., and Doig A.G. впервые использовали метод ветвей и границ [6]. Так же одним из первых вариантов адаптации метода ветвей и границ к простейшей задачи размещения был сделан Ефромсоном М.А. и Реем Т.Л. [7]. Так же методом ветвей и границ занимались Береснев В.Л. [8], Erlenkotter D [9], Bilde O. and Krarup J. [10]. Первым исследованием Лагранжевых релаксаций занимался Everett H. [11], позднее их исследованиями занимались Held M., Karp R.M.[12], Fisher M.L.[13], Northup W.D, Shapiro J.F. [14].
Объектом исследования задача о P-медиане.
Предметом исследования методы решения задачи о P-медиане.
Целью работы является разработка и анализ эвристических алгоритмов для решения задачи о P-медиане.
Для достижения цели поставлены следующие задачи:
1) реализовать эвристические алгоритмы, для решения задачи о P-медиане;
2) выполнить анализ и точную настройку эвристических алгоритмов;
3) произвести вычислительный эксперимент;
4) на основании вычислительного эксперимента сделать вывод о допустимости или недопустимости использования эвристик при решении задач о P-медиане.
В ходе дипломной работы были реализованы алгоритмы муравьиной колонии и имитации отжига. Алгоритмы были проанализированы и настроены таким образом, что бы получать оптимальные решения за приемлемое время.
Было проведено сравнение работы алгоритмов и точного метода ветвей и границ, в результате было выявлено, что эвристические алгоритмы обладают достаточно высокой точностью. И их использование для решения задач о P-медиане допустимо. Так же данные позволяют сделать вывод, что для матриц размерностями меньше 50x50 алгоритмы позволяют получить точное решение. А на больших матрицах, только приближенное с маленьким значением ошибки. Эвристические алгоритмы, в отличии от точных. Позволяют самостоятельно определять баланс точности и времени вычисления.
Применение эвристических алгоритмов в решении задач о P-медиане оправданно. Хотя алгоритмы и не всегда получают оптимальные решения. Полученные значения, позволяют утверждать, что в сферах где значение ошибки 2-3% не являются значимыми, эвристические алгоритмы дадут существенный выигрыш во времени выполнения.
