Файл: Падалко Л.П. Математические методы оптимального планирования развития и эксплуатации энергосистем учеб. пособие.pdf

ж е одноэкстремальными,

потому

что у

них

существует

одна экстремальная точка,

д о с т а в л я ю щ а я

абсолютный

(глобальный)

минимум

или

максимум

задаче .

З а д а ч и

невыпуклого

программирования

называют

многоэкстре­

мальными,

потому что у них может

быть

не одна

экстре­

мальная

точка. Методы

выпуклого

программирования,

солютного оптимума . Точное решение задачи

при этом

не гарантируется.

§ 2.2. Теорема Куна—Таккера

В а ж н о е

место

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

занимает теорема

К у н а — Т а к к е р а . Эта теорема

представ ­

ляет

собой

обобщение метода множителей

Л а г р а н ж а

для

экстремальных задач, с о д е р ж а щ и х в качестве огра­

тельного м е т о д а решения з а д а ч .

Пусть рассматривается

с л е д у ю щ а я з а д а ч а :

min

/ { * ! ,

х2,...,

хп);

(2.2)

qt(xlt

х2,...,

хп)

< 0 (/ =

1, 2, ... , т ) ;

(2.3)

* , > ( ) .

(2.4)

Теорема

К у н а — Т а к к е р а

опирается на понятие седло -

вой точки,

которой

д а д и м определение. С этой целью з а ­

пишем

функцию Л а г р а н ж а

для рассматриваемой

з а д а ч и :

m

F(X,

l) =

f(X) +

2iXiqj(X).

Пара векторов

X

=

хъ

х2,...,

хп и

X — Хг,

Х2,...,

Хт

называется седловой

точкой

функции

F(X,

X)

в

области

х1 >- 0,

Xj >• 0

для

всех

і и

/, если

выполняется

следующее

соотношение:

F(X,

X) <

F(X,

X) <

F{X,

Kj.

(2.5)

Это

соотношение

может

быть

записано

т а к ж е

иначе:

F(X,

X) =

min

max

F(X,X).

(2.6)

A'

0

АГ О

Условие

(2.6)

требует

минимизации

функции

Л а ­

г р а н ж а

ПО ОДНОЙ Группе ПеремеИНЫХ

(Х = Х\, Xz,

хп)

и

максимизации по другой группе переменных

(Х=Х\,

Х%,

Хт). Искомое

решение и

определяет

седловую

точку.

М о ж н о д а т ь геометрическую интерпретацию

седловой

точке. С этой целью обратимся к рис. 2.3. Вдоль

оси

х\

целевая

функция

выпуклая,

а

вдоль

оси

х% —

вогнутая.

В точке

Х = 0(хі = 0, Х 2 = 0 )

целевая

функция

достигает

минимума по Х\ и максимума

по х% Н а рис.

2.4

д а н а

другая

геометрическая

интерпретация

седловой

точки.

Здесь показаны линии постоянного уровня целевой

функ­

ции в окрестности седловой точки. Из этой

геометриче­

ской интерпретации понятен смысл условия (2.6),

в

со­

ответствии с которым осуществляется минимизация

функ­

ции по X и максимизация

по X.

И т а к, з а д а ч а

нахождения

седловой

точки_

функции

f(xu

х2,

хп)

сводится

к нахождению точки X,

X,

удов­

летворяющей

соотношению (2.6).

Теорема Куна.—Таккера формулируется

следующим

образом: вектор

Х=

(хи

х2,

х„)

тогда

и

только

тогда

представляет_решение

задачи

(2.2)

—(2.4),

когда

сущест­

вует

вектор

% такой,

что F(X,

X)<F(X,

%)^F(X,

Я) для

всех

х'і > 0,

kj

>

0.

Д а н н у ю теорему мы

приводим

без доказательства, от­

сылая читателя к специальной литературе [14].

Таким образом, из

теоремы

К у н а — Т а к к е р а

вытека­

ет, что решение задачи

(2.2) — (2.4)

сводится к

нахож ­

дению седловой точки для функции

Л а г р а н ж а .

Учитывая, что условия К у н а — Т а к к е р а (2.5),

(2.6) от­

таком

виде:

m

l

f

_

i

L

+

V

l

A

>

0 ;

(2.7)

dF

х, = 0, л - , . >0;

(2.8)

дх,

dF

=

<7/<0;

.

(2.9)

дК,-

q,h

= 0 ,

\

> 0 .

(2.10)

Эти условия м о ж н о интерпретировать следующим об­

разом. Ввиду того что седловая точка

является

миними­

зирующей

по

отношению

к

к а ж д о й переменной

xh

она

не может

совпадать

с точкой, у

.,

dF

^ п

так

как

которой

-—

< 0 ,

иначе

функция

могла

бы уменьшаться

dxt

х,.

с увеличением

dF

Таким

образом,

в седловой

точке

^ 0 . В

то

ж е вре-

dxt

xt

мя, если в седловой

точке

> 0 ,

то

переменная

допустимых

решений, т а к

ж е как и в линейном програм ­

мировании,

представляет

выпуклый многогранник.

Н а рис. 2.5 п о к а з а н этот многогранник

для линейных

условий задачи, рассмотренной в § 1.1. Пусть

целевая

функция имеет общий вид (xi—а)2+(Х2—Ь)2=с.

З а д а ч а

состоит

в том,

чтобы найти

ту

точку многогранника, в

которой

целевая функция

приобретает

минимальное

(максимальное)

значение. К а к

видно из рис. 2.5,

имеют­

ся три

возможности решения

(для случая

минимизации

целевой функции) . Искомые оптимальные

точки

обозна­

чены через х*. Таким образом,

если в линейном програм ­

так и внутри области допустимых

решений.

З а п и ш е м условие

К у н а — Т а к к е р а

для

квадратичной

задачи . С этой целью составим функцию

Л а г р а н ж а :

п

п

п

т

п

F(x, х) = 2 Р Л +

2 2

W )

+ 2

М 2

anxi ~ bi)-

,•=1

t = l

j=l

i=]

1=1

С д е л а е м следующие

обозначения: