Решение задачи оптимизации

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ

2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ НА ОПТИМИЗАЦИЮ

2.1 Численные методы решения задач одномерной оптимизации

2.2 Методы безусловной минимизации функций многих переменных

2.2.1 Многомерный поиск без использования производных

2.2.2 Многомерный поиск, использующий производные

2.2.3 Методы, использующие сопряженные направления

3. РАЗРАБОТКА ФАКУЛЬТАТИВНОГО УРОКА НА ТЕМУ «ПРИМЕНЕНИЕ ПРОИЗВОДНОЙ В РЕШЕНИИ ЗАДАЧ НА ОПТИМИЗАЦИЮ»

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. К примеру, Поляк под оптимизацией понимает «скорее стремление к совершенству, которое, возможно, и не будет достигнуто». [7, c. 90]

Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла. [5, c. 94]

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

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

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

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

Цель данной работы - рассмотреть возможности применения производной при решении задач на оптимизацию в школьном курсе математики.

В работе поставлены следующие задачи:

· Раскрыть формулировку математической задачи оптимизации;

· Привести алгоритмы методов оптимизации: одномерной оптимизации; безусловной оптимизации функцией многих переменных,

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

1. ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ

В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом: минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Под минимизацией (максимизацией) функции n переменных f(x)=f(x1, ... ,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).

При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f(x) > min (max),

x принадлежит U,

где f(x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные.[10, c. 80]

2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ НА ОПТИМИЗАЦИЮ

2.1 Численные методы решения задач одномерной оптимизации

Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси:

f(x) > min ,

x принадлежит [a, b].

Максимизация целевой функции эквивалента минимизации ( f(x) -> max ) эквивалентна минимизации противоположной величины ( -f(x) -> min ), поэтому, не умаляя общности можно рассматривать только задачи минимизации.

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

Для решения задачи минимизации функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации. [10, c. 81]

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b].

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

Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.

Разобьем отрезок [a,b] на n равных частей точками деления:

xi=a+i(b-a)/n, i=0,...n

Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величины Eps=(b-a)/n. [7,c 91]

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

Можно усовершенствовать метод перебора с целью уменьшения количества значений F(x), которые необходимо находить в процессе минимизации. Во-превых, если оказывается, что F(xi)<= F(x[i+1]), то отпадает необходимость вычислять F(x) в точках x[i+2], x[i+3] и т.д.. Во-вторых, разумно было бы сначала определить отрезок, содержащий оптимальную точку, грубо, т.е. найти точку xm с небольшой точностью, а затем искать ее на этом отрезке с меньшим шагом дискретизации, повышая точность. Эти возможности улучшения и реализованы в методе поразрядного поиска. В этом методе перебор точек отрезка происходит сначала с шагом sh=x[i+1]-xi > eps до тех пор, пока не выполнится условие F(xi) < F(x[i+1]) или пока очередная из точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения F(x) снова не перестанут уменьшаться или очередная точка не совпадет с другим концом отрезка и т.д. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг дискретизации не превосходит eps [6, c. 45]

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

Шаг1. Выбрать начальный шаг sh=(b-a)/4. Положить x0=a. Вычислить F(x0).

Шаг2. Положить x1=x0+sh. Вычислить F(x1).

Шаг3. Сравнить F(x0) и F(x1). Если F(x0)>F(x1), то перейти к шагу 4, иначе -- к шагу 5.

Шаг4. Положить x0=x1 и F(x0)=F(x1). Проверить условие принадлежности x0 интервалу [a,b]. Если a < x0 < b, то перейти к шагу 2, иначе -- к шагу 5.

Шаг5. Проверка на окончание поиска: если |sh| <= eps, то вычисления завершить, полагая xm=x0, Fm=F(x0), иначе -- перейти к шагу 6.

Шаг6. Изменить направление поиска: положить x0=x1, F(x0)=F(x1), sh=-sh/4. Перейти к шагу 2.

Метод деления пополам

Рассмотрим функцию F, которую требуется минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции , которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии eps>0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой к теоретическому значению (b1-a1)/2, и в то же время такое, чтобы значение функции в этих двух точках были различимы.

