Основы теории оптимизации (стр. 10 )

Перед вами поставили задачу: указать наилучший вариант консервной банки фиксированного объема V, имеющей обычную форму прямого кругового цилиндра. Получив такое задание, вы неизбежно должны спросить: "По какому признаку следует сравнивать банки между собой, какая банка считается наилучшей?" Иными словами, вы попросите указать цель оптимизации.
Рассмотрим два варианта этой задачи.
1. Наилучшая банка должна иметь наименьшую поверхность S. (На ее изготовление пойдет наименьшее количество жести.)
2. Наилучшая банка должна иметь наименьшую длину швов l. (Швы нужно сваривать, и мы хотим сделать эту работу минимальной.)
Для решения этой задачи запишем формулы для объема банки, площади ее поверхности и длины швов:

V=pr2h,  S=2pr2+2prh, l=4pr+h.  (7)

Объем банки задан, это устанавливает связь между радиусом r и высотой h. Выразим высоту через радиус: h=V/(pr2) и подставим полученное выражение в формулы для поверхности и длины швов. В результате получим

S(r)=2pr2+2V/r,  0 < r < ∞,  (8)

l(r)=4pr+V/(pr2),  0 < r < ∞.  (9)

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

S'(r)=4pr-2V/r2=2/r2(2pr3-V)  (10)

и исследуем ее знак. При 0<r<r1=3Ö V/(2p)  производная отрицательна и функция S(r) убывает, при  r1< r < ∞ производная положительна и функция S(r) возрастает. Следовательно, своего наименьшего значения эта функция достигает в точке r=r1 , в которой ее производная обращается в нуль. График функции S(r), иллюстрирующий проведенный анализ, показан на рис.3.

Рис. 3. График функции S(r)

Итак, радиус и высота банки, наилучшие с точки зрения условия минимальности S(r), определяются формулами

r1=3Ö V/(2p) ,  h1=2r1,  (11)

при этом 

 S(r1)=3 3Ö 2pV2 <=S(r).  (12)

Рассмотрим теперь задачу во второй постановке. Продифференцируем функцию l(r):

1'(r)=4p-2V/pr3=2/pr3(2p2r3-V).  (13)

Как  и  в  предыдущем  случае, при  0 < r < r2=3Ö V/(2p2 )  производная  отрицательна  и  функция  l(r)  убывает,  при r2< r < ∞ производная положительна и функция l(r) возрастает. Следовательно, своего наименьшего значения эта функция достигает в точке r=r2, в которой ее производная обращается в нуль. График функции показан па рис. 4.

Рис. 4. График функции 1(r)

Итак, радиус и высота банки, наилучшие с точки зрения условия минимальности l(r), определяются формулами

r2=3Ö V/(2p2 ) ,  h=2pr2,  (14)

при этом

1(r2)=3 3Ö 4pV  <= 1(r).  (15)

Мы видим, что при разных критериях оптимизации получаются существенно разные ответы. В первом случае (11) высота "наилучшей" банки равна ее диаметру, во втором (14) она в p раз больше диаметра.

Свойства функции одной переменной

Напомним основные свойства функции одной переменной

Монотонность функции.

Функция f(x) является монотонной, если для любых x1 и x2 из области определения функции выполняется, таких, что x1≤x2  выполняется неравенство , если функция монотонно возрастающая  или , если функция монотонно убывающая.

  Унимодальность.

Функция f(x) является унимодальной на отрезке (a, b), если она монотонна по обе стороны от единственной на отрезке точки x*, то есть

или

Критерии оптимальности для функций одной переменной.

  Определение глобального минимума

Функция f(x), определённая на множестве S достигает глобального минимума в точке x** S, если f(x**)≤ f(x) для всех x S.

  Определение локального минимума.

Функция f(x), определённая на множестве S имеет локальный минимум в точке x* S, если существует такая ε-окрестность точки x*, что для всех x из этой ε - окрестности  f(x**)≤ f(x) .

  , ,

  Если функция f(x) не унимодальна, то наименьший из локальных минимумов будет глобальным (аналогично – наибольший из локальных максимумов будет глобальным максимумом).

Необходимые условия оптимальности

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

1. 

2.    (минимум)

или

 (максимум)

  Стационарной точкой называется x*, в которой выполняется .

Это точки максимума, минимума и перегиба.

  Достаточные условия оптимальности.

  Пусть в точке x* первые (n-1) производных функции обращаются в ноль, а (n) производная отлична от ноля, тогда если n- нечётное, то x* - точка перегиба. Если n - чётное, то это точка оптимума. При этом, если n-я производная положительная, то точка локального минимума, отрицательна – точка локального максимума.

  Алгоритм:

1.  Найти 1-ю производную и станционарные точки.

2.  Найти следующую производную, не равную нулю.

3.  Анализировать найденную производную, как указано выше.

  Методы одномерной оптимизации можно разделить на:

·  методы исключения интервалов;

· методы точечного оценивания (полиномиальной аппроксимации);

· методы с использованием производных.

Методы интервалов

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

  Правила исключения интервалов.

Пусть f(x) унимодальна на интервале (a, b) и достигает минимума в точке x*. Рассмотрим точки x1 и x2 такие, что если , то точка x* принадлежит интервалу (x1, b), а интервал (a, x2) исключается.

Если , то исключаются оба интервала (a, x2) и (x1, b), а точка оптимума находится принадлежит интервалу (x1, x2).

Достоинства метода.

·  единственное ограничение на функцию – её унимодальность;

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

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

1.  Этап установления границ интервалов.

2.  Этап уменьшения интервалов.

Рассмотрим эти этапы.

  Этап установления границ интервалов.

1. Выбирается исходная точка 2.  С помощью эвристических приёмов строятся границы интервала.