🗊Презентация Оптимальное управление

Оптимальное управление Старший преподаватель каф. “Кибернетика” Локтюшев Александр Викторович

1. Постановка задачи оптимизации

Понятие “оптимизация” Людям свойственно стремление к лучшему, и если им приходится выбирать из нескольких возможностей, то желание найти среди них лучшую представляется вполне естественным. Для постановки задачи принятия решения необходимо выполнение двух условий: 1) должно быть много вариантов решений; 2) лучший вариант должен быть выбран по определенному принципу.

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

Понятие “оптимизация” Под оптимизацией понимают процесс выбора наилучшего варианта из всех возможных Для того чтобы найти оптимальную из возможностей, приходится решать задачи на отыскание максимума или минимума Оба эти понятия объединяются термином «экстремум» (от латинского extremum, означающего «крайнее»). Поэтому задачи на отыскание максимума или минимума называют экстремальными задачами.

История развития оптимизации 825 г. до н.э. – задача царицы Дидоны Финикийская царевна Дидона и с ней небольшой отряд жителей города Тира, спасаясь от преследований тирана, покинули родной город и отправились на кораблях на запад вдоль берегов Средиземного моря. Выбрав на африканском побережье удобное место (нынешний Тунисский залив), Дидона и ее спутники решили основать здесь поселение. Дидоне, удалось "уговорить предводителя местных жителей Ярба, и он неосторожно согласился уступить Дидоне клочок земли, «который можно окружить бычьей шкурой». Как поступила царица Дидона, чтобы территория охваченной земли оказалась наибольшей?

Параметрические задачи требуется указать оптимальную форму участка земли, который при заданной длине периметра L, имеет наибольшую площадь S.

Задача Евклида (IV в. до н.э.) В заданный треугольник ABC с высотой Н и основанием b вписать параллелограмм наибольшей площади S, стороны которого параллельны двум сторонам треугольника

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

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

Постановка задачи оптимизации 1) Вербальное (словесное) описание задачи Найти стороны прямоугольника, вписанного в окружность радиуса R и имеющего наибольшую площадь S

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

Переменные, характеризующие объект управления: x1 … xm u1 y1 ur yn Входные переменные: возмущающие (внешние) воздействия (xk, k=1,2,…,m); управляющие воздействия (uj, j=1,2,…,r); Выходные переменные (yi, i=1,2,…,n).

Состояния объекта управления Статическое состояние Динамическое состояние

Статическое состояние Признаком статического состояния объекта управления является постоянство во времени переменных, характеризующих состояние объекта управления, т.е. dxi/dt = 0, где xi – переменные, характеризующие состояние объекта управления. Физически статическое состояние есть состояние, при котором имеет место Приход (энергии, вещества) = = Расход (энергии, вещества)

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

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

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

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

Классификация задач оптимизации

Классификация задач оптимизации 2) По области определения Неограниченными: x R – Безусловная задача оптимизации Ограниченными: x D(x) – Условные задачи оптимизации, или задачи с ограничениями, — это такие, при формулировке которых задаются некоторые условия (ограничения) на множестве;

Ограничения представляют собой различные технические, экономические, экологические условия, учитываемые при решении задачи. Ограничения представляют собой зависимости между переменными х1, х2, ... хn, задаваемые в форме неравенств или равенств f1(х1, х2, ... хn) < b1; f2(х1, х2, ... хn) = b2; . . . . . . . . . . . . . . . . . . . fm(х1, х2, ... хn) > bm. Общее количество ограничений равно m. Правые части ограничений, представляющие собой постоянные коэффициенты bj (j=1, 2, … m), называются свободными членами. Как и в выражении целевой функции, зависимости между переменными в системе ограничений могут быть линейными и нелинейными.

Граничные условия устанавливают диапазон изменения искомых переменных di ≤ хi ≤ Di, i=1, 2, … n, где di и Di - соответственно нижняя и верхняя границы диапазона изменения переменной xi. Наиболее часто в технических задачах все искомые переменные, как правило, неотрицательны. В этом случае граничные условия имеют следующий вид: хi ≥ 0, где i = 1, 2, ... n. При наличии ограничений и граничных условий ищется уже не абсолютный, а относительный экстремум целевой функции. На рис. показана некоторая функция одного переменного Z(x). Указан диапазон изменения переменной х (нижняя граница d и верхняя граница D). Видно, что абсолютный минимум функции соответствует точке 1, а относительный минимум – точке 2, принадлежащей заданному диапазону изменения переменной х.

3) По виду зависимости Зависимость между переменными в целевой функции может быть линейной или нелинейной. Линейной называется такая зависимость, в которую переменные xi входят только в первой степени и с этими переменными выполняются только действия сложения, вычитания и умножения на постоянный коэффициент. Такие задачи оптимизации называются задачами линейного программирования. Во всех других случаях зависимость будет нелинейной, а задачи оптимизации – задачами нелинейного программирования.

Пример задачи линейного программирования Обозначим через tj - время, в течении которого изделия выпускаются по j-ой технологии. Выпуск изделий за это время составит cj tj штук, а израсходовано будет единиц aij tj i- ого ресурса . Общее потребление каждого j-ого ресурса всеми технологическими процессами не должно превышать величины bi . Требуется найти при ограничениях .

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

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

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

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

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

Выбор критериев оптимальности для задач оптимизации объектов, находящихся в статическом и динамическом состояниях Критерии оптимальности для объектов, находящихся в статическом состоянии: для объектов с сосредоточенными параметрами – целевая функция в виде ; для объектов с распределенными параметрами – функционал в виде где , l – пространственная координата.

Динамическое состояние Признаком динамического состояния объекта управления является изменение во времени переменных, характеризующих состояние объекта управления, т.е. dxi/dt  0. Физически динамическое состояние есть состояние, при котором имеет место Приход (энергии, вещества) - Расход (энергии, вещества)  = Накопление или истечение (энергии, вещества).

Связь переменных при динамическом состоянии объекта Связь переменных при динамическом состоянии объекта управления: , или , где . Здесь - переменная, характеризующая состояние объекта управления.

Вариационное исчисление Задача о брахистохроне. В 1696 г. появилась заметка И. Бернулли с интригующим заглавием: «Новая задача, к решению которой приглашаются математики».

Введем в плоскости систему координат (х, у) так, чтобы ось х была горизонтальна, а ось у направлена вниз. В соответствии с законом Галилея, скорость тела М в точке с координатами (х, у (х)) если тело без трения спускается по кривой F(*) не зависит от формы кривой F(*) между точками А и (х, у(х)), а зависит лишь от ординаты у(х) и равна , где g—ускорение силы тяжести. Введем в плоскости систему координат (х, у) так, чтобы ось х была горизонтальна, а ось у направлена вниз. В соответствии с законом Галилея, скорость тела М в точке с координатами (х, у (х)) если тело без трения спускается по кривой F(*) не зависит от формы кривой F(*) между точками А и (х, у(х)), а зависит лишь от ординаты у(х) и равна , где g—ускорение силы тяжести. При этом требуется найти наименьшее время, которое потребуется на. преодоление пути от А к В, т. е. надо минимизировать интеграл

Критерии оптимальности для задач оптимизации объектов, находящихся в динамическом состоянии Критерии оптимальности для объектов, находящихся в динамическом состоянии есть функционал в виде: , где , t – время. Функционал есть математический оператор, который функции на входе ставит в соответствие число на выходе.

2. Одномерная оптимизация 2.1 Необходимые и достаточные условия экстремума функции одной переменной

Задачи оптим. проектирования Пусть требуется спроектировать бак горючего в виде прямого цилиндра заданного объема V, на изготовление которого будет затрачено наименьшее количество листовой стали.

Необходимые и достаточные условия минимума функции одной переменной

Пример 1. Аналитический поиск безусловного экстремума. Функция одной переменной

К примеру 1

Пример 2. Аналитический поиск условного экстремума. Функция одной переменной

Примеры исследования функции одной переменной на экстремум Пример 1. Q = (1-u)3. Необходимое условие экстремума : 3(1-u*)2(-1) = 0, (1-u*)2 = 0, u* =1. Достаточное условие экстремума = -6(1-u*) = -6(1-1) = 0, . k = 3 – нечетное. Ответ: при u* =1 исследуемая функция не имеет экстремума, это точка перегиба

Примеры исследования функции одной переменной на экстремум Пример 2. Q = (1-u)4. Необходимое условие экстремума: 4(1-u*)3(-1) = 0, u* =1. Достаточное условие экстремума = -12(1-u*)2 = -12(1-1)2 = 0, = 24(1-u*) = 24(1-1) = 0, = -24  0. k = 4 – четное, < 0 Ответ: при u* =1 исследуемая функция имеет минимум.

2. Одномерная оптимизация 2.2 Численные методы прямого поиска экстремума функции одной переменной

Достаточное условие унимодальности

Стратегия поиска экстремума