Решаем задачу методом динамического программирования

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

Максимальная наращеная мощность 24.

Пример: оптимизация на графе:

.

Разобьем транспортную сеть на состояния: пункт принадлежит состоянию S₁, если из него можно попасть в конечный пункт за 1 шаг.

Так пункты {7, 8, 9} S₁.

По аналогии пункты {5, 6} S₂, {2, 3, 4} S₃, {1} S₄.

Начинаем оптимизацию 1-го состояния (почему?).

В последний пункт можно попасть за один шаг из пунктов 7,8,9. Их стоимости (этих маршрутов) отмечены в прямоугольниках. Так для пункта 5: min {6+9, 6+3} = 9. При этом ненужный путь зачеркиваем.

Далее оптимизируем 2-е состояние (с учетом принципа Беллмана).

В квадратных скобках пунктов 5, 6 отмечаем минимальную сумму попадания в конечный пункт с учетом оптимизации 1- го состояния (этого требует принцип Беллмана!). Продолжая оптимизацию, доходим до 4-го состояния.

Далее - обратный ход: отсекая бесперспективные ветви сети, прочитываем оптимальный путь:

1→ 4→ 6→ 8→ 10.

Рис. 14.2

§ 15 Вероятностные модели

Мы рассмотрим три основных модели:

1. Оптимальное поведение на фондовой бирже [ 5 ]

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

Обычно инвестор вкладывает наличный капитал в несколько видов ценных бумаг (будем говорить об акциях), составляющих портфель инвестора.

Дата добавления: 2015-06-04