Особенности алгоритма метода искусственного базиса
Алгоритм метода искусственного базиса имеет следующие особенности:
1. Ввиду того, что начальное опорное решение расширенной задачи содержит искусственные переменные, входящие в целевую функцию с коэффициентом –M (в задаче на максимум) или +M (в задаче на минимум), оценки разложений векторов условий 
состоят из двух слагаемых 
и 
, одно из которых не зависит от M , а другое зависит от M. Так как M сколь угодно велико по сравнению с единицей 
>>1), то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемые оценок .
2. Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения.
3. После того как все векторы, соответствующие искусственным переменным, исключаются из базиса, расчет продолжается обычным симплексным методом с использованием оценок , не зависящих от M.
4. Переход от решения расширенной задачи к решению исходной задачи осуществляется с использованием доказанных выше теорем 3.2.-3.4.
И
Р е ш е н и е. Составляем расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом +1 (всегда). Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим переменную 
, во второе – переменную 
. Данная задача – задача на нахождение максимума, поэтому и в целевую функцию вводятся с коэффициентом –M. Получаем:
Задача имеет начальное опорное решение 
с базисом 
. Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:
Записываем исходные данные в симплексную таблицу (табл. 3.1.1). При этом оценки и 
для удобства вычислений записываем в две строки: в первую – слагаемые , не зависящие от M, во вторую – слагаемые , зависящие от M. Значения удобно указывать без M, имея в виду, однако, что оно там присутствует.
Таблица 3.1.1
3 2 
-8 -M -M
| Б |  |  |  |  |  |  |  |  |  |  |   |
 | -M -M | -7 -2 |  | |  | ||||||
 | -3 | -2 | -1 | ||||||||
 | -12 | -5 | -4 | -5 |
Начальное опорное решение не является оптимальным, так как в задаче на максимум имеются отрицательные оценки (см. теорему 3.1). Выбираем номер вектора 
, вводимого в базис опорного решения, и вектора 
, выводимого из базиса. Для этого вычисляем приращения целевой функции 
при введении в базис каждого из векторов с отрицательной оценкой и находим максимум этого приращения. При этом слагаемыми оценок 
(без M) пренебрегаем до тех пор, пока хотя бы одно слагаемое (с M) отлично от нуля. В связи с этим со слагаемыми оценок может отсутствовать в таблице до тех пор, пока присутствует строка . Находим:
при k=3.
В столбце « » (см. табл. 3.1.1) за разрешающий элемент выбираем коэффициент 1 во второй строке и выполняем преобразование Жордана.
Вектор , выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем опорное решение 
с базисом 
(табл. 3.1.2). Решение не является оптимальным, так как имеется отрицательная оценка 
Таблица 3.1.2
| Б | | | | | | | | |  |
| | -M | -5 | -1 |  -2 | - | ||||
| | -1 | -1 | |||||||
| | -2 | -1 |
←
В столбце « » единственный положительный элемент принимаем за разрешающий и переходим к новому опорному решению 
с базисом 
(табл.3.1.3).
Таблица 3.1.3
| Б | | | | | | | | |
| | -8 | -5 -8 | -1 -1 | |||||
 | -10 |
Данное опорное решение является единственным оптимальным решением расширенной задачи, так как в задаче на максимум оценки для всех векторов, не входящих в базис, положительны. По теореме 4.2 исходная задача также имеет оптимальное решение, которое получается из оптимального решения расширенной задачи отбрасыванием нулевых искусственных переменных, т.е. 
О т в е т: 
при