Simplex_a4

§ 6. Симплекс-метод

21

2) В этой системе сделаем следующие преобразования: при помощи метода Гаусса выделим единичную матрицу в базисных столбцах, а затем исключим базисные переменные из уравнения, содержащего z.

В результате получится система вида
	z → min,
x1 + 0 + : : : + 0 + 1;m+1xm+1 + : : : + 1nxn = 1;
		x2 + : : : + 0 + 2;m+1xm+1 + : : : + 2nxn = 2;
			. . . . . . . . . . . . . .	(3)
			xm + m;m+1xm+1 + : : : + mnxn = m;
			z + m+1xm+1 + : : : + nxn = ;
xi		>	0; i = 1; : : : ; n.
Из этой системы следует, что

x0 = ( 1; : : : ; m; 0; : : : ; 0);

где все i > 0 и z(x0) = .

3) Предположим, что i 6 0 при всех i = m + 1, . . . , n. Тогда из последнего уравнения системы (3) следует, что значение функции z невозможно уменьшить, не нарушая условий xi > 0. В данном случае минимальное значение функции z уже найдено; при этом zmin = , и

точкой минимума является x0.	{m + 1; : : : ; n},
Предположим теперь, что есть такой номер j0
при котором j0 > 0. Рассмотрим тогда семейство точек
x(t) = (x1(t); : : : ; xm(t); 0; : : : ; 0; t; 0; : : : ; 0);	t > 0;

где параметр t стоит на месте j0, а xi(t) находятся из системы (3):

xi(t) = i − ij0 t; i = 1; : : : ; m:

Очевидно, xi(t) > 0 при всех достаточно малых t, и, следовательно, x(t) Ω. Значение целевой функции в этой точке будет равно

z(x(t)) = − j0 t < z(x0) при t > 0:

Чем больше параметр t, тем меньше значение функции в точке x(t).

22	ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Если ij0 6 0 при всех i = 1, . . . , m, то xi(t) > 0 для любого t > 0. В этом случае целевая функция не ограничена снизу на множестве Ω,

и исходная задача не имеет решения (минимума у целевой функции на множестве Ω нет).

Если найдутся ij0 > 0 при некоторых i {1; : : : ; m}, то мы можем увеличивать t только до тех пор, пока выполняются условия

xi(t) = i − ij0 t > 0; i = 1; : : : ; m;

то есть вплоть до значения

	min	i	};
t0 =	ij0 >0{ ij0

где минимум берется по всем i {1; : : : ; m}, для которых ij0 > 0. Из невырожденности задачи вытекает, что этот минимум достигается лишь при единственном значении индекса i = i0. При этом, очевидно, xi0 (t0) = 0. Отсюда вытекает, что точка x(t0) имеет ровно m = rank A положительных координат, и, значит, она является крайней точкой множества Ω.

По построению значение целевой функции в новой крайней точке x(t0) стого меньше, чем в точке x0, а координаты x(t0) удовлетворяют равенствам xi0 (t0) = 0 и xj0 (t0) = t0. Значит, базисными переменными для новой крайней точки будут все базисные переменные точки x0, кроме xi0 , и еще одна переменная xj0 .

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

4) Повторяем шаг 2) и шаг 3) до тех пор, пока не найдем точку минимума вместе с минимальным значением целевой функции, либо пока не обнаружим, что целевая функция неограничена снизу на Ω.

Сформулируем теперь алгоритм решения ЗЛП симплекс-методом при помощи таблиц. Вначале необходимо привести задачу к каноническому виду (1) и переписать ее в виде (2).

§ 6. Симплекс-метод

23

1) По исходной системе (2) составляем таблицу, которая называется нулевой симплекс-таблицей:

xb	x1	x2	: : :	xm	xm+1	: : :	xn	b
x1	a11	a12	: : :	a1m	a1;m+1	: : :	a1n	b1
x2	a21	a22	: : :	a2m	a2;m+1	: : :	a2n	b2
.	. .	. . . . . . . . . . . . . . . .
xm	am1	am2	: : :	amm	am;m+1	: : :	amn	bm
z	−c1	−c2	: : :	−cm	−cm+1	: : :	−cn	0

В ней столбец xb содержит базисные переменные начального опорного плана, а последняя строка называется z-строкой.

2) Применяя метод Гаусса, приводим часть матрицы, отвечающую базисным переменным, к единичной, и выражаем целевую функцию через свободные переменные. Полученная таблица называется первой симплекс-таблицей:

xb	x1	x2	: : :	xm	xm+1	: : :	xn	b
x1	1	0	: : :	0	1;m+1	: : :	1n	1
x2	0	1	: : :	0	2;m+1	: : :	2n	2

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

xm	0	0	: : :	1	m;m+1	: : :	mn	m
z	0	0	: : :	0	m+1	: : :	n

3) Если i 6 0 для всех i = m + 1, . . . , n, то минимальное значение функции z равно и достигается в точке x0 = ( 1; : : : ; m; 0; : : : ; 0).

Предположим, что существует j0 > 0. Тогда выбираем столбец, содержащий это j0 (разрешающий столбец). Если сразу несколько коэффициентов j положительны, то можно выбрать любой из них (например, максимальный). После этого смотрим на коэффициентыij0 в разрешающем столбце.

Если ij0 6 0 для всех i = 1, . . . , m, то ЗЛП не имеет решения, так как целевая функция в этом случае не ограничена снизу на Ω.

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

24	ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

{ }

i

t0 = min

ij0 >0 ij0

В силу невырожденности задачи этот минимум достигается на единственном номере i = i0. Тогда переменная xi0 будет исключаться из базисных. Элемент i0j0 > 0 называется разрешающим элементом, а строка таблицы, в которой стоит разрешающий элемент, называется

разрешающей строкой.

Строим новую симплекс-таблицу. Вместо базисной переменной xi0 в столбце xb записываем новую базисную переменную xj0 . Всю разрешающую строку делим на разрешающий элемент, и тем самым делаем коэффициент i0j0 равным единице. Затем при помощи элементарных преобразований строк делаем нулевыми все элементы разрешающего столбца, кроме i0j0 . В итоге получается примерно такая табличка:

xb

x1

: : :

xi0−1

xi0

xi0+1

: : :

xm

: : :

xj0

: : :

xn

b

x1

1

: : :

0

1′ ;i0

0

: : :

0

: : :

0

: : :

1′ ;n

1′

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

x

0

: : :

1

′

0

: : :

0

: : :

0

: : :

′

1;n

′

1

i0−1

i0 1;i0

i0

−

i0

−

−

xj0

0

: : :

0

i′0;i0

0

: : :

0

: : :

1

: : :

i′0;n

i′0

xi0+1

0

: : :

0

i′0+1;i0

1

: : :

0

: : :

0

: : :

i′0+1;n

i′0+1

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

xm	0	: : :	0	m;i′	0	0	: : :	1	: : :	0	: : :	m;n′	m′
z	0	: : :	0	i′0		0	: : :	0	: : :	0	: : :	n′	′

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

Замечание 6.1. При помощи симплекс-метода также можно решать задачи, в которых целевая функция исследуется на максимум. Во-первых, можно свести задачу на максимум к задаче на минимум, просто изменив знак целевой функции. Однако на практике можно этого и не делать, так как алгоритм симплекс-метода для задачи на

§ 6. Симплекс-метод

25

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

Образно говоря, при решении задач на минимум мы «боремся» с положительными коэффициентами в z-строке, а при решении задач на максимум — с отрицательными.

Проиллюстрируем работу симплекс-метода на примерах.

Пример 6.2. Решить задачу

z = −3x1 − 2x2 → min;
	1	2 6
		+ 3x2 6 12;
4x1
4x		+ x 8;
		− x2 6 9;
4x1
	; x2 > 0:
x1

Решение. Приведем задачу к каноническому виду:

z = −3x1 − 2x2 → min;
4x1 + 3x2 + x3 = 12;
4x	1	+ x	2	+ x	4	= 8;
4x1		x2 + x5 = 9;
xi >−0;				i = 1; : : : ; 5:

