Глава 2
СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ и НЕРАВЕНСТВ, ВЫПУКЛЫЕ МНОЖЕСТВА
2.1. Система /п-линейных уравнений с п переменными
Рассмотрим следующую систему т-линейных уравнений, содержащую п переменных, полагая т<п:
(2.1)
ml 1 mz Iтп п т
Любые т переменных системы т линейных уравнений с п неизвестными {т<п) называются основными или базисными, если определитель матрицы коэффициентов при них не равен нулю. Общее число комбинаций базисных переменных не превосходит
числа .
{п-т)\т\
Эта система может быть также запи-сана в виде: Z,yy = ,» = U...,.
Или в матричном виде: Ах = Ь.
В задачах линейного программирования рассматриваются системы, в которых ранг г матрицы системы А = (<3f,y), / = , j = меньше
числа переменных, т.е. г<п. Это означает, что наибольшее число независимых переменных уравнений системы равно г. Далее будем полагать, что в системе (2.1) число независимых уравнений равно т, т.е. г = т.
Любые т переменных системы /w-линейных уравнений с п неизвестными (w < п) назьюаются основными, или базисными, если определитель матрицы коэффициентов при них не равен нулю. Тогда остальные п-т переменных назьюаются небазисными. Учитьшая, что максимально возможное
число сочетаний из п столбцов по т равно = ----, общее число
п {п-т)\т\
комбинаций базисных переменных не превосходит числа С .
Рассмотрим следующий пример. Найти все возможные группы базисных переменных в системе
- 2 - ЗХз + Х4 = 1
3xi + Х2 + Зхз - Х4 = 2.
Общее число комбинаций базисных переменных не превосходит чис-
Возможные комбинации базисных переменных {хрХз}, {рз}» {хрХ4}, {х2,Хз}, {х2,Х4}, {xjjX} . Выясним, например, являются ли базисными переменные {хрХ4}.
Рассмотрим определитель из столбцов матрицы при переменных
Xi,X4
1 1
3 -1
= 1 3= 40.
Следовательно переменные xi,X4 являются базисными. Рассматривая определители для всех перечисленных комбинаций переменных, получили, что базисными являются комбинации {хрХз}, {рз}» {i4} • Комбинации {х2,Хз}, {x2,X4}, {x3,X4} являются небазисными.
Например, для {:2,X4} получили
-1 1 1 -1
= 1-1=0.
Для дальнейшего исследования системы (2.1) докажем следующую теорему.
Теорема 2.1. Если для системы w-линейных уравнений с п неизвестными (w <«) ранг матрицы A = {aj, / = l,...,w, 7=1,...,« равен т.е.
существует хотя бы одна группа базисных переменных, то эта система является неопределенной, причем каждому набору значений небазисных переменных соответствует одно решение системы.
Доказательство, Пусть Xi,...,x - основные переменные (если это не так, то нумерацию соответствующих переменных можно изменить), т.е. определитель матрицы
*т\
Оставим в левой части уравнений (2.1) члены с переменными xi,...,x, а члены с переменными xi,...,x„ перенесем в правую часть.
Получим
111 + 122 + - + щХп = 1 -" - "
211 + 222 + - + щХп = 2 - 2mlml " - " Inn(2.2)
.тЛ +m22 + - + тЛ = *m " mmlml ---mA
Задавая неосновным небазисным переменнымпроизволь-
ные значения, каждый раз будем получать новую систему с новыми сво-бодными членами ,",Ь .
Каждая из полученных систем будет иметь один и тот же определитель 117 О.
Следовательно, в силу теоремы Крамера, каждая из этих систем будет иметь единственное решение. Так как полученных таким образом систем бесконечно много, то система (2.1) будет иметь бесконечное множество решений.
Пример. Решить систему уравнений
- 2 - 2X3 + Х4 = О
2xi + Х2 - 2x3 - Х4 = 0.
Базисными переменными здесь являются переменные {хрХз}, {х1,хз}, {xi,X4}. Выберем в качестве базисных переменных Xj, Х2, а переменные Х3, Х4 будем считать небазисными и перенесем их с соответствующими коэффициентами в правые части системы.
Получим:
Xj Х2 - 2X3 Х4 2xi +Х2 = 2X3 +Х4.
Решая данную систему, найдем Xj = 4/Зхз, Х2 = Х4 - 2/Зхз.
Задавая небазисными переменными произвольные значения, например Хз = q, Х4 = С2, получим бесконечное множество решений этой системы вида Xi = 4/3ci, Х2 = С2 - 2/3ci, Х3 = q, X4 = C2.
Решение X = [x,...,x) системы (2.1) будем называть допустимым, если оно содержит лишь неотрицательные компоненты, т.е. Xj > О для любых 7 =!,...,«. В противном случае решение является недопустимым. Среди всего множества решений системы вьщеляют так называемые базисные решения.