Теория оптимального управления

Содержание

 

1. Теоретическая часть 2

Общие принципы теории оптимального управления 2

Возможность применения линейного программирования в теории оптимального управления 4

Симплекс-метод  линейного программирования 8

Описание  графического метода линейного программирования 12

2. Расчетная  часть 16

Список используемой литературы 22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретическая часть

Общие принципы теории оптимального управления

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

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

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

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

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

Сформулируем задачу оптимального управления:

• Уравнения состояния: (1).
• Граничные условия , (2).
• Минимизируемый функционал:

.

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

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

 

 

 

 

 

 

 

 

 

Возможность применения линейного программирования в теории оптимального управления

 

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

Линейное программирование представляет собой наиболее часто  используемый метод оптимизации. К  числу задач линейного программирования можно отнести задачи:

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

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

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

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

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

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

Тогда её можно представить  как выпуклую комбинацию вершин

 

 

Поскольку - линейный функционал, то

 

 

Обозначим через m минимум  из всех значений , и пусть он достигается в вершине , т.е.

 

 

Но тогда, так как  ,

 

то 

 

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

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

 

 

то  принадлежит допустимой области и

 

,

 

что и доказывает теорему.

Эта теорема имеет важнейшее  значение, так как она указывает  путь решения задачи линейного программирования. Совсем не надо перебирать все точки допустимой области. Достаточно перебрать вершины допустимой области, а ведь их - конечное число. Кроме того, как это окажется далее, не нужно перебирать все вершины, можно этот перебор существенно сократить. Только вот как узнать, имеем ли мы дело с вершиной или нет?

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

Примеры моделей, приводящих к задачам линейного программирования

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

Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x принадлежат некоторой области G:

 

 

В зависимости от вида функции  и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении.

Линейное программирование характеризуется тем, что

а) функция  является линейной функцией переменных ;

б) область G определяется системой линейных равенств или неравенств

 

 

 

 

 

 

Симплекс-метод  линейного программирования

 

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

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

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

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

Третий столбец - компоненты опорного плана. В дополнительной строке в этом столбце пишется величина . Её легко вычислить перемножая числа из второго столбца и третьего столбца и складывая их.

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

 

.

 

Заметим, что для векторов, входящих в базис, эти разности всегда равны нулю.

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

Этап 1

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

Если все эти разности , то план является оптимальным

Этап 2

Если есть столбцы, где  , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис.

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

Этап 3

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

где просматриваются лишь те дроби  , для которых

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

Этап 4

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

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

.

Остальные элементы этой строки заполняются величинами

.

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

Написанные выше формулы  для пересчета элементов направляющей строки можно записать следующим  правилом:

 

.

 

Этап 5

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

 

;

 

для координат разложения по базису

 

;

 

для дополнительной строки

 

.

 

Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу

 

.

 

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

Далее итерации продолжаются.

 

 

 

 

 

 

 

 

 

 

 

Описание  графического метода линейного программирования

 

Графический метод довольно прост и нагляден для решения  задач линейного программирования с двумя переменными. Он основан  на геометрическом представлении допустимых решений и ЦФ задачи.

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