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

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

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

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

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

Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:

где α_rj — коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки (соответствующей исключаемой переменной х_r) и столбца, соответствующего переменной x_j. При наличии нескольких альтернативных переменных, выбор делается произвольно.

Пример: Дана задача линейного программирования:

Минимизировать

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

Начальная симплекс-таблица имеет вид:

Среди дополнительных переменных этой задачи х₃ и х₄ являются избыточными, а x₅ — остаточной. Умножим каждое равенство, соответствующее избыточным дополнительным переменным, на -1; в результате правые части этих равенств непосредственно указывают на базисные переменные, которые являются недопустимыми (х₃ = -3, х₄ = -6, х₅= 3). Этот подход всегда используется при реализации двойственного симплекс-метода.

Поскольку z_j – с_j ≤ 0 для всех j = 1,..., 5, начальное базисное решение является оптимальным (но не допустимым). Таким образом, приведенная таблица удовлетворяет требованиям начальной таблицы двойственного симплекс-метода, а именно — оптимальности и недопустимости.

Двойственное условие допустимости указывает на переменную х₄ (= -6) как на вводимую в базис. Теперь применим двойственное условие оптимальности для определения исключаемой переменной. Для этого используем следующую таблицу.

Приведенные отношения показывают, что исключаемой переменной будет х₂. Отметим, что переменные х_j будут кандидатами на исключение из базисного решения только тогда, когда коэффициент α_4j будет строго отрицательным. По этому критерию переменные x₃, х₄, х₅ не рассматриваются как кандидаты на исключение из базиса.

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

Последняя таблица показывает, что из базиса исключается переменная x₃ и вводится x₁. В результате получаем следующую симплекс-таблицу.

Решение, представленное в последней таблице, допустимо (и оптимально), поэтому вычисления заканчиваются. Это решение имеет вид х₁ = 3/5, х₂ = 6/5, z = 21/5.

На рис. 1 показана последовательность шагов двойственного симплекс-метода при решении этой задачи.

Рис. 1. Последовательность шагов двойственного симплекс-метода

Алгоритм начинается в крайней точке А (которой соответствует недопустимое, но "лучше, чем оптимальное" решение), затем он переходит к точке В (которой также соответствует недопустимое, но "лучше, чем оптимальное" решение) и заканчивается в точке С, уже принадлежащей области допустимых решений.

Матричное представление симплексных вычислений.

В анализе чувствительности решения задачи ЛП нас интересует один принципиальный вопрос: как изменение коэффициентов целевой функции и ограничений влияет на оптимальность и допустимость текущего оптимального решения? Если эти изменения ведут к новому решению, то как найти это новое решение (если оно существует)? Конечно, можно ответить на этот вопрос путем решения задачи заново. Но для типовой практической задачи, имеющей тысячи переменных и ограничений, такой путь будет не эффективным. Поэтому необходимо выяснить, как вычисления в симплекс-методе зависят от изменений коэффициентов исходной задачи. В частности, следует выяснить, как от этих изменений зависят оптимальность и допустимость решения, представленного в виде симплекс- таблицы.

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

1. Матрица А порядка m x n – это прямоугольный массив элементов с m строками и n столбцами.

2. Вектор-строка V размерности n – матрица порядка 1 x n.

3. Вектор-столбец P размерности m– матрица порядка m x 1.

Эти определения математически можно представить как: