Полная версия

Главная arrow Экономика arrow Исследование операций в экономике

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

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

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

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

(2.1)

или в краткой записи

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

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

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

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

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

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

Выясним, могут ли быть основными переменные х,, х2. Так как определитель матрицы из коэффициентов при этих переменных то xv х2 могут быть основными переменными. Рассуждая аналогично, найдем, что могут быть основными переменные xv х.,; .г,, xv но не могут быть основными х2, х3; х2, х4; х3, х4, так как в трех последних группах переменных соответствующие определители равны нулю (например, для переменных х3, х4 определитель). ►

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

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

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

Оставим в левых частях уравнений системы (2.1) члены с переменными х,, х2, ..., хт, а члены с переменными x,n + v xm+2' •••' хп перенесем в правые части. Получим

Задавая неосновным переменным х + 1, хт+2,..., хп произвольные значения, каждый раз будем получать новую систему с новыми свободными членами bv b2, ..., Ьт. Каждая из полученных систем будет иметь один и тот же определитель |Л| ф 0, следовательно, в силу теоремы Крамера каждая из этих систем будет иметь единственное решение. Так как получаемых таким образом систем бесконечно много, то и система (2.1) будет иметь бесконечное множество решений. ■

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

Решение. В задаче 2.1 установлено, что основными могут быть переменные xr х2; xv х3; xv х4. Возьмем в качестве основных переменные х,, х2, а переменные х3, х4 будем считать неосновными и перенесем их с соответствующими коэффициентами в правые части уравнений системы. Получим

Решая данную систему любым способом, найдем х, =2/3; х2 = 2/3 – 2х3 + х4. Задавая неосновным переменным х3 и х4 произвольные значения, например х3 =cv х4 2, получим бесконечное множество решений этой системы (х, = 2/3; х2 = 2/3-2С[ + с2; х3 = с,; х4 = с2). ►

Решение X = (х,,х2,..., хи) системы (2.1) называется допустимым[1], если оно содержит лишь неотрицательные компоненты, т.е. х, > 0 для любых/ =1,2,..., п. В противном случае решение называется недопустимым. Так, в задаче 2.2 решение системы при с{ =2, с2 = 5, т.е. Х{ = (2/3; 5/3; 2; 5), является допустимым, а при с4 =2, с2 = 1, т.е. Х2 = (2/3; – 7/3; 2; 1), – недопустимым.

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

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

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

2.3. Найти все базисные решения системы, приведенной в задаче 2.1.

Решение. В задаче 2.1 было установлено, что существует три группы основных переменных: χν х2; х,, х3; χν х4, т.е. число базисных решений равно 3.

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

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

Если взять за основные переменные ху х3 и приравнять нулю соответствующие неосновные переменные х2 = х4 = 0, получим второе базисное решение Х2 = (2/3; 0; 1/3; 0) – также допустимое. Аналогично можно найти и третье базисное решение Х3 =(2/3; 0; 0; -2/3) – недопустимое. ►

Совместная система (2.1) имеет бесконечно много решений, из них базисных решений – конечное число, не превосходящее С".

  • [1] Именно такие решения представляют интерес в большинстве задач линейного программирования.
 
<<   СОДЕРЖАНИЕ   >>