2.3 Симплексный метод

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

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

а) строится начальное решение;

6) проводится оценка найденного решения по соответствующему критерию оптимальности;

в) если условие оптимальности не выполняется, переходят к новому решению.

Этапы б) и в) выполняются до тех пор, пока будет получено оптимальное решение.

Все правила проиллюстрируем на примере:

Найти , при ограничениях

I этап. Построение начального решения.

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

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

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

3. Если среди ограничений есть неравенства, то, вводя дополнительные переменные, преобразуют их в уравнения. В нашем случае:

Получили канонический вид задачи.

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

,

где – основные переменные;

–дополнительные переменные;

–искусственные переменные.

Все переменные – неотрицательны.

в) Выписывают векторы коэффициентов при неизвестных и вектор свободных членов.

г) строят первую симплексную таблицу следующего вида:

Таблица 1

Базис			2	- 1	0	0	0			С.О.
		4	1	2	-1	0	0	1	0	4
		5	5	1	0	-1	0	0	1	1
	0	3	-1	1	0	0	1	0	0	-
-строка		0	-2	1	0	0	0	0	0
-строка		9	6	3	-1	-1	0	0	0

Заполняют таблицу по правилам:

1. Вносят все векторы .

2. В самую верхнюю строку записывают коэффициенты целевой функции при соответствующих неизвестных.

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

4. В столбец переносят из верхней строки числа, соответствующие базисным векторам.

5. Чтобы получить элементы двух последних строк, вектор умножают последовательно на векторы , ,…, и от результата вычитают соответствующее число из верхней строки

В -строку записывают коэффициенты при , в -строку – коэффициенты без .

д) После того, как составлена симплекс-таблица, можно записать решение. Оно всегда содержится в столбце и соответствует переменным с номерами базисных векторов. Неизвестные, векторы которых не входят в базис, равны нулю. В данном случае имеем:

.

ІІ этап. Проверка оптимальности решения

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

Следуя данному критерию, можем заключить, что полученное из таблицы 1 решение не является оптимальным: в -строке есть 2 положительных числа – это 6 и 3.

б) В случае, когда критерий оптимальности не выполняется, выбирают ключевой столбец – по наибольшему положительному числу в -строке (а затем в -строке), начиная со второго. Ключевой столбец показывает, какой вектор войдет в новый базис. В таблице 1 – наибольшее число в -строке (начиная со второго) равно 6, в новый базис войдет .

в) Определяют симплексные отношения, для этого элементы делят на положительные элементы ключевого столбца (на отрицательные и нули не делят). В таблице 1 симплексные отношения равны 4 и 1, в третьей строке ставят прочерк, т.к. на (– 1) не делят.

г) Ключевую строку выбирают по наименьшему симплексному отношению (С.О.), она показывает, какой вектор выйдет из базиса. Наименьшее симплексное отношение равно 1, ключевой будет вторая строка, из базиса уйдет искусственный вектор .

д) Элемент, стоящий на пересечении ключевой строки и ключевого столбца, называется генеральным. В построенной таблице генеральный элемент равен 5.

III этап. Построение нового решения (таблицы 2).

а) Формируют новый базис, заменяя вектор на вектор . В данной задаче новый базис будет состоять из векторов , , . Поскольку из базиса вышел искусственный вектор , то соответствующий ему столбец следует отбросить. Когда из базиса уходит последний искусственный вектор, то отбрасывают и -строку.

б) Столбец заполняют по правилу, изложенному выше – из верхней строки.

Таблица 2

Базис			2	- 1	0	0	0		С.О.
		3	0	9/5	-1	1/5	0	1	5/3
	2	1	1	1/5	0	-1/5	0	0	5
	0	4	0	6/5	0	-1/5	1	0	10/3
-строка		2	0	7/5	0	-2/5	0	0
-строка		3	0	9/5	-1	1/5	0	0

в) Вычисления ведут по таким правилам.

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

2. Ключевой столбец дополняют нулями.

3. Если в ключевой строке есть нули, то соответствующие им столбцы переносят без изменения – это .

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

–генеральный элемент, – новый элемент, – старый элемент, – элемент ключевой строки, – элемент ключевого столбца.

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

Например, для столбца имеем:

Для столбца получим:

Решение, соответствующее ІІ-й таблице, берем из , оно имеет вид:

.

Для анализа второго решения повторяют все действия, начиная со II этапа. Проверка показала, что во II таблице условие оптимальности не выполняется: есть два положительных числа – это 9/5 и 1/5. Берут наибольшее и выделяют ключевой столбец , находят симплексные отношения и выбирают ключевою строку (первая), генеральный элемент равен 9/5. Все вычисления приводят к таблице 3. Из базиса уходит последний искусственный вектор , поэтому таблица 3 не будет содержать столбец и -строку.

Таблица 3

Базис			2	- 1	0	0	0	С.О.
	-1	5/3	0	1	-5/9	1/9	0	-
	2	2/3	1	0	1/9	-2/9	0	6
	0	2	0	0	2/3	-1/3	1	3
-строка		-1/3	0	0	7/9	-5/9	0

Решение в соответствии с таблицей 3 имеет вид:

.

Данное решение оптимальным не является – проверку ведем по -строке, в ней содержится положительное число 7/9. Строим еще одну таблицу.

Таблица 4

Базис			2	- 1	0	0	0
	-1	10/3	0	1	0	-1/6	5/6
	2	1/3	1	0	0	-1/6	-1/6
	0	3	0	0	1	-1/2	3/2
-строка		-8/3	0	0	0	-1/6	-7/6

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

.

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

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

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