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

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

(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 х₁ +4 x₂ (которую можно рассматривать как вогнутую) и квадратичной формы , которая является отрицательно-определенной и, следовательно, также вогнутой. Система ограничений задачи включает только линейные неравенства, поэтому область допустимых решений выпуклая. Следовательно, можно воспользоваться теоремой Куна-Таккера.

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

и запишем, используя (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

- M

- M

bi

x1

x2

l1

l2

v1

v2

w1

w2

z1

z2

- М

z1

-1

- М

z2

-1

-1

w1

w2

-1

Dj

-2

-4

-3

-1

-1

-1

-6

- М

z1

-1

x2

1/2

-1/4

-1/4

w1

-1

1/2

1/2

w2

1/2

-1/4

-1/4

Dj

-2

-1

-2

-1

-2

x1

1/2

-1/2

x2

-1/2

-1/2

w1

-3/2

-1/2

1/2

1/2

w2

-1/2

-3/4

-1/4

Dj

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

Дата добавления: 2014-10-22