Характеристики элементов сетевой модели

При расчетах для сетевой модели определяются следующие характеристики ее элементов.

Характеристики событий

1. Ранний срок свершения события tp(0) = 0, tР(j) =тахi{tр(i) + t(ij)}, j=1—N характеризует самый ранний срок завершения всех путей, в него входящих. Этот показатель определяется «прямым ходом» по графу модели, начиная с начального события сети.

2. Поздний срок свершения события t_п(N) = t_р(N), t_п (i) = min_j {(t_п(j)–t(ij)}, i=1—(N-1) характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием. Этот показатель определяется «обратным ходом» по графу модели, начиная с завершающего события сети.

3. Резерв времени события R(T) = t_п(i) – t_р(i) показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ.

Резервы времени для событий на критическом пути равны нулю, R(i) = 0.

Характеристики работы (i,j)

1. Ранний срок начала работы: .

2. Ранний срок окончания работы:

3. Поздний срок начала работы:

4. Поздний срок окончания работы:

5. Резервы времени работ:

• полный резерв – максимальный запас времени, на который можно отсрочить начало или увеличить длительность работы без увеличения длительности критического пути. Работы на критическом пути не имеют полного резерва времени;

• частный резерв – часть полного резерва, на которую можно увеличить продолжительность работы, не изменив позднего срока ее начального события;

• свободный резерв – максимальный запас времени, на который можно задержать начало работы или (если она началась в ранний срок) увеличит ее продолжительность, не изменяя ранних сроков начала последующих работ;

• независимый резерв – – запас времени, при котором все предшествующие работы заканчиваются в поздние сроки, а все последующие – начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ.

Замечания. Работы, лежащие на критическом пути, резервов времени не имеют. Если на критическом пути L_кр лежит начальное событие iработы (i,j), то R_п(i,j)=R_l(i,j). Если на L_кр лежит конечное событие j работы (i,j), то R_п(i,j)=R_c(i,j). Если на L_кр лежат и событие i, и событие j работы (i,j), а сама работа не принадлежит критическому пути, то R_п(i,j)=R_c(i,j)=R_п(i,j)

Характеристики путей

Продолжительность пути равна сумме продолжительностей составляющих ее работ.

Резерв времени пути равен разности между длинами критического пути и рассматриваемого пути.

Резерв времени пути показывает, на сколько может увеличиться продолжительность работ, составляющих данный путь, без изменения продолжительности срока выполнения всех работ.

В сетевой модели можно выделить так называемый критический путь. Критический путь L_кр состоит из работ (i,j), у которых полный резерв времени равен нулю R_п(i,j)=0, кроме этого, резерв времени R(i) всех событий i на критическом равен 0. Длина критического пути определяет величину наиболее длинного пути от начального до конечного события сети и равна . Заметим, что в проекте может быть несколько критических путей.

3. Коэффициент напряженности работ

Для оценки трудности своевременного выполнения работ служит коэффициент напряженности работ:

где t(L_тах(i,j)) – продолжительность максимального пути проходящего через работу (i,j);

t^’_кр – продолжительность отрезка пути L_тах(i,j), совпадающего с критическим путем.

Видно, что К_н(i,j) < 1. Чем ближе К_н(i,j) к 1, тем сложнее выполнить данную работу в установленный срок. Напряженность критических работ полагается равной 1. Все работы сетевой модели могут быть разделены на 3 группы: напряженные (К_н(i,j) > 0,8), надкритические (0,6 < К_н(i,j) < 0,8) и резервные (К_н(i,j) < 0,6).

В результате перераспределения ресурсов стараются максимально уменьшить общую продолжительность работ, что возможно при переводе всех работ в первую группу.

8.2. Анализ проектов. Метод CPM

Исходным шагом для применения метода CPM является описание проекта в виде перечня выполняемых работ с указанием их взаимосвязи. Для описания проекта используются два основных способа: табличный и графический. Рассмотрим следующую таблицу, описывающую проект.

Работа	Непосредственно предшествующая работа	Время выполнения
A	-	tA
B	-	tB
C	B	tC
D	A, C	tD

В первом столбце указаны наименования всех работ проекта. Их четыре: A, B, C, D. Во втором столбце указаны работы, непосредственно предшествующие данной. У работ A и B нет предшествующих. Работе C непосредственно предшествует работа B. Это означает, что работа C может быть начата только после того, как завершится работа B. Работе D непосредственно предшествуют две работы: A и C. Это означает, что работа D может быть начата только после того, как завершатся работы A и C. В третьем столбце таблицы для каждой работы указано время ее выполнения. На основе этой таблицы может быть построено следующее графическое описание проекта.

Из приведенных выше определений и соотношений непосредственно следует:

1) Длина критического пути равна T.

