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

Для построения исходного опорного плана при решении задачи симплекс-методом необходимо, чтобы матрица коэффициентов при переменных, имеющая «m» строк и «n» столбцов (m<n), содержала в себе единичную матрицу порядка «m». Такая матрица получалась после введения дополнительных переменных в исходные ограничения вида «≤». Однако, если исходные ограничения задаются сразу уравнениями, то нет никакой гарантии, что матрица коэффициентов содержит единичную матрицу порядка «m». То же относится и к системе неравенств вида «≥».

Дополнительные переменные входят в такую систему с коэффициентами «-1». В этих случаях для решения задачи применяется симплекс-метод с искусственным базисом.

В левую часть уравнений вводятся неотрицательные искусственные переменные ω₁, ω₂, …, ω_m, коэффициенты при которых образуют единичную матрицу. Эти же переменные с большими по абсолютной величине отрицательными коэффициентами (-M) включаются в целевую функцию.

В результате расширенная задача принимает вид:

При условиях:

,

Искусственные переменные необходимы для построения исходного плана задачи. В процессе решения они должны выводиться из базиса, т.к. в окончательном плане задачи должны соблюдаться исходные уравнения, а это возможно когда ω_i=0.

Решение задачи линейного программирования методом искусственного базиса включает следующие этапы.

1. Составляют расширенную задачу.

2. Находят опорный план расширенной задачи.

3. С помощью обычных вычислений симплекс-методом исключают искусственные переменные из базиса. Анализ ведут по «m+2» строке. В результате находят опорный план исходной задачи, либо устанавливают ее неразрешимость.

4. Используя найденный опорный план исходной задачи симплекс-методом находят оптимальный план (анализ ведут по «m+1» строке) или устанавливают неразрешимость задачи.

Возможны случаи, когда при оптимизации опорного плана расширенной задачи в «m+2» строке еще остается отрицательное число, но в соответствующем ему столбце нет положительных коэффициентов, следовательно, в базисе остаются несколько искусственных переменных и они не могут быть выведены. Это означает, что исходная задача не имеет искомого решения. Полученный план не удовлетворяет всем поставленным условиям, и окончательный базис будет содержать искусственную переменную.

Пример:

Найти оптимальное решение задачи

F=-2x₁+3x₂−6x₃−x₄→min

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

Приведем задачу к виду основной задачи линейного программирования, учитывая, что целевая функция должна стремиться к max

:

F=-2x₁+3x₂−6x₃−x₄→max

Среди векторов, составленных из коэффициентов при неизвестных, только два единичных (х₄ и х₅), поэтому в левую часть третьего уравнения добавим искусственную переменную ω и составим расширенную задачу:

F=-2x₁+3x₂−6x₃−x₄−М ω →max

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

1-ая итерация

План можно улучшить. Анализ ведем по второй индексной строке. Вводимой переменной будет х₃,а выводимой ω т.к.

Примечание.

Искусственную переменную всегда стараются вывести первой. Как только ω выведена из базиса, на последующих итерациях столбец ω не заполняется и индексная строка будет одна.