Алгоритм дихотомического поиска

Алгоритм дихотомического метода для минимизации строго квазивыпуклой фунции на интервале [a1,b1].

Начальный этап. Выбрать константу различимости 2еps > 0 и допустимую конечную длину интервала неопределенности l > 0. Пусть [a1,b1] - начальный интервал неопределенности. Положить k=1 и перейти к основному этапу.

Основной этап. Шаг 1. Если bk-ak < l, то остановиться; точка минимума принадлежит интервалу [ak,bk]. В противном случае вычислить pk=(ak+bk)/2-eps qk=(ak+bk)/2+eps и перейти к шагу 2.

Шаг2. Если F(pk) < F(qk), положить a[k+1]=ak и b[k+1]=qk. В противном случае положить a[k+1]=pk и b[k+1]=bk. Заменить k на k+1 и перейти к шагу 1.

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

Сравнение различных процедур линейного поиска естественно производить в соответствии со следующим коэффициентом сжатия (длина интервала неопределенности после k выполненных наблюдений)/(длина интервала неопределенности до выполнения наблюдений).

Очевидно, что более эффективные схемы соответствуют меньшим значениям коэффициента сжатия. В дихотомическом поиске значение коэффициента приблизительно равно (0.5)^(k/2). Метод золотого сечения является более эффективным, для него значение коэффициента сжатия равно (0.618)^(k-1).

Рассмотрим такое симметричное расположение точек x1 и x2 на отрезке [a,b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет, кроме первой, ограничиться определением только одного значения f(x), так как другое значение уже найдено на одной из предыдущих итераций. Для определения точек x1 и х2 рассмотрим сначала отрезок [0,1] и для определенности положим, что при уменьшении исключается правая часть этого отрезка. Пусть х2=q, тогда симметрично расположенная точка x1=1-q. Пробная точка х1 отрезка [0,1] перейдет в пробную точку х1'=1-q нового отрезка [1,q]. Чтобы точки x2=q и x2'=1-q делили отрезоки [0,1] и [0,q] в одном и том же отношении, должно выполняться равенство

1/q = q/(1-q) или q^2 = 1-q

откуда находим положительное значение q = 0.61803...

Таким образом для произвольного отрезка [a,b] выражения для пробных точек примут вид:

x1=a+(1-q)(b-a) x2=a+q*(b-a)

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

Алгоритм метода золотого сечения для минимизации строго квазивыпуклой фунции на интервале [a1,b1].

Начальный этап. Выбрать допустимую конечную длину интервала неопределенности l>0. Пусть [a1,b1] - начальный интервал неопределенности. Положить p1=a1+(1-0.618)(b1-a1) и q1=a1+0.618(b1-a1). Вычислить F(p1) и F(q1), положить k=1 и перейти к основному этапу.

Основной этап. Шаг 1. Если bk-ak < l, то остановиться; точка минимума принадлежит интервалу [ak,bk]. В противном если F(pk)>F(qk), то перейти к шагу 2, а если F(pk)<=F(qk),то к шагу 3.

Шаг2. Положить a[k+1]=pk, b[k+1]=bk, p[k+1]=qk, q[k+1]=a[k+1]+0.618(b[k+1]-a[k+1]). Вычислить F(q[k+1]) и перейти к шагу 4.

Шаг3. Положить a[k+1]=ak, b[k+1]=qk,q[k+1]=pk, p[k+1]=a[k+1]+(1-0.618)(b[k+1]-a[k+1]). Вычислить F(p[k+1]) и перейти к шагу 4. Шаг4. Заменить k на k+1 и перейти к шагу 1.

2.2 Методы безусловной минимизации функций многих переменных

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

2.2.1 Многомерный поиск без использования производных

Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. Важно отметить, что для применения этих методов не требуется не только дифференцируемости целевой функции, но даже аналитического задания. Нужно лишь иметь возможность вычислять или измерять значения f в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации. В основном все описанные методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f(x+lym*d) при условии, что lym принадлежит L, где L обычно задается в форме L=E1, L={lym: lym >= 0} или L={l: a<=lym<=b}. Будем предполагать, что точка минимума lym* существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть не ограниченным или оптимальное значение функции конечно, но не достигается ни при каком lym.

Метод циклического покоординатного спуска.

В этом методе в качестве направлений поиска используются координатные векторы. Метод осуществляет поиск вдоль направлений d1, ..., dn, где dj - вектор, все компоненты которого, за исключением j-ого, равны нулю. Таким образом, при поиске по направлению dj меняется только переменная xj, в то время как все остальные переменные остаются зафиксированными.

Алгоритм циклического покоординатного спуска

Начальный этап. Выбрать eps >0, которое будет использоваться для остановки алгоритма, и взять в качестве d1, ..., dn координатные направления. Выбрать начальную точку x1, положить y1 = x1, k=j=1 и перейти к основному этапу.

Основной этап. Шаг 1. Положить lymj равным оптимальному решению задачи минимизации f(yj+lym*dj) при условии, что lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то перейти к шагу 2.

Шаг 2. Положить x[k+1] = y[n+1]. Если || x[k+1] - xk || < eps, то остановиться. В противном случае положить y1= x[k+1], j=1, заменить k на k+1 и перейти к шагу 1.

Метод Хука и Дживса

Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке.

1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.

При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2 . Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.

Алгоритм Хука и Дживса с использованием одномерной минимизации.

Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1,..., dn и направлений поиска по образцу.

Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.

Основной этап. Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то положить x[k+1] = y[n+1]. Если ||x[k+1] - xk|| < eps , то остановиться; в противном случае перейти к шагу 2.

Шаг 2. Положить d = x[k+1] - xk и найти lym - оптимальное решение задачи минимизации f(x[k+1]+lym*d) при условии lym принадлежит E1. Положить y1= x[k+1]+lym*d, j=1, заменить k на k+1 и перейти к шагу 1.

Метод Розенброка.

Рассмотрим вариант метода с применением одномерной минимизации. На каждой итерации процедура осуществляет итеративный поиск вдоль n линейно независимых и ортогональный направлений. Когда получена новая точка в конце итерации, строится новое множество ортогональных векторов. На рисунке новые направления обозначены через q1 и q2.

Построение новых направлений поиска в методе Розенброка.

Построение направлений поиска

Пусть d1,..., dn - линейно независимые векторы, по норме равные единицы. Предложим, что эти векторы взаимно ортогональны, т. е. (di*dj) = 0 для i != j. Начиная из текущей точки xk, целевая функция последовательно минимизируется вдоль каждого из направлений, в результате чего получается точка x[k+1]. В частности, x[k+1]- xk = Sum(lymj*dj), где lymj - длина шага по направлению dj. Новый набор направлений q1,..., qn строится с помощью процедуры Грамма-Шмидта следующим образом:

dj, если lym j = 0,

aj = {

Sum(lymi*di), i=[j,n], если lymj != 0,

aj, при j = 1,

bj = {

aj - Sum (aj*qi)*qi, i=[1,j-1], при j >= 2,

qj = bj /|| bj ||.

Новые направления построенные таким образом являются линейно независимыми и ортогональными.

Алгоритм метода Розенброка с минимизацией по направлению

Начальный этап. Пусть eps > 0 - скаляр, используемый в критерии остановки. Выбрать в качестве d1,..., dn координатные направления, начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.

Основной этап. Шаг 1. Найти lymj - оптимальное решение задачи минимизации f(yj+lymj*dj) при условии lym принадлежит E1 и положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. В противном случае перейти к шагу 2.

Шаг 2. Положить x[k+1]= y[n+1]. Если ||x[k+1] - xk|| < eps, то остановиться. В противном случае положить y1= x[k+1], заменить k на k+1 положить j=1 и перейти к шагу 3.

Шаг 3. Построить новое множество линейно независимых и взаимно ортогональных направлений в соответствии с процедурой Грамма-Шмидта. Обозначить новые направления d1,..., dn и вернуться к шагу 1.

Минимизация по правильному симплексу.

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

В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, а в E3 - правильного тетраэдра. Если x0 - одна из вершин правильного симплекса в En, то координаты остальных n вершин x1,..., xn можно найти, например, по формулам:

xj0 + d1 , i != j,

xji ={ .....................................................................(1)

xj0 + d2 , i=j,

где d1 = a(sqrt(n+1) - 1) / n*sqrt(2), d2 = a(sqrt(n+1) + n - 1) / n*sqrt(2), a - длина ребра.

Вершину x0 симплекса, построенного по формулам (1), будем называть базовой. В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины, например, xk симметрично относительно центра тяжести xc остальных вершин симплекса. Новая и старая вершины y и xk связаны соотношением: (y+ xk)/2 = xс, где xc = (1/n)Sum(xi) для всех i!=k. В результате получаем новый симплекс с тем же ребром и вершинами y=2xс-xk, xi, i=0,...,n, i!=k. Таким образом происходит перемещение симплекса в пространстве. На рисисунке представлена иллюстрация этого свойства симплекса для двумерной области.

Построение нового симплекса в Е2 отражением точки х2.

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

Алгоритм минимизации по правильному симплексу

Начальный этап. Выбрать параметр точности eps, базовую точку x0, ребро a и построить начальный симплекс по формулам (1). Вычислить f(x0).

Основной этап. Шаг 1. Вычислить значения f(x) в вершинах симплекса x1,..., xn.

Шаг 2. Упорядочить вершины симплекса x0,..., xn так, чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).

Шаг 3. Проверить условие (1/n)Sum[f(xi)-f(x0)]^2 < eps^2, i=[1,n].

Это одно из возможных условий останова. При его выполнении "дисперсия" значений f(x) в вершинах симплекса становится меньше e2, что, как правило, соответствует либо малому ребру a симплекса, либо попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.

Если это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном случае перейти к шагу 4.

Шаг 4. Найти xс и выполнить отражение вершины xn : y=2*xс- xn. Если f(y)<f(xn), то положить xn=y и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершиной x0. Остальные n вершин симплеска найти по формуле xi=( xi+ x0)/2, i=1,...,n. Перейти к шагу 1.

Поиск точки минимума по деформируемому симплексу

Алгоритм минимизации по правильному симплексу можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины y вместо вершины xn , соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках:

z1= xc - a( xc - xn), 0<a<1;

z2 = xc + a( xc - xn), 0<a<1; ............................................................(2)

z3 = xc + b( xc - xn), b приближенно равно 1;

z4 = xc + g( xc - xn), g<1.

Геометрическая иллюстрация этих процедур для двумерного пространства приведена на рисунке.

Пробные точки z1, z2, z3, z4 для перехода к новому симплексу

Новые симплексы полученные в результате процедуры сжатия (a,b); отражения (c); растяжения (d)

Так как величина a принадлежит интервалу (0;1), то выбор точек z1 и z2 соответствует сжатию симплекса; b приближенно равно 1, поэтому выбор точки z3 соответствует отражению, а g>1 и выбор точки z4 приводит к растяжению симплекса.

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

На практике хорошо зарекомендовал себя следующий набор параметров a=1/2, b=1, g=2.

Алгоритм метода поиска точки минимума функции по деформируемому симплексу

Начальный этап. Выбрать параметр точности eps, параметры a, b и g, базовую точку x0 , параметр a и построить начальный симплекс. Вычислить значение функции f(x0).

Основной этап. Шаг 1. Вычислить значения функции в вершинах симплекса x1,..., xn.

Шаг 2. Упорядочить вершины симплекса x0,..., xn так, чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).

Шаг 3. Проверить условие (1/n)Sum[f(xi)-f(x0)]^2 < e^2, i=[1,n].

Это одно из возможных условий останова. При его выполнении "дисперсия" значений f(x) в вершинах симплекса становится меньше e2, что, как правило, соответствует либо малому ребру a симплекса, либо попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.

Если это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном случае перейти к шагу 4.

Шаг 4. Найти xс и пробные точки zk , k=1,...,4 по формулам (2). Найти f(z*)=minf(zk). Если f(z*)<f(xn), то положить xn = z* и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Уменьшить симплекс, полагая xi=( xi+ x0)/2, i=1,...,n перейти к шагу 1.

2.2.2 Многомерный поиск, использующий производные

Пусть функция f(x) деференцируема в Еn . В этом разделе рассматривается итерационная процедура минимизации вида:

xk = x[k-1] + lym[k]*dk, k=1,... ,

где направление убывания dk оперделяется тем или иным способом с учетом информации о частных производных функции f(x), а величина шага lym[k] >0 такова, что

f(xk) < f(xk-1), k=1,2,....

Так как функция предполагается дифференцируемой, то в качестве критерия останова в случае бесконечной итерационной последовательности { xk }, как правило, выбирают условие ||grad(f(xk))||<eps, хотя, разумеется, могут быть использованы и другие критерии.

Метод наискорейшего спуска является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Вектор d называется направлением спуска для функции f в точке x, если существует такое d > 0, что f(x+lym*d)<f(x) для всех lym принадлежащих интервалу (0, d). В частности, если

f(x+ld)-f(x)

lim -------------------< 0, при lym->0+

lym

то d - направление спуска. В методе наискорейшего спуска осуществляется движение вдоль направления d, для которого ||d|| = 1 и которое минимизирует приведенный выше предел. Если f дифференцируема в точке x и grad(f(x))!=0, то -grad(f(x))/||grad(f(x))|| является направлением наискорейшего спуска. В связи с этим метод наискорейшего спуска иногода называют градиентным методом.

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

Метод наискорейшего спуска является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Вектор d называется направлением спуска для функции f в точке x, если существует такое d > 0, что f(x+lym*d)<f(x) для всех lym принадлежащих интервалу (0, d). В частности, если

f(x+ld)-f(x)

lim -------------------< 0, при lym->0+

lym

то d - направление спуска. В методе наискорейшего спуска осуществляется движение вдоль направления d, для которого ||d|| = 1 и которое минимизирует приведенный выше предел. Если f дифференцируема в точке x и grad(f(x))!=0, то -grad(f(x))/||grad(f(x))|| является направлением наискорейшего спуска. В связи с этим метод наискорейшего спуска иногода называют градиентным методом. [9, c. 70]

Алгоритм метода наискорейшего спуска

При заданной точке x алгоритм наискорейшего спуска заключается в реализации линейного поиска вдоль направления -grad(f(x))/||grad(f(x))|| или, что то же самое, вдоль направления -grad(f(x)).

Начальный этап. Пусть eps > 0 - константа остановки. Выбрать начальную точку x1, положить k=1 и перейти к основному этапу.

Основной этап. Если ||grad(f(x))|| < eps , то остановиться; в противном случае положить dk = -grad(f(x)) и найти lym[k] - оптимальное решение задачи минимизации f(xk + lym*dk) при lym >= 0. Положить x[k+1]=xk+lym[k]*dk, заменить k на k+1 и повторить основной этап.

2.2.3 Методы, использующие сопряженные направления

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

Определение. Пусть H - симметрическая матрица порядка nxn. Векторы d1,..., dk называются H-сопряженными, или просто сопряженными, если они линейно независимы и di(t)Hdj = 0 при i != j, где di(t) - вектор строка.

Минимум квадратичной функции может быть найден не более чем за n шагов при условии, что поиск ведется вдоль сопряженных относительно матрицы Гессе направлений. Поскольку произвольная функция может быть достаточно хорошо представлена в окрестности оптимальной точки ее квадратичной аппроксимацией, понятие сопряженности становится очень удобным для оптимизации как квадратичных, так и неквадратичных функций^. [9,c . 77]

Метод Дэвидона - Флетчера - Пауэлла

Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка nxn, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.[2,c . 100]

Алгорим метода Дэвидона - Флетчера - Пауэлла

Начальный этап. Пусть eps >0 - константа для остановки. Выбрать точку x1 и начальную симметрическую положительно определенную матрицу D1 . Положить y1 = x1, k=j=1 и перейти к основному этапу.

Основной этап. Шаг 1. Если ||grad(f(x))|| < eps , то остановиться; в противном случае положить dj = -Dj*grad(f(yj)) и взять в качестве lymj - оптимальное решение задачи минимизации f(yj + lym*dj) при lym >= 0. Положить y[j+1] = yj + lymj*dj. Если j < n, то перейти к шагу 2. Если j=n, то положить y1=x[k+1]=y[n+1], заменить k на k+1, положить j=1 и повторить шаг 1 [1,c . 140]

Шаг 2. Построить Dj+1 следующим образом:

pjpj(t) ...........Djqjqj(t)Dj

Dj+1 = Dj +...------------.... -...-------------- ,

pj(t)qj............. qj(t)Djqj

где

pj = lymj*dj,

qj = grad(f(y[j+1])) - grad(f(yj)).

Заменить j на j+1 и перети к шагу 1.

3. РАЗРАБОТКА ФАКУЛЬТАТИВНОГО УРОКА НА ТЕМУ

«ПРИМЕНЕНИЕ ПРОИЗВОДНОЙ В РЕШЕНИИ ЗАДАЧ НА

ОПТИМИЗАЦИЮ»

В данном разделе разработаем модель факультативного урока на тему: «Применение производной в решении задач по математике». В качестве основного средства обучения выступает учебное Сканави М.И. [9]

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

Урок состоит из

Ход урока.

1. Проверка домашнего задания:

Ответы:

15.176 - f(x)=x²+(18-x)²; [0 ; 18]; (9 ; 9)

15.177 - f(x)=x*2x(180-3x)= =360x²-6x³ (0 ; 180); 40 : 60 : 80

15.179 - x - длина, 294/x - ширина,

f(x)=2x+3, 14Ч21

№ 583. Точки, в которых могут находиться наибольшее и наименьшее значения функции y=x³-3x²-105x+25, определяютсяурав-нением 3x²-6x-105=0 и границами отрезка, т.е. x₁=-6, x₂=-5, x₃=1

(решение x=7 в отрезок не входит). у₁=306, y₂=325, y₃=-82.

2. Устно:

а) Дан график функции y=f(x). Какие утверждения верны?

1. а, с - критические точки (+); y

2. а, с - точки экстремума(+); _n

3. на интервале (k, t) функция _l

дифференцируема (-);

4. [a, c] - промежуток убывания (+); k ^{a 0 c t} x

5. l - точка максимума(-);

6. max f(x)=n(+);

^[k,t]

7. x_max=a(+).

б) На чертеже - график производной функции f(x).

