Исследование методов штрафных функций

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

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

Государственное образовательное учреждение высшего профессионального обучения

АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

(ГОУВПО «АмГУ»)

Факультет математики и информатики

Кафедра МАиМ

Специальность 010501 «прикладная математика»

Курсовая работа

по курсу: Методы оптимизации

на тему: Исследование методов штрафных функций

Благовещенск 2006

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

Государственное образовательное учреждение высшего профессионального обучения

АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

(ГОУВПО «АмГУ»)

Факультет математики и информатики

Кафедра МАиМ

Специальность 010501 «прикладная математика»

Задание

к курсовой работе студентов

Тема работы: Исследование методов штрафных функций;

Срок сдачи студентами законченной работы: 15.12.2006 г.;

Дата выдачи задания: 01.09.2006 г.

Руководитель

к.ф-м.н., доцент

Задание принял к исполнению 02.09.2006 г.

Реферат

Курсовая работа, 26 страниц, 4 рисунков, 2 таблиц, 5 источников.

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНЕ, ОПТИМИЗАЦИЯ, ШТРАФ, БАРЬЕРНАЯ ФУНКЦИЯ, АЛГОРИТМ, МЕТОД, ИТЕРАЦИЯ

Объектом исследования являются методы штрафных функций.

Изучены методы и механизмы переход от задачи условной оптимизации к эквивалентной задаче или последовательности задач безусловной оптимизации.

По ходу исследования были решены некоторые примеры с помощью этих методов.

Содержание

Введение

1. Общая задача нелинейного программирования

1.1 Постановка задачи

1.2 Теорема (обобщенное правило множителей Лагранжа)

1.3 Регулярный случай

1.4 Теорема (обобщенное правило множителей Лагранжа в регулярном случае)

1.5 Достаточные условия, существование, единственность

1.6 Об ограничениях-равенствах

1.7 Еще один достаточный признак условного минимума

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

2.1 Метод барьерных поверхностей

2.1.1 Алгоритм метода барьерных поверхностей

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

2.2.1 Алгоритм метода штрафных функций

Заключение

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

ВВЕДЕНИЕ

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

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

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

1. Общая задача нелинейного программирования

1.1 Постановка задачи

Общей задачей нелинейной условной оптимизации мы будем называть условную задачу минимизации

f0(x) ? min, x ? ?,(1.1)

где ? выделяется как ограничениями типа равенств

fi(x) = 0, i = 1, ..., k,(1.2)

так и ограничениями типа неравенств

gj(x) ? 0, j = 1, ..., l(1.3)

Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из Rm в Rk и Rl, соответственно, определяемые координатами fi и gj. Поэтому задачу (1.1)-(1.3) можно записывать в виде

f0(x) ? min, f(x) = ?, g(x) ? ?.(1.4)

(напомним, что неравенство g(x) ? ? означает покоординатные неравенства).

Нам также потребуется следующее обозначение: a+ = (a + |a|)/2; таким образом, a+ = a, если a ? 0 и a+ = 0, если a ? 0. Для векторов a ? Rm операция "+" определяется покоординатно: a+ = ((a1)+, ..., (am)+). Кроме того, через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j ? {1, ..., l}: gj(x) = 0} -- это номера ограничений, которые в данной точке существенны. Например, на рисунке 1 J(x1) = {2}, а J(x2) = ?.

1.2 Теорема (обобщенное правило множителей Лагранжа)

Пусть f0, f, g ? C1, а x* -- локальное решение задачи (1.4). Тогда найдутся такие ?*0 ? R, ?* ? Rk, ?* ? Rl, не равные одновременно нулю, такие, что ?*j ? 0 при j ? J(x*) и

(1.5)

Доказательство. Возьмем r > 0 таким, чтобы x* = argminx??r f(x), где ?r = ? ? B(x*, r). Для любого n ? N определим функцию f n: Rm ? R равенством

f n(x) = f0(x) + n(||f(x)||2 + ||g+(x)||2) + ||x ? x*||2.

Задача 1. Докажите, что f n ? C1, в частности, покажите, что (||g+(x)||2)? = 2g+(x)g?(x).

Поскольку f n непрерывно дифференцируемы и поэтому непрерывны, функции f n на шаре B(x*, r) достигают минимума; обозначим его через xn. В частности,

f n(xn) ? f n(x*),(1.6)

т. е.

f0(xn) + n(||f(xn)||2 + ||g+(xn)||2) + ||xn ? x*||2 ? f n(x*).

Отсюда, поскольку, как легко видеть, f n(x*) = f0(x*),

ыражение в квадратных скобках ограничено, так как xn ? B(x*, r). Поэтому ||f(xn)||2 + ||g+(xn)||2 ? 0 при n ? ? и, следовательно, f(xn) ? Q и g+(xn) ? ? при n ? ?.

