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

 

является 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.

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

 

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

 

Как и должно быть, у всех критических событий резервы времени равны 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 больше С²_П__Ъ то граф является связным.

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

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