Методы оптимизации в ТКС

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Реферат

Методы оптимизации в ТКС

Вступление

аппроксимация золотой сечение касательная

Задачи линейного программирования были первыми подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции - симплекс-метод, ставший основным при решении задач линейного программирования.

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

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

1. Методы поиска точек экстремума функции на отрезке

Пусть дана функция f (x), для которой на заданном отрезке [a; b] нужно найти максимальное значение или минимальное значение и установить, в какой точке x^* это экстремальное значение достигается. Так как задача нахождения максимума функции f (x), эквивалентна задаче нахождения минимума функции f _(x) = - f (x), то можно всюду далее предполагать, что решается задача поиска минимума.

1.1 Метод простого перебора

Будем предполагать, что искомый минимум является строгим, то есть f (x) > f (x^*) при всех x ? x^*, x [a; b], и других точек локального минимума на отрезке нет. Предположим также, что точка минимума x^* - внутренняя точка отрезка. Зададимся точностью , с которой будем приближённо отыскивать x^*. Приближённое значение точки минимума обозначим , то есть  - это такое число, что

Простейший способ обнаружить точку x^* с точностью  - это перебирать точки x_i отрезка [a; b] с шагом h ? начиная с x₀ = a_, до тех пор, пока не будет выполнено условие f (x_i+1) > f (x_i), то есть пока функция не начнёт возрастать после точки минимума. При этом точка x^* может оказаться либо на отрезке [x_i-1; x_i], либо на отрезке [x_i; x_i+1] (cм. следующий чертёж):

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

Если не предполагать, что локальный минимум на отрезке [a; b] только один и, что точка минимума - внутренняя точка отрезка, то придётся изменить метод так: вычислять значения f (x_i) до тех пор, пока точка x_i не достигнет правого конца отрезка - точки b на каждом шаге сравнивать текущее значение f (x_i) с минимальным из предыдущих значений m заменяя это минимальное значение m на f (x_i) при m > f (x_i). Наконец, вычислить

f (b) (если точка b не совпадает с последней из точек x_i) и также сравнить с минимальным из предыдущих значений. После этой процедуры m будет приближённо равно , а та точка, в которой получено значение функции, равное m - приближённым значением точки минимума x^*.

1.2 Общая схема методов поиска минимума на отрезке

Теперь мы перейдем к рассмотрению других методов, более общих в том смысле, что они не требуют условия непрерывности или дифференцируемости. Они просто предполагают, что по крайней мере в некотором интервале функция f(x) обладает свойством унимодальности. Функция называется унимодальной на отрезке [a₀, b₀], если она монотонно убывает от a₀ до некоторого x^* из [a₀, b₀], а затем возрастает до b₀. В этом случае x^* соответствует локальному минимуму функции, и он единственный.

Пусть функция f(x) унимодальна на отрезке [a₀, b₀]. Необходимо найти точку минимума функции на этом отрезке с заданной точностью е. Все методы одномерного поиска базируются на последовательном уменьшении интервала, содержащего точку минимума. Возьмем внутри отрезка [a₀, b₀] две точки x₁ и x₂: a₀ < x₁ < x₂ < b₀, и вычислим значения функции в этих точках. Из свойства унимодальности функции можно сделать вывод о том, что минимум расположен либо на отрезке [a₀, x₂], либо на отрезке [x₁, b₀]. Действительно, если f (x₁) < f (x₂), то минимум не может находиться на отрезке [x₂, b₀], если f (x₁) > f (x₂), минимум не может находиться на отрезке [a₀, x₁]. Если же f (x₁) = f (x₂), то минимум находится на интервале [x₁, x₂].

Алгоритм заканчивается, когда длина интервала, содержащего минимум, становится меньше е.

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

Точки x₁, x₂ находятся симметрично относительно середины отрезка [a₀, b₀] и делят его в пропорции золотого сечения, когда длина всего отрезка относится к длине большей его части также, как длина большей части относится к длине меньшей части:

и .

Отсюда:

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

Неточное задание величины на ЭВМ уже при достаточно небольшом количестве итераций может приводить к погрешностям и потере точки минимума, так как она выпадает из интервала неопределенности. Поэтому, вообще говоря, при реализации алгоритма возможность такой ситуации должна быть предусмотрена.

1.4 Метод деления отрезка пополам

Пусть дано уравнение f(x)=0, функция f(x) непрерывна на интервале [a, b]. Условие f(a) Ч f(b)<0 указывает тогда на наличие хотя бы одного корня на этом отрезке.

Поделим отрезок [a, b] пополам точкой c, координата которой c=(a+b)/2 и вычислим значение функции f(c).

Возможны два случая:

а) f(a) Ч f(c)>0, т.е. значения функции на концах отрезка [a, c] одинаковы по знаку; тогда корень уравнения находится на отрезке [c, b] и отрезок [a, c] можно исключить из дальнейшего рассмотрения, перенеся точку a в точку c: a=c; f(a)=f(c) (рис. а);

б) f(a) Ч f(c)<0, т.е. значение функции на концах отрезка [a, c] противоположны по знаку; тогда корень находится на отрезке [a, c] и отрезок [c, b] можно исключить из дальнейшего рассмотрения, перенеся точку b в точку c: b=c (рис. б).

После исключения правой или левой половины отрезка продолжают деление пополам до тех пор, пока длина оставшегося интервала [a, b] не станет меньше некоторой заданной малой величины e, т.е. Ѕ b-aЅ <e, и тогда любое значение аргумента из отрезка [a, b] можно считать корнем с погрешностью e. Обычно принимают в качестве корня середину отрезка.

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

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

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

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

В методах прямого поиска при вычислении значений минимизируемой функции f(x) неизбежно возникают погрешности, к которым чувствительны алгоритмы прямого поиска, основанные на сравнении значений функции в отдельных точках. Если унимодальная функция f(x) непрерывно дифференцируема на отрезке минимизации, то точку „‡* наименьшего значения функции можно вычислять как корень уравнения f ' (x) ??0 с помощью тех или иных методов численного решения нелинейных уравнений.

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

2.1 Метод средней точки

Будем искать минимум функции f (x) непрерывно дифференцируемой и строго унимодальной на отрезке [a, b]. В этом случае единственной точкой x*О[a, b] минимума будет стационарная точка, в которой f ' (x*) ??0. Отметим, что непрерывно дифференцируемая унимодальная на отрезке функция может иметь на нем более одной стационарной точки. На отрезке определяются две точки ak, bk, в которых производные имеют разные знаки, f ' (ak) f ' (bk) <--0. Искомый оптимум находится между ними. Делим интервал пополам: , если f ' (xk) >--_--(<--0), то из двух интервалов оставляем тот, на концах которого производная имеет разные знаки.

Метод средней точки напоминает метод дихотомии, но сходится к искомому значению „‡* быстрее. Поскольку для метода средней точки после вычисления n значений производной минимизируемой на отрезке [0, 1] функции f(x) для длины интервала неопределенности получаем l_n = 1/2ⁿ.

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

2.2 Метод Ньютона (метод касательной)

