Методичка по курсовым и лабораторным работам (1085639), страница 9
Текст из файла (страница 9)
Матрица системы:
2 1 –1 1
A = 1 –1 0 0 .
1 0 –2 0
Расширенная матрица:
2 1 –1 1 –1
= 1 –1 0 0 2
1 0 –2 0 3
Определим ранг матрицы A. Он не может быть больше трех, т. к. число строк равно 3. Составим какой-нибудь определитель, вычеркнув из матрицы какой-нибудь столбец, например, последний. Получим
2 1 –1
D = 1 –1 0 .
1 0 –2
Вычисляя этот определитель по известному правилу, получим:
D = 5 ? 0.
Определитель третьего порядка не равен 0, значит, ранг матрицы системы равен 3. Очевидно, ранг расширенной матрицы тоже равен 3, т. к. из элементов расширенной матрицы можно составить тот же определитель. Из равенства рангов матриц следует, что система уравнений совместна.
Пример 3.2.
Исследовать на совместность систему двух уравнений с тремя неизвестными:
2x1 – x2 + x3 = – 4,
4x1 – 2x2 + 2x3 = 1.
Матрица системы:
2 –1 1
A = 4 –2 2 .
Расширенная матрица:
2 –1 1 –4
= 4 –2 2 1 .
Нетрудно убедиться, что все возможные определители 2-го порядка, составленные из элементов матрицы системы A, равны 0. Поэтому ранг матрицы A равен 1.
При определении ранга расширенной матрицы заметим, что определитель
D = 
= 18 ? 0.
Значит, ранг расширенной матрицы равен 2. Следовательно, система уравнений несовместна.
Итак, если система уравнений-ограничений ЗЛП совместна, то матрица системы и ее расширенная матрица имеют один и тот же ранг. Этот общий ранг r называется рангом системы и равен числу линейно независимых уравнений среди уравнений системы.
Очевидно, что ранг системы не может быть больше числа уравнений (числа строк матрицы A) и числа неизвестных (числа столбцов матрицы A), т. е.
r ? m, r ? n, т. е. r ? min(m, n).
При r = n число линейно независимых уравнений системы (3.14) равно числу переменных n. Остальные m – n уравнений линейно зависимы. Отбросим эти . уравнения. Тогда мы имеем систему из n уравнений и n переменных, причем определитель матрицы этой системы не равен нулю. Из алгебры известно, что в этом случае система имеет единственное решение.
Итак, при r = n система уравнений-ограничений ЗЛП имеет единственное решение x1, x2, …, xn.
Если в этом решении хотя бы одна из величин x1, x2, …, xn отрицательна, то полученное решение недопустимо и, значит, ЗЛП не имеет решения.
Если все величины x1, x2, …, xn неотрицательны, то полученное решение допустимо и, поскольку оно единственно, оно и будет оптимальным.
Этот тривиальный случай не представляет интереса и в дальнейшем будем рассматривать только случай, когда r < n, т. е. когда число линейно независимых уравнений системы (3.14) меньше числа переменных n. Тогда, если система совместна, у нее существует бесчисленное множество решений. При этом n – r переменным мы можем придавать произвольные значения. Будем называть эти переменные свободными, а остальные r переменных – базисными.
Пример 3.3.
Рассмотрим систему двух уравнений с четырьмя неизвестными:
2x1 – x2 + x3 – x4 = 1,
–x1 + x2 – 2x3 + x4 = 2. (3.17)
Ранг этой системы равен r = 2 (уравнения линейно независимы). Выберем в качестве свободных переменных, например, x3 и x4, а в качестве базисных – x1 и x2. Выразим базисные переменные через свободные.
2x1 – x2 = 1 – x3 + x4,
–x1 + x2 = 2 + 2x3 – x4.
Складывая эти уравнения, получим
x1 = 3 + x3.
Умножая второе уравнение на 2 и складывая со вторым, получим
x2 = 5 + 3x3 – x4.
Таким образом, базисные переменные x1 и x2 выражены через свободные x3 и x4. Свободным переменным x3 и x4 можно придавать любые значения. При этом всегда будем получать совокупность значений x1, x2, x3, x4, удовлетворяющую системе уравнений. Например, полагая x3 = x4 = 0, получим x1 = 3, x2 = 5. Эти значения удовлетворяют системе уравнений (3.17). Полагая x3 = 1, x4 = 2, получим x1 = 4, x2 = 6. Эти значения также удовлетворяют системе уравнений (3.17).
Вообще, если ранг системы равен r, то всегда можно выразить какие-то r базисных переменных через n – r остальных свободных и, придавая свободным переменным любые значения, получить бесчисленное множество решений системы.
В дальнейшем для простоты будем считать, что все уравнения-ограничения ЗЛП линейно независимы, при этом ранг системы r равен числу уравнений m, т. е.
r = m < n.
В этом случае система имеет бесчисленное множество решений. Если среди них существуют какие-то решения, для которых все x1, x2, …, xn неотрицательны, то каждое из них допустимо. Возникает задача – найти среди допустимых решений оптимальное, т. е. такое решение x1, x2, …, xn при котором линейная функция
f(x1, x2, …, xn) = с1x1+ с2x2 + …+cnxn
обращается в минимум.
Без ограничения общности можно считать, что первые m переменных x1, x2, …, xm являются базисными, а остальные n – m переменных xm+1, xm+2, …, xn – свободные. Перепишем систему (3.14) в следующем виде:
a11x1+ … + a1mxm + a1,m+1xm+1 +…+ a1nxn = b1,
………………………………………………… (3.18)
am1x1+ … + ammxm+ am,m+1xm+1 +…+ amnxn = bm.
Выразим базисные переменные через свободные
:x1= b1 – (a1,m+1xm+1 +…+ a1nxn ),
………………………….
xm = bm – am,m+1xm+1 +…+ amnxn .
или
xi = bi – 
, i =1,…, m. (3.19)
Если в равенстве (3.19) положить свободные переменные равными нулю, xm+1= xm+2 = …= xn = 0, то получим частное допустимое решение системы (3.18)
xi = bi, i =1,…, m или x0 = (b1, b2, …, bm, 0, …, 0).
Если все компоненты этого решения неотрицательны, т. е. bI ? 0,, i =1,…, m, то назовем это решение допустимым базисным (или опорным) решением.
Если допустимое базисное решение содержит более, чем n – m нулевых компонент (т. е. хотя бы одна базисная переменная обращается в нуль), то решение называется вырожденным, в противном случае – невырожденным.
Выбор m базисных переменных из общего числа n переменных может быть реализован различными способами. Число таких способов равно 
Следовательно, число допустимых базисных решений не превосходит C
.
Пример 3.4.
Найти все базисные и допустимые базисные решения системы уравнений
x1 + x2 + x3 = 2, (3.20)
x1 – x2 + x4 = 1,
x1, x2, x3, x4 ? 0.
Число линейно независимых уравнений m =2, число переменных n =4. Число способов выбора базисных переменных C = C
= 6. Приравнивая нулю свободные переменные, получим все 6 вариантов частных допустимых решений системы (3.20):
| Базисные переменные | Свободные переменные | Частное решение |
| x1, x2 x1, x3 x1, x4 x2, x3 x2, x4 x3, x4 | x3, x4 x2, x4 x2, x3 x1, x4 x1, x3 x1, x2 | (3/2, 1/2, 0, 0) (1, 0, 1, 0) (2, 0, 0, –1) (0, –1, 3, 0) (0, 2, 0, 3) (0, 0, 1, 1) |
Из этих шести допустимых решений только четыре удовлетворяют условию неотрицательности x1, x2, x3, x4 ? 0. Следовательно, существует четыре допустимых базисных решения: (3/2, 1/2, 0, 0), (1, 0, 1, 0), (0, 2, 0, 3), (0, 0, 1, 1).
Можно показать, что каждое допустимое базисное решение определяет угловую точку (вершину) множества допустимых решений, которое представляет собой выпуклый многогранник в пространстве размерности n – m и наоборот, каждой вершине многогранника допустимых решений соответствует допустимое базисное решение.
Соотношения (3.19) позволяет выразить базисные переменные через свободные. Используя эти соотношения, выразим целевую функцию f(x1, x2, …, xn) = 
через свободные переменные:
f(x1, x2, …, xn) = 
= 
+ 
= 
(bi – ) + =
+ 
,
где
= f(x0)= f(b1, b2,…, bm, 0, …, 0),
pj = cj – 
.
Итак, для допустимого базисного решения x0 = (b1, b2,…, bm, 0, …, 0) ЗЛП имеет следующий канонический вид:
f(x1, x2, …, xn) = f(x0) + ® min, (3.21)
xi + = bi ,i =1,…, m, (3.22)
xj ? 0, j = 1, 2, …, n. (3.23)
Этой форме записи соответствует так называемая симплекс-таблица:
| xm+1 … xj … xn | ||
| x1 . . . xi . . . xm | a1,m+1 … a1j … a1n . . . . . . . . . ai,m+1 … aij … ain . . . . . . . . . am,m+1 … amj … amn | b1 . . . bi . . . bm |
| pm+1 … pj … pn | – f (x0) |
Пример 3.5.
Составить одну из симплекс таблиц примера 3.
f(x1, x2, x3, x4) = –x1– 2x2 ® min
x1 + x2 + x3 = 2, (3.24)
x1 – x2 + x4 = 1,
x1, x2, x3, x4 ? 0.
В качестве базисных переменных удобно выбрать x3, x4. Тогда переменные x1, x2 будут свободными.
Из (3.24) выразим базисные переменные через свободные:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
