II метод искусственного базиса

Рассмотрим задачу (2) с ограничениями типа (4):

(5)

Предположим, система (5) не имеет не предпочтительный вид. Введем искусственные переменные w_{n +1}, …, w_n+m так, чтобы (5) принял предпочтительный вид. (Если какое-нибудь равенство k в (5) имеет предпочтительный вид, то искусственную переменную w_n+k либо не вводим, либо считаем w_n+k = 0).

Составим следующую задачу:

(6)

Теорема: пусть задача (5) имеет допустимое решение. Решение X ^* = (x ₁, …, x_n, w_{n +1}, …, w_n+m) задачи (6) является оптимальным Û w_n+i = 0, i = 1.. m.

Теорема гарантирует равенство 0 всех искусственных переменных в оптимальном решении X ^* Þ X = (x ₁, …, x_n) является допустимым решением задачи (5), но, вообще говоря, оно не является оптимальным решением задачи, как это было в случае I метода искусственного базиса.

Однако на практике II метод имеет следующее применение. Предположим, оптимальное решение X ^* задачи (6) найдено СМ. Тогда ненулевым компонентам X ^* соответствуют линейно независимое векторы A_j. Так как ненулевыми компонентами по теореме могут быть только исходные переменные x_j, а не искусственные w_n+i, то решению X ^* соответствуют линейно независимые векторы из системы A_j. Если оказалось, что оптимальное решение X ^* не вырождено, то число линейно независимых векторов составляет базис. Этот базис и соответствующие ему переменные x_j могут быть приняты в качестве первоначального допустимого базисного решения задачи (5).

Таким образом, алгоритм метода:

1. задача (5) преобразуется в (6)

2. задача (6) решается СМ.

3. если решение X ^* не вырождено, то в последней таблице СМ вычеркиваются столбцы, соответствующие искусственным переменным и пересчитывается D _j. Полученная таблица будет являться исходной для решения задачи (5)