ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Исходные данные.

Формула приведенных затрат

Z=(C+Eн K) l, где Ен=0,15 (15%) - нормативный коэффициент экономической эффективности капитальных вложений К и эксплуатационных расходов С.

l - длина трассы.

АВ=30км - действующая ЛЭП

Предполагаемая трасса АДЕ1С, которая состоит из трех участков:

АД - реконструированный участок действующей ЛЭП

ДЕ1 - участок по степи

Е1С - участок по лесу

Длина любого участка однозначным образом определяется его проекцией на линию АВ.

Проекция АД=АД=х1

Проекция ДЕ1=ДЕ=х2

Проекция Е1С=ЕВ=х3

Определим возможные пределы изменения каждой проекции

0 х3 ВК - максимальная величина проекции лесного участка. Величину ВК можно определить из подобия треугольников АВС и К1В1С.

ВК=В1К1, В1К1=ВК=

Итак, 0 х3 18.

Величины х2 и х1 могут изменяться от 0 до 30, т.к. максимальная длина этих отрезков совпадает с участком действующей ЛЭП.

Сумма проекций двух строящихся участков, лесного и степного также может изменяться в пределах от 0 до 30, т.е. 0 х2+х3 30. Это вытекает из того, что предельное положение участка СЕ1 есть отрезок СК1, а тогда участок Е1Д совпадет с участком К1А.

Количество вариантов выбора путей для каждого участка однозначным образом определится количеством вариантов изменения значений соответствующих проекций. Вообще говоря, различие этих вариантов можно определить, изменяя переменные хi с каким угодно шагом. Так, например, изменение на 1км приведет к рассмотрению около 600 различных вариантов, с учетом всевозможных комбинаций для каждой переменной. Отсюда, для уменьшения количества рассматриваемых вариантов, ограничимся шагом изменения переменных равным 6км, т.к. даже в этом случае придется

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

I-ый - реконструкция действующего участка ЛЭП плюс строительство в степи и лесу, т.е. полная трасса;

II-ой - строительство участка в зоне степи и леса;

III-й - строительство участка по лесу.

Иначе говоря, этапами мы считаем сами этапы строительства, только нумеруем и перечисляем их в определенном порядке.

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

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

Проиллюстрируем сущность задач динамического программирования на следующем примере.

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

Примечаний нет.