3.12. Пример расчета параметров сетевого графика

Рассмотрим конкретный пример расчета параметров сетевого графика, представленного на рис. 3.28. Будем обозначать вершины графа не чис­лами, а буквами латинского алфавита. С помощью алгоритма Фалкер- сона нетрудно проверить, что приведенный на рисунке орграф является сетью, в которой исходным и завершающим являются события N и К. На данном рисунке уже приведены результаты расчетов. В каждой записи сверху над разделительной горизонтальной чертой приведены расчеты, относящиеся к ранним срокам, а под горизонтальной чертой —

0+2=2

Рис. 3.28


к поздним срокам свершения событий. Жирным шрифтом выделены значения ранних и поздних сроков для каждого события.

Вычислим ранние сроки свершения событий. Расчет начинается со значения 0 для исходного события ]М, т. е. £Р(]М) = 0, что отмечено на рисунке около данной вершины над горизонтальной чертой. Далее в соответствии с общей методикой расчета необходимо рассмотреть все те события, для которых известны ранние сроки свершения всех предшествующих событий. Такими событиями являются Б и и для этих событий получаем:

<р(8) =г <р(Г*) + Г(Г*, Б) = 0 + 7 = 7, = <Р(]Ч) + Г(Г*, W) = 0 + 2 = 2,

что и отмечено на рис. 3.28 (максимум, стоящий в общей формуле, в данном случае вычислять не требуется, поскольку для рассматри­ваемых событий имеется только по одному предшествующему). После этих вычислений становятся известными ранние сроки всех предше­ствующих событий для события Е; по общей формуле

гР(Е) = тах{гр(М) + Т(М,Е);гр(8)+Т(8,Е)} = = тах{0 + 6; 7 + 1} = тах{6; 8} = 8.

Максимум достигается при движении от события Б; отметим это стрел­кой на соответствующей дуге БЕ. Далее рассматриваем событие С^:

*р(СЭ) = тах{гр(Е) + Г(Е,                 + Т(чу, <2)} =

= тах{8 + 3; 2 + 8} = тах{11; 10} = 11.

Отмечаем стрелкой дугу ЕС^, на которой достигается максимум. Рас­сматриваем событие II:

*р(Ы) = тах{гр(Е) + Г(Е, Ы); *р(8) + Т(Б, II); ^(<2) + Г(СЗ, И)} = = тах{8 + 5; 7 + 3; 11 + 4} = тах{13; 10; 15} = 15.

Отмечаем стрелкой дугу С^И. Наконец, для завершающего события К получаем:

4Р(К) = тах{*р(д) + Т(<2, К); *р(И) + Г(И, К); *р(ЧУ) + Г(\У, К)} = = тах{11 + 7; 15 + 2; 2 + 9} = тах{18; 17; 11} = 18.

Отмечаем дугу С^К. Расчет ранних сроков закончен, все они представ­лены на рисунке. Тем самым, критический срок для данного сетевого графика равен 18. Заметим, что последовательность вычисления ран­них сроков свершения событий совпадает с порядком разбиения вершин сети на группы в алгоритме Фалкерсона.

Критический путь строится в обратном направлении от завершаю­щего события К к исходному событию N с использованием отмеченных стрелками дуг, что дает цепочку К — — Е — Б — N. Для события Б ни одной предшествующей дуги стрелкой не отмечено, но тут вариант дви­жения определен однозначно: других кроме N8 входящих в вершину Б дуг нет. Записывая полученную последовательность в естественном по­рядке, получаем следующий критический путь:

Г*->8->Е->С}->К.

(Отмеченная стрелкой дуга С^И при построении критического пути не использована.)

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

Обратимся к расчету поздних сроков свершения событий. Расчет начинается с уже известного критического срока 18 для завершающего события К, £П(К) = 18, что отмечено на рис. 3.28 около данного события под горизонтальной чертой. Далее в соответствии с общей методикой расчета необходимо рассмотреть все те события, для которых известны поздние сроки свершения всех последующих событий. Таким событием


Событие

г

Предшествующее событие Н

Длительность работы Т(Л,г)

Сумма

*р(/!)+Г(М)

Ранний срок *р(»)

Е

N /Э

6 1

0 + 6 = 6 7+1 = 8

8

К

/СЗ

и w

7 2 9

11 + 7 = 18 15 + 2 = 17 2 + 9=11

18

N

0

 

/Е \У

3 8

8 + 3=11 2 + 8=10

11

и

Е

/сз

э

5 4 3

8 + 5=13 11+4=15 7 + 3 = 10

15

э

N

7

0 + 7 = 7

7

w

N

2

0+2 = 2

2

 

является II, и для него по формуле получаем:

МЫ) = <п(К) - Г(И, К) = 18 - 2 = 16,

что и отмечено на рис. 3.28 (минимум, стоящий в общей формуле, в данном случае вычислять не требуется, поскольку для события И имеется только одно последующее). После этих вычислений становятся известными поздние сроки всех событий, последующих за событием С}; по общей формуле

*п(<Э) = тш{*п(К) - К); £п(11) - Г(СЭ,11)} = = тт{18 - 7; 16 - 4} = тт{11; 12} = 11.

Минимум достигается при движении по дуге С^К; этот факт можно отметить на дуге графа, однако в этом нет необходимости, поскольку критический путь, для построения которого служат отметки, уже най­ден. Далее рассматриваем события Е и ЧУ:

<„(Е) = гшп{<п(СЭ) - Т{Е, С}); Ъ(К) - Г(Е, Я)} = тш{8; 11} = 8, *П(ЧУ) = тт{<п(К) - Т(ЧУ, К); ЗД) - Г(ЧУ, <Э)} = тт{9; 3} = 3. Рассматриваем событие Б:

^(Б) = пип{*п(Е) - Г(8,Е);*П(11) - Г(8,И)} = тт{7; 13} = 7. Наконец, для исходного события N получаем:

= тш{*п(Е) - Г(Г*,Е);*П(8) - Т^, Б); *П(ЧУ) - Г(Г*,ЧУ)} = = тт{2;0;1} =0.

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

Событие і

Последующее событие 3

Длительность работы

т,і)

Разность Чз)~Т(г,з)

Поздний срок

ш

Е

СЗ

И

3 5

11 - 3 = 8 16-5 = 11

8

К

18

N

Е Э

ЧУ

6 7 2

8-6 = 2 7-7 = 0 3-2 = 1

0

СЗ

К

и

7 4

18 - 7 = 11 16-4= 12

11

И

К

2

18-2 = 16

16

э

Е И

1 3

8-1 = 7 16 - 3 = 13

7

 

К

СЗ

9 8

18-9 = 9 11 - 8 = 3

3

 

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

Событие і

Поздний срок

*п(»)

Ранний срок

Резервы времени

г(і)=г п(і)-*р(г)

Е

8

8

0

К

18

18

0

N

0

0

0

СЗ

11

11

0

И

16

15

1

э

7

7

0

3

2

1

 

Как и должно быть, у всех критических событий резервы времени равны 0. У некритических событий И и № резервы времени равны 1. На этом расчет временных параметров заданного сетевого графика полностью завершен.

О Контрольные вопросы

1.               Сформулируйте понятие графа и приведите примеры графов.

2.               Сформулируйте основные понятия теории графов.

3.               Каким образом можно применить метод перечисления путей к ре­шению вопроса о связности заданного графа?

4.               Структура графа задана с помощью матриц смежности и инци­дентности. Сформулируйте в терминах данных матриц алгоритм перечисления путей.

5.               В чем заключается сходство и в чем состоит различие между методом ДП решения задачи о кратчайшем пути на неориенти­рованных графах и классическим методом ДП? Что является аналогом функций Беллмана?

6.               В каком случае задача о кратчайшем пути на неориентированном графе не имеет решения?

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

8.               Поясните, как проводится расчет оценок длины пути при решении задачи о кратчайшем пути методом ДП?

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

10.             С какой целью расставляются метки на ребрах графа в ходе расчетов по методу ДП?

11.             Почему метод ДП решения задачи о кратчайшем пути на неори­ентированных графах не применим в случае отрицательных весов ребер?

