Грицюк С.Н., Мирзоева Е.В., Лысенко В.В. Математические методы и модели в экономике

Подождите немного. Документ загружается.

20

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Найти все полные пути, вычислить их длину и ре-

зервы времени. Построить сетевой график в масштабе

времени.

Решение

Чтобы найти указанные параметры работ, исполь-

зуем формулы (6.23)—(6.32), а также результаты

решения предыдущего примера, оформленные в виде

сетевого графика (рис. 6.10).

Результаты расчетов сведем в табл. 6.5.

Графа 3 заполняется с помощью сетевого графика

(рис. 6.10). Последовательно выписываются числа, сто-

ящие в левых секторах кружков. Графу 4 заполняют,

складывая числа граф 2 и 3. Затем заполняем графу 6,

Таблица 6.5

Работа

Про-

дол-

жи-

тель-

ность

t(i,j)(i,j)i,j),j)j))

Сроки выполнения

Резервы

времени

работ

ранние поздние

на-

чало

рн

(i,j)i,j),j)j))

окон-

чание

ро

(i,j)i,j),j)j))

на-

чало

пн

(i,j)i,j),j)j))

окон-

чание

по

(i,j)i,j),j)j))

пол-

ный

(i,j)i,j),j)j))

сво-

бод-

ный

(i,j)

1 2 3 4 5 6 7 8

=(1,2) 15 0 15 0 15 0 0

=(2,3) 16 15 31 15 31 0 0

=(2,4) 6 15 21 22 28 7 0

=(3,5) 6 31 37 31 37 0 0

=(4,6) 5 21 26 28 33 7 0

=(5,7) 8 37 45 37 45 0 0

=(6,7) 6 26 32 39 45 13 13

=(6,9) 14 26 40 33 47 7 7

=(6,8) 8 26 34 35 43 9 0

=(7,9) 2 45 47 45 47 0 0

=(8,9) 4 34 38 43 47 9 9

=(9,10) 3 47 50 47 50 0 0

21

Математические методы и модели в экономике

выбирая последовательно числа из правых секторов

кружков сетевого графика. Графа 5 равна разности

граф 6 и 2. Графа 7 равна разности граф 6 и 4. Графа 8

заполняется на основе формулы R

(i,j) = t

�

(j) – t

ро

(i,j).

Здесь числа t

(j) берутся из левых кружков графика, а

ро

(i,j) — из графы 4. Для работы а

= (1,2). Она окан-

чивается в секторе кружка, моделирующего событие 2,

поэтому t

(2) = 15. Из графы 4 имеем t

ро

(1,2) = 15. Зна-

чит R

(1,2) = 15 – 15 = 0. Для работы a

= (6,7) имеем

(7) = 45; t

ро

(6,7) = 32. Поэтому R

(6,7) = 45 – 32 = 13

и т. д. Выявим теперь всевозможные полные пути для

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

же резервы времени.

: 1→2→3→5→7→9→10 — критический путь;

: 1→2→4→6→7→9→10;

: 1→2→4→6→9→10;

: 1→2→4→6→8→9→10.

Длина этих путей:

= t(L

) = t

кр

= 15 + 16 + 6 + 8 + 2 + 3 = 50 дней;

= t(L

) = 15 + 6 + 5 + 6 + 2 + 3 = 37 дней;

= t(L

) = 15 + 6 + 5 + 14 + 3 = 43 дня;

= t(L

) = 15 + 6 + 5 + 8 + 4 + 3 = 41 день.

Таким образом, длительность максимального пути

равна 50 дням, за это время все работы комплекса

будут выполнены, то есть 50 дней — это минимальное

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

Определим резервы времени по выявленным путям.

Используя формулу (6.28), получим:

R(L

) = t

кр

– T

= 0 дней;

R(L

) = t

кр

– T

= 50 – 37 = 13 дней;

R(L

) = t

кр

– T

= 50 – 43 = 7 дней;

R(L

) = t

кр

– T

= 50 – 41 = 9 дней.

В пределах имеющихся резервов времени общий срок

выполнения работ не увеличивается, если не увеличи-

лась длительность выполнения любой из работ крити-

ческого пути.

Для наглядности выявления резервов времени постро-

им сетевой график работ (рис. 6.9) в масштабе времени.

22

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Построение начинается с критического пути L

соответствии с правилами сетевого моделирования с

учетом изображения длительности работ t

в масштабе

времени по оси абсцисс. По оси ординат длина стрелок

выбирается из соображений удобства восприятия сети

в целом. Этим объясняется, например, большая длина

стрелки работы а

по сравнению с а

, хотя по масш-

табу времени t

> t

. В результате получим сетевой

график, изображенный на рис. 6.11.

Рис. 6.11. Сетевой график работ в масштабе времени

При построении сетевого графика в масштабе вре-

мени мы сталкиваемся с необходимостью введения

фиктивных работ (пунктирные стрелки) и

фиктивных событий . Время выполнения этих

фиктивных работ равно нулю, а их структура показы-

вает расположение свободных резервов времени:

= R

(6,7) = 13 дней;

= R

(6,9) = 7 дней;

= R

(8,9) = 9 дней.

2

Математические методы и модели в экономике

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

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

всесторонний анализ, с тем чтобы в дальнейшем при-

нять меры по его оптимизации.

Анализ сетевого графика начинается с анализа

структуры сети, включающего контроль построения

сетевого графика, установление целесообразности вы-

бора работ, степени их расчленения.

Затем проводится классификация и группировка

работ по выявлению резервов, с тем чтобы определить

степень трудности выполнения в срок каждой группы

работ.

Величина полного резерва времени не всегда может

достаточно точно характеризовать, насколько напря-

женным является выполнение той или иной работы

некритического пути. Все зависит от того, на какую

последовательность работ распространяется вычис-

ленный резерв, какова продолжительность этой пос-

ледовательности.

Определить степень трудности выполнения в срок

каждой группы работ некритического пути можно с

помощью коэффициента напряженности работ.

Коэффициентом напряженности К

работы

(i,j) называется отношение продолжительности не-

совпадающих (заключенных между одними и теми же

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

путь максимальной продолжительности, проходящий

через данную работу, а другим — критический путь:

где t(L

max

) — продолжительность максимального

пути, проходящего через работу (i,j);

t’

кр

— продолжительность отрезка рассматри-

ваемого пути, совпадающего с критическим путем;

кр

— продолжительность(длина) критического

пути.

(6.34)

2

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Пример

Найти коэффициент напряженности работы

= (4,6), изображенной на рис. 6.10.

Решение

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

= (4,6), — это путь

: 1→2→4→6→9→10;

t(L

max

)= t(L

) = 43 дня.

Несовпадающие отрезки этого пути и критическо-

го пути заключены между событиями 2 и 9. Для пути

— это отрезок 2→4→6→9; а для критического пу-

ти — отрезок 2→3→5→7→9.

Отрезок пути L

, совпадающий с критическим пу-

тем, — это отрезки 1→2 и 9→10, длина t’

кр

которого

равна t’

кр

= 15 + 3 = 18; длина критического пути

кр

= 50. Подставим найденные величины в формулу

(6.34):

Формулу (4.33) можно привести к виду:

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

(i,j) может из-

меняться в пределах от 0 (для работ, у которых

отрезки максимального из путей, не совпадающие

с критическим путем, состоят из фиктивных работ

нулевой продолжительности) до 1 (для работ крити-

ческого пути).

Чем ближе к 1 коэффициент напряженности, тем

сложнее выполнить данную работу в установленные

сроки, а чем ближе он к нулю, тем большим относи-

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

ходящий через данную работу.

Работы могут обладать одинаковыми полными ре-

зервами, но разной степенью напряженности. И на-

(6.35)

2

Математические методы и модели в экономике

оборот, различным полным резервам могут соответс-

твовать одинаковые коэффициенты напряженности.

Из формулы (6.35) видно, что величина коэффи-

циента напряженности зависит от R

и t’

кр

. Чем пол-

ный резерв времени R

больше выполнения некоторой

работы и t’

кр

, (то есть чем меньше t

кр

– t’

кр

— отрезок

времени максимального пути, проходящего через эту

работу и не совпадающего с критическим путем), тем

больше будет дробь, стоящая в правой части форму-

лы (6.35), и чем меньше коэффициент напряженности

этой работы, тем легче будет ее выполнить. В общем

случае указанная дробь определяет удельный вес пол-

ных резервов времени работ в продолжительности от-

резков максимальных путей, не совпадающих с кри-

тическим путем. Чем больше этот удельный вес, тем

меньше коэффициент напряженности.

6.5.7. Задача оптимизации времени

выполнения проекта

Оптимизация сетевого графика представляет про-

цесс улучшения организации выполнения комплекса

работ, целью которого является сокращение длины

критического пути, сокращение общей стоимости ра-

бот, рационального использования ресурсов и др.

Рассмотрим метод решения задачи минимизации

общей продолжительности проекта.

Сетевой график составляется после распределения

всех ресурсов по каждой работе. Эти ресурсы опреде-

ляют время выполнения работ. На сетевом графике

не все работы критические. Поэтому можно умень-

шить время t

кр

за счет резервов на некритических ра-

ботах. Перераспределяя эти резервы на критические

работы, можно уменьшить время их выполнения и

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

меньший t

кр

. Оптимальным сетевой план будет такой,

когда t

кр

получится наименьшим из всех возможных

в данных условиях.

2

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Обозначим ресурсы по работам а

, а

,… соответс-

твенно b

, b

,… .

Пусть работа а

со временем ее выполнения t

ле-

жит на критическом пути, а а

— некоторая работа,

лежащая на некритическом пути, и время ее выпол-

нения — t

Механизм перераспределения средств включает

уменьшение средств работы а

на некоторую величину

< b

, что приводит к увеличению ее времени выпол-

нения

Средства х

, вложенные в работу а

, то есть х

, приводят к уменьшению времени ее выполнения:

В практике выполнения расчетов ϕ(х

) и f(х

)

обычно представляют приближенными линейными

выражениями вида:

Обозначим — коэффициент пересчета.

Тогда формулы (6.36) примут вид:

При таких операциях должно выполняться условие:

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

равняться сумме вложенных средств на критические

работы: , где М — число работ, на которые

средства вкладывались, а N — число работ, с которых

средства снимались.

Общий срок выполнения всего комплекса работ оп-

ределяется целевой функцией:

Здесь i — номера тех работ критического пути,

средства которых не изменились.

(6.36)

(6.37)

2

Математические методы и модели в экономике

Требуется так перераспределить средства с некри-

тических работ на критические, чтобы функция (6.37)

приняла наименьшее значение.

Сколько средств можно взять с некритической ра-

боты? Ясно, что все взять нельзя. Снимаемые средства

определяются наличием резервов времени. Пусть сво-

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

равен R

(а

). Тог-

да должно выполняться условие t

≤ R

(а

), откуда

— ограничение на снимаемые с работы а

средства.

замечание. Если мы снимаем средства с работы

, лежащей на пути L, то нельзя вкладывать данные

средства в другую работу, лежащую на этом пути, ко-

торая является также частью критического пути.

Решение задачи оптимизации состоит в последова-

тельном переносе средств с некритических работ на

критические, переходе от одного пути к другому до

тех пор, пока все работы не будут находиться на кри-

тических путях и иметь резервы. В этом случае дли-

тельность всех путей станет одинаковой.

Пример

Провести оптимизацию сетевого графика (рис. 6.11)

по критерию минимума времени выполнения всех ра-

бот комплекса; построить оптимальный сетевой план

работ; определить экономию. При условии, что c

= 0,1;

= 0,2; c

= 0,3; c

= 0,4; c

= 0,5; c

= 0,6; c

= 0,7; c

= 0,9;

= 0,8; c

= 1,0; c

= 1,1; c

= 1,2.

Решение

Выявленные свободные резервы позволяют про-

вести оптимизацию сетевого графика, связанную с

лучшим перераспределением выделенных ресурсов, и

построить план выполнения всего комплекса работ за

меньшее время, то есть более экономный.

Оптимизацию сетевого графика будем проводить

путем переноса части средств с некритических работ

на критические, фиксируя при этом номера работ, с ко-

торых средства снимаются и на которые переносятся.

2

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Перенося резервы с некритических работ на крити-

ческие, мы будем увеличивать некритический путь и

уменьшать критический до тех пор, пока не совпадут

длительности всех путей.

Расположим длительности всех путей последова-

тельно в порядке увеличения их резервов и начнем

оптимизацию с первой пары путей L

и L

На первом этапе оптимизации переносим резервы

с некритического пути L

некритической работы а

имеющей свободный резерв времени R

= R

(а

) = 7

дней. Берем часть средств х

работы a

и переносим на

работу а

критического пути. Эти средства на работе

обозначим х

. Тогда длительность новых критичес-

ких путей: Величину переносимых

средств х

�

можно определить, решив систему:

при ограничении

По условию: T

= 50; T

= 43; с

= 0,2; t

= 16; c

�

= 0,9;

�

= 14; R

= 7.

Поэтому система (6.38) примет вид:

Отсюда: х

= 0,443.

Ограничение выполнено.

Новое время выполнения работ а

и а

находятся

по формулам: ; новый крити-

ческий срок

Имеем:

(6.38)

2

Математические методы и модели в экономике

На втором этапе рассматриваем следующий бли-

жайший некритический путь L

, на котором у работы

имеется свободный резерв времени:

Снимаемая с работы а

часть средств х

должна

удовлетворять условию

Средства х

перенесем на работу а

в количестве

и на работу а

�

в размере для ускорения выполнения

работ первого и третьего путей.

Для нахождения величин переносимых средств со-

ставим систему уравнений:

Подставим в систему (6.39): с

= 0,2; = 14,592;

�

= 0,9; = 19,582; = 48,583; Т

= 41; с

= 1,1;

= 4.

Имеем:

Cледовательно,

Ограничение выполнено.

Новое время выполнения работ а

, а

находим

по формулам:

(6.39)