2) Если R(i,j) = 0, то работа (i,j) лежит на критическом пути; если R(i,j)≠0, то работа (i,j) не лежит на критическом пути.

3) Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем r(i,j), то наиболее раннее время наступления последующего события не изменится.

4) Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем R(i,j), то время, необходимое на выполнение всего проекта, не увеличится.

Контрольные вопросы.

1. Правила построения сетевых графиков.

2. Определение пути в сетевом графике, виды путей, важность определения критического пути.

3. Какова взаимосвязь полного и свободного резервов работы?

4. Как можно найти критических путь в сетевой модели, без непосредственного суммирования длительностей работ?

5. Чему равно наиболее раннее время наступления события?

6. Метод CPM разработан для ...

§ описания проектов, путем указания всех работ, предшествующих данной работе;

§ описания проектов, путем представления каждой работы в виде пары узлов сети;

§ минимизации издержек на сокращение продолжительности проекта;

§ нахождения критического пути для проектов с заданным временем выполнения каждой работы;

§ нахождения критического пути для проектов с неопределенным временем выполнения работ.

8.3. Варианты заданий по теме «Метод CPM»

Вариант 1

Экономический факультет МГУ разрабатывает новую программу повышения квалификации преподавателей количественных методов анализа экономики. Желательно, чтобы эту программу можно было реализовать в наиболее сжатые сроки. Существуют существенные взаимосвязи между дисциплинами, которые необходимо отразить, составляя расписание занятий по программе. Например, методы управления проектами должны рассматриваться лишь после того, как слушатели обсудят различные аспекты (коммерческие, финансовые, экономические, технические и т.д.) проектного анализа, связанные с жизненным циклом проекта. Дисциплины и их взаимосвязь указаны в следующей таблице.

Дисциплина	Непосредственно предшествующая дисциплина	Время изучения в днях
A	-
B	-
C	A
D	A
E	C, B
F	C, B
G	D, E

Найдите:

§ минимальное время, за которое можно выполнить программу;

§ длину критического пути;

§ количество дисциплин находящихся на критическом пути;

§ резерв времени изучения дисциплины F.

Вариант 2

«Системы Управленческих Решений» (СУР) представляет собой консалтинговую компанию, специализирующуюся на разработке систем поддержки проектов. СУР заключила контракт на разработку компьютерной системы, предназначенной для помощи руководству фирмы при планировании капиталовложений. Руководитель проекта разработал следующий перечень работ и их непосредственных предшественников:

Работа	Непосредственно предшествующая работа	Время выполнения
A	-
B	-
C	-
D	B
E	A
F	B
G	C, D
H	B, E
I	F, G
J	H

Постройте графическое представление проекта.

Найдите:

§ длину критического пути;

§ сколько работ находится на критическом пути;

§ резерв выполнения работы F.

Вариант 3

Рассмотрите следующую сеть проекта (продолжительность работ показана в неделях):

Работа	Непосредственно предшествующая работа	Время выполнения
A	-
B	-
C	A
D	A
E	B
F	D, E
G	D, E
H	C, F

Найдите:

§ за какое минимальное время может быть выполнен проект;

§ сколько работ находится на критическом пути;

§ на сколько недель можно отложить выполнение работы D без отсрочки завершения проекта в целом;

§ на сколько недель можно отложить выполнение работы С без отсрочки завершения проекта в целом.

Вариант 4

Проект пусконаладки компьютерной системы состоит из восьми работ. Непосредственно предшествующие работы и продолжительность выполнения работ показаны ниже.

Работа	Непосредственно предшествующая работа	Время выполнения
A	-
B	-
C	A
D	B, C
E	D
F	E
G	B, C
H	F, G

Найдите:

§ критический путь;

§ сколько времени потребуется для выполнения проекта;

§ сколько работ на критическом пути;

§ чему равно наиболее раннее время начала работы C;

§ на сколько можно отложить выполнение работы C без отсрочки завершения проекта в целом;

§ чему равно наиболее позднее время окончания работы F;

§ на сколько можно отложить выполнение работы F без отсрочки завершения проекта.

Вариант 5

Московский государственный университет рассматривает предложение о строительстве новой библиотеки. Работы, которые следует выполнить перед началом строительства, представлены ниже. Продолжительность работ показана в неделях.

Работа	Содержание работы	Непосредственно предшествующая работа	Время выполнения (недель)
A	Определить место строительства	-
B	Разработать первоначальный проект	-
C	Получить разрешение на строительство	A, B
D	Выбрать архитектурную мастерскую	C
E	Разработать смету затрат на строительство	C
F	Разработать проект строительства	D, E
G	Получить финансирование	E
H	Нанять подрядчика	F, G

Найдите:

§ критический путь;

§ сколько работ находится на критическом пути (фиктивные работы не учитываются);

§ через какое минимальное время после принятия решения о реализации проекта можно начать работу по строительству библиотеки;

§ насколько недель можно отложить выбор архитектурной мастерской;

§ чему равно наиболее позднее время завершения работы по обеспечению финансирования.

8.4. Анализ проектов. Метод PERT

Для того, чтобы использовать метод PERT, для каждой работы i, время выполнения которой является случайной величиной, необходимо определить следующие три оценки:

Оптимистическое время - время выполнения работы i в наиболее благоприятных условиях.

Наиболее вероятное время - время выполнения работы i в нормальных условиях.

Пессимистическое время - время выполнения работы i в неблагоприятных условиях.

Учитывая, что время выполнения работы хорошо описывается бета – распределением, среднее или ожидаемое время t_i выполнения работы i может быть определено по формуле

Если время выполнения работы i известно точно и равно , то

Располагая указанными выше тремя оценками времени выполнения работы, мы можем также рассчитать общепринятую статистическую меру неопределенности – дисперсию или вариацию var_i времени выполнения работы i:

Если время выполнения работы i известно точно, то = var_i = 0.

Пусть Т - время, необходимое для выполнения проекта. Если в проекте есть работы с неопределенным временем выполнения, то время Т является случайной величиной. Математическое ожидание (ожидаемое значение) времени выполнения проекта Е(Т) равно сумме ожидаемых значений времени выполнения работ, лежащих на критическом пути. Для определения критического пути проекта может быть использован метод CPM. На этом этапе анализа проекта время выполнения работы полагается равным ожидаемому времени t_i. Вариация (дисперсия) общего времени, требуемого для завершения проекта, в предположении о независимости времен выполнения работ равна сумме вариаций работ критического пути. Если же две или более работы взаимозависимы, то указанная сумма дает приближенное представление о вариации времени завершения проекта.

Распределение времени T завершения проекта является ассимптотически нормальным со средним Е(Т) и дисперсией (T). С учетом этого можно рассчитать вероятность завершения проекта в установленный срок T0. Для определения вероятности того, что T≤T0, следует использовать таблицу распределения величины z=(T0-E(T))/s(T), которая имеет стандартное нормальное распределение.

Пример 1.

Конструкторское бюро Московского часового завода разработало новый настольный радиобудильник. По мнению проектировщиков, запуск в серию нового продукта позволит расширить рынок сбыта и получить дополнительную прибыль. Руководство МЧЗ приняло решение провести работу по изучению возможности реализации нового продукта. Конечным результатом этого исследования должен стать доклад с рекомендациями относительно действий, которые должны быть предприняты для организации производства и сбыта нового продукта. Перечень работ и характеристики времени их выполнения (в неделях) указаны в следующей таблице.

Работа	Содержание работы	Непосредственно предшествующая работа	Оптимистическое время ai	Наиболее вероятное время mi	Пессимистическое время bi
A	Подготовить конструкторский проект	-
B	Разработать маркетинговый план	-		1,5
C	Подготовить маршрутные карты	A
D	Построить прототип	A
E	Подготовить рекламную брошюру	A
F	Подготовить оценки затрат	C	1.5		2.5
G	Провести предварительно тестирование	D	1.5		4.5
H	Выполнить исследование рынка	B, E	2.5	3.5	7.5
I	Подготовить доклад о ценах	H	1.5		2.5
J	Подготовить заключительный доклад	F,G,I