12.             Дайте детальное описание алгоритма Дийкстры решения задачи о кратчайшем пути.

13.             Структура графа задана с помощью матриц смежности и ин­цидентности. Сформулируйте в терминах данных матриц

1)            метод ДП решения задачи о кратчайшем пути;

2)            алгоритм Дийкстры решения задачи о кратчайшем пути.

14.             Сформулируйте понятие ориентированного графа и приведите примеры.

15.             Сформулируйте основные понятия, относящиеся к теории ори­ентированных графов.

16.             Для чего применяется алгоритм Фалкерсона и что является результатом его выполнения?

17.             Структура орграфа задана с помощью матриц смежности и ин­цидентности. Сформулируйте в терминах данных матриц

1)       алгоритм Фалкерсона;

2)       метод ДП решения задачи о кратчайшем пути.

18.             В чем заключается сходство и в чем состоит различие между задачами о кратчайшем пути на графах и орграфах?

19.             Сформулируйте метод ДП решения задачи о кратчайшем пути для смешанных (частично ориентированных) графов.

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

21.             Запишите основные расчетные формулы, применяемые при ре­шении задач о кратчайшем и о максимальном пути на орграфах методом ДП.

22.             На основании каких принципов проводится исключение дуг ор­графа при решении задач о кратчайшем и о максимальном пути методом ДП?

23.             Опишите структуру и порядок заполнения таблиц, используе­мых при решении задачи о кратчайшем пути на орграфах ме­тодом ДП.

24.             В чем состоят особенности задачи о максимальном пути на ор­графах?

25.             Что такое сетевое планирование и для решения каких задач оно применяется?

26.             Сформулируйте основные понятия сетевого планирования.

27.             В чем заключается аналогия и в чем состоит различие между задачей о максимальном пути и задачей построения критического пути на сетевом графике?

Дайте определения временным параметрам событий сетевых гра­фиков и опишите методы их вычисления.Задачи для самостоятельного решения

3.1. Для орграфов, изображенных на рис. 3.29-3.36, выполнить сле­дующие задания:

1)               составить матрицу смежности и матрицу инцидентности (при составлении матрицы инцидентности указать нумерацию дуг);

2)               составить список смежности;

3)               найти кратчайший путь из вершины 2 в вершину 8 двумя методами — методом перечисления путей и методом ДП;

4)               найти максимальный путь из вершины 9 в вершину 1 двумя ме­тодами — методом перечисления путей и методом ДП на орграфе;

5)               упорядочить вершины орграфа с помощью алгоритма Фалкер­сона и выяснить, является ли орграф сетью;

6)               если орграф является сетью, то найти исток и сток сети и пере­рисовать граф так, чтобы исток находился слева, сток — справа, а все дуги имели направление слева направо;

7)               считая, если это возможно, орграф сетевым графиком, вычис­лить временные параметры событий и найти критический путь.

3.2. Считая приведенные на рис. 3.29-3.36 графы неориентирован­ными (т. е. игнорируя указанную стрелками ориентацию ребер), вы­полнить следующие задания:

1)               составить матрицу смежности и матрицу инцидентности графа;

2)               построить все пути из вершины 3 в вершину 7;

3)               найти кратчайший путь из вершины 2 в вершину 9 методом ДП;

4)               найти кратчайший маршрут из вершины 1 в вершину 8 с про­хождением через промежуточную вершину 5 методом ДП.

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

зано число выполненных творческих операций, а по вертикали — число выполненных рутинных операций. Точки на схемах, приведенных на рис. 3.37-3.40, отвечают промежуточным положениям в ходе выполне­ния операций, а числа между точками указывают время выполнения соответствующих операций.

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

3.4.           Доказать, что в любом графе число вершин нечетной степени четно.

3.5.           Доказать, что если связный граф имеет п вершин, то он является деревом в том и только в том случае, когда в нем имеется 71—1 ребро.

3.6.           Доказать, что если число ребер графа порядка п > 2 больше С2П_Ъ то граф является связным.

3.7.           Доказать, что не существует графа, степени всех вершин ко­торого попарно различны.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27  Наверх ↑