Очевидно, точка x0 = (0; 0; 12; 8; 9) является начальным опорным планом. Выбираем базис из переменных x3, x4, x5 и строим нулевую симплекс-таблицу:

xb	x1	x2	x3	x4	x5	b
x3	4	3	1	0	0	12
x4	4	1	0	1	0	8
x5	4	−1	0	0	1	9
z	3	2	0	0	0	0

26 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

потому что
min {	12	;	8		;	9		} =	8		= 2:
	4		4			4			4

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

xb	x1	x2	x3	x4	x5	b
x3	0	2	1	−1	0	4
x1	1	1=4	0	1=4	0	2
x5	0	−2	0	−1	1	1
z	0	5=4	0	−3=4	0	−6

Новой крайней точкой будет точка x′0 = (2; 0; 4; 0; 1) (напомним, что значения базисных координат записаны в b-столбце, а прочие координаты равны нулю). Значение целевой функции в этой точке равно −6 (оно записано на пересечении z-строки и столбца b).

Поскольку в z-строке имеется положительный элемент, минимум в точке x′0 не достигается. Разрешающим столбцом будет столбец x2, а разрешающим элементом — элемент, стоящий в строке x3, потому что

{}

			min			4	;	2		=	4	= 2:
					2						2
							1=4
Строим новую симплекс-таблицу:
	xb	x1		x2			x3			x4			x5	b
	x2	0		1		1=2			−1=2				0	2
	x1	1		0	−1=8				3=8				0	3=2
	x5	0		0			1			−2			1	5
	z	0		0	−5=8				−1=8				0	−17=2

§ 6. Симплекс-метод

27

Новым опорным планом будет x′′0 = (3=2; 2; 0; 0; 5), а значение целевой функции в этой точке равно −17=2. Так как все элементы z-строки неположительны, минимум целевой функции достигнут, и найденный опорный план является решением канонической задачи. Отбрасывая лишние координаты x3, x4, x5 (которых не было в исходной задаче), получаем

Ответ: zmin = −17=2 в точке (3=2; 2).

Упражнение. Решите данную задачу графически.

Пример 6.3. Решить задачу

	z = 2x1 + x2 − 3x3 + 5x4 → max;
		1 2 3		4 6
		−
		+ 7x2 + 3x3 + 7x4 6 47;
x1
3x			x + x + 2x	8;
	2x1 + 3x2 − x3 + x4 6 10;
		> 0; i = 1; : : : ; 4:
xi

Решение. Приведем задачу к каноническому виду:

	z = 2x1 + x2 − 3x3 + 5x4 → max;
		−
		+ 7x2 + 3x3 + 7x4 + x5 = 47;
x1
3x			x + x + 2x + x = 8;
		1 2 3 4 6
	2x1 + 3x2 − x3 + x4 + x7 = 10;
		> 0; i = 1; : : : ; 7:
xi

Для нее начальным опорным планом будет

x0 = (0; 0; 0; 0; 47; 8; 10):

Строим нулевую симплекс-таблицу. Как и в предыдущем примере, она совпадает с первой симплекс-таблицей:

xb	x1	x2	x3	x4	x5	x6	x7	b
x5	1	7	3	7	1	0	0	47
x6	3	−1	1	2	0	1	0	8
x7	2	3	−1	1	0	0	1	10
z	−2	−1	3	5	0	0	0	0

28 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Так как в ее z-строке есть отрицательные элементы, то максимум целевой функции в точке x0 не достигается. Разрешающим столбцом объявим столбец x4. Тогда разрешающий элемент будет в строке x6,

поскольку
min {	47	;	8		;	10		} =	8		= 4:
	7		2			1			2

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

xb	x1	x2	x3	x4	x5	x6	x7	b
x5	−19=2	21=2	−1=2	0	1	−7=2	0	19
x4	3=2	−1=2	1=2	1	0	1=2	0	4
x7	1=2	7=2	−3=2	0	0	−1=2	1	6
z	11=2	7=2	11=2	0	0	5=2	0	20

