Алгоритмы с оценками для некоторых задач размещения производства тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Курочкин, Александр Александрович

• Курочкин, Александр Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Курочкин, Александр Александрович

Оглавление

Введение

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

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

1.2 Основные определения

1.3 Основные утверждения

1.4 Описание алгоритма

1.5 Трудоемкость алгоритма

2 Двухэтапная задача размещения на дереве

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

2.2 Основные утверждения

2.3 Описание алгоритма

3 Поиск совершенного паросочетания в случайном графе

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

3.2 Описание алгоритма

3.3 Трудоемкость алгоритма

3.4 Вероятностный анализ алгоритма

3.4.1 Оценка этапа 1

3.4.2 Оценка этапа 2

3.4.3 Оценка с помощью неравенства Чебышева

3.4.4 Оценка с помощью теоремы Петрова

3.5 Задача на ориентированном графе

3.6 Задача на двудольном графе

4 Задача размещения с ограничениями на объемы производства на случайных входах

4.1 Задача с одинаковыми ограничениями

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

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

4.1.3 Идея и описание алгоритма

4.1.4 Анализ алгоритма

4.2 Задача с произвольными ограничениями

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

4.2.2 Описание алгоритма

4.2.3 Анализ алгоритма

Заключение

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

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

Литература

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

Введение

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

В общем виде математическую модель реальной задачи можно представить таким образом:

С{х) —> min,

x£Q

где через Q обозначается множество управлений, допустимых в условиях реальной задачи (допустимые решения задачи), а через С(х) обозначается стоимость (целевая функция), связанная с осуществлением управления х. Задача состоит в поиске оптимального управления х* Е Q, с которым связана минимальная стоимость реализации С* = С(х*).

Основной вопрос состоит в том, каким образом можно эффективно найти оптимальное управление х*1 Если множество допустимых управле-

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

Для произвольного алгоритма Л через Тд будем обозначать трудоемкость (временную сложность) алгоритма, то есть число элементарных операций, требуемых для его реализации. Под элементарными операциями принято понимать любую арифметическую операцию или операцию сравнения двух чисел. Нас будет интересовать функция Тд(п) зависимости трудоемкости алгоритма от длины п записи входных данных индивидуальной задачи. Мы будем говорить, что алгоритм Л является полиномиальным, если Тл(п) — 0(р(п)) для некоторого полинома р(п), то есть, если временная трудоемкость алгоритма ограничена полиномом от длины записи входных данных задачи.

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

зуя принятую в [23] терминологию. К классу Р относится множество всех задач распознавания свойств, для решения которых возможно построение алгоритмов с полиномиальной трудоемкостью. Класс КР состоит из таких задач распознавания, предполагаемое решение для которых (или как это называется в [23] "догадка для решения") можно за полиномиально ограниченное время проверить на истинность. Очевидно, что Р с NP.

Огромную роль в определении сложностного статуса оптимизационных задач играет понятие полиномиальной сводимости, для определения которого также воспользуемся работой [23]. Считается, что задача N1 полиномиально сводится к задаче N2, если для любой индивидуальной задачи Д £ N1 за полиномиальное время можно построить индивидуальную задачу /2 ^ N2, а по оптимальному решению х?> задачи Д за полиномиальное время можно построить оптимальное решение х\ задачи Д.

Важнейшее открытие было сделано в 1971 в [16] — найден класс задач распознавания свойств (называемый NP-пoлным), к которым полиномиально сводится любая задача из КР. Таким образом, если для какой-либо NP-пoлнoй задачи будет предложен точный полиномиальный алгоритм решения, то это будет означать, что любая задача из класса NP также может быть решена за полиномиальное время и NP = Р. Оптимизационные задачи, к которым полиномиально сводятся NP-пoлныe задачи распознавания свойств, принято называть КР-трудными. К этому классу относятся уже такие популярные задачи, как задача о коммивояжере, задача о вершинном покрытии, задача о ранце. В настоящее время положительный ответ на вопрос о совпадении классов Р и NP считается маловероятным, поэтому поиск точных полиномиальных алгоритмов для КР-трудных задач

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