1. Определите критический путь для данного проекта.

2. Чему равно ожидаемое время выполнения проекта?

3. С какой вероятностью проект может быть выполнен за 20 недель.

На следующем рисунке показано графическое представление этого проекта.

Решение.

Используя информацию, указанную в таблице, определим ожидаемое время и вариацию времени выполнения каждой работы проекта. Например, для работы A:

t_A = (a_A + 4 m_A + b_A)/6 = (4 + 4 * 5 + 12)/6 = 6 ;

= var_A = ((b_A - a_A )/6 )² = ((12 – 4)/6)² = 1.78.

Проводя аналогичные расчеты для других работ, получаем следующую таблицу.

Работа	Ожидаемое время ti	Дисперсия	Непосредственно предшествующая работа
A		1.78	-
B		0.44	-
C		0.11	A
D		1.78	A
E		0.11	A
F		0.03	C
G		0.25	D
H		0.69	B, E
I		0.03	H
J		0.11	F,G,I

Полагая время выполнения работы равным ожидаемому времени ее выполнения t_i , находим критический путь, используя метод CPM.

Результаты расчетов представлены в следующей таблице.

Работа	Время выполнения	tрн	tро	tпн	tпо	Дисперсия	R
A						1.78
B						0.44
C						0.11
D						1.78
E						0.11
F						0.03
G						0.25
H						0.69
I						0.03
J						0.11

Критический путь для данного проекта включает работы A, E, H, I, J. Длина критического пути равна 6 + 3 + 4 + 2 + 2 = 17. Это означает, что ожидаемое время выполнения проекта составляет 17 недель.

Предполагая, что распределение времени выполнения проекта является нормальным, мы можем определить вероятность того, что проект будет выполнен за 20 недель. Определим дисперсию времени выполнения проекта. Ее значение равно сумме значений дисперсий времен выполнения работ на критическом пути: s²(T)= 1.78+ 0.11 + 0.69 + 0.03 +0.11 = 2.72. Тогда, учитывая, что s(T) = 1.65, находим значение z для нормального распределения при T0=20:

z = (T0-E(T))/ s(T) = (20-17) /1.65 = 1.82.

Используя таблицу нормального распределения, находим вероятность того, что время T выполнения проекта находится в интервале E(T)≤T≤T0. На пересечении столбца «1.8» и строки «0.02» таблицы нормального распределения находим значение 0.4656. Следовательно, искомая вероятность того, что время T выполнения проекта находится в интервале 0≤T≤T0, т.е. вероятность того, что проект будет выполнен за 20 недель при ожидаемом времени его выполнения 17 недель, равна 0.5 + 0.4656 = 0.9656.

Контрольные вопросы.

1. Метод PERT разработан для:

а. описания проектов, путем указания всех работ, предшествующих данной работе

б. описания проектов, путем представления каждой работы в виде пары узлов сети

в. минимизации издержек на сокращение продолжительности проекта

г. нахождения критического пути для проектов с заданным временем выполнения каждой работы

д. нахождения критического пути для проектов с неопределенным временем выполнения работ

2. Объясните суть оптимизации сетевых моделей по критерию «Время - затраты».

3. Какими свойствами должна обладать работа, выбираемая на конкретном шаге для сокращения?

8.5. Варианты заданий по теме «Метод PERT»

Вариант 1

Ниже даны оценки продолжительности выполнения работ (в днях) применительно к небольшому проекту:

Работа	Оптимистическое время аi	Наиболее вероятное время mi	Пессимистическое время bi
A
B
C		7.5
D
E
F

Рассчитайте ожидаемое время выполнения и дисперсию для каждой работы. Известно, что критический путь составляют работы B, D, F.

Найдите:

§ чему равно ожидаемое время выполнения работы B;

§ чему равна дисперсия времени выполнения работы D;

§ ожидаемое время выполнения проекта;

§ чему равна дисперсия времени выполнения проекта.