Пусть теперь {xni} -- произвольная сходящаяся, скажем к y, подпоследовательность. Тогда, как легко видеть, во-первых, y ? ? и, во-вторых, f ni(xni) ? f0(y) + ||y ? x*||2 при n ? ?. Поэтому, подставляя в (1.6) ni вместо n и переходя к пределу в получившемся неравенстве при i ? ?, получим

f0(y) + ||y ? x*||2 ? f0(x*).

С другой стороны, так как x* = argmin f(x), f0(x*) ? f0(y). Отсюда ||y ? x*||2 ? 0, т. е. y = x*. Таким образом, любая сходящаяся подпоследовательность последовательности {xn} сходится к x*. Последнее, учитывая компактность последовательности, гарантирует ее сходимость к тому же пределу.

Далее, в силу доказанного можно считать, что при всех n точка xn лежит внутри шара B(x*, r). Поэтому в силу теоремы Ферма (f n)?(xn) = Q, т. е.

(1.7)

Положим теперь

?n0 = sn, ?ni= 2nfi(xn)sn, ?nj= 2n[gj(xn)]+sn. Поскольку ?n0,?nj,?nj? [?1, 1] (n ? N; i = 1, ..., k; j = 1, ..., l), можно считать, не ограничивая общности, что найдутся такие ?*0,?*iи ?*j, что

??n0? ?*0, ?ni? ?*i, ?nj? ?*j при n ? ?.

Умножив (1.7) на sn и переходя в получившемся равенстве к пределу при n ? ?, получаем

(1.8)

Остается заметить, что, во-первых, так как |?n0|2+ ?ki=1|?ni |2+?lj=1|?nj|2=1, не все из ?*0,?*i,?*jравны нулю, во-вторых, поскольку ?nj= 2n[gj(xn)]+sn ? 0, неотрицательны и ?*jи, наконец, в-третьих, если j ? J(x*) (т. е. gj(x*) < 0), то gj(xn) < 0 при больших n; поэтому [gj(x*)]+ = 0, что влечет равенство ?*j= 0 и, следовательно, равенство

Таким образом (1.8) -- это (1.5).

1.3 Регулярный случай

Так же, как и в случае ограничений-равенств в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если ?*0? 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (1.5) на ?*0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: Rm?Rk?Rk ? R (в регулярном случае) равенством

L(x, ?, ?) = f0(x) + (?, f(x)) + (?, g(x)).

Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ?1(x),..., f ?k(x)линейно независимы и для некоторого ненулевого вектора h ? Rm

(f ?i(x),h) = 0 при i = 1, ..., k

и

(g?j(x),h) < 0 при j ? J(x).

Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ?i(x)),и, во-вторых, он образует с градиентами g?j(x)активных ограничений (указывающими, очевидно, вовне множества ?) тупой угол (рисунок 2).

1.4 Теорема (обобщенное правило множителей Лагранжа в регулярном случае).

Пусть f0, f, g ? C1, а x* -- регулярное локальное решение задачи (1.4). Тогда найдутся ?* ? Rk, ?* ? Rl не равные одновременно нулю, такие, что ?*j ? 0 при j ? J(x*) и

L?x(x*,?*, ?*) = 0,(1.9)

(?*, g(x*)) = 0.(1.10)

Доказательство. Пусть ?0**, ?** и ?** -- величины, существование которых утверждается в теореме 1.2. Покажем, что ?0** ? 0. В предположении противного умножим (1.5) скалярно на вектор h, фигурирующий в определении регулярности x*:

(1.11)

В силу регулярности (f ?i(x*),h) = 0 и (g?j(x),h) < 0, а по теореме 7.2 ?j**? 0 при j ? J(x*). Поэтому (1.11) влечет равенство ?** = Q. Но тогда (1.5) означает, что

что вместе с линейной независимостью f ?i(x*)дает равенство ?** = Q. Противоречие.

Таким образом ?0**? 0. Положим теперь ?*i= ?i**/?0**(i = 1, ..., k),

Очевидно теперь, (1.10) выполняется автоматически, а (1.9) тривиально получается из (1.5).

1.5 Достаточные условия, существование, единственность

Ситуация с задачей (1.1)-(1.3) несколько отличается от изучавшихся ранее, поскольку минимумы здесь могут быть двух типов. В случае, когда в точке минимума x* нет активных ограничений, т. е. J(x*) = ?, ситуация полностью аналогична описанной в предыдущем параграфе, поскольку ограничения-неравенства в окрестности точки x* можно опустить (смотри рисунок 3а). В случае же, когда J(x*) ? ? минимум может достигаться на границе множества ? и точка x* может не быть стационарной точкой (смотри рисунок 3б).

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

