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

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

Описание симплекс-метода решения задачи ЛП дадим в терминах симплексных таблиц. Сначала изложим метод для специальной задачи ЛП, а затем покажем, как каноническую задачу ЛП привести к виду специальной.

Определение 11. Симплексной таблицей специальной задачи ЛП (32) называется таблица вида табл. 3. Строка симплексной таблицы, соответствующая целевой функции , называетсяиндексной.

Определение 12. Симплексная таблица называется допустимой, если все элементы столбца , за исключением быть может, неотрицательны.

Определение 13. Две симплексные таблицы называются эквивалентными, если соответствующие им специальные задачи ЛП эквива- лентны.

Заметим, что вектор является базисным решением задачи (32), причем. Действительно, еслито вектор; если не всеравны нулю, то система векторов-столбцов, соответствующих ненулевым компонентамвектора, линейно независима, как подсистема системы столбцов единичной матрицы. Будем говорить, что базисное решениесоответствует симплексной таблице.

Т а б л и ц а 3

B										
		1		0		0				
…	…	…		…		…	…		…		…
		0		1		0				
…	…	…		…		…	…		…		…
		0		0		1				
f		0		0		0				

Перейдем к изложению симплекс-метода.

Шаг 0 (начальный шаг). Для специальной задачи (32) составляем начальную симплексную таблицу. Соответствующее ей базисное решение назовемтекущим. Переходим к шагу 1.

Шаг 1 (проверка на оптимальность). Если для всех, то конец работы метода текущее базисное решение оптимально. В противном случае переходим к шагу 2.

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

Шаг 3 (выбор ведущего столбца). Столбец, имеющий номер q, назовем ведущим, если идля некоторого. Если таких столбцов несколько, то выбираем любой из них. Переходим к шагу 4.

Шаг 4 (выбор ведущей строки). Строку номер p назовем ведущей, если

. (36)

Если таких строк несколько, то выбираем любую из них. Переходим к шагу 5.

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

(37)

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

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

За м е ч а н и я.

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

2) Правило выбора ведущей строки (36) гарантирует, что решение, соответствующее новой симплексной таблице, является допустимым и базисным.

Следующие три утверждения дают теоретическое обоснование симплекс-метода.

Теорема 4 (условия оптимальности решения). Если для всех, то текущее базисное решение задачи (32) оптимально.

Доказательство. Если для всех, то для любого допустимого решениях задачи (32)

(38)

в силу неотрицательности всех его компонент, поэтому

, (39)

где х  любое допустимое решение, а  текущее базисное решение задачи (32). Следовательно, для любого, т. е. оптимальное решение задачи (32). Теорема доказана.

Теорема 5 (условие неразрешимости задачи). Если существует такой номер q, что и среди элементовq-го столбца нет положительных: то целевая функцияf(x) неограниченно возрастает на множестве D допустимых решений задачи (32).

Д о к а з а т е л ь с т в о. Пусть условие теоремы выполнено: существует такой номер q, что и все.

Рассмотрим вектор

, (40)

у которого q-я компонента равна t, t > 0. Вектор является допустимым решением задачи (32) для любогоt > 0, однако

при , (41)

так как , т. е. функцияf(x) неограниченно возрастает на множестве D. Теорема доказана.

Теорема 6 (о переходе к новому базисному решению). Если существует такой номер q, что идля некоторого, то преобразование симплексной таблицы по формулам (19) приводит к получению допустимого базисного решения, причем, где базисные решения, соответствующие старой и новой таблицам.

Д о к а з а т е л ь с т в о. Ранее нами уже было замечено, что преобразование симплексной таблицы по формулам (37) приводит к допустимому базисному решению . Найдем значение:

, (42)

так как и. Итак, соотношениеустановлено. Теорема доказана.

Пример 8. Решить симплекс-методом задачу об оптимальном распределении ресурсов (см. пример 1).

Построим каноническую задачу ЛП, эквивалентную задаче (4). Для этого введем дополнительные переменные . Получим:

(43)

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

Т а б л и ц а 4

B
	120	2	4	2	1	0	0
	100	1	4	3	0	1	0
	200	3	0	3	0	0	1
f	0	30	50	40	0	0	0

Т а б л и ц а 5

B
	60	1	2	1	0,5	0	0
	40	0	2	2	0,5	1	0
	20	0	6	0	1,5	0	1
f	1800	0	10	10	15	0	0

Т а б л и ц а 6

B
	40	1	1	0	0,75	0,5	0
	20	0	1	1	0,25	0,5	0
	20	0	6	0	1,5	0	1
f	2000	0	20	0	12,5	5	0

Отсюда и, где,.

Итак, оптимальный план ;. Это означает, что для получения максимального дохода в 2000 денежных единиц предприятию следует выпустить 40 партий продукции, 20 пар- тий продукции , а продукциюпроизводить не следует.