Вариант 2

Проект строительства плавательного бассейна состоит из девяти основных работ. Работы, их непосредственные предшественники и оценки времени выполнения работ в днях показаны ниже.

Работа	Непосредственно предшествующая работа	Оптимистическое время аi	Наиболее вероятное время mi	Пессимистическое время bi
A	-
B	-
C	A, B
D	A, B
E	B
F	C
G	D
H	D, F
I	E, G, H

Постройте сеть для этого проекта.

Найдите:

§ каков ожидаемый срок завершения проекта;

§ чему равна стандартная ошибка (корень квадратный из дисперсии) времени завершения проекта;

§ какова вероятность того, что проект будет выполнен за 24 рабочих дня.

Вариант 3

Рассмотрите следующий проект (оценки времени выполнения работ указаны в неделях).

Работа	Непосредственно предшествующая работа	Оптимистическое время ai	Наиболее вероятное время mi	Пессимистическое время bi
A	-
B	-	2.5		3.5
C	A
D	A		5.5
E	B
F	D, E
G	D, E
H	C, F

Найдите:

§ какова ожидаемая продолжительность проекта;

§ какова вероятность того, что проект будет завершен за 21 неделю;

§ какова вероятность того, что проект будет завершен за 25 недель.

8.6. Оптимизация сетевых моделей по критерию «время-затраты»

Оптимизация сетевого графика представляет процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения. Она проводится с целью сокращения длины критического пути, рационального использования ресурсов.

В первую очередь принимаются меры по сокращению продолжительности работ, находящихся на критическом пути. Это достигается: перераспределением всех видов ресурсов, как временных (использование резервов времени некритических путей), так и трудовых, материальных, энергетических; сокращением трудоемкости критических работ за счет передачи части работ на другие пути, имеющие резервы времени; параллельным выполнением работ критического пути; изменением состава работ и структуры сети.

В процессе сокращения продолжительности работ критический путь может измениться и в дальнейшем процесс оптимизации будет направлен на сокращение продолжительности работ нового критического пути и так будет продолжаться до получения удовлетворительного результата. В идеале длина любого из полных путей может стать равной длине критического пути. Тогда все работы будут вестись с равным напряжением, а срок выполнения проекта существенно сократится.

8.6.1. Методика оптимизации сетевых моделей по критерию «Время – затраты»

Целью оптимизации по критерию «Время – затраты» является сокращение времени выполнения проекта в целом. Эта оптимизация имеет смысл только в том случае, когда время выполнения работ может быть уменьшено за счет задействования дополнительных ресурсов, что приводит к повышению затрат на выполнение работ (см. Рисунок 1). Для оценки величины дополнительных затрат, связанных с ускорением выполнения той или иной работы, используются либо нормативы, либо данные о выполнении аналогичных работ в прошлом. Под параметрами работ и понимаются так называемые прямые затраты, непосредственно связанные с выполнением конкретной работы. Таким образом, косвенные затраты типа административно-управленческих в процессе сокращения длительности проекта во внимание не принимаются, однако их влияние учитывается при выборе окончательного календарного плана проекта.

Рисунок 1. Зависимость прямых затрат на работу от времени ее выполнения

Важными параметрами работы (i,j) при проведении данного вида оптимизации являются:

· коэффициент нарастания затрат

,

который показывает затраты денежных средств, необходимые для сокращения длительности работы (i,j) на один день;

· запас времени для сокращения длительности работы в текущий момент времени ,

где t_T(i,j) – длительность работы (i,j) на текущий момент времени, максимально возможное значение запаса времени работы равно

.

Эта ситуация имеет место, когда длительность работы (i,j) еще ни разу не сокращали, т.е. .

Общая схема проведения оптимизации «время-затраты»

1. Исходя из нормальных длительностей работ , определяются критические L_kp и подкритические L_п пути сетевой модели и их длительности T_kp и T_п.

2. Определяется сумма прямых затрат на выполнение всего проекта при нормальной продолжительности работ.

3. Рассматривается возможность сокращения продолжительности проекта, для чего анализируются параметры критических работ проекта.

3.1. Для сокращения выбирается критическая работа с min коэффициентом нарастания затрат k(i,j), имеющая ненулевой запас времени сокращения Z_T(i,j).

3.2. Время , на которое необходимо сжать длительность работы (i,j), определяется как

,

где – разность между длительностью критического и подкритического путей в сетевой модели. Необходимость учета параметра ∆T вызвана нецелесообразностью сокращения критического пути более, чем на ∆T единиц времени. В этом случае критический путь перестанет быть таковым, а подкритический путь наоборот станет критическим, т.е. длительность проекта в целом принципиально не может быть сокращена больше, чем на ∆T.

4. В результате сжатия критической работы временные параметры сетевой модели изменяются, что может привести к появлению других критических и подкритических путей. Вследствие удорожания ускоренной работы общая стоимость проекта увеличивается на величину

.

5. Для измененной сетевой модели определяются новые критические и подкритические пути и их длительности, после чего необходимо продолжить оптимизацию с шага 3. При наличии ограничения в денежных средствах, их исчерпание является причиной окончания оптимизации. Если не учитывать подобное ограничение, то оптимизацию можно продолжать до тех пор, пока у работ, которые могли бы быть выбраны для сокращения, не будет исчерпан запас времени сокращения.

Примечание. Рассмотренная общая схема оптимизации предполагает наличие одного критического пути в сетевой модели. В случае существования нескольких критических путей необходимо либо сокращать общую для них всех работу, либо одновременно сокращать несколько различных работ, принадлежащих различным критическим путям. Возможна комбинация этих двух вариантов. В каждом случае критерием выбора работы или работ для сокращения должен служить минимум затрат на их общее сокращение.

8.6.2 Пример проведения оптимизации сетевой модели по критерию «Время - затраты»

Проведем максимально возможное уменьшение сроков выполнения проекта при минимально возможных дополнительных затратах для следующих исходных данных (табл.1, Рисунок 2).

Таблица 1

Исходные данные для оптимизации «Время-затраты»

(i,j)	Нормальный режим	Ускоренный режим
Tн(i,j)	Сн(i,j)	Tу(i,j)	Сп(i,j)
(1,2)
(1,4)
(2,3)
(2,4)
(3,5)
(4,5)
Ск=1,50 руб./день	С0=73,00 руб.

Рисунок 2. Исходная сетевая модель

Исходя из нормальных длительностей работ, получаем следующие характеристики сетевой модели:

· Общие затраты на проект руб.

· Длительность проекта дней.

· Критический путь или .

· Подкритический путь или , дней.

Кроме того, вычислим коэффициенты нарастания затрат и максимальные запасы времени сокращения работ сетевой модели (таблица 2).

Таблица 2

Коэффициенты нарастания затрат работ сети

(i,j)	Zmax(i,j) [дни]	k(i,j) [руб./день]
(1,2)		7,00
(1,4)		3,00
(2,3)		3,50
(2,4)		2,00
(3,5)		0,60
(4,5)		1,00

I шаг. Для сокращения выбираем критическую работу (4,5) с минимальным коэффициентом k(4,5)=1,00 руб./день. Текущий запас сокращения времени работы (4,5) на данном шаге равен дня. Разность между продолжительностью критического и подкритического путей дня. Поэтому согласно п.3.2 описанной выше общей схеме оптимизации сокращаем работу (4,5) на ∆t¹=min[3,2]=2 дня. Новая текущая длительность работы дня, а запас ее дальнейшего сокращения сокращается до дня. Измененный сетевой график представлен на рисунке 3

Рисунок3. Сетевая модель после первого шага оптимизации

После ускорения работы (4,5) возникли следующие изменения.

· Затраты на работу возросли на 1,00руб./день*2дня=2,00 руб. и общие затраты на проект составили руб.

· Длительность проекта дней.

· Критические пути и .

· Подкритический путь , дней.

II шаг.Одновременное сокращение двух критических путей можно провести либо ускорив работу (1,2), принадлежащую обоим путям, либо одновременно ускорив различные работы из каждого пути. Наиболее дешевым вариантом является ускорение работ (3,5) и (4,5) – 1,60 руб./день за обе работы, тогда как ускорение работы (1,2) обошлось бы в 7 руб./день. Поскольку , то сокращаем работы (3,5) и (4,5) на ∆t²=min[5,1,6]=1 день. Запасы дальнейшего сокращения времени работ сокращаются до и дней. Измененный сетевой график представлен на Рисунок 4.

