Лабораторная работа №12. Методы одномерного поиска для решения задач оптимизации

Цель работы:

• составить блок-схему и программу для определения экстремума функции методом сканирования;

• определить точки экстремума целевой функции с использованием составленной программы по методу сканирования и прикладных программ по методам “локализации экстремума” и “золотого сечения”;

• сопоставить эффективность используемых методов.

1. ОПИСАНИЕ МЕТОДИКИ РАСЧЕТОВ

Для всех методов постановка задачи следующая – определить положение экстремума (минимума) на интервале [А, В].

1.1. Метод сканирования

Алгоритм метода следующий. Интервал поиска [A,B] разбивается на N равных участков, каждый из которых равен шагу поиска h. Далее последовательно определяется значение целевой функции во всех точках разбиения, включая точки А и В, и запоминается минимальное (максимальное) значение целевой функции (рис. 12.1). Таким образом, экстремальное значение функции может быть найдено с точностью до величины шага поиска.

Рис. 12.1

1.2. Метод локализации экстремума

Интервал поиска [A, В] разбивается на 4 равные части и в точках разбиения и на границах интервала вычисляется значение целевой функции – в точках 0, 1, 2, 3 и 4 (рис. 12.2). Локализуется положение экстремума (минимума) на интервале в два раза меньшем [2; 4], чем предыдущий [0;4]. Полученный интервал снова делим на 4 равные части.

Рис. 12.2

Локализация экстремума продолжается до тех пор, пока не будет достигнута заданная точность. Блок-схема программы “OPTIMIZE. Метод локализации экстремума”, реализующая данный метод, приведена на рис. 12.3.

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

В основе этого метода лежит закон геометрического отношения или “золотого сечения” (рис. 12.4). Пусть дан отрезок а, который разделен на две неравные части b и c так, что выполняется отношение:

или a  c = b ² (12.1)

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

Поскольку с=а–b, то подставив выражение для с в (12.1) и введя новую переменную k= , после преобразований получим:

k² + k – 1 = 0 (12.2)

Решив (12.2), получим приближенное значение k ≈ 0,62.

Порядок поиска экстремума методом "золотого сечения" следующий. На исследуемом интервале определяются две точки x₁ и x₂:

x₁ = x_min + (1–k)  a,

x₂ = x_min + k  a,

где а – длина интервала [x_max; x_min]. В точках x₁ и x₂ рассчитывается целевая функция. По найденным значениям R(x₁) и R(x₂) с учетом R(x_min) и R(x_max)

Рис. 12.3. Блок-схема метода локализации экстремума

определяется подинтервал, в котором локализован экстремум. В данном случае это [x_min; x₂]. Далее внутри подинтервала [x_min; x₂] находится точка x₃:

x₃ = x_min + (1–k)  a,

где а – длина подинтервала [x_min; x₂].

Рис. 12.4

Далее вычисляется значение целевой функции R(x₃) и сравниваются значения R(x₂), R(x₁), R(x₃). Находится минимальное значение (в данном случае R(x₃) и процедура продолжается, определяется аналогично точка x₄ и т.д., пока не будет найден экстремум с заданной точностью. Блок-схема программы "OPTIMIZE. Метод золотого сечения", реализующая данный метод, приведена на рис. 12.5.

2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Работа выполняется в такой последовательности:

• составляют блок-схему и программу для определения экстремума (минимума) методом сканирования;

• выполняют расчеты на ЭВМ по составленной программе (метод сканирования) и прикладным программам “OPTIMIZE. Метод “локализации экстремума” и “OPTIMIZE. Метод “золотого сечения”;

• дается оценка сравнения эффективности методов.

3. ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ

В таблице 12.1 приведены целевые функции и область допустимых изменений исследуемых независимых переменных. Требуемая точность определения координат точки экстремума 0,001.

Таблица 12.1

№ варианта	Целевая функция R(x)	Диапазон изменения переменных
1	4,4х3 – 9,2х2 – 7,3х +10,97	0; 10
2	0,4х3 + 2,5х 2–14х +2	0; 10
3	0,2х4 – 1,5х3 – 4х + 25	0, 10

Рис. 12.5. Блок-схема метода “золотого сечения”

Продолжение таблицы 12.1

№ варианта	Целевая функция R(x)	Диапазон изменения переменных
4	0,5х4 – 8х2 + 2х +2	0; 10
5	0,2х4 – 0,7х3 – 6,5х + 8,2	0; 10
6	4х4 – 9х3 +2х2 – 8х +2	0, 10
7	3х3 – х2 – 13х – 660	0; 10
8	х3 – 0,39х2 –10,5х +11	0; 10
9	х3 – 1,473х2 –5,738х + 6,763	0, 10
10	0,8х4 + 0,35х2 –,8х + 0,8	0; 10
11	х3 – 16х2 +25х + 44	0; 10
12	х3 – 10х –760	0; 10
13	1,6х4 – 2,7х2 +11,3х –160,6	–10, 0
14	3х4 – 7х2 +13х – 65,3	–10, 0
15	х4 –2х2 + 9х – 16,8	–10, 0
16	2х4 – 5х2 +10х – 34,81	–10, 0
17	х4 – 5х2 +14х – 1200	–10, 0
18	0,1х3 +х2 – 4х –20	–10, 5
19	х4 – 2х2 +5х –3,2	–10, 0
20	4,2х3 –9,1х2 –7,2х+12	– 3, 9

4. ОФОРМЛЕНИЕ ПРОТОКОЛА

В протоколе по лабораторной работе описываются результаты расчетов, выполненных на ЭВМ. Приводится блок-схема программы по методу сканирования, листинг программы и результаты расчетов.

5. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие существуют методы одномерного поиска?

2. Суть методов одномерного поиска.

3. Метод сканирования. Алгоритм расчета.

4. Блок-схема метода сканирования.

5. Метод локализации экстремума. Алгоритм расчета.

6. Блок-схема метода локализации экстремума.

7. Метод "золотого сечения". Алгоритм расчета.

8. Блок-схема метода "золотого сечения".

9. Сравнительная характеристика методов одномерного поиска.