Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 53
Текст из файла (страница 53)
Случай 2: г»=а» и у»=0. Случай 3: а»(~»(со и Х»=0. Эти условия играют важную роль при выводе потокового алгоритма в сетях, который будет рассмотрен далее. Методат ри аааанаа проектами Алгоритм. Процедура, рассматриваемая в данном разделе, была разработана Фалкерсоном 1161, и ее можно рассматривать как двойственный метод, так как ее вывод основан на структуре двойственной задачи и условиях дополняющей нежесткости задач линейного программирования. Прежде чем приступать к описанию алгоритма, изложим некоторые простые, но полезные соображения. Наиболее типичной интерпретацией дуги в сети с потоками является представление ее в виде канала или трубы, по которой Веркнии отсек с огРаниченной пропускнои . спосоеностью- Нигкнии отсек с неограниченной пропускной спосоеностью Рис. 4Л7. Интерпретация дуги как трубопровода с двумя отсеками.
транспортируется определенный вид товара. Несколько более сложной, но удобной интерпретацией дуги в рамках рассматриваемого алгоритма является представление ее в виде трубопровода с двумя отсеками, как показано на рис. 4.17. Верхний отсек трубопровода, изображенного на рис. 4.17, имеет ограниченную алропускную способность, а нижний отсек— неограниченную пропускную способность. При такой интерпретации предполагается, что поток проходит через нижний отсек только в том случае, когда превышается пропускная способность верхнего отсека.
В противном случае нижний отсек не используется. С помощью графического представления функций (рис. 4.!6) можно убедиться, что случай 1 наблюдается, когда в верхнем отсеке еще отсутствует насыщение; случай 2 появляется, когда верхний отсек полностью заполнен; случай 3 тхиеет место, когда поток поступает в нижний отсек, пропускная способность которого, как уже говорилось выше, считается бесконечной. Таким образом, абсолютное значение тангенса угла наклона линии зависимости между затратами и продолжительностью данной работы можно интерпретировать как пропускную способность верхнего отсека дуги, изображающей эту работу на сетевом графике. Рассматриваемый алгоритм может использоваться для по- строения кривой зависимости между затратами и продолжи- 328 Глава 4 тельностью проекта.
В этом случае алгоритм начинается с максимальной продолжительности проекта, и на каждом шаге оцениваются дополнительные затраты, с помощью которых достигается некоторое сокращение продолжительности проекта. Пример такой кривой дан на рис. 4.18. Алгоритм состоит из трех основных шагов. Первым шагом является проверка возможности сокращения заданной продолжительности проекта. На втором шаге осуществляется процедура расстановки пометок для модификации потоков в сети, сооти Ф о а и я й $ 6 Ф а а о Продопжитепьиость проекта Рис. 4Л8. Кривая зависимости продолжи. тельиости проекта от затрат.
ветствующих двойственной задаче. На третьем шаге выполняется сокращение продолжительности проекта, если на втором шаге алгоритма достигается непрорыв. Блок-схема алгоритма изображена на рис. 4.19. Начало вычислений. Если продолжительность проекта необходимо сократить относительно максимального значения, полагаем Т=1„, где 1п можно получить рекуррентным способом с помощью следующего прямого соотношения: 1~=шах[1;+Ум), 1=2,3,...,п и 1„=0. Кроме того, все потоки могут быть, равны нулю или какому-либо другому значению, удовлетворяющему условиям сохранения потока.
Шаг 1. Проверка возможности сокращения продолжительности проекта. Полагаем уц=Уц. Если от узла ! до узла п сущест" вует такой путь Р, что Т.ц=О для каждой дуги (1, /) пути Р, то это означает, что до=1,ц для каждой дуги (1, /) данного пути. Однако в нетривиальных случаях Уп~Ь» и поэтому условие Т(Т невозможно. Если путь Р не существует, то продолжительность проекта Т .Т возможна. Чтобы идентифицировать узлы пути Р, их можно пометить в соответствии со следующим 329 Методы управления проектами Задание нечапьньж значении тк ГЕ и 7 Проверка возможности сокращения продопжи.
тепьности проекта Т Нет Т ( Т 1 Да Останов Рас. 4.19. Блок-схема алгоритма расчета потока сети. правилом: помечаем 1ьй узел из Ого узла через [со, 11, если дуга (1, /) находится на пути Р. В данной процедуре узел 1 имеет по- стоянную пометку '1оо, 01. Шаг 2. Процедура расстановки пометок. Разделим обсуждение процедуры расстановки пометок на две части: а) увеличение потока вдоль прямых дуг и б) уменьшение потока вдоль обратных дуг. а) Прямые дуги. Если дуга (1,1) относится к случаю 1, то для достижения оптимальности необходимо выполнение условия (1н=О. Таким образом, поток 1н можно увеличить на миннмаль- ззо Глава 4 ное значение, лежащее между величиной потока в 1-м узле и величиной, необходимой для достижения значения ац, которое отражает условия на поток для случая 2.
Таким образом, )чму узлу можно дать пометку [дь 1], где д;=ш)п [уц ац — )ц]. Если дуга (1, 1) относится к случаю 3, то поток гц можно увеличить на любую величину, так как в этом случае пропускная способность дуги становится неограниченной. Поэтому весь поток, имеющийся в 1-м узле, можно переместить в )ьй узел. Это означает, что /-й узел может получить пометку [дь 1], где у1 =уь б) Обратные дуги. Если дуга (1, 1) относится к случаю 1, то после любого сокращения потока )ц необходимым условием оптимальности остается Уц=О. Это означает, что из 1-го узла в )ьй узел можно направить встречный поток, величина которого ограннчмвается потоком, имеющимся в 1-м узле. Назначение встречного потока состоит в том, чтобы уменьшить величину потока 1ц.
Поэтому для 1-го узла из узла 1' можно задать пометку [уц 1], где д;=ппп[уь Ь]. Если дуга (1, /) относится к случаю 3, то необходимым условием оптимальности остается Тц=О, если поток 1ц сокращается таким образом, что дуга (1, 1) не переходит ~в случай 1. Следовательно, для дуги должны сохраняться условия случая 3 или обеспечиваться переход к случаю 2. Тогда для 1-го узла можно задать пометку [уц Д из /-го узла, где д; ш)п[дь )ц †]. Шаг 3. Процедура изменения момента наступления события.
Этот этап выполняется только в том случае, когда происходит непрорыв, т. е. когда невозможно задать пометку для и-го узла. Пусть Š— множество помеченных узлов, а Š— множество непомеченных узлов. Назначение этого шага алгоритма состоит в том, чтобы ускорить время наступления каждого события множества Е. Пусть 1енЕ и уяЕ. Если дуга (1, у) удовлетворяет хотя бы одному из условий Тц(0 н У;~(0, то время наступления )что события может быть сокращено, чтобы выполнялось это условие для уц, которое является необходимым для достижения оптимальности.
Чтобы показать это, введем следующие определения: В = ((1, у) ~ (ЕЕ, )ЕЕ, Л;~ ( О или Уц ( 0), ~,=т1п(Уц=Уц+1,— 14 (0]. в Условие уц=уц+1; — 1; можно переписать в виде О=уц+1;— — (1~)+уц), откуда следует, что 1~ можно уменьшить на — уц (заметим, что уц(0), чтобы удовлетворялось условие, согласно зз1 Метода управления проектами которому новое значение уш вычисленное при новом значении (ь ра~вио нулю, что требуется для обеспечения оптимальности. Аналогично если дуга (1, 1) удовлетворяет хотя бы одному из условий Ер)0 н Уп)0, то время наступления /-го события может быть сокращено, чтобы выполнялось условие для уд, коРис. 4.20.
Сетевая модель для примера. торое необходимо для достижения оптимальности. Как и ранее, вводим следующие определения: В=((/,1)((ЕЕ, )ЕЕ, Е~т) О илн У~т> ьа=т(п!рн — — от+1,— $, 0]. в Условие ттн=уп+тт — г; можно переписать в виде О=уп+ (1;— — уп) — ть откуда следует, что 1~ можно сократить на уд (заметим, что уп)0), чтобы выполнялось условие, согласно которому новое значение у;;, вычисленное при новом значении Гь было равно нулю, что требуется для обеспечения оптимальности. Если произ~водится такое же сокращение времени наступления каждого )что события множества Е, то может.
использоваться следующая процедура. 1. Находим ьь 2. Находим ьа. 3. Находим ь=ш)п1ьь ьа). 4. Уменьшаем 1т на ~ для каждого узла 1~Е. После изменения всех значений г~ начинаем про'едуру расстановки пометок (шаг 2), беря во всех случаях в качестве пометки [оо, 11 для того, чтобы сократить объем вычислений. Пример оптимального соотношения между временем и затратамн. Построим кривую для соотношения между затратами и продолжительностью проекта, представленного на рнс. 4.20.
Дополнительные данные, необходимые для решения этой задачи, приводятся в табл. 4.15. Глава 4 Таблица 4.15. Данные о сроках и затратах ! дуга Гуо а„. Таблица 4.1б. Сроки наступления начального события Каждая дуГа ПОМЕЧаЕтСя ЧЕтЫрЬМя ЧИСЛаМИ 11.гу, !угу, а;;, Тг11.
Момент наступления каждого события обозначается 11г1 и записывается возле 1-го узла. Все начальные значения потока при- !51 5 [151 19! Рис. 4.21. Исходные решения задачи. нимаются равными нулю. Начальные значения гг можно вычислить, как показано в табл. 4.16. Начальные решения показаны на рис. 4.21. Метода управления проектами 13, 11 151 Дуга ()» Т„ -3 4 О 1о) (,О1 (1,2) О (2, 4) О. (4,5) О 11, 41 1! 51 191 Результатом этой итерации является прорыв при Оп=1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
