Достаточное условие оптимальности базисного решения задачи ЛП, основанное на характеристике «симплекс-таблицы».

Рассмотрим алгоритм решения задач симплексным методом. 1. Задача ЛП должна бать приведена к каноническому виду. Преобразовать все ограничения равенства к виду, при котором правая часть ограничений – неотрицательное число. 2. Выписать матрицу ограничений, проверить, есть ли набор столбцов, образующих единичную матрицу. Если такого набора нет – переходим к пункту 5. 3. Набор есть – разбить переменные на 2 группы – базисные и не базисные. Базисные соответствуют столбцам, образующим ед.матрицу, остальные – не базисные. Полагая всякую не базисную переменную = 0, а базисную = правой части ограничений, в которых эта переменная присутствует, получаем опорное решение. 4. Построить симплекс таблицу, отвечающую полученному опорному решению. Все строки таблицы 1-го шага, за исключением строки оценок ∆j (индексная строка), заполняем по данным системы ограничений и ЦФ. 5. Сделать вывод для построения начальной симплекс-таблицы, применить метод искусственного базиса. Пусть дана задача ЛП: Прибавляем дополнительную переменную для приведения к каноническому виду:
Выписываем матрицу ограничений: Построение первоначальной симплекс-таблицы:

Индексная строка ∆j для переменных находится по формуле: ; При этом возможны следующие случаи решения задачи на максимум: • если все оценки (для задачи на max), то найденное решение оптимальное; • если хотя бы одна оценка но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как F(x)→∞, т. е. ЦФ не ограничена в ОДР; • если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению; • если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка. Пусть одна или наибольшая по абсолютной величине оценка , тогда k-й столбец - разрешающий. За разрешающую строку принимаем ту, которой соответствует минимальное отношение свободных членов к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении разрешающих строки и столбца, называют разрешающим элементом. 6. Заполнить симплексную таблицу 2-го шага: меняем местами базисную и небазисную переменные, разрешающий элемент заменяем на обратный, элементы разрешающей строки делим на разрешающий элемент, все элементы разрешающего столбца делим на разрешающий элемент и записываем с обратным знаком. Остальные элементы рассчитываем по правилу прямоугольника. Опорное решение проверяем на оптимальность и т.д.
Индексная строка ∆j для переменных находится по формуле: ; При этом возможны следующие случаи решения задачи на максимум: • если все оценки (для задачи на max), то найденное решение оптимальное; • если хотя бы одна оценка но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как F(x)→∞, т. е. ЦФ не ограничена в ОДР; • если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению; • если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка. Пусть одна или наибольшая по абсолютной величине оценка , тогда k-й столбец - разрешающий. За разрешающую строку принимаем ту, которой соответствует минимальное отношение свободных членов к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении разрешающих строки и столбца, называют разрешающим элементом. 6. Заполнить симплексную таблицу 2-го шага: меняем местами базисную и небазисную переменные, разрешающий элемент заменяем на обратный, элементы разрешающей строки делим на разрешающий элемент, все элементы разрешающего столбца делим на разрешающий элемент и записываем с обратным знаком. Остальные элементы рассчитываем по правилу прямоугольника. Опорное решение проверяем на оптимальность и т.д.