Общая постановка задачи динамического программирования

Основные данные о работе

Версия шаблона	2.1
Вид работы	Творческое эссе
Название дисциплины	Моделирование систем
Тема	Общая постановка задачи динамического программирования
Фамилия
Имя
Отчество
№ контракта

 

Основная часть

Общая постановка задачи динамического программирования

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

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

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

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

Очевидно, выигрыш зависит от управления: W = W(U).

Мы хотим найти такое управление (оптимальное) U = u, при котором выигрыш  максимален:      

То из управлений, при котором  достигается этот максимум, и есть оптимальное управление u.  

Таким образом, поставлена общая задача оптимизации управления физической системой. Однако она поставлена еще не полностью. Обычно в таких задачах должны быть учтены некоторые условия, накладываемые на начальное состояние системы S0 и конечное состояние Sw.

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

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

Тот факт, что начальное состояние  системы S0, входит в область, мы будем  записывать с помощью принятого  в математике «знака включения», аналогично для конечного состояния системы. Таким образом, общая задача оптимального управления формулируется следующим:

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

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

На  окончательной стадии определяется для каждого шага окончательное (безусловное) оптимальное управление. Предварительная (условная) оптимизация производится по шагам, в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация – также по шагам, но в непосредственном порядке: от первого шага к последнему. Из двух стадий оптимизации естественно более важной и трудоемкой является первая. После окончания первой стадии. Выполнение второй трудности не представляет: остается только «прочитать» рекомендации, уже заготовленные на первой стадии. В основе поэтапной процедуры лежит принцип оптимальности, который состоит в следующем: Каким бы ни было состояние S системы в результате какого-то числа шагов, мы должны выбрать управление на ближайшем шаге так, чтобы оно, в совокупности с оптимальным управлением на всех следующих шагах, приводило к максимальному выигрышу на всех оставшихся шагах, включая данный. При решении любой задачи динамического программирования удобно придерживаться навсегда установленного, стандартного порядка действий. Этот порядок можно установить в такой форме. Выбирая способ описания процесса, т. е. параметров, характеризующих состояние системы, фазового пространства и способа разделения операции на «шаги». Записать выигрыш на i-м шаге в зависимости от состояния системы S в начале этого шага и управления Ui. wi = wi(S, Ui). Записать для i-го шага функцию, которая выражает изменение состояния системы от S к S’ под влиянием управления Ui: S’ = ji(S, Ui). Записать основное функциональное уравнение, выражающее функцию Wi(S) через Wi+1(S). Найти функцию Wm(S) (условный оптимальный выигрыш) для последнего шага. Максимум берется только по тем управлениям, которые приводят систему в заданную область конечных состояний и соответствующее ей условное оптимальное управление на последнем шаге: um(S). Зная Wm(S) и используя уравнение при конкретном виде функций wi(S, Ui), ji(S, Ui) найти одну за другой функции и соответствующие им условные оптимальные управления. Если начальное состояние S0 задано, найти наибольший выигрыш и далее безусловные оптимальные управления. Если начальное состояние S0 не задано, а только ограничено условием, найти оптимальное начальное состояние S0, при котором выигрыш, W1(S) достигает максимума и далее, по цепочке, безусловные оптимальные управления.

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

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

Предположим, что интересующий нас процесс можно разбить на N шагов, а действия, совершаемые на i-ом шаге, характеризуются совокупностью показателей. Состояние процесса к началу этого шага имеет характеристику в виде набора параметров. Обычно предпринимаемые действия не являются полностью произвольными, а зависят от состояния, которое возникло перед i-тым шагом, т.е. Очевидно, результирующее значение критерия Z, получаемое в конце процесса, будет определяться теми, которые были приняты, т.е. Возникает вопрос: Как выбрать, чтобы величина Z приняла экстремальное значение? Ответ можно получить, рассматривая Z как функцию переменных и находя экстремум z одним из известных способов, однако этот путь не всегда прост (особенно при большом числе переменных).

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

Динамическое программирование основывается на двух важных принципах оптимальности и вложения.

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

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

Реализация названных принципов  дает гарантию того, что, во-первых, решение, принимаемое на очередном шаге, окажется наилучшим с точки зрения всего  процесса (а не «узких интересов» отдельного этапа). Во-вторых, последовательность решений одношаговой, двух шаговой и т. п. задач приведет к решению исходной N-шаговой задачи.

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

Продать машину и заменить ее новой;

Ремонтировать ее и продолжать эксплуатацию;

Продолжать эксплуатацию без ремонта.

Шаговое управление – выбор одного из этих трех решений. Непосредственно  числами они не выражаются, но можно  приписать первому численное  значение 1, второму 2, третьему 3. Какие  нужно принять решения по годам (т.е. как чередовать управления 1, 2, 3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение готовых машин были минимальны?

Показатель эффективности (в данном случае это не "выигрыш", а "проигрыш", но это неважно) равен        ,    где wj – расходы в j-м году. Величину W требуется обратить в минимум.

Управление операцией в целом  представляет собой какую-то комбинацию чисел 1, 2, 3, например: х=(3,3,2,2,1,3…….), что  означает: первые два года – эксплуатировать  машину без ремонта, последующие три года – ее ремонтировать, в начале шестого года – продать, купить новую, затем снова эксплуатировать без ремонта и т.д. Любое управление представляет собой вектор (совокупность чисел)

х=(j1, j2……jm), где каждое из чисел j1, j2, ..., jm имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел, при которой величина минимальна.

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

 

Список использованных интернет-ресурсов

№ п/п	Наименование интернет-ресурса	Ссылка на конкретную используемую страницу интернет-ресурса
1	Электронный учебник  "Экономико-математические методы"	http://www.math.mrsu.ru/text/courses/method/dinamicheskoe_programmirovanie1.htm
2	Научная библиотека избранных естественно-научных  изданий	http://stu.sernam.ru/book_rop.php?id=29
3	Академик	http://dic.academic.ru/dic.nsf/ruwiki/117498