Как найти все опорные решения системы

Опорные решения системы линейных уравнений.

Рассмотрим систему
из m линейных уравнений с n
неизвестными, причем m<n:

(2.8)

Базисом системы
линейных уравнений называется максимальное
количество линейно независимых векторов
системы. Для данной системы это количество
равно m . Воспользуемся методом
последовательных исключений неизвестных
и выделим в системе некий исходный
единичный базис:

(2.9)

В полученной
системе единичные вектора

называются базисными, а вектора


— свободными.

О п р е д е л е н и е  5. Базисными
решениями называются решения системы,
получаемые при приравнивании свободных
неизвестных нулю.

О п р е д е л е н и е  6. Базисное
решение называется невырожденным,
если все базисные переменные полученного
решения ненулевые, в противном случае
базисное решение называется вырожденным.

Очевидно, что
базисные решения проще находить, если
система приведена к единичному базису,
поэтому отыскание всех базисных решений
сводится к последовательному преобразованию
системы к всевозможным единичным
базисам. Этого можно достигнуть путем
последовательных преобразований
однократного замещения.

Для выполнения
одного преобразования однократного
замещения нужно выбрать среди не
единичных столбцов коэффициентов
отличный от нуля разрешающий элемент
A_qp и провести одно
преобразование схемы последовательных
исключений. Тогда разрешающий ( p-й )
столбец коэффициентов превратится в
единичный, а, наоборот, единичный столбец,
имеющий координату 1 в разрешающем q-м
уравнении, станет не единичным. Это
соответствует переходу в число базисных
неизвестного x_p и, наоборот,
выводу из числа базисных неизвестного,
относительно которого было разрешено
q-е уравнение.

При этом нужно
следить за тем, чтобы в процессе
преобразований не повторялся ранее
встречавшийся базис. Для этого необходимо
систематизировать расчеты.

Важно также
запомнить, что если r — количество
базисов, которые могут быть выделены
из данной системы, то
.
Причем равенство достигается только в
том случае, если ни один из векторов ни
при каком из базисов не является
вырожденной комбинацией.

О п р е д е л е н и е  7. Опорными
решениями системы называются те
базисные решения, которые имеют все
неотрицательные значения неизвестных.

Конечно, их можно
выделить, если найдены все базисные
решения, но такой путь ведет к чрезвычайно
сложным расчетам. Если же выбирать
разрешающий элемент из дополнительных
условий, то те же преобразования
однократного замещения обеспечат
переход не просто к базисным, а к опорным
решениям. Эти дополнительные условия
заключаются в следующем:

1) разрешающий
столбец (номер p) выбирается так,
чтобы в нем оказался хотя бы один
положительный элемент A_ip >
0;

2) разрешающая
строка (номер q) выбирается из
условия, чтобы отношение

было наименьшим из значений

при A_ip > 0.

После выбора
разрешающего элемента дальнейшие
вычисления ведутся согласно обычным
правилам преобразований однократного
замещения.

Как и при определении
базисных решений, здесь также необходимо
следить, чтобы на какой либо итерации
не вернуться к ранее найденному опорному
решению. Это условие дополнительно
ограничивает выбор разрешающего
элемента.

Ï ð è ì å ð  3.  С
помощью преобразований однократного
замещения найти все базисы и опорные
решения следующей системы уравнений:

Р е ш е н и е
. Количество опорных решений
данной системы линейных уравнений
.

A1	A2	A3	A4	A5	A0	A0/A1	A0/A2			Опорные решения
-2	3	1	0	0	9		3		Базис	x1	x2	x3	x4	x5
1	1	0	1	0	8	8	8		A3,A4,A5	0	0	9	8	9
3	-2	0	0	1	9	3			A3,A4,A1	3	0	15	5	0
					min	3			A1,A2,A3	5	3	10	0	0
									A1,A2,A5	3	5	0	0	10
A1	A2	A3	A4	A5	A0	A0/A2	A0/A5	Шаг 1	A2,A4,A5	0	3	0	5	15
0	1,667	1	0	0,667	15	9	22,5
0	1,667	0	1	-0,33	5	3
1	-0,67	0	0	0,333	3		9
					min	3
A1	A2	A3	A4	A5	A0	A0/A5	A0/A4	Шаг 2
0	0	1	-1	1	10	10
0	1	0	0,6	-0,2	3		5
1	0	0	0,4	0,2	5	25	12,5
					min	10
A1	A2	A3	A4	A5	A0	A0/A4	A0/A3	Шаг 3
0	0	1	-1	1	10		10
0	1	0,2	0,4	0	5	12,5	25
1	0	-0,2	0,6	0	3	5
					min	5
A1	A2	A3	A4	A5	A0	A0/A1	A0/A3	Шаг 4
1,667	0	0,667	0	1	15	9	22,5
-0,67	1	0,333	0	0	3		9
1,667	0	-0,33	1	0	5	3
					min	3

Дальнейший перебор
не приводит к нахождению новых опорных
решений.

В предыдущем
примере заданная система уравнений
имела некоторый выделенный исходный
базис. Если система не приведена к
единичному базису, то для его нахождения
необходимо выполнить следующую
последовательность действий:

1) начинаем с
преобразования системы методом
последовательных исключений, причем
выбор разрешающего элемента на начальном
этапе может быть совершенно произвольным;

2) если после
приведения системы к единичному базису
появились отрицательные свободные
элементы, выберем среди них наибольший
по абсолютной величине и вычтем почленно
выделенное таким образом уравнение
из всех остальных уравнений с отрицательными
свободными членами. Само же выделенное
уравнение перепишем, умножив все
коэффициенты на -1;

3) дальнейшие
преобразования системы будем проводить
согласно правилам однократного замещения,
выбирая разрешающий столбец из условия,
чтобы он имел в выделенной строке
положительный элемент. Для выбора
разрешающей строки вычисляем отношения
A_io к A_ip и берем
в качестве разрешающей строку с
минимальным полученным значением;

4) предположим,
что после выполнения некоторого
количества итераций (3) мы все же не
смогли выделить базис полностью и пришли
к таблице, в которой выделенная строка
не имеет ни одного положительного
элемента, кроме свободного члена.
Очевидно, что процесс последовательных
преобразований на этом обрывается, ибо
становится невозможным выбор разрешающего
столбца по указанному выше принципу.
Нетрудно прийти к выводу, что в этом
случае исходная система уравнений не
имеет ни одного решения с неотрицательными
значениями неизвестных, в том числе и
опорного решения, или, как говорят,
несовместна в области неотрицательных
(допустимых) решений.

В случае, если
исходная система имеет хотя бы одно
опорное решение, после конечного числа
описанных выше итераций будет получено
исходное опорное решение.

Ï ð è ì å ð 4.  Найти
исходное опорное решение системы
уравнений, приведя ее к единичному
базису при неотрицательных свободных
членах:

Р е ш е н и е
. 

A1	A2	A3	A4	A5	A6	A7	A0	A0/Ak	Исходная матрица
1	1	0	-3	4	1	0	-6
1	-1	1	5	-4	6	0	8
0	1	-1	-6	5	-4	0	-12
1	0	0	1	3	1	1	-3
A1	A2	A3	A4	A5	A6	A7	A0	A0/Ak	Шаг 1
1	1	0	-3	4	1	0	-6
0	-2	1	8	-8	5	0	14
0	1	-1	-6	5	-4	0	-12
0	-1	0	4	-1	0	1	3
A1	A2	A3	A4	A5	A6	A7	A0	A0/Ak	Шаг 2
1	1	0	-3	4	1	0	-6
0	-2	1	8	-8	5	0	14
0	-1	0	2	-3	1	0	2
0	-1	0	4	-1	0	1	3
A1	A2	A3	A4	A5	A6	A7	A0	A0/Ak	Шаг 3
1	2	0	-5	7	0	0	-8
0	3	1	-2	7	0	0	4
0	-1	0	2	-3	1	0	2
0	-1	0	4	-1	0	1	3
A1	A2	A3	A4	A5	A6	A7	A0	A0/A4	Шаг 4
-1	-2	0	5	-7	0	0	8	1,6
0	3	1	-2	7	0	0	4
0	-1	0	2	-3	1	0	2	1
0	-1	0	4	-1	0	1	3	0,75
A1	A2	A3	A4	A5	A6	A7	A0	A0/Ak	Шаг 5
-1	-0,75	0	0	-5,75	0	-1,25	4,25
0	2,5	1	0	6,5	0	0,5	5,5
0	-0,5	0	0	-2,5	1	-0,5	0,5
0	-0,25	0	1	-0,25	0	0,25	0,75

Исходная система
уравнений не имеет опорных решений, так
как несовместна в области неотрицательных
(допустимых) решений.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

Содержание:

Системы уравнений, как и отдельные уравнения, используют для решения сложных и необходимых задач. Системы уравнений бывают с двумя, тремя и более переменными. В этой главе вы ознакомитесь с простейшими системами двух уравнений с двумя переменными. Основные темы лекции:

• уравнения с двумя переменными;
• график линейного уравнения;
• системы уравнений;
• способ подстановки;
• способ сложения;
• решение задач составлением системы уравнений.

Уравнения с двумя переменными

До сих пор мы рассматривали уравнение с одной переменной. Однако существуют задачи, решение которых приводит к уравнениям с двумя переменными.

Пример:

На 22 руб. купили несколько книжек по 5 руб. и географических карт — по 3 руб. Сколько купили книжек и карт?

Решение:

Пусть купили х книжки у карт. За книжки заплатили 5х руб., а за карты — 3у руб. Всего заплатили 22 руб., то есть, 5х + Зу = 22.

Это уравнение с двумя переменными. Приведём и другие примеры таких уравнений с двумя переменными:

Уравнение вида ах + by = с, где а, b, с — данные числа, называется линейным уравнением с двумя переменными х и у. Если

Примеры линейных уравнений:

два первых из них — уравнение первой степени с двумя переменными.

Паре чисел х = -1 и у = 9 удовлетворяет уравнение 5х + Зу -= 22, так как А пара чисел х = 1 и у = 2 этому уравнению не удовлетворяет, поскольку

Каждая пара чисел, удовлетворяющая уравнение с двумя переменными, т. е. обращающая это уравнение в верное равенство, называется решением этого уравнения.

Обратите внимание: одно решение состоит из двух чисел, на первом месте записывают значение х, на втором — у. Корнями их не называют.

Чтобы найти решение уравнения с двумя переменными, следует подставить в уравнение произвольное значение первой неременной и, решив полученное уравнение, найти соответствующее значение второй переменной.

Для примера найдем несколько решений уравнения

Если х = 1, то отсюда у = -2. Пара чисел х = 1 и у = -2 — решение данного уравнения. Его записывают ещё и так: (1; -2). Придавая переменной х значения 2, 3, 4, . , так же можно найти сколько угодно решений уравнения: (2; 1), (3; 4), (4; 7), (5; 10), . Каждое уравнение первой степени с двумя переменными имеет бесконечно много решений.

Уравнение также имеет бесконечно много решений, но сформулированную выше задачу удовлетворяет только одно из них: (2; 4).

Два уравнения с двумя переменными называют равносильными, если каждое из них имеет те же решения, что и другое. Уравнения, не имеющие решений, также считаются равносильными.

Для уравнения с двумя переменными остаются справедливыми свойства, сформулированные для уравнений с одной переменной.

Обе части уравнения с двумя переменными можно умножить или разделить на одно и то же число, отличное от нуля. Любой член такого уравнения можно перенести из одной части уравнения в другую, изменив его знак на противоположный. В результате получается уравнение, равносильное данному.

Например, уравнение можно преобразовать так: . Каждое из этих уравнений равносильно друг другу.

Иногда возникает потребность решить уравнение с двумя переменными во множестве целых чисел, то есть определить решения, являющиеся парами целых чисел. Способы решения таких уравнений определил древнегреческий математик Диофант (III в.), поэтому их называют диофантовыми уравнениями. Например, задача о книжках и картах сводится к уравнению где х и у могут быть только целыми (иногда натуральными) числами.

Переменную у из этого уравнения выразим через х:

Будем подставлять в равенство вместо х первые натуральные числа до тех пор, пока не получим целое значение переменной у. Это можно делать устно. Если х = 2, то у = 4. Других натуральных решений уравнение не имеет. Поэтому задача имеет единственное решение: 2 книги и 4 карты.

Пример:

Решение:

а) При любых значениях х и у значения выражения не может быть отрицательным числом. Поэтому уравнение не имеет решений.

б) Значение выражения равно нулю только при условии, когда x -3 = 0 и y = 0. Значит, уравнение имеет только одно решение: х = 3, у = 0.

Пример:

Составьте уравнение с двумя переменными, решением которого будет пара чисел (1; -5).

Решение:

Пишем любой двучлен с переменными х и у, например Если х = 1, а у = -5, то значение даного двучлена равно 28. Следовательно, уравнение удовлетворяет условие задачи.

Есть много других линейных уравнений с двумя переменными, имеющих такое же решение (1; -5).

График линейного уравнения с двумя переменными

Рассмотрим уравнение Давая переменной х значения -2, -1,0,1,2, 3. найдём соответствующие значения переменной у. Будем иметь решение данного уравнения: (-2; -б), (-1; -4,5), (0; -3),

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Примеры решения СЛАУ

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

Перед изучением примеров решения задач советуем изучить теоретический материал по СЛАУ, прочитать все теоремы и методы решения. Список тем находится в правом меню.

Примеры по темам:

СЛАУ: основные понятия, виды

Задание. Проверить, является ли набор $<0,3>$ решением системы $left<begin 3 x-2 y=-6 \ 5 x+y=3 endright.$

Решение. Подставляем в каждое из уравнений системы $x=0$ и $y=3$ :

$$3 x-2 y=-6 Rightarrow 3 cdot 0-2 cdot 3=-6 Rightarrow-6=-6$$ $$5 x+y=3 Rightarrow 5 cdot 0+3=3 Rightarrow 3=3$$

Так как в результате подстановки получили верные равенства, то делаем вывод, что заданный набор является решением указанной СЛАУ.

Ответ. Набор $<0,3>$ является решением системы $left<begin 3 x-2 y=-6 \ 5 x+y=3 endright.$

Задание. Систему $left<begin x-y+z-4 t=0 \ 5 x+y+t=-11 endright.$ записать в матричной форме и выписать все матрицы, которые ей соответствуют.

Решение. Заданную СЛАУ записываем в матричной форме $A cdot X=B$ , где матрица системы:

$$A=left(begin 1 & -1 & 1 & -4 \ 5 & 1 & 0 & 1 endright)$$

$$A=left(begin 1 & -1 & 1 & -4 \ 5 & 1 & 0 & 1 endright)$$

вектор-столбец свободных коэффициентов:

то есть, запись СЛАУ в матричной форме:

$$left(begin 1 & -1 & 1 & -4 \ 5 & 1 & 0 & 1 endright)left(begin x \ y \ z \ t endright)=left(begin 0 \ -11 endright)$$

Задание. Записать матрицу и расширенную матрицу системы $left<begin 2 x_<1>+x_<2>-x_<3>=4 \ x_<1>-x_<2>=5 endright.$

Решение. Матрица системы $A=left(begin 2 & 1 & -1 \ 1 & -1 & 0 endright)$ , тогда расширенная матрица $tilde=(A mid B)=left(begin 2 & 1 & -1 & 4 \ 1 & -1 & 0 & 5 endright)$

Критерий совместности системы

