Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл (16,20Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 146

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

1.3. НЕРАВЕНСТВА

Система (10) не может иметь неотрицательных решений. Действи

тельно,	подставляя (9)		в (10), получаем
	п -1		п - 1
	%jaj Н" £		/^1 хз
	3= 1		3 = 1
Если бы система (10)			имела неотрицательное решение х]	^ 0,
/ = 1 , . . ., п — 1 , то в силу (8) коэффициент при ага в (11)				был
бы положителен.		Тогда,	очевидно, система (3) имела бы неотрица
тельное	решение	вопреки предположению.

Итак, система (10) не имеет неотрицательных решений. Приме няя индуктивное предположение к системе (10), получаем: суще

ствует такой у', что
у 'а )^ 0 , при			; = 1,		. . . ,	п — 1	и	у'Ь' < 0 .		( 1 2 )
Полагая теперь
					-	J»
					У*71
легко убеждаемся в том, что
Уаз =	( у' —		У) aj = У аз—				—
	v	yan	'			Уап
=	y' (a; —		an) = y ' - a ^ 0				(/ =	1,	—	1)
(в силу (12));
ya„= ( y ' ~ l ^ - y )					an=	y'a„— l^ .y a „ = 0,
		V	Уа П	'			Уа 71
так как в рассматриваемом случае уа„ < 0;
уЬ = (у' — -4^- у) ь =					у' (ь — -^-yb) = у'Ь' <					0
	'	Уап	’		'	Уа п	'
(в силу (12)).		вектор	у является решением системы (4). Индук
Таким образом,		вектор	у является решением системы (4). Индук
ция завершена		и теорема		доказана. в
Теорема	1.3.	(Лемма		Минковского — Фаркаша					о	неотрица

тельном решении системы линейных неравенств.) Выполняется только одна из следующих альтернатив’, либо система неравенств

22	РЛ. 1. ОСНОВНЫЕ понятия

имеет неотрицательное решение, либо неотрицательное решение имеет система

УА > 0 , уЬ < 0.

Д оказательство. Пусть А* — произвольная (т X ?г)-матрица. По теореме 1.2 либо А*х* = b имеет неотрицательное решение, либо имеет решение система неравенств уА* ^ 0 , уЬ < 0. Поло жим А* = [А, I], х* = [х, s]. Тогда теорему 1.2 можно сформу лировать следующим образом:

а) либо система уравнений

Ах + Is =		Ь
имеет решение х ^ 0, s ^	0,
б) либо имеет решение система неравенств
уА > 0,	у1 > 0,	уЬ < 0.

Но утверждение (а) эквивалентно тому, что Ах ^ Ь имеет неотрицательное решение, а утверждение (б) эквивалентно тому, что уА ^ 0 и уЬ < 0 имеет неотрицательное решение. Теорема доказана полностью. ш

Поскольку теорема 1.3 верна для любых А и Ь, мы можем за менить А и Ь на —А* и —Ь*. Затем умножим обе части неравенств на —1, что изменит смысл неравенств на противоположный. Освободившись от (*), оформим полученный результат в виде следствия.

Следствие 1.1. Из двух систем линейных неравенств
Ах > Ь,		(13)
у А < 0 ,	уЬ > 0	(14)
одна и только одна имеет неотрицательное решение.
Теорема 1.4. Система неравенств
Кх >	0, х > 0,	\|(15)

где К т = —К,

имеет по крайней мере одно такое решение х, что

Кх + х > 0.

Д оказательство. Через К ; обозначим i-ю строку из К. Докажем,

что существует такой	вектор	х,- =	х Л, . . ., хц, . . ., xin],	что
K;Xj	хц >	0, KjXi + xi j ^ O .		(16)

1.4. КОНУСЫ, ВЫПУКЛЫЕ МНОЖЕСТВА И ВЫПУКЛЫЕ ФУНКЦИИ 23

Положим в следствии 1.1 b = е; и А = К. Если неотрицатель ным решением обладает система (13), то существует такой хг ^ 0 , что

т.	е.					Кхг^ег,
т.	е.
			К гХг >		1,	К ; Х г > 0		(/' ф	I ) .
Следовательно,			К;х* -f- хц >			0,	К 7-х* + xtj^>0.
	Если неотрицательное решение имеется у системы (14), то
существует xf^ O , такой, что
						х Г к < 0
(это равносильно любому из следующих неравенств:
			Ктхг< 0 ,			- К 1 г< 0 ,		Кхг> 0 ),
и соответственно
			xfe, >	0,	т. е.		хц > 0	и	хи ^ 0 ,
откуда, как и выше,				получаем			соотношения			(16). Итак, в обоих
случаях KjXj -j- хц				0 и К }Х1-\-хц^0				(1Ф]).		Пусть в следствии
1.1	Ь последовательно принимает значения еь									е2, . . . ,	е*, . . . , е„,
a	Xj,	. . . , хп	суть	соответствующие				им	решения.		Тогда х =
	71
=	2	хг будет	искомым решением (17),					для которого выполняется
	i=l
					Кх + х > 0 .
1.4.		Конусы,	выпуклые		множества и			выпуклые функции
	Каждый вектор с п компонентами соответствует точке «-мер
ного		евклидова пространства.					Компоненты			вектора	совпадают

с координатами точки. Пусть дан вектор а; множество точек прямой, содержащей начало координат и данный вектор, может

быть аналитически задано как {х \| х = Ха,	X	^ 0}. Будем назы
вать лучом полупрямую с одним концом	в	начале координат,

а другим — уходящим в бесконечность. Луч, выходящий из нача ла координат и содержащий вектор а, есть множество

{х | х = Ха, X > 0}.

Часть прямой, заключенная между двумя точками, вместе с этими точками называется отрезком. Отрезок от точки а до точки b можно представить как множество в виде

24 ГЛ. 1. ОСНОВНЫЕ п о н я т и я

По аналогии с плоскостью в трехмерном пространстве, гиперпло скость в Е п определяется как множество точек

{х | ах = а}.

Замкнутое полупространство, состоящее из гиперплоскости и то чек, расположенных по одну сторону от этой гиперплоскости, будем обозначать

{х | ах ^ а}.

Конусом С называется множество точек, таких, что

если х £ С, К ^ 0, то Кх £ С.

Пример 1. Любая прямая, проходящая через начало коорди нат, является конусом; в качестве х можно выбрать любой вектор, принадлежащий прямой.

Пример 2. Любая полупрямая, проходящая через начало координат, является конусом. (Останется ли полупрямая конусом, если исключить из нее точку, совпадающую с началом координат?)

Пример 3. Любая гиперплоскость в Еп, проходящая через начало координат, есть конус.

Пример 4. Замкнутое полупространство с граничной гипер плоскостью, проходящей через начало координат, есть конус.

Пример 5. Заштрихованная область на рис. 1.1 есть конус.

Пример 6. Заштрихованная область на рис. 1.2 есть конус.

Пример 7 Множество решений системы Ах ^ 0 образует конус.

1.4. КОНУСЫ, ВЫПУКЛЫЕ МНОЖЕСТВА И ВЫПУКЛЫЕ ФУНКЦИИ 25

Пример 8. Будут ли конусами отрезок и прямая, проходящая через две данные точки?

		{х \| х = Ха +				(1 — к) Ь,	0 ^ К ^ 1},
		{х \| х =		+ (1 — А.) Ь, —оо < X <; оо}.
Множество С точек из Е п называется выпуклым конусом, если
выполняются			следующие условия:
1)	если	х,	у £ С,	то	х + У € С;
2)	если	х 6 С и 1 ^ 0			,	то Хх £ С.
Конусы, приведенные						в примерах 1, 2, 3, 4 и 6, являются
выпуклыми, а конус в						примере	5 — невыпуклый, нескольку
можно указать два				вектора, сумма			которых не принадлежит С.

