МЕТОДЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Область применения. Метод используется для решения задач математического программирования, позволяющих представлять их в виде нескольких менее сложных подзадач с одной целевой функцией.
Метод особенно эффективен для задач, условия которых позволяют составить сетевой график перехода от этапа к
361 этапу, где узлы сети будут соответствовать различным значениям переменных, а дуги — допустимым вариантам решения [51].
Особенности применения. Основным принципом положенным в основу метода динамического программирования является принцип оптимальности, суть которого заключается в том, что каждое последующее решение строится оптимальным образом независимо от решений, получаемых на всех предыдущих этапах, кроме последнего. Чтобы реализовать этот принцип, необходимо в исходной задаче определить [42]:
¦ этапы решений (подзадачи, на которые она декомпозируется);
¦ управляемые переменные (варианты решений) на каждом этапе;
¦ информацию для решения задачи на каждом этапе;
¦ рекуррентные вычислительные процедуры, связывающие соседние этапы.
Другими словами, в методе динамического программирования искусственно создаются условия для независимой оптимизации на отдельном этапе по результатам только предыдущего, причем с гарантией того, что полученное решение будет находиться в области допустимых.
Наиболее употребительные методы. Различают прямые и обратные методы оптимизации. Они отличаются друг от друга различным представлением переменной и видом рекуррентных соотношений [51].
МЕТОДЫ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Область применения. Методы используются для задач, в которых все или отдельные параметры описываются с помощью случайных величин. Задачи стохастического программирования возникают тогда, когда каждое действие приводит к неоднозначному исходу и с каждым решением можно связать числовые параметры целевой функции f?X, О), s = 0, 1, т. При этом параметры fs(X, 0) зависят от конкретного решения X и состояния среды 0. В стохастическом программировании 0 является элементарным событием некоторого вероятностного пространства.
Особенности применения. Общий подход для решения подобного класса задач заключается в оптимизации некоторой вторичной целевой функции, представляющей собой какую-нибудь стохастическую (вероятностную) характеристику исходной (первичной) функции. В зависимости от вида математической модели (аналитической, вероятностной или статистической) в качестве стохастических характеристик могут использоваться математические ожидания, дисперсии, вероятности либо их оценки. Для неслучайных стохастических характеристик (при известных законах распределения) задача сводится к детерминированной. Если не удается установить аналитическую (формульную) зависимость между параметрами и показателями, то приходится прибегать к методу статистического моделирования (методу Монте-Карло) и с его помощью рассчитывать оценки вторичной целевой функции.
Наиболее употребительные методы. Для решения стохастических задач оптимизации можно использовать градиентные методы, методы стохастического моделирования и стохастической аппроксимации, методы программирования с вероятностными ограничениями.
Похожие рефераты:
