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

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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

	1.2. ЭКВИВАЛЕНТНЫЕ ФОРМУЛИРОВКИ	17
Если	имеется га таких переменных х} (/'= 1, 2, . . га),	то их
можно заменить (га + 1) неотрицательными переменными х)		и х0,
ПОЛОЖИВ	X j = х) — х0.

Пусть исходная задача линейного программирования имеет такой вид:

минимизировать

	П
	z j ci x j
	3= 1
при условиях
п
^ I & i j X j ~	( i= 1) • • ■? пт),
3= 1
Xj ^ о	(/ = 1, . . га).

Тогда новая задача, эквивалентная исходной, будет формули роваться следующим образом:

минимизировать

пп

	2 c j X j	( ZJ c j ) Хо
	3 = 1	3=1
при условиях
п
2	ацх] — ( 2 atj) xQ=	bt	(г= 1, ...,гаг),
5 = 1	з
	^ / > 0		( / = 1, 2, . . . , га),
	х0^ 0 .

Описанные выше эквивалентные преобразования позволяют дать следующее определение задачи линейного программирования. Задачей линейного программирования назовем задачу минимиза ции или максимизации линейной функции, переменные которой удовлетворяют системе линейных ограничений. Среди ограниче ний могут быть как неравенства, так и равенства, а переменные могут быть подчинены или не подчинены требованию неотрица тельности ([37]).

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

найти минимум
Z =	сх	(1')
при условиях
Ах >	Ь,	(2')
х >	0.	(3')
2 т. Х у

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

Вектор х назовем неотрицательным, если каждая его компо нента неотрицательна, т. е. xj ^ 0 для всех /, положительным, если xj > 0 для всех /, и полуположительным, если xj ^ 0 для всех j и Xj > 0 хотя бы для одного /.

Прежде чем приступить к изучению способа нахождения вектора х, минимизирующего (1') и удовлетворяющего условиям (2') и (3'), необходимо ответить на вопрос о существовании реше ния (2') и (3'). В следующем параграфе мы изучим свойства реше ний систем линейных неравенств.

1.3. Неравенства

Будем говорить, что вектор х является решением системы неравенств Ах ^ Ь (или равенств Ах = Ь), если х удовлетворяет

системе Ах ^ b (или Ах = Ь). Компоненты вектора х могут быть положительными, отрицательными или нулевыми.

Т е о рем а 1.1. (О разрешимости системы линейных уравнений.)

Из двух систем линейных уравнений

Ах = Ь (Ь=^0)		( 1)
и	0,	(2а)
уА =	0,	(2а)
yb =	А =#= 0	(26)
имеет решение одна и только	одна.

Д оказательство. Сначала докажем, что (1) и (2) не могут иметь решений одновременно. Предположим противное. Умножив (1)

на	у слева и использовав (26), получим уАх = yb	= А, ф 0	(3),
а	умножив (2а) на х справа — равенство уАх =	Ох = 0.	(4)

Полученное противоречие доказывает невозможность одновремен ной разрешимости систем (1) и (2).

Теперь докажем следующее утверждение. Если система (1) не имеет решений, то система (2) имеет по крайней мере одно

решение.

Пусть

аь

а2,

. . .,

ат — вектор-столбцы матрицы

и аь

а2,

. . ., аг — система

базисных

векторов

матрицы А,

где

г <; т 1)

(г строго меньше т,

в противном случае

вектор Ь может

быть выражен в виде линейной комбинации векторов aj,

а2, . . .

. . .,

ат ).

Поскольку

система (1) не

имеет

решения,

векторы

аь .

. .,

аг, Ь линейно

независимы,

другими

словами,

система

(г +

векторов

[аь

а2,

. . .,

аг, Ь] имеет ранг, равный г +

Пусть

[аь . . .,

аг, Ь]

[Аг,

Ь]. Поскольку ранг системы столб

цов матрицы равен рангу системы строк, то ранг системы строк матрицы [Аг, Ь] также равен г + 1. Поэтому любую (г + 1)-мер-

В Подразумевается, что А есть {т X «)-матрица.— Прим. ред.

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

ную вектор-строку, в том числе и [0, 0, . . ., О, А,], можно выра зить линейной комбинацией базисных вектор-строк матрицы [АГ,Ь]. Обозначим коэффициенты линейной комбинации через y t; тогда.

(у и У^ 1 • • *» Ут)	• • ■>	Ь]	(0, 0, . . ., О, А),
или в другой форме:
уА,. = О,	У ~ {Уи • •		ут),
	уЬ =	А.

Любой небазисный вектор можно выразить в виде линейной ком

бинации базисных векторов: ak —				(£ = 1, . . . , г). Тогда yafe==
				i
= S	И*Уаг =	0 (i =-• 1,	.. ., г; к = 1,	.. ., п), откуда получаем уА = О,
г	А, т. е.	условие	(2).
уЬ =	А, т. е.	условие	(2).
Теорема		1.1. доказана. л

Теорема 1.2. (О неотрицательном решении системы линейных уравнений.) Имеет место только одна из следующих альтернатив: либо система

Ах = Ь (Ь ф 0)

(3)

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

уА >	0,	(4а)
уЬ <	0.	(46)
Д оказательство. Сначала покажем, что системы (3) и (4)		одно

временно не могут иметь требуемых решений. Действительно пусть

х > 0 и	у — требуемые решения систем (3) и (4)				соответственно.
Тогда,	умножив	(3) слева на	у и использовав		(46), получим
		У Ах =	уЬ <	0,	(5)
а умножив (4а)		на х ^ 0 справа, придем к
		уАх ^	0- х =	0.	(6)

Условия (5) и (6) противоречат друг другу, т. е. указанные в тео реме утверждения исключают друг друга.

Покажем теперь, что одна		из систем — (3)		или (4) — всегда
имеет решение. Предположим, что система (3)				не имеет решения.
Тогда, полагая в теореме 1.1 А = —1, получаем
уА = 0	и	уЬ =	—1 < 0,
т. е. у является решением	системы		(4).

2 *

20	ГЛ. 1. ОСНОВНЫЕ понятия
Поэтому для доказательства теоремы достаточно рассмотреть
случай, когда система (3) имеет решение.
Предположим,	что система (3) имеет решения, но неотрица

тельного решения среди них нет. Покажем тогда, что система (4)

будет иметь решение. Доказательство					проведем индукцией			по
п — числу столбцов матрицы А. Если п					=	1,	то система (3) при
нимает вид
			= Ь.
По предположению она		имеет	отрицательное				решение:
\			< 0.
Полагая затем у =	— Ьг, убеждаемся,			что
уЬ = — Ьг • Ь = —Ь2 < 0 и Уа 1 = У ~ - = — ^ 7 > °>
т. е. у = —Ьт является		решением системы (4) при п = 1.
Индуктивное предположение будет иметь следующий вид:
Если система
		2	a}Xj =	b				(7)
		j—i
не имеет неотрицательных решений,				то существует такой у,				что
yaj^O	при	/ = 1,	. . . , п — 1			и	y b < 0 .	(8)

Рассмотрим систему (3) с числом столбцов, равным п. По пред положению она не имеет неотрицательных решений. Следователь но, таких решений не имеет и система (7). Тогда по индуктивному предположению найдется вектор у, удовлетворяющий условиям (8). Если при этом окажется, что уап ^ 0 , то у будет удовлетворять

системе (4): уА ^ 0, yb < 0. Таким образом, доказан индуктив ный переход, а вместе с ним и теорема.

Если же уап <1 0, то положим