В.3. Основные этапы исследования. Краткая характеристика разделов курса МО.

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

Если - квадратичная форма, а функции , представляющие систему ограничений неравенств линейны, то задача МП называется задачей квадратичного программирования (КП).

В общем случае задачи МП – нелинейные задачи, т.е. - нелинейная функция переменных, - нелинейная функция.

4 – ПК. Этот этап предлагает детальный анализ полученного решения сравнения его с экспериментальными данными и дальнейшую корректировку МР, ММ и даже СПЗ.

5 – РР. Один из важных этапов, предполагающий защиту проекта (решенной проблемы) перед комиссией.

ЛК № 4

06.03.2003

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

В заключении В.3. выясним смысл термина " системное исследование".

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

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

В.4. Глобальный (абсолютный) оптимум, локальный (относительный) оптимум и связанные с ними определения и соотношения.

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

Итак, .

Аналогично определяется глобальный максимум.

Пусть т. , где - множество, на котором задана функция , а - окрестность т. , определяемая неравенством: , - евклидова норма, соответствующая разности векторов.

Если и выполняется неравенство: , то - локальный (относительный) минимум функции , а т. - локальный относительный план (решение) задачи минимизации.

Аналогично определяется локальный относительный максимум.

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

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

.

Более того, т. доставляет функции , где , максимальное значение, т.е. .

Смысл этого утверждения очевиден, если вспомнить примеры с функциями одной переменной.

Раздел 1

ЛК №5

13.03.2003

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

1.2. Достаточные условия для точки локального минимума (максимума).

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

(1)

Разложение (1) можно представить более кратко, используя понятие: " скалярное произведение векторов" и " векторно-матричное произведение".

