Задачи оптимального управления относятся к теории экстремальных задач, то есть задач определения максимальных и минимальных значений. Уже то обстоятельство, что в этой фразе встретилось несколько латинских слов (maximum - наибольшее, minimum - наименьшее, extremum - крайнее, optimus - оптимальное), указывает, что теория экстремальных задач была предметом исследования с древних времен. О некоторых таких задачах писали еще Аристотель (384-322 годы до н.э.), Евклид (III в. до н.э.) и Архимед (287-212 годы до н.э.). Основание города Карфагена (825 год до н.э.) легенда ассоциирует с древнейшей задачей определения замкнутой плоской кривой, охватывающей фигуру максимально возможной площади. Подобные задачи именуются изопериметрическими.
Характерной особенностью экстремальных задач является то, что их постановка была порождена актуальными запросами развития общества. Более того, начиная с XVII века доминирующим становится представление о том, что законы окружающего нас мира являются следствием некоторых вариационных принципов. Первым из них был принцип П. Ферма (1660 год), в соответствии с которым траектория света, распространяющегося от одной точки к другой, должна быть такова, чтобы время прохождения света вдоль этой траектории было минимально возможным. Впоследствии были предложены раз- личные широко используемые в естествознании вариационные принципы, например: принцип стационарного действия У.Р. Гамильтона (1834 год), принцип виртуальных перемещений, принцип наименьшего принуждения и др. Параллельно развивались и методы решения экстремальных задач. Около 1630 года Ферма сформулировал метод исследования на экстремум для полиномов, состоящий в том, что в точке экстремума производная равняется нулю. Для общего случая этот метод получен И. Ньютоном (1671) и Г.В. Лейбницем (1684), работы которых знаменуют зарождение математического анализа. Начало развития классического вариационного исчисления датируется появлением в 1696 году статьи И. Бернулли (ученика Лейбница), в которой сформулирована постановка задачи о кривой, соединяющей две точки А и В, двигаясь по которой из точки А в В под действием силы тяжести материальная точка достигнет В за минимально возможное время.
В рамках классического вариационного исчисления в XVIII-XIX веках установлены необходимые условие экстремума первого порядка (Л. Эйлер, Ж.Л. Лагранж), позднее развиты необходимые и достаточные условия второго порядка (К.Т.В. Вейерштрасс, А.М. Лежандр, К.Г.Я. Якоби), построены теория Гамильтона-Якоби и теория поля (Д. Гиль- берт, А. Кнезер). Дальнейшее развитие теории экстремальных задач привело в XX веке к созданию линейного программирования, выпуклого анализа, математического программирования, теории минимакса и некоторых иных разделов, одним из которых является теория оптимального управления.
Эта теория подобно другим направлениям теории экстремальных задач, возникла в связи с актуальными задачами автоматического регулирования в конце 40-х годов (управление лифтом в шахте с целью наискорейшей остановки его, управление движением ракет, стабилизация мощности гидроэлектростанций и др.). Заметим, что постановки отдельных задач, которые могут быть интерпретированы как задачи оптимального управления, встречались и ранее, например в “Математических началах натуральной философии” И. Ньютона (1687). Сюда же относятся и задача Р. Годдарда (1919) о подъеме ракеты на заданную высоту с минимальными затратами топлива и двойственная ей задача о подъеме ракеты на максимальную высоту при заданном количестве топлива. За прошедшее время были установлены фундаментальные принципы теории оптимального управления: принцип максимума и метод динамического программирования.
Указанные принципы представляют собой развитие классического вариационного исчисления для исследования задач, содержащих сложные ограничения на управление.
Сейчас теория оптимального управления переживает период бурного развития как в связи с наличием трудных и интересных математических проблем, так и в связи с обилием приложений, в том числе и в таких областях, как экономика, биология, медицина, ядерная энергетика и др.
Все задачи оптимального управления можно рассматривать как задачи математического программирования и в таком виде решать их численными методами.
При оптимальном управлении иерархическими многоуровневыми системами, например, крупными химическими производствами, металлургическими и энергетическими комплексами, применяются многоцелевые и многоуровневые иерархические системы оптимального управления. В математическую модель вводятся критерии качества управления для каждого уровня управления и для всей системы в целом, а также координация действий между уровнями управления.
Если управляемый объект или процесс является детерминированным, то для его описания используются дифференциальные уравнения. Наиболее часто используются обыкновенные дифференциальные уравнения вида. В более сложных математических моделях (для систем с распределёнными параметрами) для описания объекта используются дифференциальные уравнения в частных производных. Если управляемый объект является стохастическим, то для его описания используются стохастические дифференциальные уравнения.
Если решение поставленной задачи оптимального управления не является непрерывно зависящим от исходных данных (некорректная задача), то такая задача решается специальными численными методами.
Система оптимального управления, способная накапливать опыт и улучшать на этой основе свою работу, называется обучающейся системой оптимального управления.
Реальное поведение объекта или системы всегда отличается от программного вследствие неточности в начальных условиях, неполной информации о внешних возмущениях, действующих на объект, неточности реализации программного управления и т.д. Поэтому для минимизации отклонения поведения объекта от оптимального обычно используется система автоматического регулирования.
Иногда (например, при управлении сложными объектами, такими как доменная печь в металлургии или при анализе экономической информации) в исходных данных и знаниях об управляемом объекте при постановке задачи оптимального управления содержится неопределённая или нечёткая информация, которая не может быть обработана традиционными количественными методами. В таких случаях можно использовать алгоритмы оптимального управления на основе математической теории нечётких множеств (Нечёткое управление). Используемые понятия и знания преобразуются в нечёткую форму, определяются нечёткие правила вывода принимаемых решений, затем производится обратное преобразование нечётких принятых решений в физические управляющие переменные.
АННОТАЦИЯ
Настоящее пособие знакомит с основными условиями оптимальности и методами решения задач вариационного исчисления и оптимального управления. Будет полезно для подготовки и проведения практических занятий по разделу "Оптимальное управление", а также при выполнении домашних заданий по этой теме студентами.
Учебное пособие является электронной версией книги:
Оптимальное управление в примерах и задачах. Сотсков А.И., Колесник Г.В. - М.: Российская экономическая школа, 2002 - 58 с.
Предисловие
1. Простейшая задача вариационного исчисления.
Уравнение Эйлера
Примеры
Упражнения
2. Задача оптимального управления. Принцип максимума
Примеры
Упражнения
3. Фазовые ограничения в задаче оптимального управления
Примеры
Упражнения
4. Динамическое программирование и уравнение Беллмана
Примеры
Упражнения
Литература
Предисловие
Теория оптимального управления является одним из разделов курса "Математика для экономистов", читаемого в Российской экономической школе.
Опыт преподавания показывает, что данный раздел - один из наиболее сложных для освоения. Это прежде всего связано с концептуальными отличиями изучаемых в нем задач оптимального управления от задач конечномерной оптимизации, и, как следствие, с существенным усложнением используемых в них условий оптимальности.
В связи с этим представляется полезным дать наглядную иллюстрацию применения данных условий оптимальности к решению задач различных типов. Настоящее пособие и является попыткой дать такую иллюстрацию. В нем содержатся примеры и задачи по четырем темам:
. вариационному исчислению;
. принципу максимума в задачах без ограничений;
. принципу максимума при наличии фазовых ограничений;
. динамическому программированию.
Каждый раздел состоит из теоретической части, описывающей базовые понятия и результаты, используемые при решении соответствующих задач, примеров с решениями, а также задач для самостоятельной работы студентов.
Следует подчеркнуть, что данное пособие ни в коем случае не является теоретическим курсом, а ориентировано прежде всего на практическое применение методов оптимального управления. В качестве теоретического пособия по данному разделу можно порекомендовать, например, книгу.
По мнению авторов, данное пособие будет полезным преподавателям при подготовке и проведении практических занятий по разделу "Оптимальное управление", а также студентам при выполнении домашних заданий по этой теме.
Электронная версия книги : [Скачать, PDF, 633.8 КБ ].
Для просмотра книги в формате PDF требуется программа Adobe Acrobat Reader, новую версию которой можно бесплатно скачать с сайта компании Adobe.
6.2.1. Постановка и классификация задач теории оптимального управления. В подавляющем большинстве рассмотренных нами задач факторы, связанные с изменением изучаемых объектов и систем в течение времени, выносились за скобки. Возможно, при выполнении определенных предпосылок такой подход является конструктивным и правомерным. Однако очевидно и то, что это допустимо далеко не всегда. Существует обширный класс задач, в которых необходимо найти оптимальные действия объекта, учитывающие динамику его состояний во времени и пространстве. Методы их решения составляют предмет математической теории оптимального управления.
В весьма общем виде задача оптимального управления может быть сформулирована следующим образом:
Имеется некоторый объект, состояние которого характеризуется двумя видами параметров - параметрами состояния и параметрами управления, причем в зависимости от выбора последних процесс управления объектом протекает тем или иным образом. Качество процесса управления оценивается с помощью некоторого функционала*, на основе чего ставится задача: найти такую последовательность значений управляющих параметров, для которой данный функционал принимает экстремальное значение.
* Функционалом называется числовая функция, аргументами которой, как правило, служат другие функции.
С формальной точки зрения многие проблемы оптимального управления могут быть сведены к задачам линейного или нелинейного программирования большой размерности, так как каждой точке пространства состояний соответствует свой вектор неизвестных переменных. Все же, как правило, движение в данном направлении без учета специфики соответствующих задач не приводит к рациональным и эффективным алгоритмам их решения. Поэтому методы решения задач оптимального управления традиционно связаны с другим математическим аппаратом, берущим свое начало от вариационного исчисления и теории интегральных уравнений. Следует также заметить, что опять-таки в силу исторических причин теория оптимального управления была ориентирована на физические и технические приложения, и ее применение для решения экономических задач носит в определенном смысле вторичный характер. В то же время в целом ряде случаев модели исследования, применяющие аппарат теории оптимального управления, могут привести к содержательным и интересным результатам.
К сказанному выше необходимо добавить замечание о тесной связи, существующей между методами, применяемыми для решения задач оптимального управления, и динамическим программированием. В одних случаях они могут использоваться на альтернативной основе, а в других довольно удачно дополнять друг друга.
Существуют различные подходы к классификации задач оптимального управления. Прежде всего, их можно классифицировать в зависимости от объекта управления:
Ø Ø задачи управления с сосредоточенными параметрами;
Ø Ø задачи управления объектами с распределенными параметрами.
Примером первых является управление самолетом как единым целым, а вторых - управление непрерывным технологическим процессом.
В зависимости от типа исходов, к которым приводят применяемые управления, выделяют детерминированные и стохастические задачи. В последнем случае результатом управления является множество исходов, описываемых вероятностями их наступления.
По характеру изменения управляемой системы во времени различают задачи:
Ø Ø с дискретно изменяющимся временем ;
Ø Ø с непрерывно изменяющимся временем .
Аналогично классифицируются задачи управления объектами с дискретным или непрерывным множеством возможных состояний. Задачи управления системами, в которых время и состояния меняются дискретно, получили название задач управления конечными автоматами . Наконец, при определенных условиях могут ставиться задачи управления смешанными системами.
Многие модели управляемых систем основаны на аппарате дифференциальных уравнений как в обыкновенных, так и в частных производных. При исследовании систем с распределенными параметрами, в зависимости от вида используемых дифференциальных уравнений в частных производных, выделяют такие типы задач оптимального управления, как параболические, эллиптические или гиперболические.
Рассмотрим два простейших примера задач управления экономическими объектами.
Задача распределения ресурсов. Имеется т складов с номерами i (i ∊1:m ), предназначенных для хранения однородного продукта. В дискретные моменты времени t ∊0:(T -l) происходит его распределение между объектами-потребителями (клиентами) с номерами j , j ∊1:n . Пополнение запаса в пунктах хранения продукта в t -й момент времени определяется величинами a i t , i ∊1:m , а потребности клиентов в нем равняются b j t , j ∊1:n . Обозначим через c t i,j - затраты на доставку единицы продукта из i -го склада j -му потребителю в момент времени t. Также предполагается, что продукт, поступивший на склад в момент t , может быть использован, начиная со следующего момента (t +l). Для сформулированной модели ставится задача найти такой план распределения ресурсов {х t i,j } T m xn , который минимизирует суммарные расходы на доставку потребителям продукции со складов в течение полного периода функционирования системы.
Обозначив через х t i,j количество продукта, поставляемое j -му клиенту с i -го склада в t -й момент времени, а через z t i - общее количество продукта на i -м складе, описанную выше проблему можно представить как задачу нахождения таких совокупностей переменных
которые обращают в минимум функцию
при условиях
где объемы начальных запасов продукта на складах z 0 i = ž i . предполагаются заданными.
Задачу (6.20)-(6.23) называют динамической транспортной задачей линейного программирования . С точки зрения приведенный выше терминологии независимые переменные х t i,j представляют собой параметры управления системой, а зависящие от них переменные z t i - совокупность параметров состояния системы в каждый момент времени t. Ограничения z t i ≥ 0 гарантируют, что в любой момент времени с любого склада не может быть вывезен объем продукта, превышающий его фактическое количество, а ограничения (6.21) задают правила изменения этого количества при переходе от одного периода к другому. Ограничения данного вида, которые задают условия на значения параметров состояния системы, принято называть фазовыми.
Отметим также, что условие (6.21) служит простейшим примером фазовых ограничений, поскольку связываются значения параметров состояния для двух смежных периодов t и t +l. В общем случае может устанавливаться зависимость для группы параметров, принадлежащих нескольким, возможно несмежным, этапам. Такая потребность может возникнуть, например, при учете в моделях фактора запаздывания поставок.
Простейшая динамическая модель макроэкономики. Представим экономику некоторого региона как совокупность п отраслей (j ∊1:п ), валовой продукт которых в денежном выражении на некоторый момент t может быть представлен в виде вектора z t =(z t 1 , z t 2 ,..., z t n ), где t ∊0:(Т -1). Обозначим через A t матрицу прямых затрат, элементы которой a t i,j , отражают затраты продукции i -й отрасли (в денежном выражении) на изготовление единицы продукции j -й отрасли в t -й момент времени. Если X t = ║x t i,j ║ n xm - матрица, задающая удельные нормы продукции i -й отрасли, идущей на расширение производства в j -й отрасли, а у t = (у t 1 , у t 2 , ..., у t n ) - вектор объемов продукции отраслей потребления, идущей на потребление, то условие расширенного воспроизводства можно записать как
где z 0 = ž - исходный запас продукции отраслей предполагается заданным и
В рассматриваемой модели величины z t являются параметрами состояния системы, а X t - управляющими параметрами. На ее базе могут быть поставлены различные задачи, типичным представителем которых является задача оптимального вывода экономики на момент Т к некоторому заданному состоянию z *. Данная задача сводится к отысканию последовательности управляющих параметров
удовлетворяющих условиям (6.24)-(6.25) и минимизирующих функцию
6.2.2. Простейшая задача оптимального управления. Один из приемов, применяемых для решения экстремальных задач, состоит в выделении некоторой проблемы, допускающей относительно несложное решение, к которой в дальнейшем могут быть сведены остальные задачи.
Рассмотрим так называемую простейшую задачу управления . Она имеет вид
Специфика условий задачи (6.27)-(6.29) состоит в том, что функции качества управления (6.27) и ограничения (6.28) являются линейными относительно z t , в то же время функция g (t , х t ), входящая в (6.28), может быть произвольной. Последнее свойство делает задачу нелинейной даже при t =1, т. е. в статическом варианте.
Общая идея решения задачи (6.27)-(6.29) сводится к ее «расщеплению» на подзадачи для каждого отдельно взятого момента времени, в предположении, что они успешно разрешимы. Построим для задачи (6.27)-(6.29) функцию Лагранжа
где λ t - вектора множителей Лагранжа (t ∊0:Т ). Ограничения (6.29), носящие общий характер, в функцию (6.30) в данном случае не включены. Запишем ее в несколько иной форме
Необходимые условия экстремума функции Ф(х, z, λ) по совокупности векторов z t задаются системой уравнений
которая называется системой для сопряженных переменных . Как можно заметить, процесс нахождения параметров λ t в системе (6.32) осуществляется рекуррентным образом в обратном порядке.
Необходимые условия экстремума функции Лагранжа по переменным λ t будут эквивалентны ограничениям (6.28), и, наконец, условия ее экстремума по совокупности векторов х t ∊Х t , t ∊1:(Т -1) должны быть найдены как результат решения задачи
Таким образом, задача поиска оптимального управления сводится к поиску управлений, подозрительных на оптимальность, т. е. таких, для которых выполняется необходимое условие оптимальности. Это, свою очередь, сводится к нахождению таких t , t , t , удовлетворяющих системе условий (6.28), (6.32), (6.33), которая называется дискретным принципом максимума Понтрягина.
Справедлива теорема.
Доказательство.
Пусть t , t , t , удовлетворяют системе (6.28), (6.32), (6.33). Тогда из (6.31) и (6.32) следует, что
и поскольку t удовлетворяет (6.33), то
С другой стороны, в силу (6.28) из (6.30) следует, что при любом векторе t
Следовательно,
Применяя теорему (6.2), а также положения теории нелинейного программирования, касающиеся связи между решением экстремальной задачи и существованием седловой точки (см. п. 2.2.2), приходим к выводу о том, что векторы t , t являются решением простейшей задачи оптимального управления (6.27)-(6.29).
В результате мы получили логически простую схему решения данной задачи: из соотношений (6.32) определяются сопряженные переменные t , затем в ходе решения задачи (6.33) находятся управления t и далее из (6.28) - оптимальная траектория состояний t ,.
Предложенный метод относится к фундаментальным результатам теории оптимального управления и, как уже это упоминалось выше, имеет важное значение для решения многих более сложных задач, которые, так или иначе, сводятся к простейшей. В то же время очевидны и пределы его эффективного использования, которые целиком зависят от возможности решения задачи (6.33).
КЛЮЧЕВЫЕ ПОНЯТИЯ
Ø Ø Игра, игрок, стратегия.
Ø Ø Игры с нулевой суммой.
Ø Ø Матричные игры.
Ø Ø Антагонистические игры.
Ø Ø Принципы максимина и минимакcа.
Ø Ø Седловая точка игры.
Ø Ø Цена игры.
Ø Ø Смешанная стратегия.
Ø Ø Основная теорема матричных игр.
Ø Ø Динамическая транспортная задача.
Ø Ø Простейшая динамическая модель макроэкономики.
Ø Ø Простейшая задача оптимального управления.
Ø Ø Дискретный принцип максимума Понтрягина.
КОНТРОЛЬНЫЕ ВОПРОСЫ
6.1. Кратко сформулируйте предмет теории игр как научной дисциплины.
6.2. Какой смысл вкладывается в понятие «игра»?
6.3. Для описания каких экономических ситуаций может быть применен аппарат теории игр?
6.4. Какая игра называется антагонистической?
6.5. Чем однозначно определяются матричные игры?
6.6. В чем заключаются принципы максимина и минимакcа?
6.7. При каких условиях можно говорить о том, что игра имеет седловую точку?
6.8. Приведите примеры игр, которые имеют седловую точку и в которых она отсутствует.
6.9. Какие подходы существуют к определению оптимальных стратегий?
6.10. Что называют «ценой игры»?
6.11. Дайте определение понятию «смешанная стратегия».
СПИСОК ЛИТЕРАТУРЫ
1. Абрамов Л. М., Капустин В. Ф. Математическое программирование. Л.,1981.
2. Ашманов С. А. Линейное программирование: Учеб. пособие. М., 1981.
3. Ашманов С. А., Тихонов А. В. Теория оптимизации в задачах и упражнениях. М., 1991.
4. Беллман Р. Динамическое программирование. М., 1960.
5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М., 1965.
6. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями. Л., 1984.
7. Гасс С. Линейное программирование (методы и приложения). М., 1961.
8. Гейл Д . Теория линейных экономических моделей М., 1963.
9. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация / Пер. с англ. М., 1985.
10. Давыдов Э. Г. Исследование операций: Учеб. пособие для студентов вузов. М., 1990.
11. Данциг Дж. Линейное программирование, его обобщения и применения. М.,1966.
12. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М., 1976.
13. Ермольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя В.И. Математические методы исследования операций: Учеб. пособие для вузов. Киев, 1979.
14. Зайченко Ю. П. Исследование операций, 2-е изд. Киев, 1979.
15. Зангвилл У. И. Нелинейное программирование. Единый подход. М., 1973.
16. Зойтендейк Г. Методы возможных направлений. М., 1963.
17. Карлин С. Математические методы в теории игр, программировании и экономике. М., 1964.
18. Карманов В. Г. Математическое программирование: Учеб. пособие. М., 1986.
19. Корбут А.А., Финкелыитейн Ю. Ю. Дискретное программирование. М., 1968.
20. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. М., 1977.
21. Кюнце Г.П., Крелле В. Нелинейное программирование. М.,1965.
22. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.3. Линейное и нелинейное программирование. Киев, 1975.
23. Мак-Кинси Дж. Введение в теорию игр. М., 1960.
24. Мухачева Э. А., Рубинштейн Г. Ш. Математическое программирование. Новосибирск, 1977.
25. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М, 1970.
26. Оре О. Теория графов. М., 1968.
27. Таха X. Введение в исследование операций/ Пер. с англ. М.,1985.
28. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.,1972.
29. Хедли Дж. Нелинейное и динамическое программирование. М., 1967.
30. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения). М., 1969.
31. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы. М., 1963.
32. Lapin L. Quantitative methods for business decisions with cases. Fourth edition. HBJ, 1988.
33. Liitle I.D.C., Murty K.G„ Sweeney D.W., Karel C. An algorithm for traveling for the traveling salesman problem. - Operation Research, 1963, vol.11, No. 6, p. 972-989/ Русск. пер.: Литл Дж., Мурти К., Суини Д., Керел К. Алгоритм для решения задачи о коммивояжере. - В кн.: Экономика и математические методы, 1965, т. 1, № 1, с. 94-107.
ПРЕДИСЛОВИЕ............................................................................................................................................................................................................ 2
ВВЕДЕНИЕ.................................................................................................................................................................................................................... 3
ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.......................................................................................................................................... 8
1.1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ............................................................................................. 9
1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ........................................................... 11
1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП..................................................................... 15
1.4. СИМПЛЕКС-МЕТОД........................................................................................................................................................................................ 17
1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД..................................................................................................................................... 26
1.6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ....................................................................................... 30
1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД................................................................................................................................................... 37
КЛЮЧЕВЫЕ ПОНЯТИЯ.......................................................................................................................................................................................... 42
КОНТРОЛЬНЫЕ ВОПРОСЫ................................................................................................................................................................................... 43
ГЛАВА 2. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ................................................................................................................................. 44
2.1. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ...................................................................................... 44
2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ................................................................................................... 55
КЛЮЧЕВЫЕ ПОНЯТИЯ.......................................................................................................................................................................................... 59
КОНТРОЛЬНЫЕ ВОПРОСЫ................................................................................................................................................................................... 59
ГЛАВА 3. ТРАНСПОРТНЫЕ И СЕТЕВЫЕ ЗАДАЧИ................................................................................................................................ 60
3.1. ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ........................................................................................................................ 60
3.2. СЕТЕВЫЕ ЗАДАЧИ........................................................................................................................................................................................... 66
КЛЮЧЕВЫЕ ПОНЯТИЯ.......................................................................................................................................................................................... 73
КОНТРОЛЬНЫЕ ВОПРОСЫ................................................................................................................................................................................... 73
ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ................................................................................................................................... 74
4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ..................................................................................................................... 74
4.2. МЕТОД ГОМОРИ............................................................................................................................................................................................... 78
4.3. МЕТОД ВЕТВЕЙ И ГРАНИЦ.......................................................................................................................................................................... 81
КЛЮЧЕВЫЕ ПОНЯТИЯ.......................................................................................................................................................................................... 86
КОНТРОЛЬНЫЕ ВОПРОСЫ................................................................................................................................................................................... 86
ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ........................................................................................................................... 86
5.1. ОБЩАЯ СХЕМА МЕТОДОВ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ................................................................................. 86
5.2. ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.................................................................................................... 93
КЛЮЧЕВЫЕ ПОНЯТИЯ........................................................................................................................................................................................ 101
КОНТРОЛЬНЫЕ ВОПРОСЫ................................................................................................................................................................................ 101
ГЛАВА 6. КРАТКИЙ ОБЗОР ДРУГИХ РАЗДЕЛОВ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ................................................................. 101
6.1. ТЕОРИЯ ИГР...................................................................................................................................................................................................... 101
6.2. ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ........................................................................................................................................... 108
КЛЮЧЕВЫЕ ПОНЯТИЯ........................................................................................................................................................................................ 112
КОНТРОЛЬНЫЕ ВОПРОСЫ................................................................................................................................................................................ 112
СПИСОК ЛИТЕРАТУРЫ........................................................................................................................................................................................ 112
Оптимальные САУ это системы в которых управление осуществляется таким образом что требуемый критерий оптимальности имеет экстремальное значение. Граничные условия определяющие начальное и требуемое конечное состояния системы технологическая цель системы. tн Её ставят в тех случаях когда особый интерес представляет среднее отклонение в течение определённого интервала времени и задача системы управления обеспечить минимум этого интеграла...
Поделитесь работой в социальных сетях
Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск
Оптимальное управление
Воронов А.А., Титов В.К., Новогранов Б.Н. Основы теории автоматического регулирования и управления. М.: Высшая школа, 1977. 519с. С. 477 491.
Оптимальные САУ это системы, в которых управление осуществляется таким образом, что требуемый критерий оптимальности имеет экстремальное значение.
Примеры оптимального управления объектами:
- Управление движением ракеты с целью достижения ею заданной высоты или дальности при минимальном расходе горючего;
- Управление перемещением приводимого двигателем механизма, при котором минимизировались бы затраты энергии;
- Управление атомным реактором, при котором максимальна производительность.
Задача оптимального управления формулируется следующим образом:
“Найти такой закон изменения во времени управления u (t ), при котором система при заданных ограничениях перейдёт из одного заданного состояния в другое оптимальным образом в том смысле,что функционал I , выражающий качество процесса, получит при найденном управлении экстремальное значение “.
Чтобы решить задачу оптимального управления, необходимо знать:
1.Математическое описание объекта и среды, связывающее значения всех координат исследуемого процесса,управляющих и возмущающих воздействий;
2.Ограничения физического характера на координаты и закон управления, выраженные математически;
3. Граничные условия, определяющие начальное и требуемое конечное состояния системы
(технологическая цель системы);
4.Целевую функцию (функционал качества
математическая цель).
Математически критерий оптимальности чаще всего представляют в виде:
t к
I =∫ f o [ y (t ), u (t ), f (t ), t ] dt + φ [ y (t к ), t к ], (1)
t н
где первое слагаемое характеризует качество управления на всём интервале (t н , t н ) и называется
интегральной составляющей, второе слагаемое
характеризует точность в конечный (терминальный) момент времени t к .
Выражение (1) называется функционалом, так как I зависит от выбора функции u (t ) и получающегося при этом y (t ).
Задача Лагранжа. В ней минимизируется функционал
t к
I=∫f o dt.
t н
Её ставят в тех случаях, когда особый интерес представляет среднее отклонение в течение
определённого интервала времени, и задача системы управления обеспечить минимум этого интеграла (ухудшение качества продукции, убыток и т.п.).
Примеры функционалов:
I =∫ (t ) dt критерий минимальной ошибки в установившемся режиме, где x (t )
- отклонение управляемого параметра от заданного значения;
I =∫ dt = t 2 - t 1 = > min критерий максимального быстродействия САУ;
I =∫ dt = > min критерий оптимальной экономичности.
Задача Майера. В этом случае минимизируемым является функционал, определяемый только терминальной частью, т.е.
I = φ =>min.
Например, для системы управления ЛА, описываемым уравнением
F o (x , u , t ),
можно поставить следующую задачу: определить управление u (t ), t н ≤ t ≤ t к так, чтобы за
заданное время полёта достичь максимальной дальности при условии, что в конечный момент времени t к ЛА совершит посадку, т.е. x (t к ) =0.
Задача Больца сводится к задаче минимизации критерия (1).
Базовыми методами решения задач оптимального управления являются:
1.Классическое вариационное исчисление теорема и уравнение Эйлера;
2.Принцип максимума Л.С. Понтрягина;
3.Динамическое программирование Р. Беллмана.
УРАВНЕНИЕ И ТЕОРЕМА ЭЙЛЕРА
Пусть задан функционал:
t к
I =∫ f o dt ,
t н
где некоторые дважды дифференцируемые функции, среди которых необходимо найти такие функции (t ) или экстремали , которые удовлетворяют заданным граничным условиям x i (t н ), x i (t к ) и минимизируют функционал.
Экстремали отыскиваются среди решений уравнения Эйлера
I = .
Для установления факта минимизации функционала необходимо удостовериться, что вдоль экстремалей выполняются условия Лагранжа:
аналогичные требованиям положительности второй производной в точке минимума функции.
Теорема Эйлера: “Если экстремум функционала I существует и достигается среди гладких кривых, то он может достигаться только на экстремалях”.
ПРИНЦИП МАКСИМУМА Л.С.ПОНТРЯГИНА
Школа Л.С.Понтрягина сформулировала теорему о необходимом условии оптимальности, сущность которой в следующем.
Допустим, что дифференциальное уравнение объекта вместе с неизменяемой частью управляющего устройства заданы в общей форме:
На управление u j могут накладываться ограничения, например, в виде неравенств:
, .
Цель управления состоит в переводе объекта из начального состояния (t н ) в конечное состояние (t к ). Момент окончания процесса t к может быть фиксированным или свободным.
Критерием оптимальности пусть будет минимум функционала
I = dt .
Введём вспомогательные переменные и образуем функцию
Fo ()+ f () f ()+
Принцип максимума гласит, что для оптимальности системы, т.е. для получения минимума функционала, необходимо существование таких ненулевых непрерывных функций, удовлетворяющих уравнению
Что при любом t , находящемся в заданном диапазоне t н≤ t ≤ t к , величина Н, как функция допустимого управления, достигает максимума.
Максимум функции Н определяется из условий:
если не достигает границ области, и как точная верхняя грань функции Н по в противном случае.
Динамическое программирование Р.Беллмана
Принцип оптимальности Р.Беллмана:
“ Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.”
Под “поведением” системы следует понимать движение этих систем, а термин “решение” относится к выбору закона изменения во времени управляющих сил.
В динамическом программировании процесс поиска экстремалей разбивается на n шагов, в то время как в классическом вариационном исчислении ведётся поиск экстремали целиком.
Процесс поиска экстремали базируется на следующих предпосылках принципа оптимальности Р.Беллмана:
- Каждый отрезок оптимальной траектории является сам по себе оптимальной траекторией;
- Оптимальный процесс на каждом участке не зависит от его предыстории;
- Оптимальное управление (оптимальная траектория) ищется с помощью попятного движения [от y (T ) к y (T -∆) , где ∆ = Т/ N , N число участков разбиения траектории, и т.д.].
Эвристически уравнения Беллмана для требуемых постановок задач выведены применительно к непрерывным и дискретным системам.
Адаптивное управление
Андриевский Б.Р., Фрадков А.Л. Избранные главы теории автоматического управления с примерами на языке MATLAB . СПб.: Наука, 1999. 467с. Глава 12.
Воронов А.А., Титов В.К., Новогранов Б.Н. Основы теории автоматического регулирования и управления. М.: Высшая школа, 1977. 519с. С. 491 499.
Анхимюк В.Л., Опейко О.Ф., Михеев Н.Н. Теория автоматического управления. Мн.: Дизайн ПРО, 2000. 352с. С. 328 340.
Необходимость в адаптивных системах управления возникает в связи со значительным усложнением решаемых задач управления, причем специфическая особенность такого усложнения заключается в отсутствии практической возможности для подробного изучения и описания процессов, протекающих в управляемом объекте.
Например, современные высокоскоростные летательные аппараты, точные априорные данные о характеристиках которых во всех условиях функционирования не могут быть получены из-за значительных разбросов параметров атмосферы, больших диапазонов изменения скоростей полета, дальностей и высот, а также из-за наличия широкого спектра параметрических и внешних возмущений.
Некоторые объекты управления (самолеты и ракеты, технологические процессы и энергетические установки) отличаются тем, что их статические и динамические характеристики изменяются в широких пределах непредвиденным заранее образом. Оптимальное управление такими объектами возможно с помощью систем, в которых недостающая информация автоматически пополняется самой системой в процессе работы.
Адаптивными (лат.” adaptio ” приспособление) называются такие системы, которые при изменении параметров объектов или характеристик внешних воздействий в процессе эксплуатации самостоятельно, без участия человека изменяют параметры регулятора, его структуру, настройку или регулирующие воздействия для поддержания оптимального режима работы объекта.
Создание адаптивных систем управления осуществляется в принципиально иных условиях, т.е. адаптивные методы должны способствовать достижению высокого качества управления при отсутствии достаточной полноты априорной информации о характеристиках управляемого процесса или в условиях неопределенности.
Классификация адаптивных систем :
Самоприспосабливающиеся
(адаптивные)
Системы управления
Самонастраивающиеся Самообучающиеся Системы с адаптацией
Системы системы в особых фазовых
Состояниях
Поисковые Беспоиско- Обучающие- Обучающие- Релейные Адаптивные
(экстремаль- вые (анали- ся с поощре- ся без автоколеба- системы с
Ные) тические) нием поощрения тельные переменной
Системы системы системы структурой
Структурная схема классификации АС (по характеру процесса адаптации)
Самонастраивающиеся системы (СНС) представляют собой системы, в которых адаптация при изменении условий работы осуществляется путем изменения параметров и управляющих воздействий.
Самоорганизующимися называются системы, в которых адаптация осуществляется за счет изменения не только параметров и управляющих воздействий, но и структуры.
Самообучающаяся это система автоматического управления, в которой оптимальный режим работы управляемого объекта определяется с помощью управляющего устройства, алгоритм которого автоматически целенаправленно совершенствуется в процессе обучения путем автоматического поиска. Поиск производится с помощью второго управляющего устройства, являющегося органической частью самообучающейся системы.
В поисковых системах изменение параметров управляющего устройства или управляющего воздействия осуществляется в результате поиска условий экстремума показателей качества. Поиск условий экстремума в системах этого типа осуществляется с помощью пробных воздействий и оценки полученных результатов.
В беспоисковых системах определение параметров управляющего устройства или управляющих воздействий производится на основе аналитического определения условий, обеспечивающих заданное качество управления без применения специальных поисковых сигналов.
Системы с адаптацией в особых фазовых состояниях используют особые режимы или свойства нелинейных систем (режимы автоколебаний, скользящие режимы) для организации контролируемых изменений динамических свойств системы управления. Специально организованные особые режимы в таких системах либо служат дополнительным источником рабочей информации об изменяющихся условиях функционирования системы, либо наделяют системы управления новыми свойствами, за счет которых динамические характеристики управляемого процесса поддерживаются в желаемых пределах независимо от характера возникающих при функционировании изменений.
При применении адаптивных систем решаются следующие основные задачи:
1 . В процессе функционирования системы управления при изменении параметров, структуры и внешних воздействий обеспечивают такое управление, при котором сохраняются заданные динамические и статические свойства системы;
2 . В процессе проектирования и наладки при начальном отсутствии полной информации о параметрах, структуре объекта управления и внешних воздействиях производят автоматическую настройку системы в соответствии с заданными динамическими и статическими свойствами.
Пример 1 . Адаптивная система стабилизации углового положения ЛА.
f 1 (t ) f 2 (t ) f 3 (t )
Д1 Д2 Д3
ВУ1 ВУ2 ВУ3 f (t ) f 1 (t ) f 2 (t ) f 3 (t )
u (t ) W 1 (p ) W 0 (p ) y (t )
+ -
Рис. 1.
Приспосабливающаяся система стабилизации ЛА
При изменении условий полета меняется передаточная функция W 0 (p ) ЛА, а, следовательно, и динамическая характеристика всей системы стабилизации:
. (1)
Возмущения со стороны внешней среды f 1 (t ), f 2 (t ), f 3 (t ) , приводящие к контролируемым изменениям параметров системы, приложены к различным точкам объекта.
Возмущающее воздействие f (t ) , приложенное непосредственно к входу объекта управления, в отличие от f 1 (t ), f 2 (t ), f 3 (t ) не меняет его параметров. Поэтому в процессе работы системы измеряют только f 1 (t ), f 2 (t ), f 3 (t ).
В соответствии с принципом обратной связи и выражением (1) неконтролируемые изменения характеристики W 0 (p ) из-за возмущений и помех вызывают сравнительно небольшие изменения параметров Ф(p ) .
Если поставить задачу более полной компенсации контролируемых изменений, чтобы передаточная функция Ф(р) системы стабилизации ЛА оставалась практически неизменной, то следует надлежащим образом изменить характеристику регулятора W 1 (p ). Это и осуществляется в приспосабливающейся САУ, выполненной по схеме рис.1. Параметры внешней среды, характеризуемые сигналами f 1 (t ), f 2 (t ), f 3 (t ), например давление скоростного напора P H (t ) , температура окружающего воздуха T 0 (t ) и скорость полёта υ(t ) , непрерывно измеряются датчиками Д 1 , Д 2 , Д 3 , и текущие значения параметров поступают в вычислительные устройства В 1, В 2 ,В 3 , вырабатывающие сигналы, с помощью которых подстраивается характеристика W 1 (p ), чтобы компенсировать изменения характеристики W 0 (p ).
Однако, в АСАУ данного типа (с разомкнутым циклом настройки) отсутствует самоанализ эффективности осуществляемых ею контролируемых изменений.
Пример 2. Экстремальная система управления скоростью полета ЛА.
Z Возмущающее
Воздействие
X 3 = X 0 - X 2
Устройство авто- X 0 Усилительно- X 4 Исполнительное X 5 Регулируемый X 1
Матического по- преобразователь- устройство объект
Иска экстремума + - ное устройство
Измерительное
Устройство
Рис.2.Функциональная схема экстремальной системы управления скоростью полета ЛА
Экстремальная система определяет наивыгоднейшую программу, т.е. то значение X 1 (требуемая скорость движения ЛА), которое нужно в данный момент выдерживать, чтобы производился минимум расхода горючего на единицу длины пути.
Z - характеристика объекта; X 0 - управляющее воздействие на систему.
(величина расхода горючего)
y(0)
y(T)
Самоорганизующиеся системы
В этих нормах отдельно нормируется каждый компонент микроклимата в рабочей зоне производственного помещения: температура относительная влажность скорость движения воздуха в зависимости от способности организма человека к акклиматизации в разное время года характера одежды интенсивности производимой работы и характера тепловыделений в рабочем помещении. Перепады температуры воздуха по высоте и по горизонтали а также изменения температуры воздуха в течение смены при обеспечении оптимальных величин микроклимата на рабочих местах не должны... Управление: понятие признаки система и принципы Органы государственного управления: понятие виды и функции. По содержанию административное право является государственно-управленческим правом реализующим правовой интерес большинства граждан для чего субъекты управления наделяются юридически властными полномочиями представительскими функциями государства. Следовательно объектом действия юридических норм являются специфические управленческие общественные отношения возникающие между субъектом управления управляющим и объектами... Государственное регулирование социально-экономического развития регионов. Местные бюджеты как финансовая основа социально-экономического развития региона. Разные территории Украины имеют свои особенности и отличия как относительно экономического развития так и в социальном историческом языковом и ментальном аспектах. Из таких проблем нужно прежде всего назвать несовершенство отраслевой структуры большинства региональных хозяйственных комплексов их низкую экономическую эффективность; значительные отличия между регионами в уровнях...Определение и необходимость построения оптимальных систем автоматического управления
Системы автоматического управления обычно проектируют, исходя из требований обеспечения тех или иных показателей качества. Во многих случаях необходимое повышение динамической точности и улучшение переходных процессов систем автоматического управления достигается с помощью корректирующих устройств.
Особенно широкие возможности повышения показателей качества дает введение в САУ разомкнутых компенсационных каналов и дифференциальных связей, синтезированных из того или иного условия инвариантности ошибки относительно задающего или возмущающих воздействий . Однако эффект влияния корректирующих устройств, разомкнутых компенсационных каналов и эквивалентных им дифференциальных связей на показатели качества САУ зависит от уровня ограничения сигналов нелинейными элементами системы. Выходные сигналы дифференцирующих устройств, обычно кратковременные по длительности и значительные по амплитуде, ограничиваются элементами системы и не приводят к улучшению показателей качества системы, в частности ее быстродействия. Лучшие результаты решения задачи повышения показателей качества САУ при наличии ограничений сигнала дает так называемое оптимальное управление.
Задача синтеза оптимальных систем строго сформулирована сравнительно недавно, когда было дано определение понятия критерия оптимальности. В качестве критерия оптимальности в зависимости от цели управления могут быть выбраны различные технические или экономические показатели управляемого процесса. В оптимальных системах обеспечивается не просто некоторое повышение того или иного технико-экономического показателя качества, а достижение минимально или максимально возможного его значения.
Если критерий оптимальности выражает технико-экономические потери (ошибки системы, время переходного процесса, расход энергии, средств, стоимость и т. п), то оптимальным будет такое управление, которое обеспечивает минимум критерия оптимальности. Если Же он выражает рентабельность (к. п. д., производительность, прибыль, дальность полета ракеты и т. д.), то оптимальное управление должно обеспечить максимум критерия оптимальности.
Задача определения оптимальной САУ, в частности синтез оптимальных параметров системы при поступлении на ее вход задающего
воздействия и помехи, являющихся стационарными случайными сигналами, рассматривалась в гл. 7. Напомним, что в данном случае в качестве критерия оптимальности принято среднеквадратическое значение ошибки (СКО). Условия повышения точности воспроизведения полезного сигнала (задающего воздействия) и подавления помехи носят противоречивый характер, и поэтому возникает задача выбора таких (оптимальных) параметров системы, при которых СКО принимает наименьшее значение.
Синтез оптимальной системы при среднеквадратическом критерии оптимальности является частной задачей. Общие методы синтеза оптимальных систем основываются на вариационном исчислении. Однако классические методы вариационного исчисления для решения современных практических задач, требующих учета ограничений, во многих случаях оказываются непригодными. Наиболее удобными методами синтеза оптимальных систем автоматического управления являются метод динамического программирования Беллмана и принцип максимума Понтрягина.
Таким образом, наряду с проблемой улучшения различных показателей качества САУ возникает задача построения оптимальных систем, в которых достигается экстремальное значение того или иного технико-экономического показателя качества.
Разработка и внедрение оптимальных систем автоматического управления способствует повышению эффективности использования производственных агрегатов, увеличению производительности труда, улучшению качества продукции, экономии электроэнергии, топлива, сырья и т.
Понятия о фазовом состоянии и фазовой траектории объекта
В технике часто возникает задача перевода управляемого объекта (процесса) из одного состояния в другое. Например, при целеуказании необходимо антенну радиолокационной станции повернуть из начального положения с начальным азимутом в заданное положение с азимутом Для этого на электродвигатель, связанный с антенной через редуктор, подают управляющее напряжение и. В каждый момент времени состояние антенны характеризуется текущим значением угла поворота и угловой скоростью Эти две величины изменяются в зависимости от управляющего напряжения и. Таким образом, существуют три связанных между собой параметра и (рис. 11.1).
Величины характеризующие состояние антенны, называются фазовыми координатами, и - управляющим воздействием. При целеуказании РЛС типа станции орудийной наводки возникает задача поворота антенны по азимуту и углу места. В этом случае будем иметь четыре фазовые координаты объекта и два управляющих воздействия. У летящего самолета можно рассматривать шесть фазовых координат (три пространственные координаты и три компоненты скорости ) и несколько управляющих воздействий (тяга двигателя, величины, характеризующие положение рулей
Рис. 11.1. Схема объекта с одним, управляющим воздействием и двумя фазовыми координатами.
Рис. 11.2. Схема объекта с управляющими воздействиями и фазовыми координатами.
Рис. 11.3. Схема объекта с векторным изображением управляющего воздействия и и фазового состояния объекта
высоты и направления, элеронов). В общем случае в каждый момент времени состояние объекта характеризуется фазовыми координатами а к объекту может быть приложено управляющих воздействий (рис. 11.2).
Под переводом управляемого объекта (процесса) из одного состояния в другое следует понимать не только механическое перемещение (например, антенны РЛС, самолета), но также требуемое изменение различных физических величин: температуры, давления, влажности кабины, химического состава того или иного сырья при соответствующем управляемом технологическом процессе.
Управляющие воздействия удобно считать координатами некоторого вектора называемого вектором управляющего воздействия. Фазовые координаты (переменные состояния) объекта также можно рассматривать, как координаты некоторого вектора или точки в -мерном пространстве с координатами Эту точку называют фазовым состоянием (вектором состояния) объекта, а -мерное пространство, в котором в виде точек изображаются фазовые состояния, называется фазовым пространством (пространством состояний) рассматриваемого объекта. При использовании векторных изображений управляемый объект можно изобразить, как показано на рис. 11.3, где и - вектор управляющего воздействия и представляет собой точку в фазовом пространстве, характеризующую фазовое состояние объекта. Под влиянием управляющего воздействия и фазовая точка перемещается, описывая в фазовом пространстве некоторую линию, называемую фазовой траекторией рассматриваемого движения объекта.