1. Что можно сказать о дифференцируемости функции

2. Какие из заданных точек

(b, f(b)); (d, f(d)); (c, f(c)); (k, f(k))

являются критическими для f(x)?

3. Назвать промежутки возрастания и убывания для f(x).

3. Решение задач - подготовка к контрольной работе.

a) Исследовать функцию y=4x⁴-x³ и построить график.

1.Область определения - множество действительных чисел.

2.Точки пересечения с осями координат.

x³(4х-16/3)=0, х=0, х=4/3, (0;0); (4/3;0).

3.Промежутки монотонности.

y'=16х³ -16х²=0 , x₁=0, x₂=1

4. Минимум

x_min =1, y_min=-4/3.

5.Точки перегиба.

y”= 48x²-32x=0, следовательно, x₁=0, x₂=2/3

Знак y'' в точках x₁=0, x₂=2/3 меняется, следовательно, это точки перегиба (при этом только в т. 0 касательная параллельна оси x).

6. Строим на основании перечисленных свойств график функции (качественно):

y'=0 (касательная параллельна оси x) в точках x=0 и x=1;

т. (0,0) - точка перегиба;

т. (1,-4/3) - минимум;

т. (2/3, -0.79) - точка перегиба (отн. касательной);

y'<0 на интервалах (-?, 0),

