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

Основной принцип метода: вычисления начинаются с «стартового» базисного решения, а затем ведётся поиск решений, «улучшающих» значение целевой функции. 1 Это возможно только в том случае, если возрастание какой-то переменной приведёт к увеличению значения функционала. 1

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

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

Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами. 1 В первой строке указывают «наименование» всех переменных. 1 В первом столбце указывают номера базисных переменных, а в последней ячейке — букву Z (это строка функционала). 1 В «середине таблицы» указывают коэффициенты матрицы ограничений. 1 Последний столбец — вектор правых частей соответствующих уравнений системы ограничений. 1 Крайняя правая ячейка — значение целевой функции. 1

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