Составить схему алгоритма, написать программу решения задачи оптимизации

Вопросы, подлежащие изучению

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

2. Методы оптимизации: метод перебора; метод дихотомии; метод золотого сечения.

3. Условия сходимости методов.

4. Оценка погрешности оптимизации.

5. Графическая иллюстрация процесса оптимизации.

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

Задание

1. Выбрать индивидуальное задание по номеру варианта из табл. 6.6-1 для решения задачи одномерной оптимизации:

· функцию f(x), минимум которой необходимо найти;

· метод оптимизации для ручного расчета - значение параметра p;

· метод оптимизации для расчета на ПК - значение параметра t.

2. Провести исследование индивидуального варианта задания:

· построить график функции ;

· выбрать начальный отрезок неопределенности (отрезок, содержащий точку минимума);

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

3. Провести «ручной расчет» трех итераций и определить длину отрезка, содержащего точку минимума, после трех итераций.

Составить схему алгоритма, написать программу решения задачи оптимизации

указанным в задании методом для «расчета на ПК» и провести контрольное тестирование программы, воспользовавшись исходными данными и результатами рассмотренного примера.

5. Решить задачу оптимизации с точностью E = 10^-4с помощь написанной программы («расчета на ПК»).

6. Вычислить число итераций, необходимых, чтобы локализовать точку минимума с

точностью E1 = 10^-4, расчет сравнить с результатом, полученным на ПК.

Решить задачу оптимизации с помощью математических пакетов.

6.6.3. Варианты задания

Таблица 6.6-1

№ вар.	f(x)	t	p
	– 2 (1 + x) e^–^x – 2 cos(x)
	(x – 1)
	10 sin(x³) cos(-x)
	x² cos(x + 3) – 4
	cos(x – 5) e²^x^{/ 3}
	– 4 sin(x) + x^{1 / 2}
	– 5 sin³(x) – cos³(x)
	– cos(2x + 1) ln(2 / x) + 3
	x sin(x + 1) – cos(x – 5)
	(1 + x²)^{1 / 2} + e^–^x
	– 8 sin(- x³) e^–^x
	5 e^–^x + 4 x + x³ / 3
	sin(x – 1) – x cos(x + 3)
	3 cos(x²) / ln(x + 5)
	sin(x²) + 1 / (2 – x)
	sin(e^x) – e^–^x + 1
	sin(x + 1) e^{2 /}^x
	– 5 x sin(x + 1) + 2 cos(x)
	1 + sin(4x) / ln(x)
	2 sin(4x) ln(– x) – 3
	x^{3 / 2} – 2 x sin(x)
	x sin(x) + cos(x) + 5
	e^–^x sin(2x)
	sin(2x) – 2 sin(x)
	sin(2x) – x
	cos(– 2x) e^–^x
	e^–^x sin(– 2x)
	e^–^x cos(– 2x)
	cos(x + 2) + cos(2x) + x
	cos(2x) + 2 sin(x)

В табл. 6.6-1 t – номер метода для вычисления минимума с точностью 10^-4
(п.6 задания), p – номер метода для вычисления трех итераций (п.3 задания). Значения параметров t и p соответствуют: 1 – методу дихотомии, 2 – методу золотого сечения.

Содержание отчета

1. Индивидуальное задание.

2. Результаты исследования индивидуального варианта задания:

· график функции ;

· начальный отрезок неопределенности;

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

3. Результаты «ручного просчета», представленные в табл. 6.6.2, и длина отрезка, содержащего точку минимума, после трех итераций.

Таблица 6.6-2

№ итерации	a	b	x₁	x₂	f(x₁)	f(x₂)

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

5. Результаты «расчета на ПК», представленные в табл. 6.6.3.

Таблица 6.6-3

№ итерации	a	b	x₁	x₂	f(x₁)	f(x₂)

6. Число итераций, необходимых для локализации точки минимума, и результат сравнения с «расчетами на ПК».

7. Результаты решения задачи оптимизации, полученные с помощью пакетов.

6.6.5. Пример выполнения контрольного задания

1. Задание для решения задачи одномерной оптимизации:

· функция, для которой необходимо найти минимум – ;

· методы решения задачи оптимизации для «ручного расчета» – золотого сечения и дихотомии;

· методы решения задачи оптимизации для «расчета на ПК» – золотого сечения и дихотомии.

2. Исследование задания:

· график функции :

· начальный отрезок неопределенности (отрезок, содержащий точку минимума) выберем по построенному графику - отрезок [2.5; 3.5] - начальный отрезок неопределенности;

· результат проверки выполнения аналитического условия унимодальности функции на выбранном отрезке:

;

при , так как sin(x) и cos(x) не

обращаются в нуль одновременно и .

Значения сведем в следующую таблицу:

х	2.5	2.6	2.7	2.8	2.9	3.0	3.1	3.2	3.3	3.4	3.5
f’(x)	-1.44	-1.34	-1.15	-0.94	-0.69	-0.42	-0.13	0.19	0.52	0.87	1.23

На отрезке [2.5; 3.5 ] функция монотонно возрастает, следовательно, функция

y=f(x) - унимодальная на этом отрезке.

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

Результаты «ручного расчета» и длина отрезка, содержащего точку

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

Схема алгоритма приведена на рис. 6.6.3-2 в [2]. Программу студенты должны составить самостоятельно.

Метод дихотомии

Одномерная оптимизация

1. Какое значение функции называют оптимальным?

2. В чем заключается задача одномерной оптимизации?

3. Какой минимум называют локальным?

4. Что такое глобальный минимум?

5. Каковы необходимые и достаточные условия экстремума функции?

6. Когда применяются численные методы одномерной оптимизации?

7. В чем их преимущества и недостатки по сравнению с аналитическими методами?

8. В чем суть методов одномерного поиска и при каких условиях они применяются?

9. Что означает понятие «унимодальная функция»?

10. В чем суть условия унимодальности?

11. Почему в методах одномерной оптимизации при переходе к следующей итерации часть отрезка можно отбросить?

12. Какое деление отрезка называют золотым сечением?

13. В чем состоит суть метода дихотомии?

14. В чем суть метода золотого сечения?

15. Влияет ли вид функции на скорость сходимости метода дихотомии?

16. Влияет ли вид функции на скорость сходимости метода золотого сечения?

17. В чем заключается основное достоинство метода золотого сечения?

18. Во сколько раз на очередной итерации уменьшается длина отрезка неопределенности в методе дихотомии?

19. Во сколько раз на очередной итерации уменьшается длина отрезка неопределенности в методе золотого сечения?

20. Как оценивается погрешность методов оптимизации?

21. Можно ли с использованием численных методов одномерной оптимизации найти максимум функции?