7. СИМПЛЕКС МЕТОД ИЛИ МЕТОД ПОСЛЕДОВАТЕЛЬНОГО УТОЧНЕНИЯ ОЦЕНОК

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

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

Q(x)= c1 x1 + c2 x2 +... + cn xn → min ,

с системой ограничений следующего вида:

a x + a x +... + a

x =b ,

11

1

12

2

1n

n

1

..................................................

a

m1

x

+ a

m2

x

+... + a

x

= b .

1

2

mn

n

m

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

x

= a'

x

+... + a'

x

+b'

,

1

1,m+1

m+1

1,n

n

1

(7.3)

....................................................

x

= a'

x

+... + a'

x

+b' .

m

m,m+1

m+1

m,n

n

m

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

x1,..., xm

назовем

базисными

переменными. Остальные переменные задачи –

небазисные.

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

Q(x)= cm' +1 xm+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 (опорный план).

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

74

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

Q(x)= x 4 −x5 → min ,

x1 + x2 − x3 +

x4 − 2x5 =1, 2x4 + x5 = 2, 3x4 + x5 = 3.

Выберем в качестве базисных следующие переменные {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 − x	+ 2x ,
		2	4
x1 = 5 − 2x2 +3x4				,
x		=1+ x −5x ,
3		2	4

Q(x)= −2 − x4 + x2 → min .

Соответствующий опорный план x2 =[5 0 1 0 2]Τ и Q(x2 )= −2.

Целевую функцию можно уменьшить за счет увеличения x4 . Увеличение x4 приводит к уменьшению только x3 . Поэтому вводим в базис переменную x4 , а x3 исключаем из базиса. В результате получим следующие выражения для новой системы базисных переменных и целевой функции:

75

x	= 1 + 1 x							− 1 x				,
4			5	2		2			5		3
			28		7					3
x1	=			−		x2			−		x3			,
			5		5					5
x = 12				−	3 x −					2 x			,
5			5		5			2		3		3
Q(			)= −		11		+		4 x2 +						1 x3 → min .
		x
					5				5						5

			3		28		1	12	Τ
	Соответствующий опорный план x					0 0
				=	5		5	5		и значение це-

левой функции Q(x3 )= −115 . Так как все коэффициенты при небазисных переменных в целевой функции неотрицательны, то нельзя уменьшить целевую

функцию за счет увеличения x						или	x , следовательно, полученный план		3 яв-
								x
					2		3
ляется оптимальным.
Пример 2. Пусть имеем задачу
Q(				)= −x1 − x2 → min ,
			x
	x3 =1+ x1 − x2,
	x4 = 2 − x1 + 2x2				,
	x ≥ 0.

Переменные {x3, x4} – базисные, а					{x1, x2}	– небазисные переменные.
Опорный план		0 =[0 0 1 2]Τ , Q(		0 )= 0 .
	x		x
Теперь вводим в базис переменную					x1, а x4	исключаем из базиса. В ре-

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

x1 = 2 + 2x2 − x4, x3 = 3 + x2 − x4 ,

Q(x)= −2 −3x2 + x4 .

Опорный план x1 =[2 0 3 0]Τ , значение целевой функции Q(x1 )= −2 .

76

Теперь можно заметить, что при увеличении x2 значения переменных x1 и x3 также возрастают, то есть при x2 → ∞ в допустимой области Q(x)→ −∞ (задача не имеет решения).

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

7.1. Алгоритм симплекс метода

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

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

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

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

Q(x)= x4 − x5 → min ,

x1 + x4 − 2x5 =1, x2 − 2x4 + x5 = 2, x3 +3x4 + x5 = 3,

x ≥ 0 .

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

					−x4	−x5		1
	x1		=		1	–2		1
	x2		=		–2	1		2
	x3		=		3	1		3
	Q(			)=	–1	1		0
		x
Она уже соответствует опорному						плану				1 =[1 2 3 0 0]Τ (столбец
									x

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

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

ложительных коэффициентов в строке Q(x).

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

77

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

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

	br	= min		bi		a	≥ 0	,
	a			a		il
	rl			il

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

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

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

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

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 на небазисную переменную x5 .

x2	–2	1	2
x3	3	1	3
Q(x)	–1	1	0

78

−x4

−x2

1

x1

–3

2

5

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

x5

–2

1

2

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

x3

5

–1

1

x3

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

Q(

)

1

–1

–2

x

−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(

)

-1/5

-4/5

-11/5

x

Построение опорного плана.

Пусть необходимо решить задачу:

Q(x)= c1 x1 + c2 x2 +... + cn xn → min(max),

a	x		+...........		+ a	x	= b ,
1,1		1			1,n	n	1
................................................
am,1 x1 +				..........	+ am,n xn = bm ,
a		x		+... + a		x	≤b	,
m+1,1			1		m+1,n	n	m+1
.................................................
				+	+ am+p,n xn ≤ bm+p.
am+p,1 x1

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

0 = b1 − a1,1 x1 −..................				− a1,n xn ,
..........................................................
0 = bm − am,1 x1 −...............				− am,n xn ,
x	= b	− a	x	−... − a	x ,
n+1	m+1	m+1,1	1	m+1,n	n

..........................................................
	x1	− − am+p,n xn ,
xn+p = bm+p − am+p,1

где xn+i ≥ 0 , i =1,..., p .

79

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

			−x1	−x2	….	−xS	.…	−xn	1
0			a1,1	a1,2	….	a1,S	….	a1,n	b1
….			….	.…	….	.…	.…	.…	.…
0			am,1	am,2	….	am,S	….	am,n	bm
xm+1			am+1,1	am+1,2	….	am+1,s	….	am+1,n	bm+1
….			….	….	….	….	….	….	…
xm+p			am+p,1	am+p,2	….	am+p,S	….	am+p,n	bm+p
Q(		)	−c1	−c2	….	−cS	….	−cn	0
	x

Правила выбора разрешающего элемента при поиске опорного плана

1. При условии отсутствия “0-строк” (ограничений-равенств) и “свободных” переменных (т.е. переменных, на которые не наложено требование неотрицательности).

•Если в столбце свободных членов симплексной таблицы нет отрицательных элементов, то опорный план найден.

•Есть отрицательные элементы в столбце свободных членов, например bi < 0 . В такой строке ищем отрицательный коэффициент ail , и этим самым

определяем разрешающий столбец l . Если не найдем отрицательный ail , то си-

стема ограничений несовместна (противоречива).

•В качестве разрешающей выбираем строку, которой соответствует

	b						b
			b
минимальное отношение:	r	= min		i			i	> 0	, где	r	– номер разрешающей
	arl						ail
		i	ail

строки. Таким образом, arl – разрешающий элемент.

• После того, как разрешающий элемент найден, делаем шаг модифицированного жорданова исключения с направляющим элементом arl и перехо-

дим к следующей симплексной таблице.

2. В случае присутствия ограничений-равенств и “свободных” переменных поступают следующим образом.

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

80