Добавить в избранное

Классификация оптимальных систем автоматического управления. Оптимальное управление технологическими процессами (Лекция) Физика общих процессов производственных систем

Государственное образовательное учреждение

высшего профессионального образования

Московский физико-технический институт

(государственный университет)

УТВЕРЖДАЮ

Проректор по учебной работе

Ю.А.Самарский

«____»_______________2004 г.

П Р О Г Р А М М А

по курсу: ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ

по направлению 511600

факультет ФУПМ

кафедра математических основ управления

курс IV

семестр 7, 8

лекции – 50 час. Экзамен – 8 семестр

семинары – 50 час. Зачет – 7 семестр

лабораторные занятия – нет

Самостоятельная работа – 2 часа в неделю

ВСЕГО ЧАСОВ 100

Программу и задание составил: д.ф.-м.н., профессор Жадан В.Г.

Заведующий кафедрой С.А. Гуз

1. Основная задача оптимального управления. Принцип максимума Л.С. Понтрягина (принцип минимума). Каноническая форма записи. Принцип максимума для систем, содержащих управляющие параметры.

2. Задачи с подвижным правым концом. Условия трансверсальности. Задачи Лагранжа и Больца. Задачи Майера и Лагранжа с нефиксированным временем окончания процесса. Задача на быстродействие. Задача с подвижным левым концом.

3. Доказательство принципа максимума Л.С. Понтрягина для задачи Майера. Понятие игольчатой вариации. ЛеммаГронуолла–Беллмана. Учет оптимизации по управляющему параметру.

4. Связь принципа максимума с вариационным исчислением. Уравнение Эйлера. Первые интегралы уравнения Эйлера. Условия Веерштрасса, Лежандра и Якоби. Уравнение Якоби. Условия Веерштрасса–Эрдмана.

5. Линейные системы. Принцип максимума для линейных систем. Теорема о конечном числе точек переключений.

6. Множество достижимости для линейных систем. Экстремальное управление и экстремальный принцип.

7. Точечная управляемость для линейных систем. Критерий точечной управляемости. Теорема Калмана о точечной управляемости. Полная управляемость линейных систем. Теорема Калмана о полной управляемости автономных систем.

8. Проблема наблюдаемости. Критерий наблюдаемости для линейной системы. Наблюдение начального состояния. Связь между наблюдаемостью и управляемостью. Критерий полной наблюдаемости стационарной системы.

9. Формализм Лагранжа и его использование для решения задач оптимального управления. Проблема синтеза оптимального управления.

10. Проблема идентификации. Критерий идентифицируемости. Критерий полной идентифицируемости стационарной системы.

11. Системы с разрывными правыми частями. Условие скачка импульсов.

12. Понятие инвариантных систем. Свойства динамических систем. Опорное поле импульсов. Необходимые и достаточные условия инвариантности. Корректирующая функция.

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

14. Элементы теории динамического программирования. Необходимые условия оптимальности. Достаточные условия оптимальности. Уравнение Беллмана. Вывод принципа максимума из динамического программирования. Связь с вариационным исчислением.

15. Методы решения краевых задач. Применение метода Ньютона. Перенос граничных условий. Метод прогонки для нелинейных задач.

16. Численные методы, основанные на последовательном анализе вариантов. Метод «киевского веника», метод блуждающей трубки, метод локальных вариаций.

17. Численные методы, основанные на редукции к задачам нелинейного программирования. Вычисление производных по компонентам вектора управлений в случае дискретных процессов. Метод штрафов, метод нагруженного функционала.

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

19. Достаточные условия оптимальности В.Ф. Кротова для непрерывных и дискретных процессов. Применение формализма В.Ф. Кротова для решения линейных задач.

20. Особые управления. Определение особых управлений с помощью скобок Пуассона. Условия Келли и Коппа–Мойера.

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

1. Моисеев Н.Н. Численные методы в теории оптимальных систем. – М.: Наука, 1971.

2. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. – М.: Наука, 1982.

3. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1987.

4. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе З.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. – М.: Физматгиз, 1961.

5. Васильев Ф.П. Методы решения экстремальных задач. – М.: Наука, 1988.

6. Габасов Р., Кириллова Ф.М. Принцип максимума в теории оптимального управления. – Минск: Наука и техника, 1974.

7. Флеминг У., Ришел Р. Оптимальное управление детерминированными и стохастическими системами. – М.: Мир, 1978.

8. Основы теории оптимального управления /Под редакцией В.Ф. Кротова. – М.: Высшая школа, 1990.

9. Ли Э.Б., Маркус П. Основы теории оптимального управления. М.: Наука, 1972.

10. ГабасовР., Кириллова Ф.М. Особые оптимальные управления. – М.: Наука, 1973.

Задание можно посмотреть

В общем случае автоматическая система состоит из объекта управления и совокупности устройств, которые обеспечивают управление этим объектом. Как правило, эта совокупность устройств включает в себя измерительные устройства, усилительные и преобразовательные устройства, а также исполнительные устройства. Если объединить эти устройство в одно звено (управляющее устройство), то структурная схема системы выглядит следующим образом:

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

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

Управляющее устройство вырабатывает управляющее воздействие
. Таких управляющих воздействий может быть несколько, они образуют- мерный управляющий вектор.

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

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

Мы будем рассматривать такие объекты управления, которые являются управляемыми. То есть вектор состояния можно изменять требуемым образом путем соответствующего изменения вектора управления. Будем подразумевать, что объект полностью наблюдаемый.

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

- угол отклонения рулей высоты

- курс

- элерон

- тяга

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

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

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

На любой угол рулей высоты, курса, элерона существуют ограничения:

- тяга сама по себе ограничена.

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

Мы будем рассматривать объекты управления, которые описываются дифференциальным уравнением:

(1)

Или в векторном виде:

--мерный вектор состояния объекта

--мерный вектор управляющих воздействий

- функция правой части уравнения (1)

На вектор управления
накладывается ограничение, мы будем полагать, что его значения принадлежат некоторой замкнутой областинекоторого-мерного пространства. Это означает, что управляющая функция
в любой момент времени принадлежит области(
).

Так, например, если координаты управляющей функции удовлетворяет неравенствам:

то область является-мерным кубом.

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

. были непрерывны по всем аргументам и имели непрерывные частные производные по переменным

.

В качестве критерия, который характеризует качество работы системы, выбирается функционал вида:

(2)

В качестве функции
будем предполагать, что она непрерывна по всем своим аргументам и имеет непрерывные частные производные по

.

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

Любая автоматическая система предназначена для управления каким-либо объектом, должна быть построена таким образом, чтобы осуществляемое ею управление было оптимальным, т.е наилучшем в том или ином смысле. Задачи оптимального управления чаще всего возникают в подсистемах управления технологическими процессами. В каждом случае существует некоторая технологическая задача, для выполнения которой предназначается соответствующая машина или установка (объект управления), снабженная соответствующая системой управления, т.е. речь идет о некоторой САУ, состоящей из объекта управления и совокупности устройств, которые обеспечивают управление этим объектом. Как правило эта совокупность включает в себя измерительные, усилительные преобразовательные и исполнительные устройства. Если объединить усилительные, преобразовательные и исполнительные устройства в одно звено, называемое управляющим устройством или регулятором, то функциональная схема САУ может быть приведена к виду на рис. 1. 1.

Рис. 1. 2 Функциональная схема оптимальной системы

На вход управляющего устройства поступает задающее воздействие, которое содержит инструкцию о том, каково должно быть состояние объекта - так называемое «желаемое состояние».

На объект управления может поступать возмущающие воздействие z, представляющие нагрузку или помеху. Измерение координат объекта измерительным устройством может производиться с некоторыми случайными погрешностями x (ошибка) .

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

Под характеристиками объекта понимают зависимость выходных величин объекта от входных

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

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

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

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

Иногда к системе управления предъявляются различные, подчас противоречивые требования. Законы управления, которые одновременно наилучшим образом удовлетворяли бы каждому требованию, не существует. Поэтому из всех требований нужно выбрать одно главное, которое должно удовлетворяться наилучшим образом. Другие требования играют роль ограничений. Следовательно, выбор критерия оптимальности должен производиться, только на основании изучения технологии и экономики рассматриваемого объекта и среды. Эта задача выходит за рамки теории ОУ.

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

Как видно, величина Q зависит от функций.

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

Для процессов управления использоваться такие критерии:

1. оптимальное быстродействие (время переходного процесса)

2. минимум среднеквадратичного значения ошибки.

3. минимум расхода затрачиваемой энергии.

Таким образом, критерий оптимальности может относиться к переходному или к установившемуся процессу в системе.

В зависимости от критерия оптимальности оптимальные системы можно разделить на два основных класса -- оптимальные по быстродействию и оптимальные по точности.

Системы оптимального управления в зависимости от характера критерия оптимальности можно разделить на три типа:

а) равномерно-оптимальные системы;

б) статистически-оптимальные системы;

в) минимаксно-оптимальные системы.

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

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

Минимаксно-оптимальные -- это такие системы, которые в наихудшем случае дают возможно наилучший результат. Они отличаются от равномерно-оптимальных тем, что в ненаихудшем случае могут дать худший результат, чем какая-либо другая система .

