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

1. Заполняем симплекс таблицу по данным задачи в каноническом виде.

2. Если выполнено условие оптимальности, то базисный план задачи оптимален.

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

4. Выбираем направляющий столбец по S по наименьшему или наибольшему по модулю положительному (отрицательному) элементу строки оценок для задачи минимизации (максимизации).

5. Составляем отношения положительных элементов столбца свободных членов b к соответствующим положительным элементам направляющего столбца. Среди них выбираем наименьшее, т.е. если ; j=s, то r – направляющая строка, и элемент a_rs - это генеральный или ключевой элемент на данном шаге.

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

1. Элементы направляющей строки умножаются на 1/a_rs

2. Все остальные элементы пересчитываются по правилу прямоугольника

7. Возвращаемся к пункту 2.

Теоремы.

1. Если все оценки некоторого базиса опорного решения задачи минимизации (максимизации) являются неположительными (неотрицательными), то это опорное решение является оптимальным, причем С_о=min f (С_о=max f) (признак оптимальности).

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