Симплекс-метод решения задачи линейного программирования

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

Само слово «симплекс» определяется как многогранник, выпуклая оболочка аффинно независимых точек n-мерного пространства [16]. Давая геометрическую интерпретацию решения задачи ЛП, Дж. Б. Данциг обнаружил, что множество допустимых решений – многогранник. Название «симплекс-метод» указывает на связь, подмеченную Данцигом, теории многогранников с решением задачи линейного программирования.