Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 52
Текст из файла (страница 52)
Сетевая модель работ для задачи сокравгеиия сроков за счет увеличения затрат, ного значения приращения зат1рат для каждой работы (например, затраты на выполнение работы за 7 сут вместо 8 равны 400 долл. +80 долл.=480 долл.). Если заданы «нормальные» продолжительности всех работ, то продолжительность проекта составляет 22 сут, что определяется с помощью критического пути, состоящего из работ (О, 1), (1, 2), (2, 4), (4, 5) на рис.
4.11. Результаты вычислений приводятся в табл. 4.13. Как показано на,рис. 4.12, соответствующая стоимость выполнения проекта составляет 3050 долл. Заметим, что принятие неправильного решения, согласно которому ускоряется выполнение всех работ, не лежащих на критическом пути, ие приводит к сокращению продолжительности проекта. Между этими верхним и нижним значениями затрат при продолжительности проекта 22 сут возможны несколько других значений в зависимости от числа некритических работ, срок ~выполнения которых сокращается. Таблица 4.18. Анализ критического вутн 220 Глава 4 Точка выполнения всех работ в сжатые сроки , кРоме лежащик ическом пути, я в сжатые сроки 40 с о м к и о х о 35 ка выполнения свх работ в мальные сроки 3000 17 1З 19 20 21 22 Продолжительность, сут Рис. 4.12.
Зависимость между продолжительностью проекта и прямыми за- тратами. с с о с л х о. ельность имальнык тах Продолжительность проекта Рис. 4.13. Определение продолжительности проекта прн минимальных общих затратах. Если устанавливаются сокращенные сроки выполнения всех работ, то продолжительность осуществления проекта можно сократить до !7 сут, но, как следует из рис. 4.12 1верхняя левая точка), общие затраты при этом возрастают до 4280 долл. Однако продолжительность осуществления проекта, равную 17 сут, можно достигнуть при меньших затратах без ненужного уско- 321 Методы иравлвния ароектаии рения отдельных работ.
Так, работа 10, 2) может продолжаться не 6, а 7 единиц времени, работа (1,4) — не 7, а 8 единиц времени, а работа 12, 3) — 4, а не 1 единицу времени. Если все остальные работы выполняются в ускоренном темпе, то стоимость выполнения проекта за 17 сут снижается до 3520 долл. Мсо 4900 о К 4ООО зыю 2000 17 1В 19 20 21 22 Плололжительиость, сут Рис. 4.14.
Оптимальное сокращение сроков за счет прямых и косвенных затрат. Как легко установить путем эксперимента, это самая низкая стоимость осущесттвления проекта за 17 сут. Как показано на рис. 4.12, продолжительность проекта может иметь некоторое промежуточное значение, лежащее между 17 и 22 сут. Для каждой продолжительности проекта существует некоторый интервал возможных значений стоимости, зависящих от продолжительности отдельных работ и оттого, производится ли ненужное ускорение сроков их осуществления. На рис.
4.!2 показаны кривые максимальных н минимальных затрат и область возможных затрат при каждой продолжительности проекта, лежащая между этими кривыми. В этом простом примере кривую минимальных прямых затрат легко определить методом проб и ошибок. Однако в более реальных ситуациях, когда имеются десятки или даже сотни 21 †16 322 Глава 4 Таблица 4.14.
Изменение затрат нри сокращении сроков работ работ, построение кривой методом проб и ошибок становится исключительно утомительным занятием, либо оно вообще невозможно. Поэтому были разработаны .различные систематические методы вычислений, в том числе методы математического программирования, позволяющие быстро определить кривую минимальных затрат при любом возможном значении продолжительности проекта. Некоторые из этих стандартных методов предназначены для использования в тех случаях, когда компро-. миссные соотношения между временем и затратами являются нелинейными; многие из ннх позволяют получить кривую минимальных общих затрат (равных сумме прямых и косвенных затрат), что показано на рнс.
4.13. Чтобы проиллюстрировать влияние ускорения работ на общие затраты, рассмотрим снова предыдущий пример с постоянными косвенными затратами, равными 130 долл./сут. В данном случае кривая, изображенная на рис. 4.13, представлена на рис. 4.14. Результаты вычислений при~водятся в табл. 4.14. 4.12.1. ПОТОКОВЫЙ АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ МЕТОД КРИТИЧЕСКОГО ПУТИ, В СЕТИ С ЗАВИСИМОСТЬЮ МЕЖДУ ВРЕМЕНЕМ И ЗАТРАТАМИ Продолжительность любой работы проекта можно регулировать количеством ресурсов, выделяемых для выполнения работы. В общем случае можно предположить, что руководители проекта могут оценивать продолжительность работ как функцию суммы денежных средств, затраченных на каждую из ннх.
Поэтому при таком допущейии можно построить математическую модель, предназначенную для минимизации общей стоимости проекта. Модель позволяет найти оптимальные значения сроков наступления событий и продолжительностей работ при заданных продолжительности проекта, отношениях предшество- 323 Метром уп аелениа проектами при условии, что 1,.— !!+У„< б — ! +1„=Т у!! ((!г! Уц~ ьг! для всех (1, |) в А, для всех (1, !) в А, для всех (|,!) в А.
Эта модель эквивалентна рассматриваемой ниже задаче линейного программирования с максимизацией функции цели. 21' вания, верхних и нижних пределах продолжительности каждой работы. Для формулировки задачи линейного программирования и вывода процедуры решения принимаем следуюшие обозначения: уц — продолжительность работы (|, 1); 1| — момент наступления 1-го события; сц — стоимость работы (|, /) как функция продолжительности работы, т. е. сц = ! (Уц); йл! — нижний предел продолжительности рабоТЬ| (| 1) ! (!ц ВЕРХ ! Тангенс угпа наклона ний предел продолжитель- прямоа равен -а;1 ности работы (|, !); Т— заданная продолжительность проекта. | В рассматриваемом случае предполагается сущест- в| и,, У!! вованне линейной зависи- МОСТИ продолжИТельноСТИ р с 4 13 Л ис.
4.16. Линейная зависимость между От затРат, т е. сп=!(УЦ) = затратами и продолжительностью. = Ь||.— ацуц, где 1.ц<уц< <1!ц. Это линейное соотношение показано на рис. 4.15. Нижний предел обычно соответствует более быстрому выполнению работы, а в качестве верхнего предела принимается «нормальная» продолжительность. При заданной продолжительности проекта и линейном соотношении между затратами и продолжительностью для проекта с представлением сети в виде 6= (Ь(, А) требуется знать, какие работы множества А необходимо ускорить, а для каких сохранить нормальную продолжительность. Как показано ниже, рассматриваемую задачу можно сформулировать как задачу линейного программирования. Предполагается, что множество узлов р) можно определить как (е= (1, 2, ..., и), где узел 1 обозначает начало проекта, а узел л — окончание проекта.
Мин нмизнровать ~~~~(܄— а, !Уы). 1|, ||ее 324 Глава 4 Ограничения на неотрнцательность /; и уи не заданы в модели в явном виде, а это означает, что все ограничения соответствующей двойственной задачи линейного программирования должны иметь вид .равенств. Максимизировать ~~~' аыум !!, /) ва при условии, что /! — /»+ум< О для всех (!',/"/ в А, /Ъ+!в= ! уы < У!» для всех (»,/» в А, — ум< — й!» для всех (/,// в А.
Пусть /!/, о, уп и бу — двойственные переменные, соответствующие предыдущим линейным ограничениям. Двойственные переменные перечисляются в таком же порядке, в котором вводились ограничения в данную модель. Двойственную задачу можно сформулировать следующим образом. Минимизировать (То+ ~~1' У!»у!» — ~~~~~ 1,!»6!»~ !,/ !./ при условии, что Г!»+у!! — 6,» — — а!» для всех (!,/» в А, '~'„~!» — о = О ! ~~~' [Г!» — Г/!1 = О для всех / = 2,..., п — 1, ! — ~~1' Г»„+и = О ! [!», у,», 6,.» > О для всех (й /) в А.
На основании математической структуры двойственной задачи двойственные переменные /!/ можно рассматривать как потоки в сети с ограниченной пропускной способностью. Вторая, третья и четвертая грунт)ы ограничений соответствуют ограничениям потока для источника, промежуточных и конечного узлов соответственно. В частности, третья группа ограничений соответствует известным ограничениям на сохранение потока.
Используя условия дополняющей нежесткости для задач линейного программирования, можно вывеств следующие результаты, которые должны !выполняться для оптимального решения: »,— /»+у„< О, [„=О, Метода уираеления проектами уц <Ц,н ум=О, уц > Ен, б»*--0, 1»>0, г,— Г,+д»=О, ум > О, у»=им, е) Уц Последние два условия означают, что уц и бц не могут быть одновременно положительными при допущении,' что Е»ФУ».
ее ао Рис. 4дб. Зависимость то и бц от 1о. Поскольку 1»+уц — бц=а», легко сделать вывод, что неотрицательные значения уц и б» определяются по формулам: 1. у»=⻠— 1» при бц=О. 2. 6»=1» — оц при уц=О. Поэтому можно записать: 1. уц=гпах10; вц — 1»1 при бц=О. 2. бц=гпах[0; 1ц — а»1 при уц=О. Графическое представление уц и бц как линейных функций от 1» показано на рис. 4Л6. При исследовании всех возможных значений уц, бц и 1» можно выделить три случая.. Случай 1: уц)0 и б»=0; 0(Ь(вц и у»=У».
Случай 2: у»=0 и бц=О; Ь= а» и Ец(у»~У». Случай 3: у»=0 и бц)0; 1»)вц и уц=Е». На основе условий дополняющей нежесткости для каждого случая находятся следующие условия оптимальности: Случай 1 0(~м(вц и 1,.— 1,+Иц — О. 326 Глава 4 или ~„=О и ~,— ~,+им<0. тю вв Гк а» Случай 2 Гм=ам и г,— ~,+Ум=О, ~и< Ум< Ъ. Случай 3 ам <~м < оо и ~,— 16+1»= О. Введем следующие дополнительные символы: Ъ « — 6+ ~и ~.и = ~~ — 6+~ц У» = ~~ — 6+А Таким образом, условия оптимальности для каждого случая можно записать ~в более компактном виде: Случай 1: 0(~»(а» и У»=0 или Б»=0 и У»(0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
