МО-Лекции

Очевидно, что столбцы матрицы B образуют базис m -мерного пространства. Поэтому вектор A0 и любой столбец матрицы D можно представить в виде линейной комбинации столбцов матрицы B .

Умножим (3) на B 1 слева:
B 1Bx	B 1Dx B			1	A	(4)
B			D		0
и найдем отсюда xB :
x	B 1	A	0 B 1Dx	D	.	(5)
B

Придавая xD различные значения,					будем получать различные реше-
ния xB .
Если положить xD 0 , то
		x	B	B	1	A	.	(6)
					0

Решение (6) называют базисным решением системы из m уравнений с m n неизвестными.

Если полученное решение содержит только положительные компоненты, то оно называется базисным допустимым.

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

Если среди компонент xB нет нулевых, то базисное допустимое решение называется невырожденным.

Определение 6. План x задачи линейного программирования будем называть опорным, если векторы условий Ai с положительными

коэффициентами линейно независимы.

То есть опорный план – это базисное допустимое решение расширенной системы, угловая точка многогранника решений.

Определение 7. Опорное решение называется невырожденным, если оно содержит m положительных компонент (по числу ограничений).

Невырожденный опорный план образуется пересечением n гиперплоскостей из образующих допустимую область. В случае вырожденности в угловой точке многогранника решений пересекается более чем n гиперплоскостей.

80

8.2. ОСНОВНАЯ ТЕОРЕМА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Теорема 1 [8]

1.Линейная форма z c x достигает своего минимума в угловой точке многогранника решений.

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

Доказательство. Доказательство теоремы основано на следующей лемме.

Лемма. Если D – замкнутое, ограниченное, выпуклое множество, имеющее конечное число крайних (угловых) точек, то любая точка x D может быть представлена в виде выпуклой комбинации крайних точек D (рис. 8.1).

Рис. 8.1. Допустимая область

1) Пусть x 0 – некоторая внутренняя точка. Многогранник ограниченный, замкнутый, имеет конечное число угловых точек. D – допустимое множество.

Предположим, что точка x 0 является оптимальной точкой, т. е. z x 0 z x , x D . Предположим, что точка x 0 не является угло-

вой. Тогда на основании леммы точку x 0 можно выразить через угловые точки многогранника xi , т. е.

p			p
x 0	i x i ,	i 0 ,	i 1 .
i 1		i	1

81

Так как функция z x	линейна, то
	p
	z x 0	i z x i .	(*)
	i 1
Выберем среди точек	xi ту, в которой линейная форма z x		прини-

мает наименьшее значение. Пусть это будет точка x k . Обозначим минимальное значение функции в угловой точке через z :

z z(x k ) min z x1 , z x 2 , , z x p .

1 i p

Подставим данное значение функции в линейную форму (*) вме-

сто z	x i	и получим
			p			p
		z	x 0	i z	z		i	z .
			i 1			i 1
Так	как	x 0 – оптимальная		точка,		то	получили		противоречие:
z x 0	z* (!). Следовательно,			z	x 0	z x k		, x 0	x k – угловая
точка.
2) Предположим,			что линейная форма z				x	принимает минималь-

ное значение более чем в одной угловой точке, например, в угловых

точках	x1, x 2 ,..., x q		имеем z		x1	z x 2 ...	z	x q	z . Тогда если
x является выпуклой комбинацией этих точек, т. е.
			q	i x i ,	q
		x			i	1 и i	i	0 ,
			i 1	i	1
		a		a
то z x	z	i x i	z	i	z .
	i	1		i 1

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

82

достигает в любой точке, являющейся выпуклой комбинацией этих угловых точек.

Теорема 2. Если известно, что система векторов условий A1,..., Am ,

(m n)	линейно независима и такова, что
	x1A1			... xm Am A0 ,
где все	x j 0 , то точка x			x1,..., xm , 0,..., 0 является угловой точ-
кой многогранника решений.
Теорема 3. Если вектор x				является угловой точкой многогранника

