Задача 1

М.А. Плескунов

ЗАДАЧИ СЕТЕВОГО ПЛАНИРОВАНИЯ

Екатеринбург

УрФУ

УДК

ББК

П

Рецензенты: кафедра информационных систем в экономике Уральского государственного экономического университета (зав. кафедрой – проф., д-р физ.-мат. наук А. Ф. Шориков); ст. науч. сотр., канд. физ.-мат. наук В. Е. Пак (ИММ УрО РАН)

Плескунов М. А.

П Задачи сетевого планирования: учебно-методическое пособие /

М. А. Плескунов. – Екатеринбург: УГТУ-УПИ, 2012. – 66с.

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

Библиогр.: 7 назв. Рис. 12.

УДК

ББК

© УрФУ 2012

©Плескунов М.А., 2012

ЗАДАЧИ СЕТЕВОГО ПЛАНИРОВАНИЯ

Задача 1

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

Работа	Продолжительность работы	Опирается на работы
b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 10 b 11		- - - b 1 b 1 b 3 b 2, b 5, b 6 b 2, b 5, b 6 b 4, b 7 b 3 b 2, b 5, b 6, b 10

или в компактной записи:

b ₁(5)→ b ₄(6), b ₅(4); b ₃(3)→ b ₆(1), b ₁₀(9); b ₂(8), b ₅(4), b ₆(1)→ b ₇(2), b ₈(6); b ₄(6), b ₇(2)→ b ₉(3); b ₂(8), b ₅(4), b ₆(1), b ₁₀(9)→ b ₁₁(7).

Решение.

Сначала строим структурный сетевой график и вводим правильную нумерацию событий:

Рис. 1

Наиболее ранние сроки наступления событий находим по формуле

,

где максимум берется по всем событиям j, непосредственно предшествую-щим событию i. Начальному событию присваиваем

Тогда:

;

;

;

;

;

.

Итак, критическое время Т _кр = 19. Минимальный срок выполнения проекта 19 дней.

Наиболее поздние сроки наступления событий находим по формуле

,

где минимум берется по всем событиям j, непосредственно следующим за событием i. Конечному событию присваиваем наиболее поздний срок наступления равный критическому времени:

Тогда:

;

;

;

;

;

.

Рис. 2

Критическое время Т _кр = 19.

Событие	Ранний срок T p(i)	Поздний срок T п(i)	Резерв времени R (i)
* 0 * 2 * 5 * 6

Временные характеристики событий:

Резервы времени событий найдены по формуле

Критический путь проходит через события с нулевым резервом времени, т.е. через события 0, 2, 5, 6.

Найдем резервы времени работ.

Наиболее ранний возможный срок начала работы b_k = (i, j) равен наиболее раннему сроку наступления события i: S _p(b_k) = T _p(i), а наиболее поздний допустимый срок окончания работы b_k = (i, j) равен наиболее позднему сроку наступления события j: E _п(b_k) = T _п(j).

Полный резерв времени работ найдем по формулам

.

Свободный резерв времени работ найдем по формуле

.

Работа bk = (i, j)	Продолжитель-ность работы, t(bk) = tij	S p(bk)	E п(bk)	r п(bk)	r c(bk)
b 1 = (0, 1) b 2 = (0, 3) * b 3 = (0, 2) b 4 = (1, 4) b 5 = (1, 3) b 6 = (2, 3) b 7 = (3, 4) b 8 = (3, 6) b 9 = (4, 6) * b 10 = (2, 5) * b 11 = (5, 6) φ = (3, 5)					–3 –3 –3

Критические работы – b ₃, b ₁₀, b ₁₁. Резервы времени этих работ равны нулю.

Работаφ = (3, 5) – фиктивная работа.

Резерв времени некритической дуги b находим как разность между длиной замыкающего критического участка и длиной самой некритической дуги:

.

Коэффициент напряженности некритической дуги определяем по формуле

.

Рис. 3

Резервы времени и коэффициенты напряженности некритических дуг:

Некритические дуги	a	b	Резерв времени дуги, R (b)	Коэффициент напряженности дуги, N (b)
(2,3,5) (0,3,5) (0,1,3,5) (0,3,6) (0,1,3,6) (0,1,4,6) (0,1,3,4,6) (2,3,6) (2,3,4,6)				1/9 ≈ 0,11 2/3 ≈ 0,67 3/4 = 0,75 14/19 ≈ 0,74 15/19 ≈ 0,79 14/19 ≈ 0,74 14/19 ≈ 0,74 7/16 ≈ 0,44 6/16 = 0,375

Дуги, коэффициент напряженности которых N (b) > 0,8, составляют критическую зону, дуги с коэффициентом напряженности 0,6 ≤ N (b) ≤ 0,8 образуют подкритическую зону, а дуги с коэффициентом N (b) < 0,6 дают резервную зону. И нашем случае в критическую зону попадает только критический путь, в подкритической зоне находятся дуги (0,1,3,6), (0,1,3,5), (0,3,6), (0,1,4,6), (0,1,3,4,6) и (0,3,5). Из них самая напряженная дуга (0,1,3,6). Она быстрее других может перейти на критический путь. Дуги (2,3,5), (2,3,6) и (2,3,4,6) образуют резервную зону.