Новым опорным планом будет точка x′0 = (0; 0; 0; 4; 19; 0; 6), а значение целевой функции в этой точке равняется 20. Разрешающим столбцом будет столбец x2, а разрешающим элементом будет число 7=2, стоящее в строке x7.

Строим следующую симплекс-таблицу:

xb	x1	x2	x3	x4	x5	x6	x7	b
x5	−11	0	4	0	1	−2	−3	1
x4	11=7	0	2=7	1	0	3=7	1=7	34=7
x2	1=7	1	−3=7	0	0	−1=7	2=7	12=7
z	6	0	4	0	0	2	1	26

Очередным опорным планом будет точка x′′0 = (0; 12=7; 0; 34=7; 1; 0; 0), значение целевой функции в ней равно 26.

Так как все элементы z-строки неотрицательны, точка x′′0 является решением канонической задачи, и целевая функция принимает в ней свое максимальное значение zmax = 26. Возвращаясь к исходной задаче, получаем

Ответ: zmax = 26 в точке (0; 12=7; 0; 34=7).

§ 7. Поиск начального опорного плана (w-задача)

29

Задания. Решите симплекс-методом следующие задачи.

10.1.z = x1 + x2 → max;

2x1 + x2 + x3 = 16;

x1 − x2 6 2;

> 0; i = 1; : : : ; 3:

xi

10.3.

z = −3x1 + 12x2 → max;

1

2 >

−

−

+ 4x2 6 16;

x1

x

x

2;

5x

8;

3x

6

x1

1>−0:

2

10.5.

z = 3x1 − x2 → max;

−

2 >

1

3x1 2x2 6 3;

10;

5x

−

4x

−

−

2 6

x1

1> 0:

+ x

5;

2x

10.2.z = −10x1 − x2 → min;

2x1 + 11x2 6 7;

4x − 5x > 5;

1 2

x1; x2 > 0:

10.4.

z =

−

x1 + 3x2

→

min;

3x1

2x2 6 3;

−

5x

1

4x

>

9;

2

−

−

−

2x

+ x

−

5;

x1;1x2 >2 0>:

§ 7. Поиск начального опорного плана методом искусственного базиса (w-задача)

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

	z = c1x1 + c2x2 + : : : + cnxn → extr;
	a11x1 + a12x2 + : : : + a1nxn = b1;
	a21x1 + a22x2 + : : : + a2nxn = b2;
	(4)
. . . . . . . . . . . .

a x + a x + : : : + a x = b ;

m1 1 m2 2 mn n m

xi > 0; i = 1; : : : ; n;

где bi > 0, i = 1, . . . , m.

30 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Ниже дается описание метода искусственного базиса.

Прежде всего следует привести исходную задачу к каноническому виду, в котором все правые части bi неотрицательны. Этого можно добиться при помощи изменения знака у тех уравнений, в которых bi < 0.

Затем к каждому из уравнений задачи (4) добавим новую «искусственную» неотрицательную переменную, а в качестве целевой функции возьмем новую функцию w, равную сумме этих «искусственных»

переменных:
	w = xn+1 + xn+2 : : : + xn+m → min;
a11x1 + a12x2 + : : : + a1nxn + xn+1 = b1;
a21x1 + a22x2 + : : : + a2nxn + xn+2 = b2;
		(5)

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

a x + a x + : : : + a x + x = b ;

m1 1 m2 2 mn n n+m m

xi > 0; i = 1; : : : ; n + m:

Полученная задача называется w-задачей. Для w-задачи сразу виден начальный опорный план: x0 = (0; : : : ; 0; b1; b2; : : : ; bm). Очевидно, что для всех x из области определения w-задачи выполняется неравенство w(x) > 0. Кроме того, если допустимое множество Ω исходной задачи

(4) непусто, то для всех точек x Ω соответствующие искусственные переменные в (5) обращаются в нуль. Значит, на этих точках целевая функция w тоже будет принимать нулевое значение. Таким образом, чтобы получить начальный опорный план для исходной задачи (4), достаточно найти крайнюю точку для w-задачи (5), в которой целевая функция w достигает минимума, равного нулю.

Далее решаем w-задачу симплекс-методом, описанным выше. Если