Методичка по курсовым и лабораторным работам

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МГАПИ

УТВЕРЖДАЮ

Проректор по УР

____________ Соколов В.В.

«___» ___________ 2002 г.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению курсовых и лабораторных работ по дисциплине

«Методы оптимизации»

Рекомендуется для направления подготовки

дипломированного специалиста

654600 – «Информатика и вычислительная техника»

специальности – 22.02.00.

Автоматизированные системы обработки

информации и управления.

Москва 2002

АННОТАЦИЯ

Методические указания соответствуют программе курса “Методы оптимизации” для студентов специальности 22.02.03.

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

Авторы: Казаков С.А., Правоторова Н.А.

Научный редактор: проф. Петров О.М.

Рецензент:

Рассмотрено и одобрено на заседании кафедры ИТ-7

"__"____________2002 г. Зав. кафедрой __________О.М. Петров

Ответственный от кафедры за выпуск учебно-методических материалов

доц. Правоторова Н.А.

СОДЕРЖАНИЕ

Введение

Тема 1. Задачи одномерной безусловной минимизации

1.1. Постановка задачи

1.2. Метод перебора

1.3. Метод поразрядного поиска

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

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

1.6. Метод золотого сечения

1.7. Метод средней точки

1.8. Метод Ньютона

Тема 2. Задачи многомерной безусловной минимизации

2.1. Необходимые сведения из курса линейной алгебры

2.2. Постановка задачи многомерной оптимизации

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

2.4. Методы спуска

2.5. Метод градиентного спуска с дроблением шага

2.6. Метод наискорейшего спуска

2.7. Метод сопряженных градиентов

2.8. Метод покоординатного спуска

2.9. Метод Ньютона

Тема 3. Задачи многомерной оптимизации при наличии ограничений. Линейное программирование

3.1. Постановка и классификация задач математического программирования

3.2. Постановка задачи линейного программирования

3.3. Графическое решение ЗЛП

3.4. Симплекс-метод

3.5. Метод искусственного базиса

Указания к выполнению лабораторных работ

Указания к выполнению типового расчета

Краткие сведения о математиках

Список литературы

ВВЕДЕНИЕ

Всякая задача, в которой ищется максимум или минимум некоторой функции n действительных переменных f(x₁, x₂, …, x_n), относится к задачам оптимизации. Функция f(x₁, x₂, …, x_n) называется целевой функцией. Если на переменные x_i не наложено ограничений, т. е. -¥ < x_i <¥, то задача оптимизации называется задачей безусловной оптимизации, в противном случае говорят о задаче условной оптимизации. В силу того, что max f(x₁, x₂, …, x_n) = -min(-f(x₁, x₂, …, x_n)), всегда можно свести задачу оптимизации к задаче минимизации. Учитывая это, будем в дальнейшем говорить о задаче минимизации функции f(x₁, x₂, …, x_n).

Тема 1. Задачи одномерной безусловной минимизации

1.1. Постановка задачи

Пусть f(x) – действительная функция одной переменной, определенная на множестве X Ì (-¥, ¥). Точка x^* Î X называется точкой локального минимума f(x) на множестве X, если существует такая e-окрестность этой точки, что для всех x из этой окрестности, т. е., если | x - x^*| < e, выполняется условие f(x^*) £ f(x). Если выполняется условие f(x^*) < f(x), то x^* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x^*Î X называется точкой глобального минимума f(x) на множестве X, если для всех x Î X выполняется условие f(x^*) £ f(x). Значение функции f(x^*) называется минимальным значением f(x) на множестве X, Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение.

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

Известно, что для того, чтобы точка x^* была точкой локального минимума дифференцируемой функции f(x), необходимо, чтобы выполнялось равенство

f '(x^*) = 0. (1.1)

Точка x^*, удовлетворяющая равенству (1.1), называется стационарной точкой. Если функция f(x) дважды дифференцируема, то для того, чтобы стационарная точка x^* была точкой строгого локального минимума, достаточно, чтобы выполнялось неравенство

f ''(x^*) > 0. (1.2)

Если дважды дифференцируемая функция f(x) задана на отрезке [a, b], то можно предложить следующий путь решения задачи нахождения глобального минимума:

1. Найти все стационарные точки на отрезке [a, b] из условия (1.1), т.е. найти корни уравнения f '(x) = 0, принадлежащие отрезку [a, b].

2. Найденные стационарные точки исследовать на выполнение условия (1.2), т.е. из найденных стационарных точек выделить точки локальных минимумов, для которых выполняется неравенство f ''(x) > 0.

3. Сравнить между собой значения f(x) на концах отрезка [a, b] и в точках локальных минимумов. Наименьшему из этих значений соответствует точка глобального минимума f(x) на отрезке [a, b].

Пусть функция f(x) определена на отрезке [a, b]. Функция f(x) называется унимодальной, если на этом отрезке имеется единственная точка x^* локального минимума функции f(x), причем функция строго убывает при x £ x^* и строго возрастает при x ³ x^*. Многие алгоритмы минимизации функции одной переменной построены в предположении, что функция унимодальна на некотором отрезке. Этот отрезок будем называть отрезком локализации точки x^*.

Из определения унимодальной функции вытекает следующее важное свойство. Пусть f(x) унимодальная функция на отрезке [a, b] и a £ x₁ < x₂ £ b. Тогда

если f(x₁) £ f(x₂), то x^* Î [a, x₂];

если f(x₁) > f(x₂), то x^* Î [x₁, b], (1.3)

где x^* – точка минимума f(x) на отрезке [a, b].

Иллюстрация свойства (1.3) представлена на рис 1.1 и 1.2.

Рис. 1.1

Рис. 1.2.

Аналитический метод нахождения минимума функции одной переменной состоит в решении в явном виде уравнения (1.1) и проверке условия (1.2). Однако во многих случаях это или невозможно, или затруднительно. В таких случаях используются численные методы решения. Мы будем рассматривать методы прямого поиска, основанные на построении минимизирующих последовательностей x₁, x₂, …, x_n, …,. Точки x₁, x₂, …, x_n, … называют пробными точками.

1.2. Метод перебора

Этот метод является простейшим из прямых методов минимизации.

Пусть f(x) – унимодальная на отрезке [a, b] функция. Разобьем отрезок [a, b] на n равных частей точками x₀, x₁, x₂, …, x_n, так, что x_i = a + ih, i = 0, 1, … , n, h = . Вычислим значения функции f(x) в точках x_i и сравнив их, найдем точку x_m, для которой f(x_m) = f(x_i).

За приближение x^* примем x_m.

Оценим погрешность метода перебора.

В силу выбора точки x_m справедливы неравенства

f(x_m–1) ³ f(x_m), т.е. x^* Î [x_m–1, b];

f(x_m) £ f(x_m+1), т.е. x^* Î [a, x_m+1].

Следовательно, x^* Î [x_m–1, b]Ç [a, x_m+1] = [x_m–1, x_m+1]. Длина отрезка [x_m–1, x_m+1] равна , и точка x_m является его серединой. Поэтому

çx_m – x^*ç£ = e_n.

Итак, чтобы обеспечить требуемую точность e определения минимума функции f(x) методом перебора, нужно число отрезков разбиения n выбрать из условия £ e, т.е.

n ³ . (1.4)

Пример 1.1.

Найдем минимум функции f(x) = x⁴ + e ^–x, x Î [0, 1] с точностью до e = 0.1.

Число отрезков разбиения найдем из условия (1.4):

n ³ = 10.

Определим величину шага h:

h = = = 0.1.

Вычислим значения функции f(x) в точках x_i = a + ih = 0.1× i, i = 0, 1, … , 10. Эти значения представлены в таблице 1.1.

Таблица 1.1

Из таблицы 1.1 видно, что минимальное из вычисленных значений есть f(0.5) = 0.67. Таким образом, x^* » 0.5 и f(x^*) » 0.67.

1.3. Метод поразрядного поиска

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

Изложенная идея реализуется в методе поразрядного поиска следующим образом. Перебор точек отрезка происходит сначала с шагом D = x_i+1– x_i >e до тех пор, пока функция не начнет увеличиваться, т. е. не выполнится условие f(x_i+1) ³ f(x_i) или пока очередная точка не совпадет с правым концом отрезка [a, b], на котором ищется минимум функции f(x). После этого шаг уменьшается (обычно в четыре раза) и перебор точек производится в обратном направлении, справа налево, пока значения функции f(x) снова не станут увеличиваться или очередная точка не совпадет с левым концом отрезка и т. д. Процесс завершается, когда перебор в данном направлении закончен, и величина шага не превосходит заданной точности e.

Алгоритм 1.1 (Алгоритм метода поразрядного поиска).

Шаг 1. Ввести исходные данные: a, b, e.

Шаг 2. Выбрать начальный шаг D = . Положить x₀ = a. Вычислить f(x₀).

Шаг 3. Положить x₁ = x₀ + D. Вычислить f(x₁).

Шаг 4. Сравнить f(x₀) и f(x₁). Если f(x₀) > f(x₁), то перейти к шагу 5, иначе – к шагу 6.

Шаг 5. Положить x₀ = x₁ и f(x₀) = f(x₁). Проверить условие x₀ Î (a, b), т. е. a < x₀ < b. Если условие выполнено, перейти к шагу 3, иначе – к шагу 6.

Шаг 6. Проверка на окончание поиска. Если êD ê£ e, то вычисления завершить, положив x^* » x₀, f(x^* ) » f(x₀), иначе – перейти к шагу 7.

Шаг 7. Изменение направления и шага поиска. Положить x₀ = x₁ и f(x₀) = f(x₁), D = – . Перейти к шагу 3.

Пример 1.2.