Алгоритмы локального поиска для задачи о ρ-медиане с предпочтениями клиентов

• Автор: Алексеева, Екатерина Вячеславовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Новосибирск
• Количество страниц: 92 с. : ил.

Глава 1. Задача о р-медиане с предпочтениями клиентов

1.1. Постановка задачи и её свойства

1.2. Задача МПК в условиях неоднозначности выбора клиентов

1.3. Алгоритм локального спуска и правила замещения

1.4. Экспериментальные исследования

1.4.1. Влияние правил замещения на качество локальных оптимумов и число итераций алгоритма

1.4.2. Исследование расположения локальных оптимумов

1.4.3. Сравнительный анализ с классической задачей о р-медиане

Глава 2. Локальные оптимумы и их свойства

2.1. Сложность задачи локального поиска

2.2. Временная сложность алгоритма локального поиска

2.3. Вычислительная сложность алгоритма локального поиска
в среднем случае
2.4. Погрешность локальных оптимумов
2.5. Локально седловые точки
Глава 3. Генетические алгоритмы
3.1. Нижние оценки оптимального решения
3.1.1. Сведения к задачам ЦЛП
3.1.2. Сведение к задаче с парой матриц
3.1.3. Новое сведение к задаче с парой матриц
3.2. Процедура Резенде и Вернека
3.3. Генетические алгоритмы
3.3.1. Общая схема алгоритма

3.3.2. Генетический локальный поиск для задачи МПК
3.3.3. Экспериментальные исследования
3.3.4. Выбор параметров алгоритма
3.3.5. Сравнение нижних оценок
Глава 4. Задача выбора оптимального парка
сельскохозяйственных машин
4.1. Постановка задачи на содержательном уровне
4.2. Предпочтения клиентов
4.3. Математическая постановка задачи
4.4. Сведение к задаче МПК
4.5. Структура системы поддержки принятия решений
4.5.1 Подготовка исходных данных
4.5.2 Блок оптимизации
4.5.3 Анализ полученных результатов и формирование отчётов
Заключение
Список литературы
Теория дискретных задач размещения является одной из интенсивно развивающихся областей в исследовании операций. Возникновение этих задач и первые попытки их решения приписывают французским и итальянским математикам 17 века и, в частности, Пьеру Ферма (1601-1665). Он интересовался следующей задачей. Заданы три точки на плоскости. Найти такую четвертую точку, что сумма расстояний от неё до трех заданных точек была бы минимальной. Решением этой задачи занимался ученик Галилея, итальянский математик Евангелиста Торричелли (1608-1647). Возможно, что первым, кто сформулировал и решил эту задачу был итальянский математик Батисто Ковальери (1598-1647), однако точное первенство установить уже очень трудно. В начале двадцатого века (1909) Альфред Вебер исследовал более общую задачу о нахождении центра тяжести для трех взвешенных точек, а позже (1941) Курант и Роббинс популяризировали так называемую задачу Штейнера (1796-1863) о нахождении кратчайшей остовной сети для трёх точек на плоскости.
По-настоящему бурное развитие модели размещения получили с рождением вычислительной техники. Линейные модели, модели частично-целочисленного программирования, статистические и динамические модели размещения, а также модели с нелинейными целевыми функциями рождались из приложений по размещению нефтяных и газовых станций, размещению предприятий, станций метро, милицейских и пожарных участков и др. В СССР первые модели размещения предприятий исследовались В.П. Черениным и В.Р. Хачатуровым [19]. Интерес к этим моделям в Институте математике им. С.Л. Соболева СО РАН связан в первую очередь с приложениями в области стандартизации и унификации [1,17, 18]. Работы
В.Л. Береснева, Э.Х. Гимади, В.Т. Дементьева, Н.И. Глебова, а позже А.И. Давыдова, Ю.А. Кочетова, A.B. Плясунова, Ю.В. Шамардина, Л.Е. Горба-

3.1.2 Сведёние к задаче с парой матриц
Рассмотрим матрицы А = (йу),г 6 ; 6 ^ и В = (%),* € 1,3 £ Л» У
которых число строк совпадает, а число столбцов может быть различным. Задача с парой матриц (ПМ) заключается в том, чтобы найти непустое подмножество строк 5 С / на котором достигается минимум следующей целевой функции [1]:
Заметим, что если J^ = I, а,-у = аг- при г = и щу = 0, в противном случае, то получаем простейшую задачу размещения [54]. Таким образом, задача с парой матриц является ИР-трудной в сильном смысле.
Известно [8], что для задачи (1.1)—(1.7) можно построить сведёние к задаче ПМ с дополнительным ограничением |5| = р. Для построения сведения представим матрицу (с^) в виде суммы двух матриц сг-у = + Ьц, г €
I, j € <7, где
при всех 3 € J.
Тогда, задача (1.1)—(1.7) может быть записана в следующем виде: найти
Для получения нижней оценки эту задачу можно переписать в виде задачи ЦЛП и вычислить оптимум в линейной релаксации. Однако, представление в терминах ЦЛП может оказаться неединственным. Как мы уже

% = °’ Чі = Xтіп{°;%!з -%}’к = 2’---’т’Э Є I (3-12)

Ні = %’ Ні = % + Xтах^0; %гі ~ ^ = 2 т,у Є Т, (3.13)
перестановка (г{,... ,і3т)л Є J соответствует (3.1). Очевидно, что
Ь-] .<&;.<•■•< 6-і •
И 9 — го? — — г
К 7 . иі •