В14 Определение базисного допустимого решения (БДР) задачи линейного программирования

Система векторов А₁, А₂,…, A_k называется линейно зависимой, если существуют такие числа α₁, α₂,…, α_k не равные нулю одновременно, что сумма α₁*А₁+α₂*А₂+α_k*A_k=Θ (нулевому вектору). В противном случае систему векторов называют линейно независимой.

Пример 1:

Являются ли вектора линейно зависимыми?

- линейная комбинация векторов.

α₁= -1, α₂=2, α₃= -1

Ответ: линейно зависимы.

Линейная зависимость векторов означает, что один из них можно выразить через остальные.

Пример 2:

Линейно независимы, т. к. α₁ и α₂ не могут быть одновременно равны 0.

Опр: Максимальное кол-во линейно независимых векторов – столбцов матрицы называется рангом матрицы.

r(ранг)=2; ранг = 1, т.к. можно выразить через

Замечания:

1) у единичной матрицы всегда полный ранг (все столбцы линейно независимы)

2) если определитель квадратной матрицы=0, то её столбцы линейно зависимы

3) в матрице количество линейно независимых строк равно количеству линейно независимых столбцов

БДР – это решение, которое удовлетворяет следующим условиям:

1) оно допустимо

2) количество базисных переменных = рангу матрицы А

3) базисные переменные соответствуют линейно независимым столбцам матрицы А

Пример:

х = (5, 0, 1, 7) – числа выбираем сами как удобно, например x₂=0 => x₁=5.

1) +; 2) базисные переменные 5,1,7 соответствуют столбцам единичной матрицы; 3) ранг = 3.