/
Автор: Зайденман И.А. Маргулис А.Я.
Теги: математика математический анализ математика для детей издательство знание
Год: 1967
Текст
q-Ql математика
СЕРИЯ |~
XIX рй=
1967 CS
науке
технике
15
ИА- ЗАИДЕ НМ АН
А- Я* МАРГУЛИС
МАТЕМАТИКА
В СЕТЕВОМ
ПЛАНИРО-
ВАНИИ
И. А. ЗАЙДЕНМАН,
АЯ. МАРГУЛИС
МАТЕМАТИКА
В СЕТЕВОМ
ПЛАНИРОВАНИИ
Издательство «Знание»
Москва 1967
Брошюра рассказывает о системе сетевого планирования
и управления как объекте приложения различных, областей
математического знания. В доступной форме изложены основ-
ные идеи сетевого планирования, сводящиеся к некоторым
экстремальным задачам теории графов, освещены вопросы
вероятностного подхода к сетевым моделям и в популярной
форме рассказано о нескольких, в том числе и о нерешенных
еще задачах, связанных с вопросами оптимизации сетевых пла-
нов с точки зрения максимальной экономии ресурсов, времени
и затрат.
Брошюра рассчитана на широкий круг читателей, интере-
сующихся проблемами современной математики и вопросами
ее практического применения,
СОДЕРЖАНИЕ
Предисловие . * . ...............у й ♦ 3
Введение. Основные понятия Сетевых моделей , 4
Г лава 1. Сетевые графики как объект математической
теории графов.................................12
Глава 2. Сетевые графики как объект теории вероят-
ностей .......................................27
Глава 3. Сетевые графики как область приложения
методов линейного программирования .... 34
Глава 4. Сетевые графики как объект теории нелиней*
•ного программирования........................45
Заключение . . г .............................43
МАТЕМАТИКА В СЕТЕВОМ ПЛАНИРОВАНИИ
2—2—4___________
&3 № 24 и. 15.1967
Редактор В. Ю. Иваницкий
Худож. редактор Е. Е. Соколов
Техн, редактор М. Т. Перегудова
Корректор Г. И. Трибунская
Обложка Б. В. Макарова
Д01971 Сдано в набор 17,111—1967 г. Подписано к печати
9.III—1967 г. Формат бум. 60 X 901 /16. Бумага типографская
№ 3. Бум. л. 1,5. Печ. л. 3,0 Уч.-изд. л. 3,17
Тираж 56 000 экз. Заказ 1013 Цена 9 коп,
Издательство «Знание». Москва, Центр. Новая пл., д. 3/4.
Типография изд-ва «Знание», Москва, Центр, Новая пл., ДчЗ/4,
ПРЕДИСЛОВИЕ
Цель настоящей брошюры — познакомить читателя с не-
которыми математическими задачами, связанными с новым
методом планирования и управления, получившем в нашей
стране название Системы Сетевого Планирования и Управле-
ния — сокращенно «Системы СПУ»*
Система СПУ — одна из новых форм научного метода планирования
сложных работ, в осуществлении которых может принимать участие боль-
шое число исполнителей (отдельных лиц и организаций). Эта система по-
зволяет не только оценить составленный план и скорректировать его, обес-
печив сокращение сроков выполнения работы и снижение материальных
затрат, но и дает возможность в процессе выполнения плана находить
«узкие» участки всего комплекса работ и вносить поправки в организа-
цию работы в целом.
Нередко при ознакомлении с системой СПУ создается впечатление, что
ввиду исключительной простоты основных идей, на которых базируется
эта система, применение математики в ней ограничивается элементарными
операциями и что система СПУ не требует знаний, выходящих за пределы
программы начальной школы. При этом ссылаются на то, что больший*
ство рекомендуемых расчетов и формул ограничивается использованием
четырех действий арифметики. Отчасти это так. Для применения метода
СПУ, по крайней мере в его простейшей форме, к улучшению организации
работ на том или ином участке достаточно математических знаний в объ<
еме элементарной арифметики. Но и сложнейшие математические задачи,
подлежащие решению на электронных цифровых вычислительных машинах,
искусственно приводятся каждый раз именно к такому виду, который тре-
бует только все тех же четырех действий: сложения, вычитания, умноже-
ния и деления. Стало быть, сам факт, что некоторая задача может быть
решена простыми действиями (даже если таких действий потребуется не-
сколько сот тысяч!), теперь никого не должен удивить — в век вычисли-
тельных машин это стало привычным.
Полезное участие математика в решении подобных задач состоит имен-
но в том, чтобы наиболее экономным способом свести их решение к вы-
полнению отдельных элементарных операций. Однако в системе сетевого
планирования дело обстоит гораздо сложнее.
В области применения математических методов к решению экономичен
ских задач сложилось своеобразное положение. Необходимость учета чрез*
мерного количества исходных данных и, с другой стороны, невозможность
рассмотреть в нужные сроки все возможные варианты требуют нового
подхода к решению таких задач. Этот новый подход состоит в отыскании
таких упорядоченных последовательностей элементарных вычислительных
операций, которые вели бы кратчайшим путем к поставленной цели без
необходимости' «перебора» всех возможных вариантов.
3
Практика преподносит математикам все новые и новые сюрпризы/Вся*
кая математическая модель реальной задачи по необходимости что-то уп-
рощает. Учет ранее опущенных отдельных условий, т. е. большее прибли-
жение к реальности, приводит к новой, более трудной задаче, решение ко-
торой может Привести к значительной экономии средств или к сокраще-
нию сроков ввода в действие различных объектов (от отдельных станков
до крупных сооружеий).
Нахождение простых приемов решения такого рода слож-
ных задач составляет содержание ряда новых направлений а
развитии математики. Наша брошюра начинается с рассказа
об основных идеях метода СПУ, а затем уже читатель знако-
мится с системой СПУ, как объектом приложения различные
областей математического знания.
ВВЕДЕНИЕ. ОСНОВНЫЕ ПОНЯТИЯ СЕТЕВЫХ
МОДЕЛЕЙ
Вопросы составления сетевых графиков и их анализа по-
дробно разобраны во многих недавно изданных книгах. В ка-
честве примера можно привести «Азбуку сетевых планов*
И. Сыроежина [9], «Системы сетевого планирования и управ-
ления» [8] и др. В них детально разобраны принципы построе-
ния и анализа сетевых графиков. Исходя из этого, мы здесь
ограничимся только кратким изложением самой сути сетевого
планирования. В последующих главах мы рассмотрим те ма-
тематические методы, которые используются в сетевом пла-
нировании.
Предположим, что необходимо выполнить некоторую работу — строи-
тельство, создание образцов новой техники, реконструкцию или ремонт
/предприятия, освоение выпуска новой продукции и т. п., или усовершен-
ствовать какой-либо уже существующий процесс производства. Предполо-
жим далее, что в этой общей, «большой» работе должны принять участие
многие исполнители — отдельные сотрудники, группы, коллективы или це-
лые предприятия, так что отдельные задания будут поручены различным
людям, группам, бригадам, лабораториям, цехам, мастерским, заводам^
комбинатам и т. д. Как наилучшим образом распределить , исполнителей,
чтобы, скажем, выполнить всю «большую» работу в наиболее короткий
срок? Или как распределить ресурсы — рабочую силу, материалы, финал*
,сы, оборудование, чтобы вся «большая» работа обошдась наиболее деше-
во? Что надо делать, если вдруг в процессе выполнения работ окажется,
что отдельные исполнители не укладываются в сроки, которые были на-
мечены планом? Откуда перебросить подкрепления — средства, оборудо-
вание, людей? Как узнать в любой момент, что сейчас самое главное, где
самый ответственный участок, от работы которого зависит успех всего де-
ла? И что понимать под словами «самый ответственный участок»? Почти
каждый исполнитель считает (и это естественно!), что порученный ему
^участок и есть как раз самый главный. И каждый (не из корыстных целей*
а из любви к своему делу!) просит помочь в первую очередь именно ему.
!Как часто решения руководителей, отвечающих за большой комплекс ра-
бот, оказываются следствием не анализа всей ситуации в целом, а особой
«настойчивости» отдельных подчиненных, умеющих «выбить» вне очереди
нужные им материалы или оборудование],-.
' 'Прежде всего .надо знать взаимосвязь всех отдельных
звеньев «большой» работы, т. е. знать, какие другие участки
зависят от каждого данного участка, и знать, от каких участ'
ков зависит каждый данный участок. Кроме того, надо знать,
как отразятся возможные задержки любого звена на работе
других звеньев всего коллектива. Если таких звеньев много,
то даже обзор Состояния дел и учет зависимостей между ра-
ботой отдельных исполнителей (звеньев) становится нелегкой
проблемой. Недаром так часто говорят об «искусстве» руко-
водства, о «таланте» руководителя, но сравнительно редко
можно услышать слова «наука руководства». А такая наука
В условиях бурного технического прогресса настоятельно не-
обходима.
Первая задача — установление взаимосвязи всех звеньев
«большой» работы — решается, в Первом приближении, до-
вольно просто. Оказывается, наилучшим способом это может
быть сделано в графической форме. Для этого достаточно ус-
ловиться изображать кружками, квадратами или какими-либо
другими нехитрыми фигурами важнейшие моменты всего
комплекса работ. Такими важнейшими моментами следует из-
брать моменты начала или моменты окончания каких-либо
отдельных частных процедур, работ, организационных меро-
приятий, поставок, составления документации, погрузок, раз-
грузок, изготовления отдельных деталей, узлов, механизмов,
машин, проведения каких-либо операций, испытаний, обра-
боток и т. д. и т. п. Что именно выбрать — это дело руководи-
теля. Подобные моменты именуются в системе сетевого пла-
нирования «событиями». Главной отличительной чертой собы-
тий служит то, что само по себе событие не требует никаких
затрат, никаких ресурсов — ни времени, ни рабочей силы, ни
оборудования, ни материалов, ни денег. Разумеется, для того
чтобы произошло некоторое событие, являющееся, скажем,
моментом окончания сборки некоторого агрегата, нужно вы*
полнить ряд работ и затратить немало ресурсов. Но когда
все это сделано, само событие «окончание сборки агрегата»
произойдет, так сказать, автоматически, т. е. коль скоро агре-
гат уже собран, «окончание его сборки» уже произошло.
Для того чтобы могло произойти некоторое событие (в
смысле данного выше определения), обязательно должны
произойти некоторые другие события. Например, для того
чтобы агрегат был собран, необходимо, чтобы было законче-
но изготовление тех узлов, из которых этот агрегат должен,
состоять. Таким образом, событию — «окончание сборки аг-
регата»— должны предшествовать такие события, как окон-
чание работ по изготовлению тех узлов, которые мы поручили
отдельным исполнителям. Исключение составляет только одно
событие, всегда выделяемое при составлении сетевого графи-
ка, это — «начало работ данного комплекса» —самое первое
£
событие, определяющее момент, начала работ, входящих г в
данную «большую работу». Если какие-либо два события об-
ладают тем свойством, что одно из них (скажем, первое) обя-
зательно должно предшествовать другому (второму), причем
между этими двумя событиями мы не включили больше нм*
каких промежуточных событий, то первое событие называется
предшествующим по отношению ко второму, а второе назы-
вается последующим по отношению к первому. Этот факт на
нашей графической схеме изображается таким образом: пред-
шествующее событие соединяют стрелкой с последующим со*
'бытием, причем стрелка эта направлена всегда от предшест*
вуюшего события к последующему (см. рис. 1,а)Л Стрелка^
.соединяющая два события, называется работой.
Рис. А
Если некоторое событие может наступить только после на*
-ступления нескольких предшествующих событий, то на нашем
графике в кружок, соответствующий этому событию, будет
входить столько стрелок, сколько предшествующих событий
имеет данное событие. На рис. 1,6 событие, обозначенное
кружком с цифрой 4, имеет три предшествующих ему события.
Если, наоборот, данное событие предшествует нескольким;
событиям, то из кружка, соответствующего данному событию,
выходит ровно столько стрелок, сколько последующих собы-
тий имеет данное событие. На рис. 1,я событие, обозначенное
кружком с цифрой 1, имеет три последующих события. Един-
ственное условие (очень важное!), налагаемое на количество
стрелок—«работ», состоит в том, что любые два события мо-
ту т быть соединены не более чем одной стрелкой.
Напомним, что стрелки на схеме называются работами.
Поясним происхождение этого названия. Рассмотрим рис. 1,а.
Пусть событие 1 есть событие «Начата сборка агрегата»^ &
6
событие 2 — «Закончена сборка агрегатам. Стрелка, соеди-
няющая первое событий со вторым, может быть истолкована,
как графическое изображение самого процесса сборки агре-
гата. Таким образом, если стрелка (работа) соединяет два
события, то первое событие— как бы оно у нас на схеме ни
Называлось — имеет также смысл начала данной работы, а
второе — конца данной работы. Если при этом стрелка изо-
бражает действительную работу, то эта работа требует за-
траты ресурсов — времени, сил, средств, оборудования, мате-
риалов, энергии. Иногда может требоваться только время, на-
пример, если первое событие есть «окончание отливки метал-
ла в форму», а второе — «начало дальнейшей его обработки».
В этом случае стрелка, соединяющая эти два события, изо-
бражает процесс остывания металла в форме. Единственным
ресурсом, который при этом расходуется, является время
(кстати сказать, самый драгоценный ресурс!). Такие работы,
на «выполнение» которых расходуется только время и больше
ничего, называются ожиданиями,
Но возможен еще и такой случай. Мы назвали событиями
моменты начала и окончания некоторых работ. Но может слу-
читься, что после окончания некоторой работы (например,
сборки узла) можно непосредственно приступить к началу не-
которой другой работы (например, к сборке агрегата, все
остальные узлы которого уже собраны), хотя на нашей схеме
окончание первой работы (сборки узла) и начало второй ра-
боты (сборки агрегата) отмечены разными событиями. Про-
изойти это может сплошь и рядом потому, что для второго со-
бытия на схеме имеется еше несколько предшествующих со-
бытий, каждое из которых необходимо должно произойти до
наступления начала сборки агрегата. Те из предшествующих
событий, после наступления которых последующее событие
может произойти без какой бы то ни было затраты ресурсов,
в том числе и без затраты времени, на схеме соединяют о
последующим событием не сплошными, а пунктирными стрел-
ками и эти стрелки называют фиктивными работами. На
рис. 1,г подобная фиктивная работа соединяет события 2 и 3.
Положим, что на этом рисунке изображен график сборки
некоторого агрегата, состоящего из двух узлов — узла № 2 и
узла № 4. Пусть событие 1 есть начало всей работы, собы-
тие 2 — окончание сборки узла № 2, событие 4 — окончание
сборки узла № 4, а событие 3 — начало сборки агрегата. До-
пустим также, что сборка узла № 2 производилась в том же
цехе, где должна вестись сборка агрегата, а узел № 4 изго-
тавливался на другом заводе или даже в другом городе. Тогда
работа, соединяющая события 4 и 3, есть «Доставка узла №4
в сборочный цех». Работа же, соединяющая события 2 и 5.
только показывает, что к сборке агрегата нельзя приступить,
пока не будет готов узел № 2*
Z
Таким образом, фиктицрые работы это стрелки, указываю^
щие логическую связь (и только ее) между событиями — по-»
следующее событие не может произойти раньше предшест-
вующего,— тогда как остальные работы, в том числе ожида-
ния, указывают на то, что между наступлением предшествую-
щих и последующих событий необходимо должно пройти не-
которое время. Это время, которое необходимо затратить на
выполнение каждой работы, называется продолжительностью
работы. Согласно этому определению продолжительность
каждой фиктивной работы равна нулю.
Наименования предшествующий и последующий относятся
не только к событиям, ио и к работам. А именно, если в неко-
торое событие «входит» несколько работ (скажем, р работ) и
выходит несколько работ (скажем, q работ), то каждая из р
входящих работ считается предшествующей каждой из q вы-
ходящих работ, и, наоборот, каждая из q выходящих работ
считается последующей для каждой из р входящих работ.
Из определения, как говорят математики, «отношения
предшествующий — последующий» вытекают три важнейших
свойства сетевых графиков, которые мы назовем соответст-
венно свойствами А, В и С. Эти свойства следующие.
Свойство А: ни одно событие не может произойти до тех
пор, пока не будут закончены все входящие в него работы.
Свойство В: ни одна работа, выходящая из данного собы-
тия, не может начаться до тех пор, пока не произойдет данное
событие.
Из свойств А и В вытекает следующее свойство С: ни одна
последующая работа не может начаться раньше, чем будут
закончены все предшествующие ей работы.
Итак, если нам удалось найти моменты, «достойные» име-
новаться событиями, соединить их стрелками-работами, ука-
зывающими отношение «предшествующий — последующий» и
установить, хотя бы ориентировочно, чему равна ожидаемая
продолжительность каждой нефиктивной работы, сетевой гра-
фик готов.
Можно идти другим путем — начать с перечня всех работ,
их начала и окончания назвать событиями, соединить их стрел-
ками в соответствии с отношением «предшествующий — после-
дующий» и добавить два события — «начало всех работ» и
«окончание «большой» работы». Мы придем к тому же резуль-
тату, хотя, возможно, число событий будет больше, чем в пер-
вом случае, и нам придется для удобства работы упростить
.сетевой график, удалив из него, так сказать, лишние события.
!Подобное укрупнение графика должно проводиться по опре-
делённым правилам, и мы об этом поговорим несколько поз-
же. JB общем, оба способа равноправны — можно начинать
как с?выделения событий, так и с составления полного переч-
ня работ. Важно при этом отметить, что сам процесс состав^
Ления сетевого графика приводит к необходимости учета всех
звеньев «большой» работы. Он как бы гарантирует, что ничто
не будет упущено. В этом заключается одно из важных до-
стоинств сетевого планирования.
Достигается это обычно тем, что ответственным исполните-
лям каждой работы поручают составить свой «частичный» се-
тевой график, изображающий порученный им участок работы.
На этом частичном графике может быть не одно, а несколько
начальных событий — это окончание работ, выполняемых
смежниками, т. е. тех работ, без которых данный исполнитель
не может выполнить порученное ему дело. Кроме того, этот
частичный график может содержать несколько конечных со-
бытий— окончание тех работ, которые данный исполнитель
должен сделать для других смежников. Полученные таким
образом частичные сетевые графики подлежат так называе-
мой «сшивке» — конечные события отдельных частичных гра-
фиков отождествляются с исходными событиями других ча-
стичных графиков, например, конечное событие «закончено
изготовление детали № 12» отождествляется с начальным со-
бытием «получена от исполнителя деталь № 12».
Исполнителям поручается также дать оценку продолжи-
тельности каждой работы, которую они сочли необходимым
включить в свой частичный график. Обычно требуется дать,
по крайней мере, две оценки этой продолжительности: «опти-
мистическую оценку» — сколько времени продлится данная
работа при самых благоприятных обстоятельствах и «песси-
мистическую оценку» — сколько времени продлится данная
работа при самом неблагоприятном стечении обстоятельств.
В ряде случаев желательна еще одна «наиболее вероятная
оценка» — сколько времени продлится данная работа при су-
ществующих в данный момент обстоятельствах (при имею-
щихся в распоряжении исполнителей ресурсах — рабочей си-
ле, оборудовании, энергетике, материалах и т. п.). При выдаче
подобных оценок исполнители должны руководствоваться как
'действующими нормативами, так и собственным практическим
опытом.
Из полученных двух или трех оценок продолжительности
каждой работы рассчитывают так называемое «ожидаемое
время», т. е. статистически ожидаемую продолжительность
данной работы. Соответствующие формулы будут даны в
третьей главе.
«Сшитый» сетевой график должен удовлетворять двум тре-
бованиям. Первое требование состоит в том, что график дол-
жен содержать только одно начальное событие («начало
«большой» работы») и только одно конечное событие («окон-
чание «большой» работы»). Если эти условия не выполнены,
приходится добавить еще одно начальное событие и соединить
его стрелками с имевшимися несколькими начальными собы-
1013-2
9
тиями или добавить еще одно конечное событие, к которому
проводят стрелки от нескольких имевшихся конечных собы-
тий. Это исправление графика никаких трудностей не пред-
ставляет.
Второе требование к сетевом}^ графику не разрешает на-
личия так называемых\ ^циклов». Здесь требуются некоторые'
пояснения. Прежде всего введем очень важное понятие «путь».
Путем на сетевом графике называется последовательность
работ, конец каждой из которых совпадает с началом следую-
щей. События на сетевых графиках принято обозначить циф-
рами — каждому событию дается какой-либо условный номер
с таким расчетом, чтобы не было двух событий с одинаковыми
номерами. Работы принято обозначать парой цифр — номера*
ми событий, служащих соответственно началом (первая циф-
ра) и концом (вторая цифра) данной работы. Так, на рис. 1,а
имеются два события (/ и 2) и одна работа (/, 2). На
рис. 1,6 — три работы: (1,4), (2,4) и (3,4). На рис. 1,г рабо-
ты (1,4) и (4,3) образуют путь. Другой путь на этом же ри-
сунке образуют работа (1,2) и фиктивная работа (2,5).
Если последовательность работ образует замкнутый путь;
т. е. конец последней работы совпадает с началом первой ра-
боты, то такой путь называется циклом. Из свойства С ясно,
что ни одна из работ, входящих в такой цикл, никогда не мо-
жет начаться. Следовательно, сетевой график, содержащий
*хотя бы один цикл, никогда не сможет быть реализован, по-
скольку он, очевидно, содержит логическую ошибку. На боль-
шом и сложном графике, содержащем, скажем, сотни событий,
и полученном в результате «сшивки» десятков частичных гра-
фиков, сплошь и рядом может по ошибке возникнуть цикл.
О том, как такие ошибки обнаруживаются, будет рассказано
в следующей главе. На рис. 1,6 график содержит цикл, состоя-
щий из работ (2,4), (4,3) и (3,2). В соответствии с вышеска-
занным, график 1, д никогда не сможет быть реализован.
Итак, если график удовлетворяет двум вышеуказанным
требованиям и для каждой работы известна ее ожидаемая
продолжительность, сетевой график готов для анализа и ра-
боты.
Уже сам процесс составления сетевого графика, как утвер«
ждают специалисты и с чем соглашаются его «потребители»,
приносит большую пользу тем, что он заставляет еще раз хо-
рошенько учесть все потребности данной «большой» работы..
Как только график составлен, уже само его существование
дает возможность каждому исполнителю и руководителю всей
работы немедленно дать ответ на вопрос: от каких работ все-
го комплекса зависит, а от каких не зависит выполнение лю-
бой данной работы. Больше того, уже один взгляд на график
показывает, какие работы нужно делать сначала, какие —
позже, какие можно вести параллельно, а какие — нельзя, Тач
10
ким образом, сама по себе схема, состоящая из работ и собы-
тий, уже очень полезна. Но вспомним, что каждая работа
имеет еще некоторую числовую оценку — ожидаемую продол-
жительность ее выполнения. Наличие этой числовой оценки
позволяет осуществлять математический анализ сетевого гра-
фика. В результате такого анализа можно определить в пер-
вую очередь следующие параметры сетевого графика:
1. Наиболее раннее возможное время начала каждой ра-
боты, или наступления каждого события.
2. Наиболее позднее допустимое время окончания каждой
работы, или наступления каждого события, еще не вызываю-
щее задержки в установленном (плановом, директивном) сро-
ке выполнения всей «большой» работы.
3. Резервы времени каждой работы (и времени наступле-
ния каждого события) — на сколько единиц времени может
быть задержано выполнение данной работы без того, чтобы
задержать срок окончания «большой» работы (это так назы-
ваемый полный резерв времени), или даже без того, чтобы
'изменить сроки проведения остальных работ графика (это так
называемый свободный резерв времени).
4. Может быть найден так называемый критический
.лить — самый длинный путь, ведущий из начального события
графика в его конечное событие. При этом за длину любого
Шути принимается сумма продолжительностей всех работ, вхо-
дящих в этот путь. Критический путь, как самый длинный
путь, определяет наиболее ранний возможной срок окончания
'всей «большой» работы. Он обладает тем важнейшим свойст-
вом, что задержка в выполнении любой работы и наступле-
ния любого события, лежащих на этом пути, неизбежно вле-
чет за собой задержку ровно на такой же срок в наступлении
конечного события, т. е. в сроке окончания всей «большой»
работы, если только руководство работами не примет своевре-
менно мер — переброски ресурсов с работ, обладающих ре-
зервами времени, на работы, лежащие на критическом пути.
5. Могут быть найдены важнейшие в каждый данный мо-
мент работы — это те работы, у которых резервы времени ми-
нимальны. Они или уже находятся на критическом пути, или
грозят попасть на него в ближайшее время.
Кроме этих параметров, о которых очень подробно расска-
зано, например, в книге «Азбука сетевых планов», сетевые
графики позволяют решать много других задач, получать
оценки вероятности своевременного, досрочного или запозда-
лого наступления тех или иных событий, искать способы ус-
корения всей «большой» работы, удешевления ее, наиболее
экономного использования различных ресурсов и многие дру-
гие вопросы.
ЛГ
Глава I
СЕТЕВЫЕ ГРАФИКИ КАК ОБЪЕКТ МАТЕМАТИЧЕСКОЙ
ТЕОРИИ ГРАФОВ
Математическая теория графов развивалась совершенно
независимо от сетевого планирования. Когда были придуманы
сетевые графики, оказалось, что они представляют собой не
что иное, как один из объектов этой теории — так называемые
направленные графы, ряд вопросов теории которых был до*
статочно подробно разработан математиками. Как всегда про-
исходит в подобных случаях, произошло взаимное обогащение
обеих ветвей науки — сетевое планирование воспользовалось
готовыми результатами теории графов, а теория графов полу-
чила, так сказать, в подарок много новых задач, вытекавших
из ее нового применения.
Что же такое графы?
Графом называется совокупность конечного числа точек
(называемых вершинами графа) и попарно соединяющих не-
которые из этих вершин линий (называемых дугами или реб-
рами графа). На рис. 2 изображено несколько графов. Граф
Рис,
на рис. 2, а содержит шесть вершин и шесть дуг, причем две
дуги соединяют одни и те же две вершины (такие дуги назы-‘
ваются кратными), а одна дуга (правая верхняя) начинается
и кончается в одной и той же вершине. Такая дуга называется
петлей. Граф на рис. 2,6 не содержит ни одной дуги, он со-
12
стоит из изолированных шести вершин. Граф, состоящий
только из изолированных вершин, называется нуль-графом.
В отличие от него, граф на рис. 2, в содержит шесть вершин,
каждая пара которых соединена в точности одной дугой. Это
так называемый полный граф. Он не содержит ни кратных
дуг, ни петель. Количество дуг полного графа равно количе-
ству различных пар его вершин. Это количество, в свою оче-
редь, равно числу сочетаний из п элементов по два, где п —.
. п(п — 1)
число вершин графа, т. е. величине —4 Если совокуп-
ность (множество) вершин некоторого графа можно разде-
лить на две группы (два подмножества) таким образом, что
не существует ни одной дуги, соединяющей вершины разных
подмножеств, такой граф называется несвязным (например,
графы на рис. 2, а и б). Если этого сделать нельзя — такой
граф называется связным (рис. 2,в и г).
Если на каждой дуге задано направление, указанное стрел-
кой, то граф называется ориентированным. При этом если
каждая пара вершин графа соединена парой противоположно
ориентированных дуг — такой граф называется симметриче-
ским графом. Симметрические графы находят применение в
транспортных задачах о перевозках, поскольку с их помощью
удобно изображать сеть дорог с двусторонним движением,
соединяющих конечное число пунктов (вершин графа).
Если граф ориентирован, не содержит кратных дуг и яв-
ляется связным, такой граф называется асимметрическим.
Последовательность ориентированных дуг, начало каждой
последующей из которых совпадает с концом предыдущей,
называется путем на графе. Вершина асимметрического гра-
фа, в которую не входит ни одна дуга, называется истоком,
а вершина, из которой не выходит ни одна дуга, называется
стоком. Замкнутый путь на ориентированном графе назы-
вается циклом.
Если асимметрический граф не содержит циклов, имеет
только один исток и только один сток, такой граф называется
направленным графом. Такой граф изображен на рис. 2,(3. На
нем все пути, выходящие из его единственного истока — вер-
шины № 1, заканчиваются в его единственном стоке — верши-
не № 7, и кроме того, в отличие от графа, изображенного на
рис. 2, г, в нем нет ни одного цикла.
Из сказанного во введении относительно условий, которым
должен удовлетворять сетевой график, ясно, что сетевой гра-
фик с точки зрения классификации графов, есть не что иное,
как ориентированный связный асимметрический граф с одним
истоком, одним стоком и без циклов, т. е., согласно определе-
нию, сетевой график есть направленный граф. При этом вер-
шинами графа служат события сетевого графика, а дугами —
работы сетевого графикаА
13.
Вершины графа, т. е. события сетевого графика, принято
нумеровать. Будем обозначать номера вершин строчными ла-
тинскими буквами i, j, п. При этом число (п +1) будет у
нас всегда обозначать общее количество вершин графа, т. е.
количество событий сетевого графика. Если дуга соединяет
вершины / и j и направлена от вершины I к вершине j, такая
дуга будет обозначаться символом (i, j), который мы уже
применяли выше.
Введем теперь понятие изоморфизма. Два графа считают-
ся изоморфными, если вершины каждого из них можно зану-
меровать таким образом, чтобы каждой вершине и каждой
дуге одного графа соответствовала бы в точности одна верши-
на с тем же номером на другом графе и в точности одна дуга
с тем же обозначением на другом графе, и наоборот. Напри-
мер, граф на рис. 2,д изоморфен графу на рис. 2, е. Иными
словами, с точки зрения теории графов это один и тот же
граф, только по-разному изображенный. Таким образом, ни
взаимное расположение вершин на чертеже, ни форма линий,
изображающих дуги, не имеют никакого значения. Важно
только количество вершин и дуг и порядок, в котором они со-
единены, разумеется, с учетом ориентации дуг. То же самое
относится и к сетевым графикам. Один и тот же сетевой гра-
фик может иметь совершенно различный внешний вид при
одинаковой внутренней структуре — той структуре, которая
обеспечивает отражение логических взаимосвязей между со-
бытиями, выражаемых отношением «предшествующий — по-
следующий».
Основная характеристика работы — ее ожидаемая продол-
жительность— в теории графов называется длиной дуги. От-
сюда делается понятным выражение «длина пути» — это сум-
ма длин всех дуг, образующих данный путь. Длину дуги (i, j)
мы будем обозначать символом Если некоторый путь D
содержит дугу (i, j), этот факт мы будем обозначать симво-
лом (i, /)€ L- Тогда длина пути L равна
/ = s tn, (i-о);
(б /) С А
где суммирование распространено на все дуги, входящие в
этот путь. (Здесь и в дальнейшем для обозначения формул ис-
пользования двойная нумерация: первая цифра означает но-
мер главы, вторая — номер формулы).
Для сокращения всех дальнейших записей мы введем еще
несколько обозначений. Прежде всего условимся изображать
о'ношение «предшествующий — последующий» символом сд
'для событий и аналогичным символом для работ, т. е. выра-
жение (it, /1)с (»2, р) означает, что работа (Д />) предшествует
работе (Д /2). Аналогично, запись i U' будет означать, что со-
бытие i предшествует событию д то же означает запись /эй
И
Далее, если событие tz не является предшествующим по отно-
шению к событию Ь, но существует конечное число таких со-
бытий a, ii, b, ..., ik> 6, что событие а предшествует событию ii,
далее леи т. д. и наконец ikczb} т.е. если на графе сущест-
вует путь, ведущий из события а в событие.&, в этом случае
мы будем писать а<Ь. Это выражение читается так: «есть
путь из а в &». Отношение a<z.b, как видно, является частным
случаем отношения и <6. То же самое будем записывать и
для работ (дуг графа). Таким образом, запись (щ /i)< (й, р),
означает, что существует путь, в котором работа (и, /1) прохо-
дит раньше, чем работа (Д /2)г
В дальнейшем в этой главе мы больше не будем пользо-
ваться словами «вершина» и «дуга», заменяя их изоморфны-
ми им понятиями «событие» и «работа».
Итак, сетевой график — направленный граф, состоящий из
событий и работ, характеризуемых величинами tn , построен.
Приступим к его исследованию.
В дальнейшем для наглядности мы будем решать все за-
дачи применительно к определенному, конкретному сетевому
графику. Этот график изображен на рис. 3, а. Он содержит
11 событий и. 18 работ. Нетрудно убедиться, что на нем имеет-
ся только один исток — событие 1 и один сток —событие 11.
Так как график сравнительно невелик (реальные сетевые гра-
фики нередко содержат сотни событий), простым его про-
смотром можно проверить, что он не содержит циклов. Таким
образом, график на рис. 3, а есть направленный граф. Рас-
смотрим различные общие задачи, решаемые для графиков
произвольной сложности, на этом простом примере.
Над каждой работой изображено неотрицательное число.
Это — продолжительность данной работы. Над фиктивными
работами — таких на графике две, работа (3, 9) и работа (7Л
б)—естественно, стоит цифра нуль.
Для решения многих задач полезно прежде всего изменить
нумерацию событий таким образом, чтобы ив соотношения
/</ следовало неравенство i < /, т. е. чтобы любой путь шел
только через события с возрастающими номерами. Такую ну-
мерацию мы назовем правильной. Мы сейчас покажем, что
если граф направленный, то всегда можно ввести правильную
нумерацию.
Единственный исток графика — начальное событие № 1’
не содержит на графе ни одной входящей в него работы. При-
пишем этому событию новый номер № 0. Вычеркнем все рабо-
ты, выходящие из 0. Просмотрим все события, в которых окан-
чиваются эти вычеркнутые работы (это события 2, 5 и 7), и
найдем среди них события, которые не имеют теперь входя-
щих в них работ (за исключением уже вычеркнутых). Таких
событий два—2 и 7. Эти события назовем событиями первого
ранга и обозначим (вообще, в произвольном порядке^ следую-
515
Рис. 3.
16
щими двумя числами,натурального ряда %— I и 2. На этом за-
кончен первый шаг нашего алгоритма.
Переходим ко второму шагу. Вычеркиваем все работы, вы*
ходящие из событий первого ранга. На рис. 3,а такими рабо-
тами являются работы (2,4), (2,3), (7,5), (7,6) й (7,8). Пос-
ле этого найдем, что входящих работ, не имеют события 4 и 5.
Это — события второго ранга, которые мы должны занумеро-
вать следующими двумя числами 3 и 4.
Перейдем теперь к так называемому общему шагу. Пусть
уже проведен (k—1) шаг и определены события (k—1)-го
ранга. Тогда, вычеркивая все работы, выходящие из событий
'{k—1)-го ранга, и просматривая события, в которых эти ра-
.боты заканчиваются, выбираем события, не имеющие ни одной
входящей в них работы (за исключением уже вычеркнутый
работ). Эти события называем событиями й-го ранга и нуме-
руем последовательными числами натурального ряда, начи:
ная с наименьшего, еще не использованного числа при преды-
дущей нумерации на (k— 1)-ом шаге нашего алгоритма.
Сетевой график содержит конечное число событий. Поэто-
му если после каждого шага нашегр алгоритма найдется хотя
;бы одно событие соответствующего ранга, мы исчерпаем всё
события за конечное число шагов. Процедура может оборват^
ся только в том случае, если после некоторого шага не ока-
жется событий требуемого ранга. Мы докажем, что для на^
правленного графа это невозможно. Более того, докажем, что',
во-первых, полученная таким путем нумерация правильная:,
т. е. удовлетворяет поставленному условию (есйи /-</, то i<j),
й что, во-вторых, все события направленного графа получат
при этом алгоритме номера.
Для доказательства первого положения достаточно заме-
тить, что в процессе вычеркивания дуг мы движемся все вре-
мя в направлении стрелок-работ и поэтому никакое предше*
ствующее событие не может получить номер, больший, чем
любое последующее.
Для доказательства второго утверждения допустим про?
тивное, а именно, что после некоторого k-ro шага не нашлось
ни одного события k-ro ранга, т. е. во все оставшиеся событий
входит хотя бы одна работа. Тогда, беря любое из оставшихся
незанумерованными заново событий, перейдем от него к ка-
кому-либо другому в направлении, обратном стрелке на той
входящей в это первое событие работе, которая по нашему
допущению обязательно найдется. От этого второго событий
•перейдем к следующему — а именно к тому, из которого в
это второе событие идет работа, существующая согласно все
тому же допущению. Так как в каждое из оставшихся собы-
тий входит не менее одной работы, этот процесс можно про?
должать неограниченно. Поскольку сетевой график с самого
начала .содержит только конечное число событий, то номера
Я
событий неизбежно начнут повторяться. Это значит, что если
пройти тот же путь в прямом направлении, т. е. в направле-
нии, указанном стрелками, мы получим замкнутый путь —-
цикл, что противоречит исходному предположению о том, что
сетевой график циклов не содержит. Полученное противоре-
чие доказывает наше второе утверждение. На рис. 3,6 изо-
бражен тот же граф, что и на рис, 3, а, но уже с правильной
нумерацией.
Приведенный выше алгоритм носит название «алгоритма
вычеркивания дуг». Как видно из доказательства, он не толь-
ко позволяет ввести на графе правильную нумерацию, но и
дает возможность обнаружить циклы. Признаком существовав
ния цикла служит отсутствие событий какого-Либб ранга, об-
наруживаемое во время введения правильной нумерации.
Из вышесказанного следует также, что ранг события—*
это максимальное число отдельных пабот, входящих в какой-
либо один из путей, ведущих из нулевого (начального) собы*,
тия в данное. Так, события первого ранга не имеют путей, со-
стоящих более чем из одной работы, ведущих в них из 0. Со-
бытия второго ранга «связаны» с 0 путями, которые состоят
не более чем из двух работ, причем для каждого события вто-
рого ранга хоть один такой путь обязательно существует. На*
пример, 7 — событие четвертого ранга, так как имеется путь
из четырех работ— (0,2), (2,4), (4,5), (5,7), ведущий из 0 в
7, но нет пути из более чем четырех работ между 0 и 7.
Как и во многих других алгоритмах, мы вынуждены были
в процессе введения правильной нумерации двигаться «шага-
ми»— от одних событий к другим, однако направлял нас в:
этом движении сам алгоритм. Разумеется, можно было бь*
сначала рассмотреть все пути, ведущие из 0 к каждому собы-
тию и определить ранг каждого события. После этого можно
было ввести нумерацию, придав сначала новые номера собы-
тиям первого ранга, затем — второго и т. д. Но чем больше
событий и работ содержит график, тем больше таких путей.-
Насколько быстро растет число путей, затрудняя проведение
методов расчетов, связанных с их полным перебором, мы уви*
дим сейчас, рассмотрев алгоритм определения числа путей.
Обозначим через Ng(i) число путей, ведущих из 0 в собы-
тие i. Примем, что для события 0 имеет место соотношение
Wo(6) == 1. Тогда, чтобы получить число путей, ведущих от О
к какому-либо событию i, необходимо рассмотреть все пред-;
шествующие ему события j, т. е. такие, что jczi, и сложить
все числа No(j). В самом деле, любой путь, ведущий из 0 в jl
станет путем, ведущим из 0 в i, если добавить к нему работу
'(/, i). Двигаясь от событий к событиям в порядке возрастания
их рангов, мы пройдем все события и найдем для каждого из
них ;Vo(i). Для графа, изображенного на рис, Згб, получим!
18
Wo(0) = 1;
N0(l) =/Vo(0) = l;
Xo(2) = A’o(O) = 1;
N0(3) =WoU) = i;
NQ(4)—No(O) 4-JV0(2) = 2;
N0(5) =Ло(/) +Wo(4)=3;
A0(6) ~W) +AM#)=3}
N0(7) ~N0(5) +/V0(5)=6;
M)(S) =M>(2) +M>(7) =7;
7V0(9) ==AM7) +A'0(S) = 14;
NQ(1O) =N0(3) + N0(9) = 15.
Общая формула имеет вид:
JVo(O== 2 N0(j).
J CZ i
d-I)]
Таким образом, уже в событие с номером 10 ведет из О
пятнадцать различных путей. Для графиков, содержащих
сотни событий, число путей может достигать многих тысяч и
десятков тысяч. Таким образом, алгоритм вычеркивания дуг
бесспорно экономит время.
Аналогично можно найти число путей, ведущих от задан-
ного события I в конечное событие п. Оно определяется с по-
мощью аналогичной формулы:
А,(«) =AH0=* 2 N„(j), (1-2);
/ zoi
в которой, однако, суммирование ведется по последующим, а
не по предшествующим событиям.
Из формул (1—1) и (1—2) следует, что общее количество
путей, ведущих из 0 в п и проходящих через данное событие i,
равно
ЛГ(О ~Л’о(ОЛМО, (1-3);
так как любой из путей от 0 до I можно сочетать с любым из
путей от i до п и при этом получится путь из 0 до п.
Формула (1—1) для No(n) и формула (1—2) для Nn(0)'
дают общее количество путей, соединяющих Осп для всего
графа в целом. Как мы уже напоминали читателю, самый
длинный из этих путей называется критическим. Если в графе
есть несколько путей максимальной (одинаковой) длины, все
они называются критическими. В графе рис. 3,6 критический
путь проходит через события 0, 2, 4, 5, 7, 8, 9 и 10. Он обозна-
чен более толстыми линиями, чем остальные работы графам
Как определить этот критический путь, не вычисляя длины
всех пятнадцати путей из 0 в п, об этом мы сейчас расскажем
читателю.
Упомянутый нами во введении важнейший параметр сете-
19
вого графика — наиболее раннее возможное время наступле-
ния /-го события обозначается символом Тр (j) и определяется
также рекуррентной формулой
' (1—4),
Эта формула гласит, что Тp(j) есть длина самого длинного
из No(j) путей, ведущих из 0 в /. Если бы все tu на всем гра-
фике были равны одному и тому же числу t, то Tp(j) просто
равнялось бы рангу события j, умноженному на число t, так
как самым длинным путем был бы путь, состоящий из макси-
мального числа действительных работ. В этом случае при-
шлось бы ввести дополнительное понятие «действительный
ранг», так как в определении ранга, данном выше, различие
между нефиктивными и фиктивными работами никакой роли
не играло бы. На самом деле все /// вообще говоря, различ-
ны, и формулу (1—4) следует применять шаг за шагом, лучше
всего двигаясь в порядке правильной нумерации событий. По-
ясним это на нашем примере. Для начального события 0 на
сетевом графике рис. 3,6 положим Тр(0) = 0. Тогда для со-
бытий первого ранга 1 и 2, применяя формулу (1—4), полу-
чим:
Тр(1) -Тр (0) +4 = 4;
Тр(2) = Тр (0) + 5 = 5;
Для события 3 найдем:
Тр(3) = Тр(1) + 6 = 4 + 6= 10;
Для события 4'.
Тр(4)=тах{ (ТД0 +0; (7^(2) 4-7)]= max {10,12} = 12?
Для события 5:
Тр(5) = тах[(Тр(1) + 8);(Тр(4) + 3)} = max [12; 15 }= 15?
Продолжая этот процесс, получим:
Тр(6) = 13; Г, (7) = 15; Тр(8) = 17; Тр(9) = 21-Тр (10) = 24.
Полученные значения Тр(1) надпишем над кружками, изобра-
жающими события (см. рис. 3,в).
Существуют различные упрощенные способы вычисления
Tp(j) с помощью специальной формы записи всех tn в опре-
деленным образом составляемые таблицы. Эти способы носят
название «табличных алгоритмов» и широко применяются
при обработке реальных сетевых графиков. Нас в данный мо-
мент интересует только сам факт, что при любом существую-,
щем алгоритме мы неизбежно должны шаг за шагом доби-
раться из нулевого события к данному, интересующему нас..
Алгоритм обеспечивает то, что мы через каждое событие в
20
процессе подобных вычислений пройдем только один раз и
не будем вынуждены перебирать и сравнивать между собою
все пути, имеющиеся на графе.
Самое позднее допустимое время наступления события i,
.которое принято обозначать символом Tn(i), определяют с
помощью аналогичной формулы, на этот раз снова «обращен-
ной» не к предшествующим, а к последующим событиям. В на-
ших обозначениях эта формула выглядит так:
гп(0 = (1-5)
Для определения Тп (/) для каждого события необходимо
«двигаться» в направлении, обратном правильной нумерации,
т. е. от конечного события п к начальному событию О. Обра-
тимся снова к рис. 3, в. Для события 10 полагаем
Тп(10)==Т^10) ==24.
Для события 9, применяя формулу (1—5), получим:
?’п(9) = Тп(10)— 3 = 24 — 3 = 21.
Для события 8 найдем:
7\(<S) = (9) — 4 = 21 —4 = 17.
Для события 7:
7й(7)=тш {(Гп(9)—5);(ГП(5)—2)} = /жп { 16; 15} = 15.
Для события 3:
Тп0)= min {(Гл(10) — 6); (Гп (7) — 1) } = min { 18; 14} = 14.
При этом мы каждый раз переходим к таким событиям, у ко-
торых для последующих событий уже определены Тп(}). Од-
новременно с 7\(3) мы можем найти Тп (5) и Тп{6),
Продолжая этот процесс, получим:
ГД5) = 15; Гп(0 = 14; Тл(1) = 7; Тл(4) = 12; 7\(2) = 5;
Тп(0)=0.
Полученные значения 7П(/) подпишем под кружками, изобра-
жающими события (см. рис. 3,в).
Разность между 7’п(0 и 71p(i) для данного события назы-
вается резервом времени события и вычисляется по формуле:
7?(0 =rn(i)-7’p(i), Д1-6Х
которую иногда называют «уравнением времени». Название
это оправдано тем, что критический путь проходит через об-
ладающие минимальными R(i). В частности, если директив-
ный (утвержденный) срок наступления окончания всей «боль-
шой» работы, т. е. момент наступления события п, совпадает
с величиной Tp(n), у всех событий, лежащих на критическом
пути, резерв времени R(J) = 0,
21
В нашем примере /?(i) — 0 для событий 1, 2, 4, 5, 7, 8, 9 й
'10, через которые, следовательно, и проходит критический
путь, как это и изображено на рис. 3, б.
Полный резерв времени работы (I, j) вычисляется по фор*
муле
rn(G /)=Гп(/)-Тр(0-^.- '(1-7).
Свободный резерв времени работы (t, /) вычисляется по
формуле
Гс(ъ/) = тр(/) — т„(0 — . .(1-8);
«Из этих формул следует, что
1) задержка в выполнении работы (i, j) на величину А,
большую чем r„ (i, j), приведет к задержке в наступлении ко-
нечного события на величину А — г (i, j);
2) задержка в выполнении работы (г, /) на величину д, не
превосходящую rc(i, j), вообще не повлияет ни на один другой
срок, определяемый данным графиком.
Приведем доказательства этих утверждений.
Обозначим максимальную длину пути от заданного собы-
тия i к другому заданному событию / через 1^ах- Тогда:
7р(0 = i°Jax; ;(i-9):
; Xi-iox
*(0 =^-^л ,(1-11):
; (1—12).
и, наконец, *
Таким образом, нахождение всех параметров сетевого гра-
фика сводится к вычислению символов вида / %ах при различ-
ных значениях i и /.
Из формулы (1 — 12) следует, что r„(i, j) есть разность
между длиной критического пути 1^х и максимальным пу-
тем между 0 и п, содержащим работу (i, /). Следовательно,
если увеличить ti, как раз на эту разность, указанный путь
превратится в критический, а если увеличить tij на А, боль-
шее чем гл (i, j), указанный путь не только станет критиче-
ским, но и превзойдет по длине прежний критический путь
на величину [А — r„ (I, /)], что и требовалось доказать в
первом случае.
Чтобы доказать второе утверждение, достаточно заметить,
что если событие / произойдет в самый ранний допустимый
срок, равный 1%£х, а событие i — в самый поздний допустимый
срок, равный Z тона выполнение работы (i, j)
останется еще время, равное I0-'— Ц0'" — 11^пг ), тогда как
22
требуемое для этого время составляет 1ц Отсюда видно, что
увеличение tn на величину (I, j) не может повлиять на все.
ТР(0 и Тп(») остальных событий графика (см. рис, 4),
1<..tli—4
тра) Ш tp(j) r„(j)
К определению
свободного резерва
Рис. .4,
В нашем примере полные резервы времени, как нетрудно
убедиться на рис. 3, в, соответственно равны:
гп(0,1) =7-0-4 = 3; .
Г „(7,3) = 14—4—6 = 4?
га (2,4) = 12—5—7 = 0;
г„ (3,73) =24—10—6 = 8;
гв«6) = 14-12-1=1 и т. д.
г„ (3,2) =5—0—5=0;
га (1,5) = 15—4—8 = 3;
га(3,7) = 15—10—1 =4;
г„ (4,5) = 15—12—3 = 0:
Свободные резервы этих же работ равны:
гс(3, 7) = 4—0—4 = 0;
гс(1,3) = 10—7—6 = 3;
гс(2,4) = 12—5—7 = 0;
1\(3,10) =24—14—6 = 4;
Г е(4,6) = 13—12—1 = 0 и т. д.
гс(О,2) = 5—0—5 = 0;
гс(/, 5) = 15—7—8 = 0;
гс(3,7) = 15—14—1 =0;
гс(4,5) = 15—12—3 = 0:
События, через которые проходит критический путь, назы-
ваются критическими событиями. Аналогично работы, входя»
щие в состав критическото пути, тоже называются критиче-
скими. Мы видим, что у критических работ (в нашем примере
это работы (3,2), (2,4), (4,5) и т. д.) и полные и свободные
резервы времени равны нулю. Равенство нулю полного резер-
ва времени работы является необходимым и достаточным при-
знаком того, что данная работа критическая (если, как мы
уже сказали, директивное время равно величине 7^(10)). На-
против, свободный резерв может быть равным нулю и даже
.отрицательным и у некритических работ. Например, как пока-
.•23
ваяо выше, rc (1, ЗУ == —З.Это означает, что если увеличить про»
должительность работы (1,3) на три единицы времени (на-
пример, на три дня), то все работы, лежащие на самом длин-
ном пути, соединяющем события 3 и 10 (это путь, идущий че-
рез события 3, 7, 9 и 10), при условии, что событие 1 наступило
в свой наиболее поздний срок — через семь дней после начала
работ, придется начать с опозданием на три дня по сравнению
с их наиболее ранними сроками — величинами Тр(3), Тр(7),
и Тр(9).
Таким образом, из формул (1—9) — (1—13) следует, что
все параметры сетевого графика носят, так сказать, экстре-
мальный характер. Все они определяются через величины ви-
да /да^т. е. через значения максимальных длин путей, соеди-
няющих на графе два определенных события.
Формула (1—4) дает универсальный алгоритм для опре-
деления 1^. Она легко может быть записана для каждой па-
ры событий i и k, для которой i-<k, а именно, в этом случае
вместоследует писать
пьИЛ *
Поэтому алгоритм нахождения I называют иногда уни-
фицированным алгоритмом.
Если почему-либо нужно найти только одну величину 10^ах
для одного события i, нет необходимости вычислять Т р(/) для
всех событий / ранга меньшего, чем ранг i. Достаточно мето-
дом «вычеркивания дуг» двинуться от события i назад (т. е.
в направлении, обратном указанному стрелками) и дойти до
нулевого события. При этом мы вычеркнем только те работы,
которые принадлежат каждому из путей, ведущих из 0 в L
При проверке какого-либо участка большого сетевого графика
или при изменении в процессе выполнения плана оценок 1ц
для некоторых работ такой метод может значительно сэко-
номить время.
Рассмотрим еще один вопрос, относящийся к теории гра-
фов. Мы уже знаем, что изоморфные друг другу графы счи-
таются тождественными. Спрашивается, как наиболее эко-
номно задать сетевой график, не изображая его в виде реаль-
ного чертежа?
Сделать это можно, по крайней мере, двумя различными
путями. Первый метод состоит в задании графика множеством
его работ. В самом деле, указав все имеющиеся на графике
работы и их продолжительности, мы, очевидно, однозначно
(с точностью до изоморфизма!) опишем все отношения «пред-
шествующий— последующий» и тем самым однозначно опи-
шем график.
Для построения графика, заданного множеством работг
24
достаточно нарисовать столько кружков, сколько различных
номеров событий встречается в перечне работ, проставить на
кружках номера и затем соединить события стрелками в со-
ответствии с перечнем работ, проставляя над стрелками их
«длину» — продолжительность соответствующей работы.
Стрелки, соответствующие работам нулевой продолжительно-
сти, как говорилось выше, следует проводить пунктирными
линиями.
При задании графика с упорядоченной, правильной нуме-
рацией событий целесообразнее всего перечень работ состав-
лять в так называемом словарном порядке: в перечне работы
ставятся в порядке номеров их начальных событий, а при рав-
ных начальных событиях в порядке номеров их конечных со-
бытий. Так, приведенный на рис. 3, б сетевой график задается
следующим множеством словарно упорядоченных его работ:
(0,1) (0,2) (0,4) (1,3) (1,5) (2,4) (2,6) (2,8) (3,7)
(4,5) (4,6) (5,7) (6,7) (7,8) (7,9) (8,9) и (9,10).
\3,10),
Предлагаем читателю, не заглядывая в график рисун-
ка 3,6, самостоятельно восстановить сетевой график по выпи-
санному нами множеству его работ. Продолжительности ра-
бот (в том же порядке) соответственно равны 4, 5, 6, 6, 8, 7,
О, 5, 1, 6t 3t 1, 0, 1, 2, 5, 4 и 3 единицам времени.
Современные методы обработки сетевых графиков на
электронных вычислительных машинах требуют введения дан-
ных о графике именно в такой форме. В результате обработки
они непосредственно выдают на печать интересующие потре-
бителя параметры графика в том или ином порядке.
Другой метод задания сетевого графика состоит в зада-
нии так называемой матрицы инциденций. Терминология эта
целиком заимствована из теории графов. Матрицей инциден-
ций, в ее простейшей форме, называется квадратная таблица,
содержащая ровно столько строк и столбцов, сколько собы-
тий (включая 0) содержит график, т. е. (/г + 1) строк и (л-fl
4- 1) столбцов. На пересечении ьой строки и /-го столбца ста-
вится единица, если на графике есть работа (ц /) и нуль в про-
тивном случае. Так как по подобной матрице немедленно
можно составить перечень всех работ, ясно, что график за-
дается матрицей однозначно. Если на графике уже введена
правильная нумерация, то единицы на матрице могут стоять
только правее так называемой главной диагонали, соединяю-
щей клетку матрицы с нулевыми номерами (0; 0) с клеткой а
наибольшими номерами (п; п). Ниже приводится матрица ин*,
диденций для сетевого графика, изображенного на рис. 3,5-
25
Ц7" '!
0 0 1 1 0 1 0 0 0 0 0 0
! 0 0 0 1 0 1 0 0 0 0 0
2 0 0 0 0 1 0 1 0 1 0 0
3 0 0 0 0 0 0 0 1 О 0 I
4 0 0 0 0 0 1 I 0 0 0 0
5 0 0 0 0 0 0 0 1 0 0 О
6 0 0 0 0 О 0 0 1 0 0 0
7 0 0 0 0 0 0 0 0 1 1 О
8 0 0 0 0 0 0 0 0 0 1 0
9 0 0 0 0 0 0 0 0 0 0 I
10 0 0 0 0 0 0 0 0 0 0 0
Несмотря на кажущуюся громоздкость Подобной записи,
сна в ряде случаев бывает очень полезна.
Так, независимо от того, введена на графике правильная
нумерация или нет, матрица инциденций позволяет сразу про-
верить, нет ли на графике лишних истоков и стоков, В самом
деле исток, по определению, не имеет входящих работ, а пото-
му должен быть представлен столбцом, состоящем из одних
нулей. По аналогичной причине сток представлен строкой,
также состоящей из одних нулей.
В нашем примере это столбец с номером 0 и строка с но-
мером 10,
Наличие лишних «нулевых» строк или столбцов свидетель»
ствует о том, что график не является направленным графом й,
стало быть, где-то допущена ошибка.
Прежде чем перейти к дальнейшим вопросам, связанным
с матрицей инциденций, объясним ее название. В теории гра-
фов дуга и вершина называются инцидентными, если вершина:
служит началом или концом данной дуги. Более того, две вер-,
шины считаются инцидентными, если они соединены дугой, а
•'две дуги — если они имеют по крайней мере одну общую
вершину (напомним, что в симметрических графах и вообще в
графах с кратными дугами две дуги могут иметь и две общие
вершины). Поэтому наша'матрица, показывающая, какие со»,
бытия инцидентны друг с другом, и называется матрицей ин-,
циденций.
Матрица инциденций позволяет легко выписывать различ-
ные пути графа. Например, на вопрос, зависит ли выполнение
работы [7, 8) от выполнения работы (2, 4) матрица дает ут«.
вердительный ответ, так как в седьмом столбце единицы стоят,
в пятой и шестой строках, а в четвертой строке единицы стоят
в пятом и шестом столбцах. Стало быть, от события 4 к собы-?
тию 7 ведут два пути: (4,5), (5,7) и (4,6), (6,7), или, в сокра-ч
щенной записи, пути (4, 5, 7) и (4, 6, 7), Если номера интере-?
сующих нас событий отстоят дальше друг от друга, прихб-*
дится просмотреть „большее. количество строк и столбцов.
2Ц
Разумеется, тот же вопрос можно решить и на графике, и на
перечне работ, поскольку все это лишь различные методы за-
дания одного и того же графа.
Недостатком матрицы инциденций в ее простейшей форме
является отсутствие информации о величинах ttJ , которую
придется давать дополнительно. Этот недостаток легко устра-
ним, если вместо нулей в матрице ставить точки или прочерки,
а вместо единиц — величины //у. В этом случае выявляется
даже экономичность записи в виде матрицы. В самом деле,
если график содержит много событий и большое число работ,
то в перечне работ одни и те же номера событий будут повто-
ряться много раз, тогда как в форме матрицы инциденций
можно вообще не вводить номеров событий, если график уже
упорядочен, т. е. если введена правильная нумерация. Более
того, существуют программы для ЭЦВМ (по крайней мере,
составление таких программ не представляет труда), по кото-
рым электронная цифровая вычислительная машина может
упорядочить нумерацию на произвольно составленной матри-
це. инциденций, если только матрица отображает направлен-
ный граф, или же обнаружить ошибки, если график составлен
неправильно с точки зрения вышеуказанных требований. По-
этому при обработке очень больших графиков матрицы инци-
денций могут найти полезное применение.
На этом мы закончим рассмотрение вопросов о способах
задания сетевых графиков.
Отметим, что все рассматривавшиеся до сих пор графики,
согласно нашим определениям, имели фиксированные значе-
ния продолжительности каждой работы, т. е. точно установ-
ленные величины tij . Между тем, как мы знаем, оценки ве-
личин tij получают в результате усреднения первоначальных
оценок, выдаваемых обычно с большим разбросом. Спраши-
вается, как же могут отразиться на важнейших параметрах
графика те, исходные неточности, которые с самого начала за-
ложены в Оценках, зачастую довольно субъективных?
Ответ на этот вопрос будет дан во второй главе.
Глава 2
СЕТЕВЫЕ ГРАФИКИ КАК ОБЪЕКТ ТЕОРИИ
ВЕРОЯТНОСТЕЙ
Если >на сетевом графике продолжительность каждой ра-
боты есть фиксированная величина, такой график называется
детерминированным сетевым графиком. Существуют два ос-
новных метода анализа и расчета сетевых графиков, получае-
мых путем учета всех выданных исполнителями оценок про-
должительности различных работ. Первый метод состоит в
27
том; что график превращают в детерминированный', заменяя
различные оценки — оптимистическую, пессимистическую и
вероятную, одной оценкой 1ц , рассчитываемой обычно по эм-
пирической формуле
t +4/ -4-t
f .. опт ~ вер 1 песс/ (q jj
6
и вводя добавочную характеристику — меру неопределенности
данной оценки — дисперсию оценки t а, обозначаемую сим-
волом и вычисляемую обычно по эмпирической формуле:
о I- = )2л (2-2J
В этом случае все расчеты на графике сначала проводятся
так, как если бы мы имели дело с детерминированным график-
ком, т. е. по методам, разобранным в предыдущей главе. За-
тем, однако, с помощью учета величин а у можно рассчитать
вероятности того, что полученные из расчета параметры гра-
фика, такие, как ранние сроки 7p(i), поздние сроки (i), ре-
зервы времени и т. п., действительно будут находиться в тех
или иных числовых границах. Фундаментальное значение для
всех подобных расчетов имеет вводимое при этом допущение
о том, что продолжительности различных работ на графике
(точнее двух любых работ) являются независимыми величи-
нами с точки зрения теории вероятностей. При этом допуска-
ют, что с определяемой по формуле (2—2) величиной о?. мож-
но в дальнейшем обращаться как с «настоящей» теоретико-
вероятностной дисперсией, вычисляемой как средний квадрат
отклонения реально наблюдаемых значений от их мате-
матического ожидания. Точно так же обращаются и с вели-
чиной tif , определенной формулой (2—1), считая ее равной
истинному математическому ожиданию продолжительности
данной работы (I, j). Тогда по известной теореме теории ве-
роятностей о том, что дисперсия суммы независимых случай-
ных величин равна сумме дисперсий слагаемых, можно полу-
чить значения дисперсий практически для любого параметра
графика, поскольку, как было показано нами в предыдущей
главе, все параметры могут быть представлены как суммы,,
содержащие в качестве слагаемых величины tn и определен-
ные нами величины 1^ах. Но величины 1^ах по определению
также являются суммами величин вида /// , так как они суть
длины путей, а длина пути есть сумма длин входящих в него
Дуг.
Таким образом, в конечном счете любой параметр графика^
из перечисленных выше, есть сумма длин дуг, т. е. сумма про-
должительностей работ. Пусть А есть некоторый параметр
графика. Тогда всегда его можно представить в виде
28
Л= 2 t№t ,(2-3):
(А i)QA
где, разумеется, сумма имеет алгебраический смысл, т. е.
оценки tn могут входить в нее как со знаком « + », так и со
знаком «—». Поскольку теорема о дисперсии суммы относит-
ся именно к алгебраическим суммам, согласно этой теореме
= S a’, (2-4Х
(U)G^
где оД— означает дисперсию параметра А, а суммирование
производится по всем (г, /), от которых зависит А.
Эти формулы лежат в основе вероятностных расчетов, про-
водимых на сетевых графиках, превращенных в детерминиро-
ванные.
Так как величины —ожидаемые продолжительности
работ суть не что иное, как математические ожидания этой
продолжительности, то математическое ожидание А любого
параметра А, являющегося суммой величин вида to , есть
сумма математических ожиданий слагаемых, т. е. 2 . Ос-
тается оценить вероятности отклонения величины А от своего
математического ожидания Л, если дисперсия osA уже изве-
стна. Для этого необходимо знать закон распределения вели-
чины А, т. е. вероятность того, что А меньше любой наперед
заданной величины х. Эта вероятность обозначается символом
Р{4 <х) . Так как А есть сумма независимых случайных ве-
личин вида to , то если число слагаемых в этой сумме доволь-
но велико, скажем, достигает нескольких десятков, по извест-
ной теореме Ляпунова сумма имеет распределение, близкое к
нормальному. Это означает, что искомая вероятность может,
быть приближенно представлена формулой:
! х (Х~А)2
Р(А<х}= -—=$ е 202 dx. '(2-5):
О' у 2 л —0Q
Функция
X2
X —------
Ф(х) = f * 2 dx (2—6)',
/2л о
называется интегралом вероятности, или функцией Лапласа.
Ее значения приведены в справочниках по математической
статистике. Предыдущая формула с помощью этой функции
может быть записана в виде:
«ь 2 О
(.2-7)'
29
а потому значение вероятности попадания случайной величи-
ны А в интервал (а, 0) может быть найдено по следующей
формуле:
। р._ д’ а__д
Р[а<А<0}==—- [Ф( 1-------)-Ф(------)]. (2-8);
2 а а
С помощью этой последней формулы нетрудно найти, имея
таблицы функции Ф, вероятности различных отклонений пара-
метров А сетевого графика, первоначально вычисленных как
параметры детерминированного графика.
Как видно из формулы, для определения этой вероятности
достаточно найти отношение интересующего нас отклонения
величины А к квадратному корню из ее дисперсии, т, е. отно-
шение
А—А
Это отношение носит специальное название. Оно называет-
ся критическим отношением. Таким образом, критическое от-
ношение есть дробь, в числителе которой стоит разность меж-
ду значением величины А и ее математическим ожиданием А,
а в знаменателе — квадратный корень из дисперсии of, так
называемый стандарт величины А. Выпишем таблицу вероят-
д________________________________________д
костей того, что критическое значение z = —— меньше той
или иной величины В столбце z даны значения критиче-
ского отношения, в столбце Р2 соответствующие вероятности.
Таблица значений вероятностей критических отношений для нормального
распределения
Z Рг Z Рг
0,0 0,5000 — 3,0 0,0013
0,5 0,6915 — 2,5 0,0062
1.0 0,8413 — 2,0 0,0228
1,5 0,9332 — 1,5 0,0668
2,0 0,9772 — 1,0 0,1587
2,5 0,9938 — 0,5 0,3085
3,0 0,9987 — 0,0 0,5000
Как видно из таблицы, получение критического отношения
больше чем 3,0 имеет вероятность 1—0,9987 = 0,0013. Такую
же малую вероятность имеет получение критического отноше-
ния меньшего чем —3,0. Это обстоятельство иногда называют
«Правилом За»: отклонения в любую сторону от математиче-
ского ожидания, превышающие За, настолько маловероятны,
что ими можно пренебречь. В частности, так поступают, оце-
нивая эксперименты, в которых измеряемая величина дала
30
слишком большие отклонения от среднего значения, наблю-
даемого в остальных опытах. Такие «большие» отклонения
следует или отбросить, как ошибочные, или искать существен*
ные факторы, которые остались неучтенными и изменили са-
му экспериментальную процедуру.
Обратимся снова к сетевому графику, изображенному на
рис. 3,6. Критический путь на этом графике проходит через
события О, 2, 4, 5, 7, 8, 9 и 10. Его длина равна сумме длин ра-
бот (6,2); (2Л);- (4,5); (6,7); (7,8); (8,9) и (9,10), т. е.
5 + 74-3 + 0 + 2 + 4+3 = 24 ед. времени. ' ;
Допустим, что дисперсии оценок продолжительности работ,
найденные по формулам (2—4), соответственно равны 1; 1,5?
0,5; 0; 0,4; 1 и 0,6 (мы ради экономии места не выписывали
все оптимистические, пессимистические и вероятные оценки
величин tij и не приводили расчетов ожидаемых ///; сейчас
мы допускаем, что все такие расчеты уже проведены и о#
вычислены). Тогда дисперсия длины критического пути равна
1 + 1,5 + 0,5 + 0 + 0,4 + 1 + 0,6 = 5,0.
Найдем теперь вероятность того, что наша «большая» ра-
бота продлится не 24 дня, как указывает длина критического
пута, а например,. 26 дней. Вероятность того, что длина крити-
ческого пути станет равной не менее чем 26 дням, вследствие
приближенных оценок продолжительности критических работ
((именно из-за этого, а не по другим причинам!) есть вероят-
ность получения критического отношения, не меньшего, чем
26—24 2,00
(вычисления проведены приближенно, с точностью до третьей
значащей цифры), Из нашей таблицы следует, что это соот-
ветствует примерно вероятности 0,80. Это означает, что в
80% случаев задержка не превысит двух единиц времени,
однако в оставшихся 20% случаев график будет выполнен не
ранее, чем за 26 единиц времени. Таким образом, вероятность
задержки графика на две единицы времени (скажем, на два
дня или две недели) только за счет неопределенности, содер-
жавшейся в оценках на критическом пути, равна 20%. «Пра-
вило 3 о» гласит, однако, что задержка на величину 3 X 2,24 --
= 6,72 ~ 7 ед. времени уже чрезвычайно маловероятна. Так
же маловероятно и выполнение графика в срок меньший, чем
24—7 = 17 ед. времени. Таким образом, вероятностный анализ
только одного критического пути дает право утверждать, что
почти наверняка график будет выполнен (с вероятностью
99,74%!) в срок между 17 и 31 единицами времени, а с вероят-
ностью (при 2 о) 95,44% —в срок между [24—(2,24 X 2)] и
[24+А (2,24 X 2)], т, е, примерно, между 19,5 и 23^5 ед, времени.
31
Может, однако, случиться, что неопределенность (а она
тем больше, чем больше соответствующие дисперсии) оценок
на. путях, не являющихся критическими, больше неопределен-
ности оценок критического пути настолько, что не исключено
их превращение в критические пути. Все эти и подобные им
вероятности легко могут быть найдены этим же методом. Вви-
ду очевидной простоты получения подобных вероятностных
оценок, мы на этом задерживаться больше не будем, а сдела-
ем, несколько замечаний.
Во-первых, при работе по этому методу полезно с самого
начала вычислить дисперсии.для всех работ, т. е. все величи-
ны az/. Тогда нетрудно определить ад для любого интерес
сующего нас параметра А.
Во-вторых, сам данный метод является приближенным еще
в том смысле, что заключение о нормальном виде закона рас-
пределения, сделанное нами на основании допущения о при-
менимости теоремы Ляпунова, справедливо только для пара-
метров, являющихся суммой, по крайней мере, двух-трех де-
сятков исходных оценок. Однако хотя в случае сумм, состоя-
щих из малого числа слагаемых, необходимо пользоваться
другими законами распределения, например так называемым
распределением Стьюдента [3], сама процедура остается
прежней. Только оценка вероятности получения того или ино-
го критического отношения или некоторых других дробей, со-
держащих все те же дисперсии, должна производиться соот-
ветственно по другим таблицам.
Наконец, и это самое важное, даже числовая ошибка, по-
лученная за счет использования округленных значений, не ис-
кажает практически основных выводов о пригодности данно-
го разработанного нами графика для решения в срок постав-
ленной задачи, так как практически важное значение имеют
только достаточно большие отклонения (т. е. отклонения,
имеющие достаточно малые вероятности, скажем, 0,05 или
0,01) от математических ожиданий.
Все эти рассуждения относятся к расчетам на детермини-
рованных графиках, причем такие расчеты, как правило, про*
водятся вручную.
Существует второй основной метод учета всех выданных
исполнителями оценок. Этот метод состоит в том, что график
рассматривается как вероятностная модель, на которой оцен-
ки могут, вообще говоря, принимать любые значения, лежа-
щие в крайних, указанных исполнителями пределах, и даже
выходящие за эти пределы в той степени, в которой это допу-
скают законы теории вероятностей. Суть этого метода, кото-
рый называется методом статистических испытаний, состоит в
получении (на этот раз на электронной цифровой вычисли-
тельной машине — ЭЦВМ) очень большого количества от-
дельных реализаций данного сетевого графика, отличающихся
32*
тем, что продолжительности работ —величины ?,/ на каждом
из графиков случайно «выбираются» машиной по законам,
характеризующим распределение каждой из отдельных оце-
нок tn . При этом, правда с малой вероятностью, каждая из
оценок может даже «выходить» за границы ±3<Т// , если толь-
ко машина «проиграла» достаточно большое количество раз
весь сетевой график, так что появление больших отклонений
отдельных tij стало статистически возможным. При каждом
таком «проигрывании» графика машина находит критический
путь и вычисляет все необходимые параметры графика. Но
теперь уже математическое ожидание любого параметра и
его дисперсия определяются не через входящие в него слагае-
мые tij, а непосредственно как среднее значение и среднеквад-'
ратичное отклонение из всех значений данного конкретного
параметра, полученных во всех «проигранных» машиной ва-
риантах графика. Это — наиболее точный метод анализа се-
тевого графика, рассматриваемого как вероятностная модель.
Любопытно, что в разных вариантах критическими могут оказаться
различные пути на графике. Тогда можно ввести некоторую статистическую
меру критичности пути — отношение числа вариантов, в которых данный
путь был критическим, к общему числу рассмотренных машиной вариантов.
Располагая пути и входящие в них работы в порядке убывания их критич-
ности, мы тем самым привлечем внимание руководителей работ к самым
узким участкам плана, которые если и не критичны, то при небольших из-
менениях продолжительности работ становятся критичными.
Интересно остановиться на вопросе о том, сколько раз необходимо
«проиграть» один и тот же график на машине, чтобы получить заданную
точность оценок параметров. Оказывается, это число весьма велико.
Поскольку при многократном моделировании средние оценки уже пол-
ностью соответствуют условиям теоремы Ляпунова, при решении этого
вопроса можно уверенно считать, что здесь «работает» нормальное рас-
пределение. Решая с помощью таблиц для нормального распределения, на-
пример, вопрос о том, чему должна равняться минимальная «кратность»
моделирования графика для получения с вероятностью 90% оценок, от-
клоняющихся от «истинных средних» не более чем на 0,01 получаемой их
дисперсии, найдем, что график нужно «проиграть» около 27 000 раз. Для
той же ошибки, но вероятности 95%, кратность составит около 38 500 раз.
Разумеется, такое количество расчетов полного графика иод силу только
электронной машине. При этом время, затрачиваемое на «проигрывание»
столь большого количества реализаций, составляет всего несколько часов
(для больших графиков, содержащих несколько сот событий), причем ма-
шина выдает не все получаемые результаты, а непосредственно среднее
значение искомого результата и его дисперсию.
Основным допущением и в этих расчетах является наше
основное допущение о независимости продолжительности
каждой работы от продолжительности всех основных работ.
Это положение является, вообще говоря, не совсем убедитель-
ным, так как нетрудно найти действительные фактические
случаи, когда продолжительность работы зависит, вообще,
от момента ее начала. Скажем, скорость проведения строи-
тельных работ, связанных с затвердеванием бетона, зависит
от температуры и, стало быть, от погоды, времени года и т. п.
33
Однако рассмотрение сетевых графиков, на которых вели*
чины tif зависят друг от друга, представляет еще нерешенную
математическую задачу, * ;
Разрабатываемую и еще не исчерпанную задачу представ-
ляет также вопрос о наиболее удобных и точных методах
определения математических ожиданий и дисперсий продол*
жительности отдельных работ, по которым отсутствует доста-
точно большой объем статистических даннЫх из прежнего
опыта их проведения.
Количество работ, посвященных применению теории веро-
ятностей и математической статистики к сетевым графикам,
непрерывно растет. В этой области нас еще ждут интересные
результаты.
Глава 3
СЕТЕВЫЕ ГРАФИКИ КАК ОБЛАСТЬ ПРИЛОЖЕНИЯ
МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Основными параметрами графика, которыми мы интересо-
вались в двух предыдущих главах, были те или иные времен-
ные оценки. В самом деле, все они выражались через длины
различных путей, являющиеся, в свою очередь, суммами длин
дуг — продолжительностей отдельных работ. В результате
анализа графика руководство «большой» работой получало
сведения о том, какие работы являются самыми напряженны-
ми по времени, какие обладают резервами времени. За счет
увеличения продолжительности «второстепенных» (с точки
зрения сроков) работ можно перебросить ресурсы на крити-
ческие (по срокам) работы и тем обеспечить выполнение гра-
фика в срок или даже досрочно. Но мы совершенно не каса-
лись вопроса о том, как это надо делать, т.е. сколько и каких
ресурсов следует передать с одних работ на другие, чтобы
распределить все ресурсы наиболее выгодным — оптималь-
ным — образом с точки зрения, например, скорейшего выпол-
нения всей «большой» работы. Дело в том, что при любой пе-
реброске ресурсов меняется график, поскольку вносятся из-
менения в оценки tij 9 Слишком большие задержки («второсте-
пенных» работ могут превратить их в критические и даже не
сократить а, наоборот, замедлить выполнение графика в це-
лом. При этом самым главным обстоятельством является тот
факт, что в подавляющем большинстве случаев все виды ре-
сурсов— рабочая сила, оборудование, энергетика, финансы
и т. п., в каждой данной работе ограничены, т. е. по каждому
виду ресурсов существует предел, больше которого данный
ресурс расходовать нельзя.
Задачи оптимального распределения ограниченных ресур-
сов по работам сетевого графика представляют сюбой слож-
34
ные математические задачи, характер которых зависит как от
сложности самого графика, так и от той величины, которую
мы стремимся оптимизировать. Эта величина снова может
быть временем — тогда задача ставится так: надо распреде-
лить ресурсы таким образом, чтобы выполнить график в ми-
нимальное время. Но эта величина может быть и стоимостью:
надо распределить ресурсы так, чтобы при заданном времени
проведения всей работы, получить минимальную стоимость ее
выполнения. Наконец, это могут быть и сами ресурсы: надо
минимизировать потребление ресурсов при заданном времени
проведения «большой» работы. При этом каждый раз необхо-
димо исходить из той логической взаимосвязи очередности
выполнения всех работ, которая задана исходным сетевым
графиком. Именно это последнее обстоятельство налагает на
задачи оптимизации при сетевом планировании характерные
специфические ограничения.
Поясним сказанное следующим примером. Допустим, что ресурсы по-
ступают ежедневно в различных количествах. Тогда, если ряд работ, зану-
мерованных на графике с правильной нумерацией «большими» цифрами,
требует какого-либо специфического вида ресурса, то до начала этих ра-
бот, т. е. до выполнения всех предшествующих им работ, данный вид ре-
сурса совершенно бесполезен. Никакое перераспределение ресурса здесь не
может помочь, необходимо перераспределить сроки поставок различных ре-
сурсов.
Задачи оптимального распределения ресурсов в самом общем виде
при наличии k видов различных ограниченных ресурсов, потребляемых на
N различных работах, скорости выполнения которых являются некоторыми
произвольного вида функциями от количества ресурсов, причем работы
связаны в сетевой график — настолько сложны, что к их решению еще и
не приступали. К настоящему времени решен ряд отдельных, частных за-
дач, в которые введены очень серьезные математические ограничения на
зависимости времени выполнения работ от количества имеющихся ресур-
сов. В большинстве случаев подобные задачи или решаются специальными
полуграфическими алгоритмами, или сводятся к известным в математике
задачам линейного (или выпуклого) программирования. Мы рассмотрим
здесь несколько задач по оптимизации сетевых планов методами линейного
программирования.
Прежде всего напомним читателю сущность метода линей-
ного программирования.
Задачами линейного программирования называются зада-
чи, в которых требуется отыскать значения неизвестных пере-
менных величин Xi, Х2, х„, удовлетворяющих линейным ог-
раничениям вида
Я11*1 + ^12*2 + ••• + oinx bi
321*1 + «22^2 + ••• + а2п х „-^Ь 2
^1X1 + ат 2Х2 +... + атп х „< b т
'(всего т ограничений; т < п) и обладающих тем свойством,
что некоторая линейная функция (называемая «целевой
функцией»)
у = CiXi + С2Х2 -f;....+ спхп .(3—2)
хз-о:
35
достигает при этом своего максимального или минимального
значения.
Совокупность неотрицательных чисел Xt, Хг, .... х„, удовле-
творяющих условиям (3—1), называется допустимым реше-
нием задачи линейного программирования. Допустимое реше-
ние, при котором достигается максимум (или минимум) целе-
вой функции у, и называется оптимальным решением.
В реальных задачах линейного программирования, в том числе и в
задачах, относящихся к сетевым графикам, имеются десятки и даже сотни
ограничений и неизвестных. Поэтому перебор всех допустимых решений,
число которых очень велико даже в задачах с требованием целочисленно-
сти всех неизвестных, не под силу даже ЭЦВМ. Единственными приемле-
мыми способами решения таких задач являются различные алгоритмы, по-
зволяющие путем последовательных «шагов» — перехода от одного допу-
стимого решения к другому, сравнительно коротким путем добираться до
оптимального решения, минуя великое множество ненужных вариантов.
За недостатком места мы не можем себе позволить изложить здесь хо-
тя бы один такой алгоритм. Мы поясним только сущность подобных алго-
ритмов. С точки зрения «л-мерной геометрии» ограничения задачи линей-
ного программирования представляют уравнения плоскостей в п-мерном
эвклидовом пространстве. Совокупность ограничений выделяет в этом про-
странстве некоторый выпуклый многогранник, аналогичный выпуклому
многоугольнику на плоскости. Если это не так, т. е. если не существует
выпуклого многогранника, точки которого удовлетворяют ограничениям
задачи, то задача неразрешима, так как условия несовместимы. Если же
существует, то подстановка значений х^ хп в целевую функцию дает
число, пропорциональное «расстоянию» от точки (хь х2,...» хп) до плоско-
сти, уравнение которой представляет собой целевая функция. Задача ли-
нейного программирования состоит в том, чтобы найти по крайней мере
одну вершину многогранника, наиболее близкую (в случае поисков мини-»
мума) или наиболее удаленную (в случае поисков максимума) от «плоско-
сти», описываемой уравнением целевой функции.
Суть алгоритмов состоит в том, что, двигаясь от вершины
многогранника к вершине, попадают в конце концов в верши-
ны, обладающие указанными «экстремальными» свойствами.
При этом нет никакой необходимости проверять различные
«внутренние» точки многогранника и, вообще, все точки, от-»,
личные от его вершин.
Если ограничения, налагаемые на переменные, имеют раз-
личный характер неравенств:
одни неравенства имеют вид
«^1%! + aknXn^b
а другие —
a^Xi 2X2 $
то путем соответствующих замен переменных задача сводится
к предыдущей, если только она имеет допустимые решения,
Покажем теперь, каким образом некоторые задачи опти-
мизации сетевых планов могут быть сформулированы в таком
виде, который допускает их сведение к известным задачам ли-
нейного программирования^
36
Наиболее естественным образом это удается сделать в за-
дачах об оптимизации стоимости комплекса работ, представ-
ленного сетевым графиком. Мы сейчас рассмотрим подобную
задачу, однако заранее оговоримся, что ради сведения ее к
задаче линейного программирования приходится вводить не
очень естественное допущение о том, что стоимость выполне-
ния каждой работы графика от ее продолжительности задает-
ся линейной формулой вида:
С ij — CLij — bijtij , (3 3)
где сц —стоимость работы, а ац и b // —некоторые положи-
тельные константы. Если принять это допущение, то возникает
такая задача: при найденном критическом пути так использо-
вать резервы, имеющиеся у некритических работ, чтобы полу-
чить план работ, минимальный по стоимости.
Задача эта сводится к задаче линейного программирова-
ния следующим образом.
Обозначим совокупность критических работ через LKp,
Тогда в оптимальном по'стоимости плане некритические рабо-
ты необходимо «затянуть» на такой срок (ради снижения
стоимости), чтобы все они стали критическими. Весь вопрос
состоит в том, как распределить между различными некрити-
ческими работами имеющиеся резервы времени, чтобы полу-
чить наибольший выигрыш в деньгах. Раз все работы опти-
мального плана критичны, то для всех них справедливо соот-
ношение:
^-/ =Т(/)-Г(0> (3-4):
поскольку все Tp(i) — Гп (/).
С другой стороны, если продолжительности некритических
работ до оптимизации составляли величины то оптималь*
ные продолжительности могут быть только большими, чем
, т. е.
/to). (3-5):
Поскольку по условию мы не затрагиваем работ критиче-
ского пути, то для i£L кр остается 7(f) = Г (°) (Q.
Так как удешевление производится только за счет некрити-
ческих (первоначально) работ, то задача сводится к отыска-
нию минимума целевой функции
У — — by t и) =х
(ь i) & кр
= S [а ц — bц [T(j) Т(/)]}
при ограничениях
т(/)-т(О»^р) у
T(Q =7(0) (f) J
(3—6}
(3—71
37
'(первое для всех работ, не входящих в ; второе для всех
событий, входящих в Лкр).
Легко видеть, что это — типичная задача линейного про-
граммирования. То, что нам довольно быстро удалось ее сфор-
мулировать, объясняется в данном случае ясным смыслом це-
левой функции, с самого начала заданной условиями задачи.
Если допустимо, ради удешевления стоимости всех работ,
закончить «большую» работу за время, большее длины крити-
ческого пути, скажем, за время Т > Ткр) то в качестве пере-
менных могут быть использованы и сроки наступления собы-
тий, лежащих на критическом пути, так как критические рабо-
ты также могут быть увеличены по продолжительности, если
это экономически выгодно. В этом случае задача несколько
изменяется, так как нужно найти минимум целевой функции:
У = s [аи-Ьц [T(j)-7(f)] }, (3—8)^
(й /)
где суммирование распространено на все работы сетевого гра-
фика при ограничениях:
Т(/) -Т(0> для всех (й /); Т(0) - 0 и Т(п)<Т. (3-9)
В обоих рассмотренных примерах роль переменных играют
величины, на которые и наложены линейные ограничения.
Теперь обратимся к более сложному примеру — к задаче о
распределении ограниченных ресурсов, обеспечивающем вы-,
полнение большой работы в минимально возможный срок. За-
дача эта формулируется так.
Совокупность работ сетевого графика выполняется с за-
тратой k видов ресурсов. В простейшем случае количество
каждого ресурса в течение всего срока выполнения плана по-
стоянно, в более общем — различно в различные дни (недели
или месяцы), т. е. составляет функцию времени. Мы рассмот-
рим наиболее простой случай, когда все работы сетевого гра-
фика выполняются с помощью одного и того же ресурса (ска-
жем, рабочей силы) и ежедневное количество этого ресурса
(т. е. число рабочих) постоянно и равно величине с (в данном
случае, разумеется, с есть целое число). Задача состоит в*том,
чтобы так определить время начала каждой работы (в преде-
лах возможных сдвигов, допускаемых всей структурой сетевое
го графика), чтобы выполнить всю «большую» работу в ми-
нимально возможный срок. При этом продолжительность каж^
дой работы будет зависеть от того, какое количество ресурса
будет нами выделено для проведения этой работы. Так как,
вообще говоря, продолжительность выполнения данной рабр-
ты зависит от количества ее исполнителей нелинейно, то такдя
задача никак не может быть сведена к задаче линейного
граммирования. Поэтому нам придется ввести дополнительное
упрощение. А именно, нам придется допустить, что каХадя
работа должна выполняться строго определенным, noefthhi-
38
яым количеством рабочих. Математически это означает, что
ежедневное потребление данного ресурса, так называемая
интенсивность потребления ресурса, обозначаемая символом
:И‘ц ; для каждой работы есть величина постоянная. Таким
образом, каждая Иц = const для всех работ (I, j) нашего се-
тевого трафика. Назовем объемом работы (по данному виду
ресурса) произведение ее интенсивности на ее продолжитель-
ность; т. е; величину V ц= Иц 'tn . Теперь мы можем матема-
тически выразить то обстоятельство, что сетевой график не
может быть выполнен ранее, чем позволяет наличие данного
ресурса. Так как объем всех работ графика в наших обозначе-
ниях равен
V = человеко-дней, (3—10)’
1то величина
Трес = — VV(i дней :<3—11У
С
определяет минимально допустимую продолжительность всей
«большой» работы ввиду ограниченности ресурса. Но, с дру-
гой стороны, эта продолжительность не может быть меньше
длины критического пути нашего сетевого графика, т. е. вёли-
„чины lkp = 1°т2х- Таким образом, при оптимальном распределе-
нии ресурса (т. е. при оптимальном выборе допустимых мо-
ментов начала каждой работы) минимальная продолжитель-
ность всей «большой» работы не может быть меньше наиболь-
шей из этих двух оценок, т. е.
Tmin^max / Трее} м (3 12)
Задача линейного программирования будет состоять в том,
чтобы постараться возможно ближе приблизиться к этой ниж-
ней границе за счет единственно допустимой процедуры — вы-
бора разрешенных графиком сроков начала и окончания каж-
дой из работ, т. е. сроков наступления событий сетевого гра-
фика.
Прежде чем перейти к математической формулировке этой
задачи, необходимо будет ввести еще несколько определений
и обозначений. Мы видим, что даже такая сверхупрощенная
постановка задачи требует весьма значительной формализа-
ции. Это не случайно. Трудности, связанные с необходимостью
учета всех логических взаимосвязей между событиями и ра-
ботами, как мы уже говорили во введении, делают математи-
ческую формулировку (даже формулировку, не говоря уже о
решении!) оптимальных задач сетевого планирования делом
значительной сложности. Ограничимся этим замечанием и
продолжим наши рассуждения дальше.
. Назовем фронтом работ некоторую совокупность работ
графика, которые график позволяет веети одновременно. На<
Д9
пример, на графике рис. 3,6 работы (О,1) /(0,4) и (0,2) обра-*:
зуют фронт работ. Удобнее всего пояснить это понятие на так
называемой «линейной диаграмме». На рис. 5 построена ли-<
нейная диаграмма для графика рис. 3,6. По оси абсцисс на
фике, скажем — дни. По оси ординат размещены работы (в
«словарном порядке»), причем, как видно из диаграммы, на-
чало каждой работы (/, j) отнесено к наиболее раннему сроку
наступления события i, т. е. к 'I p(i). Тогда все работы, пересе-
кающие какую-либо вертикальную прямую, образуют то, что
мы назвали фронтом работ.
Из рис. 5 видно, что следующим за фронтом F\ работ (0,1)\
'(0,2), (0,4) будет фронт F2 работ (0,2), (0,4), (1,3), (1,3),
продолжительность которого по оси абсцисс составляет всего
одну единицу времецщ Следующим фронтом F3 будет фронт
40
работ (0,4), (1,3)> (1,5), (2,4) и (2,-8), который продолжается
также только одну единицу времени (поскольку заканчивает-
ся работа (0,4). Процесс рассмотрения различных фронтов
работ на рис. 5 читатель теперь может продолжить сам. Бук-
вами хтна диаграмме обозначены моменты, на которые при-
ходятся начала или концы работ.
Таким образом, каждый фронт работ на данной конкрет-
ной линейной диаграмме продолжается между двумя соседни-
ми значениями хт.
Так как интенсивности всех работ постоянны, если вести
работы -согласно диаграмме, т. е. начать их в моменты Tp(i),
«большая» работа будет закончена за время, определяемое в
точности длиной критического пути. Так обстояло бы дело,
если бы ресурс не был ограничен. Однако ограничение, нала-
гаемое на ресурс, может привести к тому, что для выполнения
некоторого фронта работ не хватит имеющегося ресурса и
тогда часть работ этого фронта неизбежно придется отодви-
гать на более поздние сроки, т. е. на нашей линейной диаграм-
ме вправо. Передвижка любой работы, не имеющей свобод-
ного резерва времени, повлечет передвижку других работ,
расположенных на графике правее данной. Только те работы,
которые имеют свободный резерв времени, например, работа
(0,4), могут быть сдвинуты на величину своего rc(i,j), не вы-
зывая других изменений на графике. Однако коль скоро мы
обязаны учитывать ограничение ресурса, возможно, что при-
дется сдвигать и такие работы, которые приведут к сдвигу да-
же конечного события 10, так как формула (3—12) может по-
требовать выбора Tmint превосходящего длину критического
пути.
Вышеприведенное рассуждение показывает, каким путем
мы имеем право оптимизировать наш график в данной зада-
че. Существуют алгоритмы подобной оптимизации, состоящие
в правилах передвижения «вправо», шаг за шагом работ каж-
дого данного фронта, которые перед этим каждый раз упоря-
дочивают в зависимости от оказывающихся у них в данный
момент резервов времени. Подобные «эвристические» алго-
ритмы дают часто неплохое приближение к оптимальному
решению, о чем мы расскажем в конце главы. Здесь мы по-
ставили перед собой цель — свести данную задачу к задаче
линейного программирования [4]. Для достижения этой цели
осталось уже сравнительно немного.
Суммарный ресурс, необходимый для выполнения работ
каждого фронта Fk , есть
S Ии , (3—13)
Этот ресурс — интенсивность фронта работ — сохраняется
постоянным между каждыми двумя «отмеченными» на нашей
4J
линейной диаграмме соседними моментами хт и xfn+i , А мо-
менты х т суть не что иное, как моменты фактического начала
или окончания всех работ нашего сетевого графика. Если не-
которые Иk > с, такой фронт работ неосуществим, так как для
него нехватает ресурса. Рассматривая данный сетевой график,
построим все возможные фронты работ, пусть это будут Л,
F2, ...» fw .
Например диаграмма на рис. 5 дает возможность постро-
ить двадцать четыре различных фронта работ. Однако этими
двадцатью четырьмя фронтами работ не исчерпываются все
варианты фронтов, разрешенные нашим сетевым графиком.;
Дело в том, что начала работ могут быть перемещены вправо
на диаграмме, если у работ имеются резервы времени. Про-
изведя все такие возможные перемещения и рассмотрев на
различных линейных диаграммах все получающиеся при этом
фронты работ, мы можем все различные фронты работ выпи-
сать в одну строку. Это и будет требуемая совокупность Fy
F2, Fx.
Часть из этих фронтов принципиально неосуществима из*
за того, что для одновременного проведения всех работ, вхо-
дящих в данный фронт, не хватает ресурса (скажем, рабочей
силы). Зная ресурс, выбросим из строки все неосуществимые
фронты, для которых FIk> с. Продолжительность каждого из
оставшихся М фронтов работ, т. е. расстояния между сосед-
ними точками Тт-7 и , обозначим через хт\ х т ~^т —
(т =1,2, ...,7И). (На рис. 5 имеем: То = О, щ = 4, х2 = 5, тз = 6,
Т4 = 10 И T. Д.).
Теперь мы должны выбрать такую совокупность фронтов
работ, чтобы, во-первых, в ней содержались целиком все ра-
боты нашего сетевого графика, чтобы, во-вторых, все эти
фронты были осуществимы с точки зрения наличия ресурса,
л чтобы, наконец, суммарная продолжительность всех фрон-
тов работ была минимально возможной, так как мы ищем
распределение ресурса, минимизирующее время выполнения
всей нашей большой работы. При этом необходимо, чтобы ни
в коем случае не была нарушена логическая очередность вы-
полнения работ, предписываемая нам исходным сетевым гра-
фиком. Труднее всего выполнить именно это дополнительное
условие. Для его выполнения допустим сначала, что на нашвхМ
графике с упорядоченной, правильной нумерацией событий
существует некоторый путь, проходящий через все события.
(В нашем примере, на графике рис. 3, б такого пути нет). Если
такой путь есть, то он обязательно имеет вид 0, 1, 2, 3, ..., п,
поскольку нумерация на графике, по предположению, пра-
вильная. В том случае, когда такой путь имеется, наша зада-
ча может быть теперь математически сформулирована сле-
дующим образом: необходимо найти совокупность значений
Xi, х2, Яз такую, что она минимизирует линейную форму
42
м
т=- 2 хп (3—14)
m = 1
при условии хт^>0 и при ограничениях
2 = (3-15):
(^/)
для всех работ (г, /) сетевого графика. Последнее ограниче-
ние означает, что все работы должны быть выполнены. Что
касается первого ограничения xm^ 0, то оно позволяет даже
не отбрасывать сначала неосуществимые фронты, а просто
сразу положить для них xk = 0, если > с. В написанной
выше сумме суммирование распространено на все фронты, со-
держащие данную работу (i, j), что и обозначено символом
Tm3
Полученная задача есть уже задача линейного программирования, по*
скольку ищется экстремум (в данном случае минимум) целевой линейной
функции (3—14) при линейных ограничениях.
Условие наличия пути, проходящего через все события графика, обес*
лечивает невозможность нарушения логической очередности работ при сум*
мировании продолжительности фронтов [4].
Однако сплошь и рядом на сетевом графике отсутствует путь, прохо*
дящий через все события. В этом случае приходится дополнительно строить
такой путь, вводя необходимые фиктивные работы. Однако при этом мо-
жет получиться ровно столько различных сетевых графиков, сколькими
способами можно добавить фиктивные работы для построения нужного
нам пути. Для оптимизации распределения ресурсов необходимо тогда
рассмотреть все полученные варианты таких графиков и выбрать тот, для
которого решение задачи линейного программирования дает минимальное
значение времени Т.
Рассмотренный пример показывает, насколько сложно сведение специ*
фических задач сетевого планирования к уже решенным проблемам мате*
матики.
Мы не будем рассматривать на нашем сетевом графике конкретные
расчеты, относящиеся к разобранным выше примерам. Это потребовало бы
большого объема выкладок, выходящего за рамки этой книжки. Подобные
примеры подробно разобраны в специальной литературе [4].
До сих пор мы рассматривали только такие задачи, в которых продол-
жительность каждой работы или вообще не могла быть изменена (пример
с распределением ограниченного ресурса), или могла быть только увеличена
(примеры с поисками минимальных по стоимости планов). Однако важней-
шей задачей сетевого планирования является нахождение оптимального
распределения ресурсов за счет удлинения сроков выполнения некритиче-
ских работ и сокращения сроков выполнения критических работ. Вообще с
этой точки зрения идеально сбалансированный график должен быть весь
ст начала до конца критичным, так как только в этом случае можно счи-
тать. что псе имевшиеся в нашем распоряжении возможности использова-
ны до конца. Правда, это даже теоретически не всегда возможно сделать,
так как, во-первых, ресурсы могут быть существенно ограничены, а, во-
вторых, ресурсы могут не быть взаимозаменяемыми. Последнее означает,
что различные работы потребляют различные ресурсы, которые невозмож-
но перебросить, таким образом, с одной работы на другую. Полный учет
Всех подобных зависимостей даже для сравнительно простых графиков
представляет задачи, на сегодняшний день не решенные.
>43
Обычно подходы к решению, подобных, более сложных задач, ищутся
на пути создания тех или иных алгоритмов, о чем мы уже говорили выше.
Хотя содержание настоящей главы составляли некоторые
задачи, сводимые к методу линейного программирования, мы
остановимся вкратце на одном таком алгоритме [4], предназ-
наченном для решения задачи об оптимальном распределении
ресурса при работах, проводимых с переменной интенсив-,
ностыо.
В отлцчие от задачи, рассмотренной выше, здесь считается,
что каждая работа имеет постоянный объем, а продолжитель-
ность ее обратно пропорциональна интенсивности, т. е.
t, = . (3—161
w ч
В частности, если перебросить часть ресурса с работы (Z!r
/1), не являющейся критической, на работу (/2, /2), лежащую
на критическом пути, то продолжительность некритической
работы возрастет (так как интенсивность ведения ее умень-
шится), а продолжительность критической работы сократится
(так как интенсивность ведения ее увеличится). Спрашивает-
ся: если при этих условиях задано ежедневное ограничение,
накладываемое на ресурс, то как распределить ресурс наи-
лучшим образом, обеспечив выполнение всей большой работы
в кратчайший допустимый срок?
Оказывается, что даже для Такой простой задачи до настоящего вре»
менП не существует точного решения. Алгоритм (один из возможных) со-
стоит в том, что в каждый данный момент, как упоминалось в начале этой
главы, работы данного фронта работ упорядочиваются в порядке возра-
стания имеющихся в них резервов времени. Ресурс выделяется в первую
очередь работам с минимальным резервом времени. Делается это за счеТ
работ с большими резервами до тех пор, пока, если количество ресурса
это позволяет, резервы времени не сравняются. Таким образом, идея ал-
горитма состоит в том, чтобы обеспечить в каждый данный момент, так
сказать, «равнокритичность» работ сетевого графика. Непосредственнее
распределение ресурсов по работам каждого фронта при наличии на гра-
фике нескольких тысяч работ представляет задачу, посильную только
ЭЦВМ. Отсутствие общего подхода к решению таких задач является серь-
езным тормозом в дальнейшем совершенствовании математических методов
планирования. Несомненно, что поиски новых удачных алгоритмов каж-
дый раз, в случае успеха, приносят ощутимую пользу Практике.
Но читатель уже, по-видимому, почувствовал, что отсутствие единого
теоретического подхода ко всему кругу оптимальных задач сетевого пла-
нирования никак не облегчает, а необычайно затрудняет решение основных
его вопросов.
- Глава 4
СЕТЕВЫЕ ГРАФИКИ КАК ОБЪЕКТ ТЕОРИИ
НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задачи, связанные с нахождением экстремумов целевой функции мно-
гих переменных, на которые наложена совокупность некоторых ограниче-
ний, называются задачами нелинейного программирования, если сама це-
левая функция (или некоторые из ограничений) нелинейны, т. е. не могут
быть выражены через линейные комбинации переменных с постоянными
коэффициентами. В общей постановке все задачи поисков оптимальных
планов на основе сетевых графиков по сути своей нелинейны. Рассмотрен-
ные в предыдущей главе примеры приводились к линейному виду только
ценой весьма серьезных ограничений, налагаемых на свойства работ гра-
фика.
В настоящей главе мы попытаемся сформулировать экстре-
мальные задачи сетевого планирования в самом общем виде.
Пусть график содержит (n + 1) событие и Af работ, при-
чем, как следует из теории графов, /V . Каждая ра-
бота для своего выполнения требует затраты различных ре,-
сурсов. Пусть все работы графика в своей совокупности могут
быть выполнены k видами различных ресурсов
и, г2, rk, (4—1)'
причем известен объем каждой работы по каждому ресурсу.
В общем случае такой объем работы может быть изображен
в виде вектора с k компонентами, каждая из которых пред-
ставляет объем данной работы по данному виду ресурса. Этот
«вектор» объема работы можно записать в виде:
К/ = { у.(2) ...,Ур}, (4—2)-
где У™ — количество m-го ресурса, требуемое для выполне-
ния работы (i, j).
При этом следует иметь в виду два обстоятельства. Во-пер-
вых, не каждая работа требует всех видов ресурсов. Таким
образом, некоторые величины V™ могут равняться нулю. Во-
вторых, в большинстве . случаев различные Vtj , т. е.
различные компоненты вектора Уц не независимы, а, наобо-
рот, связаны друг с другом, так как, например, количество
человеко-часов, идущее на обработку какой-либо детали, свя-
зано с количеством затрачиваемых станко-часов и с количе-
ством потребляемой электроэнергии. Поэтому различные ком-
поненты подобного вектора могут быть, как правило, выраже-
ны через небольшое их число, иногда даже через какой-нибудь
один из них. Это обстоятельство означает, что на компоненты
каждого вектора К/ могут быть наложены некоторые огра-
45
<pjs> (V’.V(V)=0 J>
ничения, которые в оощем виде можно записать как иекото«
рые соотношения вида *
(4-3)
выписываемые отдельно для каждой работы. Разумеется^ если
эти соотношения можно разрешить как уравнения относи-
тельно каждого компонента У% 9 то можно выразить часть
компонентов через другие, которые окажутся независимыми.:
Выбор зависимых и независимых компонентов, разумеется, с
математической точки зрения произволен, а с экономической
определяется теми ресурсами, которые в данной работе мо-
гут быть переменными величинами. Скажем, если мы оптими-
зируем распределение станко-часов, то остальные ресурсы—
скажем, человеко-часы и электроэнергию — следует выражать
через станко-часы, а не наоборот.
Далее, продолжительность выполнения каждой работы
есть некоторая функция от количества имеющихся ресурсов,
т. е. от интенсивности ее выполнения. Достаточно при этом
рассматривать только независимые ресурсы, через которые
выражены все компоненты векторов Уц д Для каждой работы
имеем:
ч- -fii ...У (4—4).
с учетом соотношений (4—3). Если в течение всей работы
(i, j) интенсивности потребления ресурсов были постоянны, то
, (4-5);
Ит]
if
т. е. продолжительность работы определяется максимальной
величиной из отношений ее объемов к соответствующей интен-
сивности. Если же интенсивности переменны — то более -слож*
пым образом.
Поскольку хотя бы некоторые виды ресурсов ограничены,
то имеют место следующие (на этот раз линейные) ограничен
ния на величины :
•2 H^Rm 5 /п=1, 2, ,.,,kr ;(4-6)’
(й j)
где суммирование распространяется на все работы сетевого
/рафика, a Rm— верхняя граница наличия т-го ресурса. В об-
щем случае эти границы в различные сроки различны, а пото*
му в каждый момент времени t мы имеем т условий:
SH7 (t)^Rm (t)s (4-7);
'<i, i) ”
При всем этом важнейшими дополнительными условиями
являются условия, налагаемые самим сетевым графиком, т. о*
43
t a = max
логическом очередностью выполнения всех его работ. Эти ус-
ловия сводятся к одному, нам уже известному: ни одна рабо*
та с индексом (4 /) не может быть начата ранее, чем будут
закончены все работы, имеющие «Ь> вторым индексом, т. е,
все работы вида (a, i).
Далее, в каждой конкретной задаче следует ввести в рас*
смотрение целевую функцию, экстремум которой мы должны
обеспечить. Это может быть общее время Т, проведения всей
«большой» работы, определяемое как * Это может быть
стоимость всех затраченных ресурсов, т. е. стоимость всей
«большой» работы при фиксированной продолжительности ее
выполнения. Это может быть количество какого-либо дефи-,
цитного ресурса, которое надо минимизировать при постоян-
ном 10^ах и вне зависимости от стоимости работ. Наконец, это
может быть нахождение так называемой «параметрической
кривой» — кривой «время — стоимость», в которой каждому,,
заранее задаваемому значению продолжительности всей ра-
боты соответствует минимальная стоимость работ при задан-,
ной продолжительности..
Каждая из этих и подобных им задач оптимизации должна решаться
с учетом всех вышеуказанных зависимостей и ограничений. Решение любой
из этих задач в настоящее время в общем виде не только не получено, но
и не найдены пути к его осуществлению. Все полученные до сих пор реше-
ния относятся к крайне специальным частным случаям, примеры которых
были разобраны в предыдущей главе. Правда, они не ограничиваются слу-
чаями, сводящимися к линейному программированию, однако они все же
составляют очень малую часть задач, решения которых настоятельно тре-
бует практика.
Надо сказать, что при анализе сравнительно небольших сетевых гра*
фиков даже «интуитивное» распределение ресурсов по работам в зависи*
мости о г резервов времени работ уже дает заметную экономию времени*
сил и средств. В этом — несомненное достоинство сетевого планирования.
Математическое «решение» более сложных графиков на ЭЦВМ в первую
очередь также дает «иерархию» работ по их резервам времени, позволяю-
щую руководителям принимать обоснованные решения при распределении
ресурсов.
Нетрудно, однако, заметить, что получение решений задач оптимиза-
ции принесет дальнейшие экономические выгоды, позволит гораздо более
экономно расходовать ресурсы и в то же время значительно сокращать
сроки выполнения больших и сложных работ.
В настоящее время усиленно ищутся интуитивные, как говорят —-
«эвристические», подходы к решению подобных задач. Результатом таких
поисков являются различные алгоритмы для решения некоторых упрощен-
ных проблем оптимизации. Алгоритмы эти, как правило, не дают оптималь-
ных решений, но дают решения, достаточно близкие к ним. Впрочем, за-
частую теоретически пока невозможно установить, насколько именно они
близки к оптимальным, так как для очень многих задач оптимальные зна-
чения просто неизвестны.
Мы уже говорили во второй главе, что при анализе сетевых графиков
считается, что продолжительность каждой работы не зависит от момента
ее начала и что в действительности это не всегда так. Отметим, что даль-
нейшее усложнение проблем путем введения подобных зависимостей вида
пока не представляется целесообразным хотя бы по той при*
47
чине, что и без такого уточнения мы еще не умеем решать очень многих
задач оптимального планирования.
Отрасль математики, к которой близки эти проблемы — нелинейное
(а также динамическое) программирование, сейчас находится в процессе
своего роста. Несомненно, что одержанные здесь успехи принесут сразу же
ощутимую пользу проблемам сетевого планирования, о которых мы крат-
ко рассказали в этой главе.
ЗАКЛЮЧЕНИЕ
В настоящей книге мы рассмотрели некоторые вопросы
применения математики в задачах сетевого планирования.
Как видно из сказанного, сетевое планирование затраги-
вает три раздела математики — теорию графов, теорию ве-
роятностей (с математической статистикой) и теории опти-
мальных задач линейного и нелинейного программирования.
Однако надо сказать, что разрабатываемые в настоящее
время алгоритмы решения различных задач сетевого плани-
рования, строго говоря, ни к одной из существовавших ранее
ветвей математики отнести нельзя. Это по существу новый
раздел прикладной математики, который так и следует на-
звать «математика сетевого планирования» и который являет-
ся одним из направлений «математической экономики».
В настоящей книге мы не касались вопросов обработки се-
тевых графиков на электронных цифровых вычислительных
машинах. Составление алгоритмов и программ машинной об-
работки сетевых графиков, представляет сейчас очень быстро
развивающуюся область прикладной вычислительной матема-
тики. К сожалению, по этим вопросам пока нет обзорной ли-
тературы.
Наша скромная цель при написании этой книжки состояла
лишь в том, чтобы привлечь внимание читателей к важным и
сложным вопросам, стоящим перед математикой сетевого пла-
нирования. Если читатель почувствовал, насколько важно для
практики научиться решать подобного рода задачи, мы счи-
таем нашу цель достигнутой.
9 коп.
Индекс
70096
Вниманию читателей!
Принимается подписка на научно-популярные брошюры изда-
тельства «Знание» по серии «Естествознание и религия».
Задача серии — популярно рассказать о том, как достижения
астрофизики, химии, медицины, астробиологии, археологии и других
наук опровергают религиозные представления о мире.
Подписчики получат во втором полугодии 1967 года следующие
брошюры:
Ангарская М. Н., химик и писатель. Мир невидимых.
Балабанов Е. М., доктор физико-математических наук.
В глубь атома.
М е л ю х и н С. Г., доктор философских наук. Источники раз-
вития материи.
Шишина Ю. Г., врач. Рассказ о крови.
Л ич ко А. Е., доктор медицинских наук. Глазами психиатра.
Подписная цена на серию:
на полугодие — 54 коп.
на квартал — 27 коп.
В каталоге «Союзпечати» серия «Естествознание и религия» по-
мешена в разделе «Научно-популярная литература» под рубрикой
«Брошюры издательства «Знание».