Рисунок 4. Сетевая модель после второго шага оптимизации

После ускорения работ (3,5) и (4,5) возникли следующие изменения.

· Общие затраты на проект составили

руб.

· Длительность проекта дней.

· Два критических пути и .

· Подкритический путь , дней.

III шаг. Поскольку на данном шаге работа (4,5) исчерпала свой запас ускорения, то наиболее дешевым вариантом сокращения обоих критических путей является ускорение работ (3,5) и (2,4) - 2,60 руб./день за обе работы. Сокращаем работы (3,5) и (2,4) на ∆t³=min[4,4,6]=4 дня. Запасы дальнейшего сокращения времени работ (3,5) и (2,4) обнуляются. Измененный сетевой график представлен на Рисунок5.

Рисунок 5. Сетевая модель после третьего шага оптимизации

После ускорения работ (3,5) и (2,4) возникли следующие изменения.

· Общие затраты на проект составили

руб.

· Длительность проекта дней.

· Два критических пути и .

· Подкритический путь , дней.

IV шаг. Поскольку кроме работы (1,2) все остальные работы критического пути исчерпали свой запас времени ускорения, то единственно возможным вариантом сокращения обоих критических путей является ускорение работы (1,2). Сокращаем работу (1,2) на дня. Запас дальнейшего сокращения времени работы (1,2) обнуляется. Измененный сетевой график представлен на Рисунок 6.

Рисунок 6. Сетевая модель после четвертого шага оптимизации

Рисунок 7 График время–затраты

После ускорения работы (1,2) возникли следующие изменения.

· Общие затраты на проект составили руб.

· Длительность проекта дней.

· Три критических пути , и .

· Подкритические пути отсутствуют.

Дальнейшая оптимизация стала невозможной, поскольку все работы критического пути исчерпали свой запас времени ускорения, а значит проект не может быть выполнен меньше, чем за дней.

Таким образом, при отсутствии ограничений на затраты минимально возможная длительность проекта составляет 7 дней. Сокращение длительности проекта с 16 до 7 дней потребовало 28,00 рублей прямых затрат. В отличие от прямых затрат при уменьшении продолжительности проекта косвенные затраты (С_к=1,50 руб./день) убывают, что показано на графике (см. Рисунок 7). Минимум общих затрат (точка А) соответствует продолжительности проекта 14 дней.

Если же учитывать ограничение по средствам, выделенным на выполнение проекта, С₀=73,00 рубля, то оптимальным является выполнение проекта за 9 дней (точка B).

8.7. Варианты заданий по теме «Оптимизация сетевых моделей по критерию «Время-затраты»

Задание

Имеются следующие исходные данные: С_н(i,j) - стоимость выполнения работы (i,j), имеющей нормальную продолжительность Т_н(i,j); Т_у(i,j) - время ускоренного выполнения работы (i,j); C_п(i,j) - повышенную стоимость выполнения работы (i,j), имеющей ускоренную продолжительность;С_к - ежедневные косвенные затраты организации, выполняющей проект; С₀ - ограничение по средствам, выделенным на проведение оптимизации. Проведите максимально возможное сокращение времени выполнения проекта с учетом заданного ограничения на денежные средства С₀, отобразите принятое решение на графике затрат.

Вариант 1

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A
B
C
D
E
F
G
H
I
J
K
	С0=99,00 руб.	Ск=1,20 руб./день

Упорядочение работ

1) A,E и F - исходные работы проекта, которые можно начинать одновременно;

2) Работы B и I начинаются сразу по окончании работы F;

3) Работа J следует за E, а работа C - за A;

4) Работы H и D следуют за B, но не могут начаться, пока не завершена C;

5) Работа K следует за I;

6) Работа G начинается после завершения H и J.

Вариант 2

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A
B
C
D
E
F
G
H
I
	С0=100,00 руб.	Ск=0,90 руб./день

Упорядочение работ

1) D - исходная работа проекта;

2) Работа E следует за D;

3) Работы A, G и C следуют за E;

4) Работа B следует за A;

5) Работа H следует за G;

6) Работа F следует за C;