(0,1);

y'>0 на интервале (1, ?).

б) Исследовать функцию y=.

1.Область определения - множество действительных чисел,

кроме x=1.

2.Точки пересечения с осями координат:

y=0 при x²-2x+2=0 - не выполняется ни при каких значениях x, следовательно, график с осью абсцисс не пересекается; пересечение с осью y (т.е. x=0) в точке (0, -2).

3.Критические точки и промежутки монотонности.

y'=, x₁=0, x₂=2; x₃=1

4. Экстремумы: минимум в точке x_min =2, y_min=2;

максимум в точке x_max=0, y_max=-1.

5. Асимптоты.

=±? x=1 - вертикальная асимптота;

=±? горизонтальных асимптот нет;

Ищем наклонные асимптоты в виде прямых y=kx+b:

=1 k=1

=-1 b=-1 прямая y=x-1 является асимптотой.

6. Строим на основании перечисленных свойств график

y

₁

^о1x

4. Решение задач на оптимизацию.

№ 15.180. [9]

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

Какова наибольшая вместимость полученной коробки?

Решение.

Пусть х дм - сторона вырезанного квадрата, тогда длина коробки

(8-2x) дм, высота - х дм.

V(х)=(8-2х)(5-2х)х на интервале (0;2,5).

V(х)=40х-26х²+4х³.

Приравниваем 0 производную

V'(x)=40-52x+12x²=0

Решения этого уравнения x₁=1, x₂=20/6, причём x₂ не входит в

рассматриваемый интервал.

На интервале (0, 1) V'(x)>0, на интервале (1, 0) V'(x)<0

Следовательно, функция объёма V(x) имеет в т. x=1 максимум и

max V(x) = V(1)=18 дм³.

Ответ: наибольший объём коробки 18 дм³.

№ 15.197. [9]

Боковое ребро правильной треугольной пирамиды имеет заданную длину и составляет с плоскостью основания угол б. При каком значении б объём пирамиды будет наибольшим?

Решение.

Объём правильной пирамиды V=, где h=a sinб,

S_ABC=0.5 AH*BC.

Ao=a cosб AH=3/2Ao=3/2 a cosб, BC=AC==

и, следовательно,

V(б)=a³cos²б sinб , б(0,90)

(границы интервала не включены, поскольку очевидно, что V(0)=V(90)=0)

Для нахождения наибольшего объёма исследуем функцию V(б) на максимум, для чего приравняем 0 производную:

V'(б)=0 =0- 2cosб sin²б +cos³б=0

cos²б-2sin²б=0(разделив на cos²б?0) 2tg²б=1

tgб =и б=arctg.

