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

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

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

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

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

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

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

Сформулируем симплекс-метод в виде следующей последовательности шагов.

Шаг 0. Построить симплекс-таблицу, соответствующую заданному базисному допустимому решению, таблица будет прямо допустимой.

Шаг 1. Если симплекс-таблица двойственно допустима, то КОНЕЦ (получено оптимальное решение).

Шаг 2. Иначе выбрать ведущий столбец s по правилу:

Шаг 3. Если , то выбрать ведущую строку r по правилу:

иначе КОНЕЦ (задача неразрешима из-за неограниченности целевой функции).

Шаг 4. Преобразовать симплекс-таблицу, положить q (r) := s и перейти на шаг 1.

Шаги с 1-го по 4-ый образуют одну итерацию симплекс-метода. Обоснование шага 1 содержится в лемме 4, а шага 3 – в леммах 5 и 6. Из доказательства леммы 6 также следует, что при элементарном преобразовании сохраняется прямо допустимость симплекс-таблицы.

В данном алгоритме не описан 0-ой шаг, а именно, способ построения начальной симплекс-таблицы. Предполагается, что известно начальное б.д.р.

Реализация 0-го шага содержится в параграфе 4 при описании двухфазного симплекс-метода.

При выполнении шагов 2 и/или 3 выбор ведущего столбца s и/или ведущей строки r может оказаться неоднозначным. Существуют разные правила выбора ведущего элемента. Ограничимся теми правилами, которые приводят к детерминированному алгоритму решения задач ЛП.

При выборе ведущего столбца используются следующие способы:

а) правило Данцига, которое заключается в выборе s с минимальным z0s < 0 ;

б) правило Блэнда, которое состоит в выборе наименьшего s такого, что z0s < 0 .

При выборе ведущей строки используются следующие способы:

а) правило Блэнда: выбрать строку r с минимальным номером базисной переменной q (r) , удовлетворяющей условиям шага 3;

б) лексикографическое правило, описанное в параграфе 3: выбрать строку r , для которой вектор лексикографически минимален среди векторов

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