Симплексный метод (СМ), основные принципы, алгоритм

Общая идея СМ-а

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

Но с практической точки зрения все не так просто:

1) угловых точек может быть очень много,

2) нахождение координат всех угловых точек также достаточно трудоемко.

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

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

Таким образом, идеи СМ-а предполагают:

1) уметь находить одну угловую точку,

2) уметь останавливаться,

3) уметь переходить к нехудшей угловой точке.

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

Таким образом, любую задачу ЛП можно привести к предпочтительному виду. Предположим, что это есть следующий вид:

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

Запишем исходную задачу с введенными выше обозначениями в виде специальной таблицы, называемой симплекс-таблицей:

БП		В		…			…
	…
				…
…	…	…	…	…	…
				…
				…

Признак оптимальности допустимого базисного решения:

Если для некоторого допустимого базисного решения все оценки , то оно доставляет максимум (минимум) целевой функции .

Переход к нехудшему допустимому базисному решению

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

Преобразование симплекс-таблицы

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

1) элементы разрешающей строки в новой симплекс-таблице делится на разрешающий элемент

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

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

Признак альтернативного решения

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

Признак неограниченности целевой функции

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

Симплекс-метод конечен, если задача невырожденная, т.е. все базисные переменные >0.

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