Абстрактная задача нелинейного программирования

ОБЩАЯ ЗАДАЧА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции \(f\left(x_{1}, x_{2}, \ldots, x_{n}\right)\) при условии

\( \left.\begin{array}{l} g_{i}\left(x_{1}, x_{2}, \ldots, x_{n}\right) \leq b_{i}, i=\overline{1, k}, \\ g_{i}\left(x_{1}, x_{2}, \ldots, x_{n}\right)=b_{i}, i=\overline{k+1, m}, \end{array}\right\} \)

где \( f \) и \( g_{i} \) – некоторые известные функции n переменных, а \( b_{i}\) – заданные числа.

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

\( g_{i}\left(x_{1}, x_{2}, \ldots, x_{n}\right)=\sum_{j=1}^{n} a_{i j} x_{j}(i=1, m) \), а целевая функция является сепарабельной (суммой \(n\) функций \(\varphi_{j}\left(x_{j}\right)\)) , или квадратической.

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

МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА

Рассмотрим частный случай общей задачи нелинейного программирования (15.1) – (15.2), предполагая, что система ограничений (15.2) содержит только уравнения, отсутствуют условия неотрицательности переменных, \( f\left(x_{1}, x_{2}, \ldots, x_{n}\right)\) и \(g\left(x_{1}, x_{2}, \ldots, x_{n}\right)\) – функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных \( \lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}\) , называемых множителями Лагранжа, и составляют функцию Лагранжа.

\(F\left(x_{1}, x_{2}, \ldots, x_{n}, \lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}\right)=f\left(x_{1}, x_{2}, \ldots, x_{n}\right)+\sum_{i=1}^{m} \lambda_{i}\left[b_{i}-g_{i}\left(x_{1}, x_{2}, \ldots, x_{n}\right)\right]\)

находят частные производные

\(\frac{\partial F}{\partial x_{j}}(j=\overline{1, n}), \frac{\partial F}{\partial \lambda_{i}}(i=\overline{1, m})\)

и рассматривают систему \(n + m\) уравнений

\(\left\{\begin{array}{l} \frac{\partial F}{\partial x_{j}}=\frac{\partial f}{\partial x_{j}}-\sum_{i=1}^{m} \lambda_{i} \frac{\partial g_{i}}{\partial x_{j}}=0, j=\overline{1, n} \\ \frac{\partial F}{\partial \lambda_{i}}=b_{i}-g_{i}\left(x_{1}, x_{2}, \ldots, x_{n}\right)=0, i=\overline{1, m} \end{array}\right.\)

с \(n + m\) неизвестными \(x_{1}, x_{2}, \ldots, x_{n}, \lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}\).Решив систему уравнений (15.3), получают все точки, в которых функция (15.1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (15.3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции \(f(x)=x_{1} x_{2}+x_{2} x_{3}\) при ограничениях

\( \left\{\begin{array}{l} x_{1}+x_{2}=2 \\ x_{2}+x_{3}=2 \end{array}\right. \)

Составим функцию Лагранжа\[ F\left(x_{1}, x_{2}, x_{3}, \lambda_{1}, \lambda_{2}\right)=x_{1} x_{2}+x_{2} x_{3}+\lambda_{1}\left(x_{1}+x_{2}-2\right)+\lambda_{2}\left(x_{2}+x_{3}-2\right) \]

Продифференцируем ее по переменным \( x_{1}, x_{2}, x_{3}, \lambda_{1}, \lambda_{2} \). Приравнивая полученные выражения к нулю, получим следующую систему уравнений\[ \left\{\begin{array}{l} x_{1}+\lambda_{1}=0 \\ x_{1}+x_{3}+\lambda_{1}+\lambda_{2}=0 \\ x_{2}+\lambda_{2}=0 \\ x_{1}+x_{2}-2=0 \\ x_{2}+x_{3}-2=0 \end{array}\right. \]

Из второго и третьего уравнений следует, что \( \lambda_{1}=\lambda_{2}=-x_{2}\); тогда

\( \left\{\begin{array}{l} x_{1}-2 x_{2}+x_{3}=0 \\ x_{1}+x_{2}=2 \\ x_{2}+x_{3}=2 \end{array}\right. \)

Решив данную систему, получим\[x_{1}^{*}=x_{2}^{*}=x_{3}^{*}=1\] и \(f\left(x^{*}\right)=2\)

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

• http://www.math.mrsu.ru/text/courses/method/obshaya_zadacha_nelineinogo_programmirovaniya.htm
• http://www.math.mrsu.ru/text/courses/method/metod_mnogitelei_lagranga.htm