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

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

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

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

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

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

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

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

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

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

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

15)

Для его применения необходимо, чтобы знаки в ограничениях были вида

“ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему :

1. Приведение системы ограничений к каноническому виду путём введения

дополнительных переменных для приведения неравенств к равенствам.

2. Если в исходной системе ограничений присутствовали знаки “ равно ”

- 8 -

или “ больше либо равно ”, то в указанные ограничения добавляются

искусственные переменные, которые так же вводятся и в целевую функцию

со знаками, определяемыми типом оптимума.

3. Формируется симплекс-таблица.

4. Рассчитываются симплекс-разности.

5. Принимается решение об окончании либо продолжении счёта.

6. При необходимости выполняются итерации.

7. На каждой итерации определяется вектор, вводимый в базис, и вектор,

выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса

или каким-нибудь другим способом.

16) Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и являетсямодификацией табличного метода. Решение системы производится путём вводаискусственных переменных со знаком, зависящим от типа оптимума, т.е. дляисключения из базиса этих переменных последние вводятся в целевую функцию сбольшими отрицательными коэффициентами ( , а в задачи минимизации - сположительными ( . Таким образом из исходной получается новая ( - задача. Если в оптимальном решении ( - задачи нет искусственных переменных, эторешение есть оптимальное решение исходной задачи. Если же в оптимальномрешении ( - задачи хоть одна из искусственных переменных будет отлична отнуля, то система ограничений исходной задачи несовместна и исходная задачанеразрешима.

МЕТОД ИСКУССТВЕННОГО БАЗИСА»

«МЕТОД ИСКУССТВЕННОГО БАЗИСА»

1. Применение метода искусственного базиса.

2. Решение ЗЛП методом искусственного базиса.