Введем определение приближенного алгоритма, как это сделано в [59]. Будем говорить, что алгоритм Л имеет оценки точности (£п,6п) в классе К,п задачи минимизации размерности п, если выполнено неравенство

(С(хА) - С(х") т \ С(х') "/ Ь

где х* — оптимальное решение для индивидуальной задачи /п, хл — решение, полученное при помощи алгоритма Л, Р{£} — вероятность события 5, еп — относительная погрешность получаемого решения, 5п — вероятность несрабатывания алгоритма Л.

Алгоритм называется асимптотически точным в классе задач /С = если для него существуют такие оценки (еп, 5п), что еп —V 0, 5п —»■ О при п —> оо. Применение подобных алгоритмов обосновано для задач высокой размерности.

Будем говорить, что алгоритм Л решения задачи минимизации имеет гарантированную оценку точности р: если для любой индивидуальной задачи / стоимость построенного алгоритмом решения отличается от оптимального не более чем в р раз, то есть < р.

Данная диссертация посвящена исследованию задачи размещения производства, которая составляет один из наиболее актуальных и широких разделов исследования операций и в общей постановке является КР-трудной. Одними из первых Отечественных ученых, рассматривающих данную задачу, были Дементьев (1965 год [62]), Гимадутдинов (1969 год

[60]), Всреснев (1971 год [51]). Одна из первых Отечественных монографий по данной задаче была издана в 1978 [52]. Среди современных научных книг по дискретной теории размещения хотелось бы выделить работу Mirchandani и Francis [39], которая содержит довольно широкий анализ различных постановок задачи.

Сформулируем простейшую задачу размещения (FLP, Facility Location Problem), которую можно рассматривать как базовую для других постановок задачи. Пусть заданы множество I — {1 ,...,т} возможных пунктов размещения производства некоторого однородного продукта (которые далее мы также будем называть "предприятиями" и "производителями") и множество J = {1,..., п} пунктов потребления данного продукта (которые далее мы также будем называть "клиентами"). Известны затраты gf, связанные с открытием предприятия в пункте г Е /. Для каждого пункта потребления j G J задан объем спроса bj. Также заданы транспортные затраты связанные с доставкой единицы продукции из i Е / в j £ J. Требуется определить пункты размещения производства и транспортные потоки между производителями и клиентами таким образом, чтобы удовлетворить потребности всех клиентов и минимизировать общие затраты на размещение производства и поставку продукции.

Рассмотрим математическую постановку FLP в виде задачи частично-целочисленного линейного программирования. Требуется определить минимум функции

т т п

с(х) = giXi + giiXiJ

i—1 г=1 j=1

по переменным при выполнении условий

т ?;=1

— bjxi¿ ъ е 1,3 е ^

хц >0, хг е {о, 1}, г е /, з е 3,

где

Х{, г Е /, — переменные выбора предприятий (если Х{ = 1, то в соответствующем решении предприятие г 6 / является открытым),

Хц, г Е 1,з Е </, — транспортные переменные, задающие объем продукта, поставляемый предприятием г Е / в пункт спроса Е «/.

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

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

• Задача с ограничениями на объемы производства. Когда

для каждого предприятия задана некоторая предельная мощность

с?г > 0, г Е /, которая задаст ограничение на максимальный объем

производимого продукта ^ Xij < г Е /.

з^

• Задача с ограниченными пропускными способностями коммуникаций. Когда для каждого направления из пункта г Е / в пункт з Е </ задано ограничение на максимальный объем продукта

fij > 0, который может быть вдоль него перевезен. То есть, к исходной задаче размещения добавляется дополнительное ограничение Xij < fij, г G /, J € J.

• Задача на случайных входных данных. Когда часть входных данных (потребности клиентов, транспортные расходы и т.д.) генерируется случайным образом согласно некоторого заданного вероятностного распределения.

Задача размещения является NP-трудной даже в простейшей постановке, что было доказано, например, в [23] (к ней сводится задача о минимальном покрытии конечного множества системой подмножеств). Это означает, что построение точного полиномиального алгоритма решения данной задачи выглядит малоперспективным и поэтому для FLP и ее обобщений актуальны исследования в следующих двух направлениях:

• построение приближенных алгоритмов решения с гарантированными оценками точности,

• выделение классов задач, для которых возможно построение точных полиномиальных алгоритмов решения,

Для простейшей задачи размещения в самой общей постановке в 1982 году Hochbaum [27] предложила полиномиальный жадный алгоритм, отыскивающий допустимое решение задачи с оценкой точности O(logn), где п — число пунктов спроса. При этом использовалось сведение простейшей задачи размещения к задаче о покрытии. В то же время Feige в работе [20] показал, что если NP £ DTIME(n°^loglogn)), то для любого £ > 0

нельзя построить приближенный алгоритм решения задачи о покрытии с оценкой точности не хуже (1 — е) log п. Здесь через DTIME(/(n)) обозначается класс задач распознавания, которые могут быть решены за время, ограниченное функцией f(n).

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

• Метрическая задача размещения. Множества / и J являются точками некоторого метрического пространства с заданной метрикой. В этом случае предполагается, что для любых точек г,.;', к £ IUJ заданы расстояния в метрическом пространствесц, Cjk, Cik и выполняется неравенство треугольника с^ + > с^-. Транспортные расходы в задачах такого типа индуцируются расстояниями между точками.

• Задача на графах специального вида. Множества I и J являются вершинами некоторого графа G = (V, Е), V — I U J, с неотрицательными длинами ребер dij, а стоимость доставки единицы продукции gij, i € I,j Е J, определяется длиной кратчайшего пути между вершинами г и j в графе G. Граф (7, как правило, предполагается связным (популярные варианты -- путь, дерево, двудольный граф).

Для наиболее распространенной метрической задачи размещения из-

вестно множество приближенных алгоритмов с гарантированными оценками точности. В 1997 году Shmoys, Tardos и Aardal в [44] получили один из первых результатов в данном направлении — алгоритм с гарантированной оценкой точности 3.16, основанный на методе линейной релаксации (LP-rounding). Двумя годами позже Guha, Khuller в [25] улучшили оценку точности до 2.41, добавив технику жадного алгоритма в алгоритм Shmoys, Tardos и Aardal. Одновременно в [25] было доказано, что для метрической задачи нельзя построить приближенный алгоритм с оценкой точности лучше, чем 1.463, при условии NP £ DTIME(n°(loglogn)). Chudak в [14] предложил модифицировать алгоритм Shmoys, Trados и Aardal путем использования другой техники округления полученного после релаксации решения, что позволило усилить оценку точности до 1.736. Примерно в это же время Charikar и Guha [12] получили алгоритм с оценкой 1.728, добавив к Chudak прямо-двойственный и жадный алгоритм. В 2001 году Jain и Vazirani [48] построили первый комбинаторный приближенный алгоритм с оценкой точности 3 и временной трудоемкостью 0(п2 log п). В том же 2001 году Jain, Mahdian и Saberi предложили новый алгоритм с оценкой 1.61 и трудоемкостью 0(п3). В 2002 году Sviridenko [42] построил алгоритм с оценкой 1.582, основанный на методе LP-rounding. Также в этой работе был усилен результат Guha [25] относительно невозможности построить алгоритм с оценкой точности лучше 1.463 — условие NP ^ DTIME(ra°(loglogn)) было заменено на NP ^ Р. В 2002 году Mahdian, Ye, Zhang в [37] использовали различные жадные техники и построили алгоритм с трудоемкостью О(п3) и оценкой 1.52, которая долгое время оставалась одной из лучших. Самый точный на текущий момент приближенный алгоритм с оценкой 1.488

был предложен Li в 2011 году в работе [35]. Данный алгоритм является улучшенной модификацией алгоритма с оценкой точности 1.5, построенного Byrka в 2007 в [11]. Улучшения оценки точности удалось достичь за счет вероятностного выбора одного из ключевых параметров. Более конкретно, в [11] был предложен алгоритм, зависящий от параметра 7, который имел точно заданное значение (7 ^ 1.6774). В [35] было предложено использовать значение 7, выбранное случайным образом (согласно некоторого вероятностного распределения), что привело к улучшению оценки точности.

Сильные результаты были получены для некоторых задач размещения на графах различного вида. В частности, стоит отметить, что задача размещения на дереве является полиномиально разрешимой. В 1976 году Trubin [64] впервые построил точный алгоритм решения этой задачи с временной трудоемкостью 0(п3), где п — число пунктов спроса. Отметим, что в 1983 году алгоритм с аналогичной трудоемкостью был построен Kolen в [30]. В том же 1983 году Girnadi [57] удалось построить менее трудоемкий алгоритм, решающий данную задачу за время 0(тп), где m — число пунктов возможного размещения производства. Алгоритм с лучшей на сегодняшний день трудоемкостью, предложенный в 2002 Shah и Farach-Colton в [43], решает задачу за время O(nlogn). Однако, данный результат по какой-то причине не получил широкого распространения в литературе.

Для отыскания точного решения на к-деревьях также были построены точные алгоритмы решения: для 2-дерева Ageev в 1990 году в [50] предложил алгоритм с трудоемкостью 0(ш3п), позже в 1992 году Ageev обобщил этот результат на случай А;-дерева и в [4] обосновал алгоритм с трудо-

емкостью 0(тк+1п). В 1995 году Ageev в [5] также установил, что простейшая задача размещения является NP-трудной, даже если матрица транспортных расходов порождена расстояниями на плоской решетке (плоской решеткой называется граф G с множеством вершин {vij, 1 < i,j < n}, в котором вершины соединены ребром тогда и только тогда, когда

К-Л + и-Л = !)•

Отметим, что задача размещения с ограничениями на объемы производства (CFLP, Capacitated FLP) является обобщением простейшей задачи размещения и поэтому также является NP-трудной. В силу уже отмеченного выше результата [27], маловероятно, что для CFLP существует приближенный алгоритм решения с оценкой точности лучше 0(logп). Поэтому, опять же, имеет смысл обратить внимание на изучение специальных подклассов задачи. Для метрической постановки задачи Korupolu, Plaxton, Rajaraman в 2000 году в [31] впервые предложили приближенный алгоритм решения задачи с оценкой точности 8(1+6:), в основе которого лежит метод локального поиска. В 2005 году Chudak, Williamson [15] модифицировали этот результат и установили оценку точности 6(1 + е).

На текущий момент в литературе известно очень мало результатов относительно построения точных алгоритмов решения для каких-либо вариаций задачи размещения с ограничениями на объемы производства. Можно выделить работу А. Агеева [2], которому удалось построить точный алгоритм с трудоемкостью 0(n5m2 + n3m3) для решения задачи размещения на цепи с одинаковыми ограничениями на объемы производства. Стоит отметить, что задача размещения на цени с произвольными ограничениями на объемы производства является NP-трудной (поскольку содержит в каче-

стве подзадачи задачу о ранце, если положить все транспортные расходы равными 0), поэтому предложенный в [2] комбинаторный алгоритм выглядит еще более интересным. Также задачу на цепи ранее рассматривали Mirchandani, Kohli, Tamir в [40], где для постановки с единичными потребностями клиентов и некоторыми дополнительными ограничениями предложили точный алгоритм решения с трудоемкостью 0{тптт(СтаХ: п)) (Сгпах — максимальное значение в матрице транспортных расходов).

Многоэтапная задача размещения производства также является NP-трудной, поскольку содержит FLP в качестве подзадачи. Наибольший практический интерес представляет изучение метрического варианта данной задачи. Для приближенного решения /^-этапной задачи размещения в 1999 году Aardal, Gavian, Chudak, и Shmoys в [1] предложили алгоритм с оценкой точности 3 для любого значения к. Отметим, что в основе данного алгоритма лежит метод линейной релаксации с необходимостью решения задачи линейного программирования, что приводит к соответствующей трудоемкости получения оценки. Первый комбинаторный алгоритм был предложен в 2000 году (Meyerson, Munagala, Plotkin [36]) и имеет оценку точности O(logn). В 2002 году Агеев [3] показал, что многоэтапная задача за полиномиальное время сводится к простейшей метрической задаче размещения, при этом стоимость решения возрастает не более чем вЗ раза. Учитывая этот факт, для решения многоэтапной задачи можно использовать любой из известных приближенных алгоритмов решения простейшей метрической задачи [11], [12], [14], [25], [37], [42], [35], [44], [47] и получить соответствующую оценку точности, увеличенную в 3 раза. В 2004 году Ageev, Ye, Zhang в [6] модифицировали некоторые процедуры, предложенные в [3],

и построили новый комбинаторный алгоритм, имеющий оценку точности h(k) < 3.27 для всех значений к и h(k) —> 3.27, при к —» оо. При этом h{2) « 2.421, Л(3) « 2.845, /¿(4) « 3.0565, h(5) « 3.168 и так далее. То есть, в случае к = 2 и /с = 3 построенный алгоритм даже улучшает оценку точности, предложенную Aardal, Gavian, Chudak и Shmoys для некомбинаторного алгоритма из [1]. Для двухэтапной задачи (к = 2) лучший результат на текущий момент предложен Zhang в [49], где построен алгоритм с оценкой точности 1.77.

Возникает логичный вопрос — является ли двухэтапная задача более сложной, чем одноэтапная? Правильный ответ на этот вопрос был получен в 2012 году Krishnaswamy и Sviridenko в [33], где установлена нижняя оценка точности для приближенных алгоритмов решения двухэтапной задачи размещения 1.539 (напомним, нижняя оценка для одноэтаиной задачи 1.463). Также в [33] показана новая оценка точности для fc-эташюй задачи 1.61. Отметим, что эти оценки получены некомбинаторными методами.

Данная диссертационная работа организована следующим образом. В первой главе рассматривается задача размещения с одинаковыми ограничениями на объемы производства на путевом графе. А именно, предполагается, что стоимость обслуживания^-, i 6 I,j G J, задается расстоянием между вершинами i и j в путевом графе G — (V, Е), V = / U J, с неотрицательными длинами ребер dij между любыми двумя вершинами г, j Е V. Отметим, что сетевая задача CFLP также является NP-трудной, поскольку содержит в качестве подзадачи вариант задачи о рюкзаке (достаточно рассмотреть случай, когда все ребра графа имеют нулевую длину). В частности, CFLP является NP-трудной и па путевом графе. Однако, если при

этом предполагается, что все предприятия имеют одинаковое ограничение на объем производимого продукта, то задача становится полиномиально разрешимой и для неё в работе Ageev [2] был построен точный алгоритм с временной трудоемкостью 0(т5п2 + т3п3). В диссертации предлагается модификация предложенного в [2] алгоритма, а именно — точный полиномиальный алгоритм, имеющий на порядок меньшую трудоемкость по обоим параметрам 0(т4п2), что на текущий момент является лучшим результатом из известных в литературе.

Во второй главе рассматривается двухэтапная задача размещения производства на дереве. Предполагается, что множества пунктов потребления ./V и возможного размещения производства каждого этапа М\, М2 являются вершинами некоторого дерева с неотрицательными длинами ребер, а затраты на транспортировку единицы продукции из пункта в пункт совпадают с длиной пути, соединяющего эти пункты. Отметит, что слож-ностной статус многоэтапной задачи на дереве до сих пор не установлен. В то же время, если дерево является цепью, то в 1995 году Гимади [56] предложил точный полиномиальный алгоритм для решения /г-этапной задачи размещения с трудоемкостью 0{кпт1... гпк), где Шг — число пунктов производства на г'-ом этапе (г < к). Также в [56] предложен еще один принципиально другой точный алгоритм решения данной задачи с трудоемкостью 0(п3 тг)- Для двухэтапной задачи размещения на дереве 01тасП в [24] анонсирована идея построения точного полиномиального алгоритма решения. Во второй главе описан и обоснован алгоритм для точного решения задачи на дереве с временной трудоемкостью 0(пга3).

В третьей главе рассматривается задача по поиску совершенного па-

росочетания в случайном графе. Данная задача будет использована нами в последующем при решении задачи размещения на случайных входных данных, но она вынесена в отдельную главу, поскольку представляет существенный интерес в самостоятельной постановке. Предполагается, что задан некоторый неориентированный граф G(n,p) со множеством вершин V, \V\ = п, и множеством ребер Е, которое генерируется случайным образом — любая пара вершин соединяется ребром независимо от остальных с некоторой вероятностью р (0 < р < 1). Задача состоит в поиске совершенного паросочетания на графах такого вида. Совершенным паросочетанием графа G = (У, Е) называется набор М С Е попарно несмежных ребер, в котором участвуют все вершины V (т.е. любая вершина графа инцидентна ровно одному ребру из М).

Отметим, что для детерминированной задачи по поиску совершенного паросочетания известны точные алгоритмы: впервые точный алгоритм с временной трудоемкостью порядка 0(п4) был предложен в [18] (Edmonds, 1965), а позднее был модифицирован в работе [22] (Gabow, 1976) до алгоритма с трудоемкостью 0(п3). Примерно в это же время были предложены два других более быстрых алгоритма: Even в [19] предложил алгоритм с трудоемкостью 0(п2'5), a Kameda, Mura в [28] алгоритм с трудоемкостью 0(п\Е\). Самый лучший из известных алгоритмов был предложен в 1980 году Micali, Vazirani [38] и имеет трудоемкость 0{п1/2\Е\). Однако, поскольку мы имеем дело с вероятностной задачей, поведение которой будем исследовать при достаточно больших значениях п, то существенный интерес представляет построение менее трудоемких алгоритмов.

Для вероятностной постановки задачи в работе [9] представлен при-

ближенный алгоритм с трудоемкостью порядка О(п log п), а также доказано следующее утверждение: для любого а > 0 существует такая константа ¡3 > 0, что если р(п) > то с временной сложностью 0(пlog п) алго-

ритм находит совершенное паросочетание в графе G(n,p) с вероятностью 1 — 0(п~а). Стоит отметить, что в [9] отсутствует представление значений а и /? в явном виде, что существенно ограничивает возможность аналитического использования данного алгоритма. В диссертации предлагается новый алгоритм решения задачи, который имеет аналогичную трудоемкость O(nlogn), но при этом является более простым в понимании и дальнейшем использовании, а также имеет оценки точности, выраженные в явном виде. Проводится полный вероятностный анализ построенного алгоритма с использованием техники теоремы Чебышева и теоремы Петрова, устанавливаются оценки точности алгоритма и условия, при которых он является асимптотически точным.

В четвертой главе рассматривается задача размещения с ограничениями на объемы производства на случайных входных данных. А именно, предполагается, что элементы матрицы транспортных расходов (р^) заданы как значения независимых случайных величин с равномерной функцией распределения на целочисленном сегменте [1 , г]. Ранее подобная задача рассматривалась в работе [54], где был проведен ее вероятностный анализ и построен приближенный алгоритм решения. Было показано, что предложенный алгоритм является асимптотически точным, но при условии наложения достаточно жестких ограничений на входные данные задачи. Данная задача рассматривалась также в работе [58], где был предложен другой приближенный алгоритм решения. Но и в этой работе условия асимптоти-

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

Для решения рассматриваемой специальной задачи предлагается схема, в которой в качестве подзадачи требуется отыскивать план перевозок от заданных предприятий к потребителям, что является предметом решения задачи транспортного типа. Для последней задачи известны точные полиномиальные алгоритмы. Например, в статье [45] предложен алгоритм, имеющий трудоемкость 0(тп2 logn + n2 log2 п), в [29] представлен другой алгоритм с трудоемкостью 0(т log т(К + nlogn)) (К — число ребер графа). В данной работе предлагается метод отыскания плана перевозок, который, вообще говоря, не всегда находит решение, но является достаточно быстрым — имеет на порядки меньшую трудоемкость, чем перечисленные выше точные алгоритмы. В качестве подзадачи рассматривается проблема отыскания совершенного паросочетания в случайном двудольном графе, ребрам которого соответствуют коммуникации минимальной стоимости. Данная задача рассматривалась в третьей главе, где для ее решения был предложен приближенный алгоритм с трудоемкостью О (п log п), а также определены условия его асимптотической точности. С использованием этого метода, для задачи размещения с одинаковыми ограничениями на объемы производства построен приближенный алгоритм решения и проведен вероятностный анализ его работы. Представлены условия, при которых

Список литературы диссертационного исследования кандидат наук Курочкин, Александр Александрович, 2014 год

Литература

1. Aardal К., Gavian A. Chudak F., Shmoys D. A 3-approximation algorithm for the k-level uncapacitated facility location problem // Information Processing Letters, v.72, n.5-6, 1999, P. 161-167.

2. Ageev A.A. A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graph // Proceedings of the 2nd Intern. Workshop Discrete Optimization Methods in Production and Logistics DOM'2004, Omsk, 2004, P. 28-32.

3. Ageev A.A. Improved Approximation Algorithms for Multilelvel Facility Location Problems // Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'02), Springer, London, 2002, P. 5-13.

4. Ageev A.A. A criterion of polynomial-time solvability for the network location problem // Integer Programming and Combinatorial Optimization., Proc. IPCO II Conf. Campus Printing, Carnegie Mellon University, 1992, P. 237 245.

5. Ageev A. A .Complexity of the netwrok median problem on plannar grids // Siberian Advances in Mathematics, 5, 1995, P. 1-9.

6. Ageev A., Ye Y., Zhang J. Improved combinatorial apporximation algorithms for the k-Level facility location problem // SIAM Journal on

Discrete Mathematics 18 (1), 2004, P. 207—217.

7. Aikens C.H. Facility location models for distribution planning j/ Eur J Oper Res, 1985, 22, P. 263-279.

8. Akinc U., Khumawala B.M. An efficient branch and bound algorithm for the capacitated warehouse location problem // Manag Sci, 1977, 23, P. 585-594.

9. Angluin D., Valiant L.G. Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings // Journal of Computer and System Sciences, 18(2), 1979, P. 155-193.

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

11. Byrka J. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem // Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization, Algorithms and Techniques, 2007, Berlin, Heidelberg, P. 29-43.

12. Charikar M., Guha S. Improved combinatorial algorithms for facility location and k-median problems //In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, October 1999, P. 378388.

13. Christofidies N., Beasley J.E. An algorithm for the capacitated warehouse location problem // Journal of the Operations Research Society, 12/1, 1983, R 19-28.

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

15. Chudak F., Williamson D. Improved approximation algorithms for capacitated facility location problems // Mathematical Programming, 01/2005, 102(2), P. 207-222.

16. Cook S.A. The complexity of theorem-proving procedures // In Proceedings of the third annual ACM symposium on Theory of computing, ACM New York, NY, USA, 1971, P. 151-158.

17. Davis P.R., Ray T.L. A branch and bound algorithm for the capacitated facilities location problem // Naval Research Logistics Quarterly, 16, 1969.

18. Edmonds J. Paths, trees and flowers // Canad J. Math., 1965, 17, P.449-467.

19. Even S., Kariv O. An 0(n2'5) algorithm for maximum matching in general graphs // Proceedings of the 16th IEEE Symposium on Foundations of Computer Science, 1975, P. 100-112.

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

21. Feldman E., Lehrer F.A., Ray T.L. Warehouse locations under continuous economies of scale // Management Science, 1966, 2.

22. Gabow H.N. An efficient implementation of Edmonds' algorithm for maximum matching on graphs // Journal of the Association for Computing Machinery, Vol. 23, N. 2, 1976, P. 221-234.

23. Garey M.R., Johnson D.S. Computers and Intractablity // Freeman, San Franciskco, 1979.

24. Gimadi E.Kh. Exact Algorithm for Some Multi-level Location Problems on a Chain and a Tree // Oper. Research Proceedings, Springer-Verlag, Berlin, 1997. P. 72-77.

25. Guha S., Khuller S. Greedy strikes back: Improved facility location algorithms // Journal of Algorithms, 31, 1999, P. 228-248.

26. Guignard M., Kim S. A strong Lagrangian relaxation for capacitated plant location problems// University of Pennsylvania, The Wharton School, Dept. of Statistics, Technical Report No. 56, 1983.

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

28. Kameda T., Munro l.An 0(|V||i£|) algorithm for maximum matching of graphs// Computing, 1976, 12, P.225-231.

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

30. Kolen A. Solving covering problems and the uncapacitated plant location on the trees // Eur. J. Oper. Res., 1983, 12, N 3, P. 266-278.

31. Korupolu M., Plaxton C., Rajaraman R. Analysis of a local search heuristic for facility location problems // Journal of Algorithms, 2000, 37, P. 146-188.

32. Krarup J., Pruzan, P.M. The simple plant location problem // Survey and synthesis, European Journal of Operational Research, 1983, Vol. 12, P. 36-81.

33. Krishnaswamy R., Sviridenko M. Inapproximability Results for the Multi-level ¡Incapacitated Facility Location Problem // Proceedings of SODA 2012, P. 718-734.

34. Kuehn A.A., Hamburger M.J. A heuristic program for locating warehouses // Manag Sci, 1963, 9, P. 643-666.

35. Li S. A I.488-approximation algorithm for the uncapacitated facility location problem // International Colloquium 011 Automata, Languages and Programming (ICALP), 2011, P. 77-88.

36. Meyerson A., Munagala K., Plotkin S. Cost-distance: Two metric network design // Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2000, P. 624-630.

37. Mahdian M., Ye Y., Zhang J. A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem, manuscript, 2002.

38. Micali S., Vazirani V.An 0(y/\v\\E\) algorithm for finding maximum matching in general graphs // Proc. 21st Ann. Symp. on Foundations of Computer Science, IEEE, 1980, P. 17-27.

39. Mirchandani P.B., Francis R.L. (eds.) Discrete location theory // Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York, 1990.

40. Mirchandani P., Kohli R., Tamir A. Capacitated location problems on a line ¡I Transportation Science 30 (1996), 1, P. 75-80.

41. Nauss R.M. An improved algorithm for the capacitated facility location problem 11 J Oper Res Soc, 1978, 29, P. 1195-1201.

42. Sviridenko M. An 1.582-approximation algorithm for the metric uncapacitated facility location problem!/ Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Volume 2337, 2002, P. 240-257.

43. Shah R., Farach-Colton M. Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees // Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2002, P. 108-115.

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

45. Tokuyama T., Nakano J. Efficient algorithms for the Hitchcock transportation problem// Symposium on Discrete Algorithms: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, Orlando, Florida, United States, 1992. P. 175-184.

46. Jacobson S.K. Heuristics for the capacitated plant location model // European Journal of Operational Research, 1983, 12, P. 253-261.

47. Jain K., Mahdian M., Saberi A. A new greedy approach for facility location problems, manuscript, 2001.

48. Jain K., Vazirani V. Approximation algortihms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation // Journal of the ACM, 48, 2001, P. 274-296.

49. Zhang J. Approximating the two-level facility location problem via a quasi-greedy approach // Math. Program. 108(1), 2006, P. 159-176.

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

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

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

53. Боровков А.А. Теория вероятностей // Москва: Наука, 1986.

54. Вознюк И.П., Гимади Э.Х., Филатов М.Ю. Асимптотически точный алгоритм для решения задачи размещения с ограниченными объемами производства // Дискретный анализ и исследование опера-

ций, Новосибирск: Изд-во ИМ СО РАН, 2001, Сер. 2, Том 8, №2, С. 3-16.

55. Гимади Э.Х. Математические моделии методы исследования операций // Учебное пособие: СибГУТИ, Новосибирск, 2009.

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

57. Гимади Э.Х. Эффективный алгоритм решения задачи размещения с областями обслуживания связными относительно ациклической сети // Управляемые системы: Сборник научных трудов. Новосибирск: Институт математики СО АН СССР, 1983. Выпуск 23. С. 12-23.

58. Гимади Э.Х., Курочкин А.А. Одна задача размещения с одинаковыми объемами производства на случайных входных данных // Вестник НГУ. Серия: Математика, механика, информатика, Новосибирск: Изд-во НГУ, 2011, Т. 11, вып. 1, С. 15-34.

59. Гимади Э.Х., Перепелица В.А. Асимптотический подход к решению задачи коммивояжера // Сб. научн. тр. Вып. 12. Новосибирск: Ин-т математики СО АН СССР, 1974, С. 35-45.

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

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

62. Дементьев В.Т. Об одной задаче оптимального размещения точек на отрезке // Дискретный анализ, Новосибирск: Ип-т математики Сиб. отд. АН СССР, вып. 4, 1965, С. 23-27.

63. Петров В.В. Предельные теоремы для сумм независимых случайных величин, М.: Наука, 1987.

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