Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

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

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

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

tp(S) = tp(N) + T(N, S) = 0 + 7 = 7, ip(W) = tp(N) + T(N, W) = 0 + 2 = 2,

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

<Р(Е) = max{^(N) + T(N,E);fp(S)+T(S,E)} = = max{0 + 6; 7 + 1} = max{6; 8} = 8.

Максимум достигается при движении от события S; отметим это стрелкой на соответствующей дуге SE. Далее рассматриваем событие Q:

ip(Q) = max{ip(E) + Г(Е, Q);ip(W) + T(W, Q)} = = max{8 + 3; 2 + 8} = max{ll; 10} = 11.

Отмечаем стрелкой дугу EQ, на которой достигается максимум. Рассматриваем событие R:

tp(R) = max{tp(E) + Г(Е, R);ip(S) + T(S, R);ip(Q) + T(Q, R)} = = max{8 + 5; 7 + 3; 11 + 4} = max{l3; 10; 15} = 15.

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

ip(K) = max{tp(Q) + T(Q, К); tp(R) + T(R, К); ip(W) + T(W, К)} = = max{ll + 7; 15 + 2; 2 + 9} = тах{18; 17; 11} = 18.

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

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

N^S^E^Q-*K.

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

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

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

 

Событие і

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

h

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

г(м

Сумма tp(h) + T(h,i)

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

Е

N ✓ S

6 і

0 + 6 = 6 7 + 1 = 8

8

К

/Q R W

7 2 9

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

18

N

 

0

Q

W

3 8

8 + 3=11 2 + 8=10

11

R

Е /Q

S

5 4 3

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

15

S

N

7

0 + 7 = 7

7

W

N

2

0 + 2 = 2

2

 

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

in(R) = *П(К) - T(R, К) = 18 - 2 = 16,

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

i„(Q) = min{tn(K) - T(Q,K);in(R) - T(Q,R)} =

= min{18 - 7; 16 - 4} = min{ll; 12} = 11.

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

<П(Е) = min{in(Q) - Г(Е, Q);in(R) - Г(Е, R)} = min{8; 11} = 8, in(W) = min{in(K) - T(W, К); in(Q) - T(W, Q)} = min{9; 3} = 3. Рассматриваем событие S:

in(S) = min{tn(E) - r(S,E);tn(R) - T(S,R)} = min{7; 13} = 7. Наконец, для исходного события N получаем:

t„(N) = тіп{гп(Е) - T(N,E);in(S) - T(N,S);in(W) - T(N,W)} = = min{2;0;l} = o.

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

 

Событие і

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

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

m,j)

Разность tn(j)-T(i,j)

Поздний срок *„(»)

Е

Q R

3 5

11 - 3 = 8 16-5 = 11

8

К

18

N

Е S

W

6 7 2

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

0

Q

к

R

7 4

18 - 7 = И 16-4= 12

11

R

К

2

18-2 = 16

16

S

Е R

1 3

8-1 = 7 16- 3 = 13

7

W

К Q

9 8

18-9 = 9 11 - 8 = 3

3

 

 

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

 

Событие і

Поздний срок

Ранний срок

*р(0

Резервы времени r(i)=t„(i)-tp(i)

Е

8

8

0

К

18

18

0

N

0

0

0

Q

11

11

0

R

16

15

1

S

7

7

0

W

3

2

1

 

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

 

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

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

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

примеры.

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

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

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

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

Задачи для самостоятельного решения

 

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

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

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

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

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

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

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

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

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

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

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

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

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

Подпись:

 

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

Страница: | 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 | 28 | 29 | 30 |