Исследование и решение минимаксных и минисуммных задач размещения на сетях

Значительное число работ в области исследования операций посвящено решению проблем планировки и расположения объектов. Задачи размещения имеют обширную сферу практического применения, поскольку область, в которой производится размещение, может иметь различную структуру, и термин «объект» может трактоваться достаточно широко. Такие задачи возникают при размещении различных пунктов обслуживания, например, больниц, магазинов, пожарных депо, формировании генеральных планов предприятий [5,17], проектировании печатных плат [1,6], конструировании летательных аппаратов [49] и выполнении других работ.

Следует отметить, что изучение задач размещения объектов началось в 17 веке, когда Ферма сформулировал задачу, известную ныне как задача Вебера [27,82,98]: даны три точки на плоскости, требуется найти четвертую точку, такую, что сумма расстояний от нее до трех фиксированных точек минимальна. Задача была решена геометрически Торичелли в 1640 году. В 1750 году Симпсон обобщил задачу в направлении учета произвольных весов связей между объектами. В 1909 году Вебер использовал подобную модель для определения оптимального размещения фабрики при известных точках расположения ресурсов и потребителей продукта.

Среди задач размещения можно выделить два больших класса: задачи размещения взаимосвязанных объектов и задачи размещения-распределения (задачи размещения предприятий). К первому классу относятся задачи с заранее заданной структурой связей между объектами: задача Вебера [27,45,54,82,94,98], квадратичная задача о назначениях [70,88] и т. п. В задачах из второго класса отсутствуют связи между размещаемыми объектами-" поставщиками" и производится распределение фиксированных объектов-" клиентов" между ними: задачи о р-медиане [38,40,70,84] и р-центре [40,67,70,83], простейшая задача размещения [2,3,7,9,70,77,80,89,91] и др.

В задачах оптимального размещения взаимосвязанных объектов учитывается определенное «взаимодействие» объектов между собой.

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

Формулировка каждой задачи содержит основные показатели, которые могут быть использованы для классификации задач (область размещения, форма объектов и др.). Область, в которой размещаются объекты, может быть различной: линия [14,16,63,95,99], плоскость [1, 41, 42, 54, 64, 70, 82, 96, 98], пространство [18, 71], граф или сеть [15,75, 76,83,84,94] и т. д. Объекты могут быть как точечными.

54,64,70,82−84,94,96,98], так и протяженными, например, прямоугольными [41−43]. Рассматриваются дискретные и непрерывные задачи размещения. В дискретных задачах для размещения задано конечное число мест, в непрерывных — множество, в котором могут быть расположены объекты, не является дискретным, и определена метрика для измерения расстояний между объектами.

Дискретные задачи оптимального размещения часто бывает удобно описывать с помощью моделей целочисленного программирования. Условие целочисленности позволяет учесть, например, наличие альтернатив при размещении объектов и другие особенности задачи. Для задач целочисленного программирования разработано большое количество методов решения: ветвей и границ, отсечения, множителей Jla-гранжа, декомпозиции [8,36,39,46−48,78,79], а также метод регулярных разбиений [29−35] и др.

В последние годы для решения задач оптимизации активно разрабатываются алгоритмы локальной оптимизации, а также подходы, основанные на аналогиях с природой (генетические алгоритмы, имитация отжига, алгоритмы муравьиной колонии и др.) [4,12,13,37,65,72,73, 85,90,92,97].

Рассмотрим обобщенную задачу Вебера [27,44,54,81,98]. Математически задача формулируется следующим образом. Задано т фиксированных объектов, размещенных в точках vl,., vm метрического пространства. Требуется разместить п новых объектов в этом же пространстве. Паре новых объектов (j, к) ставится в соответствие удельная стоимость связи vjk, l< г < ш, 1 < j < п. Пусть d (x, y) — расстояние между точками х и у метрического пространства. Необходимо найти набор X = (ж1,., хп) точек для размещения новых объектов, чтобы суммарная стоимость связей была минимальной:

Vjkd (xj, xk)+ J2 Y1 Wijd{vxj) min. l.

Отметим, что в указанной задаче нет ограничений на взаимное расположение объектов. В качестве метрического пространства может рассматриваться, например, плоскость с Евклидовой [82] или прямоугольной [54,64,96] метриками. В случае прямоугольной метрики обычным приемом является разбиение задачи на две однотипные независимые подзадачи по координатам. Каждая из них представляет собой одномерную задачу Вебера. Для решения последней используются потоковые алгоритмы: нахождения максимального потока [54], потока минимальной стоимости [64] или минимального разреза [96]..

В работе [52] рассматривался вариант задачи Вебера на плоскости, в которой заданы не только точки «притяжения» для размещаемых объектов, но также точки «отталкивания». Такая задача является невыпуклой, для ее решения применялся метод, основанный на необходимых и достаточных условиях глобального экстремума..

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

Сформулированная ранее задача Вебера относится к непрерывным задачам. Рассматриваются также варианты задачи, в которых для объектов заданы возможные места установки (дискретная постановка). Обозначим через a (j) номер места размещения j-го нового объекта. Пусть d (i, j) — расстояние между местами г и j размещения объектов. Задача состоит в определении вектора размещений a = (a (l),., a (n)), минимизирующего суммарную стоимость связей между объектами:.

Е vjkd (a (j), a (k))+? ? u>ijd (i, a (j))min. l.

Такие задачи называются также задачами размещения с квадратичной целевой функцией [27]..

Задача Вебера исследовалась в работах А. В. Панюкова [41−43,94]. В работе [44] показано, что задача Вебера в общем случае является iVP-трудной [10]..

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

Задачи размещения часто сводятся к минимизации взвешенной суммы расстояний, как это было выше, или минимизации максимального взвешенного расстояния между объектами [27]. К последнему типу задач относится минимаксная задача размещения. Эти задачи рассматривались на плоскости с прямоугольной метрикой [68] и на древовидной сети [69,75,76]. Для каждой пары объектов могут быть заданы максимальные расстояния [68,69,75]..

Критерием оптимального размещения новых объектов может быть минимум суммы взвешенных расстояний от фиксированного объекта до ближайшего размещенного объекта. Такая задача называется задачей о р-медиане [40,70,84]. Обозначим искомое множество размещения новых объектов через Хр = {х,., хр}. Пусть расстояние между фиксированным объектом в точке Vi, 1 < i < т и размещаемыми объектами определяется выражением d (vi, Xp) = min d (vi, Xj). i.

Обозначим через w (vi) вес соответствующего фиксированного объекта. Тогда задачу о р-медиане можно сформулировать следующим образом: найти множество точек Хр (^-медиану), минимизирующее функционал.

J2 w (vi)d (vi, Xp)..

1 .

Если в качестве критерия размещения выбирается минимум максимального взвешенного расстояния от фиксированного объекта до ближайшего нового объекта, то такая задача называется задачей о р-центре [40,67,70,83]. Множество точек Хр называется р-центром, если функционал max w (vi)d (vi, Xp) l.

В [25] приведены вариации задачи о вершинном р-центре на древовидной сети, в которых учитывались максимальные расстояния между вершинами р-центра и расстояния до выделенных вершин (так называемых баз)..

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

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

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

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

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

Нами предлагается алгоритм, в котором используются идеи из статьи [75]. В нем при бинарном поиске производится проверка не одного значения целевой функции, а некоторого интервала значений, границы которого вычисляются с применением теории двойственности в линейном программировании (ЛП) [53]. Это позволяет находить оптимальное размещение в случае, когда оптимальное значение целевой функции попадает в указанный интервал..

Исследуется дискретная минимаксная задача размещения на древовидной сети с ограничениями на максимальные расстояния, в которой новые объекты могут размещаться только в вершинах сети. Разработан г полиномиальный алгоритм ее решения..

Рассматривается минисуммная задача размещения на древовидной сети. В статье [96] предлагалось решение задачи размещения на плоскости с прямоугольной метрикой без ограничений на расстояния между объектами. Задача декомпозировалась на две задачи размещения на линии по координатам х и у. Одномерные задачи размещения решались с помощью построения серии минимальных разрезов на некоторых вспомогательных сетях. В данной работе построен алгоритм решения минисуммной задачи размещения на древовидной сети с ограничениями на максимальные расстояния между новыми и фиксированными объектами..

Во второй главе изучаются минимаксные и минисуммные задачи размещения объектов на произвольных сетях. Постановкам этих задач на плоскости и деревьях посвящено значительное количество публикаций, для их решения предлагаются полиномиальные алгоритмы [45,54,64,75,76,96]. В случае произвольной сети ситуация иная, указанные задачи являются iVP-трудными. Поэтому здесь основное внимание уделяется алгоритмам ветвей и границ, в которых при построении оценок используется теория, разработанная для задач на древовидных сетях..

Приведена классификация сложности решения минимаксных и ми-нисуммных задач размещения в зависимости от структуры сети. На деревьях эти задачи полиномиально разрешимы, на произвольных сетях — ./VP-трудны. Доказана iVP-трудность дискретной минимаксной задачи размещения..

Описана методика сведения широкого класса задач размещения на древовидной сети к эквивалентным задачам математического программирования (МП). Для минимаксных и минисуммных задач размещения взаимосвязанных объектов с использованием данной методики построены эквивалентные задачи ЛП. Полученное решение задачи ЛП может использоваться для определения оптимального размещения на древовидной сети, либо для получения нижних оценок в алгоритмах ветвей и границ..

Доказаны необходимые условия существования допустимого размещения в вершинах сети. С использованием этих условий разработаны алгоритмы ветвей и границ для решения дискретных минимаксных и минисуммных задач с ограничениями на максимальные расстояния. Указанные алгоритмы реализованы на ЭВМ, приведены результаты вычислительного эксперимента..

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

Предлагаются алгоритмы последовательного одиночного размещения [1,5,6,50], подобные методы часто применяются на практике. Согласно идее метода, объекты упорядочиваются в соответствии с некоторым критерием, а затем последовательно размещаются наилучшим образом с соблюдением заданных ограничений..

Описывается общая схема генетического алгоритма [13,37,73,97], который относится к широкому классу эволюционных стратегии, основанных на принципе моделирования процесса биологической эволюции. Предлагается несколько вариантов генетического алгоритма для решения минимаксных и минисуммных задач размещения..

Широко применяются и хорошо зарекомендовали себя для решения задач оптимизации различные методы локального поиска [37,67]. Приводится описание общей схемы алгоритма поиска с запретами [37,90]. Предлагаются варианты реализации этого алгоритма для решения минимаксных и минисуммных задач размещения..

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

В заключении приводятся основные результаты диссертации..

Основные результаты работы опубликованы в работах [19−24,55−60, 100−102] и докладывались на XI Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1999), Symposium on Operations Research (Магдебург, Германия, 1999), международной конференции «Дискретный анализ и исследование операций» (Новосибирск, 2000), научной молодежной конференции «Молодые ученые на рубеже третьего тысячелетия» (Омск, 2001), XII Байкальской международной конференции «Методы оптимизации и их приложения» (Иркутск, 2001), Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2002), International Conference on Operations Research (Клагенфурт, Австрия, 2002), 12-й Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2003), Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2003), Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2004), Международном семинаре «Discrete Optimization Methods in Production and Logistics» (Омск-Иркутск, 2004), a также на заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» в Омском филиале Института математики им. C.JI. Соболева СО РАН. щ Автор благодарит научного руководителя Колоколова А. А., а также.

Забудского Г. Г. за полезные советы, внимание и поддержку при выполнении данной работы..

Основные результаты диссертации заключаются в следующем:.

1. Предложены достаточные условия оптимальности решения для непрерывной минимаксной задачи на древовидной сети с ограничениями на максимальные расстояния. Построен полиномиальный алгоритм решения дискретного варианта задачи..

2. Разработан полиномиальный алгоритм получения точного решения для минисуммной задачи размещения на дереве с ограничениями на максимальные расстояния..

3. Доказано, что задача определения совместности ограничений на максимальные расстояния в случае размещения объектов в вершинах сети, а также дискретная минимаксная задача оптимального размещения на произвольной сети являются ./VP-трудными..

4. Получены необходимые условия существования допустимого размещения на произвольной сети для дискретного варианта задачи с ограничениями на максимальные расстояния. На их основе разработаны алгоритмы ветвей и границ для минимаксной и минисуммной задач..

5. Разработаны эвристические алгоритмы: последовательного одиночного размещения, генетический алгоритм и поиск с запретами для решения указанных выше задач. Предложенные алгоритмы реализованы, проведено их экспериментальное сравнение, которое показало эффективность разработанных алгоритмов..

Полученные в работе результаты позволяют сделать вывод о перспективности применения построенных алгоритмов. т т.

Заключение.

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