метод решения называется симплексным. Теоретической основой симплексного метода являются две теоремы.

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

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

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

Крайняя точка — это вершина многогранника (или многогранной области) допустимых планов (определение нестрогое!). Теорема утверждает, что оптимальный план, если он существует, достигается либо в одной такой точке, либо в выпуклой линейной комбинации нескольких крайних точек. Последнее означает, например, что в случае двух неизвестных оптимальный план может достигаться на ребре многоугольника, т. е. в выпуклой линейной комбинации его концов.

§ 4. Общая задача линейного программирования

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

f =c1x1 +c2 x2 +...+cn xn

при условиях

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

(1)

(2)

— 164 —

a	x	+a	x	+...+a	x	=b
	m+11 1	m+12 2		m+1n n			m+1
a	x	+a	x	+...+a	x		=b	(3)
	m+21 1		m+22 2		m+2n n		m+2 ,
....................................................
ak1x1 +ak 2 x2 +...+akn xn =bk
x j	≥0 ( j =1,2,..., n) ,							(4)

aij , bi , cj — постоянные величины и m≤k .

Функция (1) называется целевой функцией, а условия (2)-(4) — ограничениями данной задачи. Задача линейного программирования называется канонической, если находится максимальное значение функции цели и ограничения (2)-(3) имеют вид равенств.

Упорядоченный набор чисел X =(x1, x2 ,..., xn ), удовлетворяющих ограничениям задачи, называется допустимым планом (решением). План X =(x1 , x2 ,..., xn ), доставляющий максимальное (ми-

нимальное) значение целевой функции, называется оптимальным планом задачи.

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

Пример 1. Привести следующую задачу линейного программирования к канонической форме

F =2x1 −x2 +3x3 →min

x +4x		−x	≥1
1	2	3	≤2 ,
2x	−x	+x
1	2	3

−x1 +x2 +4x3 ≤5

x j ≥0 ( j =1,2,3) .

— 165 —

Решение. Заменим функцию F на f =−F , при этом получается

f=−2x1 +x2 −3x3 →max .

Влевые части второго и третьего неравенств добавим дополнительные неотрицательные переменные, а из левой части первого неравенства отнимем неотрицательную переменную. При этом предполагается, что все ограничения преобразуются в равенства.

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

f =−2x1 +x2 −3x3 +0x4 +0x5 +0x6 →max

x +4x		−x	−x =1
1	2	3	4
2x	−x	+x	+x =2 .
1	2	3	5
−x1 +x2 +4x3 +x6 =5

Дополнительные переменные задачи имеют вполне определенный экономический смысл. Например, если свободные члены системы ограничений отражают запасы сырья, то дополнительные переменные соответствуют объемам неиспользованного сырья.

§ 5. Симплексный метод

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

— 166 —

Для осуществления симплекс-метода нужно:

•уметь находить опорные планы (крайние точки);

•использовать критерий, определяющий искомое направление перехода к следующей крайней точке;

•использовать критерий оптимальности, согласно которому мы будем судить об оптимальности (или не оптимальности) полученного опорного плана.

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

Пример 1. Найти опорный план системы

x1 −2x2 +x3 +2x4 =4x1 +x2 −x3 +x4 =6.

Решение. Мы будем производить тождественные преобразования с расширенной матрицей коэффициентов системы.

	x1	x2	x3	x4	B
	1	–2	1	2	4
	1	1	–1	1	6

Используя преобразование Жордана–Гаусса, приведем матрицу к виду, содержащему два единичных столбца коэффициентов при неизвестных. Соответствующие неизвестные будут называться базисными; их наименования запишем в первый (пока пустой) столбец таблицы. Первый пересчет (с направляющим элементом a11 =1 ) дает:

	x1	x2	x3	x4	B
x1	1	–2	1	2	4
	0	3	–2	–1	2

— 167 —

Теперь направляющий элемент выберем во второй строке и втором столбце, т. е. a22 =3 . Новая матрица имеет вид

	x1	x2	x3				x4						B
x1	1	0	−		1			4				16
								3					3
			3
x2	0	1	−	2			−		1					2
												3
			3				3

Последняя матрица соответствует системе уравнений

	x +0x −			1	x +		4			x =		16
		1	2	3		3	3			4		3
				2				1			2
	0x +x −					x −			x =				,
		1	2	5		3	3			4		3

которая эквивалентна первоначальной. Здесь легко выражаются базисные неизвестные x1 и x2 :

x			=	1		x		−	4		x			+	16
	1			3			3		3			4		3
					2					1						2
x		2	=				x	+				x	4	+			.
				5			3		3					3
Переменные x3 и x4		в данном случае будут свободными; они

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

	16			2
	ние будет опорным планом —		;		;0;0 . Конечно, это не единст-
		3		3

венный опорный план. Если, например, ввести в базис вместо x1 переменную x4 (выбрать в последней матрице направляющим эле-

ментом 34 и пересчитать), то получится другой опорный план.

