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

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

{spoiler=Подробнее}

Если  ограничения  задачи  линейного  программирования  можно  преобразовать к виду   АХ £ А₀  при  А₀ ³ 0, то  система  ограничений  всегда  содержит  единичную  матрицу . Многие  задачи  линейного  программирования , имеющие  решения ,  не  содержат  единичной  матрицы  и  не  приводятся  к указанному  виду . В этом случае  для  решения   задач   применяется  метод  искусственного  базиса . Рассмотрим  общую  задачу  линейного  программирования .

Найти минимальное значение линейной функции  Z=C₁x₁+C₂x₂+  +... + C_nx_n+Mx_n+1+...+Mx_n+m при ограничениях

x_j    (j=1,2,...,n+m),

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

А_n+1, А_n+2, ...., А_n+m,

соответствующие искусственным переменным, образуют искусственный базис.

Для отыскания оптимального плана исходной задачи используют следующую теорему.

Теорема.  Если в оптимальном плане Х=(х₁,х₂,... , х_n, 0, 0, ... ,0) расширенной задачи искусственные переменные х_n+i=0(i = 1,2, ... ,m), то план Х=(х₁, х_{2, ... ,}х_n)  является оптимальным планом исходной задачи.

Пример. Найти максимальное значение линейной функции Z=5x₁+3x₂+4x₃-x₄ при ограничениях

x_j>=0 (j=1,2,3,4).

Решение. Система ограничение не содержит единичной матрицы. Прибавим к каждому уравнению по одной неотрицательной искусственной переменной (соответственно x₅³ 0, x₆³0) и перейдём к расширенной задаче.

Найти максимальной  значение линейной функции

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

x_j>=0 (j=1,2,3,4,5,6).

или векторной форме:

A₁x₁+A₂x₂+A₃x₃+...+A₆x₆=A₀

Выберем за базис единичные векторы А₅, А₆, которые и образуют искусственный базис. Приравнивая свободные неизвестные нулю: x₁=x₂=x₃=x₄=0, получаем первоначальный опорный план расширенной задачи:

Х₀=(0:0:0:0:3:3), которому соответствует разложение х₅А₅+х₆А₆=А₀.

Составим симплексную таблицу (табл.) в которой m+2 строки, и по оценкам, содержащимся в ней, проверим план на оптимальность.

Значения оценок, записанных в (m+1)-й и в (m+2)-й строках, находим по формулам.

Z(X₀)=C_базX₀=—3M—3M+0=0—6M,

Z₁—C₁=C_базX₁—C₁=—M—2M—5=—5—3M,

Z₂—C₂=C_базX₂—C₂=—3M—2M—2=—3—5M, и. т. д.,

т.е. если M заранее не фиксировано, то оценки Z_j-C_j являются линейным функциями величины М, причем функция состоит из двух слагаемых, одно из которых зависит от М, а второй -не зависит.

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

Вычислим max 0_oj(Z_j-C_j), которое достигается для вектора A₂; 0₀₂(Z_j-C_j),=3/3×(-5)=-5. Разрешающий элемент число 3, вектор А₂ включаем в базис, вектор А₅- исключаем.

Составим симплексную таблицу (табл.). для этого разделим элементы направляющей строки на 3 и произведем одно полное исключение.

В результате второй итерации с разрешающим элементом 4/3 из базиса исключен последний искусственный вектор А₆, поэтому в  (m+2)-й строке третьей итерации все оценки, кроме оценок двух искусственных векторов, обратились в нуль.

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

Опорной план 3/4;3/4;0;0;0;0;), полученные в третьей итерации, являются планом исходной задачи, и не оптимальным, так как в (m+1) -й строке имеется отрицательная оценка Z₂-C₃=-3<0.

Дальнейший итерационный процесс проводим по (m+1) -й строке, (m+2)-ю строку из дальнейшего рассмотрения исключаем, а величину М включаем в оценки искусственных векторов. В четвертой итерации находим оптимальный план исходной задачи: Х=(1;0;1;0); при этом плане Z_max(x)=9. В столбцах А₅ и А₆ получено матрица, из которой можно получить обратную, поменяв местами первую и вторую строки.

Принимая во внимание, что если  система ограничений задачи линейного программирования содержит единичный базис, то для решения задачи необходимо примерно m итераций; если  же для получения первоначального опорного плана необходимо ввести полный искусственный базис, то количество итераций увеличивается приблизительно до 2m.

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

{/spoilers}