Контрольные вопросы

1. Какая типовая задача оптимизации положена в основу задачи об изготовлении стержней?

2. К какому классу задач относится задача об изготовлении стержней и почему?

3. С помощью какой модели решаются задачи этого класса?

4. Что является исходными переменными математической модели задачи об изготовлении стержней?

5. Какой вид имеет математическая постановка данной задачи?

6. Какая система ограничений типа неравенств формирует множество допустимых альтернатив решения задачи?

Практическое задание № 7. Определение границ интервала поиска оптимума одномерной функции

Задание.

1. Определить знак начального шага (D).

1. Определить интервал поиска минимума функции по заданным исходным данным (табл. 7.1).

Таблица 7.1

Вариант	Вид функции	х0	|D|
0	3x·(x-1)	10	5
1	x^2+5	22	1
2	x^2+2x+1	-20	2
3	(1-x)^4	25	3
4	(x^2+1)/x	-20	4
5	3x·(x-1)	10	5
6	x^2+5	-20	2
7	x^2+2x+1	25	3
8	(1-x)^4	-20	4
9	(x^2+1)/x	10	1

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

Работа рассчитана на 2 аудиторных часа.

Элементы теории.

Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции сравнение значений f(х₍₁₎) и f(x₍₂₎) в двух различных точках интервала поиска позволяет определить в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют.

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

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

В процессе применения одномерных методов поиска оптимума функции можно выделить два этапа:

1. Установления границ интервала;

1. Уменьшения интервала.

Пусть функция f(х) унимодальна на замкнутом интервале a £ x £ b, а ее минимум достигается в точке х* (рис. 7.1).

Рис. 7.1

Рассмотрим точки х₍₁₎ и х₍₂₎, для которых а < х₍₁₎ < х₍₂₎ < b.

1. Если f(x₍₁₎) > f(x₍₂₎), то x*Î (x₁, b);

1. Если f(x₁) < f(x₂), то x*Î (a, x₂);

2. Если f(x₁) = f(x₂), то x*Î (х₁, x₂).

Поиск граничных точек проводится с помощью эвристических методов поиска. Одним из таких методов является метод, предложенный Свенном. Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума (k+1). Пробная точка определяется по рекуррентной формуле:

x_(k+1)= x_(k)+2^k·D , k=0,1,2...

где D - подбираемая величина шага.

Знак  подбирается путем сравнения значений f(x₍₀₎), f(x₍₀₎+) и f(x₍₀₎ – ).

Если f(x₍₀₎–)  f(x₍₀₎)  f(x₍₀₎+)то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х₍₀₎ и величина  выбирается положительной.

Если f(x₍₀₎–)  f(x₍₀₎)  f(x₍₀₎+), то  выбирается отрицательной.

Если f(x₍₀₎–)  f(x₍₀₎)  f(x₍₀₎+), то точка минимума лежит между x₍₀₎ –  и x₍₀₎+и поиск граничных точек завершен.

Алгоритм метода Свенна.

Шаг 1. Выбрать произвольную начальную точку х₍₀₎ и D – начальный положительный шаг (подбираемая величина).

Шаг 2. Вычислить f(x₍₀₎), f(x₍₀₎+ D)

Шаг 3. Сравнить f(x⁽⁰⁾), f(x⁽⁰⁾+ D):

а) если f(x₍₀₎) > f(x₍₀₎+ D) то, согласно предположению об унимодальности функции, точка минимума должна лежать правее, чем точка х₍₀₎. Положить а = х₍₀₎, х₍₁₎ = х₍₀₎ + D, f(x₍₁₎) = f(x₍₀₎+ D), k = 2 и перейти на шаг 5.

б) если f(x₍₀₎) ≤ f(x₍₀₎+ D), то вычислить f(x₍₀₎- D).

Шаг 4. Сравнить f(x₍₀₎ - D), f(x₍₀₎):

а) если f(x₍₀₎ - D) ≥ f(x₍₀₎), то точка минимума лежит между точками x₍₀₎ - D и x₍₀₎ + D, которые и образуют границы начального отрезка локализации минимума. Положить а = х₍₀₎ - D, b = x₍₀₎ + D и завершить поиск.

б) если f(x₍₀₎ - D) < f(x₍₀₎) то, согласно предположению об унимодальности функции, точка минимума должна лежать левее, чем точка х₍₀₎.

Положить b = x₍₀₎, x₍₁₎ = x₍₀₎ - D, f(x₍₁₎) = f(x₍₀₎ - D), D = - D, k=2 и перейти на шаг 5.

Шаг 5. Вычислить х_(k) = х₍₀₎ + 2_(k^-1₎· D, f(x_(k))..

Шаг 6. Сравнить f(x_(k)), f(x_(k-1)):

а) если f(x_(k-1)) ≤ f(x_(k)), то

при D > 0 положить b = x_(k),

при D < 0 положить а = x_(k)

и завершить поиск.

б) если f(x_(k-1)) > f(x_(k)), то

при D > 0 положить а = x_(k-1)

при D < 0 положить b = x_(k-1⁾,

положить k = k+1 и перейти на шаг 5.

Выполнение работы в среде MS EXCEL

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

Определение знака D.

Для этого необходимо подсчитать значения функции в точках х₍₀₎, х₍₀₎ + |D|, х₍₀₎ ‑ |D|, затем сравнить эти значения. Для сравнения значений функции и выбора в зависимости от этого знака D необходимо использовать логическую функцию MS EXCEL ЕСЛИ(). Аргумент этой функции имеет следующую размерность: ЕСЛИ (логическое выражение; значение, если истина; значение, если ложь). Для записи условий сравнения значений функции в этих точках используется также логическая функция И(), имеющая размерность И (логическое выражение 1; логическое выражение 2). Данная функция возвращает значение ИСТИНА, если хотя бы одно логическое выражение ИСТИНА, или ЛОЖЬ, если оба логических выражения ЛОЖЬ. Любая функция EXCEL может быть использована в качестве аргумента другой функции. В этом случае она называется вложенной. В MS EXCEL может быть использовано до 9 уровней вложения функций.

Для задачи функция должна быть записана таким образом:

=ЕСЛИ(И(f(х₍₀₎) <= f(х₍₀₎ -|D|);f(х₍₀₎) >= f(х₍₀₎ +|D|));D;

(ЕСЛИ(И(f(х₍₀₎)>=f(х₍₀₎ -|D|);f(х₍₀₎)<=f(х₍₀₎ +|D|));‑D;

«Поиск границ завершен»)).

Данная функция возвращает значение D или ‑ D в зависимости от значений функции в точках х₍₀₎, х₍₀₎ +|D|, х₍₀₎ ‑ |D|, либо признает точки х₍₀₎ +|D|, х₍₀₎ ‑ |D| границами интервала. В последнем случае, кроме того, что границы интервала найдены, необходимо вывести их в виде а = х₍₀₎ ‑ |D|, b= х₍₀₎ +|D|. Для этого необходимо составить новую функцию, которая не возвращает ничего, если

f(х₍₀₎ ‑ |D|) >= f(х₍₀₎) >= f(х₍₀₎ +|D|, f(х₍₀₎ -|D|) <= f(х₍₀₎) <= f(х₍₀₎ +|D|,

и возвращает в одной ячейке значение «а=», в смежной с ней – значение х₍₀₎ - |D|, еще в одной ячейке – «b=» и в смежной с ней ‑ х₍₀₎ + |D|, если

f(х₍₀₎ -|D|) >= f(х₍₀₎) <= f(х₍₀₎ +|D|.

Данная функция составляется аналогично предыдущей с использованием функций ЕСЛИ() и И().

Таким образом, если границы интервала не найдены при выполнении I этапа работы, определился, как минимум, знак D. Теперь можно приступить к определению границ интервала.

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

Вывести на экран результаты сравнения значений функции в пробных точках. Предлагается выводить эти результаты в двух графах. В левой графе выводится текст «x>» или «x<» в зависимости от значения функции в пробной точке и знака D, а в правой графе выводятся значение х в пробной точке. Если f(x_(k+1)) < f(x_(k)), то выводится «x>», если f(x_(k+1)) > f(x_(k)) – «x<» для D положительной. Для D отрицательной наоборот – «x<», если f(x_(k+1)) < f(x_(k)) и «x>», если f(x_(k+1)) > f(x_(k)). Для этого в левой графе составляется следующее выражение: =ЕСЛИ (f(x_(k+1)) < f(x_(k));ЕСЛИ(D > 0; «x>»; «x<»);ЕСЛИ(D > 0; «x<»; «x>»)). Для копирования выражения во все ячейки левой графы следует не забыть присвоить ячейке, содержащей D, абсолютный адрес.

Для вывода необходимых значений х в правой графе также составляются логические функции. Границами интервала поиска будут значения x, соответствующие последнему «x>» – а, и первому «x<» – b для D > 0, и наоборот, последнему «x<» – а и первому «x>» – b для D<0.

Пример 7. Определение интервала поиска минимума функции.

Исходные данные
f(x)	х(0)	D
(100-x)^2	30	5

Определение знака D

х(0) -D	25	f(х(0) - D)	5625	D=5
х(0)	30	f(х(0))	4900
х(0) +D	35	f(х(0)+ D)	4225

x	Индекс х	f(x)	Границы интервала
30	0	4900
35	1	4225	x>30
45	2	3025	x>35
65	3	1225	x>45
105	4	25	x>65
185	5	7225	x<185
345	6	60025	x<345

Выводы: для D = 5 границами интервала поиска минимума функции y = (100 - x)² являются 65 < x < 185.