7) Работа I начинается после завершения B, H, и F.

Вариант 3

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A
B
C
D
E
F
G
H
I
J
	С0=143,00 руб.	Ск=0,60 руб./день

Упорядочение работ

1) С, E и F - исходные работы проекта, которые можно начинать одновременно;

2) Работа A начинается сразу по окончании работы С;

3) Работа H следует за F;

4) Работа I следует за A, а работы D и J - за H;

5) Работа G следует за E, но не может начаться, пока не завершены D и I;

6) Работа B следует за G и J.

ПРИЛОЖЕНИЕ

Таблица нормального распределения.

z 0.00 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

0.0¦ .0000 .0040 .0080 .0120 .0160 .0199 .0239 .0279 .0319 .0359

0.1¦ .0398 .0438 .0478 .0517 .0557 .0596 .0636 .0675 .0714 .0753

0.2¦ .0793 .0832 .0871 .0910 .0948 .0987 .1026 .1064 .1103 .1141

0.3¦ .1179 .1217 .1255 .1293 .1331 .1368 .1406 .1443 .1480 .1517

0.4¦ .1554 .1591 .1628 .1664 .1700 .1736 .1772 .1808 .1844 .1879

0.5¦ .1915 .1950 .1985 .2019 .2054 .2088 .2123 .2157 .2190 .2224

0.6¦ .2257 .2291 .2324 .2357 .2389 .2422 .2454 .2486 .2518 .2549

0.7¦ .2580 .2612 .2642 .2673 .2704 .2734 .2764 .2794 .2823 .2852

0.8¦ .2881 .2910 .2939 .2967 .2995 .3023 .3051 .3078 .3106 .3133

0.9¦ .3159 .3186 .3212 .3238 .3264 .3289 .3315 .3340 .3365 .3389

1.0¦ .3413 .3438 .3461 .3485 .3508 .3531 .3554 .3577 .3599 .3621

1.1¦ .3643 .3665 .3686 .3708 .3729 .3749 .3770 .3790 .3810 .3830

1.2¦ .3849 .3869 .3888 .3907 .3925 .3944 .3962 ,3980 .3997 .4015

1.3¦ .4032 .4049 .4066 .4082 .4099 .4115 .4131 .4147 .4162 .4177

1.4¦ .4192 .4207 .4222 .4236 .4251 .4265 .4279 .4292 .4306 .4319

1.5¦ .4332 .4345 .4357 .4370 .4382 .4394 .4406 .4418 .4429 .4441

1.6¦ .4452 .4463 .4474 .4484 .4495 .4505 .4515 .4525 .4535 .4545

1.7¦ .4554 .4564 .4573 .4582 .4591 .4599 .4608 .4616 .4625 .4633

1.8¦ .4641 .4649 .4656 .4664 .4671 .4678 .4686 .4693 .4699 .4706

1.9¦ .4713 .4719 .4726 .4732 .4738 .4744 .4750 .4756 .4761 .4767

2.0¦ .4772 .4778 .4783 .4788 .4793 .4798 .4803 .4808 .4812 .4817

2.1¦ .4821 .4826 .4830 .4834 .4838 .4842 .4846 .4850 .4854 .4857

2.2¦ .4861 .4864 .4868 .4871 .4875 .4878 .4881 .4884 .4887 .4890

2.3¦ .4893 .4896 .4898 .4901 .4904 .4906 .4909 .4911 .4913 .4916

2.4¦ .4918 .4920 .4922 .4925 .4927 .4929 .4931 .4932 .4934 .4936

2.5¦ .4938 .4940 .4941 .4943 .4945 .4946 .4948 .4949 .4951 .4952

2.6¦ .4953 .4955 .4956 .4957 .4959 .4960 .4961 .4962 .4963 .4964

2.7¦ .4965 .4966 .4967 .4968 .4969 .4970 .4971 .4972 .4973 .4974

2.8¦ .4974 .4975 .4976 .4977 .4977 .4978 .4979 .4979 .4980 .4981

2.9¦ .4981 .4982 .4982 .4983 .4984 .4984 .4985 .4985 .4986 .4986

3.0¦ .4986 .4987 .4987 .4988 .4988 .4989 .4989 .4989 .4990 .4990