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

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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

46			ГЛ. 2. СИМПЛЕКС-МЕТОД
Непосредственно			отсюда . получаем решение	z =	3,	х2 = 4/3,
х3 = 5/3,	Zj =	0.	Если теперь х4 будет принимать положительные
значения,	то	величина z будет увеличиваться;		таким		образом,
z = 3 является минимальным значением для z.					— (3) и есть
Способ, примененный для решения задачи				(1)	— (3) и есть

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

I. Пусть дана система уравнений. Рассмотрим пространство решений этой системы. Пространством решений является множе ство всех точек, удовлетворяющих системе уравнений. Если число переменных равно числу уравнений и матрица коэффициен тов невырожденная, то пространство решений состоит из одной точки, так как система имеет единственное решение. Если пере менных больше, чем уравнений, то пространством решений обычно является прямая, плоскость или пространство более высокой размерности. Говорят, что две системы совместных уравнений эквивалентны, если они имеют одно и то же пространство решений.

Т еорем а 2.1. Процедура исключения Гаусса не изменяет про

странства решений системы совместных уравнений.

Д о к а з а т е л ь с т в о . Процедура исключения Гаусса состоит и*

двух элементарных операций:

а. умножение уравнения Ei на ненулевую константу kt и замена уравнения Ei уравнением кхЕ 4;

б. сложение уравнений Ei и Е 2 и замена уравнения Е 2 урав

нением Ei	+ Е 2.	0,	то kiEi (х) =		0,	и обратно.	Из усло
Очевидно,	если E t (х) =
вия Ei (х) = 0 и Е 2 (х)		=	0	следует,	что	Е 4 (х) +	Е 2 (х) = О
и Ei (х) =	0 и обратно. Таким образом,				метод исключения не из
меняет пространства решений.				Например, системы уравнений
	Ei (х) + Е2 (х) = 0				Ei (х) = 0
	ktEi (х) =			0	Е2(х) = 0

эквивалентны.

II. В рассмотренном примере мы начинали с допустимого реше ния Xi = 5, х2 = 3, и допустимость сохранялась на протяжении всего процесса. Если бы мы выбрали диагональную форму отно сительно z, Xi и х3, то получили бы

z	— Зх2	1 ,
	Xi — Зх2	= —4,
	I	-р х3— 3,
	х2	-р х3— 3,

2.1. ВВЕДЕНИЕ

откуда z = —1, Xi = —4, х3 = 3. Обсуждение процедуры нахож дения допустимого начального решения будет проведено в § 2.3.

III. Если z-уравнение принимает вид

	Z —По* m+l^m+l —flo, m+2— • • • a0nxn= G00i			(4)
где	a0J- ^ 0 (/	=	т + 1 , . . ., п), то почему а00 есть	минималь
ное	значение	z?

Предположим, система представлена в диагональной форме отно сительно других переменных. Нельзя ли получить z-уравнение

	2	■— Оо, jn+l^m+l —а0, т+2^т+2— • • • —О,0 п^п — &00i	(4 )
где a0j >	0	и а00 < а00? И почему мы всегда должны представлять
систему	в диагональной форме?

Имеется по крайней мере два способа ответить на эти вопросы. Сначала дадим ответ, для которого не требуется материала первой главы. Заметим, что пространство решений системы линейных уравнений не изменяется при процедуре исключения Гаусса. Таким образом, решение, удовлетворяющее уравнению (4), являет ся решением исходной системы. В уравнении (4) все переменные неотрицательны, следовательно, а00 является нижней границей z, если не рассматривать остальных уравнений диагональной формы относительно z, xit . . ., хт. (Ограничения не могут умень шить нижнюю границу минимизируемой функции.) Если из ос тальных уравнений диагональной формы следует, что х3 ^ О (/' = 1 , . . ., т), то а00 действительно является минимальным зна

чением функции z.

Используя материал гл. 1, можно дать другой ответ на постав ленные вопросы. Рассуждения при этом будут более длинными, однако они имеют прозрачный геометрический смысл. Целевая функция z, если она линейна, изображается гиперплоскостью. Остальные уравнения также являются гиперплоскостями, и их пересечение вместе с условиями Xj ^ 0 определяет пространство

решений. Поскольку гиперплоскости выпуклы, их пересечение тоже выпукло, и следовательно, пространство решений есть вы пуклое множество. Для линейной функции, являющейся выпуклой и определенной на выпуклом множестве, локальный минимум совпадает с глобальным. Уравнение (4) ■определяет локальный минимум z. Кроме того, базисное решение определяет вершину (или крайнюю точку) выпуклого множества, а мы знаем, что линей ная функция, являясь вогнутой, достигает своего минимума в край ней точке (по теореме 1.13, если существует оптимальное решение, то существует и базисное оптимальное решение). Поэтому мы представляем систему в диагональной форме (относительно опре деленных переменных), что дает нам базисное решение.

48	ГЛ . 2. СИМ ПЛЕКС-М ЕТОД

IV. На каком основании можно утверждать, что метод конечен? Поскольку мы переходим от .одного базиса к другому и существует

лишь конечное число базисов ( не более

конечность гаранти

рована, если только базисы, це будут повторяться. Если величина z все время строго уменьшается, то различным значениям z соответ ствуют разные базисы, что обеспечивает конечность. Однако в за даче на некотором шаге можно получить bt = 0. Поскольку вели

чина целевой функции изменяется на с} min	, преобразов а-
- '	Хаи'.

ние может не изменить целевой функции. Если одному и тому же z соответствует несколько базисов, возможно возникновение зацик ливания ([102], [9]). Процедура, обеспечивающая конечность, будет рассмотрена в § 2.4.

V. Пусть выбрана переменная с положительным коэффициен том в z-уравнении, а в столбце, соответствующей этой перемен ной, нет ни одного положительного члена. Тогда значение этой переменной можно сделать сколь угодно большим, причем осталь ные переменные останутся неотрицательными. Следовательно, z может принимать любые отрицательные значения, т. е. задача не имеет конечного решения.

2.2. Таблица симплекс-метода

Рассмотрим линейную программу в канонической форме: минимизировать

			z =	П
			z =	2 cixi
при условиях				з—1
при условиях
	п
	2 a i j X j = b i		(t = 1, . . . , т ) ( m ^ L n ) ,
j=i
	X j > 0			(/ = 1, . . . , n ) .
Представим	задачу в	диагональной			форме	относительно —z,
x t, . . . , x m ( C j ,	ац и bi	обозначают коэффициенты						диагональной
формы)
— Z		"Т" c m+l х т + 1 4 ~			■ • • “Ь Cji %п		—	“— 2о,
	X i	+	а 1, m+lx m+i 4 “		• • •	п^п	“	Ьи
	х2		0-2, m +i^-m +l ~Ь		• • • ~Ь <h.nx n		—	Ь2,

"1“ а т , m +lXm +l “Ь • • • “Н а тп х п — ЪтП’

2.2.

ТАБЛИЦА

СИМПЛЕКС-МЕТОДА

Базисным решением

является

z =

z0,

xi =

(г = 1,

xm+i = . . . = х п — 0.

Допустим,

что

все 6г>

т. е. мы получили

начальное базисное

решение.

Перепишем диагональную форму в следующем виде:

З’о

Ч- а0, m+l^m+l

4“ • • • Ч- Яоп^п

Яось

a i,m+i^m+i

Ч~• •

• Ч~ ЯцХп

Я10,

Ч"~ Я2, m+l^m+l

Ч- • •

• Ч- 0'2пх п

a20i

Хт +

ат, m+l^m+l Ч~~ ■■• 4“ НщпХп —

где х0= —z,я0о

= —Z0,

a0j =

cj,

a,0 = &;• Такая

форма обычно

записывается в виде

таблицы

х2

•

хт

хт+1

хп

а00

о . .

а0, т +1

* а0п

х2

а 10

а1, m+i

а1п

а 20

а2, т +1

* а2п

Хщ

ат0

ат, т+1

•

атп

Верхняя строка таблицы представляет собой выражение х0 через все переменные. Каждая строка таблицы задает уравнение, сво бодный член которого записан в самом левом столбце таблицы. Слева от таблицы записаны текущие базисные переменные. Мы начали с таблицы, в которой яго ^ 0 (г = 1, . . ., т). Если это условие выполнено, то таблица называется прямо допустимой, поскольку базисные переменные, равные аго, дают допустимое решение исходной задачи. Если a0j ^ 0 (/ = 1, . . ., п), то табли ца называется двойственно допустимой, поскольку соответствую щее решение является допустимым решением двойственной зада чи 1). Если одновременно a0j ^ 0 (/ = 1, . . ., п) и яго ^ 0 (t = = 1 , . . ., т), то решение оптимально.

Симплексный алгоритм можно описать по			шагам.
0.	Начать с таблицы,	где ai0 ^ 0 (i = 1,	. . ., т).
1.	Если все a0j ^ 0,	конец. Текущее решение является опти

мальным. В противном случае среди a0j < 0 выбрать минималь-*4

!) Термины «двойственно допустимый» и «двойственная задача» будут объяснены в гл. 3. Здесь условия a0j > 0 означают, что значение z не может быть уменьшено за счет возрастания любой небазисной переменной от нуля.

4 т. Ху

50	ГЛ. 2. СИМПЛЕКС-МЕТОД

ный. Пусть a0s = min a0j < 0, т. е. a0s — минимальный отрица-

тельный элемент. Столбец s называется ведущим столбцом.

2. Среди « i s > 0		найти aTS, такое,	что— = min —		(г =	1 , . . .
t . e. среди		положительных	a rs	i a is		найти
			элементов	столбца s
дающий минимум отношению — . Элемент ars				называется		веду-
		a is
щим элементом. Строка г называется ведущей строкой.					чтобы все
3. Использовать процедуру исключения Гаусса так,
коэффициенты в s-м столбце, кроме ars, стали				нулевыми,		a ars
стал единицей.	Заменить базисную		переменную	хТ на	xs	слева
от таблицы. Вернуться к шагу 1.
Алгоритм работает и в том случае, когда на шаге 1 выбирается
любое a0j = Cj <	0.	Критерий min cj < 0 использовался по ана-
		3

логии с «наискорейшим» спуском. На шаге 2 операция отыскания

min	для выбора ведущей строки называется проверкой отно-
i	a is

шения. Она используется для получения в результате преобразо вания ai0 ^ 0 .

Шаги алгоритма повторяются до тех пор, пока на 1-м шаге все элементы нулевой строки не станут неотрицательными. Тогда, если положить в текущей таблице базисные переменные, записан ные слева от таблицы, равными ai0, будет получено оптимальное решение.

Решим пример, используя симплексную таблицу.

Пример 1. Рассмотрим задачу: минимизировать

2 = 11 — Х 3 — £4 — Х5,

при условиях