Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по ТПР - файл Лекция№10-тпр.doc


Загрузка...
Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№10-тпр.doc

Реклама MarketGid:
Загрузка...
Лекция № 10.

Метод динамического программирования.

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

Рассмотрим функционирование некоторого объекта в течение промежутка времени Т. Пусть в момент времени tj состояние объекта характеризуется вектором , причем в начальный момент времени t1 состояние объекта задано, т.е. вектор известен. Объект меняет свое состояние под воздействием управления в моменты времени . При этом управляющее воздействие выбирается из заданной области , т.е.

(1)

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

. (2)

Здесь - заданная функция своих аргументов. Уравнение (2) является уравнением движения объекта, т.е. описывает динамику объекта во времени.

Обозначим -выигрыш, получаемый от функционирования объекта на j-м участке времени, т.е. в полуинтервале . Если в момент времени , когда объект находился в состоянии выбрать управление , то объект перейдет в состояние . Далее последовательно можно выбирать в соответствии с (1) , в из (2) определять . Этим значениям и будет соответствовать вполне определенное значение дохода:

(3)

Если выбирать другие значения управляющих воздействий, то им будут соответствовать другие состояния объекта, а следовательно, и другое значение общего дохода (3). Поэтому естественно поставить следующую оптимизационную задачу:

(4)

. (5)

(6)

- задан. (7)

Здесь необходимо найти неизвестные и , которые удовлетворяли бы ограничениям (5)-(7) и максимизировали бы целевую функцию (4).

Эта задача является в общем случае задачей нелинейного программирования и обладает следующими особенностями:

  1. Искомые переменные разбиты на N групп, в каждую j-тую из которых входят только и .

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

  3. Уравнение (5) является рекуррентным, т.е. через значения и однозначно определяется .

Многие реальные задачи ИСО сводятся к ММ вида (4)-(7), которая допускает различные интерпретации.

Решение задачи вида (4)-(7) обычными методами оказывается либо невозможным, либо неэффективным из-за большой размерности. Поэтому ее решение сводится к последовательному решению N связанных между собой задач меньшей размерности. Для выявления этих задач и связей между ними рассмотрим задачу вида (4)-(7), соответствующую последним этапам . Она запишется в виде:

(8)

. (9)

(10)

- фиксирован. (11)

В этой задаче мы не знаем, чему равно конкретное значение , но если его зафиксировать, то получим соответствующее максимальное значение (8). Если зафиксировать другое значение , то естественно максимальное значение целевой функции (8) будет другим. Обозначим максимальное значение целевой функции (8)при некотором зафиксированном через :



Запишем это равенство в виде:

(12)

Здесь первое слагаемое не зависит от , а вторая сумма функций зависит от . Поэтому выражение (12) можно переписать в виде:



Таким образом окончательно запишем:

(13)

Данное соотношение справедливо для всех , а для имеем:

(14)

Полученные рекуррентные соотношения являются основными соотношениями МДП. Это так называемые соотношения Беллмана. Они позволяют свести решение ЗНП (4)-(7) к последовательному решению N задач максимизации меньшей размерности.

Соотношение (13) позволяет вычислить , если известно , а (14) позволяет вычислить максимальное значение целевой функции на последнем этапе. Тогда рекуррентный процесс решения задачи (13)-(14) должен проводиться в порядке . Действительно, зная из (13) можно найти значения и т.д.

Рассмотрим алгоритм решения такой задачи.

1 шаг. Решается задача (14):

.

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

2 шаг. На этом шаге решается задача (13) при :



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

Далее, зная , решается задача (13) для . Наконец, при переходим к шагу N:

N шаг. , . На этом шаге решается только одна задача оптимизации, т.к. - задан. В результате получим точку максимума и значение .

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

1 шаг: ; .

2 шаг: ; .

3 шаг: ; .



N шаг: ; .

.

Таким образом, определяется решение исходной ЗНП (4)-(7) как , при этом максимальное значение целевой функции (4) будет равно значению .

^ Достоинства метода динамического программирования.

  1. На каждом этапе решается задача поиска экстремума лишь по части переменных, следовательно, размерность этих задач по сравнению с исходной значительно ниже. Это позволяет упростить поиск оптимальных значений искомых переменных.

  2. Метод ДП дает возможность решать задачи, которые не могут быть решены другими методами.

  3. Алгоритм метода ДП легко реализуется на ЭВМ.

Недостатки метода ДП.

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

  2. При большой размерности исходной задачи эти алгоритмы требуют значительных ресурсов ЭВМ.



Скачать файл (681.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru