§ 6. Метод искусственного базиса

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

Решить задачу линейного программирования методом искусственного базиса

f =x1 +2x2 →max ,

2x1 +3x2 ≤18

x1 +x2 ≥3 , x j ≥0 .x1 −2x2 ≥−4

Решение. Приведем задачу к канонической форме. f =x1 +2x2 →max ,

2x +3x		+x	=18
1	2	3	=3 .
x +x	2	−x
1		4	+x5 =−4
−x1 +2x2

Легко увидеть, что матрица ограничений имеет только два единичных столбца. Поэтому первый опорный план, если он существует, может получиться только путем пересчета. Прибавим искусственную переменную y ≥0 в левую часть второго уравнения, а в целе-

вую функцию — слагаемое −My , где M — некоторое достаточно большое положительное число. Тогда задача перепишется в виде

F =x1 +2x2 −My →max ,

— 174 —

2x +3x		+x	=18
1	2	3	+y =3 .
x +x	2	−x
1		4	+x5 =−4
−x1 +2x2

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

Базис

x3

y

x5

F

Базис

x3

y

x2

F

x1

2

1

–1

1

x1

7

2

3

2

1

−2 2

	x2	x3	x4	x5						y	B
3		1	0	0					0		18
1		0	–1	0					1		3
2		0	0	1					0		4
2		0	0	0						−M	0
	x2	x3	x4	x5						y	B
	0	1	0	−		3				0	12
						2
	0	0	–1	−		1				1	1
						2
	1	0	0		1					0	2
				2
	0	0	0	–1						−M	–4

— 175 —

Базис		x1		x2	x3					x4								x5											y									B
x3	0		0		1						7							−			1							−		7							29
								3																											3
																		3									3
x1	1		0		0					−			2					−			1								2									2
																											3								3
								3										3
x2	0		1		0					−				1					1										1									7
																		3									3								3
								3
F	0		0		0						4							−			1						−M −						4			−			16
								3										3									3								3
Базис		x1		x2		x3										x4							x5									y							B
x4		0		0			3									1							−		1						–1							29
						7																			7											7
x1		1		0			2									0							−		3			0										24
						7																			7											7
x2		0		1			1									0								2				0										26
						7														7																7
F		0		0		−		4								0							−		1				−M							−				76
								7																	7											7

Получен оптимальный план fmax = 767 при x1 = 247 , x2 = 267 .

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

•Составление расширенной задачи.

•Нахождение опорного плана расширенной задачи.

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

—176 —

§ 7. Двойственные задачи линейного программирования

Рассмотрим следующую задачу линейного программирования: f =c1x1 +c2 x2 +...+cn xn →max ,

a x +a x +...+a x ≤b
11 1	12	2	1n n	1
a x +a		x	+...+a x ≤b		, x	≥0 , b ≥0 .
21 1	22 2		2n n	2
....................................................					j	i
	+am2 x2 + +amn xn ≤bm
am1x1

Эту задачу можно переписать в матричной форме следующим образом

f =CX →max ,		(1)
AX ≤B , x j ≥0	, bi ≥0 ,	(2)

где C — вектор-строка коэффициентов целевой функции, X — вектор-столбец неизвестных, A — матрица коэффициентов системы ограничений, B — вектор-столбец свободных членов системы ограничений.

Задача линейного программирования вида

F =BT Y →min ,	(3)
AT Y ≥CT , y ≥0 ,	(4)
i

где AT ,CT и BT — транспонированные матрицы A, C и B соот-

ветственно, называется двойственной по отношению к задаче (1),

(2). Вместе эти две задачи в линейном программировании называются двойственной парой.

Пример. Составить двойственную пару для следующей задачи: f =2x1 −3x2 →max ,

— 177 —

2x1 −x2 ≤6

x1 +x2 ≤10 , x j ≥0 .x1 −2x2 ≥−8

Решение. Приведем систему ограничений к виду (2). Имеем

			2x −x ≤6
				1		2
			x +x ≤10 .
			1			2
			−x1 +2x2 ≤8
Транспонируем матрицы исходной системы.
T	2 1	−1		B	T	=(6 10 8), C	T	2
A	=	2	,					= .
	−1 1							−3

Используя полученные матрицы, записываем новую задачу

F =6y1 +10 y2 +8y3 →min ,

2 y +y	−y	≥2	, y ≥0 .
1 2	3
−y1 +y2 +2y3 ≥−3			i

Между задачами двойственной пары имеется определенная связь, заключающаяся в том, что из оптимального плана одной задачи, найденного симплексным методом, легко получается оптимальный план другой. Сформулируем некоторые из известных ре-

зультатов.		X — некоторый план исходной задачи (1)-(2), а Y
1.	Если			—
произвольный план двойственной задачи (3)-(4), то			f ( X ) ≤F(Y ) .
2.	Если	f ( X ) =F(Y ) для некоторых планов	X и Y ,	то

X — оптимальный план исходной задачи, а Y — оптимальный план двойственной задачи.

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

— 178 —