Экономические науки/8. Математические методы в экономике

Аспирант Баженов Д.В.

Херсонский национальный технический университет, Украина

Применение графов в исследованиях операций

Длительность критического пути легко найти расчётом параметров сетевого графика. Длительность кратчайшего пути равна сумме длительностей его работ. Но как найти работы, принадлежащие кратчайшему пути? Решить эту задачу трудно, особенно при разветвленной структуре сетевого графика. Если будет известно, как проходят особые пути сетевого графика, то можно перераспределить трудовые ресурсы, перенеся ресурсы с работ кратчайшего пути на работы критического пути и уравняв их длительности.

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

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

Для проверки теоремы параметры графика на рисунке пересчитаны при отрицательных значениях длительностей работ (табл.1).

Таблица 1

Работы и события комплекса работ

Работа	k	l	tkl	Событие	t^p	t^q)	Dt	D^Tt^p	D^Tt^q	C^Tt^p	C^Tt^q	Dt^qp	Dt^pp	Dt^qq
a1	0	1	-3	0	0	0	0	0	0	-3	-3	0	0	0
a2	0	2	-1	1	-3	-3	0	0	0	-1	2	3	0	3
a3	0	3	-5	2	-1	2	3	0	0	-5	-4	1	0	1
a4	0	4	-7	3	-5	-4	1	0	0	-7	-6	1	0	1
a5	1	2	-1	4	-7	-6	1	-3	-3	-1	2	6	3	6
a6	1	5	-3	5	-6	-6	0	-3	-3	-6	-6	0	0	0
a7	1	6	-4	6	-7	-6	1	-3	-3	-7	-6	1	0	1
a8	2	5	-8	7	-9	-9	0	-1	2	-6	-6	3	3	0
a9	3	4	-4					-5	-4	-7	-6	3	2	2
a10	3	7	-5					-5	-4	-9	-9	1	1	0
a11	4	6	-3					-7	-6	-7	-6	4	3	3
a12	4	7	-3					-7	-6	-9	-9	1	1	0
a13	5	7	-3					-6	-6	-9	-9	0	0	0
a14	6	7	-3					-7	-6	-9	-9	1	1	0

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

Рис.1. Кратчайший путь сетевого графика.

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

Найти особые пути сетевого графика представляется возможным только, если будут рассчитаны резервы времени всех входящих в него работ. Для поиска критического и кратчайшего пути можно использовать одну и ту же методику. Она заключается в последовательном выборе от 1-го события до завершающего тех работ, которые имеют нулевые резервы времени. Если параметры рассчитать для положительных длительностей, то методика даёт критический путь. Если их рассчитать для отрицательных длительностей, то методика дает кратчайший путь сетевого графика.

Литература:

1. Баженов Д.В., Карамушка М.В. Отношение предшествования и фиктивные работы при сетевом планировании // X науково-методична конференція «Проблеми економічної кібернетики» з нагоди 40-ї річниці «Економічної кібернетики» в Україні (15-17 вересня 2005 р., м.Київ)

2. Белова Л.Д., Ипатов М.И. Сетевые графики в планировании. М.: 1975

3. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. М.: Наука, 1965

4. Романовский И.В. Дискретный анализ. – СПб.: Невский диалект, 2003

5. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975