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

Вспомогательная задача к ЗЛП (1):
(2)
Вектор составлен из естественных переменных ЗЛП (1.) и искусственных переменных, введенных в ЗЛП (2):

Искусственные переменные не несут никакого экономического смысла. Они необходимы только для поиска начального БДП.
Единичные векторы An+1, An+2, …, An+m образуют искусственный базис системы ограничений ЗЛП (2). Они представляют собой единичную матрицу размера m × m.
В ЗЛП (2) мы имеем начальный БДП, в котором первые n координат равны нулю.
Пусть множество допустимых планов задачи (1) - D1, а множество допустимых планов задачи (2) - D2.

Теорема. (О существовании плана ЗЛП).
Пусть
оптимальный план ЗЛП (2), тогда:
Если , то план является планом задачи (1), т.е. ∈D1.
Если , то ЗЛП (1) не имеет допустимых планов, т.е. D1 есть пустое множество (D1 = ∅).
Замечание. Вспомогательная задача (2) всегда имеет оптимальный план.

П р и м е р: Рассмотрим ЗЛП:
Приведем данную ЗЛП к каноническому виду:

Единичного базиса нет, поэтому построим вспомогательную задачу, предварительно введя две искусственные переменные х5 ≥ 0 и х6 ≥ 0.