Элементы линейной алгебры и геометрии выпуклых множеств. 2. 1. Система т линейных уравнений с л переменными

⇐ ПредыдущаяСтр 5 из 7Следующая ⇒

2.1. Система т линейных уравнений с л переменными

Система т линейных уравнений с л переменными имеет вид

й,, х, + а₁₂х₂+...+a_{_jXj+...+a_lnx„ = Ь_{, о₂₁х, + а₂₂х₂+...+a₂_JXj+...+а_2пх„ = Ъ₂,

о,, х, + a_i₂x₂+...+ajjXj+...+a_inx„ ■ b,,

^amiX\ + а_т2х₂+...+a_mJXj+...+а_тпх„ = b_m, или в краткой записи

2.a_txj =b₍ (/ = 1, 2,..., /и).

В задачах линейного программирования представляют интерес системы, в которых ранг г матрицы системы А = (аф, /=1, 2,..., т; у=1, 2,..., п, или, что то же самое, максимальное число независимых уравнений системы г меньше числа переменных, т.е. г < п. Будем полагать, что в системе (2.1) все т уравнений системы независимы, т.е. г = т и соответственно т < п.

Любые т переменных системы т линейных уравнений с п переменными (т < п) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля¹.

В литературе такой определитель часто называют базисным минором матрицы А.

Тогда остальные п—т переменных называются неосновными (или свободными).

Основными могут быть разные группы из п переменных. Максимально возможное число групп основных переменных равно числу способов выбора т переменных из их общего числа я, т.е. числу сочетаний С". Но так как могут встретиться случаи, когда определитель матрицы коэффициентов при т переменных равен нулю, то общее число групп основных переменных не превосхо-

ДИТ С„.

> 2.1. Найти все возможные группы основных переменных в системе

Х\ — Х₂ — lX" \ + X4 — vJ,

2xj +x₂ + 2jc₃ - х₄ = 0.

Решение. Общее число групп основных переменных не более чем С\ =4-3/2 = 6, т.е. возможные группы основных переменных: х\, х₂; х\, ху, х\, Х4, х₂, ху, х₂, х₄; х₃, х₄.

Выясним, могут ли быть основными переменные х\, х₂. Так как определитель матрицы из коэффициентов при этих перемен-

= 1 • 1 - 2(-1) = 3 * 0, то х\, х₂ могут быть основными

ных

переменными. Рассуждая аналогично, найдем, что могут быть основными переменные х\, ху, х\, х₄, но не могут быть основными х₂, ху, х₂, Х4\ *з, ^х4> ^так ^как ^в ^ТР^ех последних группах переменных соответствующие определители равны нулю (например, для пере-

-2 2

0»

менных Хз, Х4

Для решения системы (2.1) при условии m < n докажем следующую теорему.

Теорема 2.1. Если для системы т линейных уравнений с п переменными (т < п) ранг матрицы коэффициентов при переменных равен т, т.е. существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произвольному набору значений неосновных переменных соответствует одно решение системы.

Глава 2

D Пусть, например, х\, Х2,..., х_т — основные переменные (если это не так, то нумерацию соответствующих переменных можно изменить), т.е. определитель матрицы

°п ^ап

^а2т

*0.

i ^ат2

Оставим в левых частях уравнений системы (2.1) члены с переменными х\, Х2,..., х_т, а члены с переменными х_т+\, х_т+2,..., х_п перенесем в правые части. Получим

ед + a_l₂x₂+...+a_lmx_m ж ft, -a_lm₊_lx_m₊_l-...-a_lnx„, а_пх_х + а₂₂х₂+...+а_2тх_т ж ^ - а_2т+1х_т+1-...-а_2пх_п,

^ат\^х1+^ат2^х2+--+^атт^хт = К - а_тт+хХ_т+1-...-а_т„Х„.

Задавая неосновным переменным х_т+ь х_т+2,..., х„ произвольные значения, каждый раз будем получать новую систему с новыми свободными членами b{, b^,..., b^. Каждая из полученных

систем будет иметь один и тот же определитель \А\ *■ 0, следовательно, в силу теоремы Крамера каждая из этих систем будет иметь единственное решение. Так как получаемых таким образом систем бесконечно много, то и система (2.1) будет иметь бесконечное множество решений ■.

^ 2.2. Решить систему уравнений

I — Х₂ — ZX-i + Хл — U,

2.

2*1 + х> + 2*1

Решение. В задаче 2.1 установлено, что основными могут быть переменные Х\, Х2, *ь ^ХУ, *ь *4- Возьмем в качестве основных переменные х\, Х2, а переменные *з, *4 будем считать неосновными и перенесем их с соответствующими коэффициентами в правые части уравнений системы. Получим

Х\ — Х₂ — 2Xj — Х4 ,

2х_х + х₂ = 2х₃ + х₄.

Элементы линейной алгебры и геометрии ________________________ 31

Решая данную систему любым способом, найдем х\ = 2/3; _ 2/3 — 2*з ⁺ *4- Задавая неосновным переменным дс₃ и х* произвольные значения, например, х₃ ⁼ ^сь *4 ⁼ ^сг> получим бесконечное множество решений этой системы {х\ = 2/3; х₂ = 2/3 - 2q + с₂;

_Хз = ей х» = с₂). ►

Решение Х- (х\, х₂,..., х„) системы (2.1) называется допустимым¹, если оно содержит лишь неотрицательные компоненты, т.е. х г 0 для любых; = 1, 2,..., п. В противном случае решение называется недопустимым. Так, в задаче 2.2 решение системы при с\ = 2, с₂ = 5, т.е. Х\ = (2/3; 5/3; 2; 5) является допустимым, а при с\ -2, с₂ =1, т.е. Х₂ = (2/3; — 7/3; 2; 1) — недопустимым.

Среди бесконечного множества решений системы выделяют так называемые базисные решения.

Базисным решением системы т линейных уравнений с п переменными называется решение, в котором все п—т неосновных переменных равны нулю.

В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют, опорные планы. Число базисных решений является конечным, так как оно равно числу групп основных переменных, не превосходящему С™. Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным. > 2.3. Найти все базисные решения системы, приведенной в задаче 2.1.

Решение. В задаче 2.1 было установлено, что существует три группы основных переменных Х), ху, Х\, ху, Xj, Xj, т.е. число базисных решений равно 3.

Найдем первое базисное решение, взяв в качестве основных переменные х\, Х2 и неосновных — переменные хз. *4- Приравняв неосновные переменные нулю, т.е. при хз = Xt = 0, получим систему уравнений в виде

х, - х₂ = 0, 2х_х + х₂ ■ 2,

откуда х\ = 2/3; х₂ = 2/3. Следовательно, первое базисное решение системы Х\ = (2/3; 2/3; 0; 0) — допустимое.

¹ Именно такие решения представляют интерес в большинстве задач линейного программирования.

Глава 2

Элементы линейной алгебры и геометрии

Если взять за основные переменные х_ь хз и приравнять нулю соответствующие неосновные переменные х-± = х$ = 0, получим второе базисное решение Xi = (2/3; 0; 2/3; 0) — также допустимое. Аналогично можно найти и третье базисное решение Лз = (2/3; 0; 0; — 2/3) — недопустимое.^

Совместная система (2.1) имеет бесконечно много решений, из

них базисных решений — конечное число, не превосходящее С™.

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒

Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2025 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал