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

определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются

все итерации.
За счет чего мы так легко составили исходную симплекс-таблицу в предыдущем примере? Легко видеть, что это произошло потому, что среди переменных были такие, что входили лишь в одно уравнение системы ограничений и не входили в другие.
На искусственном введении таких переменных и основан метод искусственного базиса.

канонической форме




Можно считать, что все bi≥0, так как умножением соответствующего

ограничения на -1 всегда можно сменить знак.
Возьмем ну очень большое число M и будем решать следующую вспомогательную задачу.

качестве него надо взять переменные xn+1,…,xn+m.
В качестве исходного опорного плана

надо взять план

дополнительные переменные.
Заметим, что если какая-то дополнительная переменная выведена из базиса,

то соответствующий столбец симплекс-таблицы можно просто вычеркнуть и больше к нему не возвращаться.
В конце концов возможны два варианта.
Вариант 1
Все векторы, соответствующие введенным дополнительным переменным, будут выведены из базиса. В этом случае мы просто вернемся к исходной задаче, попав в какую-то вершину допустимой области. Все столбцы симплекс-таблицы, соответствующие дополнительным переменным, тогда исчезнут и дальше будет решаться исходная задача.
Вариант 2
Несмотря на то, что M очень велико, получающийся оптимальный план будет все-таки содержать какую-то из дополнительных переменных. Это означает, что допустимая область исходной задачи пуста, то есть ограничения исходной задачи противоречивы и поэтому исходная задача вообще не имеет решений.
Заметим в заключение, что величина M вообще не конкретизируется и так и остается в виде буквы M. При решении учебных задач в дополнительную строку пишут алгебраические выражения, содержащие M, а при счете на ЭВМ вводится еще одна дополнительная строка, куда пишутся коэффициенты при M.

ее по стандартной схеме.