26494

Применение метода динамического программирования в задачах принятия решений

Реферат

Менеджмент, консалтинг и предпринимательство

Концептуально динамическое программирование применяется для анализа систем которые характеризуются следующими признаками: процесс функционирования системы включает последовательные этапы текущие этапы i конечный этап m. предполагается что для системы выполняется принцип отсутствия последействия. Суть этого принципа заключается в том что состояние Si зависит только от состояния системы на предыдущем этапе то есть на Si1 а так же зависит от управляющего воздействия Ui. И не зависит от предыдущих состояний системы и предыдущих...

Русский

2013-08-18

26.55 KB

55 чел.

4

Применение метода динамического программирования в задачах принятия решений.

1. Основные понятия и определения.

2. Общая схема решения функционального уравнения Беллмана.

1. Основные понятия и определения метода динамического программирования.

Динамическое программирование представляет собой совокупность процедур, используемых для оптимизации многошаговых процессов принятия решений. Вопросы динамического программирования были освещены в работах известных ученых (Вальда, Гирши), однако основной вклад в развитие теории многошаговых процессов внес американский математик Ричард Эрнст Беллман.

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

- процесс функционирования системы включает последовательные этапы, текущие этапы i, конечный этап m.

- на i-м шаге управляющее воздействие переводит систему из состояния Si-1, которое достигнуто на i-1 этапе в состояние Si.

- предполагается, что для системы выполняется принцип отсутствия последействия. Суть этого принципа заключается в том, что состояние Si зависит только от состояния системы на предыдущем этапе, то есть на Si-1, а так же зависит от управляющего воздействия Ui. И не зависит от предыдущих состояний системы и предыдущих управляющих воздействий.

- так же известна частная целевая функция или локальная Wi(Si, Ui), которая определяет значение критерия оптимальности, получаемого при применении на i-м этапе управляющего воздействия Ui и при нахождении системы в состоянии Si.

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

Таким образом, при решении задач методом динамического программирования необходимо найти такой вектор управлений u=(u1,…uium), который обеспечит максимизацию суммарного критерия оптимальности.

Понятия таких терминов динамического программирования как этап, состояние системы, управляющее воздействие и локальный критерий оптимальности зависят от предметной ориентации системы. Для организационно-экономических систем в качестве этапов могут выступать интервалы планирования (год, квартал, месяц). В качестве состояний могут выступать наличие свободных финансовых средств на каждом этапе. Управляющее воздействие может быть представлено возможными вариантами инвестирования финансовых средств на каждом этапе. Локальный критерий оптимальности или локальный доход – это может быть прибыль, получаемая на каком-то этапе. Суммарный критерий оптимальности – это суммарная прибыль.

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

Для решения задач принятия решений методом динамического программирования может быть использовано два подхода:

- Первый подход предполагает, что одновременно находятся компоненты вектора управления для всех компонентов решения. Это метод глобальной оптимизации. Этот метод имеет существенный недостаток, который заключается в том, что при большой размерности вектора управления, существенно возрастают объем и трудоемкость вычислений.

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

Классическая идея динамического программирования основана на реализации алгоритма обратной прогонки. W=

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

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

2. Общая схема решения функционального уравнения.

Суть принципа Беллмана состоит в следующем:

Каково бы ни было состояние системы на i-м этапе, управляющее воздействие должно быть выбрано из условия, что на последующих этапах управление будет оптимальным. Дословно формулировка предложенная Беллманом звучит следующим образом: оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояния и решения в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния полученного в результате первого решения.

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

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

Первое понятие: этапы – количество этапов конечно. Качественное определение этапа зависит от природы системы и эти этапы связаны с процессом временной либо логической последовательности принятия решения.

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

Управление: это целенаправленное управляющее воздействие на i-м этапе принятия решения.

Условное оптимальное управление – наилучшая стратегия для каждого из состояний.

Оператор перехода – определяет условия перехода из одного состояния в другое, из состояния S в состояние S. S=

Локальный критерий оптимальности – это значение критерия оптимальности (величина прибыли), получаемое от функционирования системы на i-м этапе при условии, что система находилась в состоянии S и была выбрано управляющее воздействие Ui.

Условный суммарный критерий оптимальности – это значение критерия оптимальности (суммарный оптимальный доход), полученный от функционирования системы на i, i+1 и т.д. этапах работы.

Таким образом, с учетом принятых определений суммарный критерий оптимальности на i-м этапе для состояния S – это максимум суммы локального критерия.

В соответствии с алгоритмом обратной прогонки, решение функционального уравнения начинается с последнего этапа принятия решения, то есть полагается, что i=m. Тогда суммарная оптимальность будет определяться выражением.

В результате решения уравнения находится условное оптимальное управление для каждого состояния Um(S) и условный критерий оптимальности W(S). Найденные значения управляющего воздействия используются для решения функционального уравнения Беллмана при i=m-1.

 

В результате решения уравнения находится условное оптимальное управление Um(S) и условный критерий оптимальности W(S) на m-1 этапе. Таким образом, последовательное решение уравнения Беллмана позволяет определить пары условных оптимальных воздействий и условных оптимальных критериев на каждом шаге.

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

– переход из 0-го в 1-е состояние

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

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

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

