Задачи размещения с ограничениями на объемы производства и пропускные способности коммуникаций тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Вознюк, Иван Петрович

• Вознюк, Иван Петрович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Вознюк, Иван Петрович

Введение

1 Задачи размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций

1.1 Задача размещения на сети с ограниченными пропускными способностями коммуникаций.

1.1.1 Постановка задачи.

1.1.2 Задача размещения на древовидной сети.

1.1.3 Задача размещения на два-дереве.

1.2 Задача размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций

1.2.1 Постановка задачи.

1.2.2 Сравнение релаксаций.

1.2.3 Вычисление релаксаций.

1.2.4 Реализация метода ветвей и границ.

2 Приближенные алгоритмы для решения задач размещения с ограниченными объемами производства и поставок и обоснование условий их асимптотической точности

2.1 Постановки задач.

2.2 Вспомогательные понятия и утверждения.

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

2.4 Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и единичными объемами поставок и условия его асиптотпческой точности

2.5 Замечания

3 Приближенный алгоритм для задачи размещения на максимум с ограниченными объемами производства и поставок

3.1 Постановка задачи.

3.2 Субмодулярные функции и жадный алгоритм.

3.3 Эквивалентная задача

3.4 Оценки качества алгоритма.

Введение диссертации (часть автореферата) на тему «Задачи размещения с ограничениями на объемы производства и пропускные способности коммуникаций»

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

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

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

Среди дискретных задач оптимизации принято выделять класс задач Р, разрешимых за полиномиальное время (в зависимости от длины входа) и класс NP- трудных задач, для которых построение полиномиальных алгоритмов проблематично (если только NP не равно Р). К сожалению, многие естественные и интересные задачи дискретной оптимизации являются NP-трудными. Показано, что если найдется быстрый алгоритм (число действий которого зависит полиномиально от размерности задачи) хотя бы для одной NP-трудной проблемы, то такие алгоритмы можно будет построить для всех задач из этого класса. Одной из самых фундаментальных проблем современной математики является вопрос: существует ли такой быстрый алгоритм для NP-трудных задач? Многие исследователи склоняются к отрицательному ответу на этот вопрос.

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

Одной из самых известных задач в исследовании операций является дискретная задача размещения. Имеется большое число работ, посвященных данной проблеме. Mirchandani и Francis [87] выделяют несколько основных классов задач размещения: простейшая задача размещения, задача размещения с ограниченными объемами производства, задача о р-медиане, задача о р-центре. Простейшая задача размещения, видимо, самая известная и изученная задача размещения. Ее можно рассматривать как базовую для ряда других задач размещения. Так, задача размещения с ограниченными объемами производства получается после добавления ограничений на мощности производства.

Помимо NP-трудных задач в исследовании операций имеются задачи, для которых удалось построить быстрые (полиномиальные) алгоритмы. Таковой, например, является задача о потоке минимальной стоимости [40, 90]. Процессы, которые моделируются этой проблемой, очень актуальны во многих сферах человеческой деятельности. Например, упомянутые потоки можно рассматривать как транспортные потоки, либо как потоки финансовых средств.

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

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

Можно заметить, что известна более общая многопродуктовая постановка задачи, к которой сводится в однопродуктовом случае задача размещения на сети с ограниченными пропускными способностями коммуникаций. Это задача конструирования сети с ограничениями на пропускные способности коммуникаций. Как признаются Holmberg, Yuan [77] в чьей статье рассматривалась эта проблема, получено очень мало результатов для этой задачи. Сами они смогли указать только один препринт [69]. В этих двух работах приводится апостериорный анализ численных экспериментов для неявного перебора с использованием Лагранжевых релаксаций. Судя по этим двум публикациям, сколько-нибудь других существенных результатов для этой задачи не получено.

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

Пусть даны множество I = {1,. ,ш} возможных пунктов размещения предприятий и множество пунктов потребления J = {1,., п}. В некоторых постановках задач множества I и J могут совпадать. Пусть заданы начальные затраты по размещению предприятия д®, г Е и объемы потребления продукта bj,j Е J. Указаны затраты gij по доставке единицы продукта из i Е I в j Е J. Требуется указать те предприятия из /, при вводе которых в систему, во-первых, полностью бы удовлетворялись спросы всех пунктов потребления, и, во-вторых, затраты, связанные с обслуживанием всех пунктов потребления с учетом размещения предприятий были бы минимальными.

Простейшая задача размещения (ПЗР) в комбинаторной постановке формулируется в следующем виде:

Запишем ее формулировку в виде задачи линейного целочисленного программирования. Требуется найти минимум функционала:

