Нелинейное программирование. Метод штрафных функций

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

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

КУРСОВАЯ РАБОТА

«Нелинейное программирование. Метод штрафных функций»

Введение

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

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

? в исследовании операций: оптимизация технико-экономических систем, транспортные задачи, управление запасами и т.д.;

? в численном анализе: решение линейных и нелинейных систем, численные методы, включая методы конечных элементов и т.д.;

? в автоматике: распознавание образов, оптимальное управление, фильтрация, управление производством, робототехника и т.д.;

? в математической экономике: решение больших макроэкономических моделей, моделей предпринимательства, теория принятия решений и теория игр.

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

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

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

1. Общая постановка задач оптимизации. Основные понятия и определения

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

Математическое программирование в самом общем виде можно определить как задачу оптимизации с ограничениями в пространстве Rⁿ:

Функция f(x) называется целевой функцией (функцией качества, критерием оптимальности), а множество условий g_k(x), l_j(x) и x?D - ограничениями задачи.

Решением задачи (1.1) называют любой вектор x, удовлетворяющий ограничениям, т.е. пара (х^*, f(х^*)), включающая точку х^* и значение целевой функции.

Оптимальным решением или глобальным экстремумом задачи (1.1) называют вектор x*, минимизирующий значение f(x) на множестве всех решений: f (x*) ? f(x) для всех x ?D.

Задача максимизации функции сводится к задаче поиска минимума функции F = - f(x).

Точка х^* является локальным минимумом целевой функции, если в окрестности е этой функции в этой точке достигается ее наименьшее значение.

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

2. Нелинейное программирование

Ряд практических инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск экстремума. На первый взгляд может показаться, что уменьшение размеров области должно упростить процедуру поиска экстремума. Но, напротив, процесс оптимизации становится более сложным, т.к. установленные выше критерии оптимальности нельзя использовать при наличии ограничений. Может нарушаться даже основное условие - равенство нулю первой производной в стационарной точке. Например, безусловный min f (x) = (x ? 2)² имеет место при x*= 2 (т.е. ?f (x*) = 0). Но если задача решается с учетом ограничений x ? 4, то условный минимум достигается в точке x* = 4, где f (4) = 4 ? 0.

2.1 Методы последовательной безусловной оптимизации.

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

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

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

2.2 Методы штрафных функций

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

Рассмотрим задачу:

f (x)>min, xRⁿ, (2.1)

g_i(x) ? 0, i = 1, m (2.2)

h_l (x)=0, l = 1, p.

Предполагается, что точка x* является решением этой задачи, известно некоторое начальное приближение x⁰, возможно недопустимое, т.е. не удовлетворяющее отношениям (2.2). С помощью рассматриваемых далее алгоритмов в пространстве Rⁿ строится конечная последовательность точек x^t, t = 0,1,…, k, которая начинается с заданной точки x⁰ и заканчивается точкой x^k, дающей наилучшее приближение к точке экстремума x* среди всех точек построенной последовательности. В качестве точек последовательности {x^t} берутся стационарные точки штрафной функции - целевой функции вспомогательной задачи безусловной минимизации.

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

Рисунок 2.1 - Метод внутренних штрафов

Рисунок 2.2 - Метод внешних штрафов

В зависимости от того, являются ли элементы последовательности {x^t} допустимыми или недопустимыми точками, говорят соответственно о методах внутренней (рис. 2.1) или внешней точки (рис. 2.2) Иногда их называют методами внутреннего или внешнего штрафа. Методы внутренних штрафных функций называют также методами барьерных функций.

Понятие штрафных функций

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

P (x, R) = f (x) + H (R, g(x), h(x)), (2.3)

где R - набор штрафных параметров,

H - штраф - функции R и ограничений,

H (R, g(x), h (x)) = R? (g(x), h(x)).

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

Методы внутренней точки связаны с такими H, при которых стационарные точки функции P (x, R) оказываются заведомо допустимыми.

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

Методы штрафных функций представляют большой интерес лишь при выполнении следующих требований:

1) решения подзадач должны стремиться к решению задачи нелинейного программирования вида:

lim x^t > x*, t >k < ?;

2) сложность минимизации P (x, R) должна быть того же порядка, что и для функции f (x);

3) правило пересчета R^t+1 = F(R^t) должно быть простым.

В данной работе мы рассмотрим метод внешней точки (метод внешнего штрафа).

Основные типы внешних штрафов.

Квадратичный штраф используется для учета ограничений-равенств вида:

H = R·(h (x))². (2.4)

При минимизации этот штраф препятствует отклонению величины h(x) от нуля (как вправо, так и влево). Ниже будет видно, что при увеличении R

стационарная точка соответствующей штрафной функции P (x, R) приближается к точке x*, т.к. в пределе h(x^k) = 0. Поскольку допустимая область S определяется ограничением h(x) = 0, то в допустимой области значение штрафа H = 0, а вне допустимой области H > 0 и тем больше, чем дальше точка x^t выйдет за пределы допустимой области и чем больше R.

Рис. 2.3 - Квадратичный штраф

Штраф типа квадрата срезки

Рисунок 2.4

 (2.5)

Отметим, что H - внешний штраф, и стационарные точки функции P (x, R) могут оказаться недопустимыми. С другой стороны, недопустимые точки не создают в данном случае дополнительных сложностей по сравнению с допустимыми. Различие между ними состоит лишь в том, что в допустимых и граничных точках H = 0.

Достоинства: функция P (x, R) определена и непрерывна всюду. Вычисления проводятся с положительными R; после решения очередной задачи безусловной минимизации R увеличивается.

Выбор штрафного параметра

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

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

При этом необходимо установить, как именно будет изменяться R при переходе от одной подзадачи к другой. Например, для обычного квадратичного штрафа, учитывающего ограничения равенства, целесообразно начинать с R = 0, т.е. безусловной минимизации функции, а затем последовательно увеличивать R на некоторое ДR. Вычислительные эксперименты показывают, что точно найденная стационарная точка x^t (R) перемещается вдоль некоторой гладкой кривой к точке x*.

С другой стороны, пересчет параметра R, имеющий целью обеспечить сходимость метода, автоматически приводит к ухудшению обусловленности вспомогательных задач (появление овражной структуры штрафной функции). Во многих методах безусловной оптимизации используется матрица Гессе - ?²P (x, R). Показано, что часть собственных значений этой матрицы зависит от величины R. При этом обусловленность матрицы Гессе ?²P (x, R) неограниченно ухудшается, когда R>?. Тем самым усложняется процесс решения вспомогательных задач безусловной оптимизации.

Алгоритмы

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

Шаг 1: задать значения n, m, p, е₁, е₂, е₃, x⁰, R⁰,

где n - размерность вектора x;

m - число ограничений-неравенств;

p - число ограничений-равенств;

е₁ - параметр окончания одномерного поиска;

е₂ - параметр окончания процедуры безусловной минимизации;

е₃ ? параметр окончания работы алгоритма;

x⁰ - начальное приближение для x*;

R⁰ - начальный вектор штрафных параметров.

Шаг 2: Построить P (x, R) = f (x) + H (R, g(x), h(x)).

Шаг 3: Найти значение x^t+1, доставляющее минимум функции P(x^t+1, R^t)

при фиксированном R^t. В качестве начальной точки использовать x^t, в качестве параметра окончания шага - константу е₂.

Шаг 4: Проверка выполнения условия:

|P (x^{t +1}, R^t)? P (x^t, R^{t ?1})| ? е₃.

Да: положить x^k = x^t+1 > конец.

Нет: > Шаг 5.

Шаг 5: Положить R^t+1 = R^t + ДR^t в соответствии с используемым правилом пересчета n > Шаг 2.

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

Метод множителей

Ухудшение обусловленности вспомогательных подзадач в обычной схеме метода штрафных функций существенно ограничивает применимость метода. В ряде работ предложены непараметрические схемы метода штрафных функций (т.е. не используется штраф R). Рассмотрим один из этих случаев.

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

(2.6)

Используя функцию Лагранжа, мы не можем минимизировать ее по x, л и м с целью получения «тройки» (x*, л*, м*), так как данный вектор является не точкой минимума функции L, а ее седловой точкой (стационарной точкой). Оказывается, если определенным образом модифицировать L (например, добавив к ней квадратичное штрафное слагаемое), то полученная в результате формула будет достигать своего безусловного минимума в точке Куна-Таккера исходной задачи. Используя метод множителей Лагранжа, удается избежать нежелательной деформации поверхностей уровня, свойственной методу штрафных функций.

Рассмотрим функцию:

(2.7)

где R - постоянный весовой (нормирующий) коэффициент (в принципе, R может зависеть от номера ограничения i, но не от номера итерации t);

<… > - символ, обозначающий оператор срезки.

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

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

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

Формулы пересчета у и ф

Обозначим: x^t - точка минимума штрафной функции на t - ой итерации,

 (2.8)

т.е. функции P (x, у, ф).

При переходе к (t +1) - ой итерации множители пересчитываются по формулам:

Вектор у не имеет положительных компонент из-за наличия в формуле оператора срезки (g_i (x) ? 0). Компоненты ф могут иметь любой знак.

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

Для контроля сходимости метода используют последовательности

x^t,у^t, ф^t, f (x^t), g (x^t), h (x^t).

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

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

Связь параметров у_i, ф_i с множителями Лагранжа.

Рассмотрим величины у^k, g_i(x^k), ф^k, h_l(x^k), предполагая, что они являются пределами соответствующих последовательностей. Из (2.10) видно, что ф^k может существовать, если только h_l(x^k) = 0.

Аналогично, в силу (2.9) для существования предельных значений

у^k и g_i(x^k) необходимо выполнение одного из следующих условий: либо

(2.11)

С учетом этого запишем выражение для градиента штрафной функции (2.8) в точке x^k:

Первые три ограничения следуют из (2.12).

Отсюда мы видим, что соотношения (2.13) - (2.16) - это условия Куна-Таккера для точки x^k. Таким образом, полученная предельная точка является точкой Куна-Таккера. Из (2.12) видно, что соответствующие значения множителей Лагранжа могут быть найдены по формулам:

то есть, по существу, без каких-либо дополнительных вычислений.

Недостатки: Элементы итерационной последовательности x^t приближаются к x*, находясь почти всегда вне допустимой области отсутствие правила выбора R.

3. Решение задач методом штрафов

Задача 1: Постановка:

Найти минимум в задаче:

f(x) = (x₁ - 4)² + (x₂ - 4)² > min

h(x) = x₁ + x₂ - 5 = 0.

Решение:

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

P (x, R) = (x₁ - 4)² + (x₂ - 4)² + R·(x₁ + x₂ - 5)²

Запишем уравнения, определяющие стационарную точку функции P (x, R):

= 2 (x₁ - 4) + 2R (x₁ + x₂ - 5) = 0,

= 2 (x₂ - 4) + 2R (x₁ + x₂ - 5) = 0, отсюда найдем x₁ и x₂, получим, что х₁ = х₂.

Выразим x₁ и x₂ через R: вместо x₂ подставим в первое выражение x₁ (и сократим на 2):

x₁ - 4 - 5R + 2Rx₁ = 0

x₁ = , следовательно, x₂ = .

Переходя к пределу, получим:

 = 5/2 = 2,5.

Таким образом, метод сходится к точке x* = [2,5; 2,5], тогда f (x*) = 2,25 + 2,25 = 4,5.

В таблице 1 приведены результаты расчетов при R = 0,0.1, 1, 10,100,1000…и т.д. Подсчитаем первую строчку этой таблицы.

Пусть R=0, тогда х1 = х2= 4;

P (x, R) = (4 - 4)² + (4 - 4)² + 0·(4+ 4 - 5)² = 0,

f (x) = (4 - 4)² + (4 - 4)² = 0.

Таблица 1.

R	х1 = х2	P (x, R)	f (x)
0	4	0	0
0,1	3,75	0,75	0,2
1	3	3	2
10	2,57	4,29	4
100	2,51	4,447	4,44
?	2,5	4,5	4,5

Рисунок 3.1 - Линии уровня целевой функции

A = 0,01; B = 3,0; C = 6,0; D = 9,0; J = 27.

На графиках видно, что линии уровня функции P (x, R) при R>0 сближаются с линиями уровня функции f (x).

Рисунок 3.2 Рисунок 3.3

При R=1, P (x, 1) = (x₁ - 4)² + (x₂ - 4)²+ При R=10, P (x, 1) = (x₁ - 4)² + (x₂ -4)²+

+ (x₁ + x₂ - 5)² +10 (x₁ + x₂ - 5)²

A = 5,0; B = 10,0; C = 15; D = 20; E=25; A = 5,0; B = 20,0; C = 35,0;

F = 30; G = 35; J = 50. F = 80,0; J = 140.

Соотношение между значениями f (x) и P (x, R) связано с величиной R, в данном случае R =1 (рис. 3.2). R играет роль весового коэффициента, определяющего относительную значимость ограничения и целевой функции. Ясно, что при увеличении R стационарная точка функции P (x, R) будет смещаться в сторону более точного выполнения ограничения h(x) = 0 и тем самым приближаться к x*.

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

Ответ: x* = [2,5; 2,5], f (x*) = 4,5.

Задача 2: Постановка:

Найти минимум в задаче:

f(x) = (x₁ - 4)² + (x₂ - 4)² > min

h(x) = 5 - x₁ - x₂ ? 0.

Решение: Используем штраф типа квадрата срезки:

Для нашего случая:

P (x, R) = (x₁ - 4)² + (x₂ - 4)² + R·<5 - x₁ - x₂>²

Запишем уравнения, определяющие стационарную точку функции P (x, R):

= 2 (x₁ - 4) - 2R <5 - x₁ - x₂> = 0,

= 2 (x₂ - 4) - 2R <5 - x₁ - x₂> = 0, отсюда, х₁ = х₂. С учетом этого получим:

(x₁ - 4) - R <5 - 2x₁ > = 0, где <5 - 2x₁ > - это <g(x)>.

Проанализируем результаты, когда аргумент оператора срезки g(x) ? 0 и g(x) > 0. Пусть g(x) ? 0, т.е. 2x₁ ? 5 ? 0. Тогда имеем x₁ = . Это получается из выражения (x₁ - 4) - R (5 - 2x₁) = 0

Откуда найдем значение переменной: = 5/2 = 2,5.

Таблица 2.

R	x1 = x2	f (x)	g(x)	H(x)	P (x, R)
0	4	0	-3	0	0
0,1	3,75	0,125	-2,5	0,625	0,625
1	3	2	-1	1	4
10	2,571	4,081	-0,142	0,201	4,283
100	2,507	4,445	-0,014	0,0196	4,474
1000	2,501	4,495	-0,001	0,002	4,498

Рисунок 3.4 Рисунок 3.5

P (x, 1) = (x₁ - 4)² + (x₂ - 4)² + <5 - x₁ - x₂>²

A = 3,5; B = 6,5; C = 9,5; D = 12,5; E = 15,5; F = 18,5; G = 21,5; I = 27,5.

P (x, R) = (x₁ - 4)² + (x₂ - 4)² + 10<5 - x₁ - x₂>²

A = 3,5; B = 6,5; C = 9,5; D = 12,5; E = 15,5;…; J = 30,5.

Таким образом, стационарная точка функции P (x, 1) есть точка

~x = [3,3], причем f (~x) = 2, g(~x) = ?1, P (~x, 1) = 3. При изменении R от 0 до ? стационарная точка функции P (x, R) перемещается вдоль прямой, соединяющей точку [4; 4] - безусловный минимум f (x) с точкой [2,5; 2,5] ее условного минимума. При любом (конечном) R соответствующая стационарная точка недопустима.

Ответ: x* = [2,5; 2,5], f (x*) = 4,5.

Задача 3: Постановка: (метод множителей)

Найти минимум в задаче:

f(x) = (x₁ - 4)² + (x₂ - 4)² > min

h(x) = x₁ + x₂ - 5 = 0.

Получаем: P (x, ф) = (x₁ - 4)² + (x₂ - 4)+ R (x₁ + x₂ - 5+ ф)² ? R ф²,

= 2 (x₁ - 4) + 2R(x₁ + x₂ - 5+ ф) = 0,

= 2 (x₂ - 4) + 2R(x₁ + x₂ - 5+ ф) = 0.

Отсюда: x₁ = x₂ = . (*)

При R = 1 полученное выражение (*) примет вид:

x₁ = x₂ = (9 ? ф) / 3.

Пересчитаем множитель ф по формуле (2.10) и, используя (*), точно вычислим точки безусловного минимума функции P (x, ф) по x, результаты занесены в таблицу 3.

Из таблицы видно, что определяемое по ходу процесса минимальное значение P (x, ф) возрастает с увеличением номера итерации. Таким образом, функция минимизируется по x и одновременно максимизируется по ф, т.е. фактически ищется ее седловая точка.

Таблица 3. R = 1.

t	ф	x1 = x2	h(x)	f(x)	P (x, ф)
0	0	3	1	2	3
1	1	2,6667	0,3334	3,5556	4,3333
2	1,3333	2,5556	0,1112	4,1728	4,4814
3	1,4445	2,5158	0,037	4,3896	4,4979
4	1,4818	2,5062	0,0124	4,4629	4,4997
5	1,5	2,5	0	4,5	4.5

P (x, ф) = f (x) + (x₁ + x₂ ? 5 + 1)² ? (1)².

Рисунок 3.6 - Линии уровня ШФ при ф =1

A = 5, B = 10, C = 15, D = 20, E = 25, F = 30, G = 35, H = 40, I = 45, J = 50.

P (x, ф) = f(x) + (x₁ + x₂ ? 5 +13/ 9)² ? (13/ 9)².

Рисунок 3.7 - Линии уровня ШФ при ф = 13/ 9

Форма линий уровня P (x, ф) для различных ф не меняется. Это является следствием того, что ограничение h(x) - линейно.

Ответ: x* = [2,5; 2,5], f (x*) = 4,5.

Задача 4: Постановка:

Найти минимум в задаче:

f(x) = x > min

h(x) = x ? 2.

Решение: Нетрудно заметить, что решением данной задачи является точка

x*=2, при этом f?=2, но решим задачу аналитически.

Ограничение-неравенство перепишем следующим образом:

h(x) = 2 - x ? 0

Используем штраф типа квадрата срезки:

P (x, R) = x + R·<2 - x >²

При этом предполагается, что x - внешняя точка, т.е.

x < 2, g (x) = 2 ? x > 0

Запишем уравнение, определяющие стационарную точку функции P (x, R):

= 1 - 2R·<2 - x> = 0,

Так как 2 - x > 0, то по определению срезки

получим: <2 - x > = 2 - x

Находим стационарную точку

1 - 4R + 2Rx = 0, отсюда, х = .

При этом g(x) = > 0 при R > 0, иными словами, при любом конечном R > 0 соответствующая стационарная точка является недопустимой, т.е. внешней точкой, и сделанное предположение не нарушается.

Точка x*, являющаяся решением исходной задачи, определяется следующим образом: x* = = 2.

Ответ: x*=2, f*=2

Выводы по работе

Нелинейное программирование возникло в 50-х годах 20-го века одновременно с появлением быстродействующих вычислительных машин, и эти события тесно связаны. Только с появлением быстродействующих вычислителей стало реально возможным выполнять тот громадный объем вычислений, необходимый для решения практически интересных для техники и экономики экстремальных задач. В свою очередь прогресс в области вычислительной техники в значительной степени мотивировался потребностями науки и промышленности в решении подобных задач.

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

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

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

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

Список используемых источников

1. Д. Химмелъблау /Перевод с английского И.М. Быховской и Б.Т. Вавилова. По редакцией М.Л. Быховского Прикладное нелинейное. - Изд. «Мир» Москва 1975.

2. Мицель А.А., Шелестов А.А. Методы оптимизации / часть 1 Учебное пособие / Томск-2002.

3. И.В. Бейко, Б.Н. Бублик, П.Н. Зинько Методы и алгоритмы решения задач оптимизации / Киев Головное издательство издательского объединения «Вища школа» 1983.

4. Б.Ф. Харчистов Методы оптимизации / Учебное пособие / Таганрог 2004.

5. Консультационный центр matlab компании Softline/ А.Г. Трифонов. «Постановка задачи оптимизации и численные методы ее решения».

Режим доступа: [ttp://webcache.googleusercontent.com/search? q=cache: Av6fVk5FaCAJ:matlab.exponenta.ru/optimiz/book_2/3_4.php+Метод+внешних+штрафных+функций].

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