Определение начального допустимого решения. Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений.
Поэтому для нахождения начального решения задачи требуется выразить m переменных т.е. количество переменных, равное количеству уравнений через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных в заданной задаче m4 и n8. Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны некоторые из них могут оказаться равными нулю. Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением.
Оно соответствует всем ограничениям. Начальное решение проще всего найти в случае, когда в каждом ограничении есть переменная, которая входит в него с коэффициентом 1 и при этом отсутствует в других ограничениях. Такие переменные принимаются в качестве базисных они образуют начальный базис задачи. Остальные небазисные переменные принимаются равными нулю. Таким образом, базисные переменные принимают значения, равные правым частям ограничений.
Итак, для нахождения начального допустимого решения необходимо, чтобы в каждое из уравнений входила переменная с коэффициентом 1 и не входила в другие уравнения базисная переменная. В нашем случае мы имеем только 2 базисные переменные X7 и X8 , не хватает еще двух базисных переменных. Их можно создать с помощью специального способа, который называется построением искусственного базиса. 4.3.