Теорема (достаточные условия минимума). Пусть f0, f, g ? C2, а x* -- допустимая точка такая, что для некоторых ?* ? Rk и ?* ? Rl, одновременно не равных нулю, выполнены условия (9)-(10) и при любых h ? Rm, h ? Q таких, что

нелинейный программирование алгоритм последовательность

(f ?i(x*),h) = 0 при i = 1, ..., k;

(g?j(x*),h) = 0 при j ? J(x*), ?*j> 0;

(g?j(x*),h) ? 0 при j ? J(x*), ?*j= 0

выполнено неравенство (L??xx(x*,?*, ?*)h, h) > 0. Тогда x* -- локальное решение задачи (1)-(3).

1.6 Об ограничениях-равенствах

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

f(x) = Q

эквивалентно ограничениям

f(x) ? ?, ?f(x) ? ?.

С другой стороны, задачи с ограничениями-равенствами мы уже достаточно подробно рассматривали выше.

Здесь, правда, следует помнить об одном важном обстоятельстве. При решении задач с ограничениями-неравенствами часто бывает важна (существенно используется) выпуклость функций, фигурирующих в задаче, вернее, выпуклость минимизируемой функции f0 и выпуклость множества ? допустимых точек. Последнее гарантируется выпуклостью функций gj в ограничениях-неравенствах. Множества же, выделяемые ограничениями-равенствами, не бывают выпуклыми, за исключением случая аффинных функций fi. Поэтому методы решения задач условной оптимизации, существенно использующие "выпуклость задачи" могут применяться к задачам с ограничениями-равенствами с большой осторожностью.

Напомним, что множество ? ? Rm называется выпуклым, если ?(x, y ? ?, ? ? [0, 1])[?x + (1 ? ?)y ? ?].

1.7 Еще один достаточный признак условного минимума

Напомним, что точка (x*, ?*) называется седловой точкой функции L: ?1??2 ? R (?1 ? Rm, ?2 ? Rl), если при всех (x, ?) ? ?1??2 выполнены неравенства

L(x*, ?) ? L(x*, ?*) ? L(x, ?*)

Теорема. Пусть (x*, ?*) -- седловая точка функции Лагранжа L: Rm?Rl+? R задачи (1), (3) (здесь Rl+= {? ? Rl: ? і ?}), ?* і ?, x* -- допустимая точка. Тогда x* -- глобальное решение этой задачи.

Доказательство. Пусть x -- произвольная допустимая точка, т. е. gi(x) ? 0 (i = 1, ..., l). Тогда

f0(x*) + (?*, g(x*)) = L(x*, ?*) ? L(x, ?*) = f0(x) +(?*, g(x)).(1.12)

Покажем, что

(?*, g(x*)) = 0.(1.13)

Тогда из (12), поскольку ?* і Q, а g(x) ? ?, будет следовать нужное неравенство f0(x*) ? f0(x). Для доказательства (1.13) заметим, что по условию теоремы L(x*, ?) ? L(x*, ?*), т. е.

(?*, g(x*)) ? 0.(1.14)

Равенство (1.13) вытекает теперь из (14), т.к. ?* і ?, а g(x*) ? Q.

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

Однако, если функции f0 и gi (i = 1, ..., l) выпуклы, а множество ? содержит хотя бы одну внутреннюю точку, то условия доказанной теоремы являются необходимыми и достаточными (это утверждение называется теоремой Куна -- Таккера; оно является центральным фактом теории выпуклого программирования).

2. МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ

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

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

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

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

Параметрические методы подразделяются на: 1) методы внутренней точки; 2) методы внешней точки; 3) комбинированные методы.

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

Итак, пусть задача нелинейного программирования имеет следующий вид:

минимизировать

,

(2.1)

при ограничениях

,

, .

В основу штрафных функций положено преобразование задачи (2.1)-(2.3) в задачу минимизации без ограничений вида

(2.4)

где - штрафная функция;

- весовые коэффициенты;

, - некоторые функционалы.

Выбирая вид функционала , руководствуются следующими вариантами:

при.

Для чего необходимо, чтобы точка x всегда была внутренней точкой, т.е. чтобы выполнялось условие,

при .

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

при и при .

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

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

,

,

.

2.1 Метод барьерных поверхностей

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

,(2.7)

где - параметр, значения которого убывают с каждой итерацией при ;

- положительные весовые коэффициенты.

При этом барьерная функция (поверхность) неограниченно возрастает при .

Примерами барьерных функций являются:

а) обратная функция

(2.8)

б) логарифмическая функция

.

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

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

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

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

2.1.1 Алгоритм метода барьерных поверхностей

Пусть задача нелинейного программирования имеет следующий вид:

минимизировать

при ограничениях , .

Начальный этап. Выбрать в качестве константы остановки, начальную допустимую точку , для которой , , скаляр и . Положить и перейти к основному этапу.

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

минимизировать

