Расчет сетевой модели

Классическим видом сетевой модели является детерминированная (строго определенная) сетевая модель, у которой совокупность взаимосвязанных работ (топология) и количественные оценки (продолжительности по времени выполнения работ – метрика) строго и однозначно определены:

 

{i-j} – топология

{t(ij)} – метрика, где

(i-j) – коды работ, в которых

i – код начала работы, j- код окончания работы;

t(ij) – время выполнения работы (дни, часы, недели, месяцы и пр.).

 

Целью построения сетевой модели является ее расчет. В результате расчета получаются количественные характеристики (параметры) событий и работ, которые показывают календарное время наступления событий, время начала и окончания работ и общее время выполнения всего комплекса работ от i₀ до i_n.

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

1.4.1.Временные параметры событий сетевой модели

Ранний срок наступления событий характеризует самое раннее возможное наступление любого события i относительно времени наступления i₀. Согласно алгоритму Форда ранний срок наступления события можно определить в варианте прямой прогонки сетевой модели (от i₀ до i_n), в основе которого лежит соотношение (4.1)

 

0, если i = i₀

Т^p_i = max [T^p_k + t(ki)], если i ≠i ₀ (4.1)

	kiЄUвi

По формуле (4.1) рассчитываются ранние сроки наступления всех событий сетевой модели. Необходимо иметь в виду, что для расчета надо учитывать порядок предшествования.

Полученные {Т^p_i} для всех событий представляют собой абсолютные значения времени наступления событий, т.е. через сколько единиц времени наступит событие i, начиная от точки i₀. Для перевода сроков наступления событий в календарные даты необходимо задать дату наступления исходного календарного события сетевой модели.

Значение Т^p_i показывает длину максимального пути, предшествующего событию i – t[L_{max предш}(i)]. Следовательно, значение Т^p_in показывает самый длинный по продолжительности путь в сетевой модели; он называется критическим путем Ткр и показывает минимально возможное время выполнения всех работ сетевой модели. Указанное соображение характеризуется рисунком 1.8.

 

 

Ткр

 

Рис.1.8.Фрагмент сетевой модели

 

Событию i предшествуют следующие пути:

1) I₀ -1 –2 – i (длина пути равна 16)

2) I₀ - 3 – i (длина пути равна 9)

3) I₀ - 4 – i (длина пути равна 27)

Следовательно, t[L_{max предш}(i)] = 27. Если рассчитать сетевую модель по алгоритму Форда, то T = 27.

 

 

Заметим, что алгоритм Форда не использует «перебор» путей, а направленно рассматривает только те работы, которые непосредственно входят в данное событие (См. фрагмент, изображенный на рисунке 1.9.)

 

 

Рис.1.9.Фрагмент, характеризующий связь «событие – то, что ему непосредственно предшествует».

 

Поздний срок наступления событий характеризует самое позднее время наступления события i. Расчет поздних сроков наступления событий осуществляется в варианте обратной прогонки алгоритма Форда (от i_n до i₀) по соотношению (1.2)

 

Т^p_in,если i=i

Т^п_i = min [T^п_j -t(ij),если i≠i_n (1.2)

	ijЄUиi

Согласно алгоритму Форда и формуле (1.2) для каждого события рассматривается фрагмент, изображенный на рис.1.10.

 

Рис.1.10. Фрагмент, характеризующий связь «событие – то, что из него непосредственно исходит»

Резерв времени события характеризует запас времени события (в днях,..), учитывающий возможность перенести срок наступления события, не изменяя при этом срока наступления завершающего события i_n (т.е. Ткр), и рассчитывается по формуле (1.3)

R (i) = T^п_i –T^p_i (1.3)

 

Рассмотрим пример расчета сетевой модели

Исходная информация для построения топологии сетевой модели и продолжительности работ дана в таблице 1.2.

Сетевая модель (рис.1.11) отображает процесс маркетингового исследования фирмы, желающей выйти со своим товаром на рынок. Цель расчета – определить окончательный срок исследования и календарные даты наступления событий и сроков начала и окончания работ.

Таблица 1.2. Исходная информация

Код работы i-j	Наименование работы	Продолжительность работы (i-j), дни
1-2	Исследование внутреннего рынка
1-4	Исследование зарубежного рынка
2-4	Определение сегмента внутреннего рынка
4-6	Определение политики освоения сегментов внутреннего и зарубежного рынков
1-5	Исследование качества выпускаемого товара
5-4	Разработка программы по адаптации товара к сегментам рынка
5-7	Разработка рекламной политики по продвижению товара на рынке
2-3	Разработка программы услуг по передвижению товара
3-6	Выбор посредников
7-6	Разработка политики оптовой и розничной торговли
8-8	Разработка торговой марки и упаковки
6-8	Определение ценовой политики
7-8	Разработка программы сервисного обслуживания

 

 

Рис.1.11.Сетевая модель, отображающая процесс маркетингового исследования

Произведем расчет параметров T^p_i, T^п_i и R(i).

 

Расчет T^p_i:

T^p_io = T^p₁ = 0

T^p₂ = T^p₁ + t(1-2) = 0+3 = 3

T^p₅ = T^p₁ + t(1-5) = 0+5 = 5

T^p₄ =max [T^p₂ + t(2-4); T^p₅ + t(5-4); T^p₁ + t(1-4)] = max [3+4; 5+8; 0+7] = 13

2-4

5-4

1-4

 

T^p₃ = T^p₂ + t(2-3) = 3+6 =9

T^p₇ = T^p₅ + t(5-7) =5+3 = 8

T^p₆ = max [T^p₃ + t(3-6); T^p₄ + t(4-6); T^p₇ + t(7-6)] = max [9+2; 13+2; 8+10] = 18

3-6

6-8

7-6

T^p₈ = max [T^p₃ + t(3-8); T^p₆ + t(6-8); T^p₇ + t(7-8)] = max [9+4; 18+7; 8+8] = 25

3-8

6-8

7-8

Следовательно, Ткр = Т^р₈ = 25. Это означает, что все работы сетевой модели по маркетинговому исследованию могут быть выполнены не менее, чем за 25 дней.

Расчет Т^п_i:

T^п_io = T^п₈ = 25

T^п₆ = Т^п₈ – t(6-8) = 25-7 = 18

T^п₇ = min [T^п₆ – t(7-6); T^п₈ – t(7-8)] = min [18-10; 25-8] = 8

7-6

7-8

T^п₃ = min [T^п₈ – t(3-8); T^п₆ – t(3-6)] = min [25-4;18-2] = 16

3-8

3-6

T^п₄ = T^п₆ – t(4-6) = 18-2 = 16

T^п₅ = min [T^п₄ – t(5-4); T^п₇ – t(5-7)] = min[16-8; 8-3] = 5

5-4

5-7

T^п₂ = min [T^п₃ – t(2-3); T^п₄ – t(2-4)] = min [16-6; 16-4] = 10

2-3

2-4

T^п₁ = min [T^п₂ – t(1-2); T^п₄ – t(1-4); T^п₅ – t(1-5)] = min [10-3; 16-7; 5-5] = 0

1-2

1-4

1-5

Если задать дату исходного события, то можно получить календарные даты наступления каждого события. Пусть дата i₀ будет 1.01.2001г. Будем считать, что все дни – рабочие. (Если учитывать праздничные и выходные дни, то их надо удалить из рассматриваемой шкалы). Тогда результаты расчета можно свести в таблицу 1.3.

Таблица 1.3. Временные параметры и резервы времени событий

 

Код события i	Ранний срок наступления события Трi	Поздний срок наступления события Тпi	Резерв времени события R (i)
1.01.2001.	1.01.2001.
3.01.2001.	10.01.2001.
5.01.2001.	5.01.2001.
13.01.2001.	16.01.2001.
9.01.2001.	16.01.2001.
8.01.201.	08.01.2001.
18.01.2001.	18.01.2001.
25.01.2001.	25.01.201.

 

Алгоритм Форда дает возможность рассмотреть некоторые теоретические положения, которые мы сформулируем в виде теорем (без доказательств) и которые будем

 

Теорема 1. Длина критического пути в сетевой модели равна величине Т^р_io:

т.е. Ткр = t [L_{max предш} (i_n)] = T^p_in = T^п_in. (1.4)

 

Теорема 2. Длина максимального пути, следующего за некоторой вершиной i, равна разности Ткр и соответствующей величины Т^п_i:

т.е. t [L_{max след} (i)] = Ткр – Т^п_i (1.5)

 

Теорема 3. Если некоторая величина i принадлежит критическому пути, то величины Т^р_i и Т^п_i равны между собой:

т.е. i Є Lкр => Т^р_i = T^п_i

 

Теорема 4. Если событие принадлежит критическому пути, то резерв данного события равен 0:

т.е. i Є Lкр => R(i) = 0

Обратимся к таблице 1.3. События 1, 5, 7, 6, 8 принадлежат критическому пути

 

1.4.2. Временные параметры работ сетевой модели

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

 

Т^р.н. _{i j} = Т^р _i (1.6)

 

Соответственно, раннее окончание работы будет равно:

 

Т^р.о. _{i j} = T^р.н._ij +t(ij) = T^p _i +t(ij) (1.7)

 

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

 

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

 

 

L_{max след}(i)

Ткр

 

Рис.1.12. Фрагмент сетевой модели

 

Таким образом, используя теорему 2, можно написать:

Т^п.о._{i j} = Ткр – t[L_{max след}(j)] = Ткр – Ткр + Т^п _j;

Т^п.о._ij = Т^п_j (1.8)

 

Соответственно,

Т^п.н._{i j} = Т^п.о._ij – t(ij) = T^п _j – t(ij) (1.9)

 

Как видим, для расчета экстремальных характеристик времени начала и окончания работ сетевой модели необходимо осуществить алгоритм Форда и получить для каждого события T^p_i и Т^п_i.

 

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

 

R^п_(ij) = Т^п.н._ij – Т^р.н_ij = Т^п.о._ij – Т^р.о._ij = Т^п_j - Т^р_i – t(ij) (1.10)

 

Организационно-экономический смысл полного резерва времени работы: он показывает, на сколько можно увеличить продолжительность работы, или задержать ранний момент ее начала, не изменяя Ткр. Это положение можно охарактеризовать на рис.1.13

 

i t(ij) j R^п

 

R^п

 

 

0 Т^р.н._ij Т^п.н._ij Т^р.о._ij Т^п.о._ij t

Рис.1.13. организационно-экономический смысл R^п(ij)

 

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

R^п (ij) = 0 <=> ij Є Lкр

 

На практике работы критического пути являются «узким местом» и требуют дополнительного внимания. Для оперативного управления ходом выполнения работ вычисляется еще один резерв времени работы – свободный резерв времени работы, который равен разности значений раннего срока свершения конечного события j работы (i-j) и значения раннего срока ее окончания:

 

R^c (ij) = Т^р_j – Т^р.о._ij = Т^р_j – Т^р_i – t(ij) (1.11)

 

Организационно-экономический смысл свободного резерва времени работы: он показывает, на сколько можно увеличить продолжительность работы, или задержать ранний момент ее начала, не изменяя раннего срока начала работ, которые непосредственно следуют за искомой. Это положение можно охарактеризовать на рис.1.14

 

 

i j → j k

R^c

 

Т^р.н._jk t

Рис.1.14. организационно-экономический смысл R^c (ij)

 

Теорема 6. Если работа принадлежит критическому пути, то ее свободный резерв равен нулю:

ij Є Lкр => R^c(ij) = 0

 

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

Рассчитаем все параметры работ предыдущего примера (см.рис.1.11). основой для расчета являются параметры событий (табл.1.3). Результаты расчета сведем в табл.1.4.

Таблица 1.4. Результаты расчета

Коды работ i-j	t(ij)	Тр.н.ij	Тп.о.ij	Тп.н.ij	Rпij	Rcij
1-2
1-4
2-4
1-5
5-4
2-3
4-6
5-7
3-6
7-6
3-8
6-8
7-8

Таким образом, расчет математической модели маркетингового исследования показал:

Общее время исследования (Ткр) равно 25 дням.

Если начать исследование 01.01.01 г., то к 26 января исследование должно быть закончено.

Каждая отдельно взятая работа (i-j) дает ее исполнителю полную картину плановых ориентиров. Например, работы (5-7) по разработке рекламной политике выпускаемого товара является работой критического пути, «узким местом», т.е. она среди всех работ общего комплекса имеет только один срок начала – 5 января и не имеет резервов во времени. А работу, например, (3-8) по разработке торговой марки товара можно начать 9 января, а можно 21 января, и при этом окончательный срок всего комплекса работ не изменится, т.е. эта работа имеет резерв 12 дней, что говорит о более «выгодных» условиях для исполнителей этой работы.

 

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

Теорема 7

Если продолжительность работы (ij) увеличить на величину R^п_ij, то:

_a) Т^р.н._jk^* = Т^р.н._jk + R_j