Оптимальные системы можно также подразделить на три типа в зависимости от способа получения информация об управляемом объекте:

оптимальные системы с полной информацией об объекте;

оптимальные системы с неполной информацией об объекте и пассивным ее накоплением;

оптимальные системы с неполной информацией об объекте и активным ее накоплением в процессе управления (системы дуального управления).

Существует две разновидности задач синтеза оптимальных систем:

Определение оптимальных значений параметров регулятора при заданных параметрах объекта и заданной структуре системы;

Синтез структуры и определение параметров регулятора при заданных параметрах и структуре объекта управления.

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

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

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

Достижение оптимального функционирования САУ во многом определяется тем, как осуществляется управление во времени, какова программа, или алгоритм управления. В связи с этим для оценки оптимальности систем используют интегральные критерии, вычисляемые как сумма значений интересующего проектировщиков параметра качества системы за все время процесса управления.

В зависимости от принятого критерия оптимальности рассматривают следующие виды оптимальных систем.

1. Системы , оптимальные по быстродействию , которые обеспечивают минимальное время перевода ОУ из одного состояния в другое. В этом случае критерий оптимальности выглядит следующим образом:

где / н и / к - моменты начала и окончания процесса управления.

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

2. Системы , оптимальные по расходу ресурсов , которые гарантируют минимум критерия

где к - коэффициент пропорциональности; U(t) - управляющее воздействие.

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

3. Системы , оптимальные по потерям управления (или по точности), которые обеспечивают минимальные ошибки управления на основании критерия где e(f) - динамическая ошибка.

В принципе задача проектирования оптимальной САУ может быть решена простейшим методом перебора всех возможных вариантов. Конечно, такой метод требует больших затрат времени, но современные ЭВМ позволяют в некоторых случаях им воспользоваться. Для решения задач оптимизации разработаны специальные методы вариационного исчисления (метод максимума, метод динамического программирования и др.), позволяющие учесть все ограничения реальных систем.

В качестве примера рассмотрим, каким должно быть оптимальное по быстродействию управление электродвигателем постоянного тока, если подаваемое на него напряжение ограничено предельной величиной {/ лр, а сам двигатель можно представить в виде апериодического звена 2-го порядка (рис. 13.9, а).

Метод максимума позволяет рассчитать закон изменения и(г), обеспечивающий минимальное время разгона двигателя до частоты вращения (рис. 13.9, б). Процесс управления данным двигателем должен состоять из двух интервалов, в каждом из которых напряжение u(t) принимает свое предельное допустимое значение (в интервале 0 - /,: u(t) = +?/ пр, в интервале /| - / 2: u(t) = -?/ пр)* Для обеспечения такого управления в состав системы должен быть включен релейный элемент.

Как и обычные системы, оптимальные системы бывают разомкнутыми, замкнутыми и комбинированными. Если оптимальное управление, переводящее ОУ из начального состояния в конечное и не зависящее или слабо зависящее от возмущающих воздействий, может быть задано как функция времени U = (/(/), то строится разомкнутая система программного управления (рис. 13.10, а).

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

Рис. 13.9.

а - с обшим управляющим устройством; б - с двухуровневым управляющим

устройством

Рис. 13.10. Схемы оптимальных систем: а - разомкнутой; б - комбинированной

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

Наиболее совершенными, хотя и наиболее сложными, являются комбинированные оптимальные системы (рис. 13.10, б). В таких системах разомкнутый контур осуществляет оптимальное управление по заданной программе, а замкнутый контур, оптимизированный по минимуму ошибки, отрабатывает отклонение выходных параметров. Используя канат измерения возмущений /*, система становится инвариантной относительно всего множества задающих и возмущающих воздействий.

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

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

Используются и другие вероятностные критерии. Например, в системе обнаружения целей, где важно только наличие или отсутствие цели, в качестве критерия оптимальности применяют вероятность ошибочного решения Р ош:

где Р п ц - вероятность пропуска цели; Р ЛО - вероятность ложного обнаружения.

Во многих случаях рассчитанные оптимальные САУ оказываются практически не реализуемыми ввиду их сложности. Как правило, требуется получение точных значений производных высоких порядков от входных воздействий, что технически очень трудно осуществимо. Зачастую даже теоретический точный синтез оптимальной системы оказывается невозможен. Однако методы оптимального проектирования позволяют строить квазиоптимальные системы, хотя и упрощенные в той или иной степени, но все- гаки позволяющие достичь значений принятых критериев оптимальности, близких к экстремальным.

КАТЕГОРИИ