Е (f!xi + Е Е gijXij, iei iei jeJ по всем переменным X{j при условиях

Е xij = bh J е -Л iei

О < х^ < bjXj. i E I, j E J, х{ E {0,1}, i E I.

Здесь переменные Xi - это переменные выбора: если мы открываем предприятие г, то Х{ = 1, в противном случае Х{ — 0. Переменные х^ - это переменные назначения, равные количеству единиц продукта, поставляемых из г Е / в j Е J.

Эта задача относится к числу NP-трудных проблем, так как к ней сводится NP-трудная задача о минимальном покрытии конечного множества системой конечных подмножеств [30].

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

У у ^ 1 Е I• jeJ

Перечислим известные результаты для этих задач по упомянутым выше четырем направлениям исследований.

Для ПЗР на сетях специального вида имеются ряд работ. Для случая, когда сетью является дерево, сначало Трубин [38] построил, а затем Kolen [82] переоткрыл алгоритм с трудоемкостью 0(п3), где п - размерность задачи. Гимадн [16] и позже Billionet, Costa [51] удалось улучшить оценки трудоемкости алгоритма, решая эту задачу за время 0(пт) и 0(п2) соответственно, где т - число возможных пунктов размещения производства. Самый последний результат получен Shah, Farach-Colton [97]. Они предложили алгоритм с трудоемкостью O(nlogn). Агеевым [1] была решена задача на внешнепланарном графе за время 0(n3m). Hassin и Tamir [73] представили алгоритм для последовательно-параллельной сети с временной сложностью О (г?4). Позже для этого же случая задачи Агеевым [2] был построен алгоритм с трудоемкостью 0(пга3).

Удалось также построить полиномиальные алгоритмы для ПЗР при следующих ограничениях, накладываемых на матрицу расстояний: для односвязной матрицы в монографии Береснева, Гимади, Дементьева [12]; для двусвязной матрицы в работе Береснева [10]; для квазивыпуклой, квазивогнутой и обобщенно-квазивыпуклой матрицы в статье Гимади [20]. Для задачи с матрицами, порожденными частичными q-деревьями, Агеевым [42] предложен полиномиальный алгоритм с трудоемкостью 0(nmq+l). Бересневым [10] установлена эквивалентность ПЗР и задачи минимизации булевых полиномов. Это позволило выделить новые классы эффективно решаемых задач [4, 5, 10].

В то же самое время для некоторых классов задач имеются и отрицательные результаты: Агеевым в работе [43] было показано, что ПЗР является ЛгР-трудной, даже если матрица (gij) порождена расстояниями на плоской решетке.

Можно привести еще целый ряд работ, в которых ПЗР рассматривалась как с точки зрения полиномиально разрешимых подклассов так и с точки зрения других видов анализа 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-трудных задач можно выделить те ограничения, после удаления которых задача становится полиномиально разрешимой. Было предложено заносить эти ограничения в целевую функцию с некоторыми коэффициентами, так называемыми множителями Jla-гранжа. Решение релаксированной таким образом задачи дает оценку снизу для целевой функции исходной задачи на минимум. Помимо этого, решения релаксированной задачи можно использовать в качестве начальной точки при построении приближенного решения исходной задачи с апостериорной оценкой точности.

В работе 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]. Пусть имеется приближенный алгоритм А для решения оптимизационной задачи. Пусть I - индивидуальная оптимизационная задача, Za(I) ~ значение приближенного решения, полученного алгоритмом A, Z*(/) - точное значение задачи. Есть несколько способов измерения точности приближенного алгоритма. Наиболее распространенной и используемой величиной, характеризующей точность приближенного алгоритма, является так называемая относительная точность, под которой понимается функция та{1) = Za(I)/Z*(I). Априорной оценкой относительной точности приближенного алгоритма А решения оптимизационной задачи на максимум (минимум) является величина Ra такая, что для любой индивидуальной задачи I выполняется неравенство тА{1) > Ra (тА(1) < Ra).

Такую оценку Яд, не зависящую от размерности индивидуальной задачи /, называют константной.

Для общего случая простейшей задачи размещения в работе Hoch-baum [75] построен полиномиальный жадный алгоритм, отыскивающий допустимое решение задачи, отличающиеся от точного не более чем в In п раз, где п - число пунктов потребления. При этом использовалось сведение ПЗР к задаче о покрытии конечного множества системой конечных подмножеств, для которой Clivatal [54] построил приближенный жадный алгоритм.

Для задачи о покрытии Feige [64] показал, что для любого г > О нельзя построить приближенный быстрый алгоритм с точностью (1 — s) Inn при условии, что для NP-трудных задач не существует быстрых точных алгоритмов. Поскольку задача о покрытии сводится к простейшей задачи размещения, то этот отрицательный результат переносится и на задачу размещения. Таким образом, маловероятно, что для простейшей задачи размещения в общем случае существует приближенный алгоритм, с оценкой точности лучше, чем Inn.

В метрической задаче размещения транспортные затраты удовлетворяют неравенству треугольника: для любых i,j,k Е I U J выполняется неравенство gij + gjk > 9ik■ Для этого случая 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 раза. В работах Korupolu, Plaxton, Raj агат an [83] и Chudak, Williamson [53] предлагаются алгоритмы, которые находят приближенные решения этой задачи с точностью (8 + б) и (6 + б), соответственно, для любого б > 0 без увеличения мощности предприятий. Обзор по этой задаче также представлен в докладе Агеева [3].

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

Здесь величина д® это штраф за размещение предприятия в пункте г, а величины дц интерпретируются, как прибыль, получаемая при обслуживания потребителя j Е J предприятием, размещенным в пункте г £ I. Задача сводится в нахождении такого подмножества S пунктов размещения предприятий, чтобы прибыль, получаемая при обслуживании всех пунктов потребления с учетом штрафов, была бы максимальной.

Простейшая задача размещения на минимум затрат и простейшая задача размещения на максимум затрат эквивалентны, т. е. по точному решению одной задачи можно построить точное решение другой задачи, и наоборот. Однако методы построения приближенных решений этих задач отличаются. Историческую справку и обзор по этим задачам можно найти в сборнике Cornuejols, Nemhauser и Wolsey [58].

Поскольку целевая функция простейшей задачи размещения на максимум может принимать как положительные, так и отрицательные значения, то возникают трудности с определением оценки относительной точности приближенного алгоритма. В связи с этим предлагается использовать следующую оценку для измерения относительного уклонения от точного со сдвигом в виде величины (Z* — Zq)/{Z* — Zr), где Z* и Zq - оптимальное решение и допустимое решение задачи, полученное предложенным алгоритмом, соответственно; Zr - тривиальная нижняя оценка для значения функции Z(S). Cornuejols, Fisher и Nemhauser [55] доказали, что для простейшей задачи размещения на максимум с дополнительным ограничением на количество открытых предприятий простой жадный алгоритм находит допустимое решение Z(y, для которого (Z* — Zg)/{Z* — Zr) < e~1 « 0.368, где е ~ основание натурального логарифма.

Nemhauser, Wolsey и Fisher [89] обобщили результаты [55] для произвольной задачи, целевая функция которой является субмодулярной. Целый ряд интересных результатов удалось получить Wolsey [ЮЗ] для нескольких задач размещения, в том числе и с ограниченными мощностями предприятий. Свириденко [35] удалось обобщить понятие субмодулярной функции и для задач размещения с дополнительными ограничениями построены приближенные алгоритмы с гарантированными оценками точности. Агеев и Свириденко в статье [44] улучшили результат [55] и предложили алгоритм с оценкой точности (Z* - ZG)j{Z* - ZR)< 3 - 2л/2 « 0.172.

Имеется еще одно важное направление в исследовании NP-трудных задач — это вероятностный анализ поведения алгоритмов. Здесь предполагается, что на множестве индивидуальных задач задано некоторое вероятностное распределение и оценивается математическое ожидание погрешности алгоритма на этом распределении. Вероятностное поведение некоторых данных в той или иной модели очень естественно для многих практических задач. Так, спрос на хлебобулочные изделия может иметь вероятностный характер.

Здесь мы изложим идею построения алгоритма с оценками (tn,Sn), описанную в работе Гимади, Глебов, Перепелица [25]. А впервые этот метод был предложен Гимади, Перепелица [26]. Этот подход будет использован при получении результатов одной из глав диссертации.

Пусть К - некоторый класс задач. Через Z(S) обозначим оптимальное значение целевой функции для задачи S Е К. Будем считать, что рассматриваются задачи на минимум и Z(S) > 0 для всех S £ К.

Рассмотрим теперь некоторый алгоритм А, который может быть применен к любой задаче S класса К, так что результатом этого применения является допустимое решение задачи S со значением целевой функции Za{S). При этом, вообще говоря, не исключается, что применение алгоритма А к некоторым задачам из класса К может оказаться безрезультатным.

Если получено допустимое решение задачи то качество решения данной задачи может быть оценено через величину

ZA(S) - Z(S) Z(S)

- относительное уклонение от оптимума целевой функции, полученного в результате применения алгоритма А.

Задаваясь некоторым £ > 0, можно определить множество задач Ке S Q (z K\ZA{S) ~ Z(S) < для которых относительная погрешность получаемых алгоритмом А решений не превышает заданной величины е. Набор множеств К\ для разных г > 0 мог бы служить достаточно полной характеристикой алгоритма А с точки зрения точности получаемых решений. Это, в свою очередь, позволяло бы сравнивать разные алгоритмы по указанным наборам множеств. Но трудность такого подхода к сравнению алгоритмов заключается в том, что практически мы, как правило, не имеем возможности получить простое описание множеств КА в явном виде.

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

Пусть заданы класс задач К п некоторое семейство Р вероятностных мер, определенных на классе К. Говорят, что алгоритм, А имеет, тип (t,^) относительно Р, если для всех р £ Р.

В этом случае также говорят, что алгоритм А имеет оценки (е, д) относительно Р .

Алгоритм А называется асимптотически точным на классе задач К, если существуют такие последовательности (&„), (5п), что для любого п алгоритм А удовлетворяет оценкам (sn,Sn) на подмножестве Кп С К задач размерности п и при этом еп —> 0, 5п —» 0 при п —» оо.

Заметим, что алгоритм будет точным в том и только в том случае, если он имеет оценки (0,0) относительно любого семейства вероятностных мер.

Нетрудно представить ситуацию, в которой величины £ и 6 действительно могут трактоваться как оценки вероятностного характера для относительных погрешностей получаемых с помощью алгоритма А решений. В самом деле, пусть алгоритм А имеет тип (е,5) относительно Р и он используется для решения задач класса К, которые поступают из некоторого случайного источника, имеющего распределение р Е Р. Тогда можно быть уверенным, что вероятность не получить алгоритмом А решение с приемлемой относительной погрешностью - не более (5. При этом само распределение Р мы можем и не знать, лишь бы было известно, что оно принадлежит семейству Р.

Использование техники оценок (£п,5п) позволило установить условия асимптотической точности малотрудоемких приближенных алгоритмов для решения ряда труднорешаемых задач дискретной оптимизации. Для простейшей задачи размещения этот подход был реализован в статье Гимади [18].

Для задачи размещения с ограниченными мощностями в работе Piersma [93] демонстрируется асимптотическое поведение точного решения на бесконечности. Алгоритмические вопросы в ней не рассматривались.

Имеется целый ряд интересных работ для задач размещения, полученные в этом направлении [45, 50, 57, 66, 91]. Обзор по основным методам и результатам вероятностного подхода можно найти в работах Кагр [79] и Slominski [102].

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

В первой главе рассматриваются две задачи размещения на сети: задача размещения с ограниченными пропускными способностями коммуникаций и задача размещения с ограниченными мощностями и пропускными способностями коммуникаций. Для первой задачи рассматриваются несколько частных случаев сети, Для задачи на цепи представлен полиномиальный точный алгоритм с временной сложностью Т = 0(п3) и требуемой памятью П = 0{п). В случае древовидной сети, представлен псевдополнномиальный алгоритм с оценками Т = О(nb2) и П = 0(nb). где Ь - суммарный спрос по всем пунктам потребления. Для два-древесной сети задача решается псевдополиномиальным алгоритмом за время Т = 0(пЪА) при требуемой памяти П = 0(пЬ2). Задачи решаются методом динамического программирования. Вторая задача исследуется на произвольной сети. Помимо входных данных, которые используются в первой задаче, здесь учитываются ограничения на объемы производства. На основе задачи о потоке минимальной стоимости предлагается компактная постановка задачи. Приводится априорный сравнительный анализ некоторых Лагранжевых релаксаций и линейной релаксации задачи. Представлен метод ветвей и границ для рассматриваемой задачи размещения. Предлагается несколько способов вычисления нижней оценки для подмножества решений в методе ветвей и границ, основанных на рассматриваемых релаксациях.

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

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

Z* - ZG)/{Z* - ZR) < е'1 « 0.368, где Z* - оптимум задачи; Zr - тривиальная нижняя оценка для значения целевой функции задачи, е - основание натурального логарифма.

Основные результаты диссертации докладывались на Международных конференциях "Дискретный анализ и исследование операций" (Новосибирск, 1998, 2000, 2002), на 11-ой Байкальской школе-семинаре "Методы оптимизации и их приложения"(Иркутск, 1998), на 16-ой Европейской конференции по исследованию операций (Брюссель, 1998), на Международной научной студенческой конференции (Новосибирск, 2000), на 17-ой Европейской конференции по исследованию операций (Будапешт, 2000), на научных семинарах Института математики СО РАН.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Вознюк, Иван Петрович

Заключение

Сформулируем основные результаты проведенных исследований.

1. Рассмотрены две задачи размещения на сети: задача размещения с ограниченными пропускными способностями коммуникаций и задача размещения с ограниченными мощностями и пропускными способностями коммуникаций. Для первой задачи рассматриваются несколько частных случаев сети. Для задачи на цепи представлен полиномиальный алгоритм с временной сложностью Т = 0(п3) и требуемой памятью П = 0(п). В случае древовидной сети, представлен псевдополиномиальный алгоритм с оценками Т = 0(пЪ2) и П = 0(пЬ), где Ъ - суммарный спрос по всем пунктам потребления. Для два-древесной сети задача решается псевдополиномиальным алгоритмом за время Т = 0{пЬА) при требуемой памяти П = 0{пЬ2). Задачи решаются с использованием метода динамического программирования. Вторая задача исследуется на произвольной сети. Помимо входных данных, которые используются в первой задаче, здесь учитываются также ограничения на объемы производства. На основе задачи о потоке минимальной стоимости предлагается компактная постановка задачи. Приводится априорный сравнительный анализ некоторых Лагранжевых релаксаций и линейной релаксации задачи. Представлен метод ветвей и границ для рассматриваемой задачи размещения. Предлагается несколько способов вычисления нижней оценки для подмножества решений в методе ветвей и границ, основанных на рассматриваемых релаксациях.

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

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

Z* - ZG)/(Z* - ZR) < е-1 и 0.368, где Z* - оптимум задачи; Zr - тривиальная нижняя оценка для значения целевой функции задачи, е - основание натурального логарифма,

Список публикаций автора по теме диссертации

1. Вознюк И. П. Задача размещения на сети с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций, Сер. 2, 1999, Т. 6, № 1, С. 3-11.

2. Вознюк И. П. Задача размегцения пунктов производства на два-дереве с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций, Сер. 2, 2000, Т. 7, № 1, С. 3-8.

3. Voznyuk I. Lagrangian relaxations for the edge-capacity facility location problem// Abstracts of the "Symposium on Operations Research", 1999, Magdeburg, September 1-3, P. 112.

4. Вознюк И. П. Аппроксимационный алгоритм для задачи размещения на максимум с ограниченными объемами производства и поставок // Известия ВУЗов, Математика, 2000, № 12, С. 15-21.

5. Вознюк И. П., Гимади Э. X., Филатов М. Ю. Асимптотически т,очный алгоритм для решения задачи размещения с ограниченными объемами производства // Дискретный анализ и нсследование операции, Сер. 2, 2001, Т. 8, № 2, С. 3-16.

6. Вознюк И. П. Асимптотически точный алгоритм для решения задачи размещения с ограниченными объемами производства и поставки j j Препринт института математики № 92, 2002, С. 14.

Благодарности

В заключение хочу выразить искреннюю признательность моим родителям Вознюк Петру Сергеевичу и Антониде Алексеевне за их безграничную родительскую любовь и веру в мои способности. Выражаю искреннюю благодарность моему научному руководителю Э. X. Ги-мадп за предложенную тему исследований и всестороннюю поддержку на протяжении всего времени работы над диссертацией. Я благодарен сотрудникам отдела теоретической киберненики института математики СО РАН им. С. JI. Соболева, чьи критические замечания, советы, поддержка помогли мне получить эти результаты: А. А. Агееву, Н. И. Глебову, Е. Н. Гончарову, Ю. А. Кочетову, М. Г. Пащенко, М. И. Свн-риденко, покойному А. И. Сердюкову, Ю. В. Шамардину.

Список литературы диссертационного исследования кандидат физико-математических наук Вознюк, Иван Петрович, 2003 год

1. Агеев А. А. Графы, матрицы и простейшая задача размещения // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1989, Вып. 29, С. 3-11.

2. Агеев А. А. Полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сет,и // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1990, Вып. 30, С. 3-16.

3. Агеев А. А. Алгоритмы с константными оценками точности для метрических задач размещения: обзор результатов // Тезисы докладов на международную конференцию "Дискретный анализ и исследование операций", Новосибирск, 2002, С. 11-16.

4. Агеев А. А., Береснев В. J1. Алгоритмы минимизации для некоторых классов полиномов от булевых переменных, // Модели и методы оптимизации. Труды ИМ СО АН СССР, 1988, Вып. 10, С. 5-17.

5. Белинская И. Г. Об одном классе полиномов от булевых переменных // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1981, Вып. 21, С. 6-12.

6. Береснев В. JI. Об одном классе задач оптимизации параметров однородной технической системы // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1971, Вып. 9, С. 65-74.

7. Береснев В. JT. Об одной задаче математической теории стандартизации // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1973, Вып. 11, С. 43-54.

8. Береснев В. J1. Алгоритм неявного перебора для задачи типа размещения и стандартизации // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1974, Вып. 12, С. 24-34.

9. Береснев В. JI. Об одной задаче математической теории стандартизации // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1974, Вып. 13, С. 3-9.

10. Береснев В. Л. Алгоритмы минимизации полиномов от, булевых переменных // Проблемы кибернетики, 1979, № 36, С. 225— 246.

11. Береснев В. Л. Эффективный алгоритм для задачи размещения производства с вполне уравновешенной матрицей // Дискретный анализ и исследование операций, Сер. 1, 1998, Т. 5, С. 20-31.

12. Береснев В. Д., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

13. Боровков А. А. Теория вероятностей. 2-е изд. М.: Наука, 1986.

14. Вознюк И. П. Задача размещения на сети с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций, Сер. 2, 1999, Т. 6, № 1, С. 3-11.

15. Гимади Э. X. Задача размещения на цепи с центрально-связными областями обслуживания // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1984, Вып. 25, С. 38-47.

16. Гимади Э. X. Обоснование априорных оценок качества приближенного решения задачи стандартизации // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1987, Вып. 27, С. 12-27.

17. Гимади Э. X. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и Методы Оптимизации, Труды ИМ СО АН СССР, 1988, № 10, С. 89-115.

18. Гимади Э. X. Задача стандартизации с данным,и произвольного знака и связными, квазивыпуклыми и почт,и квазивыпуклыми матрицами // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1990, Вып. 30, С. 12-23.

19. Гимади Э. X. Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи // Дискретный анализ и исследование операций, Сер. 2, 1995, Т. 4, С. 13-31.

20. Гимади Э. X., Дементьев В. Т. О методах решения некоторых задач оптимизации параметрических рядов // Стандарты и качество, 1971, № 12, С. 10-12.

21. Гимади Э. X., Дементьев В. Т. Некоторые задачи выбора оптимальных параметрических рядов и методы их решения (задачи стандартизации) // Проблемы кибернетики, 1973, № 27, С. 19-32.

22. Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики, 1975, № 31, С. 35-42.

23. Гимади Э. X., Перепелица В. А. К задаче нахождения минимального гамилътонового контура на графе со взвешенными дугами // Дискретный анализ, Новосибирск, Ин-т математики СО АН СССР, 1969, Вып. 15, С. 57-65.

24. Гимадутдинов (Гимади) Э. X. О свойствах решений одной задачи оптимального размещения точек на отрезке // Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1969, Вып. 2, С. 77-91.

25. Гришухин В. П. Полиномиальностъ в простейшей задаче размещения // 1989, препринт ЦЭМИ.

26. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.

27. Гэри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982.

28. Дейвид Г. Д. Порядковые статистики. М.: Наука, 1979.

29. Дементьев В. Т. Задача выбора типажа оборудования // Методы управления большими системами, Иркутск: СЭИ СО АН СССР, 1970, С. 60-62.

30. Кравцов М. К., Крачковский А. П. Асимптотическая оптимальность плана транспортной задачи, построенного методом, минимального элемент,а // Кибернетика и системный анализ, 1999, №1, С. 144-151.

31. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.

32. Свириденко М. И. О точности решений жадными, алгоритмами задач размещения на максимум // Дискретный анализ и исследование операций, Сер. 1, 1997, Т. 4, № 3, С. 35-48.

33. Свириденко М. И. Алгоритмы с оценками для дискрет,ных задач размещения: дис. канд. физ.-мат. наук. 1998, Новосибирск.

34. Седов С. В., Лебедев С. С. Решение одной задачи размещения с использованием узловых вектюров разрешающих множителей // Экономика и математические методы, 1999, Т. 35, № 3, С. 116121.

35. Трубин В. А. Эффективный алгоритм решения задачи размещения на сет,и в форме дерева // Доклады Академии наук СССР, 1976, Т. 231, № 3, С. 547-550.

36. Трубин В. А. Два класса задач размещения на древовидных сетях // Кибернетика, 1983, № 4, С. 84-87.

37. Форд J1. Р., Фалкерсон Ф. Р. Потоки в сетях. М.: Мир, 1963.

38. Черенин В. П., Хачатуров В. Р. Решение методом последовательных расчетов одного класса задач о размещении производства II Экономика и математические методы, 1965, № 2, С. 279-290.

39. Ageev A. A. A criterion of polynomial-time solvability for the network location problem, // Integer Programming and Combinatorial Optimization, Carnegie-Mellon University, 1992, P. 237-245.

40. Ageev A. A. Complexity of the network median problem, on planar grids II Siberian Advances in Mathematics, 1995, N 5, P. 1-9.

41. Ageev A. A., Sviridenko M. I. An 0.828-approximation algorithm, for the uncapacitat.ed facility location problem // Discrete Applied Mathematics, 1999, N 93, P. 149-156.

42. Aim S., Cooper C., Cornuejols G. and Frieze A. M.

43. Probabilistic analysis of a relaxation for the k-median problem // Mathematics of Operation Research, 1988, N 13, P. 1-31.

44. Akinc U., Khumawala В. M. An efficient branch, and, bound algorithm for the capacitated warehouse location problem, // Management Science, 1977, N 23, P. 585-594.

45. Angluin D., Valiant L. G. Fast probabilistic algorithm, for Hamiltonian circuits and matchings // Journal of Computing and System Science, 1979, V. 19, N 2, P. 155-193.

46. Arora S. Probabilistic checking of proofs and the hardness of approximation problems // 1994, PhD thesis, U.C. Berkeley.

47. Arora S., Lund C. Hardness of approximation // In the book Approximation Algorithms for NP-hard Problems, 199G, PWS Publishing.

48. Bartal Y. Probabilistic approximation of metric spaces and its algorithms applications //In Proceedings of the 37th IEE FOCS, 1996, P. 184-193.

49. Billionet A., Costa M.-C. Solving the uncapacitated plant location, problem on trees // Discrete Applied Mathematics, 1994, V. 49, N 1-3, P. 51-59.

50. Chudak F. Improved approximation algorithms for uncapacitated facility location // In Proceedings of the 6th IPCO Conference, 1998, P. 180-194.

51. Cliudak F., Williamson D. Improved approximation algorithms for capacitated facility location problems //In Proceedings of the 7th IPCO Conference, 1999, P. 99-113.

52. Chvatal V. A greedy heuristic for the set-covering problem // Mathematics of Operations Research, 1979, N 4, P. 233-235.

53. Cornuejols G., Fisher M. L., Nemliauser G. L. Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms // Management Science, 1977, V. 23, N 8, P. 789-810.

54. Cornuejols G., Fisher M. L., Nemhauser G. L. On theuncapacitated location problem, // Annals of Discrete Mathematics, 1977, N 1, P. 163-177.

55. Cornuejols G., Nemhauser G. L., Wolsey L. A. Worst case and probabilistic analysis of algorithms for location problems // Operations Research, 1980, N 28, P. 847-858.

56. Cornuejols G., Sridliaran R., Thizy J. M. Comparison, of heuristics and relaxations for the capacitated plant, location, problem // European Journal of Operational Research, 1991, N 50, P. 280-297.

57. Davis P. S., Ray T. L. Branch and bound algorithm for the capacitated facilities location problem, // Naval Research Logistics Quarterly, 1969, N 16, P. 331-343.

58. Efroymson M., Ray T. A branch and bound algorithm, for plant location // Operations Research, 1966, V. 14, N 3, P. 361-368.

59. Erlenkotter D. A dual-based approach for uncapacitated facility location // Operation Research, 1978, N 26, P. 992-1009.

60. Everett H. Generalized Lagrange multiplier method for solving problems of optimum allocation of resources // Operations Research, 1963, N 11, P. 399-417.

61. Feige U. A threshold of Inn for approximating set-cover // In Proceedings of the 28th ACM Symposium on Theory of Computing, 1996, P. 314-318.

62. Fisher M. L. Worst-case analysis of algorithms // Management Science, 1980, N 26, P. 1-18.

63. Fisher M. L., Hochbaum D. Probabilistic analysis of the planar К-median problem // Mathematics of Operation Research, 1980, N 5, P. 27-34.

64. Fisher M. L., Nortrup W. D., Shapiro J. F. Using duality to solve discrete optimization problems: Theory and Computational experience // Mathematical Programming Study, 1975, N 3, P. 5694.

65. Fisher M. L., Shapiro J. F. Constructive duality in integer programming// SIAM J. Applied Mathematics, 1974, N 27, P. 3152.

66. Gendron В., Cranio T. G. Relaxations for multicommodity capacitated network desigh problem, j j Research Report CRT-965,1994, Centre de Recherche sur les Transporsite, Universite de Montreal, Canada.

67. Geoffrion A. M. Lagrangian relaxation for integer programming // Mathematical Programming Study, 1974, N 2, P. 82-114.

68. Graham R. L. Bounds for Certain Multiprocessing Anomalies j j Bell System Technical Journal, 1966, N 45, P. 1563-1581.

69. Guha S., Khuller S. Greedy strikes back: improved facility location algorithms //In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, P. 649-657.

70. Hassin R., Tamir A. Efficient algorithm for optimization and selection on series-parallel graphs // SIAM J. Algebraic Discrete Methods, 1986, V. 7, N 3, P. 379-389.

71. Hassin R., Zemel E. Probabilistic analysis of the capacitated transportation problem // Mathematics of Operation Research, 1988, V. 13, N 1, P. 80-89.

72. Hochbaum D. S. Heuristics for the fixed cost median problem, // Mathematical Programming, 1982, N 22, P. 148-162.

73. Hochbaum D. S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems // In the book "Approximation algorithms for NP-hard problems", edited by D. S. Hochbaum, 1996, PWS Publishing Company.

74. Holmberg К., Yuan D. A Lagrangian heuristic based branch-and-bound approach fop the capacitated network design problem // Operations Research, 2000, V. 48, N 3, P. 461-481.

75. Johnson D. S. Approximation algorithms for combinatorial problems // Journal of Computing and System Science, 1974, N 9, P. 256-278.

76. Karp R. M. The probabilistic analysis of som.e combinatorial algorithms // In Algorithms and complexity: New Directions and recent results, 1976, P. 1-19.

77. Karp R. M., Motwani R., Nisan N. Probabilistic analysis of network flow algorithms // Mathematics of Operation Research, 1993, V. 18, N 1, P. 71-97.

78. Kleinschmidt P., Schannath H. A strongly polynomial algorithm for the transportation problem // Mathematical Programming, 1995, N 68, P. 1-13.

79. Kolen A. Solving covering problems and the incapacitated plant location on the trees // European Journal of Operational Research, 1983, V. 12, N 3, P. 266-278.

80. Korupolu M., Plaxton C., Rajaraman R. Analysis of a local search heuristic for facility location problems //In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, P. 1-10.

81. Land A. H., Doig A. G. An automatic methods of solving discrete programming problems // Econometrica, I960, V. 28, N 3.

82. Lin J. H., Vitter J. S. e-approximation with minimum. packing constraint violation //In Proceedings of the 24th STOC, 1992, P. 771-782.

83. Lin J. H., Vitter J. S. Approximation algorithms for geometric m.edian problems // Information Processing Letters, 1992, N 44, P. 245-249.

84. Mircliandani P. В., Francis R. L. (eds.) Discrete location theory// Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley and Sons Inc., N.Y./Chichester /Brisbane /Toronto /Singapour, 1990.

85. Nauss R. M. An improved algorithm for the capacitated facility location problem // Journal of the Operational Research Society, 1978, N 29, P. 1195-1201.

86. Nemhauser G. L., Wolsey L. A., Fisher M. L. An analysis of approximations for submodular set functions — / // Mathematical Programming, 1978, N 14, P. 265-294.

87. Orlin J. B. A faster strongly polynomial minimum cost flow algorithm. // Operations Research, 1993, N 41, P. 338-350.

88. Papadimitrou С. Worst-case and probabilistic analysis of a geometric location problem // SIAM Journal of Computing, 1981, N 10, P. 542-557.

89. Papadimitrou C., Yannakakis M. Optimization, approximation and complexity classes // Journal of Computer and System Sciences, 1991, N 43, P. 425-440.

90. Piersma N. A probabilistic analysis of the capacitated facility location problem // Journal of Combinatorial Optimization, 1999, N 3, P. 3150.

91. Rinnoy Kan A. H. G. An introduction to the analysis of approximation algorithms // Discrete Applied Mathematics, 1986, N 14, P. 171-186.

92. Sa G. Branch and bound and approximate solutions to the capacitated plant location problem // Operations Research, 1969, N 17, P. 10051016.

93. Salmi S. General technique for combinatorial approximation // Operations Research, 1977, N 25, P. 920-936.

94. Sliah R., Farach-Colton M. Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees // Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.

95. Shapiro J. F. Generalized Lagrange multipliers in integer programming // Operations Research, 1971, N 19, P. 68-76.

96. Shapiro J. F. A survey of Lagrangian techniques for discrete optimization // Annals of Discrete Mathematics, 1979, N 5, P. 113138.

97. Shmoys D. Computing near-optimal solutions to combinatorial optimization problems // In W. Cook, L. Lovasz, P. Seymour, editors Advances in Combinatorial Optimization, AMS, Providence RI, 1995, P. 355-397.

98. Shmoys D. В., Tardos E., Aardal K. Approximation algorithms for facility location problem, s //In Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, P. 265-274.

99. Slominski L. Probabilistic analysis of combinatorial algorithms: a bibliography with, selected annotations // Computing, 1982, N 28, P. 257-267.

100. Wolsey L. A. Maximizing real-valued submodular functions: primal and dual heuristics for location problems // Mathematics of Operation Research, 1982, N 7, P. 410-425.ф