Характеристика симплекс-метода

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

В последовательности преобразований модели выделяют этапы. Результатом этапа является такая форма записи модели, с которой непосредственно связан один из допустимых планов задачи – так называемый текущий опорный план. Текущий опорный план геометрически представляет собой одну из вершин многогранной области допустимых планов. Движению по этапам симплекс-метода соответствует переход от одного текущего опорного плана к другому, от одной вершины области к соседней. При каждом таком переходе значение целевой функции улучшается (во всяком случае, не ухудшается). Цепочка преобразований последовательно приближает нас к оптимальному плану. Мы приходим либо к ситуации, когда текущим опорным планом становится оптимальный план, оптимальная вершина области допустимых планов, либо к ситуации, когда по четко сформулированным признакам мы непосредственно убеждаемся в неразрешимости задачи.

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

Симплекс-метод – это универсальный алгоритм, кот может решать любую ЗЛП.

Общая схема:

1. Необходимо привести задачу к канонической форме.

Симплексная таблица для такой задачи – это таблица, заполненная следующим образом:

В столбце № указан порядковый номер строки, в столбце
– базисные переменные, по одной для каждой строки. Базисные переменные это переменные, которые входят в базисный набор, а базисный набор – это такой набор переменных, где в каждом ограничении присутствует ровно одна из набора и каждая переменная из набора присутствует ровно в одном ограничении, причем с коэффициентом 1. В столбце
- представлены коэффициенты, с которыми базисные переменные входят в целевую функцию. Дальнейшая часть таблицы, кроме критериальной строки, заполнена той числовой информацией, которая непосредственно представлена в математической модели. Элементы критериальной m+1 строки вычисляются по следующим формулам:

.

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

Текущее значение целевой функции равно d. Для выяснения вопроса об оптимальности текущего опорного плана следует рассмотреть величины , находящиеся в критериальной строке. Если , то текущий опорный план яв-ся оптимальным планом, а текущее значение ЦФ яв-ся оптимумом и задача решена. Если среди величин сущ-ет хотя бы одна отрицательная, то задача не решена и необходимо рассмотреть алгоритм преобразования. Необходимо изменить содержание таблицы. Новое содержание будет соответствовать новому набору базисных переменных, новому текущему опорному плану, а тем самым и новому значению целевой функции. Среди базисных переменных изменится одна переменная, она выйдет из набора, и на ее место войдет небазисная. Геометрический смысл: переход от одной вершины многогранной ОДП к другой, соседней вершине. Значение ЦФ стало больше или не меньше. Преобразование осущ-ся методом Гаусса. Выбираем одну отрицательную . Соответствующему столбцу таблицы, то есть столбцу коэффициентов при переменной xq, присваивается название разрешающего столбца. Среди элементов aiq разрешающего столбца следует определить разрешающий элемент среди положительных: .

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

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