Лекция_1_merged. Лекция 1. Предмет и задачи методов оптимизации
 Скачать 3.42 Mb.
|
|
, n j , 1 . ( 9) Умножив равенства (4) на произвольные множители i и сложив с (5) получим: 0 ) ( ) ( 1 * * m i j i i j x X g x X f n j ,..., 1 ( 10) (числа i называют множителями Лагранжа). Тогда в результате для определения точки * X получим систему из m n уравнений: n j x X g x X f m i j i i j ,..., 1 , 0 ) ( ) ( 1 * * ( 11) m i X g i ,..., 1 , 0 ) ( * ( 12) содержащую m n неизвестных m n x x ,..., , ,..., 1 * * 1 Соотношения (7)—(8) являются необходимыми условиями минимума функции ) ( X f из на множестве U , заданном ограничениями (2). С другой стороны, они определяют стационарные точки так называемой функции Лагранжа задачи (1) - (2): m i i i X g X f X L 1 ) ( ) ( ) , ( , потому что равенства (7) можно интерпретировать как 0 j x L , а равенства (8) - как 0 i L Опишем алгоритм решения задачи методом множителей Лагранжа. Шаг 1. Составить функцию Лагранжа ) , ( X L Шаг 2. Найти частные производные от ) , ( X L по переменным j x и i и приравнять их к нулю. Шаг 3. Найти стационарные точки функции Лагранжа, т.е. решить полученную систему уравнений. Шаг 4. С помощью достаточного условия минимума функции отобрать среди найденных стационарных точек точки локального условного минимума. Шаг 5. Сравнить значения функции в точках локального условного минимума и найти точку глобального минимума. Замечание. Система уравнений (7) - (8) представляет собой необходимые условия минимума функции Лагранжа ) , ( X L в пространстве m n E . Поэтому ее решения на шаге 3 можно искать численными методами, например, методом деформируемого многоранника, минимизируя ) , ( X L Пример 2. Минимизировать функцию двух переменных 2 2 2 1 ) ( x x X f при ограничении 0 2 2 ) ( 2 1 x x X g Шаг1. Составим функцию Лагранжа: 2 2 ) 2 2 ( ) , , ( 2 1 2 2 2 1 2 1 2 2 2 1 2 1 x x x x x x x x x x L Шаг2. Составим систему уравнений 0 0 0 2 1 L x L x L 0 2 2 0 2 0 2 2 2 1 2 1 x x x x Решим ее, выразив переменные 1 x и 2 x из первых двух уравнений через : 1 x , 2 2 x , и подставив полученные соотношения в третье уравнение: 0 2 2 2 , откуда 5 4 Следовательно: 5 4 * 1 x ; 5 2 * 2 x Методы условной оптимизации с ограничениями типа равенств и неравентсв. Рассмотрим в общей постановке задачу нелинейного программирования, заключающуюся в отыскании минимума функции многих переменных при заданных ограничениях в виде равенств и неравенств. Как и ранее, обозначим целевую функцию как ) ,..., , ( ) ( 2 1 n x x x f X f , функции, задающие ограничения типа равенств как ) ,..., , ( ) ( 2 1 n j j x x x h X h , m j ,..., 1 ; а ограничения, задающиеся неравенствами как ) ,..., , ( ) ( 2 1 n s s x x x g X g , p s ,..., 1 Тогда задачу с ограничениями можно представить как (max) min ) ( X f , ; ,..., 1 , 0 ) ( m j X h j ( 13) p s X g s ,..., 1 , 0 ) ( Допустимую область, задаваемую ограничениями типа равенств и неравенств, назовем R: p s X g m j X h E X R s j n ,..., 1 , 0 ) ( ; ,..., 1 , 0 ) ( ( 14) Рассмотрим методы, использующие преобразование задачи условной оптимизации (8) в эквивалентную последовательность задач безусловной оптимизации путѐм введения в рассмотрение вспомогательных функций. Эти методы называют методами последовательной безусловной оптимизации. Метод штрафных функций В соответствии с основной идеей исходную задачу } | ) ( min{ R X X f со смешанными ограничениями сводим к решению последовательности задач поиска безусловного минимума некоторой вспомогательной функции, то есть задачи вида ,... 2 , 1 , | , , min k E X r X P X f r X F n k k , ( 15) где ) , ( k r X P - присоединённая функция, играющая роль штрафа за нарушение ограничений исходной задачи } ,..., 1 , 0 ) ( ; ,..., 1 , 0 ) ( | { p s X g m j X h E X R s j n ; k r – весовой коэффициент, с помощью которого достигается компромисс между необходимостью удовлетворения ограничений и процессом минимизации целевой функции ) ( X f Заметим, что функция (10) не имеет ограничений, следовательно, ее минимум мог бы быть найден любыми методами безусловной оптимизации (методом деформируемого многогранника, градиентным методом и др.). Присоединѐнная функция ) , ( k r X P , называемая штрафной функцией, подбирается так, чтобы при больших k расширенная функция ) , ( k r X F мало отличалась от ) ( X f при R X и быстро возрастала при удалении точки X от допустимой области R . При этом можно выбрать ) , ( k r X P так, чтобы расширенная функция ) , ( k r X F обладала свойствами, позволяющими использовать для решения задач (10) достаточно эффективные методы безусловной минимизации. Итак, при практическом построении штрафной функции ) , ( k r X P необходимо учитывать, что она должна принимать бесконечно малые значения при выполнении ограничений исходной задачи и достаточно большие при их нарушении. Метод внешней точки. Такими свойствами обладает, например, штрафная функция вида m j p s s j k k X q X h r r X P 1 1 2 2 , , ( 16) где 0 , 0 , 0 , , 0 min X g X g X g X g X q s s s s s Как нетрудно заметить, функция (11) тождественно равна нулю, если R X , то есть если выполняются все ограничения исходной задачи. Но при нарушении хотя бы одного из ограничений возникает "штраф", величину которого можно сделать сколь угодно большой за счѐт выбора параметра 0 k r . Поэтому при решении последовательности задач (10) требуют выполнения условия k r при k , чем достигается возрастание штрафной функции ) , ( k r X P при k . При этом минимизация расширенной функции ) , ( k r X F обеспечивает выполнение ограничений исходной задачи со всѐ большей точностью. Обычно, если штрафная функция строится в виде (11), начальная точка поиска выбирается вне допустимой области R . На каждом k-том этапе определяется точка ) ( k r X минимума расширенной функции ) , ( k r X F при заданном значении параметра k r с помощью одного из методов безусловной минимизации. Полученная точка ) ( k r X используется в качестве начальной на следующем этапе, выполняемом при большем значении параметра k r . При непрерывном возрастании k r последовательность точек ) ( k r X стремится к точке X - точному решению исходной задачи (8). В качестве условия окончания поиска можно использовать неравенства 1 ) ), ( ( k k r r X P , 2 1 * * k k r X r X , ( 17) где 2 1 , параметры точности. Поскольку элементы последовательности )} ( { k r X приближаются к точке X извне допустимой области, рассмотренный метод называют методом внешней точки. Метод барьерных функций Этот метод применяется для решения задач условной оптимизации с ограничениями только типа неравенств, то есть задач вида p s X g X f s ,..., 1 , 0 | min ( 18) Идея метода заключается в сведении задачи (13) к последовательности задач безусловной минимизации n k k E X r X P X f r X F ) , ( ) ( ) , ( min , ( 19) где присоединенная функция ) , ( k r X P выбирается таким образом, чтобы при больших k она мало отличалась от целевой функции ) ( X f во внутренних точках R X , но неограниченно возрастала при приближении точки X к границе области R . Влияние такой функции при больших k состоит в создании "барьера" с крутыми склонами вдоль границы допустимой области. Поэтому они и называются барьерными функциями. Такими свойствами обладает, например, функция p s s k k X g r r X P 1 ) ( 1 ) , ( ( 20) Она определена и непрерывна внутри области R , то есть на множестве p s X g E X s n ,..., 1 , 0 ) ( и стремится к бесконечности при приближении к границе этой области R изнутри. Начальная точка задаѐтся только внутри области R . На каждом k-ом этапе ищется точка ) ( * k r X минимума расширенной функции при заданном значении k r с помощью одного из методов безусловной минимизации. Полученная точка ) ( * k r X используется в качестве начальной на следующем этапе, выполняемом при уменьшающемся значении параметра k r . При 0 k r последовательность точек ) ( * k r X стремится к точке условного минимума X . Барьерные функции как бы препятствуют выходу из множества R , а если решение задачи лежит на границе, то процедура метода приводит к движению изнутри области к границе. В качестве критерия останова можно использовать те же неравенства (12), что и в методе штрафных функций. Согласно описанной процедуре точки ) ( * k r X лежат внутри допустимой области для каждого k r . Этим объясняется, что метод барьерных функций иногда называют методом внутренней точки. Комбинированный метод штрафных функций Вернемся к рассмотрению задачи условной оптимизации (max) min ) ( X f , ; ,..., 1 , 0 ) ( m j X h j (8) p s X g s ,..., 1 , 0 ) ( со смешанными ограничениями. Данный метод является обобщением методов, описанных выше. А именно, для учета ограничений типа равенств применяют штрафные функции как в методе внешней точки, для ограничений типа неравенств – барьерные функции как в методе внутренней точки. Таким образом, в основе комбинированного метода лежит сведение исходной задачи условной минимизации } | ) ( min{ R X X f к последовательности задач без ограничений вида n k k E X r X P X f r X F ) , ( ) ( ) , ( min , где присоединенная функция имеет вид p s s k m j j k k X g r X h r r X P 1 1 2 ) ( 1 1 ) ( ) , ( ( 21) Начальная точка задается внутри допустимой области R , то есть при строгом выполнении ограничений типа неравенств p s X g s ,..., 1 0 ) ( . На каждом k-том этапе точка минимума расширенной функции ) , ( k r X F ищется при заданном значении k r с помощью одного из методов безусловной минимизации. Полученная точка ) ( * k r X используется в качестве начальной на следующем этапе, выполняемом при увеличивающемся значении параметра k r . При k r последовательность точек ) ( * k r X стремится к точному решению X исходной задачи. Лекция № 8 Линейное программирование Постановка задачи линейного программирования Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции n j j j x c X f 1 ) ( ( 1) при условиях n j i j ij m i b x a 1 ; ,..., 1 , n j i j ij p m i b x a 1 ; ,..., 1 , ( 2) n j i j ij q p i b x a 1 ; ,..., 1 , ( 3) , ,..., 1 , 0 n j x j ( 4) где j i ij c b a , , - заданные постоянные величины и n n q p p m 0 , , Функция (1) называется |