Алгоритмы с оценками для некоторых комбинаторных задач маршрутизации, размещения и планирования тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Штепа Александр Александрович
Штепа Александр Александрович
кандидат наук
2023
- Специальность ВАК РФ00.00.00
- Количество страниц 109
Оглавление диссертации кандидат наук Штепа Александр Александрович
Введение
Глава 1. Сетевая задача размещения с ограничениями на
объемы производства предприятий
1.1 Предварительные сведения
1.2 Постановка задачи и базовые обозначения
1.3 Задача UCFLP на звезде
1.4 Задача UCFLP на цепи
1.4.1 Свойства оптимальных решений
1.4.2 Полиномиальный алгоритм решения
1.5 Задача CFLP на цепи
1.5.1 Алгоритм динамического программирования
1.5.2 Улучшенный алгоритм решения
Глава 2. Задача ресурсно-календарного планирования
2.1 Предварительные сведения и обзор литературы
2.2 Постановка задачи
2.3 Постановка задачи с нескладируемыми ресурсами
2.4 Постановка задачи со складируемыми ресурсами
2.5 Быстрый точный алгоритм для ЗРКПСТ
2.6 Численные эксперименты
Глава 3. Задача поиска остовного дерева экстремального веса
с фиксированным диаметром
3.1 Предварительные сведения
3.2 Нахождение m реберно-непересекающихся остовных деревьев минимального суммарного веса с фиксированным диаметром d в полном неориентированном графе
3.3 Вероятностный анализ алгоритма Л для задачи m-d-UMinST
3.3.1 Распределение UNI(ап; Ьп)
3.3.2 Распределение EXP(an, Лп)
3.3.3 Распределение NORM(an, ап)
3.4 Задача поиска максимального остовного дерева с фиксированным диаметром И в полном неориентированном графе
3.5 Вероятностный анализ алгоритма Лтах для D-UMaxST
Заключение
Список литературы
Дискретная оптимизация, изучающая комбинаторные задачи, как самостоятельная целостная математическая дисциплина, относительно молода. На заре становления этой области математики можно было наблюдать ряд независимых направлений исследований, отдельно рассматривающих такие задачи, как оптимальное назначение, минимальное остовное дерево, транспортная задача и задача коммивояжера. Только в 1950-х годах, когда стал доступен объединяющий инструмент линейного и целочисленного линейного программирования, эти проблемы были объединены в единую структуру и установлены связи между ними.
Действительно, линейное программирование является поворотным моментом в истории дискретной оптимизации. Его первоначальная концепция, предложенная Л. В. Канторовичем и Т. Купмансом, была мотивирована приложениями, в частности, при решении задачи транспортировки грузов. После формулировки линейного программирования как общего вида задачи и разработки Дж. Данцигом в 1947 году симплекс-метода как инструмента решения, все проблемы дискретной оптимизации пытались решать с помощью методов линейного программирования, довольно часто успешно.
Однако при дальнейшей работе в этой области исследователи все чаще стали сталкиваться с задачами, которые не могут быть преобразованы к требуемому виду задачи линейного программирования, и неразрешимы с помощью симплекс-метода из-за дискретности множества допустимых решений, содержащего огромное количество целочисленных решений. В 1957 году Р. Беллманом даже обсуждалось "проклятие размерности", в том смысле, что специалисты в области исследования операций были способны решать задачи дискретной оптимизации только небольших размерностей, и в то время было непонятно, как решать реальные, встречающиеся на практике задачи с сотнями и тысячами параметров. Тем не менее на рубеже 80-х годов прошлого века, благодаря работам С. Кука, Р. Карпа и Л. А. Левина, а также книге М. Гэри и Д. Джонсона, эти ощущения сменились на более определенное понимание вопроса о сложности решения задач дискретной оптимизации.
где f (х) - целевая функция задачи, Q — дискретное множество допустимых решений, вместо extr может быть min или max. Такая задача называется общей, если же все параметры задачи принимают конкретные значения, то такая задача называется индивидуальной (или входом). Целевая функция выражает критерий, по которому сравниваются допустимые решения, а наилучшее по этому критерию решение называется оптимальным. Существуют различные целевые функции для задач дискретной оптимизации, например, время завершения всех работ проекта (задача календарного планирования), суммарная ценность предметов (задача о рюкзаке), суммарные затраты на открытие предприятий и обслуживание всего спроса клиентов (задача размещения). В то же время целевые функции могут быть различны в рамках одной задачи, например, в задаче о рюкзаке можно задаться целью максимизировать суммарную ценность предметов при ограничении сверху на их суммарный вес, или минимизировать суммарный вес предметов при ограничении снизу на их суммарную ценность.
За годы исследований разработано большое количество алгоритмов на основе совершенно различных идей для решения задач дискретной оптимизации. И подбор определенного алгоритма для конкретной задачи давно уже стал искусством. Существующие алгоритмы можно разделить на: точные алгоритмы, приближенные алгоритмы с априорной оценкой качества (данные алгоритмы на любых входных данных ошибается не более, чем в определенное количество раз), а также эвристические и метаэвристические алгоритмы, которые хорошо работают на практике, но для них не получены теоретически обоснованные априорные оценки качества.
Эвристический алгоритм разрабатывается под конкретную задачу. Мета-эвристический алгоритм — это независимый от задачи метод, который можно применять к широкому кругу проблем. Так к эвристическим алгоритмам можно отнести способ каким выбираются ведущие случайные элементы при
f (х) ^ extr
(1)
же Q
(2)
реализации алгоритма быстрой сортировки. Примерами метаэвристических алгоритмов могут служить: генетический алгоритм, алгоритм имитации отжига, локальный поиск (для детального обзора метаэвристик см. монографию [1]).
Далее потребуется ввести ряд определений. Входная длина индивидуальной задачи I — это число символов, необходимых для кодирования ее исходных данных. Например, для задачи о рюкзаке нужно задать веса Wi и стоимости q п предметов, таким образом с помощью двоичного кодирования входная длина не превышает величины 2пmax log2{wi,Ci}. Для оценки того, насколько быстро работает алгоритм используется понятие трудоемкости (временной сложности), то есть функции, которая входной длине п ставит в соответствие максимальное (по всем индивидуальным задачам длины п) количество элементарных операций, затрачиваемое алгоритмом на решение индивидуальных задач этой длины. К элементарным операциям относятся присваивание значения переменной, доступ к элементу массива по индексу, конструкции условной (if...then...else) и безусловной (goto) передачи управления, а также простейшие арифметические операции, если они производятся над числами, малыми по сравнению с длиной входа задачи: сложение, вычитание, умножение, деление и сравнение чисел [2]. Понятие трудоемкости вводится для того, чтобы сравнивать скорости работы алгоритмов, а также определить, какие алгоритмы можно считать быстрыми, а какие нет. Для этого синонимом быстрого служит понятие полиномиального алгоритма. Полиномиальным называется алгоритм, чья временная сложность оценивается величиной 0(р(п)), где р(п) — некоторый полином от длины входа п, задачи, для которых существует точный алгоритм решения, называются полиномиально разрешимыми. Алгоритмы, временная сложность которых не поддается подобной оценке, называются экспоненциальными, а соответствующие задачи — труднорешаемыми.
Ранее упомянутые в данной работе задачи такие, как задача размещения, задача ресурсно-календарного планирования и другие, были задачами оптимизации, т.е. представимыми в виде (1)-(2) с явным выражением целевой функции и множеством допустимых значений, однако из соображений удобства теория труднорешаемых задач строится для задач распознавания свойств (что дает возможность отождествить решение такой задачи с распознаванием соответствующего языка и применить уже разработанный анализ языков и машин Тьюринга [3]). Задача распознавания свойств (или задача распознавания) -это общая задача, решением которой является ответ "да" или "нет". Например,
верно ли что у задачи размещения существует решение, стоимость которого не превосходит значения Г € N. Нетрудно понять, что если рассматривается оптимизационная задача на минимум, то этой задаче можно сопоставить задачу распознавания, для которой в качестве дополнительного параметра фигурирует числовая граница Г, а соответствующий вопрос ставится о существовании решения, значение целевой функции которого не превосходит Г. Аналогично может быть получена задача распознавания для оптимизационной задачи на максимум.
Задачи распознавания свойств, для точного решения которых существует полиномиальный алгоритм, образуют класс V. Или, более формально, класс V — это класс задач распознавания, разрешимых за полиномиальное время на детерминированной машине Тьюринга. Класс МГР образуют задачи распознавания, верифицируемые (проверяемые) за полиномиальное время. Неформально класс МГР можно определить с помощью понятия "недетерминированный алгоритм". Такой алгоритм состоит из двух различных стадий — стадии угадывания и стадии проверки. По заданной индивидуальной задаче X на первой стадии происходит просто "угадывание" некоторой структуры Б. Затем X и Б вместе подаются в качестве входа на стадию проверки, которая выполняется обычным детерминированным образом и либо заканчивается ответом "да", либо заканчивается ответом "нет", либо продолжается бесконечно без остановки (как показано в [3] последние две возможности различать необязательно). Недетерминированный алгоритм "решает" задачу распознавания П, если для любой индивидуальной задачи X выполнены следующие 2 свойства:
1. Если ответом для индивидуальной задачи X будет "да", то существует такая структура Б, угадывание которой для входа X приведет к тому, что стадия проверки, начиная работу на входе (X, Б), закончится ответом "да".
2. Если ответом для индивидуальной задачи X не будет "да", то не существует такой структуры Б, угадывание которой для входа X обеспечило бы окончание стадии проверки на входе (X, В) ответом "да".
Иначе, класс МГР включает в себя все задачи распознавания, разрешимые за полиномиальное время на недетерминированной машине Тьюринга. Стоит отметить, что разрешимость за полиномиальное время влечет проверяемость, для такой верификации можно просто еще раз решить задачу, т.е. верно включение
Задача о совпадении или несовпадении классов V и МГР является одной из центральных задач исследования операций. Если эти классы совпадают, тогда любую задачу из класса МГР можно решить за полиномиальное время. В текущей работе к рассматриваемым задачам в общей постановке могут быть сведены задачи из МТ, не нарушая полиномиальности гипотетического алгоритма (см. далее понятие полиномиальной сводимости). Если гипотеза о совпадении этих классов верна, то для каждой из них существует полиномиальный алгоритм решения. В противном случае, к чему склоняется большинство исследователей, такого полиномиального алгоритма не существует. Драматизм ситуации состоит в том, что доказательство (или опровержение) совпадения этих классов к настоящему времени не получено.
Пусть Мах(Х) - некоторая функция, задающая значение максимального числового параметра индивидуальной задачи X размера п, а если задача не имеет числовых параметров, то Мах(Х) = 0. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости 0^р(п,Мах(Х, где р(х,у) -некоторый полином от двух переменных, т.е. в трудоемкость такого алгоритма могут входить числовые параметры задачи. Например, для задачи о рюкзаке с п предметами и вместимостью рюкзака W существует псевдополиномиальный алгоритм динамического программирования решения с трудоемкостью 0{лШ).
Общая задача р полиномиально сводится к общей задаче ф2, если для любой индивидуальной задачи Х1 € ф1 за полиномальное время можно построить индивидуальную задачу Х2 € ф2, а по оптимальному решению х2, задачи Х2 можно за полиномиальное время построить оптимальное решение х* задачи Х1. Задача распознавания называется МТ-полной, если выполняются два условия: первое, она принадлежит классу МТ, и второе, любая задача из МТ полиномиально сводится к ней. Если выполняется только второе условие, то задача называется МТ-трудной (труднорешаемой). Таким образом, МТ-полные задачи являются в некотором смысле "самыми трудными" задачами в классе МТ, а МТ-трудные задачи — необязательно задачи распознавания свойств, а могут быть и задачами оптимизации, т.е. задачами нахождения экстремума целевой функции в некоторой области конечномерного векторного пространства.
Задача называется МТ-полной (МТ-трудной) в сильном смысле, если существует полином от входной длины п такой, что эта задача остается МТ-полной (^"Р-трудной) для всех индивидуальных задач X, у которых максимальный числовой параметр Мах(Х) ограничен этим полиномом от входной
длины п. Стоит отметить, что .^""Р-полная в сильном смысле задача должна принадлежать классу MV.
В 1971 году американский математик С. Кук в работе [4] доказал, что к задаче о выполнимости сводится любая другая из класса MV, затем в 1972 году [5] были сформулированы 21 задача, которые являются "самыми трудными" в классе MV, и позже эти задачи стали называть ^""Р-полными. Схожие идеи, касающиеся задачи о выполнимости, были независимо предложены в то же время советским математиком Л. А. Левиным [6].
Интересно, что даже небольшие изменения условий задачи могут приводить к тому, что полиномиально разрешимая задача становится MV-трудной, и наоборот. Например, задача поиска минимального остовного дерева — полиномиально разрешима, а ее модификация, задача поиска минимального остовного дерева с ограниченным снизу диаметром — является MV-трудной [7]. Простейшая задача размещения на цепи решается за линейное время [8], если наложить ограничения на объемы производства предприятий, то в такой постановке задача на цепи NT-трудна [9]. В работе [10] показано, что задача размещения с одинаковыми объемами производства предприятий на графе-звезде ^""Р-трудна, если в каждой вершине графа находятся и возможное место открытия предприятия, и клиент, а в текущей работе для случая этой задачи, если в каждой вершине звезды находится возможное место размещения производства либо клиент построен алгоритм с линейной трудоемкостью.
Большинство задач дискретной оптимизации, в том числе интересных с практической точки зрения, .^"Р-трудны, а вопрос о совпадении или несовпадении классов Р и MV остается открытым, поэтому в этих условиях актуальными становятся исследования по разработке и обоснованию полиномиальных приближенных алгоритмов для труднорешаемых задач дискретной оптимизации с, как можно, более хорошими оценками их качества. Основные усилия специалистов по методам дискретной оптимизации направлены в сторону развития новых методов построения эффективных точных и приближенных алгоритмов, поиска полиномиально разрешимых частных случаев этих задач и получения как положительных, так и отрицательных результатов, касающихся существования алгоритмов с определенными свойствами для рассматриваемых задач.
Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Эффективные алгоритмы с гарантированными оценками точности для некоторых обобщений задачи коммивояжера2018 год, кандидат наук Незнахина Екатерина Дмитриевна
Некоторые наследственные случаи полиномиальной и псевдополиномиальной разрешимости задач о вершинной раскраске графов2021 год, кандидат наук Развенская Ольга Олеговна
Исследование математических моделей и построение алгоритмов с оценками для векторных задач об остовных деревьях2000 год, кандидат физико-математических наук Зинченко, Ольга Алексеевна
Задачи об оптимальном соединении в пространствах компактов2016 год, кандидат наук Овсянников Захар Николаевич
Исследование оптимизационных моделей сетей сбора и передачи данных при ресурсных ограничениях2013 год, кандидат наук Плотников, Роман Викторович
Введение диссертации (часть автореферата) на тему «Алгоритмы с оценками для некоторых комбинаторных задач маршрутизации, размещения и планирования»
Актуальность и степень разработанности темы исследования.
В текущей работе рассматриваются следующие задачи дискретной оптимизации:
— задача ресурсно-календарного планирования,
— задача отыскания одного или нескольких реберно-непересекающихся остовных деревьев экстремального суммарного веса с фиксированным диаметром в полном графе.
Все рассматриваемые задачи в общей постановке являются MV-трудными, т.е. в предположении V = MV, для них не существует быстрых точных алгоритмов, а общие известные подходы для решения таких задач большой размерности малоэффективны. Поэтому перспективно исследовать частные случаи этих задач, для которых существуют полиномиальные алгоритмы решения, или строить приближенные и асимптотически точные алгоритмы, последние с ростом размерности задачи строят все более точные решения. Далее будут кратко приведены постановки исследуемых задач и их приложения.
В сетевой задаче размещения с ограничениями на объемы производства предприятий (Capacitated Facility Location Problem, CFLP) задан граф транспортной сети, в вершинах которого находятся возможные места размещения предприятий и клиенты. Предприятия производят некоторый продукт, а клиенты его потребляют. Для каждого возможного места размещения предприятия известны стоимость открытия и объем производства, т.е. максимальное количество продукта, которое данное предприятие может произвести. Для каждого клиента известен его целочисленный спрос в продукте, а для каждой пары: возможное место размещения предприятия, клиент — транспортные затраты по доставке единицы продукта из предприятия клиенту. Требуется открыть подмножество предприятий для обслуживания спроса всех клиентов так, чтобы минимизировать затраты на открытие предприятий и транспортировку продукта клиентам. Эта задача часто встречается на практике, когда нужно разместить склады, школы или больницы для обслуживания клиентов. Задача CFLP может быть рассмотрена, как задача кластеризации, в которой учитываются затраты на выбор определенной вершины в качестве центра кластера, и для каждого центра задано ограничение сверху на максимальное количество экземпляров, назначенных на него. Задачи кластеризации, в свою очередь, имеют первостепенную важность в анализе данных.
Если объемы производства предприятий одинаковые, то такая задача называется однородной сетевой задачей размещения с ограничениями на объе-
мы производства предприятий (Uniform Capacitated Facility Location Problem, UCFLP).
В данной работе исследуются задачи CFLP и UCFLP, в которых исходный граф является простейшим частным случаем дерева — звездой и цепью. Актуальность данных задач обусловлена их приложениями. Так, например, задача CFLP на цепи может возникать при размещении понижающих трансформаторов высоковольтной линии электропередач в сельской местности, создании областей отдыха вдоль скоростного шоссе, составлении расписаний поставок от ритейлера к домохозяйствам, расположенным по соседству [9]. Если считать, что размещаемые объекты одинаковы по характеристикам, то получим примеры приложений для задачи UCFLP на цепи. Также такие постановки задач размещения на цепи и звезде могут встречаться при размещении объектов в малонаселенных областях, например, в условиях Крайнего Севера.
В работе [10] О. Ю. Цидулко доказала, что уже на звезде задача UCFLP становится ^""Р-трудной, если в каждой вершине графа могут одновременно размещаться и предприятие, и клиент, из чего следует, что эта задача на дереве также ^"Р-трудна.
Следующая задача, которая исследуется в данной работе, — это задача ресурсно-календарного планирования (ЗРКП). В этой задаче требуется выполнить набор работ, образующих проект, с ограничениями на предшествование работ и требуемые ресурсы для их выполнения так, чтобы время завершения всего проекта было минимально. Приложения задачи ЗРКП естественным образом возникают при планировании крупномасштабных проектов, например, Байкало-Амурской магистрали (БАМ) [11; 12], выполнении текущих заданий процессором компьютера, составления расписаний последовательности действий для станков на заводе, и др.
Известно, что задача ЗРКП без директивных сроков, но с ограничениями на отношение предшествования и одним нескладируемым ресурсом является MV-трудной в сильном смысле [3].
Задача отыскания минимального остовного дерева с ограниченным диаметром — это хорошо изученная задача дискретной оптимизации. Диаметр дерева — это количество ребер в самом длинном простом пути в дереве, соединяющем пару вершин. Рассматриваются задачи с ограничением на диаметр сверху [13—15] или снизу [7; 16], обе задачи являются .^"Р-трудными в общем случае.
Недавно автором текущей работы начала изучаться другая модификация задачи отыскания минимального остовного дерева с ограниченным диаметром, а именно, когда диаметр искомого дерева фиксирован, т.е. равен заданному целому числу. В данной работе рассматривается задача поиска нескольких ре-берно-непересекающихся остовных деревьев минимального суммарного веса с фиксированным диаметром в полном неориентированном графе, эта задача исследуется для различных вероятностных распределений весов ребер графа: равномерное, смещенное усеченно-экспоненциальное и смещенное усеченно-нормальное.
В работах [17; 18] предложен вероятностный анализ эффективного алгоритма для решения задачи поиска минимального остовного дерева с фиксированным диаметром в полном ориентированном графе. К сожалению, анализ алгоритма, представленный в этих работах, невозможно применить в случае полных неориентированных графов, по причине того, что в случае неориентированных графов нужно как-то учитывать возможную зависимость между случайными величинами, соответствующими ребрам графа, которые уже рассматривались ранее в ходе алгоритма.
Алгоритм решения задачи с фиксированным диаметром может быть преобразован в алгоритм решения задач отыскания остовных деревьев с ограничением на диаметры как сверху, так и снизу. Таким образом, приложения для задач с ограничением сверху или снизу справедливы и для рассматриваемой задачи, что подтверждает ее актуальность. Так, условие ограниченного сверху диаметра возникает в силу требований на качество связи элементов остовного дерева, например, в беспроводных сетях [19], в разработке коммуникационных сетей [20], а также в алгоритмах сжатия [21] и распределенного взаимного исключения [22].
Задача отыскания т реберно-непересекающихся остовных деревьев минимального суммарного веса с диаметром ограниченным снизу в полном графе встречается в проблемах теории надежности коммуникационных сетей, когда необходимо для множества выбранных объектов построить т-связный минимальный по весу граф, исключив при этом конфигурации, для которых после выхода из строя небольшого количества вершин графа, резко ухудшается структура сети, т.е. наложить условие на диаметр снизу для каждого из конструируемых остовных деревьев, формирующих т-связный граф.
Также в текущей работе изучается задача поиска максимального остов-ного дерева. Если не накладывать ограничения на диаметр, то такая задача полиномиально разрешима, и может быть решена, например, алгоритмом Дж. Краскала с предварительной обработкой весов ребер графа. Однако эта задача с условием фиксированного диаметра труднорешаема. Задача отыскания максимального остовного дерева с фиксированным диаметром рассматривается в полном неориентированном графе, веса ребер которого распределены согласно равномерному распределению И№(0; 1).
Целью данной работы является построение эффективных алгоритмов с оценками качества для решения задач дискретной оптимизации таких, как задача размещения с ограничениями на объемы производства предприятий, задача ресурсно-календарного планирования, задача отыскания одного или нескольких реберно-непересекающихся остовных деревьев экстремального веса с фиксированным диаметром.
Основные результаты диссертации:
1. Для однородной задачи размещения с ограничениями на объемы производства предприятий на звезде, если в каждой вершине звезды может располагаться либо возможное место размещения предприятия, либо клиент, разработан точный алгоритм с трудоемкостью 0(т + п), где т — количество возможных мест размещения предприятий, п — количество клиентов.
2. Предложена модификация известного алгоритма А. А. Агеева для однородной задачи размещения с ограничениями на объемы производства на цепи, улучшающая время работы алгоритма с 0(т3п2) до 0(т2п2), где т — количество возможных мест размещения предприятий, п — количество клиентов, что является лучшим возможным временем работы в рамках рассматриваемой схемы динамического программирования.
3. Построена модификация точного псевдополиномиального алгоритма П. Мирчандани и др. для задачи размещения с ограничениями на объемы производства предприятий на цепи, уменьшающая трудоемкость с О(тВ шж{атах,В}) до 0(тВ), где т — количество возможных мест размещения предприятий, В — суммарный спрос клиентов, атах — максимальный объем производства предприятия.
4. Для решения задачи ресурсно-календарного планирования со складируемыми ресурсами предложен точный алгоритм с трудоемкостью О^и + п[К + 1о§2п)^, где и — число дуг в графе С отношения предшествования на множестве работ, п — число работ, К — число типов ресурсов. Тем самым разработан быстрый алгоритм отыскания нижней оценки для задачи ресурсно-календарного планирования с нескладиру-емыми ресурсами.
5. Построен приближенный алгоритм с трудоемкостью 0(п2), где п -количество вершин в графе, для нахождения нескольких реберно-непересекающихся остовных деревьев минимального суммарного веса с фиксированным диаметром в полном неориентированном графе, и установлены достаточные условия асимптотической точности алгоритма в случаях, когда веса ребер распределены согласно равномерному распределению, и смещенным усеченным распределениям: экспоненциальному и нормальному.
6. Разработан приближенный алгоритм с временной сложностью 0(п2), где п — количество вершин в графе, для нахождения максимального остовного дерева с фиксированным диаметром в полном неориентированном графе, и получены условия асимптотической точности этого алгоритма в случае равномерного распределения на интервале (0; 1) весов ребер графа. Из проведенного вероятностного анализа следует аналогичный результат для равномерного распределения на интервале (ап; Ьп) весов ребер графа.
Методы исследования. В работе применялись методы дискретной оптимизации, исследования операций и теории графов, методы вероятностного анализа работы алгоритмов, а также метод динамического программирования.
Научная новизна и значимость работы. Все результаты, представленные в работе, являются новыми. Работа носит теоретический и прикладной характер. Полученные алгоритмы могут быть использованы при решении соответствующих прикладных логистических задач и задач ресурсно-календарного планирования.
На защиту выносится совокупность результатов, связанных с построением эффективных алгоритмов и доказательством их оценок качества, для
однородной и неоднородной задач размещения с ограничениями на объемы производства предприятий, задачи ресурсно-календарного планирования, задачи отыскания нескольких реберно-непересекающихся остовных деревьев минимального суммарного веса с фиксированным диаметром в полном неориентированном графе, а также задачи поиска одного остовного дерева максимального веса с фиксированным диаметром в полном неориентированном графе.
Апробация работы. Результаты работы в разные годы докладывались на всероссийских и международных конференциях: «Проблемы оптимизации сложных систем, OPCS» (очно, Новосибирск, 2019 г.), «Conference on Analysis of Images, Social Networks and Texts, AIST» (онлайн, Москва, 2020 г.), «Mathematical Optimization Theory and Operation Research, MOTOR» (онлайн, Новосибирск, 2020 г.), «Optimization and Applications, OPTIMA» (онлайн, Москва, 2020 г.), «Mathematical Optimization Theory and Operation Research, MOTOR» (смешанный режим, Иркутск, 2021 г.), «International Conference on Operations Research, OR» (онлайн, Берн, Швейцария, 2021 г.), «Conference on Analysis of Images, Social Networks and Texts, AIST» (смешанный режим, Москва-Тбилиси, 2021 г.), «Проблемы оптимизации сложных систем, OPCS» (очно, с. Кара-Ой (оз. Иссык-Куль), Киргизия, 2022 г.), «Интеллектуализация обработки информации, IDP» (смешанный режим, Москва, 2022 г.), а также на научном семинаре «Дискретные Экстремальные Задачи» Института Математики им. С.Л. Соболева СО РАН.
Публикации. Основные результаты по теме диссертации изложены в 10 работах [10; 17; 23—30], в том числе 4 статьи в научных журналах из списка ВАК [10; 23—25], 5 — в изданиях, которые индексируются в базе SCOPUS [17; 27—30], 1 публикация в трудах международной конференции [26].
Личный вклад. Постановки задач предложены научным руководителем. Разработка алгоритмов осуществлена совместно. Доказательства утверждений выполнены соискателем самостоятельно. Конфликт интересов с соавторами отсутствует.
Структура и объем диссертации. Диссертация изложена на 109 страницах с 7 рисунками и 4 таблицами, содержит введение, три главы, заключение, список публикаций автора по теме диссертации, благодарности и список литературы, состоящий из 107 источников.
Содержание работы. Во введении приведены основные понятия и идеи, которые будут использованы в дальнейшем изложении, обоснована актуальность выбранной темы, приведены цели работы, сформулированы основные результаты и научная новизна.
Первая глава посвящена сетевой задаче размещения с ограничениями на объемы производства. Эта задача рассмотрена в однородной постановке на графе-звезде и графе-цепи, и в неоднородной постановке — только на цепи. Для первых двух случаев разработаны полиномиальные точные алгоритмы решения. Для третьей — псевдополиномиальный точный алгоритм.
Во второй главе объект исследования — задача ресурсно-календарного планирования с условием, что функции выделения и потребления ресурсов постоянны в заданных временных интервалах. Предложен точный алгоритм решения этой задачи для случая складируемых ресурсов, что является алгоритмом отыскания нижней оценки для задачи с нескладируемыми ресурсами.
В третьей главе в разделах 3.2-3.3 приведен приближенный алгоритм решения задачи отыскания нескольких реберно-непересекающихся остовных деревьев минимального суммарного веса в полном неориентированном графе, и выполнен его вероятностный анализ для случая равномерного UNI(an; bn), смещенного усеченно-экспоненциального EXP(an, Лп), смещенного усеченно-нормального NORM(an,an) распределений весов ребер графа. В разделах 3.4-3.5, построен приближенный алгоритм решения задачи максимального остовного дерева в полном неориентированном графе и проведен вероятностный анализ этого алгоритма, в результате которого доказаны условия асимптотической точности для случая распределения весов ребер графа согласно равномерному UNI(0; 1) вероятностному закону.
В заключении перечислены основные результаты диссертации.
1.1 Предварительные сведения
Простейшая задача размещения или задача размещения с неограниченными объемами производства (Uncapacitated Facility Location Problem, UFLP) — это классическая оптимизационная задача для определения оптимального расположения предприятий или складов. Для нее известно большое количество применений в логистике, телекоммуникациях, здравоохранении, планировании устойчивых систем, кластеризации, компьютерном зрении и т.д. Для детального обзора заинтересованному читателю рекомендуются монография [31] и работы [32—37].
В задаче UFLP дано множество из п клиентов, каждый из которых имеет спрос в производимом продукте, и множество из т возможных мест размещения предприятий, производящих продукт. Заданы стоимости открытия предприятий и транспортные расходы по доставке единицы продукта от каждого возможного места размещения предприятия к каждому клиенту. Задача состоит в том, чтобы определить, какие предприятия нужно открыть, чтобы суммарные затраты по открытию предприятий и транспортировке продукта были минимальны. Известно, что эта задача .^"Р-трудна в сильном смысле, т.к. к ней сводится задача о покрытии множества [3; 38].
В литературе большое внимание уделено сетевой задаче UFLP, в которой клиенты и возможные места размещения предприятий находятся в вершинах реберно-взвешенного графа, и транспортные расходы определяются согласно кратчайшим длинам путей доставки. В случае полных графов эта задача совпадает с метрической. Известно, что сетевая задача UFLP остается .^"Р-трудной в сильном смысле даже на планарной решетке [39]. Тем не менее на дереве UFLP полиномиально разрешима: В. А. Трубин [40] первым предложил для нее алгоритм со временем работы 0(п3) (здесь т = п, это означает, что в каждой вершине графа находится и возможное место размещения предприятия, и клиент, некоторые из которых могут быть фиктивными: предприятие со стоимостью открытия равной ж или клиент со спросом 0), затем Э. Х. Гимади [41] был
разработан подход, использующий технику связных областей обслуживания, с трудоемкостью О(тп), позже Р. Шах и М. Фарах-Колтон [36] предложили алгоритм со временем работы 0(п log п) (т = п). Для задачи UFLP на цепи Р. Хассин и А. Тамир [8] предложили линейный алгоритм решения. В работе А. А. Агеева [42] было показано, что задача на внешнепланарном графе решается за время 0(тп3), позже в [43] был построен алгоритм со временем работы 0(тп2'5). Для задачи UFLP на последовательно-параллельном графе, частным случаем которого является внешнепланарный, были предложены алгоритмы с трудоемкостями 0(п4) в [44] и 0(т3п) в [45]. Следует отметить, что второй алгоритм построен для более широкого класса задач и использует только существование оптимального решения со связными областями обслуживания. Для UFLP на частичном k-дереве известны полиномиальные алгоритмы со временем работы 0{тк+1п) [32] и 0(пк+2) (т = п) [46].
Естественное обобщение классической UFLP — это задача размещения с ограничениями на объемы производства (Capacitated Facility Location Problem, CFLP), в которой каждое предприятие i имеет объем производства ai, что является ограничением сверху на количество продукта, которое может произвести данное предприятие. Если возможные места размещения предприятий и клиенты находятся в вершинах некоторого графа, то такая задача называется сетевой CFLP. Известно, что для метрической задачи CFLP с единичными спросами на полном графе существует приближенный алгоритм с лучшей текущей оценкой точности равной 5 [47].
Если спросы клиентов неединичные, можно рассматривать постановку задачи CFLP с делимыми спросами, где спрос клиента может быть обслужен несколькими предприятиями совместно, и постановку с неделимыми спросами, где спрос клиента должен быть обслужен только одним предприятием. Задача CFLP с неделимыми спросами является MV-трудной в сильном смысле даже на графе с одной вершиной, если в ней могут находиться несколько клиентов и предприятий, и даже в случае одинаковых объемов производства предприятий, поскольку к ней сводится задача упаковки в контейнеры. Задача CFLP с делимыми спросами ^"Р-трудна на графе с одной вершиной, поскольку к ней сводится задача о рюкзаке, однако если объемы производства предприятий одинаковы, известно, что задача полиномиально разрешима на цепи [48]. Далее всюду под задачей CFLP понимается вариант задачи с делимыми спросами.
На многих графах древесного типа задача CFLP может быть решена за псевдополиномиальное время. Так, в работе [9] П. Мирчандани и др. предложили псевдополиномиальный алгоритм решения этой задачи на цепи. При этом задача CFLP легко сводится к задаче без ограничений на объемы производства предприятий, но с ограничениями на пропускные способности ребер: из каждой вершины Vi, в которой находится возможное место размещения предприятия с объемом производства ai, можно перенести его в новую вершину, связанную с Vi ребром нулевой стоимости с пропускной способностью ai. Для задачи размещения с ограничениями на пропускные способности ребер существуют псевдополиномиальные алгоритмы в случаях, когда граф является деревом [49], частичным 2-деревом [50], частичным ^-деревом [51] для любого фиксированного к или, что эквивалентно, в графах с древовидной шириной, ограниченной к. Следовательно, на этих типах графов задача CFLP может быть также решена за псевдополиномиальное время.
Если объемы производства предприятий одинаковы, то такая задача называется однородной задачей размещения с ограничениями на объемы производства предприятий (Uniform Capacitated Facility Location Problem, UCFLP). Для метрического случая этой задачи с единичными спросами на данный момент лучшим приближенным алгоритмом является алгоритм локального поиска из работы [52] с оценкой точности равной 3. В случае входного графа, представляющего собой цепь, в 2004 году А. А. Агеев в работе [48] разработал первый полиномиальный алгоритм со временем работы 0(тъп2 + т3п3). С течением времени данный алгоритм был модифицирован, так его временная сложность была улучшена до 0(тАп2) в [53] и позднее — до 0(т3п2) в работе [54]. Для UCFLP на звезде, если в каждой вершине звезды находятся одновременно предприятие и клиент, в работе [10] О. Ю. Цидулко была доказана ^"Р-трудность.
В данной работе исследуется сетевая задача CFLP и ее однородный вариант UCFLP на простейших частных случаях дерева — звезде и цепи. Показано, что задача UCFLP на звезде, в каждой вершине которой может находиться либо предприятие, либо клиент, на звезде решается за линейное время. Для известного полиномиально разрешимого случая задачи UCFLP на цепи рассматривается алгоритм динамического программирования из работ [48; 53] и уменьшается время его работы до 0(т2п2), где т — количество возможных мест размещения предприятия, п — количество клиентов, что является лучшим возможным вре-
менем работы в рамках текущей схемы динамического программирования [48; 53]. Для неоднородной задачи СПР на цепи предлагается модификация известного псевдополиномиального алгоритма П. Мирчандани и др. [9], улучшая таким образом время работы алгоритма с О(тВ тт{ашах,В}) до 0(тВ), где В = — это суммарный спрос, атах — максимальный объем производ-
ства предприятия.
1.2 Постановка задачи и базовые обозначения
В сетевой задаче СПР дан граф С = (V, Е), где V — множество вершин графа, а Е — множество ребер. Заданы множество возможных мест размещения предприятий I = {1,..., т} и множество вершин графа Т = {г>1,... , ут} С V, указывающее места, где эти предприятия могут быть открыты, а также множество клиентов 3 = {1,... ,п}, с множеством вершин, где они размещены С = {и1,... ,ип} С V. Каждое возможное место размещения предприятия % € I имеет объем производства € N и{0} и неотрицательную стоимость открытия . Каждый клиент у € 3 имеет спрос bj € N и {0}. Для каждого ребра е € Е известна стоимость се транспортировки единицы продукта по этому ребру, а затраты по транспортировке единицы продукта из ¿-го предприятия у-му клиенту определяется как д^ = ^е€р^ °е, где Р^ — это кратчайший путь в графе между предприятием % и клиентом у. В задаче требуется открыть подмножество предприятий Б С I и обслужить весь спрос клиентов так, чтобы суммарные затраты на открытие предприятий и транспортировку продукта клиентам были минимальны. Без ограничения общности, считается, что Х^п=1 ^ ¿=1 аг, иначе задача, очевидно, не имеет допустимых решений.
В терминах целочисленного линейного программирования сетевая задача СПР может быть сформулирована следующим образом:
т1п(^ ^ + ^ ^ ^хч) , (1Л)
jеJ
при ограничениях
^ хг] = Ь,, у € 3, (О)
х13 Е N и{0}, % Е Е 1, (1.4)
где х^ равно объему спроса клиента ], который обслуживается из предприятия %. Условия (1.2) гарантируют, что спрос каждого клиента удовлетворен, в то время как неравенства (1.3) говорят о том, что объем производства предприятия % не превышен. Наконец, соотношения (1.4) означают, что спрос может делиться только на целочисленные части. Допустимое решение задачи со множеством открытых предприятий Б и планом перевозок х = (х^) обозначается через (3,х).
Замечание 1. Для сетевой задачи СПР множество открытых предприятий $ полностью определяет стоимость решения, поскольку, зная оптимальный план перевозок х = (х^) можно найти за полиномиальное время, например, решив соответствующую транспортную задачу.
Задача с требованием = а для любого г Е I называется однородной сетевой задачей размещения с ограничениями на объемы производства предприятий. Эта задача обозначается как ИСРЬР.
Определение 1. Пусть (Б,х) — допустимое решение задачи иОРЬР. Пред-
Еп
■=1 х^ = а, и ненасыщенным, если
0 < хг3 < а.
Стоит отметить, что насыщенные и ненасыщенные предприятия обязательно открыты.
1.3 Задача "ООП/Г на звезде
В данном разделе рассматривается задача ИСРЬР на звезде. Известно, что вариант этой задачи, когда в каждой вершине звезды находится и возможное место размещения предприятия, и клиент МТ-труден [10], далее будет показано, что данная задача, для которой в каждой вершине звезды может находиться либо предприятие, либо клиент, решается за линейное время. Пусть граф С = (V, Е) — звезда с центральной вершиной щ, висячими
вершинами {ух,у2, ... ,Ут} = Т, в которых расположены возможные места размещения предприятий со стоимостями открытия ..., /т соответственно, объем производства каждого предприятия равен а, и висячими вершинами {их,и2,... ,ип} = С, в которых находятся клиенты со спросами Ьх,...,Ьп соответственно. Без ограничения общности можно считать, что в центральной вершине нет ни клиентов, ни возможного места размещения предприятия, иначе всегда можно вынести возможное место размещения предприятия или клиента из и0 в отдельную висячую вершину, соединенную с и0 ребром нулевой стоимости. Затраты на транспортировку единицы продукта обозначены через ^ для ребер {щ,уг}, % = 1,... ,т, и с)+т для ребер {и0,и^}, у = 1,... ,п. Через Ф(б') обозначается значение целевой функции (1.1) для допустимого решения, определяемого набором открытых предприятий $.
Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Многокритериальная задача о назначениях на предфрактальных графах2006 год, кандидат физико-математических наук Салпагаров, Сосланбек Исмаилович
Решение задач маршрутизации и путевых разбиений графов методами раскрасок и весовых перераспределений2011 год, кандидат физико-математических наук Замбалаева, Долгор Жамьяновна
Эффективные алгоритмы с гарантированными оценками точности для задачи маршрутизации транспорта ограниченной грузоподъемности2021 год, кандидат наук Огородников Юрий Юрьевич
Модели и методы оптимального размещения взаимосвязанных объектов на дискретных множествах2006 год, доктор физико-математических наук Забудский, Геннадий Григорьевич
Исследование вычислительной сложности задач о независимом множестве и о вершинной k-раскраске в некоторых классах графов2020 год, кандидат наук Сироткин Дмитрий Валерьевич
Список литературы диссертационного исследования кандидат наук Штепа Александр Александрович, 2023 год
уЕ 'к
тш_к С*,(Л = т1п{с*(П,СЕ+и&')}, если 2 ^ ^ г" - г + 1.
Оставшиеся величины '') подсчитываются с помощью следующей
формулы, при условии, что г — г' + 1 ^ £
Ыз3") = П + {СгГ-—1 — СгГ-1) + дгзи (Взи — Щ—1 — (I — 1)а)+
+9иг-г (В'з*и — В'з"+1 — (г — *)а).
Теорема доказана.
Лемма 1.4.3. [53] Вычисление всех значений С^С), С^(]") и ''') может быть выполнено методом динамического программирования за время 0{т2п), 0{т2п) и 0{т2п2) соответственно.
Доказательство. Вычисление всех значений В^ и В'- требует О(п) времени, нахождение всех С^ может быть выполнено с трудоемкостью О(тп). Построение множеств Т и Т' для каждого фиксированного ]' осуществляется за О(т) действий, следовательно, суммарно необходимо О(тп) операций. Величины и ¿,{¿¿>1 для всех индексов могут быть найдены за общее время 0(т2п). Зная значения и , величины С^(]") и С^(]"), С^(]") и С^(]") можно последовательно вычислить за суммарное время 0(т2п). Наконец, определение величин ''') для всех индексов г, £, ]', ]" потребует 0{т2п2) операций. Лемма доказана.
Теперь, на основе этих утверждений, можно доказать основной результат этого раздела.
Теорема 1.4.2. Задача ЦСРЬР на цепи может быть решена за время 0{т2п2).
Доказательство. Из леммы 1.4.3 следует, что все значения ^¿(з") и ',]'') могут быть найдены суммарно за время Т1 = 0(т2п2). Для вычисления этих величин потребуются следующие обозначения для всех 1 < < т, 1 < < < п:
'') = ШШ {б—1,—1(Л + Ей(/',/) + С+,—№')}. (1.8)
Стоит отметить, что теперь нужно Т2 = 0(т2п2) времени для нахождения всех значений ЯгС/',]''). С учетом соотношений (1.7) и (1.8), получается следующая формула для вычисления Я %',{'' ',/'):
Яг',г" и',3'') = тт^С? ',3'') = шш{Яг',г>'—1и',3 '');Яг(з',з'')}.
г'<г<г"
Следовательно, зная все величины '') и предыдущее значение
Я^;1"—1(]',]''), можно найти следующее значение Яг',г" (/',]'') за константное время. Следовательно, вычисление Яг',гп (/',]'') для всех индексов 1 < г' < г" < т, 1 < / < < п, может быть выполнено за время Т3 = 0(т2п2).
Окончательно, из (1.5)-(1.6) следует, что, зная все значения Я-уу(]',]''), нахождение всех Я(%,]) требует Т4 = 0(т2п2) времени. Таким образом, общая трудоемкость алгоритма оценивается величиной Т1 + Т2 + Т3 + Т4 = 0(т2п2). Теорема доказана.
1.5 Задача СЕЬР на цепи
Из работы П. Мирчандани и др. [9] следует, что для задачи СПР на цепи существует точный псевдополиномиальный алгоритм динамического программирования с трудоемкостью 0(тВ шт{атоах, В}), где т — количество возможных мест размещения предприятий, атоах = шах^/а^ — максимальный объем производства предприятия, В = 7 — суммарный клиентский спрос. В этом разделе будет показано, как можно улучшить время работы этого алгоритма до 0(тВ).
Предполагается, что в заданном графе-цепи G = (V, Е) множество вершин V = {1,... , пу}, и вершины нумеруются слева направо вдоль цепи. Также полагается, что возможное место размещения предприятия i Е I = {1,... ,т} является г-ым по счету слева направо и находится в вершине Vi Е Т, а клиент j Е J = {1,... ,п} является j-ым клиентом по счету слева направо и находится в вершине Uj Е С. Если такая нумерация не задана, ее всегда можно найти за время 0(\V| log IV|).
На предварительном шаге задача CFLP на цепи G = (V, Е) с п клиентами за время О (В + т) сводится к задаче CFLP на цепи G' = (V',E') с В = e J bj клиентами, имеющими единичные спросы. Для этого естественным образом каждая вершина щ, содержащая клиента t со спросом bt > 1, заменяется подцепью из bt вершин, в каждой из которых находится клиент с единичным спросом. Стоимости транспортировки единицы продукта по ребру между последовательными клиентами такой подцепи полагаются равными нулю. В новой цепи G' = (V', Е') число вершин \V'| = П ^ т + В.
Пусть R(i, j) — оптимальное значение целевой функции подзадачи CFLP с единичными спросами клиентов на цепи, в которой первые j клиентов цепи должны быть обслужены с помощью первых предприятий. Для каждой пары индексов к, j, 1 ^ к < j ^ В, через Wi(k, j) обозначаются суммарные транспортные затраты, необходимые для обслуживания спросов всех клиентов из полуинтервала ( к, j] предприятием i, т.е. Wi(k, j) = Ylt=k+i 9и. Тогда задача решается с помощью следующей схемы динамического программирования.
R(i, 0) := 0, 0 ^i^m, R(0, j) := Q, 1 ^j^B, (1.9)
для всех = 1, . . . , т, = 1, . . . , В R(i, j) = min\ü, R(i — 1, j), fi + min {R(i — 1,k)+wi(k, j)}), (1.10)
L max{j —ai ,l}^k<j J
где Q = £r=l fi + В • £eeE ce — достаточно большое число, отвечающее отсутствию допустимого решения в соответствующей подзадаче. Если известны значения Wi(k, j), таблица R вычисляется за время 0(тВ min{amax, В}), где о-тах — максимальный объем производства предприятия [9]. Оптимум целевой функции задачи равен R( т, В), а само решение восстанавливается обратным
ходом алгоритма за время О(т), если хранить для каждого элемента (г, j) таблицы индекс к, на котором достигается минимум в (1.10).
Далее будет показано, как эффективно вычислять значения ю^к, j).
Утверждение 1.5.1. После предварительных вычислений, требующих 0(В + т) времени, значение Юг(к,]) может быть найдено за время 0(1) для любых 1 ^г ^т, 1 О <2 < В.
г
Доказательство. Рассмотрим частичные суммы ((£) = С(8-1,8),
в=1
г г
В(Ъ) = ^ ((ЛЩ и В(£) = ^ Щ для всех I = 1,... ,п' ^ В + т, где С(0 1) =0 и 3=1 3=1
1, если в вершине ^ находится клиент,
к =
0, иначе.
Эти суммы можно вычислить рекурсивно за время О (В + т). Тогда значения ю^к, j) вычисляются следующим образом. Если VI < ик < и^, то
3 из из из
юг(к,э)= ^ ди = ^ т -(&))К = £ ((*)К - ^ (&)К =
Ь=к+1 Ъ=ик+1 Ъ=ик+1 Ъ=ик+1
Пп
В(Щ ) -И(ик) - ((Уг) К = В(щ ) -И(ик) ~((Уг)(В (и, ) -В (Щ)).
Ь=ик+1
Если ик < и^ < V{, аналогично находятся
юг(к, з) = И(ик) - В(и3) + ((уг )(В (и) - В (ик)). Если ик < < и^, то
щ и
Юг(к,Л = £ ((((У1) -((*))Ь[ + £ (<ВД - (((у)Ь[ = -(И^) -В(щ))+
1=ик+1
Уг из
+(В(щ) - В(уг)) + (М ( £ Ь[ - £ = И(ик) + В(щ) - 2И(^)-
Ь=ик+1 ¿=^¿+1
-((Vг)(В(ик) + В(иj) - 2В(V,)).
Таким образом, зная значения ((£), И(£) и В(£) для каждого £ = 1,... ,п' можно найти Ю{(к,Л за время 0(1). Утверждение доказано.
В этом разделе будет показано, как сократить время работы алгоритма динамического программирования (1.9)—(1.10) до 0(тВ). Нужно последовательно вычислять строки таблицы Я, и будет показано, как, зная значения элементов в строке (г — 1), вычислить строку % за время О (В). Для этого понадобится алгоритм из [57, разд. 4], который находит минимальный элемент в каждом столбце полностью монотонной ах ^-матрицы суммарно за время 0(а+в).
Определение 3. а х в-матрица А с действительными элементами называется монотонной по столбцам, если для каждой пары столбцов с индексами < ]1 верно
Кзо) < Кп),
где г(]) — наименьший индекс строки г такой, что элемент А(г, j) равен минимальному значению в 3-ом столбце матрицы А. Матрица А называется полностью монотонной по столбцам, если любая 2 х 2 подматрица матрицы А монотонна по столбцам.
Следует отметить, что в работе [57] монотонность матрицы определялась в терминах позиции максимального элемента в каждой строке, но все результаты можно легко адаптировать для рассматриваемого случая, транспонировав матрицу и поменяв знаки соответствующих неравенств в алгоритме.
Утверждение 1.5.2. [57] Пусть а х в-матрица А полностью монотонна по столбцам. Существует алгоритм [57, разд. 4], который находит минимальный элемент в каждом столбце матрицы А суммарно за время О (а + в).
Рассмотрим %-ую строку Я, заданную соотношением (1.10). Для вычисления каждого элемента ,]), ] = 1,..., В, необходимо найти шт Аi(k,]), где В х В-матрица А{ определяется следующим образом:
Аi (к, 3) = {
Я(1 — 1,к) + п)г(к, ]), если ш&х{] — аг, 1} ^к <] и Я(1 — 1, к) < и, и + В — к, если 1 ^ к < ] — аг и Я(1 — 1,к) < и,
и + В, иначе.
(1.11)
Здесь О = 7=1 + В -^2ееЕ °е — достаточно большое число, и О > Я(г, к) для любых % = 1,... ,т, к = 1,... ,В. Элементы А{(к, j) ^ О отвечают отсутствию допустимого решения соответствующей подзадачи, и их значения выбраны так, чтобы впоследствии матрица А{ оказалась строго монотонной по столбцам. Стоит отметить, что матрица А{ определена корректно: элементы Я(г — 1, к) известны после вычисления значений (г — 1)-ой строки таблицы Я, а каждое значение ю^к, ^ можно найти за время 0(1) согласно утверждению 1.5.1. Зная минимальные элементы в каждом столбце матрицы А^, можно вычислить г-ую строку таблицы Я за время 0(В) согласно (1.10). Далее будет показано, что матрица Аi полностью монотонна по столбцам, тогда согласно утверждению 1.5.2 алгоритм из [57] найдет минимальный элемент в каждом ее столбце суммарно за время 0(В).
Лемма 1.5.1. Для каждого 1 ^ г ^ т В х В -матрица А^, определенная согласно (1.11), полностью монотонна по столбцам.
Доказательство. Сначала будет показано, что функции ю вогнуты, то есть для каждого г = 1,... ,т и любых 1 ^ к0 < к ^ < ]1 ^ В:
юг(ко,]о)+юг(к1,^юг(ко,л)+юг(к1,]о). (1.12)
Действительно, по определению, Юг(к,]) = ^Уг=к+19иЬ, и тогда
Я 30 31
щ(ко, ]\) —юг(ко, ]о) = £ дц\н — £ диЫ = £ =
г=ко+1 г=ко+1 г=за+1
31 30
= £ ^ — Е 9ггЬг = ю*(к1,Л) —юг(к1,]о).
г=к1+1 г=к1+1
Элемент матрицы А{ будет называться серым, если его значение не меньше О, и белым иначе. Следовательно, серыми являются элементы (см. рис. 1.1), лежащие не выше главной диагонали матрицы, элементы верхнего правого угла к < ] — а{, и элементы для которых Я(г — 1, к) ^ О, соответствующие случаю, когда для обслуживания первых к единиц спроса недостаточно объемов производства первых (г — 1) предприятий, что эквивалентно к >^2аЙ.
Предположим, что матрица А^, определенная согласно (1.11), не полностью монотонна по столбцам, то есть существуют индексы к0 < к\ и jo <
такие, что
Аг(ко,]о) > Аг(кг,]о) и Аг(к1,]1) ^ Аг(ко,]Х). (1.13)
\ 12 3 ... 7 ... в
А =
к>1а,
к<з-а.
Рисунок 1.1 — Схематичный рисунок матрицы А^, где заштрихованные области соответствуют серым элементам матрицы А^, Аi(k,]) ^ и, а не заштрихованные области соответствуют белым элементам А^.
Рассматриваются четыре возможных случая.
Случай 1: к1 ^ j0. Стоит заметить, что и + В ^ Аi(k,]) для любых 1 ^ к,з ^ В и любых % = 1,...,т. Тогда Аг(к1,]0) = и + В ^ Аг(к0,]0), что противоречит (1.13).
Случай 2: к0 < к1 < ]0 < и Я(1 — 1,к1) ^ и. Снова получается Аi(к1,]0) = и + В ^ Аг(к0,]0), что противоречит (1.13).
Случай 3: к0 < к1 < ]0 < ]1, Я(1 — 1,к1) < и и элемент Аг(к0,]{) серый. В этом случае, по определению (1.11), Аг(к0,]{) = и + (В — к0) > и + (В — к1) ^ А{(к1,что противоречит (1.13).
Случай 4: к0 < к1 < ]0 < , Я(1 — 1,к1) < и и элемент А^(к0,]\) белый. Последнее означает, что ]1 — а<1 ^к0 < ]]_, и тогда ]0 — а<1 ^ ]1 — а<1 ^к0 < < ]0 < Так же можно заметить, что из Я(г — 1, к]) < и следует Я(г — 1, к0) < и. Тогда согласно (1.11) элементы Аг(к0,]0), Аг(к1,]0), Аг(к]_,]{) тоже белые. А значит, сложив два неравенства из (1.13), получается
Я(г — 1, ко) +п)г(ко,]о) + Я(г — 1,Ь) +п)г(к1,]1) = Аг(ко,]о) + А{(къ31) >
> Аг(к1,]о) + Аг(ко,31) = Я(г — 1,Ь) +п)г(к1,]о) + Я(г — 1,ко) +п)г(ко,31), откуда следует:
'Шг(ко, ]о) +'Шг(Ь, ]1) > Ь, ]о) + 1Ш{(ко, 3\),
что противоречит свойству вогнутости j) (1.12). Следовательно, матрица А{ полностью монотонна по столбцам. Лемма доказана.
доказательство. Суммируя вышесказанное, более быстрый алгоритм для задачи СПР на цепи работает следующим образом. Сначала, за время 0(В + т), сводится исходная задача к задаче с единичными спросами. Затем вычисляются суммы из утверждения 1.5.1 за время О (В + т), что позднее позволит находить любое значение "ш^к,]) за 0(1).
Далее, последовательно для каждого г = 1,... ,т находится ¿-ая строка таблицы Я динамического программирования (1.10). Для этого рассматривается В х В-матрица А^, заданная согласно (1.11), которая по лемме 1.5.1 полностью монотонна по столбцам, а значит, применив к ней алгоритм из работы [57], за время О (В) можно найти минимальные элементы в каждом ее столбце. Стоит отметить, что в алгоритме из [57] не требуется непосредственно создавать и хранить В х В-массив для матрицы А^, достаточно лишь иметь доступ к любому элементу А{ за время 0(1), что может быть сделано, поскольку проверка того, что элемент А{ серый или белый требует 0(1) времени, и вычисление значения белого элемента, с учетом утверждения 1.5.1, также требует 0(1) времени. Наконец, зная значения минимальных элементов каждого столбца матрицы А^, можно вычислить все элементы ¿-ой строки Я за время О (В) согласно (1.10).
Поскольку в таблице Я всего т строк, суммарная трудоемкость предлагаемого алгоритма равна 0(т В) + О (В + т) = О(тВ). Теорема доказана.
Глава 2. Задача ресурсно-календарного планирования 2.1 Предварительные сведения и обзор литературы
В задаче ресурсно-календарного планирования с ограниченными ресурсами необходимо найти расписание выполнения работ с минимальным сроком завершения проекта. При этом должны быть учтены технологические ограничения предшествования и ограничения на ресурсы. Прерывания работ не допускаются. Далее, эта задача будет обозначаться, как ЗРКП.
В зарубежной литературе (см. обзорно-классификационные статьи [58—61]) ограниченные ресурсы традиционно делятся на возобновимые (renewable) и невозобновимые (nonrenewable).
В случае возобновимого ресурса для каждой работы задается требуемое количество ресурса в каждый из моментов ее выполнения. Имеющееся в наличии в какой-либо момент времени количество ресурса не должно быть меньше суммарного количества ресурса, требуемого всеми работами, выполняемыми в этот момент времени. Типичными представителями этого типа ресурсов являются производственные мощности, оборудование, человеческие ресурсы.
Ограничения на невозобновимые ресурсы накладываются на весь проект в целом, позволяя, например, моделировать бюджет проекта.
В русскоязычных работах [11; 12; 62—65] изначально использовалась иная классификация: ресурсы делились на нескладируемые и складируемые (в [64] - сохраняемые). В обоих случаях происходит учет баланса между выделяемым и потребляемым количеством ресурса. Но, если понятие нескладируемого ресурса в точности совпадает с описанным выше понятием возобновимого ресурса, то в случае складируемого ресурса используется другой механизм подсчета потребляемых и выделяемых объемов ресурса. Для допустимости расписания относительно складируемого ресурса достаточно, чтобы для каждого момента времени t ^ 0 суммарный по всем работам объем ресурса, потребляемого к моменту t, не превосходил объема ресурса, выделяемого к моменту t. Складируемые ресурсы невозможно учесть с помощью комбинации возобновимых и невозобновимых ресурсов. При этом, невозобновимый ресурс может рассматри-
ваться как складируемый, весь объем которого доступен с начала выполнения проекта.
В случае складируемых ресурсов любое количество ресурса, выделенного в единицу времени £ Е N и {0} и неиспользованного в этот период, может быть потреблено в любой последующий период £' > £, в отличие от нескладиру-емого (возобновимого) ресурса, для которого часть ресурса, неиспользованного в период , пропадает впустую. Примерами складируемых ресурсов являются строительные материалы с длительным сроком хранения, частично деньги.
В книге [3] показано, что задача ЗРКП даже без директивных сроков, но с ограничениями на отношение предшествования и одним возобновимым (нескла-дируемым) ресурсом является ^""Р-трудной в сильном смысле. Более того, для этой задачи маловероятно существование приближенных полиномиальных алгоритмов с гарантированной оценкой точности лучшей, чем п1—£ для любой константы £ > 0 [66].
В работе [64] для ЗРКП с ограничениями на складируемые ресурсы был описан алгоритм без обоснования оптимальности получаемого решения и анализа временной сложности. В [65] исследованы основные свойства расписаний со складируемыми ресурсами и на их основе построен алгоритм, из описания которого можно сделать вывод о его псевдополиномиальной временной сложности. В работах [11; 12] для решения ЗРКП с длительностями работ из множества неотрицательных действительных чисел К+, директивными сроками и ограничениями на складируемые ресурсы предложен асимптотически точный алгоритм, время работы которого зависит от числа дуг и в графе отношения предшествования на множестве работ, как функция порядка иlogи, причем как относительная, так и абсолютная погрешности стремятся к нулю с ростом размерности задачи.
В работе [63] представлена задача с ограниченными ресурсами, когда все работы имеют целочисленные длительности, а все функции, определяющие ресурсные ограничения (по интенсивности потребления и выделения ресурсов) являются кусочно-постоянными, причем все длины интервалов постоянства этих функций являются целочисленными. В частном случае, когда в модели отсутствуют ресурсные ограничения нескладируемого типа, построен полиномиальный алгоритм решения этой задачи. (Такая задача будет обозначаться ЗРКПСТ.) Подход к решению ЗРКП основан на использовании свойств так
называемых Т-поздних расписаний, среди которых содержится также и оптимальное расписание этой задачи.
Алгоритмическое решение ЗРКП было инициировано необходимостью разработки программно-математического обеспечения для планирования крупномасштабных проектов, связанных со строительством Байкало-Амурской железнодорожной магистрали (сокр. БАМ) [11; 12], освоением территориально-промышленных комплексов Сибири и Дальнего Востока, а также с реализацией Западно- и Восточно-Сибирского нефтегазовых комплексов [67—69]. Будучи классической задачей в области исследования операций, она имеет обширные приложения в экономике, строительстве, управлении, компьютерных технологиях.
Складируемые ресурсы интересны не только тем, что они более адекватно учитывают специфику некоторых ресурсов, обладающих свойством складиру-емости, но и тем, что понятие складируемых ресурсов позволяет расширить возможности для приближенного решения "традиционных" ЗРКП, поскольку складируемые ресурсы являются ослаблением возобновимых. Вычислению нижних оценок для ЗРКП посвящено достаточно большое количество публикаций. Последние обстоятельные обзоры можно найти в [70] и [71]. В работе [59] для вычисления нижней оценки предложен псевдополиномиальный алгоритм с трудоемкостью 0(п2К(п + и + К)Т Т), где п — число работ, и — число дуг в графе отношения предшествования на множестве работ, К — число типов ресурсов, Т — горизонт планирования. Большинство таких алгоритмов относится к так называемым "деструктивным" методам, когда, задавшись определенным сроком завершения проекта, ищется допустимое решение задачи. Если приемлемое решение не существует, срок увеличивается (обычно на единицу времени), и процедура расчета возобновляется до тех пор, пока алгоритму удается найти допустимое решение с текущим заданным сроком, либо до окончания отведенного расчетного времени. Существуют и другие подходы для решения этой задачи: нахождение дизъюнктивных оценок (основано на дополнительном отношении предшествования с проверкой определенных требований множества А, которые должны быть / не могут быть выполнены до / после некоторого множества требований В), нахождение кумулятивных оценок, методы ограниченного программирования (основаны на уменьшении временного интервала, подсчитанного для каждой работы согласно анализу доступного количества ресурсов для выбранного множества работ), алгоритмы исследования ограничений несколь-
ких ресурсов (базируются на рассмотрении "критических" множеств, то есть множеств работ, которые не могут выполняться одновременно из-за ресурсных ограничений, в то время как любое подмножество таких критических множеств не нарушает ресурсных ограничений и может быть выполнено одновременно), релаксация линейного программирования.
Стоит отметить также ряд зарубежных работ, где наряду с нескла-дируемыми ресурсами так или иначе упоминается использование ресурсов складируемых или с определенной степенью складируемости [72—75].
В данной работе рассматривается класс задач, сформулированных в рамках электронной библиотеки PSPLIB [60; 76; 77]. Для решения задачи с ограниченными складируемыми ресурсами, обозначаемой как ЗРКПСТ, представлен новый быстрый точный алгоритм c временной сложностью О^и +
п(К + log2n)^, где и — число дуг в графе G отношения предшествования на множестве работ N, п — число работ, К — число типов ресурсов. Тем самым предлагается быстро вычислимая нижняя оценка для задачи с участием ограниченных нескладируемых ресурсов, далее, ЗРКПР. Такая постановка задачи только с возобновимыми (нескладируемыми) ресурсами в англоязычной литературе называется Resource Constrained Project Scheduling Problem (RCPSP). Численные эксперименты проведены на примерах ЗРКПР из электронной библиотеки PSPLIB. Результаты вычисления нижних оценок этих задач показывают высокую эффективность предлагаемого алгоритма. На ряде серий входных данных полученные нижние оценки очень близки к наилучшим (приведенным в библиотеке), особенно на задачах с большим числом работ.
2.2 Постановка задачи
ЗРКП можно сформулировать как задачу комбинаторной оптимизации. Проект рассматривается, как ациклический ориентированный граф отношения предшествования G = (N, U). Через N = {1,... ,п}и{0,п + 1} обозначается набор работ в проекте, где работы 0 и (п + 1) — фиктивные, определяющие начало и конец проекта соответственно. Отношение предшествования на множестве N определяется набором пар U = {(г, j) | i предшествует j}. Если (i, j) Е U, то
работа j не может начаться до завершения работы i. Множество U содержит все пары (0, j) и (j,n + 1), j = 1,... ,п.
Для каждого нескладируемого ресурса к Е К,9 в момент t доступны q<p (t) единиц этого ресурса. Для каждого складируемого ресурса к Е К? в момент t поступают и могут быть использованы в любое время t1 ^ t q%(t) единиц ресурса типа к. Работа j имеет детерминированную продолжительность pj Е NU{0} и требует rjk (t) ^ 0 единиц ресурса типа к Е 1С9 У в моменты t = 1,..., Pj, начиная от момента начала ее выполнения.
Предполагается, что rjk(t) ^ qp(t), j Е N, к Е К9, t Е N U {0} (иначе задача не имеет допустимого решения). Фиктивные работы 0 и (п + 1) имеют нулевую продолжительность и нулевое потребление ресурсов.
Переменные задачи Sj — начало выполнения работы j. Поскольку каждая работа выполняется без прерывания, время завершения работы j равно Cj = Sj + pj. Расписание S определяется как (п + 2)-вектор ( s0,..., sn+i). Срок реализации проекта Cmax(S) соответствует моменту, когда завершена последняя работа с номером (п + 1), т.е. Cmax(S) = сп+1. Также вводится обозначение J(0 = {j Е N | Sj < t ^ Cj}, t Е N U {0} для множества работ, которые выполняются в течение интервала [t — 1;t) в расписании S.
Задача состоит в отыскании расписания S, допустимого по ресурсам и ограничениям предшествования, с минимальным сроком завершения проекта.
Таким образом, сформулирована следующая задача:
Cmax(S) = max(Sj + Pj) ^ min (2.1)
j ЕМ
при выполнении ограничений:
S i + Рг < Sj, y(i, j) Еи; (2.2)
£ rjk(t — Sj) ^ qpk(t), к Е KL9, t Е N U {0}; (2.3)
JЕJ (t)
t t E E (f' — si) ^ EкЕ1С°,1 Е N U {0}; (2.4)
t'=1 jeJ (t') t'=1
Sj Е N U{0}, j Е N. (2.5)
Неравенства (2.2) определяют отношение предшествования работ. Соотношения (2.3) и (2.4) обеспечивают соблюдение ограничений на нескладируемые и складируемые ресурсы соответственно, то есть общее количество потребленных
ресурсов за интервал [t — l;t) не может превышать количества соответствующих доступных ресурсов в течение этого интервала.
Задача (2.1) - (2.5) будет обозначаться, как ЗРКП. Известно, что она MV-трудна, если К? = 0 [78]. Далее будут рассмотрены два частных случаях задачи (2.1) - (2.5), для исходных данных которых верно следующее условие.
Условие 1. Функции интенсивности выделения и потребления ресурсов постоянны в заданных временных интервалах, а директивные сроки для выполнения работ отсутствуют.
2.3 Постановка задачи с нескладируемыми ресурсами
Рассмотрим специальный случай задачи (2.1) - (2.5), где выполняется условие 1 и К® = 0. При этом для всех k E Кр и t E N U {0} выполнено qk(t) = qk и rjk(t) = rjk, j E N.
Эта задача обозначается, как ЗРКПР. Пусть дан граф G = (N, U) отношения предшествования на множестве работ, К различных нескладируемых ресурсов, т.е. К = \fcp\. Также J(t) = {j E N \ Sj < t ^ Cj} — это множество работ, которые выполняются в интервале времени [t — l;t). Для каждой работы известна ее длительность pj.
Требуется найти допустимое расписание работ S = {Sj}, минимизирующее время Cmax(5) выполнения всего проекта.
) = max(Sj + Рз) ^ min (2.6)
3 EN
при ограничениях:
S г + Рг < Sj, y(i, j) EU; (2.7)
У rjk < qk, k = !,..., К, tE N U {0}; (2.8)
3 EJ (t)
Sj E N U{0}, jEN. (2.9)
Неравенства (2.7) задают отношение предшествования на множестве работ N. Условия (2.8) гарантируют выполнение ограничений на ресурсы.
Теперь рассматривается другой частный случай задания исходных данных задачи (2.1) - (2.5), когда выполнено условие 1, и К,р = 0. Также для всех к Е К,р и^ Е N и {0} выполнено (£) = дк и rjk (£) = rjk, 3 Е N.
Аналогично предыдущей задаче задан граф С = и) отношения предшествования на множестве работ, число К = 1^1 различных типов складируемого ресурса, множество работ 3(£) = {3 Е N | < £ ^ }, которые выполняются в единичном интервале \р — 1;£). Для произвольной работы 3 известна ее длительность pj.
ЗРКП состоит в том, что необходимо найти допустимое расписание 5 = {}, которое минимизирует время выполнения всего проекта Стах(5), т.е. следующая задача:
при ограничениях:
) = тах^- + Рз) ^ т!п (2.10)
8г + Рг ^ 81, У(г, з) Еи; (2.11)
Е Е г0к ^ ^ ■ ^ к = 1,...,К, гЕ N и {0}; (2.12)
V=1 3ЕЗ )
Е N и{0}, з Е N. (2.13)
Соотношения (2.11) описывает отношение предшествования работ. Неравенства (2.12) определяют ограничения на складируемые ресурсы.
Утверждение 2.4.1. Пусть параметры исходных данных в задачах ЗРКПР и ЗРКП совпадают. Тогда решение ЗРКП является допустимым решением ЗРКПр.
Доказательство. Легко понять, что в обеих задачах все параметры, целевые функции и ограничения идентичны, кроме ограничений (2.8) и (2.12). Ясно, что неравенства (2.12) являются следствием условий (2.8). Итак, найден более широкий допустимый набор решений для (2.12) по сравнению с (2.8) и решение ЗРКП является допустимым решением ЗРКПР. Или, что то же самое, минимум целевой функции ЗРКП дает оценку снизу для задачи ЗРКПР. Утверждение доказано.
Далее будет решаться задача со складируемыми ресурсами с целью получения нижней оценки для задачи с нескладируемыми (возобновимыми) ресурсами.
В работе [63] ЗРКП рассматривалась в более общей постановке по сравнению с задачей (2.10) - (2.13), что предполагает возможность учета директивных сроков завершения работ, а также более детального описания исходных данных о характеристиках функций интенсивности выделения и потребления ресурсов. Точный алгоритм, построенный для этого случая, имеет следующую временную сложность:
где
И — длина бинарной записи максимального директивного срока; и — число дуг в графе С отношения предшествования на множестве работ; I — общее (по всем ресурсам к Е К,°) число интервалов постоянства функций
(Ь) выделения ресурсов; I — общее (по всем ресурсам и всем работам) число интервалов постоянства функций г^(Ь) потребления ресурсов;
— ширина графа отношения предшествования; К — число типов ограниченных ресурсов; Щ<цг — число работ с одинаковым директивным сроком; N — число различных директивных сроков.
В настоящей статье рассматривается случай ЗРКПСТ, для которой выполнено условие 1. В таком случае, согласно выражению (2.14), временная сложность решения ЗРКП (с учетом неравенства / ^ п) оценивается величиной
независящей от параметров задачи, имеющих временной характер.
Учет специфики указанного задания исходных данных позволяет разработать следующий алгоритм Л.зРКП решения ЗРКП с улучшенной временной сложностью Оуи + п[К + \og2n)) по сравнению с оценкой (2.15).
Оф(и + I + По%2 (/К)) + Щгг Ъ%2 Щ),
(2.14)
О (и + пК (пК)) ,
(2.15)
Шаг 1. Вычислить критическое время завершения проекта Тсг и Тег-позднее расписание работ проекта (например, согласно [79]).
Шаг 2. Упорядочить список работ по моментам их начал: 0 = t0 ^ t\ ^ . . . ^ tп+1 Тег .
Шаг 3. Найти множество различных моментов Тн начал или завершений работ в Тег-позднем расписании, так что 0 = То < Т\ < ... < Тн = Тсг, где (Н +1) — количество таких моментов. Обозначить % = {0,1,..., Н}.
Шаг 4. Составить список работ J+, упорядоченный по неубыванию их моментов начал в Тсг-позднем расписании, и сформировать соответствующий список А+, h Е % начальных номеров работ с одинаковым моментом начала Тн в Ter-позднем расписании.
Шаг 5. Составить список работ J-, отсортированный по неубыванию моментов их завершения в Тсг-позднем расписании, и сформировать соответствующий список А-, h Е % начальных номеров работ, время завершения которых в Ter-позднем расписании равно Тн.
Шаг 6. Найти динамику потребления каждого ресурса в каждом временном слое (Тн~1, Тн], h = 1,...,Н. Для этого в цикле по типам ресурсов к = 1,... , К и по слоям h = 1,..., Н выполнить следующую процедуру Vk (h).
Описание процедуры Vk (h). Процедура вычисляет общую интенсивность г к (h) потребления ресурса типа к в слое h в единицу времени и общее количество Rk(h) ресурса типа к, потребленного в слое h. Предполагается, что при h > 0 уже вычислена суммарная интенсивность г к (h — 1) потребления ресурса типа к в предыдущем слое (h — 1), причем Гк(0) = 0.
Шаг 6.1. Вычислить общую интенсивность потребления работ r+(h), начинающихся в момент Тн, из списка А+.
Шаг 6.2. Вычислить общую интенсивность потребления работ r— (h), завершаемых в момент Тн, из списка А—.
Шаг 6.3. Вычислить общую интенсивность г к (h) потребления работ в слое h в единицу времени Гк(h) = Гк(h — 1) + r+(h) — r—(h).
Шаг 6.4. Вычислить суммарное количество Rk(h) ресурса типа к, по-
Як (К) = гк (К) (% - %-\).
Описание процедуры Тк(К) завершено.
Шаг 7. Для каждого типа ресурса к вычислить интегральные функции Як (К) и С^к (К) объемов ресурсов, потребленных и имеющихся в наличии к моменту Тн соответственно. Искомые величины вычисляются согласно формулам:
Як (0) = 0, Як (К) = Як (К - 1) + Як (К); Ск (К) = Як %, К = 1,...,Н.
Шаг 8. Вычислить для каждого типа ресурса к минимальную величину Ак сдвига расписания по временной оси, при котором это расписание допустимо по ресурсу типа к:
Ак = max
hem
Rk (h)
-->h
к
где множество m С m состоит из слоев h с неравенством
Rk (h) > qkTh.
Шаг 9. Вычислить величину сдвига ТСг-позднего расписания: А = max Ак.
l^k^K
Шаг 10. Вычислить длину оптимального расписания для ЗРКПСТ, что является нижней оценкой для длины расписания ЗРКПР: Т = ТСГ + А.
Шаг 11. Вернуть для ЗРКП оптимальное расписание: Sj = tj+А, j e N.
Описание алгоритма ДзРКП закончено.
Основная идея алгоритма заключается в том, что для каждого ресурса к
график интегральной функции потребления ресурсов Rk(h) должен находиться
полностью под графиком интегральной функции выделения ресурсов Qk(h),
если этого не происходит, то график Rk(h) нужно сдвинуть на величину Ак
(см. рис. 2.1). Окончательная величина сдвига А находится, как А = max А к.
l^k^K
Утверждение 2.5.1. Алгоритм ЛзРКП находит оптимальное решение ЗРКП и нижнюю оценку длины расписания в ЗРКПР.
Доказательство. Нужно убедиться в корректности вычисления величины А сдвига 7^г-позднего расписания, важны следующие соображения.
Рисунок 2.1 — Основная идея работы алгоритма ЛзРКП.
Для каждого типа ресурса к вычисляется значение Д& величины минимального сдвига графика интегральной функции потребления вправо, при котором (сдвинутый) график целиком помещается под графиком интегральной функции (к(Ь) выделения ресурсов. Максимальное по всем к из чисел Д&, выбирается в качестве значения величины Д.
Рассматриваются два случая вычисления величины Д& для некоторого 7^-позднего расписания.
Случай 1: Если Я(Ь) ^ ^Тн для всякого Ь Е %, то полагается Д& = 0.
Случай 2: Если выделено множество % С % всех слоев Ь с обратным неравенством
Я (Ь) > Як %.
Пусть Ь Е %к — некоторый слой, очевидно, найдется минимальная целочисленная величина сдвига-добавки бН к моменту Тн, изменяющая знак последнего неравенства на противоположный:
Я (Ь) < дк (% + бН),
что равносильно неравенству:
б! >
Як (Ь)
Чк
Непосредственно отсюда, с учетом целочисленности добавок бН, получается минимальная величина сдвига расписания в слое Ь относительно ресурса типа к:
ок
--!Н
Чк
(Ter + Ак)-позднее расписание оптимальным относительно ресурса типа к.
Наконец, при сдвиге А = тахАк в качестве оптимального решения
кеК
ЗРКП получается (ТСГ + А)-позднее расписание за время, анонсированное в теореме. Вместе с тем получена также нижняя оценка длины расписания в ЗРКПР, равная величине ТСГ + А. Утверждение 2.5.1 доказано.
Утверждение 2.5.2. Алгоритм ЛзРКП находит решение ЗРКП и нижнюю оценку для ЗРКП за время
о[и + n(K + log2n)), (2.16)
где и — число дуг в графе G отношения предшествования на множестве работ N, n — число работ, K — число типов ресурсов.
Доказательство. Временная сложность алгоритма ДзРКП оценивается по шагам 1-11. Шаг 1 выполняется с трудоемкостью О(и) (например, с использованием поиска в глубину [79], начиная его с начала проекта при подсчете величины ТСГ, и с конца проекта — при вычислении ТСГ-позднего расписания). Шаг 2 может быть реализован за время О(п log2n). Шаг 3 осуществляется с линейной от n трудоемкостью. Шаги 4 и 5 могут быть выполнены за время О(п log2n). Шаг 6, включая процедуру Тк (h), с использованием имеющихся данных об интенсивностях потребления ресурсов, а также списков {Th}, {A+} и {A-}, h е%, может быть реализован с трудоемкостью О(п K ). Шаги 7 и 8, с учетом H ^ п, выполняются за время О(пК). Шаги 9-11 могут быть осуществлены за время О(К), константное и О(п) соответственно. В итоге получается анонсированная оценка временной сложности. Утверждение доказано.
2.6 Численные эксперименты
Качество предложенного алгоритма было протестировано в серии численных экспериментов. С этой целью алгоритм Л.зРКП был реализован на языке
программирования С++ в среде разработки Visual Studio. Для численных экспериментов использовался настольный персональный компьютер с тактовой частотой 2.3 GHz и объемом оперативной памяти 6 Gb, под управлением операционной системы Windows 10.
В качестве тестовых примеров использовались примеры из электронной библиотеки PSPLIB [76]. Примеры для ЗРКПР в этой библиотеке разбиты на четыре части, j'30, j60, j90 и j120, с числом работ в каждом конкретном примере 30, 60, 90, и 120 соответственно. В библиотеке PSPLIB общедоступны как сами эти примеры, так и их оптимальные решения (только для примеров из j30), или наилучшие из полученных эвристических решений (для j60, j90 и j 120). Для примеров из j60, j90 и j120 приведены также наилучшие нижние оценки, полученные различными авторами на протяжении более двадцати лет.
Множества примеров j30, j60 и j90 состоят из 480 примеров каждое (48 серий примеров, 10 примеров в каждой серии). Множество j120 содержит 60 серий примеров со 120 фактическими работами, по 10 примеров в каждой серии, всего 600 примеров. Во всех примерах используются четыре типа ресурсов. Каждая серия примеров использует для своей генерации уникальную комбинацию из трех параметров: network complexity (NC) — сложность ориентированного графа отношения предшествования на множестве работ, resource factor (RF) - ресурсный фактор, и resource strength (RS) — параметр, характеризующий величину выделяемых ресурсов. Внутри одной серии примеров эти параметры фиксированы. Параметр NC означает среднее число непосредственных последователей для каждой работы. RF определяет среднее количество различных типов ресурсов, задействованных каждой работой. Параметр RS говорит о степени дефицитности ресурса. Нулевое значение параметра RS соответствует минимальной потребности каждого типа ресурсов для выполнения всех работ, в то время как значение RS = 1 соответствует количеству ресурсов, необходимому для выполнения наиболее раннего расписания. Для построения примеров из множеств j30, j60 и j90, были использованы следующие значения параметров: NC е {1.5,1.8, 2.1}, RF е {0.25,0.5,0.75,1} и RS е {0.2,0.5,0.7,1}. Для множества примеров j120 такие же параметры NC и RF, но RS мог принимать значения RS е {0.1,0.2,0.3,0.4,0.5}. Известно [80], что значения параметров RF = 1, RS = 0.2 соответствуют наиболее трудным сериям из множеств j30, j60 и j90 ( RF = 1, RS = 0.1 для j'120). Некоторые авторы (например, [60;
81]) указывали, что параметр RS является очень важным параметром с точки зрения качества решения точных и эвристических алгоритмов.
Среднее значение RS намного ниже для множества j 120, чем для остальных, а экземпляры с более низкими значениями RS являются наиболее трудными для решения, как указали несколько независимых исследований (например, [82; 83]). Идентификаторы ¿12016, ¿12036, ¿12056, ¿12011, ¿12031, ¿12051, где п = 120, соответствуют сериям с наибольшим разрывом между найденными наилучшими решениями и длиной критического пути. Для получения дополнительных сведений о тестовых задачах PSPLIB читатели могут обратиться к статьям [76; 77].
Описание параметров тестовых примеров можно найти в статье [76] и загрузить эти примеры по адресу http://www.om-db.wi.tum.de/psplib/. Показателем качества решения является среднее процентное отклонение (Average Percent Deviation, APD) полученных нижних оценок (Lower Bound, LB) для ЗРКПР от лучших нижних оценок (the Best Lower Bound, BLB), которые были взяты с веб-сайта PSPLIB.
, „ „ BLB — LB
APD = -ВЛГ- •100%
В приведенных таблицах серии примеров упорядочены в неубывающем порядке APD лучших эвристических решений (для множеств ¿60, ¿90 и ¿120) от нижних оценок, полученных с помощью алгоритма критического пути. Лучшие эвристические решения для множеств ¿60, ¿90 и ¿120 также взяты с сайта PSPLIB.
Таблицы 2.1 - 2.3 показывают APD полученных нижних границ от лучших известных нижних оценок и время (в миллисекундах), необходимое для их получения, для множеств примеров ¿60, ¿90 и ¿120 соответственно.
APD оптим. APD LB Сред. APD оптим. APD LB Сред.
Серия решения от от BLB, время, Серия решения от от BLB, время,
критич. пути, % % мс критич. пути, % % мс
45 71.57 7.77 3.3 18 0.81 0.77 3.6
13 70.62 4.38 4 6 0.70 0.68 5
29 65.00 6.99 3.5 23 0.40 0.38 3.1
41 57.32 16.93 3.3 10 0.16 0.15 6.4
25 48.62 14.50 3 43 0.14 0.13 3
9 40.35 11.10 4.3 39 0.12 0.12 3
37 33.21 18.91 3.1 4 0 0 5.2
21 33.12 20.25 3.1 7 0 0 4.1
5 27.85 15.54 4.89 8 0 0 4.7
33 10.65 9.29 3.1 11 0 0 3.9
1 9.98 8.59 3.4 12 0 0 3.2
17 9.87 8.57 3 15 0 0 2.9
46 5.45 4.85 3.3 16 0 0 3
30 3.36 3.11 3.2 20 0 0 3
42 3.03 2.82 3.4 24 0 0 3.8
2 2.41 2.26 3.2 27 0 0 3.2
34 2.30 2.18 3.2 28 0 0 3.3
26 2.11 2.01 3.3 31 0 0 3.1
3 1.98 1.89 3.6 32 0 0 3.3
22 1.87 1.69 3.1 36 0 0 3.5
38 1.75 1.66 3.1 40 0 0 3
35 1.32 1.28 3.1 44 0 0 3
19 1.30 1.25 3.1 47 0 0 3
14 1.09 1.02 2.9 48 0 0 3.5
Как можно заметить в таблице 2.1, самые "простые" серии с нулевым APD оптимального решения от решения, полученного алгоритмом критического пути, алгоритм Л.зРКП решает точно. Далее с увеличением сложности серий точность полученных решений ухудшается, своей наименьшей точности алгоритм достигает для серии 21, а затем начинается улучшение точности с ростом сложности.
APD оптим. APD LB Сред. APD оптим. APD LB Сред.
Серия решения от от BLB, время, Серия решения от от BLB, время,
критич. пути, % % мс критич. пути, % % мс
45 67.66 3.07 4.3 7 0 0 5.4
13 56.98 2.15 4.1 8 0 0 6.4
29 56.98 3.29 3.8 10 0 0 10.4
41 52.31 5.71 4.2 11 0 0 7.1
25 47.92 4.39 4 12 0 0 5.6
9 46.25 2.47 5.4 14 0 0 4.1
37 32.09 16.01 5.1 15 0 0 3.8
21 28.98 15.89 4 16 0 0 4
5 24.72 6.40 6.4 18 0 0 4.3
1 9.73 8.00 5 19 0 0 4.3
17 9.69 8.55 4.2 20 0 0 4.1
33 8.38 7.36 4.4 23 0 0 4.3
46 3.82 1.36 4.2 24 0 0 4.5
42 2.28 2.12 4.1 27 0 0 4.1
30 1.46 0.33 4.4 28 0 0 4.5
34 1.42 1.35 4.3 31 0 0 4.3
38 0.72 0.71 4.4 32 0 0 3.5
26 0.47 0.10 4.4 36 0 0 3.8
6 0.42 0.41 5 39 0 0 4.8
22 0.41 0.40 4.3 40 0 0 4.9
35 0.10 0.10 4.5 43 0 0 4.5
2 0 0 5.8 44 0 0 4.1
3 0 0 7.3 47 0 0 4.4
4 0 0 5.8 48 0 0 4.5
Из результатов таблицы 2.2 можно сделать вывод, что аналогичная ситуация для множества примеров ¿90, однако в этом множестве примеров больше "простых" серий, т.е. серий APD с нулевым отклонением BLB от LB больше. Стоит отметить, что в худшем случае для ¿90 получается это значение 16.01 процентов для серии 37, в то время как для ¿60 — 20.25 процентов для серии 21.
Серия APD оптим. решения от критич. пути, % APD LB от BLB, % Сред. время, мс Серия APD оптим. решения от критич. пути, % APD LB от BLB, % Сред. время, мс
56 152.97 5.14 17 22 11.40 9.82 9.6
16 142.37 1.23 8.6 42 11.31 8.62 16.8
36 128.01 1.73 9.1 39 8.82 1.32 15.3
51 122.72 4.33 16.6 19 8.55 1.41 10.5
31 108.93 1.88 14 54 8.19 3.93 16.3
11 105.57 1.64 12.3 8 6.90 4.22 10.6
6 74.41 4.63 8.1 28 5.69 4.23 10.4
46 71.79 8.45 16 34 5.45 2.41 10.7
26 67.68 7.02 14.6 43 4.68 4.33 15.2
37 64.75 1.98 10.7 49 4.19 3.79 15.3
57 64.46 1.46 15.4 60 3.93 1.46 18.7
17 59.30 1.51 11.4 14 3.65 1.37 11.2
52 54.02 3.09 17.4 29 2.74 1.53 12.5
12 53.25 2.78 12.7 44 1.91 1.79 15.8
32 39.92 2.61 9.6 4 1.60 1.52 9.9
47 32.83 6.32 16.4 23 1.19 1.15 10
27 31.73 4.63 11.6 24 1.17 1.11 11.5
58 30.72 2.41 15.9 9 0.75 0.48 10.5
7 29.80 5.21 14.7 25 0.75 0.72 11.5
18 25.78 2.56 10.6 50 0.64 0.60 15.8
1 25.12 14.71 11 3 0.50 0.48 10
41 24.67 16.54 16.1 20 0.41 0.13 10.3
38 24.30 2.10 12.2 40 0.38 0.13 14.9
21 21.07 14.05 12.2 55 0.31 0 15.4
53 19.06 2.83 15.6 30 0.25 0.24 12.8
33 18.62 2.84 11.3 45 0.18 0.17 16.5
13 13.43 4.21 9.6 5 0 0 15.3
48 12.74 6.91 14.9 10 0 0 9.4
2 12.74 10.34 13.2 15 0 0 10.10
59 11.80 3.31 16.6 35 0 0 12.10
В таблице 2.3 множество примеров ¿120 содержит более "сложные" серии, всего лишь 4 серии с APD оптимального решения от решения, полученного алгоритмом критического пути, равным нулю, это достигается за счет комбинации параметров NC, RF, RS, упомянутых выше. Однако в худшем случае получается значение 16.54 процентов для серии 41, что лучше, чем для ¿60, и незначительно хуже, чем для ¿90. Также можно заметить, что трудные серии для ¿120 лучше поддаются решению с помощью алгоритма ДзРКП, чем для 60 и 90
Таблица 2.4 — Нижние оценки для примеров из двух трудных серий 11 и 16 из множества примеров ¿120.
Серия Пример APD луч. реш. от критич. пути, % BLB (из PSPLIB) Получ. LB APD LB от BLB, % Время, мс
j120 16 1 176.06 179 178 0.56 7
j120 16 2 171.76 218 214 1.83 6
j120 16 3 141.24 219 215 1.83 6
j120 16 4 150.00 189 188 0.53 6
j120 16 5 117.39 184 181 1.63 7
j120 16 6 159.49 194 193 0.52 7
j120 16 7 105.56 174 172 1.15 14
j120 16 8 151.95 182 178 2.20 6
j120 16 9 132.95 188 186 1.06 15
j120 16 10 117.35 202 200 0.99 12
j120 11 1 91.11 155 152 1.94 7
j120 11 2 102.56 145 144 0.69 11
j120 11 3 117.20 186 182 2.15 16
j120 11 4 103.13 177 170 3.95 7
j120 11 5 116.49 191 190 0.52 7
j120 11 6 130.77 189 184 2.65 8
j120 11 7 97.56 148 146 1.35 14
j120 11 8 70.53 151 149 1.32 14
j120 11 9 126.32 167 166 0.60 34
j120 11 10 100.00 163 161 1.23 5
В таблице 2.4 приведены, в качестве примера, нижние оценки для каждого экземпляра из двух таких трудных серий: серии 16 и серии 11 из множества примеров ¿120. Как можно видеть, все APD решений, полученных с помощью
алгоритма Л.зРКП, от лучших нижних границ составляют не более 4 процентов, что подтверждает конкурентоспособность предлагаемого алгоритма.
На основе данных этих таблиц можно сделать вывод, что качество нижних оценок возрастает с увеличением размерности задачи. Получены нижние оценки, очень близкие к наиболее лучшим известным нижним оценкам для трудных серий примеров из множества] 120 (см. таблицу 2.3), имеющих наибольший разрыв между найденными наилучшими решениями и длиной критического пути. Для каждого случая приведены две оценки: лучшая известная (БЬБ) и полученная ЬБ предлагаемым алгоритмом, отклонение последней от БЬБ, а также время на ее нахождение.
Среднее процессорное время на обычном настольном ПК по всем экземплярам каждого из множеств примеров ]60, ]90 и ] 120 составляло 3.4, 4.8 и 13.4 миллисекунды соответственно.
3.1 Предварительные сведения
Задача поиска минимального остовного дерева (Minimum Spanning Tree, MST) широко известна, она состоит в нахождении остовного дерева (связного ациклического подграфа на всех вершинах) минимального веса в данном реберно-взвешенном графе G = (V,E). Полиномиальная разрешимость этой задачи была доказана построением полиномиальных алгоритмов О. Борувки (1926), Дж. Краскала (1956) и Р. Прима (1957). Эти алгоритмы имеют трудоемкости О (и log п), О (и log и) и 0(п2) соответственно, где и = IE | и п = |У |. Интересно отметить, что математическое ожидание веса MST в графе со случайными весами ребер может быть неожиданно маленьким. Например, для полного графа с весами ребер из класса равномерно распределенных случайных величин на интервале (0; 1) вес MST с высокой вероятностью близок к константе 2.02 [84]. Похожие результаты получены в работах [85; 86].
Одним из обобщений рассматриваемой задачи может быть задача отыскания нескольких реберно-непересекающихся остовных деревьев минимального суммарного веса, эта задача тоже полиномиально разрешима [87]. Другим обобщением является вариант задачи поиска MST с ограниченным диаметром. Диаметр дерева — это количество ребер в самом длинном простом пути в дереве, соединяющем пару вершин. Первая задача, рассматриваемая в данной главе, включает оба этих обобщения.
Задача с ограниченным диаметром состоит в следующем: дан реберно-взвешенный граф и число d, необходимо найти в этом графе MST, имеющее диаметр, ограниченный сверху или снизу числом d. Обе задачи в общей постановке являются .^"Р-трудными.
Задача с ограничением на диаметр сверху является полиномиально разрешимой для значений диаметра 2 и 3, и ^"Р-трудной для любого диаметра между 4 и (п — 1), даже для весов ребер, равных 1 или 2 [3]. Задача с ограничением снизу является ^"Р-трудной, потому что она в качестве специального
подслучая, когда диаметр равен (п — 1), содержит в себе задачу поиска гамиль-тонова пути в графе.
Способы решения задачи поиска минимального остовного дерева с диаметром, ограниченным сверху, могут быть разделены на 2 класса: точные методы и эвристические методы, т.е. алгоритмы без гарантированных оценок точности алгоритма. Для данной задачи в общей постановке не существует алгоритмов с гарантированными константными оценками точности, что следует из работы П. Маньема и М. Столлманна [88], где данный результат получен для задачи поиска минимального остовного дерева с ограниченной высотой.
Точные алгоритмы для решения этой задачи основываются на представлении задачи в виде задачи целочисленного линейного программирования [89; 90] и булевого линейного программирования с применением метода ветвей и границ [91]. Но эти подходы могут быть использованы для решения только небольших примеров задачи, для полных графов с менее, чем 100 вершинами.
В работе [92] предложен жадный эвристический алгоритм одноразового построения дерева (One Time Tree Construction) для решения этой задачи, а также модификация этого алгоритма, рандомизированная жадная эвристика [93]. Позже эти идеи были трансформированы и в дальнейшем улучшены в [94; 95]. Генетические алгоритмы для решения задачи поиска минимального остовного дерева с ограниченным сверху диаметром были предложены в [96—99]. Поиск с чередующимися окрестностями исследован в [100; 101].
Ранее в статьях [7; 15; 16; 18; 102; 103] был изучен асимптотически точный подход для задачи поиска MST с диаметром дерева, ограниченным снизу или сверху. Стоит отметить реализацию такого подхода для решения задачи с ограничением снизу на диаметр дерева, представленный в [7; 16]. Работа [7] является пионерской для асимптотически точного подхода к решению задачи о минимальном остове с ограниченным диаметром. В этой работе рассматривается равномерное распределение весов ребер графа, в котором ищется остов с диаметром не меньше заданного числа, для непрерывного и дискретного классов. Также там установлена MV-трудность задачи минимального остовного дерева с диаметром ограниченным снизу в полном неориентированном графе. В [16] продолжается анализ того же самого алгоритма, но для случая смещенно-усе-ченных вероятностных распределений: экспоненциального и нормального.
Недавно начала изучаться другая модификация задачи поиска MST с ограниченным диаметром, когда диаметр дерева фиксирован, т.е. равен за-
данному числу, и в данной работе рассматривается задача нахождения т реберно-непересекающихся остовных деревьев минимального суммарного веса с фиксированным диаметром d в полном неориентированном графе. Эта задача обозначается m-d-UMinST. Данная задача MV-трудна, потому что для т =1 и d = п — 1 это задача поиска минимального гамильтонова пути. Предлагается приближенный полиномиальный алгоритм решения m-d-UMinST и условия его асимптотической точности. Вероятностный анализ проведен при условии, что веса ребер входного графа — случайные величины, распределенные согласно равномерному UNI(an; bn), смещенному усеченно-экспоненциальному EXP(an, Лп) и смещенному усеченно-нормальному NORM(an, ап) распределениям. Предлагаемый алгоритм может быть преобразован в алгоритм решения задачи поиска т реберно-непересекающихся остовных деревьев минимального суммарного веса с ограниченным диаметром как снизу, так и сверху в полном неориентированном графе. Таким образом, все практические применения этих задач также верны и для задачи m-d-UMinST (см., например, [13; 14]).
Также в работе рассматривается задача поиска одного максимального остовного дерева с фиксированным диаметром D в полном неориентированном графе, эта задача обозначается как D-UMaxST. Эта задача также MV-трудна, поскольку в качестве специального случая для D = п — 1, она содержит задачу поиска максимального гамильтонова пути. Для решения D-UMaxST построен приближенный алгоритм, который основан на решении задачи отыскания минимального остовного дерева с фиксированным диаметром D в полном неориентированном графе, обозначается через D-UMinST. Получены условия асимптотической точности предлагаемого алгоритма для задачи на максимум в случае равномерно распределенных UNI(0; 1) весов ребер графа, из чего следуют аналогичные условия для случая UNI(an; Ьп).
3.2 Нахождение т реберно-непересекающихся остовных деревьев минимального суммарного веса с фиксированным диаметром d в
полном неориентированном графе
В данном разделе сначала формулируется исследуемая задача, а затем предлагается приближенный алгоритм ее решения.
Пусть дан полный п-вершинный реберно-взвешенный неориентированный граф С = (V, Е) и положительные целые числа т и (1 такие, что т(3 +1) ^ п. Задача т-б?-иМт8Т состоит в отыскании т реберно-непересекающихся остов-ных деревьев Т1,... ,Тт таких, что диаметр каждого из них равен (1 = Зп, и их суммарный вес минимален. Для решения этой задачи предлагается следующий алгоритм.
Описание алгоритма Л
Предварительный шаг 0. В графе С выбрать произвольное (п -т((! + 1))-вершинное подмножество V' и произвольно разбить оставшиеся т(3 + 1) вершин на т подмножеств VI..., Vm с (3 +1) вершиной в каждом.
Шаг 1. В каждом подграфе в = 1,... ,т, начиная с произвольной
его вершины, построить (3 + 1)-вершинный гамильтонов путь Р8, используя жадную эвристику "иди в ближайшую непосещенную вершину". Положить Т8 = Р8, в = 1,... ,т. Если т > 1, то на шаг 2, иначе на шаг 3.
Шаг 2. Далее предполагается без потери общности, что параметр d нечетен (см. замечание 2 ниже). Для каждой пары путей Р и Р^, 1 ^ % < j ^ т, добавить вершины из Р^ в Т; и из Р; в Т' так, чтобы построенный подграф состоял из двух 2(3 + 1)-вершинных реберно-непересекающихся поддеревьев с диаметром, равным (1. Каждый путь Р8, 1 ^ в ^ т, рассматривается в виде двух половин (подпутей) Р1 и Р,2, каждая из которых содержит одну концевую вершину и внутренних вершин пути Р8, суммарно вершин в каждой половине.
Построение реберно -непересекающихся остовных деревьев Т и Тj с помощью вершин из половин Р1, Р2 и половин Р^, Р2 описано в следующих пунктах 2.1-2.6.
2.1. Соединить каждую внутреннюю вершину Р1 кратчайшим ребром с внутренней вершиной Р^ и добавить это ребро в Т.
2.2. Соединить каждую внутреннюю вершину Р2 кратчайшим ребром с внутренней вершиной Р2 и добавить это ребро в Т.
2.3. Соединить каждую внутреннюю вершину Р^ кратчайшим ребром с
внутренней вершиной Р2 и добавить это ребро в Т.
2.4. Соединить каждую внутреннюю вершину Р^ кратчайшим ребром с внутренней вершиной Р] и добавить это ребро в Т].
2.5. Соединить каждую концевую вершину пути Р] кратчайшим ребром с внутренней вершиной пути Р^ и добавить это ребро в ^.
2.6. Соединить каждую концевую вершину пути Р^ кратчайшим ребром с внутренней вершиной пути Р] и добавить это ребро в Т].
!Шаг 3. В цикле по з = 1,... ,т каждую вершину подграфа С(У) соединить кратчайшим ребром с внутренней вершиной пути Р8 и добавить это ребро в соответствующее дерево Т3. Описание алгоритма Л закончено.
Рисунок 3.1 — Изначальные вершины графа и шаг 0 работы алгоритма Л на 16-вершинном полном графе, т = 2, d = 5.
Рисунок 3.2 — Шаги 1 и 2 работы алгоритма Л на 16-вершинном полном графе, т = 2, d = 5. Заштрихованные вершины — это концевые вершины. Сплошные ребра принадлежат дереву Т\. Точечные ребра — дереву Т%.
Рисунок 3.3 — Шаг 3 работы алгоритма Л на 16-вершинном полном графе, т = 2, й = 5. Заштрихованные вершины — это концевые вершины. Сплошные ребра принадлежат дереву Т\. Точечные ребра — дереву
Замечание 2. В случае четного параметра d нужно немного модифицировать алгоритм. На шаге 1 для каждого пути для первой выбранной вершины необходимо найти ближайшую вершину у3, з = 1,..., т за с1 действий, первую выбранную вершину для каждого пути пометить и использовать ее после выполнения шагов алгоритма. Далее, выполнить все шаги алгоритма для $ = (I — 1, где первая вершина каждого пути — это вершина у3, и после выполнения шага 3 соединить помеченные вершины с уже найденными ближайшими к ним вершинами у3, з = 1,...,т. В итоге, создаются остовные деревья, диаметр каждого из которых равен в точности в,, при этом оценка для трудоемкости алгоритма останется прежней.
Утверждение 3.2.1. Алгоритм Л строит допустимое решение задачи т-й-иЫтБТ.
доказательство. Каждая из полученных реберно-непересекающихся конструкций состоит из п вершин и (п — 1) ребер, т.к. сначала на шаге 1 строится ((! + 1)-вершинный путь и затем на шагах 2 и 3 к нему присоединяются все остальные вершины графа, не увеличивая диаметр построенного остовного дерева. В конце получается т таких конструкций — остовных деревьев, представляющих допустимое решение задачи т-^-иМтБТ. Утверждение 3.2.1 доказано.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.