6. Канонический вид злп, начальное допустимое базисное решение (ндбр),

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

Чтобы ЗЛП имела решение необходимо, чтобы система ограничений была совместна. Это возможно, если ранг mсистемы (число линейно независимых уравнений) был не больше числа неизвестных n. Случайm> n невозможен. Приm= n система имеет единственное решение, которое определяется методами обычной алгебры. Еслиm< n, то система имеетmлинейно независимых векторов – базис, через которые любой вектор системы может быть выражен как линейная комбинация. Таких базисов может быть несколько, но не больше, чем С_n^m. Переменные ЗЛП, соответствующиеmвекторам базиса, являются базисными, остальные переменные – свободные.

Базисом называют любой набор m переменных такой, что определитель, составленный из коэффициентов при этих переменных, отличен от нуля. Соответствующее решение называю базисным решением.

Переменные, входящие в базис, называют базисными (б.п.), остальные n – m переменных называют свободными.

Чтобы получить простейшее частное решение системы необходимо свободные переменные приравнять нулю, учитывая при этом неотрицательность всех переменных.

Допустимым базисным решением (ДБР) является такое, при котором все переменные неотрицательны. В противном случае базисное решение недопустимо.

Частное допустимое базисное решение, с которого начинают решение, называют начальным допустимым базисным решением (НДБР).

Чтобы найти НДБР, удобно ЗЛП записать в каноническом виде.

Канонический вид ЗЛП – это такой стандартный вид, в котором в каждом i-ом уравнении найдется такая переменная х_I, что коэффициент перед ней в данном уравнении равен +1, а в других уравнениях и в выражении целевой функции эти коэффициенты равны нулю.Если при этом всеb , то говорят о допустимом каноническом виде, в противном случае – о недопустмом.