,(2.9)

где описывается одним из выражений (2.8).

Положить равным оптимальному решению задачи (2.9) и перейти ко второму шагу.

Второй шаг. Если , то остановиться. Решение является искомым. В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.

Пример. Рассмотрим следующую задачу:

минимизировать

при условии .

Решим ее методом барьерных поверхностей с барьерной функцией . В табл. 6.7 приведены результаты вычислений. Вычисления начались при n=10, а безусловная оптимизация функции начиналась с точки. В качестве начального значения параметра выбрано . После шести итераций получена точка для которой и выполнение алгоритма остановлено. Можно непосредственно проверить, что эта точка близка к оптимальной. Учитывая, что уменьшаются, по табл. 6.7 легко заметить, что - функции, которые не уменьшаются от , а - не увеличивается от .

Кроме того, стремится к нулю.

Таблица 1

k
1	10.0	0.708; 1.532	8.334	0.970	18.039	9.705
2	1	0.828; 1.110	3.821	2.359	6.180	2.359
3	0.1	0.899; 0.964	2.528	6.419	6.170	0.642
4	0.01	0.924; 0.916	2.129	19.078	2.320	0.191
5	0.001	0.940; 0.901	2.004	59.046	2.063	0.059
6	0.0001	0.944; 0.896	1.964	184.445	1.983	0.0184

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

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

Рисунок - 4

На рисунке 4 представлена функция P вида

для трех различных значений: а) ; б) ; в) , где легко увидеть влияние барьерных поверхностей при больших значениях . Штриховой линией изображена траектория поиска.

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

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

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

минимизировать

(2.10)

при ограничениях

, (2.11)

. (2.12)

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

В частности, для ограничений типа (2.11), (2.12) целесообразно использовать штрафную функцию следующего вида:

, (2.13)

где R1, R2 - непрерывные функции, которые удовлетворяют условиям:

, если и , если ,

, если и , если .

Типичными являются следующие выражения для функций R1, R2:

; ,

где p - целое положительное число.

Таким образом, штрафная функция обычно имеет вид

,(2.14)

Далее от задачи нелинейного программирования (2.10)-(2.12) переходим к задаче безусловной оптимизации вспомогательной функции:

минимизировать

, (2.15)

где - штрафной коэффициент.

Пусть - непрерывная функция вида (2.13). Обозначим

(2.16)

Подход, связанный со штрафной функцией, состоит в решении задачи вида:

максимизировать (2.17)

при ограничении

Справедлива следующая теорема, которая обосновывает этот метод [1].

Теорема. Пусть задача нелинейного программирования задана в виде (2.10)-(2.12), где - непрерывные на Rn функции.

Предположим, что задача имеет допустимые решения и пусть - непрерывная штрафная функция вида (2.13). Предположим также, что для любого r существует решение xr, задачи минимизации вспомогательной функции и все xr принадлежат некоторому компактному подмножеству X. Тогда справедливо следующее уравнение:

(2.18)

где определяется в соответствии с (2.16).

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

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

2.2.1 Алгоритм метода штрафных функций

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

Итак, пусть имеем задачу нелинейного программирования:

минимизировать f(x)

при ограничениях , ,

где функции непрерывны.

Начальный этап. Выбрать . Выбрать начальную точку x1, параметр штрафа и число . Положить и перейти к основному этапу.

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

минимизировать

,(2.19)

где - целое.

Положить xk+1 равным оптимальному решению этой задачи и перейти ко второму шагу.

Второй шаг. Если , то остановиться. В противном случае положить . Заменить k на k+1 и перейти к первому шагу.

Пример. Рассмотрим следующую задачу:

минимизировать ,

при ограничениях .

В качестве штрафной функции выберем . Тогда на k-й итерации при заданном значении параметра rk необходимо решать следующую задачу:

минимизировать ,

где .

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

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

Таблица 2

k
1	0.1	1,4539; 0,7608	0.0935	7.8307	0.7831	0.8766
2	1	1.1687; 0.7407	0.5753	0.3908	0.3908	0.9661
3	10	0.9906; 0.8425	1.5203	0.01926	0.1926	1.7129
4	100	0.9507; 0.8875	1.8917	0.000267	0.0267	1.9184
5	1000	0.9461; 0.8934	1.9405	0,0000028	0.0028	1.9433

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ:

1. Гасс С. Линейное программирование. М.:Физматгиз,1961

2. Зангвилл В.И. Нелинейное программирование. М.: Советское радио,1973

3. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Мн., Вышэйшая школа, 1994.

4. Кузнецов А.В., Холод Н.И. Математическое программирование. - Мн., Вышэйшая школа, 1984.

5. Эрроу К.Дж., Гурвиц Л., Удзава Х. Исследования по линейному и нелинейному программированию. М.:ИЛ,1962

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