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

u v e u ve

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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