Править]Модифицированный симплекс-метод

В модифицированном методе матрица

Править]Модифицированный симплекс-метод - student2.ru

не пересчитывается, хранится и пересчитывается только матрица Править]Модифицированный симплекс-метод - student2.ru . В остальном алгоритм похож на вышеописанный.

1. Вычисляем двойственные переменные Править]Модифицированный симплекс-метод - student2.ru

2. Проверка оптимальности. Править]Модифицированный симплекс-метод - student2.ru преобразуется в Править]Модифицированный симплекс-метод - student2.ru .

Проверка заключается в вычислении Править]Модифицированный симплекс-метод - student2.ru для всех столбцов Править]Модифицированный симплекс-метод - student2.ru . Столбец со значением < 0 можно вводить вводить в базис.

Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.

Чаще выбирают значение, меньшее некоторого заданного значения Править]Модифицированный симплекс-метод - student2.ru

Если такого столбца не обнаружится, за Править]Модифицированный симплекс-метод - student2.ru принимается максимальное найденное абсолютное значение и соответствующий столбец Править]Модифицированный симплекс-метод - student2.ru вводится в базис.

3. Определение выводимого.

Пусть Править]Модифицированный симплекс-метод - student2.ru - вводимый столбец, соответствующий переменной Править]Модифицированный симплекс-метод - student2.ru Базиный план - это решение системы Править]Модифицированный симплекс-метод - student2.ru Увеличиваем Править]Модифицированный симплекс-метод - student2.ru .

Умножим слева на Править]Модифицированный симплекс-метод - student2.ru , т.е. Править]Модифицированный симплекс-метод - student2.ru .

Здесь Править]Модифицированный симплекс-метод - student2.ru - базисный план, Править]Модифицированный симплекс-метод - student2.ru - разложение вводимого столбца по базису.

Находим максимальное значение Править]Модифицированный симплекс-метод - student2.ru , при котором все значения не отрицательны. Если Править]Модифицированный симплекс-метод - student2.ru может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса.

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный план по уже приведенной формуле Править]Модифицированный симплекс-метод - student2.ru с найденным значением Править]Модифицированный симплекс-метод - student2.ru .

5. Пересчитываем обратную к базисной Править]Модифицированный симплекс-метод - student2.ru .

Пусть Править]Модифицированный симплекс-метод - student2.ru - выводимый столбец.

Матрица B представима в виде Править]Модифицированный симплекс-метод - student2.ru

где Править]Модифицированный симплекс-метод - student2.ru - базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид Править]Модифицированный симплекс-метод - student2.ru

Нам нужно найти матрицу Править]Модифицированный симплекс-метод - student2.ru , такую что

Править]Модифицированный симплекс-метод - student2.ru => Править]Модифицированный симплекс-метод - student2.ru => Править]Модифицированный симплекс-метод - student2.ru =>

Править]Модифицированный симплекс-метод - student2.ru

Откуда Править]Модифицированный симплекс-метод - student2.ru

Замечание.

При пересчете матрицы Править]Модифицированный симплекс-метод - student2.ru накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется "повторением".

[править]Мультипликативный вариант симплекс-метода

В мультипликативном варианте матрица Править]Модифицированный симплекс-метод - student2.ru не хранится, хранятся лишь множители Править]Модифицированный симплекс-метод - student2.ru

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

[править]Другие варианты симплекс-метода

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

При подавляющем числе ограничений типа "неравенство" может быть использован метод переменного базиса.

Метод основан на том, что базисная матрица может быть представлена в виде

Править]Модифицированный симплекс-метод - student2.ru

Обратная к ней имеет вид

Править]Модифицированный симплекс-метод - student2.ru

При относительно небольших размерах матрицы Править]Модифицированный симплекс-метод - student2.ru остальная часть матрицы может не храниться.

Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).

Наши рекомендации