Реализация методов штрафных функций

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

Пример:

Решением является:

Применяем метод внешней точки. Рассматриваем ограничение:

Штрафная функция будет типа квадрата «срезки»:

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

Если вычтем из одного другое и приведем, то получим .

Подставим в одно из уравнений:

так как точка внешняя, то ,и выполняется условие:

Докажем, что данная стационарная точка внешняя. Если это так, то мы можем найти решение задачи.

при –внешняя точка. То есть допущение выполняется и мы корректно провели переход.

Для получения решения:

R		f(x)		P(x,R)
	3,000	2,000
	2,572	4,082	0,204	4,286
	2,508	4,455	0,023	4,478
∞	2,500	4,500		4,500

Стационарная точка все время остается внешней. При этом штрафная функция стремится к нулю, расширенная функция стремится к исходной целевой функции.

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

Получаем задачу безусловной оптимизации:

Предполагаем, что x– внутренняя точка, то есть должно выполняться:,

Тогда будет ограничен логарифм и выполняются вычисления:

Если вычтем из одного другое, то получим .

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

При – внутренняя точка.

В следующей внутренней точке R следует уменьшать.

При – внешняя точка и следовательно должна быть отброшена.

В результате решения находим:

Таблица для следующей внутренней точки:

R		f(x)		P(x,R)
	2,349	5,454	1,195	6,649
0,1	2,484	4,600	0,341	4,941
0,01	2,498	4,510	0,057	4,567
	2,500	4,500		4,500

Алгоритм определения минимума методом штрафных функции:

1)Задаются . Определяется тип (внешняя или внутренняя), выбирается штрафная функция , строится P, полагается t=1

2)Решается одним из численных методов задача безусловной минимизации:

Полагается, что начальная точка.

Условие окончания вычислений:

– решение задачи безусловной оптимизации

3)Проверяется условие t=1. Если условие выполняется, то осуществляется переход к пункту 5. Если не выполняется, то переход к пункту 4.

4)Проверяются условия окончания решения исходной задачи:

Если условия выполняются, то вычисления завершаются. Если нет, то переход к пункту 5.

5)Определяется , полагается t=t+1 и осуществляется переход к пункту 2.

Ответ:

5. МЕТОДЫ ДИСКРЕТНОЙ ОПТИИЗАЦИИ (ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ)