Метод искусственного базиса. Для задачи, записанной в форме основной задачи линейного программирования, можно непосредственно указать ее опорный план, если среди векторов Aj, компонентами (координатами) которых служат коэффициенты при неизвестных в системе уравнений данной задачи, имеется m единичных. Однако для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов Aj не всегда есть m единичных. Рассмотрим такую задачу:
Пусть требуется найти максимум функции
F=c1x1+c2x2+…+cnxn (1)
при условиях
(2)
xj ≥0 (j = 
), (3)
где bi ≥ 0 (i = 
), m<n и среди векторов
А 1= 
; А 2= 
;…; Аn = 
нет m единичных.
Определение. Задача, состоящая в определении максимального значения функции
F=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m= c1x1+c2x2+…+cnxn-M (xn+1+…+xn+m)(4)
при условиях
(5)
xj≥0 (j= 
), (6)
где M – некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей по отношению к задаче (1)-(6).
Расширенная задача имеет опорный план
X =(0;…;0; b 1; b 2; …; b m) (n нулей),
определяется системой единичных векторов Аn +1, Аn +2, …, Аn +m, образующих базис m- го векторного пространства, который называется искусственным. Сами векторы, так же как и переменные xn+i (i = ), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.
Теорема. Если в оптимальном плане 
* =( x*1, x*2,…, x*n, x*n+1, …, x*n+m ) расширенной задачи (4)-(6) значения искусственных переменных x*n+i =0(i = ), то X*=(x*1, x*2, …, x*n) является оптимальным планом задачи (1)-(3).
Таким образом, если в найденном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то тем самым получен оптимальный план исходной задачи. Поэтому остановимся более подробно на нахождении решения расширенной задачи.
При опорном плане X =(0;…;0; b 1; b 2; …; b m) расширенной задачи значение линейной формы есть F 0 = - M 
, а значение 
равны - M 
. Таким образом, F 0 и разности 
состоят из двух независимых частей, одна из которых зависит от M, а другая – нет.
После вычисления F 0 и ∆j их значения, а также исходные данные расширенной задачи заносят в таблицу, которая содержит на одну строку больше, чем обычная симплексная таблица. При этом в (m +2)-ю строку помещают коэффициенты при M, а в (m +1)-ю – слагаемые, не содержащие M.
При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m +2)-й строки. Искусственный вектор, исключенный из базиса в результате некоторой итерации, в дальнейшем не имеет смысла вводить ни в один из последующих базисов и, следовательно, преобразование столбцов этого вектора излишне. Однако, если нужно найти решение двойственной задачи для данной (о чем будет сказано позже), то такое преобразование необходимо. Может случиться так, что в результате некоторой итерации ни один из искусственных векторов из базиса не будет исключен.
Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.
Итерационный процесс по (m +2)-й строке ведут до тех пор, пока:
1) либо все искусственные векторы не будут исключены из базиса;
2) либо не все искусственные векторы исключены, но (m +2)-я строка не содержит больше отрицательных элементов в столбцах векторов А1, А2,…, Аn+m.
В первом случае базис отвечает некоторому опорному плану исходной задачи и определение ее оптимального плана продолжают по (m +1)-й строке.
Во втором случае, если элемент, стоящий в (m +2)-й строке столбца вектора А0 отрицателен, исходная задача не имеет решения; если же он равен нулю, то найденный опорный план исходной задачи является вырожденным и базис содержит, по крайней мере, один из векторов искусственного базиса.
Если исходная задача содержит несколько единичных векторов, то их следует включить в искусственный базис.
Следовательно, процесс нахождения решения задачи (1)—(3) методом искусственного базиса включает следующие основные этапы:
1. Составляют расширенную задачу (4) — (6).
2. Находят опорный план расширенной задачи.
3. С помощью обычных вычислений симплекс-метода исключают искусственные векторы из базиса. В результате либо находят опорный план исходной задачи (1)—(3), либо устанавливают ее неразрешимость.
4. Используя найденный опорный план задачи (1)—(3), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.