Править]Вычислительная эффективность
Симплекс-метод удивительно эффективен на практике, но в 1972 Кли и Минти [1] привели пример, в котором симплекс-метод перебирал все вершины симплекса, что показывает экспоненциальную сходимость метода в худшем случае. С тех пор для каждого варианта метода был найден пример, на котором метод вел себя исключительно плохо.
Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.
Симплекс-метод имеет среднюю полиномиальную сходимость при широком выборе распределения значений в случайных матрицах.[2][3]
Вычислительная эффективность оценивается обычно при помощи двух параметров:
1) Числа итераций, необходимого для получения решения;
2) Затрат машинного времени.
В результате численных экспериментов получены результаты:
1) Число итераций при решении задач линейного программирования в стандартной форме с 
ограничениями и 
переменными заключено между и 
. Среднее число итераций 
. Верхняя граница числа итераций равна 
.
2) Требуемое машинное время пропорционально 
.
Число ограничений больше влияет на вычислительную эффективность, чем число переменных, поэтому при формулировке задач линейного программирования нужно стремиться к уменьшению числа ограничений пусть даже путём роста числа переменных.
15)
Для его применения необходимо, чтобы знаки в ограничениях были вида
“ меньше либо равно ”, а компоненты вектора b - положительны.
Алгоритм решения сводится к следующему :
1. Приведение системы ограничений к каноническому виду путём введения
дополнительных переменных для приведения неравенств к равенствам.
2. Если в исходной системе ограничений присутствовали знаки “ равно ”
- 8 -
или “ больше либо равно ”, то в указанные ограничения добавляются
искусственные переменные, которые так же вводятся и в целевую функцию
со знаками, определяемыми типом оптимума.
3. Формируется симплекс-таблица.
4. Рассчитываются симплекс-разности.
5. Принимается решение об окончании либо продолжении счёта.
6. При необходимости выполняются итерации.
7. На каждой итерации определяется вектор, вводимый в базис, и вектор,
выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса
или каким-нибудь другим способом.
16) Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и являетсямодификацией табличного метода. Решение системы производится путём вводаискусственных переменных со знаком, зависящим от типа оптимума, т.е. дляисключения из базиса этих переменных последние вводятся в целевую функцию сбольшими отрицательными коэффициентами ( , а в задачи минимизации - сположительными ( . Таким образом из исходной получается новая ( - задача. Если в оптимальном решении ( - задачи нет искусственных переменных, эторешение есть оптимальное решение исходной задачи. Если же в оптимальномрешении ( - задачи хоть одна из искусственных переменных будет отлична отнуля, то система ограничений исходной задачи несовместна и исходная задачанеразрешима.
МЕТОД ИСКУССТВЕННОГО БАЗИСА»
«МЕТОД ИСКУССТВЕННОГО БАЗИСА»
1. Применение метода искусственного базиса.
2. Решение ЗЛП методом искусственного базиса.