Задание. При каких значениях $lambda$ система $left<begin 2 x_<1>-x_<2>+x_<3>+x_<4>=1 \ x_<1>+2 x_<2>-x_<3>+x_<4>=2 \ x_<1>+7 x_<2>-4 x_<3>+2 x_<4>=lambda endright.$ будет совместной?

Решение. Ранг матрицы равен количеству ненулевых строк после приведения этой матрицы к ступенчатому виду. Поэтому записываем расширенную матрицу системы $tilde$ (слева от вертикальной черты находится матрица системы $A$ ):

и с помощью элементарных преобразований приводим ее к ступенчатому виду. Для этого вначале от второй строки отнимаем две вторых строки, а от третьей вторую, в результате получаем:

Третью строку складываем с первой:

и меняем первую и вторую строки матрицы местами

Квадратные СЛАУ. Матричный метод решения

Теоретический материал по теме — матричный метод решения.

Задание. Найти решение СЛАУ $left<begin5 x_<1>+2 x_<2>=7 \ 2 x_<1>+x_<2>=9endright.$ матричным методом.

Решение. Выпишем матрицу системы $left<begin 5 x_<1>+2 x_<2>=7 \ 2 x_<1>+x_<2>=9 endright.$ и матрицу правых частей $B=left(begin 7 \ 9 endright)$ . Найдем обратную матрицу для матрицы системы. Для матрицы второго порядка обратную можно находить по следующему алгоритму: 1) матрица должна быть невырождена, то есть ее определитель не должен равняться нулю: $|A|=1$ ; 2) элементы, стоящие на главной диагонали меняем местами, а у элементов побочной диагонали меняем знак на противоположный и делим полученные элементы на определитель матрицы. Итак, получаем, что

$$X=left(begin x_ <1>\ x_ <2>endright)=A^ <-1>B=left(begin 1 & -2 \ -2 & 5 endright) cdotleft(begin 7 \ 9 endright)=$$ $$=left(begin -11 \ 31 endright) Rightarrowleft(begin x_ <1>\ x_ <2>endright)=left(begin -11 \ 31 endright)$$

Две матрицы одного размера равны, если равны их соответствующие элементы, то есть в итоге имеем, что $x_<1>=-11$, $x_<2>=31$

Ответ. $x_<1>=-11$, $x_<2>=31$

Задание. Решить с помощью обратной матрицы систему $left<begin 2 x_<1>+x_<2>+x_<3>=2 \ x_<1>-x_<2>=-2 \ 3 x_<1>-x_<2>+2 x_<3>=2 endright.$

Решение. Запишем данную систему в матричной форме:

где $A=left(begin 2 & 1 & 1 \ 1 & -1 & 0 \ 3 & -1 & 2 endright)$ — матрица системы, $X=left(begin x_ <1>\ x_ <2>\ x_ <3>endright)$ — столбец неизвестных, $B=left(begin 2 \ -2 \ 2 endright)$ — столбец правых частей. Тогда

Найдем обратную матрицу $A^-1$ к матрице $A$ с помощью союзной матрицы:

Определитель матрицы $A$

$$Delta=left|begin 2 & 1 & 1 \ 1 & -1 & 0 \ 3 & -1 & 2 endright|=2 cdot(-1) cdot 2+1 cdot(-1) cdot 1+1 cdot 0 cdot 3-$$ $$-3 cdot(-1) cdot 1-(-1) cdot 0 cdot 2-1 cdot 1 cdot 2=-4 neq 0$$

Отсюда искомая матрица

Метод / Теорема Крамера

Теоретический материал по теме — метод Крамера.

Задание. Найти решение СЛАУ $left<begin 5 x_<1>+2 x_<2>=7 \ 2 x_<1>+x_<2>=9 endright.$ при помощи метода Крамера.

Решение. Вычисляем определитель матрицы системы:

$$Delta=left|begin 5 & 2 \ 2 & 1 endright|=5 cdot 1-2 cdot 2=1 neq 0$$

Так как $Delta neq 0$ , то по теореме Крамера система совместна и имеет единственное решение. вычислим вспомогательные определители. Определитель $Delta_<1>$ получим из определителя $Delta$ заменой его первого столбца столбцом свободных коэффициентов. Будем иметь:

$$Delta_<1>=left|begin 7 & 2 \ 9 & 1 endright|=7-18=-11$$

Аналогично, определитель $Delta_<2>$ получается из определителя матрицы системы $Delta$ заменой второго столбца столбцом свободных коэффициентов:

$$Delta_<2>=left|begin 5 & 7 \ 2 & 9 endright|=45-14=31$$

Тогда получаем, что

Ответ. $x_<-1>=-11$, $x_ <2>= 31$

Задание. При помощи формул Крамера найти решение системы $left<begin 2 x_<1>+x_<2>+x_<3>=2 \ x_<1>-x_<2>=-2 \ 3 x_<1>-x_<2>+2 x_<3>=2 endright.$

Решение. Вычисляем определитель матрицы системы:

$$Delta=left|begin 2 & 1 & 1 \ 1 & -1 & 0 \ 3 & -1 & 2 endright|=2 cdot(-1) cdot 2+1 cdot(-1) cdot 1+1 cdot 0 cdot 3-$$ $$-3 cdot(-1) cdot 1-(-1) cdot 0 cdot 2-1 cdot 1 cdot 2=-4 neq 0$$

