Схема - динамическое программирование
Cтраница 2
Поскольку поиск оптимального варианта в каждой из задач проводился по одной и той же пошаговой схеме динамического программирования от истоков речной сети к замыкающему створу, программный комплекс был объединен в некоторую систему, центральные модули которой решали либо обе задачи одновременно, либо какую-либо одну из них. Однако внедрение этой модели в течение 5 - 7 лет на многочисленных реальных объектах показало, что прикладные пользователи никогда не обращались к совместному решению обеих задач. [16]
Так, например, в основе многих моделей лежит представление речной сети в виде графов специальной структуры - входящего дерева. Применению схем динамического программирования не препятствуют любого вида нелинейности в целевой функции и ограничениях и наличие дискретных переменных. Вычислительная трудоемкость алгоритмов поиска глобального экстремума с заданной точностью не зависит от многоэкстре-мальности получающейся задачи. Ограничительные предположения состоят в аддитивности целевой функции, сепарабельности ( отделимости) всех ограничений и технических условий отбраковки вариантов по шагам расчетной схемы. Кроме того, схема динамического программирования реализуема лишь тогда, когда параметр состояния системы на каждом шаге условной оптимизации имеет размерность не выше трех. Это ограничение, к сожалению, часто оказывается наиболее существенным. Так, например, в задачах оптимального выбора водоохранных мероприятий применение рассматриваемой схемы возможно только при учете не более трех независимых видов 3В, либо требует перехода к интегральным показателям качества воды. [17]
Решение задачи основано на двумерной схеме динамического программирования, изложенной в разделе 5.4. Однонаправленный граф ВХС позволяет при этом ввести между участками отношение порядка, когда можно полагать, что все вышерасположенные участки имеют номер, меньший, чем рассматриваемый г-й участок. Возможность использования схемы динамического программирования основана на аддитивности целевой функции (5.5.4) и отделимости ограничений модели по участкам и периодам времени. [18]
Дальнейшая процедура решения строится на принципах стохастической схемы динамического программирования. Разница между стохастической и детерминированной схемами динамического программирования весьма существенна, она затрагивает структуру оптимального управления. [19]
В заключение кратко остановимся на решении технико-экономических задач выбора состава и структуры системы мониторинга, которые основаны на специфике конфигурации водного объекта. Для реки - это линейная схема движения от истоков к устью реки, что позволяет воспользоваться расчетом по схеме динамического программирования. Для этого выделяются створы верховий реки к устью, включающие в себя возможные места установок аппаратуры мониторинга. От верховий до устья проводится перебор вариантов установки аппаратуры по створам. При этом для каждого створа эти варианты учитывают их сочетания с возможными вариантами аппаратуры на всех вышележащих створах. Затем вычисляется достоверность рассматриваемых вариантов мониторинга до данного створа включительно. [20]
Каждое из ограничений (11.7.5), (11.7.6) и (11.7.14) отделимо. Тогда с учетом (11.7.11) и того факта, что Т ( J, S) - ориентированное дерево, для ее решения можно применить схему динамического программирования с шагом по вершинам j E J в направлении от листьев к корню. [21]
Каждое из ограничений (11.7.5), (11.7.6) и (11.7.14) отделимо. Тогда с учетом (11.7.11) и того факта, что Т ( J, S) - ориентированное дерево, для ее решения можно применить схему динамического программирования с шагом по вершинам j G J в направлении от листьев к корню. Диапазон допустимых значений jj определяется физическим смыслом этого параметра: во всех случаях суммарный сбросной расход из водохранилищ, расположенных непосредственно выше j - ro, не может превысить расход Q. [22]
 |
