Лекция_1_merged. Лекция 1. Предмет и задачи методов оптимизации
 Скачать 3.42 Mb.
|
Лекция №1. Предмет и задачи методов оптимизации Цель курса состоит в изучении теоретических основ и методов решения так называемых экстремальных задач, сводящихся к максимизации или минимизации некоторых функций на множествах, определяемых некоторыми ограничениями. Необходимость решения таких задач возникает в различных областях человеческой деятельности, когда из многих возможных вариантов своего поведения или принятия решения необходимо выбрать один вариант. Математическое моделирование в оптимизации Для того чтобы использовать результаты и вычислительные процедуры теории оптимизации на практике, необходимо прежде всего сформулировать рассматриваемую задачу на математическом языке, т.е. построить математическую модель объекта оптимизации. Математическая модель - это более или менее полное математическое описание исследуемого процесса или явления. В большинстве реальных ситуаций дать исчерпывающее математическое представление оптимизируемой системы с учетом всех взаимосвязей ее частей, взаимодействий с внешним миром, всех целей ее функционирования бывает затруднительно или невозможно. Поэтому при построении математической модели необходимо, как правило, выделять и учитывать в дальнейшем только наиболее важные, существенные стороны исследуемого объекта, и отбрасывать все факторы, которые, как можно ожидать, почти не повлияют на результат. В процессе построения математической модели необходимо: 1 . Определить границы объекта оптимизации Этап состоит в выделении главных переменных, параметров, факторов и ограничений. Неважные параметры следует отбросить, и в дальнейшем не учитывать. 2. Выбрать управляемые переменные На этом этапе математического моделирования необходимо провести различие между теми величинами, значения которых можно варьировать и выбирать с целью достижения наилучшего результата (управляемыми переменными), и величинами, которые фиксированы или определяются внешними факторами. Как правило, в математическом описании задачи управляемые переменные обозначаются как неизвестные « х 1 , x 2 …», а неуправляемые – конкретными числовыми значениями. Определение тех значений управляемых переменных, которым соответствует наилучшая (оптимальная) ситуация, и представляет собой задачу оптимизации. 3. Выбор целевой функции Целевая функция представляет собой формулу, выражающую цель оптимизации. Например, если целью является максимальная прибыль, целевая функция – это функция для расчета прибыли. В зависимости от конкретной задачи целевая функция должна стремиться достичь минимума или максимума. Например: 12x 1 -4x 2 +7 max В инженерной практике используется широкий спектр критериев оптимизации. Например, это могут быть критерии экономического характера, такие, как себестоимость, прибыль, капитальные затраты и т.д., технические или физические параметры системы - продолжительность технологического процесса, потребляемая энергия, максимальная механическая нагрузка, достигнутая скорость движения и другие. 4. Определение ограничений на управляемые переменные В реальных условиях на значения управляемых переменных, как правило, наложены ограничения, связанные с ограниченностью имеющихся ресурсов, мощностей и других возможностей. При построении математической модели эти ограничения обычно записывают в виде равенств и неравенств или указывают множества, которым должны принадлежать значения управляемых переменных. Например: В общем виде: g(X)≤0 Конкретное неравенство: x 1 +8x 2 -8≥0 Задание допустимого интервала: x [0;7] Совокупность всех ограничений на управляемые переменные определяет так называемое допустимое множество задачи оптимизации, обозначаемое U. 5. Окончательная формулировка математической модели задачи оптимизации Объединяя результаты предыдущих этапов построения математической модели, исходную задачу записывают в виде математической задачи оптимизации, включающей построенную целевую функцию и найденные ограничения на управляемые переменные. В общем виде математическую задачу оптимизации можно сформулировать следующим образом: минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные. При записи математических задач оптимизации в общем виде обычно используется следующая символика: (max) min ) ( X f , ( 1) U X , где ) ( X f - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные. Типы точек экстремума (экстремальных точек.) Экстремумами функции являются ее минимумы и максимумы. Точки, в которых функция достигает своего минимального (максимального) значения, называются точками минимума (максимума). Можно выделить несколько типов точек минимума и максимума, в частности: локальные или глобальные экстремумы, слабые или сильные экстремумы. Определение 1. Точка X* называется точкой слабого глобального (абсолютного) минимума или просто точкой минимума функции ) ( X f на множестве U, если ) ( ) ( X f X f для всех U X . Значение U X X f X f f | ) ( min ) ( называется глобальным (абсолютным) минимумом или просто минимумом функции ) ( X f на U. Множество всех точек минимума функции ) ( X f на U будем обозначать через U . Определение 2. Число U X называется точкой слабого локального минимума функции ) ( X f на U, если ) ( ) ( x f X f для всех U X , достаточно близких к X , т.е. если существует число 0 такое, что это неравенство выполняется для любого X U X X X U x : Определение 3. Если в определениях 1 и 2 заменить нестрогое неравенство на строгое: ) ( ) ( * X f X f , то соответствующая точка X* будет называться точкой сильного глобального либо сильного локального минимума. Рис. 1. Точка сильного глобального минимума. На рис.2 можно видеть различные типы экстремумов: Рис.2. Различные типы точек минимума. Под минимизацией (максимизацией)функции n переменных ) ,..., ( ) ( 1 n x x f X f на заданном множестве U n - мерного векторного пространства n E понимается определение хотя бы одной из точек минимума (максимума) X * =(x 1 * , x 2 * ,…x n * ) этой функции на множестве U , а также, если это необходимо, и минимального (максимального) на U значения ) ( * X f В зависимости от вида математической модели все задачи оптимизации разделяются на группы. Для каждой группы применяются свои методы оптимизации: Если целевая функция единственная, то задачу оптимизации называют задачей математического программирования, если же критерием оптимальности является требование достижения экстремального значения несколькими функциями управляемых параметров – задачей многокритериальной оптимизации. Если целевая функция и ограничения задачи математического программирования являются линейными относительно управляющих параметров, то говорят о задаче линейного программирования. При нелинейной зависимости целевой функции или ограничений от управляемых параметров говорят о задаче нелинейного программирования. Если при линейных ограничениях минимизируемая целевая функция является квадратичной формой, то говорят о задаче квадратичного программирования. В случае, когда целевая функция является отношением двух линейных функций, а ограничения линейны, имеем задачу дробно- линейного программирования. Задачи оптимизации, в которых необходимо найти наименьшее значение выпуклой целевой функции на выпуклом множестве, называют задачами выпуклого программирования. Если множество допустимых управляющих параметров оказывается конечным множеством, то мы имеем задачу дискретного программирования. А если к тому же координаты этих точек – целые числа, то говорят о задаче целочисленного программирования. Необходимые и достаточные условия минимума. Напомним некоторые понятия и факты, известные из курса математического анализа. Вектор n x X f x X f X f ) ( ,..., ) ( ) ( 0 1 0 0 называется градиентом функции ) ( X f в точке 0 X . В малой окрестности точки 0 X градиент указывает направление наискорейшего возрастания функции ) ( X f , а его норма характеризует скорость этого возрастания. Градиент в точке 0 X перпендикулярен линии (поверхности) уровня c X f ) ( , проходящей через эту точку. Условие 1: Если в точке n E X 0 функция ) ( X f дифференцируема и достигает локального минимума, то 0 ) ( 0 X f или n j x X f j ,..., 1 , 0 ) ( 0 ( 2) (необходимое условие минимума). Точки, в которых выполнено условие (3.12), называются стационарными точками дифференцируемой функции ) ( X f Если функция ) ( X f дважды дифференцируема в точке n E X 0 , то существует матрица вторых производных (матрица Гессе, гессиан) n n j i x x X f X f ) ( ) ( 0 2 0 ( 3) Из курса линейной алгебры известен критерий Сильвестра: матрица ) ( ij a A называется положительно определенной, если все ее угловые миноры положительны: 0 11 1 a ; 0 22 21 12 11 2 a a a a ;…; nn n n n a a a a 1 1 11 . ( 4) Здесь знак | | означает определитель мартицы. Соответственно: матрица ) ( ij a A называется отрицательно определенной, если знаки ее угловых миноров чередуются, начиная с минуса: 0 11 1 a ; 0 22 21 12 11 2 a a a a ;…; nn n n n a a a a 1 1 11 ( 5) Условие 2: Если в стационарной точке n E X 0 функция ) ( X f дважды дифференцируема и матрица ее вторых производных ) ( X f (Гессиан) положительно определена, то 0 X есть точка локального минимума ) ( X f (достаточное условие минимума). Условия 1 и 2 лежат в основе классического метода минимизации функций, дифференцируемых во всем пространстве n E . Приведем алгоритм этого метода. Шаг 1. Решив систему уравнений (3.12), найти все стационарные точки функции ) ( X f Шаг 2. Используя достаточные условия минимума, среди стационарных точек функции ) ( X f найти точки локального минимума и, сравнивая значения функции в них, определить точки глобального минимума. Существует Три основных класса задач нелинейной оптимизации: 1. Одномерные задачи безусловной оптимизации. 2. Многомерные задачи безусловной оптимизации. 3. Многомерные задачи условной оптимизации. Проблемы первого класса решить легче всего, в то время как проблемы третьего класса являются наиболее трудными. В дальнейших лекциях мы рассмотрим все классы этих задач. Лекция №2. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ Изложение методов оптимизации начнем с рассмотрения простейшей математической модели оптимизации, в которой целевая функция зависит от одной переменной. Такие задачи возникают при изучении объектов, зависящих от одной скалярной переменной, когда требуется выбрать эту переменную наилучшим в том или ином смысле образом. Кроме того, эти задачи входят как составная часть во многие итерационные методы решения задач минимизации функций многих переменных и других более сложных экстремальных задач. С задачами минимизации функций одной переменной мы впервые сталкиваемся при изучении начальных глав математического анализа и решаем их методами дифференциального исчисления. Может показаться, что задачи минимизации функций одной переменной достаточной просты и методы их решения хорошо разработаны и изучены. Однако это не совсем так. Оказалось, что методы дифференциального исчисления находят ограниченное применение и далеко не всегда удобны для реализации в компьютерных программах. Хотя в последнее время и появились другие, более удобные для реализации, методы, но, тем не менее, эту область экстремальных задач нельзя считать завершенной. Мы остановимся на некоторых наиболее известных методах, достаточно хорошо проявивших себя на практике. Постановка задачи одномерной оптимизации Пусть функция ) (x f определена на некотором множестве U вещественной оси x x E : 1 . Поскольку максимизация целевой функции max ) ( x f эквивалентна минимизации противоположной величины min ) ( x f , будем рассматривать только задачу минимизации функции ) (x f на множестве U. Теперь можем перейти к формулировке постановки задачи одномерной оптимизации как задачи минимизации функции ) (x f на множестве U. Условимся, что запись U x x f | ) ( min ( 1) или эквивалентная ей: ) ( min x f U x , ( 2) или f(x) min ( 3) x U будет означать, что ставится задача определения величины ) ( inf x f f U x Причем в задаче (2.1) неважно, будет ли множество U точек минимума ) (x f на U непустым, или оно пусто. В случае, когда множество U непусто, требуется наряду с f найти точку U x Классический метод решения задачи одномерной оптимизации Под классическим методом подразумевается подход к поиску точек экстремума функции, который основан на дифференциальном исчислении. Из математического анализа известны необходимые и достаточные условия экстремума функции одной переменной. Пусть функция ) (x f кусочно-непрерывна и кусочно-гладка на отрезке ] ; [ b a . Это значит, что на отрезке ] ; [ b a может существовать лишь конечное число точек, в которых ) (x f либо терпит разрыв первого рода, либо непрерывна, но не имеет производную. Тогда как известно точками экстремума функции ) (x f на ] ; [ b a могут быть лишь те точки, в которых выполняется одно из следующих условий: 1) либо ) (x f терпит разрыв; 2) либо ) (x f непрерывна, но производная ) (x f не существует; 3) либо производная существует и равна нулю; 4) либо граничные точки отрезка ] ; [ b a Все такие точки принято называть точками, подозрительными на экстремум. Поиск точек экстремума функции ) (x f начинают с нахождения всех «подозрительных» точек. После того как все эти точки найдены, проводят дополнительное исследование и отбирают среди них те, которые являются точками локального минимума или максимума. Для этого обычно исследуют знак первой производной ) (x f в окрестности подозрительной точки. Для того, чтобы подозрительная точка x была точкой локального минимума, |