3. Пример решения задачи

Пусть задан код: 231487.

Это означает: Q = 2; K = 3; M = 1; W = 4; G = 8; N = 7.

3.1. Построение таблицы исходных данных

Построения показаны на рис. 2. Последний столбец оставим пока незаполненным.

i	Номера предш. работ			Продолж.	Потр. р/с	Тр. затр.
1	0	0	0	20	6	120
2	0	0	0	60	5	300
3	0	0	0	45	8	360
4	0	1	3	40	7	280
5	0	2	3	5	10	50
6	2	4	3	20	9	180
7	0	4	5	20	12	240
8	0	6	7	40	11	440
9	3	7	1	10	14	140
10	4	3	8	20	13	260
						2370

Рис. 2

3.2. Построение сетевого графа

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

Каждая работа, имеет одну входную окружность (верхнюю) и одну выходную окружность (нижнюю). В верхнем секторе каждой окружности записываем “по максимуму” время, не раньше которого может начаться работа, показанная под кружком. В нижнем секторе каждой окружности записываем “по минимуму” время, не позже которого должна закончиться работа, показанная над кружком.

Моментом начала всего плана работ будем считать ноль.

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

3.2.1. Первый этап построения графа (установление связей в графе)

Показываем первую (самую верхнюю) окружность с секторами (рис. 3).

От этой окружности стрелкой показываем работу A1, в скобках записываем её продолжительность (20). Стрелку упираем в новую окружность с секторами.

Аналогично показываем работы A2 и A3, упирающиеся в свои окружности.

Для работы A4 создаём две новые окружности (входную и выходную), Сплошной стрелкой между ними обозначаем работу A4, в скобках записываем длительность работы (40). Во входную окружность штриховыми стрелками проводим фиктивные работы, соответствующие работам A1 и A3, которые являются предшествующими для работы А4.

Для работы A5 создаём следующие две окружности. От входной окружности вниз показываем стрелку работы A5, в скобках записываем её длительность (5). Во входную окружность штриховыми стрелками проводим фиктивные работы, соответствующие предшествующим работам A2 и A3.

Аналогично для работы A6 создаём свои окружности. Во входную окружность штриховыми стрелками проводим фиктивные работы, соответствующие работам A4, A2 и A3. От входной окружности вниз к выходной окружности показываем работу A6, в скобках записываем её длительность (20).

Подобные построения выполним для оставшихся работ A7, A8, A9, A10.

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