Общая теория.

Министерство образование и науки Российской Федерации

Московский Авиационный Институт

(Национальный Исследовательский Университет)

Факультет № 1: ”Авиационная техника”.

Кафедра: “Внешнее проектирование

И эффективность авиационных

комплексов”.

Специальность: ”Моделирование и

Исследование операций в

организационно – технических системах”.

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

По предмету: «Технологии системного моделирования».

На тему: “Решение целочисленной задачи нелинейного программирования методом динамического программирования”.

Выполнил: студент гр. 01-316

Шеленков Антон Викторович

Проверил: Горлов Валентин

Михайлович

Москва

Содержание

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

2.Общая теория…….……………………………………….…………..3 стр.

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

4.Решение многошаговых (многоэтапных) задач оптимизации

методом ДП.....................................................................................7 стр.

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

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

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

F(

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

j=1,2…,J.

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

N=12	J=3
=	0.265	=	0.366
=	0.565	=	0.166
=	0.365	=	0.566

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

Общая теория.

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

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

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

С процессом изменения состояния s системы обычно связана некоторая оценка, выраженная числом с помощью критерия Q, который зависит от состояния системы s и принятого управления u. Для постановки задачи оптимизации необходимо ещё учесть условие, накладываемые на начальное состояние и конечное состояние . В простейшем случае оба эти состоянии полностью заданы. В других задачах эти состояния могут быть ограниченны заданием области начальных данных (состояний) и конечных состояний

В общем виде задача оптимального управления формируется следующим образом: из множества возможных уравнений u найти такое уравнение u*, которое переводит систему из начального состояния > так, чтобы критерий Q(s,u) принимал максимальное значение. Специфика метода ДП заключается в том, что задача отыскания u* управляемый процесс разделяется на ряд последовательных «этапов» (шагов). Решение многих задач существенно упрощается, если процесс развёрнут поэтапно, то есть методом ДП. Идея метода, его сущность, заключается в том, чтобы отыскание максимума сложной функции многих переменных свести к операции последовательных максимизаций функций одной переменной, то есть вместо того, чтобы один раз решать сложную задачу мы предпочитаем много раз решать задачу относительно простую.

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

Общее правило формирования управления таково: в процессе многошагового планирования управление на каждом шаге должно приниматься с учётом будущего. Однако среди всех шагов существует такой, на который это правило не распространяется. Последний шаг, единственный из всех, можно планировать так, чтобы он приносил наибольшее приращение критерия Q. Спланировав его оптимальным образом, можно «пристроить» к нему предпоследний, к этому, в свою очередь, предпоследний и т.д.. Поэтому процесс ДП удобно разворачивать в возвратном времени, то есть с конца процесса к началу. ОУ зависит от того, какое возможное состояние было на предпоследнем шаге. Выбирать такое управление, которое переводило бы систему в конечное состояние s(N) и при этом позволяло бы получить максимальное приращение функции Q. Таким образом мы получаем, что последний шаг спланирован для любого исхода последнего шага. Планирование на n-1 шаге зависит от того, какие состояния были получены на предыдущих шагах. Планирование управления в динамическом программировании зависит от того, какие управления были выбраны на предыдущих шагах u(1),u(2),u(3),…,u(N).

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

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

Дата добавления: 2015-12-08