Алгоритм расчета оптимальных режимов КС. [23] |
Два режима считаются сопоставимыми, если они имеют одинаковые значения N. В этом случае из них выбирается один режим, для которого значение целевой функции соответствует заданному критерию оптимизации. В соответствии со схемой динамического программирования на каждом шаге многошагового процесса необходимо осуществлять полный перебор всех значений управляющих воздействий. Однако для КС это неосуществимо из-за большого числа возможных вариантов, что резко увеличивает общее время счета. Для уменьшения числа рассматриваемых вариантов применяется ограниченный перебор управляющих воздействий и предварительная отбраковка некоторых вариантов до их непосредственного расчета. [24]
Блок расчета оптимальных режимов линейного участка выполняет функции, аналогичные тем, которые осуществляет блок расчета оптимальных режимов КС. Особенность состоит в том, что время, затрачиваемое на расчет одного варианта, для линейного участка на порядок меньше, чем для КС. В связи с этим нет необходимости строить сложный алгоритм для сокращения числа вариантов с различными управлениями, а допускается перебор всех возможных управлений, как того требует схема динамического программирования. Для действующего газопровода всегда рассматривается только один вариант. [25]
Выбор метода решения определяется, прежде всего, спецификой инженерной постановки задач. Естественно, всегда, когда возможно, целесообразно использовать существующие методы решения задач, в частности стандартные, но часто необходима разработка новых методов. Приведем несколько примеров специальной разработки или модификации методов решения математических задач применительно к водным проблемам. Метод разгонки невязок [ Левит-Гуревич, 1969 ] был разработан для решения задач гидравлики. Многошаговые схемы динамического программирования находят широкое применение в многочисленных водохозяйственных приложениях. Модификации этой схемы для решения конкретных задач излагаются в последующих главах настоящей монографии. [26]
Так, например, в основе многих моделей лежит представление речной сети в виде графов специальной структуры - входящего дерева. Применению схем динамического программирования не препятствуют любого вида нелинейности в целевой функции и ограничениях и наличие дискретных переменных. Вычислительная трудоемкость алгоритмов поиска глобального экстремума с заданной точностью не зависит от многоэкстре-мальности получающейся задачи. Ограничительные предположения состоят в аддитивности целевой функции, сепарабельности ( отделимости) всех ограничений и технических условий отбраковки вариантов по шагам расчетной схемы. Кроме того, схема динамического программирования реализуема лишь тогда, когда параметр состояния системы на каждом шаге условной оптимизации имеет размерность не выше трех. Это ограничение, к сожалению, часто оказывается наиболее существенным. Так, например, в задачах оптимального выбора водоохранных мероприятий применение рассматриваемой схемы возможно только при учете не более трех независимых видов 3В, либо требует перехода к интегральным показателям качества воды. [27]
В случае, когда конфигурация газотранспортной системы не может быть сведена к моделям газопровода-цепочки, расчетные алгоритмы усложняются. Каждая нитка на проход приводит к появлению цикла на графе, имитирующем структуру трубопроводной системы. Это значит, что на распределение давлений накладывается еще одно ограничение в виде равенства как следствие второго закона Кирхгофа. Формально появление этого ограничения можно обойти, введя еще одну фазовую координату, например, поправочный расход по циклу. Как известно, увеличение числа фазовых координат приводит к быстрому росту объема вычислений. Практически нежелательно пользоваться схемами динамического программирования с количеством фазовых координат 4 и более. Однако даже двумерные схемы позволяют существенно расширить круг практических задач моделирования газотранспортных систем. К таким схемам сводятся все важнейшие задачи поиска оптимальных режимов на многониточных коридорах. Полное описание методов опускается, так как оно потребовало бы развернутого изложения технологических и алгоритмических деталей. [28]
После решения задачи размещения модулей возникает задача построения оптимальных связывающих сетей для электрических цепей устройств. Электрическая цепь объединяет множество контактов модулей устройства. Ограничения на выбор сети задаются обычно допустимым числом паек к контактам. В [110] задача построения кратчайшей связывающей сети с ограничением на число ветвей, входящих в каждый узел сети, сводится к задаче целочисленного программирования. Для ее решения предлагается использовать схему динамического программирования. Иногда после решения задачи трассировки приходится корректировать размещение модулей. [29]
Страницы: 1 2