Главная » Справочник » Основы организации и управления транспортными системами » Симплексный метод с искусственным базисом

Симплексный метод с искусственным базисом

Симплексный метод с искусственным базисом применяют для решения задач линейного программирования, в которых базис отсутствует. Такие задачи содержат либо систему неравенств вида ≥, либо систему равенств (уравнений), либо различные сочетания уравнений и неравенств.

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

Для этого искусственные переменные вводятся целевую функцию с максимальным положительным числом (для задач на минимум) или с максимальным по абсолютной величине отрицательным числом (для задач на максимум). В окончательном варианте решения искусственные переменные всегда будут равны нулю, поскольку при решении задачи на максимум в оптимальный план не могут войти переменные, которые имеют в целевой функции очень большие по абсолютной величине отрицательные коэффициенты, так как это уменьшает значение целевой функции до бесконечности.

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

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

Предыдущая статья Симплексный метод решения задач линейного программирования Следующая статья Современные достижения техники на транспорте

Статьи по теме