_b) R^п_jk^* = R^п_jk - R_j

_c) T^п.о._si^* = T^п.о._si - R_i

_d) R^п_si^* = R^п_si - R_i

 

 

Рис.1.15.

 

Теорема 8. Если продолжительность работы (ij) увеличить на величину, подчиненную следующим ограничениям, то:

 

α ≤ R^c_ij => Т^р.н._jk = const

 

α >R^c_ij => Т^р.н._jk^* = Т^р.н._jk + (α -R^c_ij)

 

Согласно теоремам 7,8 можно анализировать фрагменты работ, не пересчитывая всю сетевую модель.

 

Например, по результатам табл.1.4. можно сказать, что работа (2-4)имеет два резерва: R^п(2-4) = 9; R^c(2-4) = 6. Это значит, что максимально возможно увеличить продолжительность работы на 9 дней и при этом Ткр не изменится, но работа, которая непосредственно следует за (2-4), а именно (4-6), изменит свой первоначальный ранне возможный срок начала на 3 единицы, так как α=9; α -R^c(ij) =9-6 =3. Если бы работа (2-4) увеличивалась по продолжительности ровно на величину свободного резерва, т.е. на R^c(2-4) = 6 дней, то можно было бы утверждать (согласно теореме 7), что Т^р.н._4-6 не изменилось бы.

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