Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 54
Текст из файла (страница 54)
На каж- дой дуге аугментального пути потока (1, 2) — (2, 4) — (4, 5) про- исходит увеличение потока на 1. Итерация 2 12, 11 151 Дуга оу Гу -з -г -з 1о1 1,о) (1, 2) О (2, 3) О (3, 5) О 1121 12, 31 12,21 191 Поскольку пометить узел 5 не оказалось возможным, получаем непрорыв: В = ((3, 5), (2, 4), (1, 4)), В=в, ь =со. Следовательно, ~=3. Как ге, так и 14 должны уменьшаться на величину ~=3, т.
е. (4=9, 14=12 Проверка возможности сокращения продолжительности проекта. После задания у!)=011 для всех дуг сети невозможно существование пути со всеми Г;;=О. Поэтому условие Т =.Т=15 является возможным. Итерация 1 Глава 4 Итерация 3 [г, !1 [5! дуга ов ьз (1,2) Π— 3 (г, з) о -2 (з И о -з [!2! !2, 31 [о[ [,о1 [2,2! 191 Получен прорыв при ()в=2. На каждой дуге аугментального пути потока (1, 2) †(2, 3) †(3, 5) происходит увеличение потока на 2. Итерация 4 [5! Дуга Св 6„ (1,2) 0 -3 (1, 3) -6 -8 (1,4) -3 -5 5 11'! [о) [,о! [91 [ !1 111 '(.„ о -3 [01 [-, о! дуга (4 (1, г) з (2, 3) О (3, 5) О [2, 3! 19! [3,21 [61 Поскольку пометить узел 5 невозможно, результатом является непрорыв: В ((1,2), (1,3), (1,4)), ь,=З, В=о, ь =со. Следовательно, (.=3 и (в=2, 1в=6, 14=6 и 18=9.
Итерация 5 Методы уяравлеиия яроектолш результатом этой итерации является прорыв при де=2. На каж- дой дуге аугментального пути потока (1, 2) — (2, 3) — (3, 5) про- исходит увеличение потока на 2. Итерация 6 [, 11 [21 2,1 Дуга (;, [2, 4! [9! [1, 2! [6[ Получен прорыв при де=2. На каждой дуге аугментального пути потока (1, 4) †(4, 5) происходит увеличение потока на 2.
Итерация 7 [сю, 1! [2! Дуга Г; [9! [1, 2! [6! ' Поскольку пометить узел 5 невозможно, получаем нецрорыв1 В = ((1, 4), (2, 4), (3, 5)), ~! = 1, В=о, ( =со. Таблица 4.17. Оптимальное решение (!. 2) З (". З! О (3. 5) О (!. 4) О (4, 5) О (1, 2] 3 (2, 3) О (3, 5) О (2, 4) 3 (1, 4) О Ее о — 2 -з -2 О [ [О! 2о о -2 -з -! -2 Р,О! [О! 336 Глава 4 СЛЕдОВатЕЛЬНО, Ь=! Н 14 — — б, 14 =8. Итерацня 8 )] 121 !.в о -2 0 1 о 16! Дуга )74 з <2,З) О (3, 5) ! (2 4) 4 (4, 5) О 1,41 !в) !), 21 !61 Получен прорыв прн да=ос.
Следовательно, это оптимальное решение. Результаты приводятся в табл. 4.17. Соответствующая кривая зависимости между затратами н продолжнтельностыо проекта представлена на рнс. 4.22. 20 ь. ф 15 10 ж ж ~в Время, сут Рис. 4.22. Кривая зависимости продолжительности от затрат.
7)) п)ах!0, а)! — Ы бы = п)ах 10, Г)) — а))!. Продолжительности работ, соответствующие каждой точке излома кривой зависимости между затратами н продолжительностью проекта, изображенной на рнс. 4.22, можно получить с помощью условий дополняющей нежесткостн. Поскольку значення потока ~п н параметра ан известны на каждой итерации алгоритма, можно вычислить значения уп н бп с помощью соотношений ззт Методы управлении проектами Таблица 4.!д.
Сводка результатов Т= 12 Т= 15 Т4 9 Т вЂ” — 8 Дуга (т',1) Лт уи бо уи Лт уи би уи уи уо бгт уи Лгу ут бзв утг 5' 3 б 4 ,1» 3 3 5 О 2 2 5 О 2 О 2 О 3 О 2 О 2 О О 5' О 2 О 4 1 О 4 4 ! О 1 О О 3' 1 О О 4 О О 2* 4 О О 3 оо О 3 ! оо О 3 О О О 2 О О 2 О 2 3 О 1 О О 2 2 О 1 оо О 1 2 О 5 О 2 О 3 О 2 О б О 5 О 4 1 О О 7» О 4 О 3 1 оо О 3 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 5) (4, 5) 2 3 б 4 4' 3» 3 Поскольку как т;,, так и зе равны нулю, условия дополнительности указьюают лищь, что продолжительность работы лежит в некотором интервале.
В етой задаче устанавливается максимально допустимая продолжительность работы, твк как модель имеет целью минимизировать общую стоимость проекта ° В силу условий дополняющей нежесткости задачи линейного программирования при Тп)0 имеем уп (у(ь а при б»т)0 имеем уп=Ап. В противном случае Епт уп(У(ь Результаты численного решения рассматриваемой задачи приводятся в табл.
4.18. 4.12.2. ПРИМЕНЕНИЕ ПРОЦЕДУР УСТАНОВЛЕНИЯ КОМПРОМИССНОГО СООТНОШЕНИЯ МЕЖДУ ЗАТРАТАМИ И ПРОДОЛЖИТЕЛЬНОСТЬЮ ПРОЕКТА Примеры основных процедур установления компромиссного соотношения между затратами и продолжительностью проекта даются в основополагающих статьях Келли и Уолкера 121 — 231 и Фалкерсона 1151. Процедура, описанная в этих статьях, основана на линейном программировании и осуществляется с помощью потокового алгоритма в сети, для которого уже давно имеются машинные программы, хранящиеся в библиотеке фирмы 1ВМ 1111.
Такая программа автоматически выдает кривую значений продолжительности проекта при минимальных затратах и подробные данные о сроках начала и окончания работ, связанные с каждой точкой кривой. Одним из преимуществ этой стандартной программы вычисления потока в сети является то, что при использовании в качестве исходных данных целочисленных продолжительностей работ точки излома кривой стоимости (возможные продолжительности проекта) также являются целыми числами.
Однако необходимы допущения о линейных соотношениях между временем и затратами. Другой подход к этой проблеме при иных допущениях о соотношениях между временем и затратами изложен в руковод- 22 — 1684 Глава 4 стве Нациойального управления по аэронавтике и исследованию космического пространства (НАСА) и министерства обороны США по применению системы ПЕРТ-СТОИМОСТЬ [32]. Еще один полезный вариант основной процедуры разработал Фондал [14]. Схема вычислений, выполняемых вручную, позволяет сокращать и увеличивать продолжительность проекта при различных допущениях о соотношении между временем и затратами с целью определить минимальные затраты при требуемой продолжительности проекта.
Большинство методов анали. за соотношений между временем и затратами, разработанных до 1966 г., подробно рассматривается в статье [11]. К числу сравнительно новых процедур вывода соотношений между временем и затратами, разработанных после 1966 г., относится простой метод Сименса [42], который может применяться вручную или с использованием машинной программы; он позволяет получить оптимальные результаты при линейных соотношениях и близкие к оптимальным в случае нелинейных соотношений.
Бенсон и Сьюолл [2] описывают имеющуюся в продаже машинную программу для анализа соотношений между затратами и продолжительностью проекта в сетях, содержащих до 40 тыс. работ. Холландер [17] описывает еще одну большую программу, в которой могут вводиться различные допущения о соотношениях между затратами и продолжительностью работы. Модер и Филлипс [29] дают четкое изложение и сравнение процедур анализа соотношений между затратами и временем и приводят список нескольких машинных программ, предназначенных для анализа соотношений между затратами и временем. Важно заметить, что в процедурах анализа соотношений между затратами и временем ограничения на наличие ресурсов обычно не рассматриваются в явном виде. Ни одна из упоминавшихся здесь процедур не позволяет автоматически получить календарные графики работ при минимальных затратах, удовлетворяющие заданным ограничениям на наличие таких ресурсов, как денежные средства, рабочая сила и оборудование.
Например, хотя программа Бенсона и Сьюолла во многих отношениях является исключительно сложной, она не позволяет автоматически планировать сроки выпуска продукции. Программа выдает отчеты, показывающие, что для отдельных работ нарушаются ограничения на затраты или время, но задача внесения подробных изменений, необходимых для соблюдения ограничений, налагаемых на проект, ложится на человека. Необходимо также заметить, что процедуры анализа компромиссных соотношений между затратами и временем не находят широкого применения на практике.
Основной причиной этого являются большой объем и сложность исходных данных, необходимых для анализа, а также типичная неопределенность 339 Метода управления проектами этих данных. Обычно сбор подробной информации о соотношении между затратами и продолжительностью проекта, содержащего, например, сотни работ, является непростой задачей. Таким образом, хотя информация, получаемая с помощью процедур анализа соотношений между затратами и временем, потенциально очень полезна в некоторых ситуациях, в целом сегодня такие процедуры занимают сравнительно скромное место в общей иерархии сетевых методов распределения ресурсов. 4ЛЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