- оператор обратного перехода устанавливающий состояние предыдущего этапа. Если провести аналогию с графом при разработке, то алгоритм прямой прогонки основан на том, что рассматриваются дуги, кратчайшие пути для которых известны.


 

А также другие работы, которые могут Вас заинтересовать

36372. Методы формализации управленческих задач 16.83 KB
  методы формализации управленческих задач Проблемы разработки внедрения и эксплуатации АСУ имеют множество задач. Однако одним из важнейших вопросов их создания является выбор или разработка вновь методов формализации управленческих задач обеспечивающих выявление из бесчисленного множества допустимых решений оптимального или определенно эффективного решения. Кроме того цель формализации передача производства решения экономических задач АСУ. Методы формализации решения экономических задач представлены широким классом математических...
36373. Цифровые регуляторы. Достоинства. Структурная схема 34.77 KB
  Структурная схема состоит из входного устройства I вычислительного устройства II выходного устройства III входное устройство представляет собой совокупность блоков и включает в себя: АД – аналоговый датчик АЗ – аналоговый задатчик АО – блок аналоговых отклонений АЦП – аналогоцифровой преобразователь. Выходным сигналом является сигнал в цифровом коде Х [nT] который подается на вход вычислительного устройства. На выходе ВУ выдают управляющие воздействия Y[nТ] в цифровой форме которая поступает на вход выходного устройства.
36374. Чертежи общих видов щитов, пультов систем автоматизации. Правила выполнения 26.86 KB
  Чертеж общего вида единичного щита содержит следующие элементы: авид спереди фасадная плоскость; бвид на внутренние плоскости; втехнические требования; гтаблицу надписей табло и в рамках; дтаблицы для монтажа электрических и трубных проводок; еперечень составных частей; жосновную надпись и дополнительные графы. Чертеж общего вида составного щита содержит: вид спереди фронтальная плоскость; перечень составных частей; основную надпись и дополнительные графы. На чертежах общего вида щиты изображаются в следующих масштабах: 1:10...
36375. Моделирование как способ изучения, прогнозирования поведения и отображения объектов. Типы объектов. Виды моделирования 11.57 KB
  Существует два класса моделей: 1 физические которые представляют собой установки устройства воспроизводящие в том или ином масштабе исследуемый объект при сохранении физического подобия объекта. 2 абстрактные модели в них производится описание объекта на какомлибо языке как то речь чертеж схема математика. Совокупность математических соотношений описывающих характеристики объекта называется математической моделью объекта. Математическая модель отображает алгоритм функционирования объекта.
36376. ПИД – регулятор 31.47 KB
  Пропорциональная составляющая формирует на выходе управляющее воздействие пропорциональное ошибке Е. Дифференциальная составляющая формирует воздействие пропорциональное скорости изменения ошибки обеспечивает минимальное быстродействие ошибка Е по модулю всегда больше нуля. Интегральная составляющая формирует управляющее воздействие пропорционально площади ошибки т. Пропорциональная составляющая вырабатывает выходной сигнал противодействующий отклонению регулируемой величины от заданного значения наблюдаемому в данный момент времени.
36377. Прикладные программы 12.43 KB
  Прикладные программы предназначены для обработки данных пользователей ЭВМ. С помощью прикладных программ осуществляется решение: как отдельных задач так и системы взаимосвязанных задач. Область применения прикладных программ все отрасли человеческой деятельности. Эти программы находятся в постоянном развитии и расширении особенно в направлении применения оптимизирующих алгоритмов и представляются не в виде некоторого одного универсального комплекса а нескольких каждый из которых представлен совокупностью программ для разрешения вполне...
36378. Принцип действия пирометров спектрального отношения 125 KB
  Пирометры спектрального отношения измеряют цветовую температуру объекта по отношению интенсивностей излучения Еλ1 и Еλ2 в двух определенных участках спектра каждый из которых характеризуется эффективной длиной волны λ1 и λ2.Следовательно осуществив в приборе операцию логарифмирования можно свести измерение отношения интенсивностей излучения к измерению разности их логарифмов. Каждой температуре соответствует определенная длина волны на которой интенсивность излучения максимальна. В цветовых пирометрах определяется отношение интенсивности...
36379. Состав САПР. Компоненты видов обеспечения САПР 45.5 KB
  Составными частями САПР жестко связанными с организационной структурой проектной организации являются подсистемы в которых при помощи специализированных комплексных средств решается последовательность задач проектирования. Проектирующие подсистемы имеют объектную ориентацию и реализуют определенный этап проектирования или группы непосредственно связанных проектных задач например эскизное проектирование изделий проектирование корпусных деталей проектирование ТП механической обработки. Компоненты видов обеспечения Средства...
36380. Схемы внешних электрических и трубных проводок. Основные требования и правила выполнения 36 KB
  Схемы внешних электрических и трубных проводок. Схема соединений внешних проводок это комбинированная схема на которой показывают электрические и трубные связи между приборами и средствами автоматизации установленными на технологическом оборудовании вне щитов и на щитах а также подключения проводок к приборам и щитам. Схему подключения допускается не выполнять если все подключения могут быть показаны на схеме соединений внешних проводок. При необходимости раздельного изображения электрических и трубных проводок цеха участка...