Особые случаи при решении задач симплекс-методом

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

Схема решения задач линейного программирования

Завершая рассмотрение метода решения задач линейного программирования, опишем алгоритм симплекс-метода в самых общих чертах.

1. Модель линейного программирования записывают в канонической форме.

2. Выбирают опорный план.

3. Строят исходную симплекс-таблицу.

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

5. Выбирают разрешающую строку.

6. Пересчитывают симплексную таблицу.

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

1. Если в результате решения задачи линейного программирования получена симплекс-таблица, в которой выполнился критерий оптимальности, то получен оптимальный план. Признаком существования альтернативного оптимального решения является наличие нулевых элементов в «М+1»-й строке в небазисных столбцах.

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

3. Признаком несовместноcти системы ограничений (область допустимых планов пуста) является наличие ненулевых элементов в строке «М+2» после выхода из базиса искусственных переменных.

Дата добавления: 2014-11-18