(1')

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

,

Приращение функции на основании (1') можно записать в виде:

(3)

Учитывая необходимые условия: , . (4)

Подставим (3) в виде:

(4')

(5)

Квадратичная форма называется дифференциальной квадратичной формой (ДКФ).

Если ДКФ положительно определена, то и стационарная точка является точкой локального минимума.

Если же ДКФ и матрица , ее представляющая, отрицательно определены, то и стационарная точка является точкой локального максимума.

Итак, необходимое и достаточное условие для точки локального минимума имеют вид: , (эти же необходимые условия можно записать так: , , ).

- достаточное условие.

Соответственно, необходимое и достаточное условие локального максимума имеет вид:

, ( ), .

Вспомним критерий, позволяющий определить: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.

Критерий Сильвестра.

Позволяет ответить на вопрос: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.

Далее изложение будет относительно ДКФ и матрицы ее определяющей, т.е. ДКФ вида .

, - называется матрицей Гессе.

Главный определитель матрицы Гессе .

ЛК №6

20.06.2003

и ДКФ, которую оно представляет, будут положительно определенными, если все главные определители матрицы Гессе ( ) положительны (т.е. имеет место следующая схема знаков: ).

Если же имеет место другая схема знаков для главных определителей матрицы Гессе , например, , то матрица и ДКФ отрицательно определены.

ЛК №7

27.03.2003

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

Подставляем из (3) в целевую функцию (1), имеем:

(5)

Исследуемая функция на экстремум можно произвести методом Эйлера – методом безусловной оптимизации непрерывно дифференцируемой функции.

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

Недостаток метода исключения: трудности, а иногда и невозможность получения системы выражений (3). Свободный от этого недостатка, но требующий выполнения условия (4) является ММЛ.

1.5.2. Метод множителей Лагранжа. Необходимые условия в классической задаче условной оптимизации. Функция Лагранжа .

ММЛ позволяет исходную задачу классической условной оптимизации:

(1)

(2)

Преобразовать в задачу безусловной оптимизации специально " сконструированной" функции – функции Лагранжа:

, (3)

где , - множители Лагранжа;

.

Как видно, представляет собой сумму, состоящую из исходной целевой функции и " взвешенной" суммы функций , - функции, представляющие их ограничения (2) исходной задачи.

Ключевое

выражение!!!

Пусть точка - точка безусловного экстремума функции , тогда, как известно, , , или (полный дифференциал функции в точке ).

Используя концепция зависимых и независимых переменных - зависимые переменные; - независимые переменные, тогда представим (5) в развернутом виде:

(5')

Из (2) с очевидностью следует система уравнений вида:

, (6)

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

Представим (6) в " развернутом" виде, используя концепцию зависимых и независимых переменных:

, (6')

Заметим, что (6') в отличии от (5') представляет собой систему, состоящую из уравнений.

Умножим каждое -ое уравнение системы (6') на соответствующий -ый множитель Лагранжа. Сложим их между собой и с уравнением (5') и получим выражение:

(7)

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

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

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

, (8)

Перепишем (8) в виде:

, (8')

Система (8') представляет собой систему из линейных уравнений относительно известных: . Система разрешима, если (вот почему, как и в методе исключения в рассматриваемом случае должно выполняться условие ). (9)

Поскольку в ключевом выражении (7) первая сумма равна нулю, то легко понять, что и вторая сумма будет равняться нулю, т.е. имеет место следующая система уравнений:

(10)

Система уравнений (8) состоит из уравнений, а система уравнений (10) состоит из уравнений; всего уравнений в двух системах, а неизвестных : , .

Недостающие уравнений дает система уравнений ограничений (2): , .

Итак, имеется система из уравнений для нахождения неизвестных:

(11)

Полученный результат – система уравнений (11) составляет основное содержание ММЛ.

Легко понять, что систему уравнений (11) можно получить очень просто, вводя в рассмотрение специально сконструированную функцию Лагранжа (3).

Действительно,

, (12)

, (13)

Итак, система уравнений (11) представима в виде (используя (12), (13)):

(14)

Система уравнений (14) представляет необходимое условие в классической задаче условной оптимизации.

ЛК №8

03.04.2003

Найденное в результате решение этой системы значение вектора называется условно-стационарной точкой.

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

ЛК №9

10.04.2003

;

; , потому что об этом " говорят" необходимые условия.

.

Вышесказанное позволяет сформулировать алгоритм ГФА метода решения классической задачи условной оптимизации:

1) строим семейство линий уровня целевой функции: ; ;

2) строим ОДР, используя уравнение ограничения ;

3) с целью внесения исправления возрастания функции , находим и выясняем характер экстремальных точек;

4) исследуем взаимодействие линий уровня и функции , находя при этом из системы уравнений координаты условно-стационарных точек – локальных условных минимумов и локальных условных максимумов.

5) вычисляем .

Следует особо отметить, что основные этапы ГФА метода решения классической задачи условной оптимизации совпадают с основными этапами ГФА метода решения задач НП и ЛП, отличие лишь в ОДР , а также в нахождении местоположения экстремальных точек в ОДР (например, в задачах ЛП эти точки обязательно находятся в вершинах выпуклого многоугольника, представляющего ОДР ).

О практическом смысле ММЛ.

Представим классическую задачу условной оптимизации в виде:

(1)

(2)

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

Повторить вопрос о седловой точке функции двух переменных.

В пространстве задача (1), (2) принимает вид:

(1')

, где - переменная величина. (2')

Пусть - точка условного экстремума: . При изменении изменяется , т.е. . Соответственно изменится и значение целевой функции: .

Вычислим производную: . (3)

(4)

(5)

Из (3), (4), (5) . (6)

Из (5) . (5')

Подставим (5') в (3) и получаем:

(6')

Из (6) , что множитель Лагранжа характеризует " реакцию" значение (ортогональна значению целевой функции) на изменения параметра .

В общем случае (6) принимает вид: ; . (7)

Из (6), (7) , что множитель , характеризует изменение при изменении соответствующего -того ресурса на 1.

Если - максимальная прибыль или минимальная стоимость, то , характеризует изменения этой величины при изменении , на 1.

1.5.6. Классическая задача условной оптимизации, как задача о нахождении седловой точки функции Лагранжа: .

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

(1)

Повторить вопрос о выпуклых множествах и выпуклых функциях.

Очевидно, что из (1) . (2)

Из (2) , что . (3)

Как видно система (3) содержит уравнений, подобных тем уравнениям, которые представляют необходимое условие в классической задаче условной оптимизации:

(4)

где - функция Лагранжа.

В связи с аналогией систем уравнений (3) и (4), классическую задачу условной оптимизации можно рассматривать как задачу о нахождении седловой точки функции Лагранжа.

ЛК №10

17.04.2003

Раздел 2

Метод дихотомии (МД) (метод деления отрезка пополам).

Сущность МД легко понять, рисуя следующую графическую иллюстрацию.

На отрезке задана функция с одним минимумом ( унимодальная ).

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

; ; .

Если , то , .

Если , то , .

Вычисляем до тех пор, пока ,

.

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

Тогда при .

Метод Фибоначчи.

Этот метод использует последовательность чисел Фибоначчи, представляемого рекуррентным соотношением:

ЛК №12

15.05.2003

Алгоритм МФ сходен с алгоритмом МЗС.

МФ лишь немного эффективнее МД.

Градиентные методы.

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

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

В прямоугольной системе координат

;

- вектор, направленный в сторону наискорейшего убывания функции.

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

.

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