[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5]
Система m линейных уравнений с n переменными имеет вид
а11 х1+а12
х2+:+а1j хj
+...+а1n хn = b1
а21 х1+а22
х2+:+а2j хj
+...+а2n хn= b2
...
аi1 х1+аi2
х2+:+аij хj
+...+аin хn = bi
...
аm1 х1+аm2
х2+...+аmj хj
+...+аmn хn = bm
(2.1)
или в краткой записи
В задачах линейного программирования представляют интерес системы, в которых
ранг r матрицы системы А = (aij), i=1, 2, ..., m;
j=1, 2, .... n, или, что то же самое, максимальное число
независимых уравнений системы r меньше числа переменных, т.е.
r < n. Будем полагать, что в системе (2.1) все m
уравнений системы независимы, т.е. r = m и соответственно
m < n.
Определение
Любые m переменных системы m линейных уравнений с n переменными (m < n)
называются основными (или базисными), если определитель матрицы
коэффициентов при них отличен от нуля.
В литературе такой определитель
часто называют базисным минором матрицы А.
Тогда остальные (n - m) переменных называются неосновными (или
свободными).
Основными могут быть разные группы из n переменных. Максимально возможное число групп основных переменных равно числу способов выбора m переменных из их общего числа n, т.е. числу сочетаний Сnm. Но так как могут встретиться случаи, когда определитель матрицы коэффициентов при m переменных равен нулю, то общее число групп основных переменных не превосходит Сnm.
Задача 2.1 |
Найти все возможные группы основных переменных в системе x1 - x2 - 2x3 + x4 = 0, 2 x1 + x2 + 2 x3 - x4 = 0. Решение. Общее число групп основных переменных не более чем С42 =4*3/2=6, т.е. возможные группы основных переменных: x1, x2; x1, x3; x1, x4; x2, x3; x2, x4; x3, x4. Выясним, могут ли быть основными переменные x1, x2. Так как определитель матрицы из коэффициентов при этих переменных = 1 * 1 - 2 * (-1) = 3 > 0, то x1, x2 могут быть основными переменными. Рассуждая аналогично, найдем, что могут быть основными переменные x1, x3; x1,x4 но не могут быть основными x2,x3; x2,x4; x3,x4, так как в трех последних группах переменных соответствующие определители равны нулю. |
[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [В начало страницы]