Динамическое программирование

Курсовая работа

по дисциплине «Введение в исследование операций»

на тему: «Динамическое программирование»

Вариант 2821

 

Выполнила: Федорова А.А.

Гр. 1О-307Б

Проверил: Горлов В.М.

 

Москва

Содержание.

1. Постановка задачи…………………………………………….……………3

2. Динамическое программирование……………………………….………..4

3. Принцип оптимальности Беллмана………………………..……………...7

4. Решение многошаговых задач оптимизации методом динамического программирования………………………………………………………...12

5. Пример решения задачи оптимизации методом динамического программирования………………………………………………………...16

6. Задача распределения ресурсов…....……………………………………..18

7. Алгоритм……………………………………………………...……………19

8. Текст программы……….………………………………………………….21

9. Контрольный расчет……………………………………………………….24

10. Применение программы для исходной задачи.…………………………25

 

Постановка задачи

Составить оптимальный план использовании однотипных поисковых средств, если задана вероятность обнаружения объекта в – ом районе одним поисковым средством. Известно, что объект может находиться в одном из районов поиска с вероятностью .

Пусть – количество средств, назначаемых в –й район поиска.

В этом случае вероятность обнаружения объекта - ом районе

, а математическое ожидание обнаружения объекта определяется

Необходимо максимизировать при ограничениях:

Исходные данные:

N = 12	J = 3
	0.291		0.496
	0.192		0.297
	0.893		0.198

 

Для проверки сделать контрольный расчет для варианта(из лекций).

Сделать расчеты для заданного , для и .

Результаты свести в таблицу.

Динамическое программирование

Сущность динамического программирования:

В 50-х годах прошлого века был развит новый общий метод решения оптимизационных задач, названный динамическим программированием (ДП).

Динамическое программирование представляет собой математический метод оптимизации решений для исследования многошаговых (многоэтапных) операций.

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

Будем считать, что система из одного состояния в другое переходит под воздействием некоторого управления. Обозначим управление (всю систему мероприятий, с помощью которой система меняет свое состояние во времени), вектором .

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

.

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

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

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

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

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

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

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

Оптимальное управление на последнем шаге заключается в том, что для любого из возможных состояний на предпоследнем шаге выбрать такое управление, которое переводило бы систему в конечное состояние S(N) и при этом позволяло бы получить максимальное приращение функции . На последнем N-ом шаге необходимо сделать всевозможные предположения о том, чем закончится N-1 шаг. Идея каждого из этих состояний выбрать управление на последнем шаге. Пусть планируется N шаговая операция и неизвестно чем закончится N-1 шаг, то мы делаем предложение о возможных состояниях системы в конце N-1 шага. Под буквой S упоминается не обязательно одно число, это может быть целая группа характеристики системы. Это значит, что последний шаг спланирован для любого исхода предпоследнего шага. Далее к предпоследнему пристыковывается еще к более предпоследний и процесс повторяется.

Таким образом, сущность подхода динамического программирования состоит в следующем: данная конкретная задача управления «погружается» в более широкий класс задач, которые характеризуются рядом параметров; затем с помощь принципа оптимальности Беллмана составляется основное рекуррентное соотношение, связывающее задачи из этого класса. Если выполнены некоторые дополнительные предположения, относительно гладкости участвующих в рассмотрении функций, то из главного рекуррентного соотношения вытекает основное дифференциальное уравнение в частных производных - уравнение Беллмана, решая которое, можно найти решение широкого класса задач.