Численные методы решения задач линейного программирования. Прямой симплекс-метод. Базис и базисное решение.

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

Любой набор из m линейно независимых столбцов называется базисом, как и матрица B = [ ], составленная из этих столбцов.

Базисное решение называется невырожденным, если у него ровно m ненулевых компонент. В противном случае базисное решение называется вырожденным.

Базисным допустимым решением (б.д.р.) называется любой элемент множества Q = {x | Ax = b, x ≥0}, являющийся базисным решением системы Ax = b.

Не нашли, что искали? Воспользуйтесь поиском: