Принцип оптимальности.

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

По дисциплине: теория информационных процессов и систем

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

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

Семестр № 7.

Преподаватель:Александров О.Е.

Студентка гр.ДО 43010 да

г. Алапаевск

Запольских Алевтина Евгеньевна

Екатеринбург 2006

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

Введение

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

Задача оптимального управления.

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

Здесь R (x,u) и F(x) – заданные скалярные функции своих аргументов, N – момент окончания процесса, N>0.При этом функция R может отражать расход средств или энергии на каждом шаге процесса, а функция F – характеризовать оценку конечного состояния системы или точность приведения в заданное состояние.

Задача оптимального управления формулируется как задача определения допустимых управлений u(0), u(1),-,u(N-1), удовлетворяющих ограничениям, и соответствующей траектории, то есть последовательности x(0),x(1),-,x(N), которые в совокупности доставляют минимальное значение.

Минимизация обычно отвечают выбору управления, обеспечивающего наименьшие затраты средств, ресурсов, энергии, наименьшее отклонение от заданной цели или заданной траектории процесса. Наряду с этим часто ставится также задача о максимизации критерия , например о максимизации дохода или объема производства. Однако нетрудно видеть, что максимизация критерия J эквивалентна минимизации критерия (-J). Поэтому простая замена знака у функции R и F приводит задачу о максимизации критерия к задаче о его максимизации.

Элементарный подход.

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

J=R(x0,u(0))+R(f(x0,u(0)),u(1))+_=F(x0,u(0),u(1),_,u(N-1)).

Здесь F – некоторая громоздкая, но, вообще говоря , известная функция своих аргументов. Таким образом,  поставленная задача оптимального управления свелась к задаче о минимизации функции F от векторов u(0),u(1),_,u(N-1), то есть от Nm переменных. При больших N (а обычно представляет интерес именно процессы с большими N) это задача о минимизации функции большого числа переменных .

Принцип оптимальности.

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

Принцип оптимальности легко доказывается от противного. Пусть x(t)=x* - некоторая точка оптимальной траектории, то есть состояние системы вдоль оптимального процесса в момент t, 0<t<<N. Рассуждая от противного, предположим, что отрезок этого процесса от момента времени t до момента N не является оптимальным процессом в смысле критерия качества при начальном условии x(t)=x*. Значит, существует допустимое управление и соответствующая ему траектория, для которых критерий Jt принимает наименьшее значение, чем на исходном оптимальном процессе. На ряду с исходным оптимальным процессом x(k), k=0,1,_,N, процесс состоящий из двух участков: исходного процесса x(k) при k= = 0,1,_,t и «улучшенного» процесса при k= =t+1, _,N. Для этого составного процесса критерий J будет иметь меньшее значение, чем для исходного процесса, так как сумма первых t слагаемых для составного процесса остается той же, что и для исходного процесса, а сумма остальных слагаемых, равна Jt , уменьшится по сравнению с исходным процессом. Данное утверждение означает, что исходный процесс не является оптимальным, а это противоречит сделанному предложению.

Таким образом, принцип оптимальности доказан. Столь простое доказательство наводит на мысль о тривиальности этого принципа. Однако это не так: принцип оптимальности является следствием аддитивности и не имеет места с случае неаддитивного критерия.