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

Теория дискретных задач размещения является одной из интенсивно развивающихся областей в исследовании операций. Возникновение этих задач и первые попытки их решения приписывают французским и итальянским математикам 17 века и, в частности, Пьеру Ферма (1601−1665). Он интересовался следующей задачей. Заданы три точки на плоскости. Найти такую четвертую точку, что сумма расстояний от неё до трех заданных точек была бы минимальной. Решением этой задачи занимался ученик Галилея, итальянский математик Евангелиста Торричелли (1608−1647). Возможно, что первым, кто сформулировал и решил эту задачу был итальянский математик Батисто Ковальери (1598−1647), однако точное первенство установить уже очень трудно. В начале двадцатого века (1909) Альфред Вебер исследовал более общую задачу о нахождении центра тяжести для трех взвешенных точек, а позже (1941) Курант и Роббинс популяризировали так называемую задачу Штейнера (1796−1863) о нахождении кратчайшей остовной сети для трёх точек на плоскости.

По-настоящему бурное развитие модели размещения получили с рождением вычислительной техники. Линейные модели, модели частично-целочисленного программирования, статистические и динамические модели размещения, а также модели с нелинейными целевыми функциями рождались из приложений по размещению нефтяных и газовых станций, размещению предприятий, станций метро, милицейских и пожарных участков и др. В СССР первые модели размещения предприятий исследовались В. П. Черениным и В. Р. Хачатуровым [19]. Интерес к этим моделям в Институте математике им. C.JI. Соболева СО РАН связан в первую очередь с приложениями в области стандартизации и унификации [1,17,18]. Работы B. J1. Береснева, Э. Х. Гимади, В. Т. Дементьева, Н. И. Глебова, а позже А. И. Давыдова, Ю. А. Кочетова, A.B. Плясунова, Ю. В. Шамардина, JT.E. Горбаневской, A.A. Агеева и др. создали фундамент для разработки программно математического аппарата решения соответствующих экстремальных задач.

В общем виде дискретные задачи размещения моделируют ситуации', — в которых из заданного множества объектов требуется выбрать некоторое подмножество так, чтобы удовлетворить заданные потребности с наименьшими затратами или наибольшей прибылью. В качестве объектов могут выступать филиалы крупной компании, складские комплексы, компоненты микросхем и многое другое.

Дискретные задачи размещения имеют конечную область допустимых решений, поэтому заранее известно, что в задаче существует оптимальное решение. При небольшой размерности, оптимальное решение можно найти, перебрав все множество допустимых решений. Однако реальные размерности задач ограничивают возможности переборного алгоритма даже с применением современных вычислительных технологий. Поэтому основная цель, которую преследует большинство ученых в этой области заключается в разработке непереборных алгоритмов, способных за разумное время найти оптимальное или близкое к оптимальному решение задачи. Известно, что многие задачи размещения относятся к классу NP-трудных задач, т. е. построение точных полиномиальных алгоритмов скорее всего является бесперспективным подходом. Поэтому исследования дискретных задач размещения и разработка алгоритмов их решения ещё долгое время будет актуальной темой.

Основными направлениями исследований, как правило, являются:

— выявление полиномиально разрешимых случаев задачи, построение для них полиномиальных алгоритмов;

— разработка приближённых алгоритмов с априорными оценками точности;

— разработка итерационных методов локального поиска и эвристических алгоритмов.

В данной работе исследования ведутся по последнему направлению.

Существует большое число прикладных задач, для которых соответствующие математические модели принадлежат классу дискретных задач размещения. Основополагающими задачами в этом классе принято считать: простейшую задачу размещения, задачу о р-медиане и задачу о рцентре. Несмотря на то, что эти задачи являются хорошо изученными и им посвящено огромное число публикаций, они до сих пор привлекают внимание ученых, т. к. составляют основу других интересных моделей. и аккумулируют в себе основные математические трудности.

Так как диссертационная работа посвящена одному обобщению задачи о р-медиане, то приведём сначала математическую формулировку классической задачи о р-медиане и дадим краткий обзор основных известных результатов.

Пусть задано два конечных множества I = {1,., т} и 3 = {1,., п}. Первое множество будем интерпретировать как множество возможных пунктов размещения предприятий для производства некоторого однородного продукта, второе — множество клиентов, использующих этот продукт. Известны величины Сц, г € I, ]? .7, задающие транспортные затраты на обслуживание го клиента из г-го пункта. Требуется выбрать из множества / не более р пунктов, в которых следует разместить предприятия, т. е. найти подмножество 5 С / мощности не более р так, чтобы суммарные затраты на обслуживание всех клиентов были бы минимальными. Комбинаторная формулировка задачи имеет следующий вид: %

Установлено [48], что задача о^{медиане} является ИР-трудной./ В [5] показано, что если матрица (с^-) есть матрица кратчайших расстояний на дереве, то задача полиномиально разрешима. В [61] доказано, что в общем случае существование приближённого алгоритма с гарантированной относительной погрешностью не более 2^п, т где д — произвольный полином от размерности задачи, влечёт совпадение классов Р и ЫР. Особое внимание в литературе уделяется метрическому случаю, когда элементы матрицы (с¿-¿-) удовлетворяют неравенству треугольника. В этом случае стандартный алгоритм локального спуска приводит к локальному оптимуму с относительной погрешностью не более (3 + где к — число предприятий, которые могут заменяться в решении на другие при каждом локальном улучшении [25]. Каждый шаг такой итерационной процедуры имеет трудоемкость не более 0(тк), но число шагов может оказаться экспоненциальным. Лучший из известных полиномиальных алгоритмов имеет погрешность не более (3 + е), е > О, [53].

В перечисленных выше моделях размещения предполагается, что решение принимает одно лицо, стоящее на высшем уровне иерархии. Отчасти это объясняется тем, что многие задачи размещения возникли в период централизованного управления. В последнее время в условиях рыночной экономики более актуальными становятся ситуации, когда несколько лиц на разных уровнях иерархии участвуют в процессе принятия решений. В таких моделях участники процесса имеют собственные цели и предпочтения, которые могут быть противоположными, в результате чего возникают конфликтные ситуации. Процесс принятия решений в таких системах выглядит следующим образом. Первым принимает решение верхний уровень иерархии. Это решение передаётся нижестоящим и уже не меняется. Каждый уровень иерархии, получив решение вышестоящих уровней, принимает своё решение. Он преследует свои цели и использует имеющиеся у него возможности и ресурсы. Результат деятельности иерархической системы в целом зависит от работы всех уровней иерархии. Задача состоит в том, чтобы найти такое решение верхнего уровня, которое приводит систему к достижению глобальной цели.

Если верхний уровень полностью определяет поведение нижестоящих уровней, то моделирование процессов принятия решений упрощается. В этом случае возникают классические задачи математического программирования, в которых область допустимых значений задается набором равенств и неравенств. Если же верхний уровень может только влиять на работу нижних уровней, то возникает новый класс задач. Область допустимых значений в данном случае задается с помощью вспомогательных (внутренних) задач, моделирующих поведение нижних уровней иерархии. Решения вышестоящих органов выступают в этих задачах в качестве ограничений.

Задачи, в которых рассматриваются только два уровня иерархии, называются задачами двухуровневого программирования. Впервые такие задачи в игровой постановке рассматривались в [70]. В России над этими задачами работали Ю. Гермейер и его ученики [4]. Обзор современного состояния в области двухуровневого программирования можно найти, например, в [24, 73].

В диссертации рассматривается задача о р-медиане с предпочтениями клиентов (МПК). В этой задаче имеются два уровня принятия решений. Они неравноправны. Сначала на верхнем уровне принимается решение об открытии р предприятий. Затем на нижнем уровне, зная места расположения этих предприятий, клиенты самостоятельно выбирают поставщиков, руководствуясь собственными предпочтениями. Задача состоит в том, чтобы выбрать на верхнем уровне открываемые предприятия и обслужить всех клиентов с минимальными суммарными затратами, принимая во внимание тот факт, что поставщиков выбирают не на верхнем, а на нижнем уровне. Если предпочтения на нижнем уровне совпадают с предпочтениями на верхнем уровне, то получаем классическую задачу о р-медиане. Следовательно, задача МПК является КР-трудной в сильном смысле и не принадлежит классу АРХ [13].

Впервые задачи размещения с предпочтениями клиентов рассматривались П. Ханжоулем и Д. Петерсом [42]. Позже аналогичные модели независимо были построены В. Т. Дементьевым, Ю. В. Шамардиным и Л. Е. Горбачевской [6, 7, 8]. В [6] доказано, что если матрица транспортных затрат в целевой функции на верхнем уровне и матрица предпочтений клиентов на нижнем уровне обладают свойством связности, то такая задача решается эффективно. Если же матрица предпочтений является квазивыпуклой, то задача сводится к задаче о «ближайшем соседе» с фиксированным числом точек в оптимальном решении. В [8] исследовалась более общая задача без ограничения на число открываемых предприятий с условием единственности оптимального потребительского выбора. В [2] приводится сведение общего случая задачи МПК без ограничения на число открываемых предприятий к задаче минимизации полиномов от булевых переменных. Это сведение позволяет выявить полиномиально разрешимые случаи решения задачи. Вопрос построения полиномиальных приближенных алгоритмов с гарантированными оценками точности для метрической задачи МПК остаётся на сегодняшний день открытым.

Как обобщение классической задачи о р-медиане задача МПК относится к классу ОТ-трудных задач в сильном смысле. Поэтому для её решения часто используются различные эвристические алгоритмы. На сегодняшний день наиболее успешными при решении практических задач являются итерационные методы локального поиска. К ним можно отнести поиск с запретами [36, 37, 38, 64], поиск с чередующимися окрестностями [44], генетические алгоритмы [39], алгоритмы имитации отжига [20, 50] и другие метаэвристики [51, 33, 63, 65]. Многие из них используют стандартную процедуру локального спуска. Это процесс последовательного движения от текущего к соседнему решению с лучшим значением целевой функции. Процесс останавливается, когда достигнут локальный оптимум, то есть решение, которое не имеет соседнего решения с лучшим значением целевой функции. Предполагается, что для каждого решения задано множество соседних решений или окрестность. Задачу нахождения локального оптимума для заданной окрестности называют задачей локального поиска.

С теоретической точки зрения интересным представляется изучение вычислительной сложности алгоритмов локального поиска, анализ поведения алгоритма в среднем и худшем случаях. Эмпирические результаты показывают, что для многих NP-трудных задач [33, 36, 46, 63, 67] локальный поиск позволяет находить приближенные решения близкие по значению целевой функции к глобальному оптимуму. Причём трудоемкость в среднем часто оказывается полиномиальной. Однако для целого ряда окрестностей и при любом выборе направления спуска число шагов алгоритма в худшем случае, например, для решения задачи о р-медиане, не может быть ограничено сверху полиномом от длины записи исходных данных [13]. Для теоретического анализа вычислительной сложности задач локального поиска используется специальный класс PLS (сокращение от polynomial-time local search problems). С содержательной точки зрения этот класс содержит те задачи, в которых локальная оптимальность может быть проверена за полиномиальное время: для заданного решения требуется определить, является ли оно локальным оптимумом, и если нет, то найти соседнее решение с лучшим значением целевой функции. В этом случае соответствующую окрестность называют полиномиально проверяемой. Если предположить, что NP^co-NP, то в классе PLS нет NP-трудных задач [68, 75]. Другими словами, не существует NP-полных задач, которые за полиномиальное время сводились бы к какой-нибудь задаче локального поиска из класса PLS. Это утверждение показывает, что скорее всего класс PLS не содержит NP-трудных задач. Поэтому задачи локального поиска не так сложны, как NP-трудные, что, в частности, подтверждают и экспериментальные исследования. Нахождение локального оптимума для полиномиально проверяемой окрестности не представляется сложным делом на практике. В классе Р1Д как и в классе удалось выделить наиболее трудные задачи, РЬБ-полные задачи, для которых доказан аналог теоремы Кука [47]. Если существует полиномиальный алгоритм решения хотя бы одной РЬБ-полной задачи, то все задачи из класса РЬБ полиномиально разрешимы. Однако до сих пор неизвестно ни одного полиномиального алгоритма решения РЬБ-полных задач. Построение такого алгоритма было бы сенсацией. Все задачи из класса РЬБ оказались бы полиномиально разрешимыми. Как пишут Я. К. Ленстра и Т. Вредевельд [74] «.скорее всего это не так, потому что существование такого алгоритма потребовало бы разработки достаточно общего подхода для нахождения локальных оптимумов, не менее общего, чем метод эллипсоидов, так как задача линейного программирования с симплексной окрестностью принадлежит классу РЬБ» .

Аналогия с линейным программированием здесь весьма уместна и может быть даже глубже, чем кажется. Рождение симплекс метода толкнуло вперёд разработку методов линейного программирования и сегодня это один из самых мощных методов, используемых в приложениях. Он не является полиномиальным при оценке поведения в худшем случае, но в среднем он работает очень эффективно [14, 16, 62]. Аналогичную картину можно наблюдать и с алгоритмами локального спуска. Установлено [75, 13], что в худшем случае для ряда РЬБ-полных задач алгоритм локального спуска требует экспоненциального числа итераций, но в среднем его поведение полиномиально. Это обстоятельство объясняет интерес к таким алгоритмам, исследование их возможностей и модификаций, а также применение в более сложных схемах метаэвристик. Именно эти вопросы являются центральными в диссертации и исследуются на примере задачи МПК.

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

Заключение

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

2. Установлено, что целочисленное решение является локальным оптимумом для окрестности N1 тогда и только тогда, когда оно удовлетворяет условиям Куна-Таккера. Показано, что эти условия равносильны существованию множителей Лагранжа, для которых целочисленное решение исходной задачи является седловой точкой относительно окрестности N1.

3. Для решения задачи о р-медиане с предпочтениями клиентов разработан генетический алгоритм с апостериорной оценкой точности. Исследованы три формулировки задачи в виде задачи ЦЛП. Показано, что одна из этих формулировок приводит к лучшей нижней оценке, чем две другие.

4. Для задачи оптимизации парка сельскохозяйственных машин разработана система поддержки принятия решений, интеллектуальным ядром которой является математическая модель задачи о р-медиане с предпочтениями клиентов на максимум. Проведенные тестовые расчеты на реальных исходных данных показали высокую эффективность разработанного математического аппарата.