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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

На правах рукописи

КУРОЧКИН Александр Александрович

АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ РАЗМЕЩЕНИЯ ПРОИЗВОДСТВА

01.01.09 - дискретная математика и математическая кибернетика

1 з ФЕВ 2014

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 2014

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель:

доктор физико-математических наук, профессор Гимади Эдуард Хайрутдинович.

Официальные оппоненты:

Ильев Виктор Петрович, доктор физико-математических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»; Тахонов Иван Иванович, кандидат физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет», доцент.

Ведущая организация:

Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Защита состоится 26 февраля 2014 года в 16 часов на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан " Лл^сил 2014 г. Ученый секретарь -

диссертационного совета, х/(/ - _____--^г—

Д-ф.-м-н. ^Л^^-^упг^' ю. В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Проведено исследование задачи размещения с ограничениями на объемы производства на путевом графе. В случае произвольных ограничений задача является ЛГР-трудной. В случае одинаковых ограничений на объемы производства задача становится полиномиально разрешимой и для нее предложен новый точный алгоритм решения с лучшей временной трудоемкостью из известных в литературе (модификация алгоритма, предложенного в [1]).

Предложен и обоснован точный полиномиальный алгоритм решения для двухуровневой задачи размещения на дереве, в то время как сложностной статус задачи для общего случая (произвольно-/*

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

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

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

[4], [6].

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

Апробация работы. Основные результаты диссертации докладывались на Международных научных студенческих конференциях (Новосибирск, 2008, 2009), на Европейской конференции по исследованию операций ЕХЖО-ХХШ (Бонн, 2009), на Международной конференции по дискретной оптимизации и алгоритмам СЮ8А-2010 (Росток, 2010), на Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2011), на Международном симпозиуме по комбинаторной оптимизации

СО-2012 (Оксфорд, 2012), на Европейской конференции по комбинаторной оптимизации ECCO-XXVI (Париж, 2013), на Международной конференции по Дискретной оптимизации и исследованию операций DOOR-2013 (Новосибирск, 2013), на научных семинарах Института математики им. C.JT. Соболева и Института вычислительной математики и математической геофизики СО РАН.

Публикации. По теме диссертации автором опубликовано 13 работ, в том числе 3 статьи в журналах из списка ВАК.

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

Основные результаты диссертации.

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

В разделе 1.1 приводится постановка задачи. Пусть I = {¿1,..., гт} обозначает множество возможных пунктов размещения производства некоторого однородного продукта, J = {j\, — множество пунктов потребления данного продукта. Тогда задачу размещения предприятий с одинаковыми ограничениями на объемы производства можно сформулировать следующим образом

C(S, х) = Y^ 9°i + Y1Y19Ц*Ц -> .min (1)

i€S . iesjeJ (bci,x)

= jeJ, (2)

ieS

У^ Xij <d, i E I, (3)

> 0, целые, i E I,j E J, (4)

где SCI обозначает искомый набор открываемых пунктов производства (предприятий), gf — стоимость открытия предприятия в пункте i Е /, d — производственная мощность предприятий из I, bj — объем потребляемого пунктом спроса j продукта, gtj — стоимость доставки единицы продукции от возможного пункта производства i к клиенту j. Допустимое решение задачи с множеством S и величинами х = (ж^) будем обозначать (S, х).

Дополнительно предполагается, что множества / и J являются вершинами некоторого путевого графа G = (V, Е), V = / и J, с

неотрицательными длинами ребер а стоимость доставки единицы продукции , г €/,:/£ ./, определяется длиной кратчайшего пути между вершинами г и j в графе О.

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

В разделах 1.2-1.3 приводятся основные определения и утверждения, введенные в [1], которые описывают свойства некоторых оптимальных решений задачи.

Без ограничения общности будем представлять сформулированную выше задачу как задачу на прямой. Другими словами, будем полагать, что множества I = ■ ■ ■ ,гт} и = {л, • ■ • ,.7п} представляют собой множества точек некоторой прямой, причем Ч < ¿2 < • • • < гт и < < ... < ]п- Стоимость обслуживания д^., г € I, у € в таком случае определяется расстоянием между точками г и ] на прямой.

Для любых г' < I" будем называть множество а С. I сегментом предприятий и обозначать его а = [г',г"], если а = {г',...,г"}. Аналогично для любых ]' < ]" будем называть множество т С ./ сегментом клиентов и обозначать его т = [/,/'], если т = {/,■••,/}•

Пусть (5, х) — допустимое решение задачи (1)-(4). Мы будем говорить, что г е / обслуживает клиента ] £ 3, если х^ > 0. Пункт производства г £ / будем называть насыщенным, если х^ = <1 и ненасыщенным, если 0 < ^ Отметим, что насыщен-

ные и ненасыщенные пункты производства обязательно должны быть открытыми. Будем называть сегмент предприятий о простым, если он содержит открытые пункты производства и мак-

симум одно из них является ненасыщенным.

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

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

В разделе 1.4 приводится описание алгоритма Ацсрьр решения задачи. Основная идея заключается в том, что для всех г', г" €

з'6 3, рассматриваются подзадачи со множеством заводов [г', г"] и множеством клиентов [з',з"}, при условии, что сегмент предприятий [¿', г"] является простым. Оптимальное решение каждой такой подзадачи обозначается через ,з")- Доказывается, что оптимальное решение исходной задачи явным видом выражается через значения ,з"), которые могут быть эффективно вычислены. Уменьшение на порядок трудоемкости алгоритма решения задачи, по сравнению с описанным в [1], достигается именно за счет более быстрого метода подсчета данных величин.

В разделе 1.5 обосновывается трудоемкость алгоритма:

Теорема 1. Алгоритм Ацсрьр находит оптимальное решение задачи размещения (1)—(4) на цепи с одинаковыми ограничениями на объемы производства за время 0{тАп2).

Во второй главе рассматривается двухэтапная задача размещения на дереве, идея решения которой была анонсирована в работе [2] была анонсирована идея решения. В настоящей главе описан и обоснован алгоритм для точного решения данной задачи.

В разделе 2.1 приводится постановка задачи. Пусть N = {1,..., п} — множество пунктов спроса конечного продукта, а Мг с N — множество возможных пунктов размещения предприятий г-го этапа, г = 1,2. Известны затраты д\ > 0 на размещение предприятия г-го этапа в пункте г £ Мг. Для каждого пункта потребления з 6 N

задан объем спроса bj > 0. Также заданы транспортные затраты Су > 0, связанные с доставкой единицы продукции из пункта г в пункт Для удовлетворения спроса пункта з £ N необходимый объем продукта bj должен пройти по следующей цепочке: открытое предприятие 2-го этапа —» открытое предприятие 1-го этапа —> пункт Всюду далее мы будем говорить, что предприятие г € Мг, г = 1,2, участвует в обслуживании пункта спроса ] € ./V, если г задействовано в цепочке предприятий, через которые з получает конечный продукт.

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

Приводится постановка в терминах векторов назначения: 7гг = (тг[,... ,-кгп) — вектор назначения предприятий г-го этапа, где — номер пункта из Мг, в котором открыто предприятие г-го этапа, участвующее в обслуживании пункта j, г = 1,2, 1 < ] <п, 7г = (тг1, 7г'2) — пара векторов назначения, которую мы также будем называть решением задачи,

/Г(тг) = игедг{7г^} — множество предприятий г-го этапа, задействованных в решении ж, г = 1,2.

Двухэтапная задача размещения в терминах переменных назначения записывается в компактном виде

ге/1(тг) ке12(п) jeN

В данной работе рассматривается двухэтапная задача размещения на дереве, когда матрице транспортных затрат (с^) может быть поставлена в соответствие некоторая ациклическая сеть С = (./V, Е), где N = {1,..., п} — множество вершин, Е = {е^ 11 < к < п} — множество ребер. Вершины в сети соответствуют пунктам спроса. Стоимость транспортировки единицы продукта с^ из пункта i в пункт '] определяется как сумма длин ребер в цепи, соединяющей эти пункты.

В разделе 2.2 вводятся дополнительные определения, формулируются и доказываются основные утверждения относительно существования оптимальных решений, обладающих специальными свойствами. Для каждого j 6 N обозначим:

Nj — множество потомков вершины j (максимальное поддерево исходного дерева с корневой вершиной j),

/J(vr) = U{7ifc | к € Nj} — множество предприятий r-го этапа, участвующих в обслуживании клиентов Nj в назначении 7г.

Индуктивно введем специальное обозначение /^(тг) для самого близкого к вершине j & N предприятия второго этапа, задействованного в назначении тт: для корня дерева (j = 1) положим

/ii (л-) = arg min cifc, для вершины j, 1 < j < п, kei2(n)

/^г(гг), если cJ/ti(7r) = min cjk, где i — это отец j,

^•(тг) = { . ке1М

> 1 arg mm с иначе.

к€12(тт)

Основным результатом раздела является следующая теорема

Теорема 2. Существует оптимальное решение двухэтапной задачи размещения на дереве, в котором для любой вершины t (L N выполнены свойства:

С Nt U {тт,1}, /t2(тг) С Nt U {тг2} U ,н(7г).

Данное свойство позволяет построить рекуррентный алгоритм, вычисляющий оптимальное решение задачи. Обозначим через М =< М1, М2; N > исходную двухэтапную задачу размещения. Рассмотрим семейство подзадач

Mj(i, к, к') = {< Mi, М2; Nj | 7г] = г, 7Г2 = к, ßj{-K) = к' >,

г £ Mi, к, к' в Mi, 1 < j < n}.

Обозначим оптимальное решение задачи Mj(i, к, к'), удовлетворяющее свойствам теоремы 2, через Fj(i,k,k'). В силу теоремы 2 оптимальное решение исходной задачи М =< М\. М2; N > (обозначим его F*) вычисляется следующим образом

F* = min Fi(i,k,k'). ieMi,fc,fc'eM2

В заключении раздела 2.2 обосновываются рекуррентные формулы для вычисления величин /<}(г, /г, к') для всех значений ] € И, г 6 М\, к,к' Е М2.

В разделе 2.3 приводится описание алгоритма Ацп.р для точного решения двухуровневой задачи размещения на дереве, а также устанавливается, что трудоемкость алгоритма не превосходит 0(пт3), где т — максимальное число возможных пунктов производства на каждом из этапов. Данный алгоритм имеет лучшую трудоемкость из всех, известных на текущий момент в литературе.

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

В разделе 3.1 приводится постановка задачи. Пусть задан неориентированный граф О со множеством вершин V, = п, и множеством ребер Е, которое генерируется случайным образом — любая пара вершин соединяется ребром независимо от остальных с заданной вероятностью р, 0 < р < 1. Необходимо найти совершенное паросочетание в графе О.

Для данной задачи в работе [3] представлен приближенный алгоритм решения и доказано следующее утверждение: для любого а > 0 существует такая константа /? > 0, что если р(п) > 131°г^п, то с временной сложностью 0(п к^ п) алгоритм находит совершенное паросочетание в графе с вероятностью 1 — 0(п~а). Стоит отметить, что в [3] значения а и /3 не представлены в явном виде, что существенно ограничивает возможность применения данного алгоритма. В диссертации предлагается новый алгоритм решения задачи, который имеет аналогичную трудоемкость О(п^п), но при этом является более простым в понимании и имеет оценки точности, выраженные в явном виде.

В разделе 3.2 приводится описание алгоритма поиска совершенного паросочетания Лрм, который состоит из двух этапов.

Этап 1 Выделяем в б путь Ь заданной длины. Считаем, что все вершины пути Ь покрашены в белый цвет, вершины У\Ь по-

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

Этап 2 Строим совершенное паросочетание Р. Этап состоит из последовательного выполнения следующих шагов:

Шаг г, г > 1. Находимся в 7-ой вершине пути Ь (на шаге 1 находимся в первой вершине пути). Просматривая ее список смежности, ищем ребро, инцидентное какой-либо из черных вершин. Возможны два варианта:

1. Такое ребро существует. Тогда к Р добавляем данное ребро и красим вторую вершину в белый цвет. Берем (] + 1)-ую вершину пути Ь и переходим к следующему шагу.

2. Такого ребра не существует. Тогда к Р добавляем ребро, соединяющее j-yю и (] + 1)-ую вершину пути Ь. Берем (j + 2)-ую вершину пути Ь и переходим к следующему шагу.

Действуем таким образом, пока не дойдем до конца пути Ь. Если при этом все вершины графа окажутся покрашены в белый цвет, то второй этап сработал успешно и совершенное паросочетание Р построено. В противном случае считаем, что произошло несрабатывание алгоритма.

В разделе 3.3 показано, что трудоемкость алгоритма Лрм имеет порядок 0(п2р).

В разделе 3.4 проводится подробный вероятностный анализ алгоритма. Для исследования качества приближенного алгоритма используется определение алгоритмов с оценками (е, 5), предложенное Э.Х. Гимади, Н.И. Глебовым и В.А. Перепелицей. Будем говорить, [то алгоритм Л имеет оценки точности (еп, 6п) в классе Кп зада : минимизации размерности п, если выполнено неравенство

Р1——

— оптимальное решение для индивидуальной задачи 1п, хл ение, полученное при помощи алгоритма Л, Р{5} — веро-

ятность события 5, еп — относительная погрешность получаемого решения, 5п — вероятность несрабатывания алгоритма Л.

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

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

Теорема 3. При р > А > 4, алгоритм Лрм отыскания со-

вершенного паросочетания в случайном графе является асимптотически точным и имеет вероятность несрабатывания О .

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

Теорема 4. Прир > А > 4, алгоритм Лрм за время 0(п к^п)

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

В разделе 3.6 рассматривается применение алгоритма Лрм к случайному двудольному графу. Рассматривается двудольный граф С? со множеством вершин V = 5иТ, |5| = п, \Т\ = п. Каждое ребро, соединяющее вершину 5 6 5 с вершиной I £ Г, появляется независимо от других ребер с вероятностью р. Доказывается следующее утверждение

Теорема 5. Прир > А > 4, алгоритм Арм за время 0{п log п)

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

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

В разделе 4.1 рассматривается задача размещения с одинаковыми ограничениями на объемы производства. В пункте 4.1.1 приводится постановка задачи:

тп т п

с(х) = X giXi+X) X] 9iixiimin' (5) t=1 t=1 .7=1 Xi'Xij

т

= bj, j e J, (6)

i=1 n

Y,Xij<diXi, iel, (7)

3=1

Xij >0, Xi e {0,1}, i €l, j€ j. (8)

В данном разделе считаем, что объемы производства всех предприятий одинаковые

di = d, iel. (9)

Дополнительно предполагается, что транспортные расходы gij, г € I,j е J, — значения, заданные независимыми случайными величинами из класса U[l,r] (класс случайных величин, равновероятно принимающих значения из целочисленного сегмента [1,г], г — заданное целое число).

В пунктах 4.1.2—4.1.3 вводятся некоторые вспомогательные определения и описывается идея алгоритма решения. Через то обозначим минимальное количество предприятий, необходимое для удовлетворения потребностей всех пунктов спроса то = [X^eJ ^'ЛЛ •

Через /о обозначим набор из то предприятий множества I, имеющих наименьшую стоимость открытия. Для некоторых целых fc > 0 и mo > t > 0 имеет место разложение п — кто + t. Разобьем множество J на к+1 подмножеств J\,..., -h.+i следующим образом

Ji =

Js = {t + (s - 2)m0 + 1, ■ ■ •, t + (s - l)mo}, 2 < s < fc + 1.

Открыв предприятия в пунктах из /о, мы получаем транспортную задачу по доставке продукта из пунктов множества /о в пункты множества J. Рассмотрим транспортные задачи (/q. Js), 1 < s < к + 1, в каждой из которых требуется поставить продукт из /о в Js. Решение каждой задачи (/о, Js), 1 < s < к, будем искать, используя только коммуникации единичной стоимости (для которых gtj = 1). Причем ищем такое решение, в котором каждый производитель из 1о обслуживает ровно одного потребителя из Js) 1 < s < fc, и полностью удовлетворяет его спрос. Для решения каждой такой подзадачи используется алгоритм Лрм, построенный в главе 3. Если таким образом мы построим решение для всех задач (/q, Js). 1 < s < fc, то тем самым мы построим оптимальное решение транспортной задачи (Io,Ug=lJs). Для транспортной задачи (/о, Jk+i) возьмем произвольное допустимое решение. Объединение решений для задач (70, Js), 1 < s < fc+1 даст нам решение задачи (Jo, J).

В пункте 4.1.4 проводится вероятностный анализ построенного алгоритма и доказывается следующее утверждение (здесь В(п) — максимальная из потребностей пунктов спроса, В(п) = maxjejbj):

Теорема 6. При р > А > 10, т0 = пв для в б^^, и

В(п) = о^п1-20^ алгоритм решения задачи размещения (5) — (9)

на входных данных, заданных случайными величинами из класса U[l, г], имеет трудоемкость 0(п log то), относительную погрешность и вероятность несрабатывания О^п1-0-^-^.

В разделе 4.2 рассматривается задача размещения с произвольными ограничениями на объемы производства. В пункте 4.2.1 дается постановка задачи, которая отличается от представленной в пункте 4.1.1 лишь отсутствием ограничения (9).

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

В пункте 4.2.3 проводится вероятностный анализ алгоритма и доказывается следующее утверждение (здесь Отах{п) и Огпги(п) — максимальная и минимальная мощность предприятий из I соответственно):

Теорема 7. При р > Л > 10, т0 = п° для в и

В(п) = о^п1'29^, Отах(п) - МшпЫ = О^п1-20^ алгоритм решения задачи размещения (5)-(8) на входных данных, заданных случайными величинами из класса £/[1,г], имеет трудоемкость 0{п2{1~в>>т), относительную погрешность и вероятность несрабатывания О^п1^0-^-^.

Список литературы

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

[2] 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.

[3] 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.

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

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

[5] Агеев А. А., Гимади Э.Х., Курочкин А. А. Полиномиальный алгоритм решения задачи размещения на цепи с одинаковыми производственными мощностями предприятий // Дискретный анализ и исследование операций (DAOR). - Новосибирск: Изд-во Ин-та математики, 2009. - Т. 16, № 5. - С. 3-18.

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

[7] Gimadi Е. Kh., Kurochkin A. A. Uniform Capacitated Facility Location Problem with Random Input Data // Journal of Mathematical Sciences. - New York : Springer, 2013. - Vol. 188, No. 4. - P. 359-377.

[8] Гимади Э.Х., Курочкин А. А. Эффективный алгоритм решения двухэтапной задачи размещения на древовидной сети // Дискретный анализ и исследование операций. - Новосибирск: Изд-во Ин-та математики, 2012. - Т. 19, № 6. - С. 9-22.

[9] Gimadi Е. Kh., Kurochkin A. A. An effective algorithm for the two-stage location problem on a tree-like network // Journal of Applied and Industrial Mathematics. - Pleiades Publishing, 2013. - Vol. 7, Issue 2. - P. 177-186.

[10] Kurochkin A. A., Gimadi E.K., Ageev A. A. The uniform capacitated flp on path network // Proc. of the 23rd European Conference on Operational Research (Bonn, Germany, July 5-8, 2009). - 2009, Germany. - P. 232.

[11] Курочкин А. А. Асимптотически точный алгоритм решения задачи размещения с одинаковыми объемами производства на случайных входных данных // Международная конференция Дискретная Оптимизация и Исследование Операций (Новосибирск, 24-28 июня, 2013): Материалы конференции. - Новосибирск: Изд-во Ин-та математики, 2013. - С. 124.

[12] Kurochkin A., Gimadi E. Some polynomially solvable cases of hard Facility Location Problems // Proc. of 26th Conference of the European Chapter on Combinatorial Optimization (Paris, France, May 30 - June 1). — France, 2013. - P. 119.

[13] Kurochkin A., Gimadi E. Effective algorithms for some hard Facility Location Problems // Proc. of International Symposium on Combinatorial Optimization 2012 (University of Oxford, UK, September 17-19, 2012). - United Kingdom, 2012. - P. 65.

[14] Курочкин А. А., Гимади Э.Х. Полиномиальный алгоритм решения двухуровневой задачи размещения на дереве / / XIV-я Всероссийская конференция "Математическое программирование и приложения "(Екатеринбург, 28 февраля - 4 марта, 2011): Материалы конференции. - Екатеринбург, 2011. - С. 78.

[15] Kurochkin A., Gimadi Е. Effective algorithm for the two-stage FLP on the tree network // Proc. of 4th Optimal Discrete Structures and Algorithms Conference (Rostock, Germany, September 13-15, 2010).- Germany, 2010. - P. 103.

[16] Курочкин А. О двух задачах размещения с одинаковыми объемами производства // XLVII Международная научная студенческая конференция (Новосибирск, 11-15 апреля, 2009): Материалы конференции. - Новосибирск, 2009. - С. 122.

[17] Курочкин А. Асимптотически точный алгоритм отыскания паросочетания минимального веса в полном графе со случайными весами // XLVI Международная научная студенческая конференция (Новосибирск, 26-30 апреля, 2008): Материалы конференции. - Новосибирск: Изд-во НГУ, 2008. - С. 84.

Курочкин Александр Александрович

Алгоритмы с оценками для некоторых задач размещения производства

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 13.01.2014 Формат 60x84 1\16 Усл. печ. л. 1,25 Объем 20 стр. Тираж 120 экз. Заказ №24

Отпечатано Омега Принт 630090, г. Новосибирск, пр. Ак.Лаврентьева,6 email: omegap@yandex.ru

СИБИРСКОЕ ОТДЕЛЕНИЕ РАН ИНСТИТУТ МАТЕМАТИКИ ИМ. С. Л. СОБОЛЕВА

На правах рукописи

0*201 4 5 ¿030

Курочкин Александр Александрович

АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ РАЗМЕЩЕНИЯ ПРОИЗВОДСТВА

01.01.09 — дискретная математика и математическая

кибернетика

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук Гимади Э.Х.

Новосибирск 2014

Оглавление

Введение 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение 98

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

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

Литература 103

Введение

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

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

С{х) —> 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] также установил, что прост