Если такого столбца не обнаружится, за   принимается максимальное найденное абсолютное значение и соответствующий столбец   вводится в базис.

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

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

Умножим слева на  , т.е.  .

Здесь   - базисный план,   - разложение вводимого столбца по базису.

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

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

Вычисляем новый опорный план по уже приведенной формуле   с найденным значением  .

5. Пересчитываем обратную к базисной  .

Пусть   - выводимый столбец.

Матрица B представима в виде 

где   - базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид 

Нам нужно найти матрицу  , такую что

 =>   =>   =>

Откуда 

Замечание.

При пересчете матрицы   накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется "повторением".

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

В мультипликативном варианте матрица   не хранится, хранятся лишь множители 

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

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

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

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

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

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

При относительно небольших размерах матрицы   остальная часть матрицы может не храниться.

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

Двойственный симплекс-метод

Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:

при ограничениях

.

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

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

Вычислительная эффективность

Симплекс-метод удивительно эффективен на практике, но в 1972 Кли и Минти ^[4] привели пример, в котором симплекс-метод перебирал все вершины симплекса, что показывает экспоненциальную сходимость метода в худшем случае. С тех пор для каждого варианта метода был найден пример, на котором метод вел себя исключительно плохо.

---

Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.

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

Вычислительная эффективность оценивается обычно при помощи двух параметров:

1) Числа итераций, необходимого для получения решения;

2) Затрат машинного времени.

В результате численных экспериментов получены результаты:

1) Число итераций при решении задач линейного программирования в стандартной форме с   ограничениями и   переменными заключено между   и  . Среднее число итераций  . Верхняя граница числа итераций равна  .

2) Требуемое машинное время пропорционально  .

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

---

Смотрите также файлы

• 5.2. Сведения о теоремах линейного программирования.docx

• 5.1. Математическая постановка и методы решения задач линейного программирования.docx

• 4.2. Принципы и подходы к построению математических моделей. Этапы построения математических моделей.docx

• 4.1. Классификация математических моделей.docx

• 3.3. Дополнение к классификации видов моделирования систем.docx