Часть II. Элементы теории графов. u v e u ve 1 3 2 3 1 2. - презентация

1 Часть II. Элементы теории графов

2 u v e u ve

3

4

5

6 2. Поиск путей и маршрутов

7

8

9

10

11

12

13

14

15

16 )(vr – резерв времени события v – на какое время можно задержать наступление события, не увеличивая продолжительность всего проекта. Сроки начала и окончания работы ),(vua : ))utvut(,( рн. р., vu tutvut ))(,( ро. р. vu tvtvut ))(,( пн. п., ))vtvut(,( по. п.

17

18

19

20

21

22

23 Весь процесс управления является конечным многошаговым: Состояние системы в каждый момент времени зависит только от последнего управляющего воздействия и от предшествующего состояния:

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

25 Принцип оптимальности Р.Э. Бэллмана Каковы бы ни были начальное состояние системы и начальное управление, последующее управление должно быть оптимальным по отношению к состоянию, получающемуся в результате действия предыдущего управления. Оптимальное управление удобно представлять вектором, компонентами которого являются оптимальные управления на соответствующих этапах:

26

27 На предпоследнем этапе выбирают наилучшее управление с учетом проведенного исследования: и т.д.

28 Если исследованы последние k этапов управления, то на очередном шаге находят Последний шаг решения – выбор наилучшего управления на первом этапе:

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

30

31 Состояния можно описывать размерами инвестиций: которые распределяются частями последовательно.

32 ),,(),,(),,(),,( (0) (9)(0) ),,(),,(),,(),,( (6) (0)(3). В качестве концов путей интересуют лишь те вершины, для которых условно оптимальные управления принято находить, начиная с последнего.

33

34 Последний этап – выделение инвестиций филиалу С: Возможный размер инвестиций: -- содержимое последнего столбца таблицы.

35 Предпоследний этап – выделение инвестиций филиалам В и С: Возможный размер инвестиций:

36 Подведение итога (инвестирование всех филиалов): Возможный размер инвестиций:

37 -- дополнили таблицу результатами последних вычислений.

38 -- вспомнили, как получали оптимальные значения (подчеркнутые суммы) -- вычислять при меньших значениях не нужно. -- в результате двух возможных оптимальных управлений: или

39 5. Пути в нагруженных графах. Алгоритм Форда – Беллмана. D – ориентированный граф с множеством вершин множество его дуг. дуга с началом v и концом w

40

41

42

43

44

45

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