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

⇐ ПредыдущаяСтр 8 из 8

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

Теоретическое обоснование

Изучите теоретический материал по данной теме, используя литературу [1, 2] и материал изложенный ниже.

Методы внутренней точки

Рассмотрим общую задачу математического программирования, не содержащую ограничений в виде неравенств:

Z=F(x) (min) (10.1)

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

q_i(х) (10.2)

Пусть вблизи локального минимума этой задачи х^* эта окружность, где есть такая точка х⁰, в которой q_i(x⁰) 0 и выполняются условия строгой нежесткости: U_i(x^*)> 0, если q_i(х^*)

Видоизменим достаточные условия локального минимума в точке х^*.

Если в задаче математического программирования множество D выпукло, а функция F(x) дифференцируема в точке х^*Î D является точкой оптимума, то градиентÑ F(x^*) (если он отличен от нуля) составляет острый угол с вектором направленным из х^*в точку " точку х₁Î D, а скалярное произведение (Ñ F(x^*), x₁-x₂) .

Предположим, что при малом τ > 0 b в точке [x(r), u(r)] вблизи в точке (x^*, u^*) выполняются условия:

(10.3)

Выразим из второго условия (10.3) и подставим в последнее равенство:

(10.4)

Дифференцированием можно установить, что левая часть полученного выражения есть градиент функции

(10.5)

который обращается в нуль 0, в точке x(r). Причем x(r)®x^* при r®0. Функцию Z(x, r) в таком виде называют логарифмической штрафной функцией.

Можно получить другой вид функции Z (x, r), если положить U_i=x²_i:

(10.6)

(10.7)

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

1) в окрестности оптимальной точки значения функции близки к значению заданной минимизирующей функции;

2) каждая функция из построенного семейства достаточно быстро возрастает при приближении к границе допустимой области из «внутренней» части допустимой области.

Итак, к минимизируемой функции исходной задачи мы добавили ряд слагаемых, называемых штрафными (барьерными) функциями, зависящими от параметра r и функции одного из ограничений. При фиксированном значении параметра r второе слагаемое стремиться к ∞ при стремлении к нулю его аргумента, если r=const, то . Каждая функция семейства подвергается минимизации и этот процесс не может вывести x^* за пределы допустимой области. Подобные методы назвали «методами внутренней точки».

Замечание. При наличии ограничений-равенств в задаче математического программирования «метод внутренней точки» неприменим, так как не существует допустимой области (в виде областей).

Пример1.

Решение.

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

В полученных выражениях оставим знак«+» , т.к.x ₁

Зададим последовательные значения r: 1; 0.5; 0.25; 0.1; соответственно получим последовательность значений: x₁(r)=0.5; 0.309; 0.183; 0.085; x₂(r)=1.25; 0.595; 0.283; 0.107, сходящуюся к точке (0, 0) при r 0.

Действительно

Графическое решение этой задачи представлено на рисунке 10.1

Рисунок 10.1 – Графическое решение задачи

Рассмотрим решение задачи линейного программирования методом внутренней точки.

Пример 2

Решение

Строим функцию штрафа.

Z(x, r)=x₁-r ln x₁

Находим частную производную по x₁ второго порядка

следовательно x₁(r) = r – точка минимума при r> 0.

Методы внешней точки

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

1. Рассмотрим ограничения в ослабленной форме:

Преобразуем условия дополняющей нежесткости u_i^*; q_i(x^*)=0 так, чтобы оно имело смысл для отрицательных значений q_i(x^*) и сводилось к исходному условию при (это значит, что u_i (x^*) 0; u_i(x^*)принимает все значения, если q_i (x^*)=0), т.е.

u(r)=-min[0, q_i(x)] (10.9)

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

(10.10)

Подставляем (10.9) в (10.10), убеждаемся, что функция, для которой выполняются названные условия, имеет вид

(10.11)

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