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

Симплексный метод является универсальным и наиболее распространенным методом решения задач линейного программирования.

Свое название он получил от слова «симплекс», обозначающего выпуклый многогранник (на плоскости – многоугольник), число вершин которого всегда больше размерности задачи линейного программирования. На плоскости (при двух неизвестных в задаче линейного программирования) симплексом является треугольник, в трехмерном пространстве – четырехгранник и т.д.

Симплекс – это фигура (область) стороны которой описаны уравнениями или неравенствами системы ограничений задачи линейного программирования.

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

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

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

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

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)