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

Задачи оптимального управления относятся к теории экстремальных задач, то есть задач определения максимальных и минимальных значений. Уже то обстоятельство, что в этой фразе встретилось несколько латинских слов (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

ГЛАВА 3. ТРАНСПОРТНЫЕ И СЕТЕВЫЕ ЗАДАЧИ................................................................................................................................ 60

3.1. ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ........................................................................................................................ 60

3.2. СЕТЕВЫЕ ЗАДАЧИ........................................................................................................................................................................................... 66

ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ................................................................................................................................... 74

4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ..................................................................................................................... 74

4.2. МЕТОД ГОМОРИ............................................................................................................................................................................................... 78

4.3. МЕТОД ВЕТВЕЙ И ГРАНИЦ.......................................................................................................................................................................... 81

ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ........................................................................................................................... 86

5.1. ОБЩАЯ СХЕМА МЕТОДОВ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ................................................................................. 86

5.2. ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.................................................................................................... 93

ГЛАВА 6. КРАТКИЙ ОБЗОР ДРУГИХ РАЗДЕЛОВ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ................................................................. 101

6.1. ТЕОРИЯ ИГР...................................................................................................................................................................................................... 101

6.2. ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ........................................................................................................................................... 108

СПИСОК ЛИТЕРАТУРЫ........................................................................................................................................................................................ 112

Оптимальное управление

Андрей Александрович Аграчёв

Человеку свойственно стремление к совершенству. В математике оно проявляется в поиске наилучших (оптимальных) решений, включая все задачи на максимум и минимум. К теории оптимального управления относятся те из них, где решение имеет некоторую протяженность во времени или в пространстве. Подходящий образ — прокладывание наилучшего пути при движении по сильно пересечённой местности.

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

Требуется наилучшим образом перевести систему из заданного состояния в желаемое: как можно быстрее, или наиболее экономным образом, или с наибольшей выгодой, или в соответствии с каким‐то более сложным критерием; мы сами решаем, что важнее. Если мгновенная реакция системы на наши действия хорошо известна, то теория оптимального управления призвана помочь нам найти наилучшую долговременную стратегию. Вот простой пример: нужно как можно быстрее остановить колебания (скажем, остановить «качели»), прикладывая свою невеликую силу то с одной стороны, то с другой. Переходить с одной стороны на другую придётся многократно. По какому правилу это делать? Понятно, что «качели» могут быть и финансовыми, и экономическими, и физико‐техническими…

Стоит заметить, что такой очевидно прикладной предмет, как теория оптимального управления, был создан в Математическом институте имени Стеклова чистыми математиками, Львом Семёновичем Понтрягиным и его учениками, профессиональными топологами. Первые впечатляющие применения этой теории, принесшие ей славу, относятся к советской космической программе и американской программе «Аполлон». В этих программах всё делалось на пределе возможностей, и без умной оптимизации было не справиться. Среди популярных тогда задач можно отметить наиболее экономный перевод космического аппарата с одной эллиптической орбиты на другую и мягкое прилунение. Главное достижение того периода — принцип максимума Понтрягина — мощное универсальное средство, позволяющее отобрать достаточно узкий класс управляющих стратегий, среди которых только и может быть оптимальная.

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

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

Геометрическая теория управления применяется в космической навигации, робототехнике и многих других областях, но наиболее популярные современные приложения относятся, пожалуй, к квантовым системам (от медицинских аппаратов ядерного магнитного резонанса до химических манипуляций с отдельными молекулами). Обаяние геометрической теории управления состоит, среди прочего, в редкой возможности материализовать, увидеть и «пощупать» красивые и глубокие абстрактные математические концепции, ну и, конечно, создавать новые!

Литература

Тихомиров В. М. Рассказы о максимумах и минимумах. — М.: Наука, 1986. — (Библиотечка «Квант»; Вып. 56). — [Переиздания: М.: МЦНМО, 2006, 2017].

Протасов В. Ю. Максимумы и минимумы в геометрии. — М.: МЦНМО, 2012. — (Библиотека «Математическое просвещение»; Вып. 31).

Под оптимальной САУ понимается наилучшая в некотором смысле система. Критерии оптимальности могут быть различны и зависят от решаемой задачи. Наиболее часто встречаются такие критерии оптимальности:

1) Точность САУ при изменяющемся воздействии,

2) Время переходного процесса,

3) Экономичность;

Производительность;

Интегральные критерии.

К настоящему времени наибольшее развитие получили 2 направления в теории оптимальности систем:

1) Теория оптимального управления движением систем с полной информацией об объекте и возмущениях;

Теории оптимального управления при случайных возмущениях.

Для реализации оптимального управления необходимо:

Определить цель управления. Цель выражается либо целевой функцией, либо критерием оптимизации.

Целевая функция или критерий оптимизации позволяют найти количественный эффект любого решения.

Выбрать модель для анализа и определения эффективности принятого решения.

Изучить все состояния среды функционирования объекта, влияющие на прошлое, настоящее и будущее процесса управления.

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

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

1)Цель управления, представленная математически в виде некоторого функционалаили критерия управления

2)Уравнения системы - они обычно задаются в виде уравнений состояний

3)Система граничных уравнений в начальный и конечный момент времени.

4)Система ограничений, которым должны удовлетворять переменные состояния и уравнения.

Требуется найти:

Вектор управления, при котором критерий цели управления имеет экстремум (max или min).

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

Интегральные критерии качества:

Оптимальное Быстродействие

Функционал имеет вид

Оптимальная Производительность

Критерием оптимальности явл-ся угол поворота  за определенное время t и функционал имеет вид

Оптимальная экономичность

Критерием оптимальности явл-ся расход энергии за определенное время и функционал имеет вид

28. Аналитическое конструирование регуляторов. Постановка задачи.

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

Это вариационная задача, где в качестве экстремали ищется функция связывающая Х и U.

При аналитическом конструировании задача состоит в том, что бы найти закон регулирования который с учетом уравнений объекта и граничных условий доставлял бы min интегралу, характеризующему квадратичную ошибку системы и гарантирующему ее устойчивость.

Постановка задачи оптимального конструирования регуляторов.

Объект регулирования задан с помощью дифуравнений, что в операторной форме соответствует заданию передаточной функции Wор(S) (или W(S))

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

X = y 0 – y - рассогласование

Вустойчивой линейной САУ в результате переходного процесса все функции координат должны стремиться к 0. х 1 () = х 2 () = … х n () = U() = 0 (2)

В качестве критерия оптимальности выберем интеграл вида

(3), где V- положительно определённая квадратичная форма.

Т.е. если подставитьV в  (3) то это будет квадратичная ошибка системы.

Член U 2 в (4) характеризует стоимость процесса управления, т.е. затраты энергии на нагрев. U 2 гарантирует отсутствие нереализуемых в линейных регуляторах законов, он гарантирует отсутствие управляющих воздействий, при которых скорость превращается в бесконечность.

Само существование (3) гарантирует устойчивость системы. При аналитическом конструирование задание состоит в том чтобы найти в аналитической форме функцию Ф(U,U,x 1 …x k) = 0 (5) – который с учётом уравнений объекта и приграничных условий (1) и (2) доставлял бы минимум интегралу (3).