Решение задачи модели сетевого планирования с помощью граф

Нестеренко Олеся Викторовна

Учитель математики и информатики

МАОУ СОШ №45 г. Калининграда

Решение задачи модели сетевого планирования с помощью граф

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

Сетевая модель и ее элементы

     Математический аппарат сетевых моделей базируется на теории графов. 
     Графом называется совокупность двух конечных множеств:   множества точек, которые называются вершинами, и множества связей, соединяющих вершины, которые называются ребрами. Если рассматриваемые пары вершин являются упорядоченными, т.е. на каждом ребре задается направление, то граф называется ориентированным; в противном случае — неориентированным. Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь. 
     Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным. 
     В экономике чаще всего используются два вида графов: дерево и сеть. 
     Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. 
     Сеть — это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».
     В экономических исследованиях сетевые модели возникают при моделировании экономических процессов методами сетевого планирования и управления (СПУ).
     Объектом управления в системах сетевого планирования и управления являются коллективы исполнителей, располагающих определенными ресурсами и выполняющих определенный комплекс операций, который призван обеспечить достижение намеченной цели, например, разработку нового изделия, строительства объекта и т.п.
     Основой   сетевого планирования и управления является сетевая модель (СМ), в которой моделируется совокупность взаимосвязанных работ и событий, отображающих процесс достижения определенной цели. Она может быть представлена в виде графика или таблицы.
     Основные понятия сетевой модели:

1. событие,

2. работа,

3. путь.

Задача 8.4. Как изменится срок выполнения проекта (см. рис. 1), резервы времени работ и событий, коэффициенты напряженности работ, если увеличить продолжительность работы t (9,10) на величину:

а). Полный резерв времени работы — Rп (9,10);

б). Частный резерв времени работы первого вида — R1 (9,10);

в). Частный резерв времени работы второго вида или свободный резерв времени работы — Rс (9,10);

г). Независимый резерв времени работы — Rн (9,10)?

15

1

5

11

2

6

7

3

9

8

10

42

5

25

9

30

22

18

15

20

30

30

32

12

22

25

35

4

.

Рис. 1. Сетевой график по выполнению проекта

Решение

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

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

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

Путь – цепочка следующих друг за другом работ (дуг), соединяющих начальную и конечную его вершины. Полный путь L – путь, начало которого совпадает с начальным событием сети, а конец – с завершающим. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную продолжительность, называют критическим (обозначение L_кр). Продолжительность критического пути обозначается как t_кр. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

Сетевая модель должна удовлетворяет следующим требованиям:

1. Не должно быть событий с одинаковыми номерами.

2. Для каждой работы (i,j) должно выполняться i <j

3. Должны быть только одно начальное и одно конечное события.

4. Должны отсутствовать циклы, т.е. замкнутые пути, соединяющие событие с ним же самим.

При выполнении этих требований можно приступать к вычислениям числовых характеристик СМ. Исходные числовые данные СМ представляются в виде таблицы длительности выполнения каждой работы.

Характеристики элементов сетевой модели

При расчетах для сетевой модели определяются следующие характеристики ее элементов.

Характеристики событий

1. Ранний срок свершения события tp(0) = 0, tР(j) =тахi{tр(i) + t(ij)}, j=1—N характеризует самый ранний срок завершения всех путей, в него входящих. Этот показатель определяется «прямым ходом» по графу модели, начиная с начального события сети.

2. Поздний срок свершения события t_п(N) = t_р(N), t_п (i) = min_j {(t_п(j)–t(ij)}, i=1—(N-1) характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием. Этот показатель определяется «обратным ходом» по графу модели, начиная с завершающего события сети.

3. Резерв времени события R(T) = t_п(i) – t_р(i) показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ.

Резервы времени для событий на критическом пути равны нулю, R(i) = 0.

Характеристики работы (i,j)

1. Ранний срок начала работы: .

2. Ранний срок окончания работы:

3. Поздний срок начала работы:

4. Поздний срок окончания работы:

5. Резервы времени работ:

• полный резерв – максимальный запас времени, на который можно отсрочить начало или увеличить длительность работы без увеличения длительности критического пути. Работы на критическом пути не имеют полного резерва времени;

• частный резерв – часть полного резерва, на которую можно увеличить продолжительность работы, не изменив позднего срока ее начального события;

1. свободный резерв – максимальный запас времени, на который можно задержать начало работы или (если она началась в ранний срок) увеличит ее продолжительность, не изменяя ранних сроков начала последующих работ;

2. независимый резерв – – запас времени, при котором все предшествующие работы заканчиваются в поздние сроки, а все последующие – начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ.

Замечания. Работы, лежащие на критическом пути, резервов времени не имеют. Если на критическом пути L_кр лежит начальное событие i работы (i,j), то R_п(i,j)=R_l(i,j). Если на L_кр лежит конечное событие j работы (i,j), то R_п(i,j)=R_c(i,j). Если на L_кр лежат и событие i, и событие j работы (i,j), а сама работа не принадлежит критическому пути, то R_п(i,j)=R_c(i,j)=R_п(i,j)

Характеристики путей

Продолжительность пути равна сумме продолжительностей составляющих ее работ.

Резерв времени пути равен разности между длинами критического пути и рассматриваемого пути.

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

В сетевой модели можно выделить так называемый критический путь. Критический путь L_кр состоит из работ (i,j), у которых полный резерв времени равен нулю R_п(i,j)=0, кроме этого, резерв времени R(i) всех событий i на критическом равен 0. Длина критического пути определяет величину наиболее длинного пути от начального до конечного события сети и равна . Заметим, что в проекте может быть несколько критических путей.

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

Для оценки трудности своевременного выполнения работ служит коэффициент напряженности работ:

где t(L_тах(i,j)) – продолжительность максимального пути проходящего через работу (i,j);

t^’_кр – продолжительность отрезка пути L_тах(i,j), совпадающего с критическим путем.

Видно, что К_н(i,j) < 1. Чем ближе К_н(i,j) к 1, тем сложнее выполнить данную работу в установленный срок. Напряженность критических работ полагается равной 1. Все работы сетевой модели могут быть разделены на 3 группы: напряженные (К_н(i,j) > 0,8), надкритические (0,6 < К_н(i,j) < 0,8) и резервные (К_н(i,j) < 0,6).

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

Работа (i,j)

Продолжительность (дни)
(0,1)	18
(0,2)	30
(0,3)	15
(1,4)	22
(1,5)	12
(2,6)	30
(2,7)	25
(3,9)	9
(3,8)	25
(4,5)	30
(5,11)	22
(6,11)	32
(7,6)	35
(8,10)	5
(9,10)	15
(9,7)	20
(10,11)	42

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

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

К событию 5. К нему ведут два пути: прямой от события 1 и опосредствованный событием 4. Здесь надо использовать во всей полноте нижеприведенную формулу:

Значит, 5-е событие сможет наступить на 70-й день от общего начала работ (но не через 12 дней, как это может показаться вначале).

Очередным является событие 6. К нему ведут два пути: от события 2 и от события 7. Применяем формулу

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

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

.

Примем самый поздний срок наступления (11-го) события, равный 122 единицам времени, поскольку ранний срок (по предыдущим расчетам) был равен этому числу.

Определим этот показатель для последующих событий:

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

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

Полученный результат говорит о том, что расчеты произведены правильно.

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

;

;

;

;

;

;

;

;

Следовательно, критический путь проходит от 0-го до 11-го события через 2-, 6- и 7-е события, у которых резервы времени равны нулю.

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

L_кр: 026711

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

, где — полный резерв времени для

(i, j)-й работы.

Значит, работа (9,10) может быть выполнена не за 15 дней, а за 56 дней (41 + 15) без задержки выполнения всего комплекса работ, предусмотренных сетевым графиком.

По расчетам хорошо видны критические операции – их полный резерв равен нулю. Анализ расчетов и сетевого графика показывает, что критический путь имеет вид L_кр: 026711, а его длина равна

t_кр = 122.

Различают следующие разновидности резервов времени.

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

, где — свободный резерв времени для (i, j)-й работы.

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

Например, свободный резерв времени для работы (9,10) равен

.

Значит, работу (9,10) можно без всякого риска выполнить за 21 дней

(6 + 15) или начать на 6 дней позже, если ее выполнение осуществится за 15 дней.

Частный резерв времени первого вида — это запас времени, которым можно располагать в предположении, что начальное и конечное события работы совершаются в свои поздние сроки.

Этот резерв времени равен разности между самым поздним допустимым сроком наступления конечного для работы события и суммой позднего срока наступления начального события и продолжительности работы. Для расчета частного резерва времени второго вида предлагается следующая формула:

, где — частный резерв времени первого вида. Для работы (9,10) этот резерв составит

,

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

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

Формула для расчета частного резерва времени второго вида имеет вид

, где — частный резерв второго вида для (i,j)-й работы.

Для работы (9,10) частный резерв второго вида равен

Полученный результат означает следующее: не может случиться так, чтобы 10-е событие наступило в ранний срок, в то время как 9-е событие наступит в поздний срок. Включение в фигурные скобки нуля с указанием перед ним знака дает возможность считать, что указанного вида резерва не существует (ведь отрицательным резерв быть не может).

Независимый резерв времени соответствует случаю, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие — начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ.

Независимый резерв

P_н(i,j)=max0;t_p(j)–t_n(i) — t(i,j)= max {0; P_n(i,j)-P(i)-P(j)}.

P_н(i,j)=max0;t_p(10)–t_n(9) — t(9,10)= max {0; P_n(9,10)-P(9)-P(10)}=

=max0;45)–35 — 15= max0;41–11 — 35=0

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

где t(L max) — продолжительность максимального пути, проходящего через работу (i,j);

t_kp`— продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.

В общем виде коэффициент напряженности любого полного пути определяется отношением его длительности () к критическому пути ():

Анализ расчетов и сетевого графика показывает результат: критический путь имеет вид L_кр: 026711, а его длина равна

t_кр = 122.

После нахождения критического пути L_кр: 026711 и его длина равной 122, перейдем к определению коэффициентов напряженности работ.

Полный путь, имеющий наибольшую продолжительность, называется критическим путем. =122

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

Первый путь проходит через события 0 – 1 – 4 – 5 – 11 , и равен 92 . Коэффициент напряженности этого пути составляет:

.

Второй путь проходит через события 0 – 1 – 5 – 11 , и равен 52 . Коэффициент напряженности этого пути составляет:

.

Третий путь проходит через события 0 – 2 – 6 – 11 , и равен 92 . Коэффициент напряженности этого пути составляет:

.

Четвертый путь проходит через события 0 – 2 – 7 – 6 – 11 , и равен 122 . Коэффициент напряженности этого пути составляет:

.

Пятый путь проходит через события 0 – 3 – 9 – 7–6 – 11 , и равен 111 . Коэффициент напряженности этого пути составляет:

.

Шестой путь проходит через события 0 – 3 – 9 – 10 – 11 , и равен 81 . Коэффициент напряженности этого пути составляет:

.

Седьмой путь проходит через события 0 – 3 – 8 – 10 – 11 , и равен 87 . Коэффициент напряженности этого пути составляет:

.

Итого, получили 7 полных путей:

L₁:014511; t_L1=92;

L₂: 01511; t_L2=52;

L₃: 02 611; t_L3=92;

L₄: 027611; t_L4=122;

L₅: 0397611; t_L5=111;

L₆: 0391011; t_L6=81;

L₇: 0381011; t_L7=87 .

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Высшая математика для экономистов / Под ред. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.

2. Горчаков А.А., Орлова И.В. Компьютерные экономико — математические модели. – М.: Компьютер, ЮНИТИ, 1995.

3. Ерохин Н.М., Орехов Н.А., Сидоренко А.В. Статистические модели и планирование экспериментов в экономике: Методическое пособие. – Калуга: КФ МГТУ, 1994.

4. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. – М., 1997.

5. Исследование операций / Под ред. М.А. Войтенко и Н.Ш. Кремера. – М.: Экономическое образование, 1992.

6. Исследование операций в экономике: Учебное пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М., И.М. Тришин, М.Н. Фридман; под ред. Проф. Н.Ш. Кремера. – М.: ЮНИТИ-ДАНА, 2004.

7. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. – Минск: Вышэйшая школа, 1994.

8. Математическое программирование / Под ред. Н.Ш. Кремера. – М.: Финстатинформ, 1995.

9. Орехов Н.А., Левин А.Г., Горбунов Е.А. Математические методы и модели в экономике: Учебное пособие для вузов / Под ред. проф. Н.А. Орехова. – М.: ЮНИТИ-ДАНА, 2004.

10. Орехов Н.А., Сахаров Г.В., Карпушин А.А. Введение в моделирование экономических процессов и явлений. – Калуга: КФ МГЭИ, 1997.

11. Сборник задач и упражнений по высшей математике: математическое программирование / Под ред. А.В. Кузнецова. – Минск: Высшая школа, 1995.

12. Эконометрика: Учебник / Под ред. И.И. Елисеевой. – М.: Финансы и статистика, 2001.

13. https://math.immf.ru/lections/305.html