Содержание к диссертации
Введение
1 Задачи размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций 25
1.1 Задача размещения на сети с ограниченными пропускными способностями коммуникаций 25
1.1.1 Постановка задачи 25
1.1.2 Задача размещения на древовидной сети 28
1.1.3 Задача размещения на два-дереве 33
1.2 Задача размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций . 38
1.2.1 Постановка задачи 38
1.2.2 Сравнение релаксаций 41
1.2.3 Вычисление релаксаций 46
1.2.4 Реализация метода ветвей и границ 47
2 Приближенные алгоритмы для репіения задач размещения с ограниченными объемами производства и поставок и обоснование условий их асимптотической точности 51
2.1 Постановки задач 51
2.2 Вспомогательные понятия и утверждения 54
2.3 Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и условия его асимптотической точности 57
2.4 Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и единичными объемами поставок и условия его аснптотпческоп точности 66
2.5 Замечания 76
3 Приближенный алгоритм для задачи размещения на максимум с ограниченными объемами производства и поставок 80
3.1 Постановка задачи 80
3.2 Субмодулярные функции и жадный алгоритм 82
3.3 Эквивалентная задача 84
3.4 Оценки качества алгоритма 86
Заключение 91
Список публикаций автора по теме диссертации 93
Благодарности 95
Список литературы 96
- Задача размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций
- Вспомогательные понятия и утверждения
- Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и единичными объемами поставок и условия его аснптотпческоп точности
- Субмодулярные функции и жадный алгоритм
Введение к работе
Развитие экономических и производственных отношений в обществе потребовало решать задачи, связанные с принятием целесообразных (верных, правильных, оптимальных) решений в сложных системах взаимоотношения между различными объектами хозяйственной деятельности, будь то оптимальная доставка хлебобулочных изделий от хлебозаводов к магазинами или составление плана работ при постройке космического корабля.
Решая подобные задачи и абстрагируясь от их конкретных постановок, в математике возникла новая наука - исследование операций. В более узком смысле эту область науки называют теорией математических моделей и методов принятия решений. Оказалось, что во многих случаях переменные в таких задачах могут принимать только конечное число состояний. Например, в магазин может быть поставлено только конечное число хлебобулочных изделий в конечном ассортименте. В теории математического программирования такие задачи входят в область дискретной оптимизации. Множество допустимых решений таких задач конечно, и мы, в принципе, можем найти точное решение, перебрав все допустимые решения.
Осуществляя такой подход к дискретным задачам оптимизации, в большинстве случаев мы замечаем, что с ростом размерности задач (объема исходных данных) число требуемых действий для нахождения оптимального решения растет очень быстро (например, экспоненциально). А возникающие на практике проблемы, как правило, ставят перед нами задачи больших размерностей. Однако, ни в настоящий момент, ни в обозримом будущем вычислительные мощности компьютеров вряд ли будут способны решать такие задачи подобным образом.
Среди дискретных задач оптимизации принято выделять класс задач Р, разрешимых за полиномиальное время (в зависимости от длины входа) и класс NP- трудных задач, для которых построение полиномиальных алгоритмов проблематично (если только NP не равно Р). К сожалению, многие естественные и интересные задачи дискретной оптимизации являются NP-трудными. Показано, что если найдется быстрый алгоритм (число действий которого зависит полиномиально от размерности задачи) хотя бы для одной NP-трудной проблемы, то такие алгоритмы можно будет построить для всех задач из этого класса. Одной из самых фундаментальных проблем современной математики является вопрос: существует ли такой быстрый алгоритм для NP-трудных задач? Многие исследователи склоняются к отрицательному ответу на этот вопрос.
Ввиду проблематичности построения быстрых алгоритмов для NP-трудных задач научные исследования направляются на изучение более частных вопросов теории NP-трудных проблем. Можно выделить сле-
дующие основные направления исследований:
выделяются классы подзадач, для которых удается построить эффективные точные алгоритмы:
тем пли иным способом ограничивают перебор среди всего множества допустимых решений;
строятся эффективные приближенные алгоритмы с гарантированной оценкой точности;
исследуется вероятностное поведение алгоритмов при условии, что для некоторых входных данных задано вероятностное распределение.
Одной из самых известных задач в исследовании операций является дискретная задача размещения. Имеется большое число работ, посвященных данной проблеме. Mirchandani и Francis [87] выделяют несколько основных классов задач размещения: простейшая задача размещения, задача размещения с ограниченными объемами производства, задача о р-медиане, задача о р-центре. Простейшая задача размещения, видимо, самая известная и изученная задача размещения. Ее можно рассматривать как базовую для ряда других задач размещения. Так, задача размещения с ограниченными объемами производства получается после добавления ограничений на мощности производства.
Помимо NP-трудных задач в исследовании операций имеются задачи, для которых удалось построить быстрые (полиномиальные) алгоритмы. Таковой, например, является задача о потоке минимальной стоимости [40, 90]. Процессы, которые моделируются этой проблемой,
очень актуальны во многих сферах человеческой деятельности. Например, упомянутые потоки можно рассматривать как транспортные потоки, либо как потоки финансовых средств.
Содержание настоящей диссертационной работы составляют исследования обобщений задачи размещения со следующими ограничениями:
ограничения на объемы производства;
ограничения на пропускные способности коммуникаций для задач размещения на сети;
ограничения на объемы поставок как частный случай ограничений на пропускные способности коммуникаций.
Задачу размещения на сети с ограниченными пропускными способностями коммуникаций можно рассматривать как синтез NP-трудной простейшей задачи размещения и задачи о потоке минимальной стоимости. Поскольку и простейшая задача размещения, и задача о потоке минимальной стоимости очень актуальны для практических приложений, то можно надеяться, что обобщение этих задач может найти очень широкое применение на практике.
Можно заметить, что известна более общая многопродуктовая постановка задачи, к которой сводится в однопродуктовом случае задача размещения на сети с ограниченными пропускными способностями коммуникаций. Это задача конструирования сети с ограничениями на пропускные способности коммуникаций. Как признаются Holmberg, Yuan [77] в чьей статье рассматривалась эта проблема, получено очень
мало результатов для этой задачи. Сами они смогли указать только один препринт [69]. В этих двух работах приводится апостериорный анализ численных экспериментов для неявного перебора с использованием Лагранжевых релаксаций. Судя по этим двум публикациям, сколько-нибудь других существенных результатов для этой задачи не получено.
Приведем далее математические постановки простейшей задачи размещения и задачи размещения с ограниченными объемами производства, которые являются основой для исследуемой нами задачи размещения и дадим краткий обзор по полученным результатам.
Пусть даны множество I = {1,... , т} возможных пунктов размещения предприятий и множество пунктов потребления J = {1,..., п}. В некоторых постановках задач множества / и J могут совпадать. Пусть заданы начальные затраты по размещению предприятия д, і Є /, и объемы потребления продукта bj,j Є J. Указаны затраты gij по доставке единицы продукта из і Є I в j Є J. Требуется указать те предприятия из /, при вводе которых в систему, во-первых, полностью бы удовлетворялись спросы всех пунктов потребления, и, во-вторых, затраты, связанные с обслуживанием всех пунктов потребления с учетом размещения предприятий были бы минимальными.
Простейшая задача размещения (ПЗР) в комбинаторной постановке формулируется в следующем виде:
mm flf? + bj mm
^1 UeS jeJ lS
Запишем ее формулировку в виде задачи линейного целочисленного программирования. Требуется найти минимум функционала:
Е^і + ЕЕ^ч,
гЄІ гЄІ jEJ
по всем переменным Хі, X{j при условиях
Y^Xij = bj, j Є J, iei
0 < X{j < bjXi, і Є I, j Є J,
x{e {0,1}, г Є/.
Здесь переменные Хі - это переменные выбора: если мы открываем предприятие г, то .тг- = 1, в противном случае Х{ — 0. Переменные х^ - это переменные назначения, равные количеству единиц продукта, поставляемых из г Є / в j Є J-
Эта задача относится к числу NP-трудных проблем, так как к ней сводится NP-трудная задача о минимальном покрытии конечного множества системой конечных подмножеств [30].
Для задачи размещения с ограниченными объемами производства задаются также ограничения d{ на мощность каждого предприятия і (Е І. Для этой задачи помимо упомянутых выше ограничений добавляются ограничения
Перечислим известные результаты для этих задач по упомянутым выше четырем направлениям исследований.
Для ПЗР на сетях специального вида имеются ряд работ. Для случая, когда сетью является дерево, сначало Трубпн [38] построил, а затем Kolen [82] переоткрыл алгоритм с трудоемкостью О (/7,3), где п - размерность задачи. Гимадн [16] и позже Billionet, Costa [51] удалось улучшить оценки трудоемкости алгоритма, решая эту задачу за время О(пт) и 0(п2) соответственно, где т - число возможных пунктов размещения производства. Самый последний результат получен Shah, Farach-Colton [97]. Они предложили алгоритм с трудоемкостью 0(пlogп). Агеевым [1] была решена задача на внешнепланарном графе за время 0(п^т). Hassin и Tamir [73] представили алгоритм для последовательно-параллельной сети с временной сложностью О (г?4). Позже для этого же случая задачи Агеевым [2] был построен алгоритм с трудоемкостью 0(пга3).
Удалось также построить полиномиальные алгоритмы для ПЗР при следующих ограничениях, накладываемых на матрицу расстояний: для односвязной матрицы в монографии Вереснева, Гимади, Дементьева [12]; для двусвязной матрицы в работе Вереснева [10]; для квазивыпуклой, квазивогнутой и обобщенно-квазивыпуклой матрицы в статье Гимади [20]. Для задачи с матрицами, порожденными частичными q-деревьями, Агеевым [42] предложен полиномиальный алгоритм с трудоемкостью 0(nmq+l). Бересневым [10] установлена эквивалентность ПЗР и задачи минимизации булевых полиномов. Это позволило выде-
лить новые классы эффективно решаемых задач [4, 5, 10].
В то же самое время для некоторых классов задач имеются и отрицательные результаты: Агеевым в работе [43] было показано, что ПЗР является АгР-трудной, даже если матрица (/^-) порождена расстояниями на плоской решетке.
Можно привести еще целый ряд работ, в которых ПЗР рассматривалась как с точки зрения полиномиально разрешимых подклассов так и с точки зрения других видов анализа NP-трудных задач [6, 7, 9, 11, 27, 15, 17, 18, 19, 21, 22, 23, 32, 39, 41]. Более подробный обзор по полиномиально разрешимым подклассам для ПЗР можно найти в препринте Гришухина [28], а также в книге Mirchandani, Francis [87].
Далее мы коснемся переборных способов нахождения точного решения задачи размещения. Наиболее типичный представителем таких методов является метод ветвей и границ. Впервые он был предложен Land и Doig [84] для задачи многомерного рюкзака. Определение этого метод можно найти в книге Вереснева, Гимади, Дементьева [12].
Вообще говоря, метод ветвей и границ не гарантирует избежания полного перебора. Но практическая реализация этого метода в ряде случаев дает хорошие апостериорные оценки времени работы метода. В работах Вереснева [8], Вереснева, Гимади, Деменьтева [12], Гимади, Глебов, Дементьев [24]. Erlenkotter [62] и Efroymson, Ray [61] представлены реализации метода ветвей и границ для простейшей задачи размещения. Задача размещения с ограниченными объемами производства была решена методом ветвей и границ в работах Akinc,
Khumawala [46], Nauss [88], Davis, Ray [60], Sa [95] и Гимади, Глебов, Дементьев [24]. Наиболее важным этапом в этом методе является вычисление нижней оценки для задачи на минимум. Здесь следует искать компромисс между точностью оценки и трудоемкостью ее вычисления.
В качестве нижней оценки можно взять значение Лагранжевой релаксации соответствующей задачи. Это делается следующим образом. Для многих NP-трудных задач можно выделить те ограничения, после удаления которых задача становится полиномиально разрешимой. Было предложено заносить эти ограничения в целевую функцию с некоторыми коэффициентами, так называемыми множителями Ла-гранжа. Решение релаксированной таким образом задачи дает оценку снизу для целевой функции исходной задачи на минимум. Помимо этого, решения релаксированной задачи можно использовать в качестве начальной точки при построении приближенного решения исходной задачи с апостериорной оценкой точности.
В работе Everett [63] было впервые предложено использовать обобщенные множители Лагранжа для дискретной задачи оптимизации. В статьях Shapiro [98] и Fisher и Shapiro [68] идея этого метода применяется к общей задаче целочисленного программирования. Термин "Лагранжевые релаксации"был предложен Geoffrion [70]. Fisher, Northup и Shapiro [67] представили свой способ вычисления множителей Лагранжа. Имеется общий обзор Shapiro [99] по этой теме исследований. В работе Cornuejols, Fisher, Nemhauser [56] Лагранжевые релаксации исследуются для задачи размещения на максимум. (Точная формули-
ровка этой задачи будет дана ниже). В статье Cornuejols, Sridharan, Thizy [59] приводится сравнительный анализ большого числа эвристик и релаксаций, в основном Лагранжевых, для задачи размещения с ограниченными объемами производства.
Разновидностью метода ветвей и границ является метод узловых векторов, представленный в работе Седова, Лебедева [37]. Для задача размещения на минимум нижняя оценка вычисляется как максимальное значение целевой функции на множестве векторов, называемых узлами, число которых может быть существенно большим для задач большой размерности.
Общий обзор способов вычисления нижней оценки в методе ветвей и границ для простейшей задачи размещения можно найти в работе [58].
Построение точных эффективных алгоритмов для NP-трудных задач, представляется проблематичным делом (дискуссию по этому вопросу можно найти в работе Гэри и Джонсона [30]).
Поэтому, помимо построения быстрых алгоритмов для отдельных классов задач, другим важным направление исследований является построение приближенных эффективных алгоритмов с априорными (гарантированными) оценками точности. Это означает, что удается найти решение задачи, которое удовлетворяет некоторым требованиям по точности, установленными еще до получения приближенного решения.
Далее представим обзор результатов по приближенным алгоритмам с гарантированными оценками точности. В последнее время это на-
правление исследований очень бурно развивается. Так, диссертационная работа Свириденко [36] целиком посвящена исследованию приближенных алгоритмов с гарантированными оценками точности для задач размещения.
Общепринято считать, что очень известная работа Graham [71] по теории расписаний послужила началом для подобных исследований. В работе Johnson [78] вводятся понятия приближенного алгоритма и его точности в худшем случае.
В конце семидесятых годов вышло много интересных работ по приближенным алгоритмам и, как следствие этого, появилось несколько обзоров [65, 94, 96] в которых суммируются результаты, полученные за эти годы. Хорошим введением в эту область исследований являются диссертация Агога [48] и обзор Агога, Lund [49], работа Papaclimitrou, Yannakakis [92], а также обзоры [100, 76].
Напомним определения основных понятий теории приближенных решений [78]. Пусть имеется приближенный алгоритм А для решения оптимизационной задачи. Пусть / - индивидуальная оптимизационная задача, Za(I) - значение приближенного решения, полученного алгоритмом A, Z*(I) - точное значение задачи. Есть несколько способов измерения точности приближенного алгоритма. Наиболее распространенной и используемой величиной, характеризующей точность приближенного алгоритма, является так называемая относительная точность, под которой понимается функция гд(7) = Za(I)/Z*(I). Априорной оценкой относительной точности приближенного алгоритма А
решения оптимизационной задачи на максимум (минимум) является величина Ra такая, что для любой индивидуальной задачи / выполняется неравенство
ta{I)>Ra {ta{I)
Такую оценку RA, не зависящую от размерности индивидуальной задачи /, называют константной.
Для общего случая простейшей задачи размещения в работе Hoch-baum [75] построен полиномиальный жадный алгоритм, отыскивающий допустимое решение задачи, отличающиеся от точного не более чем в Inn раз, где п - число пунктов потребления. При этом использовалось сведение ПЗР к задаче о покрытии конечного множества системой конечных подмножеств, для которой Chvatal [54] построил приближенный жадный алгоритм.
Для задачи о покрытии Feige [64] показал, что для любого є > О нельзя построить приближенный быстрый алгоритм с точностью (1 — г) Inn при условии, что для NP-трудных задач не существует быстрых точных алгоритмов. Поскольку задача о покрытии сводится к простейшей задачи размещения, то этот отрицательный результат переносится и на задачу размещения. Таким образом, маловероятно, что для простейшей задачи размещения в общем случае существует приближенный алгоритм, с оценкой точности лучше, чем Inn.
В метрической задаче размещения транспортные затраты удовлетворяют неравенству треугольника: для любых i,j,k Є I U J выпол-
няется неравенство дц + gjk > дік- Для этого случая Shmoys, Tardos и Aarclal [101] предложили алгоритм, который находит допустимое решение, отличающееся от точного не более чем в 3.16 раз. Ими использована фильтрационная техника Lin и Vitter [85, 86]. Эта работа вызвала бурный рост результатов в этой области. Вслед за этой работой появились результаты, улучшающие эту оценку для рассматриваемой задачи. В работах Guha и Khuller [72] и Chudak [52] предложены ап-прокспмацпонные алгоритмы, находящие приближенные решения задачи с точностью 2.41 и 1.74 соответственно. Наиболее полный обзор результатов можно найти в докладе Агеева [3]. Наилучший результат с точностью 1.52 на сегодняшний день принадлежит Mahdian, Ye и Zhang1.
С другой стороны, Guha и Khuller [72] доказали, что для простейшей задачи размещения в метрическом случае нельзя построить приближенный алгоритм с оценкой точности лучше, чем /3 ~ 1.43, где [5 корень уравнения 1 + 2е~х = х. Таким образом, существует разрыв между положительными и отрицательными результатами, касающихся оценок точности приближенных алгоритмов для простейшей метрической задачи размещения. Это позволяет надеяться на усиление полученных для данной задачи результатов.
Для задачи размещения с ограниченными объемами производства
1 Mahdian М., Ye Y., Zhang J. Improved approximation algorithms for metric facility location problems. // 5th International workshop on approximation algorithms
for combinatorial optimization, P. 229-242.
известны следующие результаты. В работе Shmoys, Tardos и Aardal [101] для задачи с одинаковыми по величине объемами производства предложен аппроксимационный алгоритм, который находит допустимое решение, отличающееся от точного не более чем в 7 раз. При этом допускается увеличить заданные объемы производства в 3.5 раза. В работах Kompolu, Plaxton, Rajaraman [83] и Chudak, Williamson [53] предлагаются алгоритмы, которые находят приближенные решения этой задачи с точностью (8 + б) и (6 + е), соответственно, для любого е > 0 без увеличения мощности предприятий. Обзор по этой задаче также представлен в докладе Агеева [3].
Помимо простейшей задачи размещения можно рассмотреть так называемую простейшую задачу размещения на максимум, которая в комбинаторной постановке формулируется следующим образом:
max Z(S) = bj max gij - #?
S^! [jeJ ieS ieS J
Здесь величина g*- это штраф за размещение предприятия в пункте г, а величины дц интерпретируются, как прибыль, получаемая при обслуживания потребителя j Є J предприятием, размещенным в пункте г Є /. Задача сводится в нахождении такого подмножества S пунктов размещения предприятий, чтобы прибыль, получаемая при обслуживании всех пунктов потребления с учетом штрафов, была бы максимальной.
Простейшая задача размещения на минимум затрат и простейшая задача размещения на максимум затрат эквивалентны, т. е. по точ-
ному решению одной задачи можно построить точное решение другой задачи, и наоборот. Однако методы построения приближенных решений этих задач отличаются. Историческую справку и обзор по этим задачам можно найти в сборнике Cornuejols, Nemhauser и Wolsey [58].
Поскольку целевая функция простейшей задачи размещения на максимум может принимать как положительные, так и отрицательные значения, то возникают трудности с определением оценки относительной точности приближенного алгоритма. В связи с этим предлагается использовать следующую оценку для измерения относительного уклонения от точного со сдвигом в виде величины (Z* — Zg)/{Z* — Zr), где Z* и Zq - оптимальное решение и допустимое решение задачи, полученное предложенным алгоритмом, соответственно; Zr - тривиальная нижняя оценка для значения функции Z{S). Cornuejols, Fisher и Nemhauser [55] доказали, что для простейшей задачи размещения на максимум с дополнительным ограничением на количество открытых предприятий простой жадный алгоритм находит допустимое решение Zq, для которого (Z* — Zq)/{Z* — Zr) < е-1 « 0.368, где е - основание натурального логарифма.
Nemhauser, Wolsey и Fisher [89] обобщили результаты [55] для произвольной задачи, целевая функция которой является субмодулярной. Целый ряд интересных результатов удалось получить Wolsey [ЮЗ] для нескольких задач размещения, в том числе и с ограниченными мощностями предприятий. Свириденко [35] удалось обобщить понятие субмодулярной функции и для задач размещения с дополнитель-
ными ограничениями построены приближенные алгоритмы с гарантированными оценками точности. Агеев и Свириденко в статье [44] улучшили результат [55] и предложили алгоритм с оценкой точности (Z* - ZG)/{Z* -ZR)<3- 2л/2 « 0.172.
Имеется еще одно важное направление в исследовании NP-трудных задач — это вероятностный анализ поведения алгоритмов. Здесь предполагается, что на множестве индивидуальных задач задано некоторое вероятностное распределение и оценивается математическое ожидание погрешности алгоритма на этом распределении. Вероятностное поведение некоторых данных в той или иной модели очень естественно для многих практических задач. Так, спрос на хлебобулочные изделия может иметь вероятностный характер.
Здесь мы изложим идею построения алгоритма с оценками (еп,ёп), описанную в работе Гимади, Глебов, Перепелица [25]. А впервые этот метод был предложен Гимади, Перепелица [26]. Этот подход будет использован при получении результатов одной из глав диссертации.
Пусть К - некоторый класс задач. Через Z(S) обозначим оптимальное значение целевой функции для задачи S Є К. Будем считать, что рассматриваются задачи на минимум и Z(S) > 0 для всех S Є А'.
Рассмотрим теперь некоторый алгоритм А, который может быть применен к любой задаче S класса А', так что результатом этого применения является допустимое решение задачи S со значением целевой функции Za{S). При этом, вообще говоря, не исключается, что применение алгоритма А к некоторым задачам из класса К может оказаться
безрезультатным.
Если получено допустимое решение задачи 5, то качество решения
данной задачи может быть оценено через величину
ZA(S) - Z(S) Z(S)
- относительное уклонение от оптимума целевой функции, полученного в результате применения алгоритма А.
Задаваясь некоторым є > 0, можно определить множество задач Ке _ го ^ k\Za{S)-Z(S)
для которых относительная погрешность получаемых алгоритмом А решений не превышает заданной величины е. Набор множеств К\ для разных є > 0 мог бы служить достаточно полной характеристикой алгоритма А с точки зрения точности получаемых решений. Это, в свою очередь, позволяло бы сравнивать разные алгоритмы по указанным наборам множеств. Но трудность такого подхода к сравнению алгоритмов заключается в том, что практически мы, как правило, не имеем возможности получить простое описание множеств КА в явном виде.
В подобной ситуации можно пытаться использовать различные возможности косвенного описания, находить какие-то нетривиальные характеристики этих множеств. В качестве таких характеристик можно, например, рассматривать меры множеств КА относительно различных вероятностных распределений на классе К, что и осуществлено одним из возможных способов в [25].
Пусть заданы класс задач К и некоторое семейство Р вероятностных мер, определенных на классе Л'. Говорят, что алгоритм, А имеет, тип (є, 6) относительно Р, если
„ы^р *.,*.-«
для всех р Є Р.
В этом случае также говорят, что алгоритм А имеет оценки (є, 6) относительно Р .
Алгоритм А называется асимптотически точным на классе задач К, если существуют такие последовательности (єп), (5п), что для любого п алгоритм А удовлетворяет оценкам (єп,5п) на подмножестве Кп С К задач размерности п и при этом еп —> 0, 5п —» 0 при п —> со.
Заметим, что алгоритм будет точным в том и только в том случае, если он имеет оценки (0,0) относительно любого семейства вероятностных мер.
Нетрудно представить ситуацию, в которой величины є и 6 действительно могут трактоваться как оценки вероятностного характера для относительных погрешностей получаемых с помощью алгоритма А решений. В самом деле, пусть алгоритм А имеет тіш (є, 5) относительно Р и он используется для решения задач класса Л', которые поступают из некоторого случайного источника, имеющего распределение р Є Р. Тогда можно быть уверенным, что вероятность не получить алгоритмом А решение с приемлемой относительной погрешностью - не более S. При этом само распределение Р мы можем и не знать, лишь бы
было известно, что оно принадлежит семейству Р.
Использование техники оценок (єп,5п) позволило установить условия асимптотической точности малотрудоемких приближенных алгоритмов для решения ряда труднорешаемых задач дискретной оптимизации. Для простейшей задачи размещения этот подход был реализован в статье Гимади [18].
Для задачи размещения с ограниченными мощностями в работе Piersma [93] демонстрируется асимптотическое поведение точного решения на бесконечности. Алгоритмические вопросы в ней не рассматривались.
Имеется целый ряд интересных работ для задач размещения, полученные в этом направлении [45, 50, 57, 66, 91]. Обзор по основным методам и результатам вероятностного подхода можно найти в работах Кагр [79] и Slominski [102].
Далее представим кратко результаты диссертационной работы, состоящей из введения, трех глав, заключения, списка публикаций автора по теме диссертации и списка используемой литературы.
В первой главе рассматриваются две задачи размещения на сети: задача размещения с ограниченными пропускными способностями коммуникаций и задача размещения с ограниченными мощностями и пропускными способностями коммуникаций. Для первой задачи рассматриваются несколько частных случаев сети, Для задачи на цепи представлен полиномиальный точный алгоритм с временной сложностью Т = 0(7г3) и требуемой памятью П = 0{тг). В случае древовид-
ной сети, представлен псевдополнномиальный алгоритм с оценками Т = 0(пЬ2) и П = 0(nb). где Ь - суммарный спрос по всем пунктам потребления. Для два-древесной сети задача решается псевдополиномиальным алгоритмом за время Т = 0(nbA) при требуемой памяти П = 0(пЬ2). Задачи решаются методом динамического программирования. Вторая задача исследуется на произвольной сети. Помимо входных данных, которые используются в первой задаче, здесь учитываются ограничения на объемы производства. На основе задачи о потоке минимальной стоимости предлагается компактная постановка задачи. Приводится априорный сравнительный анализ некоторых Лагранжевых релаксаций и линейной релаксации задачи. Представлен метод ветвей и границ для рассматриваемой задачи размещения. Предлагается несколько способов вычисления нижней оценки для подмножества решений в методе ветвей и границ, основанных на рассматриваемых релаксациях.
Во второй главе рассматриваются две задачи о наилучшем размещении пунктов производства с ограниченными объемами производства и с ограниченными объемами производства и поставки. Основываясь на идее построения алгоритмов с оценками [25], предлагаются полиномиальные алгоритмы для нахождения приближенных решений этих задач при случайных входных данных. Проводится вероятностный анализ предложенных алгоритмов и обоснование условий на входные данные, при которых алгоритмы являются асимптотически точными.
В третьей главе изучается задача размещения на максимум с огра-
ничейными объемами производства и поставки. Предлагается приближенный алгоритм для решения этой задачи с гарантированной оценкой точности. Полиномиальный жадный алгоритм находит приближенное решение Zg-, для которого верна следующая оценка качества:
(Z* - ZG)/{Z* - ZR) < є'1 « 0.368,
где Z* - оптимум задачи; Zr - тривиальная нижняя оценка для значения целевой функции задачи, е - основание натурального логарифма. Основные результаты диссертации докладывались на Международных конференциях "Дискретный анализ и исследование операций" (Новосибирск, 1998, 2000, 2002), на 11-ой Байкальской школе-семинаре "Методы оптимизации и их приложения"(Иркутск, 1998), на 16-ой Европейской конференции по исследованию операций (Брюссель, 1998), на Международной научной студенческой конференции (Новосибирск, 2000), на 17-ой Европейской конференции по исследованию операций (Будапешт, 2000), на научных семинарах Института математики СО РАН.
Задача размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций
Добавив ограничение Ej =yv ЕрєРг ХЬ 5: d{Xj, і Є N, к постановке задачи, рассмотренной в предыдущей главе, мы получим задачу, исследуемую в этой главе. Но большое число переменных не дает возможности эффективно воспользоваться теорией Лагранфевых релаксаций. Поэтому была предложена другая постановка задачи. Пусть задана сеть G = (Лг, Б1), где множество вершин N соответствует множеству {1,... , п} пунктов потребления, Е - множество ребер сети. В каждом из пунктов потребления можно расположить производство. Для каждого пункта j Є N известны объем спроса боданного пункта потребления. Также указаны затраты на размещение производства д и ограничения на объемы этого производства с/,-, если предприятие располагается в пункте і Є N. Для каждого ребра є Є Е указана стоимость се транспортировки единицы продукта по этому ребру и максимальное количество продукта ае, который может поставляться по этой коммуникации. Требуется указать те пункты производства из iV, при вводе которых в систему, во-первых, полностью бы удовлетворялись спросы всех пунктов потребления с учетом всех ограничений и, во-вторых, сум марные затраты на ввод в действие указанных пунктов производства и обслуживание всех пунктов потребления были бы минимальными. Предлагается рассмотреть постановку задачи, отражающей в себе особенности задачи размещения и специфику задачи о потоке минимальной стоимости, синтезом которых и является исследуемая задача.
Прежде всего построим вспомогательную сеть. Введем две фиктивные вершины s и t. Каждое ребро є Є Е сети G заменяем на две противоположно направленные дуги с теми лее пропускными способностями и той же ценой транспортировки единицы продукта, что у данного ребра е. Пусть А - множество всех таких дуг. Обозначим через Агп и Аоиі множество всех дополнительных дуг, выходящих из s в N и входящих в N в t соответственно. Полагаем транспортные расходы на дугах Агп и Aout равными нулю. Обозначим через A = A U Агп U Aout множество всех дуг построенной сети. Введем переменные величины. Переменная выбора Xj равна единице, если в пункте і Є N размещается производство, и нулю в противном случае. Потоковая переменная /е равна величине потока, который поставляется по дуге є Є А. Задача размещения на сети с ограничениями на объемы производства и на пропускные способности коммуникаций формулируется в следующем виде: найти минимум суммарных затрат по всем переменным Xi, /е при условиях Условие (1.12) регулирует поток из источника s через вершину г: если Х{ = 0, то из s в пункт і ничего не поставляется; если Х{ = 1, то из s в пункт і может поставляться до d{ единиц продукта. Условие (1.13) задает ограничения на пропускные способности дуг А и Aout. Пропускные способности на дугах Aout в условии (1.13) и равенство (1.14) определяют величину спроса для каждого пункта потребления. Равенство (1.15) требует сохранение потока для каждой вершины N. Неравенство (1.16), являясь следствием (1.12) и (1-14), используется для получения хороших Лагранжевых релаксаций. Ограничение (1.17) требует, чтобы потоковые переменные были неотрицательными и переменные назначения лежали в указанных интервалах. Последнее условие используется при исследовании линейной релаксации задачи. Переменные выбора в исходной задаче целочисленные (1.18). Следующая очевидная лемма показывает эквивалентность представленной здесь постановки задачи размещения с постановкой задачи, рассмотренной в первой главе с дополнительным ограничением Лемма 3
Существует такое оптимальное "решение задачи (1.11) — (1.18), чт.о для любой пары противоположно направленных дуг продукт поставляется не более чем по одной дуге. 1.2.2 Сравнение релаксаций Предлагается исследовать соотношения порядка между некоторыми Лагранжевыми релаксациями и линейной релаксацией поставленной задачи. Воспользуемся обозначениями, взятыми из работы [59]. Если некоторое ограничение (5), отличное от (1.18), вводится с Лагранжевым множителем в целевую функцию, то оптимальное значение целевой функции полученной задачи будем обозначать Z($) Если любое ограничение (5), включая (1.18), полностью релаксируется, т. е. выносит ся из ограничений задачи, то значение соответствующей релаксации будем обозначать через Z s\ Пусть (Si),..., (Sfc) ограничения в постановке исходной задачи, (S;) (1.18), і = 1,...,к. Через P((Si),..., {Sk)) обозначим область допустимых значений переменных задачи, задаваемую ограничениями (Si),..., {Sk)- Обозначим через выпуклую оболочку допустимых решений задачи с ограничениями (Si), ..., (5,.), (1.18). Отметим следующее очевидное свойство. Замечание 1 Имеет место следующее соотношение Известно, что Z(s) = niax Zs(A), где Z ){\) - оптимальное значение релаксированной задачи при заданных множителях Лагранжа А. Для нахождения Лагранжевых релаксаций применяют метод субградиентной оптимизации, который на каждой итерации решает ре-лаксированную задачу и по ее оптимальному решению корректирует множители Лагранжа [99]. новых обозначениях исходная задача записывается в виде: Согласно теореме 1 из работы [70], если ограничение (S), отличное от (1.18), заносится в целевую функцию с Лагранжевым множителем, то соответствующую релаксацию можно выразить в следующем виде: (1.18)} \ (5)). Ниже мы сравним между собой исследуемые релаксации. Теорема 4 Для релаксаций задачи (1.11) - (1-18) выполняются следующие соотношения порядка:
Вспомогательные понятия и утверждения
Обозначим через Zn(x), Zn{x ) значения целевой функции задачи, получаемые с помощью алгоритма А и оптимальное решение соответственно, где п - размерность задачи следуя [25]. Будем говорить, что алгоритм А асимптотически точен, если существуют такие последовательности еп — 0, 5п — 0 при п —» со, что Zn(x ) Решение задачи назовем допустимым, если оно удовлетворяет всем ограничениям задачи. Поскольку рассматриваемые алгоритмы не всегда приводят к допустимым решениям, то для задачи размерности /?. определим индикаторную функцию ип: ІУП(Х) 1, если х - допустимое решение, О в противном случае. В виду этого левую часть из (2.6) можно записать в следующем виде: Для дальнейшего нам потребуется рассмотреть некоторые вспомогательные задачи и использовать известные для них результаты.
Первой такой задачей является задача нахождения совершенного паросочения в случайном двудольном графе. Пусть дан двудольный граф Вт р с множеством вершин V = S U Г, \S\ = \Т\ = т. Каждое ребро, соединяющее вершину і Е S с вершиной j Є Т, появляется независимо от других ребер с вероятностью р. В работе [47] приводится алгоритм, который позволяет находить совершенное паросочетание в случайном графе Вт:Р (для краткости обозначим его AV-алгоритмом), и доказана следующая Теорема 5 Для любого а 0 существует такая конст,ант,а /3 О, что если р(т) zm, то с временной сложностью 0(т log т) AV-алгоритм, находит совершенное паросочетание в графе BmjP с вероятностью 1 — 0(т а). Без ограничения общности здесь и далее мы будем рассматривать функцию логарифма по основанию 2. Рассмотрим также следующую транспортную задачу с ограниченными объемами поставок. Пусть дано множество пунктов отправления S и множество пунктов потребления Т, 5 = \Т\ = т. Заданы такие объемы поставки с/г- 1 и объемы спроса bj В(т) y/m/logm, і Е S,j Е Т, что выполняется условие EieS di = T,J ETI J-Пусть d{, bj - целые положительные числа, г Е /, j Е J Пусть с вероятностью р(т) появляется ребро с единичной пропускной способ ностью, соединяющее вершины г Є / и j Є J. В [80] для решения этой задачи предложен так называемый Улучшающий алгоритм (Fineiming Algorithm) и доказана следующая теорема. Теорема б Для любого а 0 существует такая констант.а (3 0, что если р(т) -—m ogm; то Улучшающий алгоритм с временной сложностью 0(т2) находит допустимое решение транспорт.ной за дачи с вероятностью 1 — (J{ — ). Здесь соотношения между а и (3 такие же, как и в теореме 5 для AV-алгорптма. В дальнейшем нам понадобится следующий известный факт из теории вероятностей. Лемма 10 Пусть At 0 — случайные величины и at 0 - произвольные числа, t Є Т. Тогда Рассмотрим задачу размещения с ограниченными объемами производства (2.1)—(2.4). Пусть bj и dj таковы, что 1 bj В(п), DQ(II) di .Di(n), і Є І, J Є J. Опишем следующий приближенный алгоритм для решения этой задачи. АЛГОРИТМ А\. 1. В силу свойства последовательности (gf), і Є /, элементы множе ства І = {1,..., m} упорядочены в следующем порядке: d\ ... dm.
Положим Пусть 1 = {1,... ,гт7о} - множество mo первых элементов множества /. 2. Открыв предприятия в пунктах из /, мы получим транспорт ную задачу по доставке продукта из пунктов множества / в пункты множества J. Пусть пункты спроса из J упорядочены в порядке неубы вания их объемов спроса: Ь\ ... Ьп. Далее пусть d = min{c/;z Є /0} и A = J2jeJ bj - mod Если A 0, то полагается щ = n и переход к шагу 4. В противном случае полагается щ = max{z/ Е?=г/ bj А}. В этом случае в дальней шем рассматриваются две копии пункта потребления по с объемами сиросов Ь По = А - E{bj\nQ j n} и Ь щ = ЪПо - b no. 3. Рассмотрим какое-либо допустимое решение, удовлетворяющее следующим условиям транспортной задачи, полученное, например, ме тодом "северо-западного угла"[29]: 4. Если в пункте 2 оказалось А 0, то алгоритм рассматривает копию пункта потребления пц с объемом спроса bn . Без ограничения общности будем считать, что при замене величины спроса ЬПо на b упорядоченность пунктов потребления не изменяется. Поэтому для упрощения записи на этом и следующем шагах алгоритма сохраняется прежняя нумерация пунктов потребления. Пункты спроса 1,... ,по обслуживаются из пунктов производства с равными мощностями d следующим образом. Пусть / = [-у2-J. Множество пунктов спроса 1,... ,щ разобьем на / + 1 групп: J = {(к — 1)ш0 + 1,..., кто}, 1 к /, J/+i = {/т0 + 1,..., га0}. 5. Рассмотрим транспортные задачи (7, Jj.), в каждой из которых требуется поставить продукт из 1 в Jj., 1 к I + 1. Последователь но решаются задачи (7, Jj.) в порядке возрастания 7 , 1 к I — 1. Найдем решения этих задач, воспользовавшись только коммуникациями единичной стоимости, ведущими из 1 в 4, 1 к I — 1. Для этого применяем AV-алгоритм [47] для нахождения совершенного па-росочетания в двудольных графах (7, Д), 1 к I — 1, полагая, что вероятность появления коммуникации единичной стоимости равна 1/г. Каждый пункт спроса j Є Л-,1 к I — 1, обслуживается в полном объеме из пункта производства по ребру единичной стоимости, входящему в одно из построенных совершенных паросочетанпй. При решении задач (7, J/) и (7, J/+i) продукт поставляем в пункты спроса из J/ U J/+i например так же как и на шаге 3, используя мощности, оставшиеся после решения задач (7, Л.), 1 к I. Пусть хк{-— решения транспортных задач (7, J/.), і Є 7, j Є J к-, 1 к I + 1. 6. Размещая предприятия в пунктах пз 7 и объединяя решения всех транспортных задач, получаем решение ж0, компоненты которого определяются следующим образом:
Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и единичными объемами поставок и условия его аснптотпческоп точности
Перейдем к рассмотрению задачи размещения с ограниченными объемами производства и поставок (2.1)—(2.3), (2.5). Далее будем рассма тривать эту задачу с единичными ограничениями на объемы поставок, т. е. ciij = 1, і Є 7, j Є J. Пусть 1 bj В(п) и с/г- таковы, что Do(n) di Di(n), і Є і, j Є J. Пусть d{ и bj - целые положительные числа і Є і, і Є J. Для решения этой задачи рассмотрим следующий алгоритм. АЛГОРИТМ А2. 1. Считается, что элементы множества І" = {1,..., т} упорядочены в порядке невозрастания их мощностей: d\ ... dm. Пусть Ь = maxjGj bj и mo = min{s 2dj Y j + k} i=\ jeJ Обозначим через / = {1,... ,mo} множество 772Q первых элементов множества /. 2. Определив множество /, мы получили транспортную задачу по доставке продукта из пунктов множества 7 в пункты множества J с ограничениями на объемы поставки.
Предположим, что пункты спроса из J упорядочены в порядке неубывания их объемов спроса: &i ... Ьп. Пусть d = mm{dj\i 6 70} и A = EjeJ bj — m$d. Если А 0, то полагается щ — п + 1 и осуществляется переход к шагу 4 алгоритма. Иначе определяется щ = max{Ar E"=w bj А}. 3. Находится какое-либо допустимое решение, удовлетворяющее следующим условиям транспортной задачи с ограниченными объема ми поставки, полученное, например, адаптированным методом "северо западного угла" [74] с временной сложностью О(топ): 4. Пусть / = [ ] Пункты спроса 1,..., щ — 1 распределяются на / + 1 групп, где Jk = {(к - 1)ш0 + 1,... , кт0}, 1 к /, Ji+i = {lmQ + 1,..., no — 1}. Мощность d каждого предприятия і Є 1 распределяем между / + 1 копиями этого предприятия следующим образом. Пусть Вк = ЕІЄЛ bj, qk = Вк - іщ[Вк/іщ\, Qk = j=1 qs, 1 к / + 1, QQ = 0. Для к = 1,..,/ и і Є 1 полагаем = [Дь/moJ + 1, если і Є {Qk-i mod m0 + 1,..., [Qk - 1) mod 7/?0 + \_Bk/moJ в противном случае. Для к = I + 1 и і Є / полагаем Множество fc-x экземпляров открытых предприятий обозначим через ІІ, где 1 к 1 + 1. 5. Находятся решения транспортных задач (ij?, Д), используя только коммуникации единичной стоимости, ведущие из 1к в Jk, 1 к I.
Применим Улучшающий алгоритм [80] для решения транспортных задач, полагая, что вероятность появления коммуникации единичной стоимости равна 1/?\ Задачу (i/+1, Ji+i) решаем например, так же как и на шаге 3. Пусть х\, - решения транспортных задач (7, Тд.), г Є 7j?, je Л, 1 к 1 + 1. 6. Открыв предприятия в пунктах из 7 и используя решения всех транспортных задач, получаем решение ж0, компоненты которого определяются следующим образом противном случае. Описание алгоритма А закончено. Рисунок 2.2 иллюстрирует алгоритм А . шагов алгоритма порядка п действий. Допустимое решение для шага 3 алгоритма можно построить за 0(пт) действий. Трудоемкость шага 4 порядка (/ + т) действий. На шаге 5 (I — 1) раз используется Улучшающий алгоритм. И шаг 6 имеет трудоемкость 0{п + га). Определим условия, при которых полученное решение почти всегда является допустимым. Справедлива следующая Лемма 12 Пусть т — 0(п1 6), где = const, и 0 0 1, D\(n) = 0(7ie log n), В(п) = O(logn) и В(п) - неубываюгцая функция, г аг. , Л, ,—, в - константа, соответствующая а т : в теореме 6. Тогда Р{іф) = 0} С(;!?У+2і", где С = const. ДОКАЗАТЕЛЬСТВО. ЕСЛИ Ejejbj пцсі (т. е. А 0), то щ п и Согласно выбору no имеем "о Поэтому Отсюда следует возможность обслуживать пункты спроса по,...,п способом, указанным на шаге 3. Дальнейшие рассуждения справедливы и при А 0. Согласно выбору По получаем Это означает, что суммарной мощности mod будет достаточно для обслуживания пунктов потребления 1,...,по — 1. Теперь убедимся в том, что мощность d каждого предприятия можно разделить способом, указанным на шаге 4 алгоритма Ач. Во-первых, при каждом к = 1,...,1 т. е. каждая задача (/, J&), 1 к /, является сбалансированной. Во-вторых, при каждом і Є 1
Субмодулярные функции и жадный алгоритм
В этом разделе, следуя работе [89], дадим определение субмодулярной функции и напомним некоторые ее свойства. Далее опишем жадный алгоритм, отыскивающий приближенное решение задачи, целевая функция которой обладает свойством субмодулярности. И, наконец, представим гарантированную оценку точности решения, получаемого этим алгоритмом. Определение 1 Пусть I-конечное множество. Вегцест.венная функция Z на множестве подмножеств I называется субмодулярной, если выполняется следующее условие: Следующие три утверждения получены в [89]. Лемма 13 Пусть с/г-, і Є I, произвольные вещественные числа. Тогда линейная функция z(S) = Егеб" -, S С I, является субмодулярной. Лемма 14 Положительная линейная комбинация субмодулярных функ-ций является субмодулярной функцией. Лемма 15 Пусть дана субмодулярная неубывающая функция v на мно-жест.ве подмножеств D и семейст.во подмножеств {);},? Є I, множества D. Тогда функция z(S) = v(UjesDi) являет.ся субмодулярной функцией на множестве подмножеств I. Пусть Z(S) - субмодулярная функция. Рассмотрим задачу: Обозначим pi(S) = Z(S U {г}) — Z(S). Для отыскания допустимого решения задачи (3.6) в работе [89] предложен следующий жадный алгоритм А.Инициализация. Пусть S0 = 0, / = /, t = 1. Итерация t. Найти i(t) Є P l такое, чтобы /9 )( -1) = maxie;(-i piiS -1). Пусть pt_x = p S1-1). Шаг 1. Если pt-i 0, то алгоритм заканчивает работу с множеством Sk\ k = t - 1 к. Если pt-i 0, то пусть Sl = S 1 U {г ВД}, Iі — р 1 \ {/(f)} и продолжить работу алгоритма. Шаг 2. Если t = /с, то алгоритм заканчивает работу с множеством Sk\ к = к. Иначе = + 1. Имеем ZQ = Z(S ) - приближенное решение, полученное алгоритмом. Пусть Z - оптимальное значение задачи (3.6). Обозначим через С (О), где О 0, класс субмодулярных функций, удовлетворяющих условию Pi(S) -0, VS С і",г Є /\ S. Пусть Z(0) 0. Из работы [89] следует
Теорема 9 Жадный алгоритм А в задаче (3.6) при условии, что Z(S) Є С (О), приводит, к следующему неравенству где е - основание натурального логарифма. Заметим, что в нашей задаче мы полагаем к = /, т. е. ограничение 5 к в задаче (З.б) несущественно, и шаг 2 алгоритма А опускается. Пусть G = maxjg/ jf + 1. Воспользуемся методом штрафных функций для построения приближенного решения. Рассмотрим следующую задачу Целевая функция (3.8) получается путем ввода штрафной функции Ejej(Sfe/ fj —bj)G в целевую функцию (3.1) исходной задачи и проведения соответствующих преобразований. Заметим, что в ограничении (3.9) имеем нестрогое неравенство. Представленная задача используется для отыскания допустимого решения задачи (3.1) - (3.5) с гарантированной оценкой точности получаемого решения. Следующие вспомогательные утверждения устанавливают связь между задачами (3.1) - (3.5) и (3.7) - (3.11). Лемма 16 Задачи (3.1) - (3.5) и (3.7) - (3.11) эквивалентны. ДОКАЗАТЕЛЬСТВО. Введение штрафной функции гарантирует нам выполнение равенства в неравенстве (3.9) для всех J G/B оптимальном решении задачи (3.7) - (3.11). Допустим, что это не так. Пусть Z значение оптимального решения и пусть для некоторых j Є J выполняется строгое неравенство в условии (3.9). Тогда рассмотрим такое допустимое решение со значением Zj\, что в некоторый такой пункт потребления j поставляется еще одна единица продукта из некоторого предприятия г, которое можно открыть, если г S. Имеем, что ZA Z , так как ZA — Z gij — g + G 0. Получили решение со значением целевой функции, большим Z . Противоречие. Таким образом, оптимальное решение задачи (3.7) - (3.11) является оптимальным решением задачи (3.1) - (3.5). Обратное утверждение очевидно. Лемма доказана. Лемма 17 Допустимое решение задачи (3.7) - (3.11), полученное жадным алгоритмом А, является допустимым решением задачи (3.1) -(3.5). ДОКАЗАТЕЛЬСТВО. Найдя допустимое решение задачи (3.7) - (3.11) жадным алгоритмом А, будем иметь равенство в неравенстве (3.9) для всех j Є J.
Допустим, что это не так. Пусть ZA значение допустимого решения, полученного жадным алгоритмом А, и пусть для некоторых j Є J выполняется строгое неравенство в условии (3.9). Тогда найдется такое і Є I, что Pi(S) g — g + G 0 для некоторого j Є J. Получили противоречие с условием остановки алгоритма А на шаге 1. Таким образом, алгоритм А получает решение, удовлетворяющее условиям (3.3) - (3.5). Лемма доказана. Поскольку значение целевой функции представленной задачи может быть как положительным, так и отрицательным, то, следуя работе [55], будем использовать оценку относительного уклонения в виде (Z — Zc)/(Z — ZR), где Z и ZQ - оптимальное решение и допустимое решение задачи, получаемые предложенным алгоритмом А, соответственно; ZR - гарантированная нижняя оценка для решения. В данной
