Содержание к диссертации
Введение
1. Постановка задач исследования 9
1.1. Обзор методов сетевого планирования и управления (СПУ) 9
1.1.1. Построение сетевой модели комплекса работ. Типы сетевых графиков и их преобразования 11
1.1.2. Использование сетевой модели для планирования и управления при реализации комплекса работ 14
1.2. Задачи исследования 18
2. Эффективный синтез сетевой модели «работы - дуги» 19
2.1. Формирование сетевого графика «работы - дуги», исходя из списков предшествующих операций 19
2.2. Алгоритм добавления фиктивных операций с целью исключения пересечений списков предшественников 24
2.3. Генерация событий 24
2.4. Эффективность метода 26
2.5. Порядок сравнения списков предшествующих операций 33
3. Комплексная оптимизация проекта с выпуклой ломаной зависимостью (влз) «стоимость - время» 3 5
3.1. Поиск минимального сечения в сети критических работ 35
3.2. Сечение резервной подсети проекта 36
3.3. Накопительный итерационный метод для определения лимита сечения резервной подсети 37
3.3.1. Алгоритм выравнивания минимальных резервов 3 8
3.3.2. Пример по накопительному итерационному методу 40
3.4. Вычисление величины возможного сокращения проекта 43
4. Структурная оптимизация при реализации комплекса работ с разработкой и применением десуперпози-ционных и декомпозиционных методов 44
4.1. Понятие метода диакоптики 44
4.2. Минимальные подсети 46
4.3. Алгоритм десуперпозиции сети 46
4.4. Алгоритм объединения нескольких последовательных операций 48
4.5. Алгоритм объединения кратных операций 49
4.6. Десуперпозиция модулей 49
4.6.1. Основные понятия 49
4.6.2. Основная теорема 52
4.6.3. Оценка количества Групп из ПослеНачал (ГПН) 53
4.6.4. Алгоритм выделения модулей 57
4.6.5. Пример к алгоритму с оценкой С? (mn ) 57
4.6.6. Итерационный процесс с удалением пройденных дуг 59
4.6.7. Применение итерационного процесса к фрагменту сети 60
4.7. Удаление и (или) стягивание дуг-операций и антипараллельная де-суперпозицией 61
4.8. Примеры построения составных квазидуг на основе параллельной и антипараллельной десуперпозиции 67
Основные результаты и выводы 70
Список литературы
- Построение сетевой модели комплекса работ. Типы сетевых графиков и их преобразования
- Алгоритм добавления фиктивных операций с целью исключения пересечений списков предшественников
- Накопительный итерационный метод для определения лимита сечения резервной подсети
- Алгоритм объединения нескольких последовательных операций
Введение к работе
Актуальность темы. В эпоху рыночных экономических отношений возрастает роль эффективных сетевых проектов, используемых экономистами, финансистами, политиками, учеными, инженерами и другими специалистами во всех сферах общественной и производственной деятельности. Об этом свидетельствует появление множества программных продуктов по сетевому планированию и управлению (СПУ): за рубежом [39, 54], а в России - следующих наиболее доступных пользователю: Microsoft Project, Project Expert, Time Line, Project Management Software, Primavera Project Planner, Галактика, Проект-Менеджмент и других.
Любая деятельность имеет вполне определенную структуру, которая может быть представлена в виде графа, то есть частично упорядоченного множества отдельных операций - работ. СПУ основано на моделировании процесса с помощью сетевого графика - ориентированного графа без контуров. Использование вычислительной техники способствует развитию области применения сложных сетевых проектов, отличающихся большим количеством работ и (или) сложными их взаимосвязями.
В классическом сетевом планировании нередко крупная операция, в свою очередь, является комплексом работ, образующих подсеть. При этом составные проекты рассматриваются, по существу, в виде суперпозиций более простых проектов-операций. Суперпозиция проектов становится естественной и наглядной при их представлении в виде двухполюсных сетей «работы - дуги», вершинами которых являются события, то есть стыки окончаний предшествующих операций и начал следующих за ними операций. Построение таких сетей часто невозможно без введения фиктивных операций, отражающих порядок следования.
В основных положениях по разработке и применению СПУ [74], а также в существующих методах СПУ [14, 55, 66, 71, 100, 105, 108] отсутствуют методы, алгоритмы и программы по построению эффективных сетевых графиков сложных проектов типа «работы - дуги» с минимальным количеством фиктивных работ. Построение сетевых моделей базируется на использовании ряда правил, на опыте и знаниях ответственного исполнителя, логически выстраивающего технологические цепочки последовательности работ [10, 44, 80, 91]. При этом имеет место многовариантность и большая трудоемкость процесса проектирования. Так, например, для проекта со ступенчатым набором предшественников из п операций количество фиктивных операций может изменяться от порядка линейного до я2, а для проекта с полным набором предшественников из п операций, частью которого является любой другой проект, может изменяться от 2{Т- п -1) до п2"-\
Структурная оптимизация сетевых графиков «работы - дуги» на этапе проектирования, приводящая к уменьшению количества вершин и дуг сети, способствует также повышению эффективности их реализации в оптимизационных алгоритмах. Такие двухполюсные сети используются, например, при оптимизации сетевых графиков по критерию «время - затраты». Об актуальности данной оптимизации свидетельствуют труды ряда учёных: Wu Y and Li С (1994), Kamburowski J (1995), De P и другие (1995, 1997), Demeulemeester E и другие (1996, 1998), Skutella M (1998), Akkan С и другие (2000), Yang HH и Chen YL (2000), Vanhoucke M и другие (2002).
К сожалению, практически во всех доступных современных программах по СПУ [59, 80, 99] не подсказываются оптимальные решения в части управления затратами (так же, как и по любому другому вопросу). Они лишь обеспечивают возможность достаточно серьёзного анализа отчётных и плановых показателей на основании данных графика. Переход от анализа «узких мест» к процессу принятия решения вызывает качественное усложнение - замену простой имитационной схемы производства его оптимизационной моделью. Такой метод управления проектами является, несомненно, полезным.
Ранее разработкой сетевых графиков занимались целые коллективы специалистов. В современных условиях при сетевом моделировании деятельности необходимо учитывать дополнительные обстоятельства:
1) На практике приходится рассматривать все более сложные проекты, при этом теряется наглядность и возможность увидеть структуру сети непосредственно.
2) Производство требует оперативного управления, поэтому время и стоимость сетевого планирования должны быть по возможности малыми, то же можно сказать о времени и стоимости самого производства.
3) Управление должно быть надежным и вместе с тем доступным как руководству, так и разработчику проекта, совсем не обязательно являющемуся специалистом в соответствующих областях экономической математики и информатики.
4) Необходимо в полной мере использовать фантастические возможности ЭВМ для создания эффективного программного обеспечения с удобным интерфейсом.
В процессе оптимизации двухполюсных сетей «работы - дуги» актуальны: 1) обратная, ранее не рассматривавшаяся задача десуперпозиции сети, заключающаяся в рекурсивном выделении двухполюсных подсетей проекта; 2) декомпозиционные задачи.
Цель работы. Упрощение структуры сложных сетевых графиков «работы - дуги» на этапах проектирования и оптимизации.
Методы исследования. Использован теоретико-множественный подход. Теоретические исследования проведены на базе методов теории ориентированных графов.
Численный анализ сетевых моделей проведён на ЭВМ с использованием принципов построения программного обеспечения [48, 50, 60, 77].
Научная новизна:
Разработаны новые методы структурной оптимизации:
преобразования сетевого графика «работы - вершины» в сетевой график «работы - дуги», основанный на исключении пересечения списков предшествующих операций с целью уменьшения количества фиктивных работ;
десуперпозиции сети, основанный на итеративной комбинации последовательных и параллельных десуперпозиции (ГШД), перемежаемых с модульной десуперпозицией;
У декомпозиции проекта на критическую и резервные подсети, заключающийся в удалении резервных и (или) стягивании насыщенных дуг с применением ППД (в том числе антипараллельной) при поиске минимального сечения критической подсети, а также в вычислении лимита сечения резервной подсети.
Теоретическая и практическая ценность:
1. Результаты диссертации могут быть использованы для дальнейшего развития теории СПУ.
2. Создана программа синтеза сетевой модели «работы - дуги» с малым количеством фиктивных работ на основе исключения пересечений списков предшествующих работ. Программа может быть использована на стадии проектирования и в учебном процессе. Проектировщикам не потребуется выявлять и нумеровать события и фиктивные операции, а достаточно только составлять для каждой операции список опорных операций. Это уменьшает трудоёмкость и сокращает процесс разработки. Программа учитывает встречающуюся на практике возможность переопределения отношения порядка, когда пользователь (даже порой искушенный [110]) наряду с необходимыми непосредственно предшествующими операциями указывает по ошибке и некоторые операции дальнего предшествования. Последние выявляются и удаляются.
3. Предложены эффективные алгоритмы десуперпозиции сети, которые могут использоваться не только в сетевом планировании, но и в других приложениях сетей, в частности, в потоковых задачах.
Реализация работы. Практическими результатами работы явились_разра-ботки математического и программного обеспечения по построению и оптимизации сетевой модели «работы - дуги», зарегистрированные в отраслевом фонде алгоритмов и программ (ОФАП) и в Информационно-библиотечном фонде РФ. Результаты использованы в научно-исследовательских работах, выполняе мых на кафедре «Информационные системы и технологии» Челябинского института (филиала) Московского государственного университета коммерции (Российского государственного торгово-экономического университета) в 2000-2004 г.г., а также используются при чтении лекций и выполнении лабораторно-практических занятий по дисциплине «Высшая математика» и «Экономико-математические методы».
Апробация работы. Основные положения диссертационной работы докладывались на научно-технических конференциях, симпозиумах и методических семинарах: "International Conference Distributed Systems: Optimization and Economic-Environmental Applications" Ekaterinburg, 30 May-2 June 2000; конференция «Вычислительные технологии - 2000», Новосибирск; Всероссийская конференция «Алгоритмический анализ неустойчивых задач», Екатеринбург, 26 февраля-2 марта 2001 г.; Симпозиумы по прикладной и промышленной математике, Сочи, 2000, Самара, 2001, Сочи 2002; Сочи 2004, а также на научных конференциях и методических семинарах ЧИ (ф) МГУК (РГТЭУ) в 2000 -2004 г.г., семинарах ЧелГУ, ЮУрГУ 2004 г.
Публикации. По материалам диссертации опубликовано 24 работы.
Построение сетевой модели комплекса работ. Типы сетевых графиков и их преобразования
Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графиком. Сетевой график - это ориентированный граф без контуров (directed acyclic Graph; это английское название иногда сокращают до «dag»), рёбра или вершины которого имеют одну или несколько числовых характеристик. Ориентированные рёбра называются дугами.
На практике встречаются сетевые графики с различной структурой: типа «работы - вершины» и «работы - дуги». На стадии разработки удобнее составить сеть типа «работы - вершины», а в процессе управления удобнее пользоваться сетью типа «работы - дуги». Так, например, сеть типа «работы - вершины» предпочтительна при частых изменениях состава и структуры проекта, так как отображение этих изменений в сети типа «работы - вершины» производится непосредственно, а в сети типа «работы - дуги» может потребовать существенной перестройки. Построение сетей типа «работы - вершины» предпочтительнее ещё и потому, что не требует введения дополнительных элементов в виде фиктивных работ. Фиктивной работой (зависимостью) называется связь между какими-то результатами работ (событиями), не требующими затрат времени вообще или требующая минимальных затрат времени, не отражаемых в сетевой модели.
Преобразование сети проекта в сопряжённую необходимо также в случае, когда имеющееся математическое обеспечение ориентировано на другой тип сети.
Переход от сети типа «работы - дуги» к сопряжённой осуществляется однозначно и без затруднений. Решение обратной задачи неоднозначно, поскольку существуют различные эквивалентные сети типа «работы - дуги», отличающиеся составом событий и фиктивных работ, и поэтому потребуется структурная оптимизация. Преобразование типа сети легко осуществить растяжением каждой вершины-работы в дугу (/ , к), представленную парой номеров начального (/ ) и конечного (к) событий, принадлежащих множеству вершин новой сети типа «работы - дуги». Прежние дуги-связи называют фиктивными работами [56, 84, 101]. Однако при этом резко увеличивается число узлов и дуг.
Фиктивные работы - это просто связи, и функции на них не определены. Количество фиктивных работ стремятся сократить [84, 92, 108].
В частности, в монографии Эддоуса М. и Стэнсфилда Р. [108] предлагается исключить из рассмотрения фиктивные операции с помощью простого практического правила: «если единственной операцией, выходящей из некоторого узла, является фиктивная логическая операция, то по всей вероятности без неё можно обойтись». Но только этим правилом не исключить все ненужные фиктивные операции.
Наиболее полные варианты сокращения предложены в [84]. «Прежде всего, объединяются начальные события для работ с одинаковым составом непосредственно предшествующих работ и конечные события для работ с одинаковым составом непосредственно следующих работ. Кроме того, исключаются фиктивные работы (/,/), удовлетворяющие следующему условию: каждая работа, непосредственно предшествующая событию j, является предшествующей также для любой работы, непосредственно следующей за событием і. Работа (/,/) исключается также в частном случае, если (i,f) является единственной выходящей для г -го события или единственно входящей для у -го. » В результате исключения дуги (i,j) события і и у объединяются. Как сказано в данной работе, «машинные варианты приведённых алгоритмов требуют некоторой модификации в связи с необходимостью представления всей исходной информации в числовой форме, ограниченностью оперативной памяти машины, а также в связи с существенным возрастанием времени счёта при использовании внешней памяти». Что касается оперативной памяти, то это становится не самым актуальным фактором. Однако просматриваются две проблемы.
Одна из них - насколько полными являются предложенные варианты сокращения? Их нельзя оценивать, как конечный результат по минимизации фик тивных работ, так как анализ уже 1-го примера из п.2.1 диссертации показывает, что возможно меньшее количество фиктивных работ.
Другая проблема - обязательно ли первоначально формировать полный список фиктивных операций, а потом его сокращать? Возможно ли создание алгоритмов с меньшей продолжительностью счёта и меньшим объёмом памяти, а главное, позволяющих вводить малое количество фиктивных работ?
Возникает идея алгоритма преобразования типа в некотором смысле противоположного: вначале добавить только необходимые фиктивные операции, после чего генерировать события.
Среди большого списка просмотренной учебной и научной литературы [2-14, 39-75, 77-161] нечто похожее удалось найти только в работе Гришина А.П. [13] - это «синтез рёберной сетевой модели на основе расширения матрицы бинарных отношений непосредственного предшествования элементарных работ». Показано, что расширенная квадратная матрица AN, элементы которой -нули и единицы, удовлетворяет условиям теоремы о свойствах матрицы смежности рёбер ориентированного графа. «Это означает что, либо в тех столбцах с номерами у, где ау = 1, другие строки матрицы AN не имеют ненулевых элементов, либо другие строки полностью совпадают со строкой і».
Необходимо учесть исключение ненужных элементарных фиктивных операций. Например, для рассмотренной матрицы А\0 на стр. 51 не следовало разрушать отношения 3 - 7, 7 - 5, 10 - 5 добавлением 13, 17, 19 строк и столбцов в предложенном рис. 3.6. Расширенная матрица Л16 вместо А\ч по-прежнему обладала бы свойствами матрицы смежности рёбер.
Предлагаемый в [13] алгоритм составления матрицы смежности вершин, исходя из матрицы смежности рёбер, сложнее предлагаемого в диссертации нового элементарного алгоритма генераций событий, в котором одинаковым множествам опорных работ соответствует одно событие.
Алгоритм добавления фиктивных операций с целью исключения пересечений списков предшественников
После устранения пересечений множеств G_(a() генерируются события по одному на каждую группу G_(at) одинакового состава, начиная с G_(#,)=0. Завершающее событие соответствует окончанию операций, для которых G_-\ad=0.
Рассмотрим пример построения сетевого графика. Упорядоченный перечень элементарных работ, всех логических связей, очередность выполнения работ, а также длительности выполнения каждой работы представлены в виде структурно-временной таблицы 2.3.
Из таблицы видим, что работы а\, aj не имеют опорных работ, это - начальные работы. После окончания работы а\ начинаются две работы - работы а3 и а4 . После работы аз начинаются работы а5 и а7 Работы я4, а5 и работы ав, а7 заканчиваются одновременно и после них выполняются работы а% и а соответственно. Работа а% и ад не являются опорными - это завершающие работы. Все опорные работы естественным образом подразделяются на пять непересекающихся групп: (а{), (аз), (аг), (а4, а5), (а , aj), заканчивающихся пятью событиями, которые пронумеруем в порядке записи (1), (2), (3), (4), (5). Добавим к ним событие (0), в котором начинаются работы а\ и а2. Номера групп опорных работ определяют начальные события перечня работ в таблице 2.4 (графа 3). Для определения конечных событий перечня работ (графа 4) используются те же группы опорных работ. Например, ясно, что работа а3 входит в группу (аз) и заканчивается событием (2), а работы а4 и а5 входят в группу (а4, а5) и завершаются событием (4). Завершающие работы а$ и я9 заканчиваются событием (6). В общем случае работы определяются тройкой чисел (as, і, j), где as - номер работы, / - номер начального события, j - номер конечного события. Кратные дуги as имеют одинаковые инцидентные события i,j, поэтому для них вводится номер дуги 5.
Алгоритмы реализованы на PC IBM. Следующий пример (табл. 2.5) показывает преимущество предложенной методики проверки взаимного вложения полных списков предшественников и генерации событий исключением пересечений.
Результаты вычислений приведены в таблице 2.6; где в графе а,- - полный перечень операций, включая фиктивные; операции с одинаковыми предшественниками сгруппированы так, что начальное событие группы последующих операций совпадает с конечным событием группы предшественников.
При учёте вложенностей G+(a,) добавляются 8 фиктивных операций, иначе потребовалось бы 11 фиктивных операций.
Эффективность метода по уменьшению количества фиктивных работ проверена на нескольких важных классах тестовых задач, охватывающих практически все встречающиеся составные части проектов: класс задач со Ступенчатым Набором Предшественников из п операций (СНПя), класс задач с Полным Набором Предшественников из п операций (ПНПя); класс задач с (п - 1) Элементными Наборами Предшественников из п операций (п - 1ЭНШ).
В частности, для класса задач со Ступенчатым Набором Предшественников из п операций (СНПл), представленного в таблице 2.7:
Задача из класса СНПя, как и любая другая задача, являются частью задачи из класса с Полным Набором Предшественников из п операций (ПНПгс). ПНПя требует большого количества фиктивных операций. Но и в этом случае предложенный метод приводит к сокращению количества фиктивных работ до минимально возможного. Например, для п = 3 данные для проекта представлены в таблице 2.9, а соответствующий сетевой график «работы - дуги» с минимальным количеством фиктивных работ - в таблице 2.10.
Для ПНПл добавляется всего 2(2" - п -1) фиктивных операций из возможных п2п х связей. Их отношение составляет: 2{2п-п-\) _ 4(2"-к-Г) _ 4 п + 1 п2п х п2п п 2" Результаты по количеству фиктивных работ для ПНПл при п = 1, ..., 10 отражены в таблице 2.11, а представление исходных данных и сетевых графиков в программе при п = 3, 5 в числовой форме показано в приложении.
Ниже приводятся пояснения к полученным оценкам для ПНПя. Количе п ство подмножеств из п элементов - это С п =2". Фиктивные операции не /= нужны для начальных операций (Сп = 1) и для операций, у которых в предшественниках единственный элемент (Сп = п). Итого всего подмножеств с фиктивными операциями: 2" - п - 1. Списки предшественников G(a,) проекта с п операциями (обозначим Gn(a$) получаем на основе списков G„.\(a,) проекта с п - 1 операциями добавлением «-ой операции отдельно и к каждому Gn.\(al)- В результате такого построения общее число фиктивных работ будет 2(2" - п - 1). Анализируя проекты ПНПл, можно проверить это общее количество. Имеем:
Анализ решений задач из класса п - 1ЭНП« показывает, что можно добавить всего вп - 12 фиктивных операций вместо возможных п - п связей.
Исходные данные и результаты, полученные с помощью созданной программы, в числовой форме для всех рассмотренных задач и задач с другими п представлены в приложении диссертации. Также с помощью программы сформированы и другие сетевые графики с минимальным количеством фиктивных операций. Например, на основе списков предшественников для каждой операции сетевого проекта из примера Mario Vanhoucke [156], получен аналогичный сетевой график с 7 фиктивными операциями. В статье [156] сетевой график создан специальной программой случайным образом. Хочется отметить минимальность фиктивных операций в нём.
Минимальность количества фиктивных работ сетевых графиков «работы - дуги», созданных с помощью нового метода и алгоритмов строго не доказана, но пока и не удаётся подобрать проект, для которого бы эта минимальность не выполнялась. Для проектов со сложными взаимосвязями важен порядок сравнения списков предшественников.
Накопительный итерационный метод для определения лимита сечения резервной подсети
После того, как сечение резервной подсети определено, следует найти условно-минимальную величину изменения длительности Л (лимит сечения подсети), при которой часть операций подсети становятся критическими. Лимит сечения подсети определяется очень просто в двух случаях: а) при положительном пересечении подкритического пути лимит Л равен минимальному резерву дуг сечения; б) при отрицательном пересечении всех дуг сечения лимит равен бесконечности.
В остальных случаях трудно предложить общее правило. Рассмотрим, например, резервную подсеть с одним некритическим событием 3 и четырьмя операциями (1, 3); (2, 3); (3, 4); (3, 5); см. рис. 3.1. Буквой S помечены начало и конец сечения, которые определяются критическим сечением. Возле дуг проставлены полные резервы. Левый класс концевых вершин: {1+, 4 }, правый класс: {2+, 5"}. Верхние знаки + и -указывают, соответственно, на входящие и выходящие дуги. Минимальные концевые вершины в левом классе 4 , в правом
Ясно, что подкритический путь пере секается сечением в отрицательном на правлении, но в любом случае имеются дуги, пересекаемые сечением положительно. На рис. 3.1 пунктиром показано сечение подсети, соответствующее свободным резервам.
Наименьший полный резерв положительно пересекаемой операции в данном случае совпадает с резервом операции (1, 3) и равен 11. Однако лимит операции больше: Л = 13. Нетрудно показать, что для сети типа рис. 3.1 с отрицательным пересечением подкритического пути лимит равен сумме резервов операций, не лежащих на подкритическом пути, за вычетом минимального резерва, то есть Л = (11 +5)-3.
Итак, в общем случае лимит подсети не совпадает ни с одним полным резервом операции. Для определения Л можно использовать накопительный итерационный метод, начиная с нуля. На каждой итерации в качестве добавки А, к Л выбирается наименьший резерв положительно пересекаемых операций, и резервы пересчитываются заново. Итерации заканчиваются, когда в подсети появится хотя бы одна операция с нулевым резервом.
Алгоритм выравнивания минимальных резервов Для пересчёта резервов можно использовать метод критического пути, однако, более эффективен (требует меньшего количества операций) алгоритм выравнивания минимальных резервов, основанный на равенстве резерва собы тия Rk наименьшим резервам как входящего (Rik), так и выходящего (Rkj) пучка операций: min R.. = R. = min R,. і к k j К}
Для этого поочерёдно пересекаем работы сечения, уменьшая или увеличивая на величину А, их резерв в зависимости от знака пересечения и выравнивая минимальные резервы после каждого пересечения по следующему правилу. Если с одной стороны от некоторого события минимальный резерв пучка изменился, то на такую же величину следует изменить резервы всех операций противоположного пучка, продолжая рекурсивно эту процедуру для всех инцидентных событий до полного выравнивания.
Поясним алгоритм пересчёта резервов на примере пучка последующих работ. О) Рис. 3.2. Прямое пересечение На рис. 3.2 показано раннее положение работ, предшествующих событию (/ ), а также позднее положение события (/ ) (вертикальный отрезок) и последующих работ (горизонтальные отрезки). Видно, что резерв события Rj совпадает с минимальными резервами пучков работ. Пусть у одной из работ (i, j), предшествующих событию , резерв Ry уменьшился на Дь Тогда (рис. 3.2) изменение Д2 резервов работ последующего пучка произойдёт только при Ry - Ді R/. А2 = max {О, Л, + Rj - RtJ}. На рис. 3.3 наряду с резервом Ry одной из предшествующих работ и минимальным резервом Rj показан резерв Rj второй работы из пучка предшествующих работ, упорядоченных по неубыванию резерва. Пусть резерв работы (ij) увеличился на Аь Резервы последующих работ изменятся на Д2.
Пример по накопительному итерационному методу Накопительный итерационный алгоритм состоит из следующих этапов: 1 1. Л = 0. 2. Начало очередной итерации. Среди положительно пересекаемых сечением операций подсети ищется минимальный резерв - это X. Если Л = 0 (есть хотя бы одна операция с 0 резервом), то END, иначе Л = Л + X. 3. Пересекаем очередную дугу сечения. Если все дуги сечения пересечены, то переход к 2. 4. У пересечённой дуги изменяем резерв: у положительно пересекаемой операции резерв уменьшаем на X, у отрицательно пересекаемой - увеличиваем на Я. 5. Пересчёт резервов: если с одной стороны от некоторого события минимальный резерв пучка изменился, то на такую же величину следует изменить резервы всех операций противоположного пучка.
Ниже подробно рассмотрен пример определения лимита Л сечения резервной подсети, приведённой на рис. 3.1, накопительным итерационным методом с алгоритмом выравнивания минимальных резервов. Изменения резервов представлены на рис. 3.4. Нумерация в примере соответствует нумерации этапов в накопительном итерационном алгоритме. 3 5 1. Л = 0. 2. Начало итерации. А, = 11 — минимальный резерв положительно пересекаемой операции (1,3) равен 11. Л = 0 + 11 = 11. 3. Пересекаем дугу (1,3). 4. У положительно пересекаемой операции уменьшаем резерв на 11. 5. Пересчёт резервов.
Алгоритм объединения нескольких последовательных операций
В свою очередь [т/ьТ/г] сегменты значений параметров сокращения составляющих квазидуг, і є /.
До тех пор, пока среди составляющих обобщённых дуг не появятся антипараллельные дуги, параметр сокращения не ограничен снизу: 8i = -оо. При наличии антипараллельных дуг параметр є ограничен, и несколько первых значений последовательности угловых коэффициентов ломаной а = с (є) могут быть отрицательными.
Рассмотрим пример сети - рис. 4.16.
В скобках записаны удельные затраты на сокращение операции на единицу времени, справа от скобки - предельная величина сокращения операции. С другой стороны дуг проставлены начальные значения параметра є: нулевые значения у критических операций, отрицательные значения у операций с положительным полным резервом R = -е. На первом шаге удаляем резервные дуги. Критические дуги (на рис. 4.16 - жирные линии) после 11І1Д элементарно определяют минимальное сечение, отсекающее вершину 1.
Угловой коэффициент первого звена ломаной - UK = 2, а наибольшее сокращение сечения - А = 3. Дуги (1, 2) и (1, 3) получили предельное сокращение и коллапсируют, поскольку они инцидентны полюсу. Замечательно, что вслед ствие слияния трёх вершин 1, 2 и 3 коллапсирует также дуга (2, 3), хотя она и не сокращалась!
На втором шаге (рис. 4.17) сеть критических работ упростилась, и минимальное сечение, очевидно, пересечёт дугу (4, 6), UK = 3. Величина А = 2 определяется уменьшением резервов до нуля.
Сеть имеет одиннадцать сечений, минимальное показано на рис. 4.18, UK =11. Проект сокращается на А = 2. На эту же величину сокращаются все дуги минимального сечения: (4, 6) + (4, 7) + (5, 6) + (5, 7). Дуги (4, 6) и (5, 7) имеют предельное сокращение и не могут быть пересечены в отрицательном направлении, поскольку имеется всего два сечения: (2, 5) - (5, 7) + (7, 8) + (4, 6) и (3, 4) - (4, 6) + (6, 8) + (5, 7) со знаком минус для этих дуг, но каждое из них содержит другую дугу со знаком плюс. При стягивании дуг (4, 6) и (5, 7) образуются две кратных антипараллельных дуги (4, 7) и (5, 6). Начало объединённой квазидуги будет в слитой вершине {4, 6}, поскольку вершина с наименьшим номером 4 входит именно в слияние {4, 6}.
Возникновение антипараллельной квазидуги Будем обозначать на рисунке квазидугу, составленную из антипараллельных дуг, не стрелкой, а ромбиком на конце. У такой квазидуги приводятся все перемежающиеся последовательности границ и угловых коэффициентов (смотри рис. 4.19), в отличие от квазидуг с параллельными дугами, у которых границы первого полубесконечного интервала и нулевой коэффициент опущены.
Минимальному сечению рисунка 4.19 соответствует UK= 16, А = 1. Квазидуги ({1, 2, 3}; {4, 6}), а также ({5, 7};8) коллапсируют, поскольку сокращаются до нижнего предела и инцидентны полюсам. В результате образуется последняя квазидуга, инцидентная обоим полюсам, (см. рис. 4.20).
Неувеличиваемая дуга имеет все границы абсцисс звеньев ломаной неотрицательные, а левую границу - нулевую. Набор параметров UK, А ломаной для последней квазидуги завершает процесс построения оптимальной ломаной всего проекта.
Следует ещё раз отметить, что в методе комплексной оптимизации каждой работе проекта может соответствовать выпуклая ломаная зависимость стоимости от времени.