Определим операции над выпуклыми конусами и установим

некоторые их		свойства.	конусы, то их суммой	Ct + С2
Если С\	и	С2 — выпуклые	конусы, то их суммой	Ct + С2
называется	множество
Ci	+	С2 = {х \| х = х4	+ х2, X! е Си х2 6 С2}.

Очевидно, сумма двух выпуклых конусов есть также выпуклый конус. Например, сумма двух прямых, проходящих через начало координат (двух выпуклых конусов) есть плоскость, содержащая эти две прямые. Сумма двух полупрямых есть конус, рассмотрен ный в примере 6.

Если Cj и С2 — выпуклые конусы, то их пересечение Сх (] Сг определяется как

Cl П с г = {х I х 6 Cl и х 6 С2}.

Очевидно, пересечение двух выпуклых конусов есть также выпуклый конус. Например, пересечение двух полупространств в Е2 образует выпуклый конус, показанный на рис. 1.2.

Для выпуклого конуса С определим двойственный ему конус С* следующим образом:

С* = {у | у х < 0 для всех х £ С}.

Двойственный конус состоит из векторов, образующих неост рые углы с векторами из С (рис. 1.3). В примере 1 двойственным

конусом С* является плоскость,				перпендикулярная к прямой.
В	примере	2	двойственный	конус	С* — полупространство
{у \| ух ^ 0 } ,		где	х — ненулевой	вектор, принадлежащий полу
прямой.		конус С называется конечнопорожденным, если
он	Выпуклый
	является	суммой конечного числа			полупрямых:

С = (аД + (а2) + . . . + (ап).

26	ГЛ. 1. ОСНОВНЫЕ ПОНЯТИЯ

Направляющие векторы этих полупрямых называются образую щими векторами выпуклого конуса.

Из определения суммы выпуклых конусов ясно, что любой вектор в конечнопорожденном конусе можно представить как

х = Я-iai

"I- . . .

-|- Япа^,

тде Xj ^

0 и 2

— 11 aj — произвольные направляющие векто-

3 =

Будем говорить, что вектор х

ры соответствующих полупрямых.

есть выпуклая линейная ком

бинация

образующих

векторов

aj а = 1 , . . . , п).

Если

рассматривать

векторы

а;

(;

= 1, . . .,

п)

как

вектор-

столбцы матрицы А, то множество

точек конечнопорожденного конуса

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

зом:

С =

{У I У =

Ах для х >

0},

т. е. каждый вектор у

в конусе

является

неотрицательной

линей

ной

комбинацией вектор-столбцов

матрицы

А.

называется вы

Множество

пуклым, если вместе с любыми

двумя

точками

этого

множества

х 4 и х 2 в нем содержится и точка Xxj +

(1 — X) х2,

0 ^

X ^ 1.

Понятие

выпуклого множества можно

сформулировать

более

общем виде.

если вместе

точками

Множество X называется выпуклым,

xt, . . .,

хА из

X множество

X содержит и

точку

х:

х — 2 XiXi,

Xi =

i=l

называемую выпуклой линейпой комбинацией точек Xj, . . ., хд.

Докажем эквивалентность этих двух определений выпуклого множества. Очевидно, первое определение является частным слу чаем второго. Поэтому множество, выпуклое по второму опреде лению, является выпуклым и по первому. Индукцией по к пока жем, что верно и обратное утверждение. При к = 2 определения совпадают. Предположим, что при к = т из выпуклости по пер вому определению следует выпуклость по второму, и докажем это утверждение при к = т + 1.

Смотрите также файлы

Циперович, М. В. Обогащение углей в тяжелых суспензиях.pdf

Чеботаревский, В. В. Лаки и краски - что это такое.pdf

Черкасов, Г. И. Введение в технологию бетона.pdf

Чупахин, В. М. Производство жестяной консервной тары учебник.pdf

Шамрай, Ф. И. Сплавы вольфрама, молибдена и ниобия с бором и углеродом.pdf

Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно