Lektsii_po_teorii_lineynogo_programmirovania

Нам надо придать ей вид общей задачи. Как это сделать, было указано в доказательстве теоремы 1. Пусть

y'=y, с'=-b. Тогда требуется найти arg min<y',с'>.

ATy=c запишем в виде ATy ≤c, -ATy ≤-c, то есть с матрицей

	AT		c
A'=	− AT	имеем A'y ≤b'=	−c .
		0
	Im

Итак, получили

c

(Зо)*о: arg min<y',с'>=?, A'y' ≤b', где c'=-b, b'= −c .

0

Двойственная к ней имеет вид

((Зо)*о)*: arg max<y'',b'>=?, A'Ty''=c', y'' ≤0

– см. теорему 7. Переведем ее в наши первоначальные обозначения.

				c
	y"
y''= y"			, <y'',b'> = <y'',	− c	> = < y",c> - < y",c> = < y" -
			0
	y"

y",c> → max?

y"

при условиях (A,-A,Im) y" =-b

y"

или A( y" - y")+ y"=-b. А так как y'' ≤0, то y" ≤0 и в остальном произвольно.

21

Значит, A( y" - y"

y", то придем к задаче

((Зо)*о)*: Ax ≤b, <

) ≥-b. Если мы положим х≡ y"-

x, c > → min – это как раз Зо.

□

Задача. В доказательстве теоремы 8 в качестве первоначальной рассмотрена только общая задача. Как провести доказательство для любой первоначально поставленной задачи линейного программирования?

Пример 3. Выведем двойственную задачу к канонической

Зк: arg max <c,x>=?, Ax=b, x ≥0.

Сначала сведем задачу к общей

A

Зк→Зо': arg min <c',x>=?, A'x ≤b', где c'=-c, A'= − A ,

− Im

b b'= −b

0

-см. теорему 1. Дальше Зо' превращаем в двойственную

(Зк)*=( Зо')*: arg max <y, b'>=? A'T=c', y ≤0

– см. пример 1.

В первоначальных обозначениях это будет такой задачей:

b

y

y= y

, arg max <y,

− b

> = < y ,b>-< y ,b>=< y - y ,b>=?,

0

y

22

(AT,- AT, -Im)y = AT( y - y )- y = -c, y ≤0, y ≤0, y ≤0.

Положим z ≡ y - y . Тогда получаем задачу

(Зк)*: arg min <z,b>=?, ATz ≥c.

□

Пример 4. Выведем двойственную задачу к нормальной

Зн: arg max <c,x>=?, Ax ≤b, x ≥0.

По теореме 1 сначала сведем эту задачу к канонической, полагая

x'= x , c'=(c1,…,cn, 0…0)T Rn+m, A'=(A, Im);

x

Зк': arg max <c',x'>=?, A'x'=b, x' ≥0.

Теперь согласно примеру 3 заменим эту каноническую на двойственную.

(Зк')*: arg min <z,b>=?, A'Tz ≥c'.

Перейдем к первоначальным переменным.

	T	c			или ATz ≥c, z ≥0.
A'Tz= A	z ≥
Im			0

Итак,

(Зн')* : arg min <z,b>=?, ATz ≥c, z ≥0.

□

Замечание. Сопоставим Зн и (Зн)*, записав их рядом.

Зн: arg max <c,x>=?, Ax ≤b, x ≥0. (Зн)*: arg min <z,b>=?, ATz ≥c, z ≥0.

Мы видим, что эти задачи даже внешне «двойственно» симметричны.

23

5. Теорема двойственности и теоремы существования решения

Теорема 9 (двойственности).

Для пары двойственных задач справедлива альтернатива:

–если значение одной из задач конечно, то значение другой тоже конечно и эти значения совпадают или

–множество допустимых значений в одной из задач пусто Доказательство:

Если значение одной из задач конечно, то есть

конечно S0(b), то же значение имеет и S**(b)=S(b) - по свойству преобразования Лежандра.

Пусть теперь D З0 ≠ø. Тогда S0(b)=-∞. Значит

S**(b)=-∞, но в двойственной задаче S**(b)= max<y,b>, AT y=c, y≥0. Это возможно только если D (З0 )* =ø.

□

Теорема 10 (существования решения).

Пусть x – допустимый элемент, на котором достигается оптимум.

Это возможно тогда и только тогда, когда в

двойственной задаче существует y - допустимый элемент, на котором достигается оптимум, и тогда

<c, x >=< y , b>.

Доказательство:

Пусть x - допустимый элемент, на котором достигается конечный оптимум задачи З0. Тогда по теореме двойственности в задаче (Зо)* есть оптимальный элемент и значения оптимумов совпадают. Пусть теперь

24

дано, что существует пара элементов ( x , y ) такие, что

<c, x >=< y ,b>. Надо показать, что эти элементы

являются оптимальными в своих задачах. Для произвольных допустимых элементов имеем Ax≤b, AT y=c, y≤0.

Поэтому <y,Ax-b>≥0 и значит

<c,x>=<AТy,x>=<y,Ax>=<y,b>+<y, Ax-b>≥<y,b>.

То есть всегда <c,x>≥<y,b> для любого x D З0 для любого y D (З0 )* .

А тогда x и y , на которых достигается равенство являются оптимальными в своих задачах.

□

Следствие: <c,x> ≥ <y,b> для любого x D З0 и для любого

y D (З0 )* .

Задача. Показать, что условия <c,x>=<y,b> является необходимым и достаточным для того, чтобы x и

y были оптимальными элементами З0 и (Зо)* - соответственно.

25

6. Критерии крайней точки невырожденной канонической задачи

Определение 5: Точка замкнутого выпуклого множества называется крайней, если не существует содержащего эту точку открытого интервала, принадлежащего данному множеству.

Запишем каноническую задачу:

Зк: argmax<c,x>=?, Ax=b, x ≥ 0, x R n , b R m

Определение 6: Каноническая задача называется невырожденной, если любая ее крайняя точка содержит ровно m ненулевых координат.

Поясним определение 6 рисунками невырожденных и вырожденных задач.

Рис. 1. (Невырожденная задача)

26

Рис. 2. (Невырожденная задача)

Рис. 3. (Вырожденная задача)

27

Теорема 11. Пусть есть каноническая задача
		Зл : argmax <c,x>=?, Ax=b, x ≥0,
и	допустимая точка x=(x1 ,…,x К ,0,…,0)T R n , j=					,
					1,k
x j	>0. Тогда для того, чтобы точка x являлась крайней
необходимо и достаточно, чтобы столбцы				a1,….,a К
матрицы		A=(a1,…,a К ,a К+1 ,…,a n )	были	линейно
независимы.

Доказательство:

Необходимость. Пусть x - крайняя точка. Рассуждаем от

противного:		предположим,			что	вектора	a1,…,a К -
линейно	зависимы, то			есть	существует		вектор	λ =
					K
( λ 1 ,….., λК )Т		≠	0, такой	что	∑λ j a j =0.		Тогда	для
					j =1
вектора	λ				АΛ=0. Поэтому точка
	Λ=		R n , имеем
		0
x(t)=x+t Λтоже			допустимая при малых t (-ε ,ε ),					x(t)
D Зk , значит x - не является крайней точкой.
								□
Достаточность.			Пусть	столбцы		a1,….,a К - линейно

независимы и (опять от противного) пусть x – не является крайней. Тогда найдутся две допустимые точки

y и z(y,z)		D Зk ,	такие что с некоторым t (0,1) ,
x=ty+(1-t)z.		Так	как x k +1 =…=x n =0,	а y k +1 ,….,y n ,
z k +1	,…,z n - неотрицательны, то необходимо y k +1 ,….,y n =
			k
z k +1	,…,z n =0. Имеем A(y-z)=0, или ∑(y j			- z j )a j =0 то есть

j=1

a1,….,ak- линейно зависимы.

□

28

Теорема 12. Пусть есть невырожденная каноническая задача и x=(x1 ,…,xk,0,…,0),

j=1,k , x j >0 допустимая точка, x D Зл . Тогда

(а) k ≥m

(b) x является крайней тогда и только тогда, когда k=m. Доказательство:

(а) Рассуждаем от противного. Пусть k<m. Рассмотрим матрицу

А= (a k ,…,ak) и множество Y= {y| y Rk+ , Аy=b}. Точка

x =(x1 ,…,x К )Т принадлежит множеству Y : Аx =Ax=b. Значит задача

З: argmax< с,y>=? Аy=b, y ≥0

имеет решение, а множество Y имеет крайнюю точку -

обозначим ее y ,		y =(y1 ,…,y l ,0,…0) R K , j=		, y j >0
			1,l
(может	после	переименования индексов). Получаем
l ≤k<m,	а по теореме 6 соответствующие столбцы
					А

y

линейно независимы. Точка x = 0 Rn опять

0

допустимая, x D Зл , а по предыдущей теореме 6 –

крайняя. Однако число ее ненулевых координат l<m, что противоречит невырожденности первоначальной задачи.

□

(b) Необходимость. Если x - крайняя, то k=m по определению невырожденности задачи.

□

(b) Достаточность. Пусть k=m и x= (x 1 ,…,x m ,0,…,0)T

Rn является допустимой точкой. Рассуждаем от

29

противного. Предположим x- не является крайней

точкой. Значит, по

предыдущей

теореме

6 вектора

а1 ,…,аm

- линейно

зависимы:

λ = (λ ,...,λ

m

)T ≠ 0

и

1

m

λ

∑

λ

j

a j

=0. Тогда для вектора Λ=

R n

,

получаем

j =1

0

и для t (-

АΛ=0. Далее, А(x +tΛ) = Ax +tAΛ = b

для t ,

ε ,ε ) с некоторым ε ,

x+t Λ D Зл . Для j=

, x j +t Λj >0

1,m

при t=0 и по непрерывности в некоторой окрестности значения t=0. Увеличивая t , придем к точке x+t Λ D Зл ,

у которой еще одна из координат первой обратится в нуль, потому что эта точка будет находиться на границе D Зл . Эта точка не крайняя, но лежит на (m-1) мерной

грани. Рассуждая по индукции, мы можем заменить эту точку другой не крайней, лежащей на (m-2) мерной

грани и так далее. Дойдем до точки x , которая принадлежит D Зл и, не являлась крайней, лежит на

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

□

30