решений, то векторы условий, соответствующие положительным компонентам вектора x , являются линейно независимыми.

Следствия:

1)угловая точка многогранника решений имеет не более m положительных компонент вектора x ;

2)каждой угловой точке многогранника решений соответствует m

линейно независимых векторов из данной системы: A1,..., An .

8.3.СИМПЛЕКС-МЕТОД

8.3.1.ВВЕДЕНИЕ В СИМПЛЕКС-МЕТОД

Этот метод называют еще методом последовательного улучше-

ния плана [8]. Метод предназначен для решения общей задачи линейного программирования.

Пусть имеем следующую задачу:

Q x c1x1 c2 x2 ... cn xn

min ,

(7)

с системой ограничений вида

a 1,1 x 1	a1,2 x2	...	a1,n xn	b1
......................................................				. (8)
a m ,1 x 1	am,2 x2	...	am,n xn	bm

83

Разрешим эту систему относительно переменных x1,..., xm :

x1	a1,m 1xm 1	...	a1,n xn	b1
....................................................				.	(9)
xm	am,m 1xm 1	...	am,n xn	bm

Векторы условий, соответствующие x1,..., xm , образуют базис. Переменные x1,..., xm назовем базисными переменными. Остальные пере-

менные задачи – небазисные.

Целевую функцию можно выразить через небазисные переменные:

Q	x	cm 1xm 1	cm 2 xm 2 ...	cn xn	c0	min .
Если приравнять небазисные переменные нулю
		xm 1	0, xm 2 0, ..., xn		0 ,
то соответствующие базисные переменные примут значения
		x1 b1	, x2 b2 , ...,	xm	bm .
Вектор x	с	такими компонентами		представляет собой угловую
точку многогранника решений (допустимую) при условии, что bi							0

(опорный план).

Теперь необходимо перейти к другой угловой точке с меньшим значением целевой функции. Для этого следует выбрать некоторые небазисную и базисную переменные так, чтобы после того как мы «поменяем их местами», значение целевой функции уменьшилось. Такой направленный перебор в конце концов приведет нас к решению задачи.

Пример 1. Пусть

Q x x 4 x5 min

x1 x4 2x5 1, x2 2x4 x5 2, x3 3x4 x5 3.

84

Выберем в качестве базисных следующие переменные: x1, x2 , x3

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

	x1	1		x4	2x5 ,
	x2	2		2x4	x5 ,
	x3	3		3x4	x5.
Переменные x4 , x5 являются			небазисными. Если взять x4 0 и
x5 0 , то получим угловую точку (опорный план)
x1	1		2	3	0	0	,
которому соответствует Q x1			0 .

Значение целевой функции можно уменьшить за счет увеличения x5 . При увеличении x5 x1 также увеличивается, а x2 и x3 – уменьшаются. Причем x2 может стать отрицательной раньше. Поэтому, вводя в базис переменную x5 , одновременно x2 исключаем из базиса. В результате

после очевидных преобразований получим следующие выражения для новой системы базисных переменных и целевой функции:

x 5	2	x2	2x4 ,
x1	5	2x2	3x4 ,
x3	1	x2	5x4 ,

	Q x	2	x4 x2	min .
Соответствующий опорный			план	x 2 5 0 1 0 2	и
Q x 2	2 .

Целевую функцию можно уменьшить за счет увеличения x4 . Увеличение x4 приводит к уменьшению только x3 . Поэтому вводим в

85

базис переменную x4 , а x3 исключаем из базиса. В результате полу-

чим следующие выражения для новой системы базисных переменных и целевой функции:

			x	1								1					x			1						x ,
	4			5								5							2	5								3
			x	28										7					x					3				x ,
	1			5								5							2	5										3
			x	12											3			x						2				x ,
	5			5								5							2	3										3
	Q x			11									4				x				1					x					min .
				5								5							2	5								3
	Соответствующий опорный план x 3																			28											0 0	1	12		и значение
																				5												5	5
	целевой функции Q		3	11						. Так как все коэффициенты при неба-
		x
						5

зисных переменных в целевой функции неотрицательны, то нельзя уменьшить целевую функцию за счет увеличения x2 или x3 . Следова-

тельно, полученный план x 3 является оптимальным.

Пример 2. Пусть имеем задачу

	Q x		x1	x2	min
	x3	1	x1	x2
	x4	2	x1	2x2 .
		x	0
Переменные x3 , x4	– базисные, а			x1, x2	– небазисные переменные.
Опорный план x0	0 0 1	2	, Q x0		0 .

86

Теперь вводим в базис переменную x1 , а x4 исключаем из базиса.

В результате получим следующие выражения для базисных переменных и целевой функции:

	x1	2	2x2		x4 ,
	x3	3	x2		x4 ,
	Q x		2	3x2		x4 .
Опорный	план x1 2 0	3	0	,	значение		целевой функции
Q x1	2 .
Теперь можно заметить, что при увеличении x2							значения перемен-
ных x1 и x3 также возрастают, т. е. при x2						в допустимой области
Q x	(задача не имеет решения).

Замечание. В процессе поиска допустимого плана может быть выявлена противоречивость системы ограничений.

8.3.2. АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Формализованный алгоритм симплекс-метода состоит из двух основных этапов [8]:

1)построение опорного плана;

2)построение оптимального плана.

Проиллюстрируем алгоритм на рассмотренном ранее примере:

Q x x4 x5 min

x1 x4 2x5 1, x2 2x4 x5 2, x3 3x4 x5 3,

x 0 .

87

1 2 3 0 0

В случае базисных переменных x1, x2 , x3 начальная симплексная таблица для данного примера будет выглядеть следующим образом:

		x4	x5	1
x1	=	1	–2	1
x2	=	–2	1	2
x3 =		3	1	3
Q x	=	–1	1	0

Она уже соответствует опорному плану x1

(столбец свободных членов).

Построение оптимального плана. Для того чтобы опорный план был оптимален при минимизации целевой функции, необходимо, чтобы коэффициенты в строке целевой функции были неположительными (в случае максимизации – неотрицательными), т. е. при поиске минимума мы должны освободиться от положительных коэффициентов в

строке Q x .

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

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

br	min	bi		ail	0 .
arl		ail

Тогда arl – разрешающий (направляющий) элемент, строка r – разре-

шающая.

Для перехода к следующей симплексной таблице (следующему опорному плану с меньшим значением целевой функции) делается шаг модифицированного жорданова исключения с разрешающим элементом arl .

88

Если в разрешающем столбце нет положительных коэффициентов, то целевая функция не ограничена снизу (при максимизации – не ограничена сверху).

Шаг модифицированного жорданова исключения над симплексной таблицей:

1)на месте разрешающего элемента ставится 1 и делится на разрешающий элемент;

2)остальные элементы разрешающего столбца меняют знак на противоположный и делятся на разрешающий элемент;

3)остальные элементы разрешающей строки делятся на разрешающий элемент;

4)все остальные элементы симплексной таблицы вычисляются по следующей формуле:

a

aij arl

arj ail

a

arj ail .

ij

arl

ij

arl

x4

x5

1

x1 =

1

–2

1

Разрешающий элемент, соответст-

x2 =

–2

1

2

вующий замене базисной переменной

x3 =

3

1

3

x2

на небазисную переменную x5

Q x

=

–1

1

0

x4

x2

1

x1 =

–3

2

5

Разрешающий элемент, соответст-

x5 =

–2

1

2

вующий замене базисной переменной

x3 =

5

–1

1

x3

на небазисную переменную x4

Q x

=

1

–1

–2

		x3	x2	1
x1	=	3/5	7/5	28/5
x5 =		2/5	3/5	12/5
x4	=	1/5	–1/5	1/5
Q x =		–1/5	–4/5	–11/5

Все коэффициенты в строке целевой функции отрицательны, т. е. мы нашли оптимальное решение

89