Матрица после перехода к новому опорному плану примет вид

— 168 —

	x1			x2	x3			x4	B
x1		3		0	−	1		1	4
	4					4
x4		1		1	−	3		0	2
	4					4

Новый опорный план записывается так (4;0;0;2).

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

брать элементы третьего столбца (вводить в базис x3 ). Пример 2. Рассмотреть задачу линейного программирования

f =2x1 +3x2 →max

x1 +2x2 ≤4

3x1 +x2 ≤6 , x j ≥0 .x1 −x2 ≥−1

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

Решение. Изобразим множество допустимых планов задачи геометрически.

Очевидно, что множество допустимых планов является пятиугольником OABCD, т. е. содержит 5 крайних точек. Также оче-

8 6

видно, что оптимальным планом будет точка C ; .

5 5

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

— 169 —

сменив предварительно знаки в третьем неравенстве (при этом свободный член станет положительным). Имеем

x +2x		+x	=4
1	2	3
3x +x		+x =6 .
1	2		4
−x1 +x2		+x5 =1
Легко видеть, что матрица этой
системы	такова,		что переменные
x3 , x4 и x5		уже базисные. Первый

опорный план имеет вид (0;0;4;6;1)

(точка O).

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

ный план. Максимизация целевой функции происходит по направлению вектора нормали опорной прямой, координаты которого

(2k;3k), где k >0 . Можно показать, что если выразить целевую

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

Базис	x1	x2	x3	x4	x5	B
x3	1	2	1	0	0	4
x4	3	1	0	1	0	6
x5	–1	1	0	0	1	1
f	2	3	0	0	0	0

— 170 —

Мы видим, что в индексной строке имеется два положительных числа; они соответствуют неизвестным x1 и x2 . Числа эти показы-

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

план единицы той или другой переменной. Поэтому следует ввести в базис x2 . Направляющим элементом, во-первых, должно быть

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

ром положительного элемента второго столбца из условия min bi . ai2

Такому условию удовлетворяет элемент a32 =1. Пересчитаем матрицу.

Базис	x1	x2	x3	x4	x5	B
x3	3	0	1	0	–2	2
x4	4	0	0	1	–1	5
x2	–1	1	0	0	1	1
f	5	0	0	0	–3	–3

Второй опорный план имеет вид (0;1;2;5;0) (точка A), а значение целевой функции f2 =3 , в чем легко убедиться непосредст-

венной подстановкой. По рисунку видно, вдоль какого ребра пятиугольника начато движение. Индексная строка сигнализирует о неоптимальности полученного опорного плана, т. к. в ней имеется еще одно положительное число 5. Ясно, что в следующий опорный план следует ввести переменную x1 . Если бы сейчас среди коэф-

фициентов ai1 первого столбца не оказалось положительных, это

означало бы, что оптимального плана не существует.

Отметим еще два факта, следующих из анализа индексной строки. Во-первых, элемент –3 из пятого столбца говорит, что если ввести в базис переменную x5 , то значение целевой функции умень-

шится. Действительно, в этом случае мы вернемся к первому

— 171 —

опорному плану. Во-вторых, последнее число индексной строки равно значению целевой функции в данной крайней точке, взятое с противоположным знаком.

Выберем направляющий элемент в первом столбце по условию

min bi >0 (число 3) и перейдем к новому базису. ai1

Базис	x1	x2	x3						x4	x5					B
x1	1	0		1					0	−		2				2
			3												3
										3
x4	0	0	−		4				1		5					7
										3					3
			3
x2	0	1		1					0		1					5
			3							3					3
f	0	0	−		5				0		1				−		19
										3
			3												3

Третий опорный план (точка B) все еще не оптимален. Выбира-

ем направляющий элемент в пятом столбце (число 53 ) и пересчита-

ем матрицу.

Базис	x1	x2	x3						x4					x5	B
x1	1	0	−		1					2				0		8
									5						5
			5
x5	0	0	−		4					3				1		7
									5						5
			5
x2	0	1		3					−		1			0		6
			5												5
									5
f	0	0	−		7				−		1			0	−		34
			5						5						5

— 172 —

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

Ответ. Максимальное значение целевой функции равно 345

при	x =	8	и	x =	6	(указаны только исходные неизвестные
	1	5		2	5

задачи).

Теперь сформулируем алгоритм симплексного метода.

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

2.Найти (методом Жордана–Гаусса) первый опорный план.

3.Составить симплекс-таблицу, введя индексную строку.

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

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

6.Методом Жордана–Гаусса пересчитать матрицу (симплекстаблицу). Перейти к пункту 4.

Замечание. Легко видеть, что путь к оптимальной вершине пятиугольника может быть короче, если от начальной точки двигаться к точке D . Тогда оптимальный план будет достигнут за 2 шага,

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

—173 —