Если строго унимодальная на отрезке [а, Ь] функция Д(х) дважды непрерывно дифференцируема на этом отрезке, то точку х* е [а, Ь] минимума этой функции можно найти путем решения уравнения Д' (х) = 0 методом Ньютона, иногда называемым методом касательных. Выбираем хо - начальное приближение. называемое обычно начальной точкой. Линеаризуем функцию Д' (х) в окрестности начальной точки, приближенно заменив дугу графика этой функции касательной в точке (хо, Д' (хо)).

Уравнений касательной имеет вид / Выберем в качестве следующего приближения к х* точку Х1 пересечения касательной с осью абсцисс (рис. 6). Получаем первый элемент итерационной последовательности (х^) На (Ј+1) - м шаге по найденной на предыдущем шаге точке х Ј можно найти точку противном случае второе слагаемое в правой части (5) может стать неограниченным. Поскольку для дважды непрерывно дифференцируемой функции в точке минимума /» (х*) > 0, то должно быть и /» (Хо) > 0. Поэтому говорят, что метод Ньютона обладает локальной сходимостью в том смысле, что надо выбрать хорошее начальное приближение, попадающее в такую окрестность точки х*, где /"(х) > 0. Однако проверка выполнения этого условия не всегда возможна. Достаточным условием монотонной сходи мости метода Ньютона будут постоянство в интервале между точками х о и х* знака производной /"(х) и совпадение его со знаком /'(х). Оказывается, что в этом случае метод Ньютона обладает квадратичной скоростью сходимости в некоторой окрестности точки х*, причем

2.3 Метод секущих

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

Выбор начальной точки х ₀ проводят следующим образом. Если на отрезке [a, b] функция fx) имеет знакопостоянную третью производную /"(x), то в качестве / выбирают тот конец отрезка [a, b], на котором совпадают знаки f(x) и f» (x), тогда / Точка - точка пересечения с осью абсцисс хорды, стягивающей дугу графика функции f'(x) на отрезке [a, b] (рис 7). Таким образом, первый шаг метода секущих выполняют согласно методу хорд, а последующие шаги - в соответствии (6).

Этот метод имеет сверхлинейную скорость сходимости, причем

где С - const, -

отношение золотого сечения.

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

Рис. 7

2.4 Метод кубической аппроксимации

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

Пусть для непрерывно дифференцируемой функции /(х), строго выпуклой на отрезке / известны значения функции и значения ее производной. Если , то рассматриваемая функция строго унимодальна на этом отрезке.

Рассмотрим метод поиска точки х* при условии уц * у 12 < 0, называемый методом кубической аппроксимации, поскольку в этом случае на отрезке / можно построить единственный многочлен третьей степени, располагая значениями функции и производных на концах этого отрезка. Этот многочлен, называемый кубическим интерполяционным многочленом Эрмита, можно преобразовать к виду:

Из необходимого условия / экстремума этого многочлена с учетом коэффициентов (8), (9) получаем квадратное уравнение

решение которого представим в виде

Легко показать, что

Если , то.- искомая точка минимума функции /х) на oтрезке Если же то оставляем меньший отрезокили такой чтобы и продолжать описанным выше способом поиск точки минимума на новом отрезке. После каждого приближения правильность вычислений подтверждается уменьшением минимального значения многочлена по сравнению с его минимальным значением на предыдущем шаге. Вычисления можно прекратить, когда длина интервала неопределенности, в котором гарантированно находится искомая точка х*, станет меньше заданной наибольшей допустимой величины е.

Алгоритм

Шаг 0. Задать, найти точкитак чтобы

Шаг 1. Вычислитьи

Определить коэффициенты многочленапо формулам (8), (9).

Шаг 2. Найтипо формулам (10). Вычислить, если,

то- искомая точка минимума, конец, иначе шаг 3.

Шаг 3. Если, то, если . Переход на шаг 1

Выводы

В процессе проектирования ставится обычно задача определения наилучших, в некотором смысле, структуры или значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчётом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией. Задача выбора оптимальной структуры является структурной оптимизацией. Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом).

Список литературы

1. Бояринов А.И., Кафаров В.В. Методы оптимизации в химической технологии. - М.: Химия, 1975, - 576 с,

2. Турчак Л.И. Основы численных методов: Учеб. пособие. - М.:Наука. Гл.ред. физ.-мат. лит., 1987. - 320 с.

3. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы: Пер.с англ. - М.: Мир, 1982, - 5бЗс.

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

5. Гилл Ф., Мюррей У., Райт M. Практическая оптимизация: Пер.с анга. - М.: Мир, 1985, - 509 с.

6. Банди Б. Методы оптимизации. Вводный курс: Пер, с англ. - М.: Радио и связь, 1988. - 128 с.

7. Химмельблау Д. Прикладное нелинейное программирование. - М.: Мир, 1975. - 535 с.

8. Карманов В.Г. Математическое программирование. - М.: Наука, 1980. -256 с.

Размещено на Allbest.ru