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

Решение задач линейного программирования симплексным методом предполагает следующие этапы:

1)     привести задачу к каноническому виду;

2)     найти неотрицательное базисное решение системы ограничений;

3)     найти оценки свободных переменных по формуле

и записать полученные оценки в симплексную таблицу;

проверить найденное опорное решение на оптимальность: если требуется найти максимум целевой функции, то:

а) если все оценки D_j ³ 0 , то найденное решение оптимально и задача решена;

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

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

4)     если выполняется случай в), то нужно перейти к следующему опорному решению;

5)     перейти к п. 3.