Так как определитель матрицы системы неравен нулю, то по теореме Крамера система совместна и имеет единственное решение. Для его нахождения вычислим следующие определители:

$$Delta_<1>=left|begin 2 & 1 & 1 \ -2 & -1 & 0 \ 2 & -1 & 2 endright|=2 cdot(-1) cdot 2+(-2) cdot(-1) cdot 1+$$ $$+1 cdot 0 cdot 2-2 cdot(-1) cdot 1-(-1) cdot 0 cdot 2-(-2) cdot 1 cdot 2=4$$ $$Delta_<2>=left|begin 2 & 2 & 1 \ 1 & -2 & 0 \ 3 & 2 & 2 endright|=2 cdot(-2) cdot 2+1 cdot 2 cdot 1+2 cdot 0 cdot 3-$$ $$-3 cdot(-2) cdot 1-2 cdot 0 cdot 2-1 cdot 2 cdot 2=-4$$ $$Delta_<3>=left|begin 2 & 1 & 2 \ 1 & -1 & -2 \ 3 & -1 & 2 endright|=2 cdot(-1) cdot 2+1 cdot(-1) cdot 2+$$ $$+1 cdot(-2) cdot 3-3 cdot(-1) cdot 2-(-1) cdot(-2) cdot 2-1 cdot 1 cdot 2=-12$$

Метод Гаусса. Метод последовательного исключения неизвестных

Теоретический материал по теме — метод Гаусса.

Задание. Решить СЛАУ $left<begin 2 x_<1>+x_<2>+x_<3>=2 \ x_<1>-x_<2>=-2 \ 3 x_<1>-x_<2>+2 x_<3>=2 endright.$ методом Гаусса.

Решение. Выпишем расширенную матрицу системы и при помощи элементарных преобразований над ее строками приведем эту матрицу к ступенчатому виду (прямой ход) и далее выполним обратный ход метода Гаусса (сделаем нули выше главной диагонали). Вначале поменяем первую и вторую строку, чтобы элемент $a_<1>$ равнялся 1 (это мы делаем для упрощения вычислений):

Далее делаем нули под главной диагональю в первом столбце. Для этого от второй строки отнимаем две первых, от третьей — три первых:

Все элементы третьей строки делим на два (или, что тоже самое, умножаем на $frac<1><2>$:

Далее делаем нули во втором столбце под главной диагональю, для удобства вычислений поменяем местами вторую и третью строки, чтобы диагональный элемент равнялся 1:

От третьей строки отнимаем вторую, умноженную на 3:

Умножив третью строку на $left(-frac<1><2>right)$ , получаем:

Проведем теперь обратный ход метода Гаусса (метод Гассу-Жордана), то есть сделаем нули над главной диагональю. Начнем с элементов третьего столбца. Надо обнулить элемент $$tilde simleft(begin 1 & -1 & 0 & -2 \ 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 3 endright)$$

Далее обнуляем недиагональные элементы второго столбца, к первой строке прибавляем вторую:

Полученной матрице соответствует система

$left<begin x_<1>+0 cdot x_<2>+0 cdot x_<3>=-1 \ 0 cdot x_<1>+x_<2>+0 cdot x_<3>=1 \ 0 cdot x_<1>+0 cdot x_<2>+x_<3>=3 endright.$ или $left<begin x_<1>=-1 \ x_<2>=1 \ x_<3>=3 endright.$

Однородные СЛАУ. Фундаментальная система решений

Теоретический материал по теме — однородные СЛАУ.

Задание. Выяснить, имеет ли однородная СЛАУ $left<begin 3 x-2 y=-1 \ x+3 y=7 endright.$ ненулевые решения.

Решение. Вычислим определитель матрицы системы:

$$Delta=left|begin 3 & -2 \ 1 & 3 endright|=9-(-2)=9+2=11 neq 0$$

Так как определитель не равен нулю, то система имеет только нулевое решение $x=y=0$

Ответ. Система имеет только нулевое решение.

Задание. Найти общее решение и ФСР однородной системы $Delta=left|begin 3 & -2 \ 1 & 3 endright|=9-(-2)=9+2=11 neq 0$

Решение. Приведем систему к ступенчатому виду с помощью метода Гаусса. Для этого записываем матрицу системы (в данном случае, так как система однородная, то ее правые части равны нулю, в этом случае столбец свободных коэффициентов можно не выписывать, так как при любых элементарных преобразованиях в правых частях будут получаться нули):

$$A=left(begin 1 & 1 & 0 & -3 & -1 \ 1 & -2 & 2 & -1 & 0 \ 4 & -2 & 6 & 3 & -4 \ 2 & 4 & -2 & 4 & -7 endright)$$

с помощью элементарных преобразований приводим данную матрицу к ступенчатому виду. От второй строки отнимаем первую, от третьей — четыре первых, от четвертой — две первых:

$$A simleft(begin 1 & 1 & 0 & -3 & -1 \ 0 & -2 & 2 & 2 & 1 \ 0 & -6 & 6 & 15 & 0 \ 0 & 2 & -2 & 10 & -5 endright)$$

Обнуляем элементы второго столбца, стоящие под главной диагональю, для этого от третьей строки отнимаем три вторых, к четвертой прибавляем вторую:

$$A simleft(begin 1 & 1 & 0 & -3 & -1 \ 0 & -2 & 2 & 2 & 1 \ 0 & 0 & 0 & 9 & -3 \ 0 & 0 & 0 & 12 & -4 endright)$$

От четвертой строки отнимем $$frac<4><3>$$ третьей и третью строку умножим на $$frac<1><3>$$ :

$$A simleft(begin 1 & 1 & 0 & -3 & -1 \ 0 & -2 & 2 & 2 & 1 \ 0 & 0 & 0 & 3 & -1 \ 0 & 0 & 0 & 0 & 0 endright)$$

Нулевые строки можно далее не рассматривать, тогда получаем, что

$$A simleft(begin 1 & 1 & 0 & -3 & -1 \ 0 & -2 & 2 & 2 & 1 \ 0 & 0 & 0 & 3 & -1 endright)$$

Далее делаем нули над главной диагональю, для этого от первой строки отнимаем третью, а ко второй строке прибавляем третью:

$$A simleft(begin 1 & 1 & 0 & -6 & 0 \ 0 & -2 & 2 & 5 & 0 \ 0 & 0 & 0 & 3 & -1 endright)$$

то есть получаем систему, соответствующую данной матрице:

Или, выразив одни переменные через другие, будем иметь:

Здесь $x_<2>, x_<4>$ — независимые (или свободные) переменные (это те переменные, через которые мы выражаем остальные переменные), $x_<1>,x_<3>,x_<5>$ — зависимые (связанные) переменные (то есть те, которые выражаются через свободные). Количество свободных переменных равно разности общего количества переменных $n$ (в рассматриваемом примере $n=5$ , так как система зависит от пяти переменных) и ранга матрицы $r$ (в этом случае получили, что $r=3$ — количество ненулевых строк после приведения матрицы к ступенчатому виду): $n-r=5-3=2$

Так как ранг матрицы $r=3$ , а количество неизвестных системы $n=5$ , то тогда количество решений в ФСР $n-r=5-3-2$ (для проверки, это число должно равняться количеству свободных переменных).

Для нахождения ФСР составляем таблицу, количество столбцов которой соответствует количеству неизвестных (то есть для рассматриваемого примера равно 5), а количество строк равно количеству решений ФСР (то есть имеем две строки). В заголовке таблицы выписываются переменные, свободные переменные отмечаются стрелкой. Далее свободным переменным придаются любые, одновременно не равные нулю значений и из зависимости между свободными и связанными переменными находятся значения остальных переменных. Для рассматриваемой задачи эта зависимость имеет вид:

Тогда придавая в первом случае, например, независимым переменным значения $x_<2>=1$ , $x_<4>=0$ получаем, что $left<begin x_<1>=-1+6 cdot 0=-1 \ x_<3>=1-frac<5> <2>cdot 0=1 \ x_<5>=3 cdot 0=0 endright.$ . Полученные значения записываем в первую строку таблицы. Аналогично, беря $x_<2>=0$ , $x_<4>=2$, будем иметь, что $x_<1>=12,x_<3>=-5,x_<5>=6$ , что и определяет второе решение ФСР. В итоге получаем следующую таблицу:

Эти две строчки и есть фундаментальным решением заданной однородной СЛАУ. Частное решение системы:

Общее решение является линейной комбинацией частных решений:

$$X=C_ <1>X_<1>+C_ <2>X_<2>=C_<1>left(begin -1 \ 1 \ 1 \ 0 \ 0 endright)+C_<2>left(begin 12 \ 0 \ -5 \ 2 \ 6 endright)$$

где коэффициенты $C_<1>, C_<2>$ не равны нулю одновременно. Или запишем общее решение в таком виде:

Придавая константам $C_<1>, C_<2>$ определенные значения и подставляя их в общее решение, можно будет находить частные решения однородной СЛАУ.

П.1. Базисные и опорные решения

Рассмотрим линейную систему из m уравнений с n переменными

(2.1)

В дальнейшем будет интересен случай, когда n > m.

Будем полагать, что в системе (2.1) все уравнения являются независимыми, что в свою очередь означает r = m, где r – ранг матрицы системы
A = (a_ij).

Рассмотрим одну из таких систем

Составим расширенную матрицу системы и проведем несложные преобразования

В данном случае r = 2, число переменных n = 3. Очевидно, что такая система имеет бесконечно много решений.

Перейдем от последней матрицы к системе уравнений

Выразим переменные х₁ и х₃ через переменную х₂

Рассмотрим столбцы перед переменными х₁ и х₃, как векторы и . Данные векторы образуют базис в двумерном пространстве. Отсюда название переменных х₁ и х₃ – базисные переменные.

В общем случае базисных переменных в системе из m независимых уравнений с n переменными будет m.

Определение 2.1. Базисными переменными системы m линейных уравнений с n переменными (m

Число базисных решений равно количеству неупорядоченных подмножеств из n элементов (число неизвестных) по m (число базисных неизвестных), т.е. это число равно

,

где n! = n × (n – 1) ×…× 3 × 2 × 1; m! = m × (m – 1) ×…× 2 × 1.

В данном примере число базисных решений определяется следующим образом

.

Среди базисных решений выделяют вырожденные решения, в которых нулевыми являются не только свободные решения, но и некоторые базисные.

Обратимся к примерам 1.1 и 1.2, рассмотренным в предыдущем параграфе. В системе ограничений одной и другой задачи присутствует требование неотрицательности переменных х₁, …, х_n. Это требование не является случайным, поскольку в экономических моделях, связанных с решением систем линейных уравнений, неизвестные величины соответствуют некоторым конкретным экономическим показателям, которые могут быть только неотрицательными. Неотрицательные базисные решения назовем опорными*.

Рассмотрим отыскание опорных решений на примере.

П р и м е р 2.1. Найти все опорные решения системы линейных уравнений:

Решение. Столбец свободных переменных не содержит отрицательных компонент. Если бы в каком-то уравнении были отрицательные свободные члены, нужно было бы умножением обеих частей уравнения на (– 1) сделать свободный член соответствующего уравнения положительным. Составим расширенную матрицу системы

и определим первый разрешающий элемент так, чтобы в последнем столбце в результате элементарных преобразований не появились отрицательные компоненты. Очевидно, разрешающий элемент должен быть положительным. В первом столбце все компоненты положительные. Какой из них можно взять в качестве разрешающего? Составим отношения (j = 1, 2, 3). Если за разрешающий элемент выбрать тот из элементов первого столбца, которому соответствует минимальное отношение, то в столбце свободных членов после преобразований не будет отрицательных компонент – это элемент а₃₁ = 1. Получим

.

Во втором столбце первоначальной матрицы за разрешающий можно взять только элемент а₂₂ = 1 (он единственный положительный элемент этого столбца)

.

В третьем столбце за разрешающий можно взять а₃₃ = 11, т. к. :

.

В четвертом столбце все элементы отрицательные и разрешающий элемент выбрать нельзя.

Остановимся на первом варианте и продолжим процесс далее

.

Очевидно, ранг матрицы равен 2, базисные неизвестные – х₁ и х₄; свободные – х₂ и х₃. Общее решение: (7 – 11х₂ + 34 х₃; х₂; х₃; 1 – 3х₂ + 9х₃).

Базисное решение (7; 0; 0; 1) является опорным.

В данном случае существует базисных решений, соответствующих базисным переменным: х₁х₂; х₁х₃; х₁х₄; х₂х₃; х₂х₄; х₃х₄. Вариант х₁х₄ уже был рассмотрен.

Вернемся к матрице системы, полученной после преобразований:

.

Варианты х₁х₃; х₂х₃; х₃х₄ невозможны, т.к. в столбце, соответствующем х₃, нет положительных компонент, и х₃ не может войти в базис. Введем в базис х₂: , значит разрешающий элемент а₁₂ = 3. Получим

.

Базисное решение — опорное.

Проверим последний вариант х₂х₄: в четвертом столбце последней матрицы разрешающим может быть только элемент а₁₂ = 1/3 > 0, но тогда из базиса уйдет неизвестная х₂ и получим базисные переменные х₁х₄, что уже было рассмотрено.

Итак, опорные решения: (7; 0; 0; 1) и .

Сформулируем общее правило выбора разрешающего элемента при отыскании опорного решения для определенного столбца j.

1. Приводим систему уравнений к виду, когда в столбце свободных членов нет отрицательных чисел.

2. В выбранном столбце j в «конкурсе» на звание «разрешающий элемент» участвуют только положительные элементы.

3. Каждый элемент в столбце свободных членов, делим на соответствующий ему элемент столбца j.

4. Выбираем из полученных соотношений наименьшее (Q_j).

5. Элемент, для которого отношение, полученное в пункте 3, наименьшее, является разрешающим элементом.

Последнее изменение этой страницы: 2017-04-12; Просмотров: 1796; Нарушение авторского права страницы

Каноническая задача линейного программирования в векторной форме имеет вид:

Положительным координатам допустимых решений ставятся в соответствие векторы условий. Эти системы векторов зависимы, так как число входящих в них векторов больше размерности векторов.

Базисным решением системы называется частное решение, в котором неосновные переменные имеют нулевые значения. Любая система уравнений имеет конечное число базисных решений, равное , где – число неизвестных, – ранг системы векторов условий. Базисные решения, координаты которых удовлетворяют условию неотрицательности, являются опорными.

Опорным решением задачи линейного программирования называется такое допустимое решение , для которого векторы условий, соответствующие положительным координатам , линейно независимы.

Число отличных от нуля координат опорного решения не может превосходить ранга Системы векторов условий (т. е. числа линейно независимых уравнений системы ограничений).

Если число отличных от нуля координат опорного решения равно , то такое решение называется Невырожденным, в противном случае, если число отличных от нуля координат опорного решения меньше , такое решение называется Вырожденным.

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

Теорема. Любое опорное решение является угловой точкой области допустимых решений.

Теорема. Любая угловая точка области допустимых решений является опорным решением.

Пример.

Графический метод решения задачи линейной оптимизации рассмотрим на примере задачи производственного планирования при
= 2.

Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1

Решение:

Таблица 14.1 Ресурсы Изделия А В C 24 8 D 8 8 E 3 8

Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В — 50 млн. руб. Требуется найти объемы производства изделий А и В, обеспечивающие максимальную прибыль.

Построим математическую модель задачи, для чего обозначим и — объемы производства изделий А и В соответственно.

Тогда прибыль предприятия от реализации изделий А и изделий В составит:

.

Ограничения по ресурсам будут иметь вид:

Естественно, объемы производства должны быть неотрицательными .

Решение сформулированной задачи найдем, используя геометрическую интерпретацию. Определим сначала многоугольник решений, для чего систему ограничений неравенств запишем в виде уравнений и пронумеруем их:

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: при , а при . Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку и, подставив ее координаты в неравенство, видим, что оно удовлетворяется. Так как точка лежит левее первой прямой, то и полуплоскость будет находиться левее прямой . На рис. 14.1 расположение полуплоскости относительно первой прямой отмечено стрелками.

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям , находятся в первом квадранте.

Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник .

Любая точка многоугольника решений удовлетворяет системе ограничений задачи и, следовательно, является ее решением. Это говорит о том, что эта задача линейной оптимизации имеет множество допустимых решений, т. е. многовариантна. Нам же необходимо найти решение, обеспечивающее максимальную прибыль.

Чтобы найти эту точку, приравняем функцию к нулю и построим соответствующую ей прямую. Вектор–градиент прямой функции имеет координаты .

Рис. 14.1

Изобразим вектор на графике и построим прямую функции перпендикулярно вектору на рис. 14.1. Перемещая прямую функции параллельно самой себе в направлении вектора, видим, что последней точкой многоугольника решений, которую пересечет прямая функции, является угловая точка В. Следовательно, в точке В функция достигает максимального значения. Координаты точки В находим, решая систему уравнений, прямые которых пересекаются в данной точке.

Решив эту систему, получаем, что .

Следовательно, если предприятие изготовит изделия в найденных объемах, то получит максимальную прибыль, равную:

(млн. руб.).

Алгоритм решения задачи линейного программирования графическим методом таков:

1. Строится область допустимых решений;

2. Строится вектор нормали к линии уровня с точкой приложении в начале координат;

3. Перпендикулярно вектору нормали проводится одна из линий уровня, проходящая через начало координат;

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будут находиться максимум или минимум функции.

В зависимости от вида области допустимых решений и целевой функции задача может иметь единственное решение, бесконечное множество решений или не иметь ни одного оптимального решения.

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

Основные понятия симплексного метода решения задачи линейного программирования.

Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения рассмотренного выше метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

Симплекс-метод основан на следующих свойствах задачи линейного программирования:

· Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.

· Множество всех планов задачи линейного программирования выпукло.

· Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.

· Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом

Для применения этого метода задача линейного программирования должна быть сформулирована в канонической форме, причем матрица системы уравнений должна содержать единичную подматрицу размерностью . В этом случае очевиден начальный опорный план (неотрицательное базисное решение).

Для определенности предположим, что первые Т Векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: .

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

Полученный опорный план снова проверяется на оптимальность и т. д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получаются оптимальный опорный план и соответствующее ему оптимальное значение целевой функции.

Признак оптимальности заключается в следующих двух теоремах.

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:

, где ,

То можно получить новый опорный план, для которого значение целевой функции будет больше исходного; при этом могут быть два случая:

1. Если все координаты вектора, подлежащего вводу в базис, неположительны, то задача линейного программирования не имеет решения;

2. Если имеется хотя бы одна положительная координата у вектора, подлежащего вводу в базис, то можно получить новый опорный план.

Теорема 2. Если для всех векторов выполняется условие , то полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор , давший минимальную отрицательную величину симплекс-разности: .

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Г, Который дает минимальное положительное отношение:

; , .

Строка Называется Направляющей, Столбец и элемент
— Направляющими (последний называют также Разрешающим Элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:

,

А элементы любой другой -й Строки пересчитываются по формулам:

,,

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

для ; , для .

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

Вычисляются частные, полученные от деления всех элементов строк, давших одинаковое минимальное значение на свои направляющие элементы. Полученные частные сопоставляются по столбцам слева направо, при этом учитываются и нулевые, и отрицательные значения. В процессе просмотра отбрасываются строки, в которых имеются большие отношения, и из базиса выводится вектор, соответствующий строке, в которой раньше обнаружится меньшее частное.

Для использования приведенной выше процедуры симплекс-метода к минимизации линейной формы следует искать максимум функции , затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной задачи линейного программирования.

Симплексный метод с искусственным базисом (М-метод)

Симплексный метод с искусственным базисом применяется в тех случаях, когда затруднительно найти первоначальный опорный план исходной задачи линейного программирования, записанной в канонической форме.

М-метод заключается в применении правил симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной задачи линейного программирования таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае её максимизации слагаемое, представляющее собой произведение числа (–М) на сумму искусственных переменных, где М – достаточно большое положительное число.

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки теперь будут зависеть от числа М. Для сравнения оценок нужно помнить, что М – достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

В процессе решения М–Задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу. Если оптимальное решение М–Задачи содержит искусственные векторы или М–Задача неразрешима, то исходная задача также неразрешима.

Путем преобразований число вводимых переменных, составляющих искусственный базис, может быть уменьшено до одной.

< Предыдущая		Следующая >