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

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

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

(4.1)

(4.2)

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

Если f, g_i – линейные функции, то имеем задачу линейного программирования. Если f – квадратичная функция, a g_i – линейная, то имеем задачу квадратичного программирования. Если f – отношение двух линейных функций, a g_i – линейные функции, то имеем задачу дробно-линейного программирования. Если f – вогнутая (выпуклая) функция, а область допустимых решений, определяемая ограничениями (4.2), является выпуклым множеством, то имеем задачу выпуклого программирования.

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

4.1. Выпуклое программирование

Рассмотрим задачу выпуклого программирования:

(4.5)

(4.6)

где является выпуклой (вогнутой) функцией; функции - выпуклыми.

Метод решения задачи выпуклого программирования опирается на теорему Куна-Таккера.

Функция , заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек Х₁ и Х₂ из множества X и любого выполняется соотношение

.

Функция , заданная на выпуклом X, называется вогнутой, если для любых двух точек Х₁ и Х₂ из множества X и любого выполняется соотношение

.

Множество допустимых решений задачи (4.5)-(4.6) удовлетворяет условию регулярности, если существует, по крайней мере, одна точка X_k, принадлежащая области допустимых решений, такая, что .

Функцией Лагранжа задачи выпуклого программирования (4.5), (4.6) называется функция

где - множители Лагранжа.

Теорема Куна-Таккера. Для задачи выпуклого программирования (4.5), (4.6), множество допустимых решений которой обладает свойством регулярности, является оптимальным решением тогда и только тогда, когда существует такой вектор , где , что точка является седловой точкой функции Лагранжа.

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

(4.7)5

(4.7)6

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

Алгоритм решения задач выпуклого программирования

Шаг 1. Составляют функцию Лагранжа.

Шаг 2. Записывают необходимые и достаточные условия существования седловой точки для функции Лагранжа (4.7)56.

Шаг 3. Находят решение системы (4.7)56 и из него получают оптимальное решение задачи выпуклого программирования.

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

Решение. Функция f(x_l,x₂) является вогнутой, поскольку представляет собой сумму линейной функции 2х₁+4x₂ (которую можно рассматривать как вогнутую) и квадратичной формы , которая является отрицательно-определенной и, следовательно, также вогнутой. Система ограничений задачи включает только линейные неравенства, поэтому область допустимых решений выпуклая. Следовательно, можно воспользоваться теоремой Куна-Таккера.

Составим функцию Лагранжа

и запишем, используя (4.7)56, необходимые и достаточные условия существования седловой точки построенной функции:

(4.8)7

(4.9)8

Систему линейных неравенств (4.8)7 перепишем следующим образом:

(4.10)9

Введем теперь дополнительные неотрицательные переменные v₁, v₂, w₁ и w₂, обращающие неравенства (4.10)9 в равенства:

(4.11)10

С учетом дополнительных переменных соотношения в системе (4.9)8 можно записать в виде:

(4.12)11

Для нахождения базисного решения системы линейных уравнений (4.11)10 с учетом выполнения равенств (4.12)11 воспользуемся методом искусственного базиса. В первое и второе уравнения системы (4.11)10 введем дополнительные неотрицательные переменные z₁ и z₂ соответственно и рассмотрим задачу линейного программирования:

Чтобы решить эту задачу, сначала находим ее допустимое базисное решение (таблица 4.1).

Из таблицы 4.1 получаем:

Таблица 4.1

ci	БП	0	0	0	0	0	0	0	0	- M	- M	bi
		x1	x2	1	2	v1	v2	w1	w2	z1	z2
- М	z1	2	0	1	2	-1	0	0	0	1	0	2
- М	z2	0	4	2	-1	0	-1	0	0	0	1	4
0	w1	1	2	0	0	0	0	1	0	0	0	8
0	w2	2	-1	0	0	0	0	0	1	0	0	12
	j	-2	-4	-3	-1	1	1	0	0	-1	-1	-6
- М	z1	2	0	1	2	-1	0	0	0	1		2
0	x2	0	1	1/2	-1/4	0	-1/4	0	0	0		1
0	w1	1	0	-1	1/2	0	1/2	1	0	0		6
0	w2	2	0	1/2	-1/4	0	-1/4	0	1	0		13
	j	-2	0	-1	-2	1	0	0	0	-1		-2
0	x1	1	0	1/2	1	-1/2	0	0	0			1
0	x2	0	1	1	-1/2	0	-1/2	0	0			1
0	w1	0	0	-3/2	-1/2	1/2	1/2	1	0			5
0	w2	0	0	-1/2	-3/4	1	-1/4	0	1			11
	j	0	0	0	0	0	0	0	0			0

Так как , заключаем, что точка ( ) является седловой точкой функции Лагранжа для исходной задачи. Следовательно, - оптимальное решение исходной задачи, f_max = 3.