- •Математическое моделирование в экономике
- •Тема 1. Математические модели в экономике
- •§1. Общие понятия
- •§2. Этапы экономико-математического моделирования
- •1. Постановка экономической проблемы и ее качественный анализ.
- •4. Подготовка исходной информации.
- •5. Численное решение.
- •6. Анализ численных результатов, их интерпретация и применение.
- •§1. Экономические ряды динамики
- •Тема 2. Моделирование экономической динамики
- •§2. Предварительный анализ и сглаживание временных рядов экономических показателей
- •§3. Расчет показателей динамики развития экономических процессов
- •§4. Тренд-сезонные экономические процессы и их анализ
- •ТЕма 3. ЛИнейное программирование
- •§1. Понятие линейного программирования
- •§2. Графический способ решения злп
- •§3. Симплексный метод
- •§4. Двойственность задач
- •§5. Транспортная задача
- •Тема 4. Нелинейное программирование
- •§1. Задача нелинейного программирования
- •§2. Метод множителей Лагранжа
- •§3. Градиентные методы
- •§4. Теорема Куна - Таккера
- •Тема 5. ДИнамическое программирование
- •§1. Основные понятия
- •§2.Особенности задач динамического программирования
- •§3. Принципы динамического программирования
- •§4. Функциональные уравнения Беллмана
§2.Особенности задач динамического программирования
1. Рассматривается система, состояние которой на каждом шаге определяется вектором xt. Дальнейшее изменение ее состояния зависит только от данного состояния xt и не зависит от того, каким путем система пришла в него. Такие процессы называются процессами без последействия.
2. На каждом шаге выбирается одно решение ut, под действием которого система переходит из предыдущего состояния xt-1 в новое xt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале интервала решения ut, т.е.
3. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
4. На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений u принадлежит Ω.
5. Требуется найти такое допустимое управление ut для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.
Любую допустимую последовательность действий для каждого шага, переводящую систему из начального состояния в конечное, называют стратегией управления. Допустимая стратегия управления, доставляющая функции цели экстремальное значение, называется оптимальной.
Управление — это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или Хт,, которой эти точки принадлежат. Тогда допустимые управления переводят точки из области Хо в ХТ.
Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Хо и оканчивающуюся в области ХТ, для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.
§3. Принципы динамического программирования
Принцип оптимальности и погружения. Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами ut и находить экстремум целевой функции одним из существующих методов оптимизации, т. е. искать сразу все элементы решения на всех N шагах. Отметим, что этот путь не всегда приводит к цели, особенно когда целевая функция задана в виде таблиц или число переменных очень велико.
Второй путь основан на идее проведения оптимизации поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. Наоборот, управление на каждом шаге выбирается с учетом всех его последствий. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса в целом. Лучше много раз решать сравнительно простую задачу, чем один раз - сложную.
Таким образом, одним из условий применимости метода динамического программирования является возможность разбиения процесса оптимизации решения на ряд однотипных шагов (этапов), каждый из которых планируется отдельно, но с учетом состояния системы на начало этапа и последствий принятого решения. Однако из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без учета последствий. Это последний шаг. Он может быть изучен и спланирован сам по себе наилучшим (в смысле выбранного критерия) образом, поскольку за ним нет больше этапов. Отсюда получаем одну из специфических особенностей динамического программирования: всю вычислительную процедуру программирования целесообразно разворачивать от конца к началу. Раньше всех планируется последний N-й шаг, за ним (N-1)-й и т. д. Но как найти оптимальное управление иN на N-м шаге, если оно определяется не только целью управления, но и состоянием системы на начало этого шага? Сделать это можно на основе предположений об ожидаемых исходах предшествующего, но еще не исследованного этапа, т.е. о значениях xN-1.
Для каждого возможного исхода xN-1 на (N — 1)-м этапе находим оптимальное управление на N-м этапе. Такой набор оптимальных управлений, зависящих от возможных исходов предыдущего этапа, называется условно-оптимальным решением u*n(xn-i). Завершив анализ конечного этапа, рассматривают аналогичную задачу для предпоследнего этапа, требуя, чтобы функция цели достигала экстремального значения на двух последних этапах вместе. Это дает условно-оптимальное решение на предпоследнем этапе u*n-1(xn-2), т. е. делаются всевозможные предположения о том, чем кончился предыдущий (N-2)-й шаг, и для каждого из предположений находится такое управление на (N - 1)-м шаге, при котором эффект за последние два шага (из них последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого исхода (N - 2)-го шага условно-оптимальное управление на (N — 1)-м и условно-оптимальное значение функции цели на последних двух шагах. Проделав такой поиск условно-оптимальных управлений для каждого шага от конца к началу, найдем последовательность условно-оптимальных управлений u1*(xo), u2*(x1),... ,u*N(xN-1).
Условно-оптимальные управления дают возможность найти не условное, а просто оптимальное управление на каждом шаге.
В процессе оптимизации управления методом динамического программирования многошаговый процесс проходится дважды. Первый раз от конца к началу, в результате чего находятся условно-оптимальные управления и условно-оптимальное значение функции цели для каждого шага, в том числе оптимальное управление для первого шага и оптимальное значение функции цели для всего процесса. Второй раз - от начала к концу, в результате чего находятся уже оптимальные управления на каждом шаге с точки зрения всего процесса. Первый этап сложнее и длительнее второго, на втором остается лишь отобрать рекомендации, полученные на первом. Следует отметить, что понятия "конец" и "начало" можно поменять местами и разворачивать процесс оптимизации в другом направлении. С какого конца начать – диктуется удобством выбора этапов и возможных состояний на их начало.
Из качественного анализа идеи поэтапной оптимизации можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип оптимальности и принцип погружения.
Принцип оптимальности. Оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления. Или в развернутой форме: оптимальная стратегия обладает таким свойством, что, каковы бы ни были начальное состояние и начальные решения, последующие решения должны приниматься исходя из оптимальной стратегии с учетом состояния, вытекающего из первого решения. Этот принцип имеет довольно простую математическую интерпретацию, выражающуюся в составлении определенных рекуррентных соотношений (функциональных уравнений Р. Беллмана).
Принцип погружения. Природа задачи, допускающей использование метода динамического программирования, не меняется при изменении количества шагов N, т. е. форма такой задачи инвариантна относительно N. В этом смысле всякий конкретный процесс с заданным числом шагов оказывается как бы погруженным в семейство подобных ему процессов и может рассматриваться с позиции более широкого класса задач.
Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшим относительно всего процесса в целом, а не узких интересов данного этапа.
