Новые калькуляторы

Симплексный метод решения ЗЛП

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

Назначение сервиса. Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:

Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel.

Количество переменных
Количество строк (количество ограничений)

При этом ограничения типа xi ≥ 0 не учитывайте. Если в задании для некоторых xi отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом. При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода.

Алгоритм симплекс-метода включает следующие этапы:

  1. Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
  2. Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
  3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
  4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.
Пример симплексной таблицы
Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения (F(x) → min, см. пример решения минимизации функции) и максимального значения ((F(x) → max, см. пример решения максимизации функции)