При этом производная V'(б)=K (1-2tg²б), K=const >0.

Таким образом, б=arctg- единственный максимум функции V(б)

на инервале и, следовательно, V(arctg) - наибольший объём.

Ответ: arctg.

5. Самостоятельная работа (2 варианта, в виде теста.)

6. Итоги урока.

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

На следующем уроке - контрольная работа.

7. Домашнее задание:

Решение задач из Сканави - 15.165, 15.168, 15.169, 15.188, 15.196. [9]

Методичка - 589, 593.

Повторить теорию.

Заключение

Таким образом, в работе рассмотрена возможность применения производной при решении задач на оптимизацию в школьном курсе математики.

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

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

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

По мнению автора, в процессе работы удалось достичь поставленных задач.

СПИСОК ЛИТЕРАТУРЫ

1. Банди Б. Методы оптимизации (вводный курс). - М.: Радио и связь,1988.

2. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1980.

3. Волкович В.Л. Волошин А.Ф. Об одной схеме метода последовательного анализа и отсеивания вариантов // Кибернетика. 1978. № 4. С. 98-105.

4. Дивеев А.И. К проблеме выбора варианта технической системы с монотонными параметрами // Проблемы машиностроения и надежности машин / РАН. 1996. № 4. С. 14--19.

5. Дивеев А.И., Северцев Н.А. Метод трансформации в схеме последовательного анализа и отсеивания вариантов // Труды международной конференции "Вопросы оптимизации вычислений (BOB-XXVII)". Киев, 6-8 окт., 1997 г. С. 94-97.

6. Зангвилл У. Нелинейное программирование. Единый подход. - М.: Сов. радио,1973.

7. Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.

8. Сеа Ж. Оптимизация. Теория и алгоритмы. - М.: Мир, 1973.

9. Северцев Н. А. Дивеев А. И. Оптимальный выбор варианта технического изделия // Проблемы машиностроения и надежности машин / РАН. 1995. № 5. С. 3--8.

10. Сканави М.И. Сборник задач по математике для поступающих в вузы. - М.: Издательство Оникс, 1994. - 324 с.

11. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, 1986.