Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ И ГЕОМЕТРИИ ВЫПУКЛЫХ МНОЖЕСТВ. 2.1. Система т линейных уравнений с л переменными




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

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

й, ,х, + а12х2+.. .+a{jXj+.. .+alnx„ = Ь{, о21х, + а22х2+.. .+a2JXj+.. .+а2пх„ = Ъ2,

о,,х, + ai2x2+.. .+ajjXj+...+ainx„ b,,

amiX\ + ат2х2+.. .+amJXj+.. .+атпх„ = bm, или в краткой записи

и

2.atxj =b( (/ = 1,2,...,/и).

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

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

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


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

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

ДИТ С„ .

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

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

2xj +x2 + 2jc3 - х4 = 0.

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

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

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

ных

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

-2 2

менных Хз, Х4

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

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




           
   
     
 
 
 

Глава 2

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

°п ап

а
И
*0.

i ат2

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

ед + al2x2+...+almxm ж ft, -alm+lxm+l-...-alnx„, апхх + а22х2+.. .+ахт ж ^ - а2т+1хт+1-.. .-а2пхп,

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

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

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

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

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

2.

2*1 + х> + 2*1

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

Х\ Х22Xj Х4,

х + х2 = 2х3 + х4.


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



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

Хз = ей х» = с2).

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

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

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

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

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

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

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

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

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



Глава 2


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



 


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

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

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


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