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

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

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

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

Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР),

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

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

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

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

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

Дата добавления: 2014-01-20