книги из ГПНТБ / Обрезков, В. И. Гидроэлектрические станции в электроэнергетических системах

Д и H а м и ч е с к о е п р о г р а м м -и р о в а и и е

Метод динамического программирования предназна­ чен в основном для управления системами, решение ко­ торых связано с задачами многошагового выбора. Тео­ ретические основы метода были разработаны Р. Беллманом [Л- 4]. В основе метода лежит принцип оптимально­ сти Беллмана, согласно которому «оптимальное управчение обладает тем свойством, что какое бы ни было начальное состояние и управление, последующее управ­ ление должно быть оптимальным по отношению к со­ стоянию, получающемуся в результате действия началь­ ного управления». Или, иначе говоря, общее поведение системы не зависит «от предыстории», т. е. поведения системы в прошлом, и определяется лишь ее начальным состоянием.

Идея метода заключается в том, что отыскание экс­ тремума функции многих переменных заменяется много­ кратным отысканием экстремума функции одного или малого числа переменных [Л. 8]. Другими словами, вме­ сто того, чтобы 1 раз решать сложную задачу, много­ кратно решается задача более простая. Для этого осу­ ществляется поэтапное планирование процесса, при ко­ тором на каждом этапе (шаге) на основе использования информации, полученной на предыдущих этапах реше­ ния, оптимизируется только один шаг, причем с учетом последствий того, к чему он приводит в будущем, т. е. на следующих этапах.

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

При поэтапном планировании с учетом последствий процесс динамического программирования обычно осу­

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

2 4 0 .

Тогда суммарный наибольший эффект за два рассма­ триваемых шага, очевидно, будет определяться как

•f*п(п-і) (Х„_2 ) = М а к с [ ф п - і ( Х п - 2 , Un-i) +/*n(X„_i)]. (7-41)

Ясно, что для оптимального управления Ь*п-і зна­ чение /*п(п-і) будет являться функцией только состояния системы Х,г _2 в момент tn-z, что и отражает запись ле­ вой части этого условия.

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

Для любого і-го шага аналогичная запись будет иметь

оптимальное управление Ui и, следовательно, весь ряд значений и „ _ ( 1 - + 1 ) и соответствующие им значения Х„_*, обеспечивающие экстремум /*о(Х0 ). Сказанное иллюст­ рирует рис. 7-1.

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

трудоемким, что и заставляет применять различные его модификации.

Г р а д и е н т н ы е м е т о д ы

Направление вектора-градиента функции / ( X ) слу­ жит, как известно, направлением максимальной скоро­ сти возрастания этой функции. Отсюда процесс оптими-

242

функции / ( X ) . Только в этом случае можно быть уве­ ренным, что процесс сходится к глобальному экстре­ муму.

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

1=1

где е — достаточно малое наперед заданное число. Указанный шаг по направлению вектора-градиента

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

и легко реализуется на ЭВМ. При С < 0 движение осу­ ществляется по направлению, обратному направлению вектора-градиента, называемого иногда антиградиентом.

Разновидностью описанного метода градиента явля­ ется метод наискорейшего спуска. В этом методе движе­ ние вдоль направления вектора-градиента осуществляет­ ся не в соседнюю достаточно близкую точку, а до полу­ чения экстремума вдоль этого направления. Найденный на этом направлении частный экстремум принимается в качестве следующей начальной точки, и движение по­ вторяется. Решение определится при достижении усло­ вия (7-45).

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

244

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

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

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

Как указывалось в предыдущем параграфе, на целе­ вую функцию / ( X , U) могут быть наложены ограничения типа равенств или неравенств: уравнения (7-1) — (7-3) или (7-4). Учет этих ограничений является наиболее сложным этапом в процедуре поиска решения, в осо­ бенности если оно граничное и не единственное (много­ экстремальные задачи). Существует много методов уче­ та ограничений. Рассмотрим те из них, которые являют­ ся наиболее распространенными.

ничений наиболее удобен для градиентных методов, ког­ да ограничения наложены на координаты xit для прин­ ципа максимума при ограничениях, накладываемых на

245

управления iij, и в динамическом программировании, когда ограничиваются как ХІ, так и щ.

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

нительных условий типа равенств (уравнение связи), которые могут быть изопериметрическими, голономными и неголономиыми. Методы и приемы учета этих ограни­

принципы построения указанной функции были рассмо­

назначен для учета любых ограничений типа неравенст­ ва. Суть его состоит в том, что определение экстремума осуществляется исходя не из целевой функции / ( X , U), а некоторой другой, состоящей из целевой и так назы­ ваемой штрафной функции, т. е.

Таким образом, смысл использования штрафной функция заключается в том, что всякое нарушение огра­ ничений как бы штрафуется по определенным матема­ тическим правилам, вытекающим из принципа: чем боль­ ше нарушение, тем больше штраф. При бесконечно боль­ ших значениях Ш(Х, 13) значение Ф(Х, U) вырождает­ ся в движение вдоль границы.

Поиск экстремума Ф(Х, U) может осуществляться любым из рассмотренных в § 7-4 методов математиче­ ского программирования.

246

Известно несколько математических формулировок штрафных функций. Рассмотрим одну из них для слу­ чая введения следующих ограничений:

Тогда уравнения (7-48)—(7-50) будут эквивалентны соответственно следующим уравнениям типа равенств:

247

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

1. Большая размерность задачи. По существу мы не имеем возможности ставить задачу на современные ЦВМ без того, чтобы не вводить определенные упрощения в ее постановку.

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

3. Требования на воду отдельных участников ком­ плекса изменяются во времени, переходя из совпадаю­ щих в противоречивые и наоборот. Так, водный транс­ порт заинтересован в период мелководья в сработке водохранилища, а энергетика, наоборот, в сохранении ма­ ксимального уровня его до наступления осенне-зимнего пика нагрузки. Зимой энергетика предъявляет повышен­ ный спрос на воду, что обычно удовлетворяет требова­ ниям по обеспечению нормальных условий стоянки су­ дов в затонах нижнего бьефа ГЭС. Противоречивы тре­ бования на воду энергетики и ирригации, энергетики и рыбного хозяйства, рыбного хозяйства и ирригации и т. д. Имеются даже противоречия внутри одной и той же отрасли народного хозяйства. Так, водный транс­ порт заинтересован в поддержании судоходных глубин в нижнем бьефе ГЭС, что требует соответствующих рас­ ходов из водохранилищ, но при этом последние сраба­ тываются, и тем самым ухудшаются условия судоходст­ ва в верхнем бьефе данной ГЭС и нижнем у вышеле­ жащей.

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

4. Вероятностный характер основной исходной инфор­ мации. Учет этого обстоятельства приводит к необходи­ мости использовать в рассматриваемых расчетах соответ-

249