Элементы матричного анализа - Методы решения системы линейных уравнений

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

Направленным отрезком называется упорядоченная пара (A, B) точек плоскости (пространства), у которой A называется началом, B -- концом. Направленные отрезки (A, B) и (C, D) назовем эквивалентными, если или если и. Знак обозначает сонаправленность: если лучи и либо лежат на одной прямой и дают в пересечении Луч, либо лежат на параллельных прямых в одной полуплоскости относительно прямой. Классы эквивалентности по указанному отношению называются векторами.

Векторное пространство (линейное пространство) - множество элементов, называемых Векторами, для которых определены операции сложения и умножения на число. Простейший, но важный пример - совокупность векторов a, b, c, ... обычного 3-мерного пространства. Каждый такой вектор - направленный отрезок, задаваемый тремя числами: ; числа называются Координатами вектора. При умножении вектора на Вещественное число соответствующий отрезок, сохраняя направление, растягивается в раз: . Сумма двух векторов находится по Правилу параллелограмма; если и то. Паре векторов a и b сопоставляют также Скалярное произведение (см. Векторная алгебра). Непосредственным обобщением З-мерного пространства является n-мерное Евклидово пространство. Его элементы - упорядоченные наборы вещественных чисел, Например, , . Сложение и Умножение векторов на число определены формулами, , а скалярное произведение - формулой Примером комплексного бесконечномерного векторного пространства может служить совокупность комплексных функций f, заданных на всей оси и квадратично суммируемых (то есть имеющих конечный интеграл ). Многие классы функций, например, Полиномы заданного порядка, функции непрерывные, дифференцируемые, интегрируемые, аналитические и тому подобные, также образуют бесконечномерные векторные пространства.

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

1. любой паре элементов х и у из L сопоставлен единственный элемент z, называемый их суммой z=x+y и принадлежащий L; 2. для любого числа и любого элемента x из L определен элемент z, который называется их произведением и принадлежащий L; 3. операции сложения и умножения на число являются ассоциативными и дистрибутивными.

Сложение допускает обратную операцию, то есть для любых х и у из L существует единственный элемент w из L такой, что x+w=y. Кроме того, имеют место формулы. Если все числа вещественны (комплексны), говорят о вещественном (комплексном) векторном пространстве; множество чисел называют полем скаляров L. Понятие векторного пространства можно ввести и для произвольного поля, например, поля кватернионов.

Если - элементы векторного пространства L, то выражение вида называется их линейной комбинацией; совокупность всех линейных комбинаций элементов подмножества S из L называют линейной оболочкой S. Векторы из L называют линейно независимыми, если условие ( - любые элементы поля скаляров) может выполняться только при. Бесконечная система векторов называется линейно независимой, если любая ее конечная часть является линейно независимой. Множество элементов подмножества S из L называется системой образующих S, если любой вектор х из S можно представить в виде линейной комбинации этих элементов. Линейно независимая система образующих S называется базисом S, если разложение любого элемента S по этой системе единственно. Базис, элементы которого каким-либо образом параметризованы, называется системой координат в S. Базис векторного пространства всегда существует, хотя и не определяется однозначно. Если базис состоит из конечного числа n элементов, то векторное пространство называется n-мерным (конечномерным); если базис - бесконечное множество, то векторное пространство называется бесконечномерным. Выделяют также счетномерные векторные пространства, у которых имеется счетный базис.

Подмножества векторного пространства L, замкнутые относительно его операций, называются подпространствами L. По любому подпространству S можно построить новое векторное пространство L/S, называемое фактор-пространством L по S: каждый его элемент есть множество векторов из L, различающихся между собой на элемент из S. Размерность L/S называется коразмерностью подпространства S в L; если размерности L и S равны соответственно n и k, то коразмерность S в L равна n-k. Если J - произвольное множество индексов i и SI - Семейство подпространств L, то совокупность всех векторов, принадлежащих каждому из SI, есть подпространство, называется пересечением указанных подпространств и обозначаемое. Для конечного семейства подпространств S1, ..., SS совокупность всех векторов, представимых в виде

, xI из SI,

Есть подпространство, называемое суммой S1, ..., SS и обозначаемое S1+ ... +SS. Если для любого элемента суммы S1+ ... +SS представление в виде (*) единственно, эта сумма называется прямой и обозначается. Сумма подпространств является прямой тогда и только тогда, когда пересечение этих подпространств состоит только из Нулевого вектора. Размерность суммы подпространств равна сумме размерностей этих подпространств минус размерность их пересечения. Векторное пространство L1 и L2 называют изоморфным и, если существует взаимно однозначное соответствие между их элементами, согласованное с операциями в них; L1 и L2 изоморфны тогда и только тогда, когда они имеют одинаковую размерность.

Конкретные примеры векторного пространства можно найти в математическом аппарате практически любого раздела физики. Конечномерными вещественными векторными пространствами являются, например, Трехмерное физическое пространство (без учета кривизны), Конфигурационное пространство и Фазовое пространство системы n классических точечных частиц. К числу бесконечномерных комплексных векторных пространств принадлежат Гильбертовы пространства, конкретные и абстрактные, составляющие основу математического аппарата квантовой физики. Простейший пример гильбертова пространств уже упоминавшееся пространство. Основные физические примеры - пространства векторов состояний различных систем микрочастиц, изучаемых в Квантовой механике, Квантовой статистической физике и Квантовой теории поля. Находят применение и такие векторные поля, у которых поле скаляров не совпадает со множеством вещественных или комплексных чисел: так, гильбертово пространство над полем кватернионов используется и одной из формулировок Квантовой механики, а гильбертово пространство над полем октонионов - в одной из формулировок Квантовой хромодинамики. В современных Теориях суперсимметрии интенсивно применяются так называемые градуированные векторные поля, то есть линейные пространства вместе с их фиксированным разложением в прямую бесконечную сумму подпространств.

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

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

Система векторов, которая не является линейно зависимой, называется линейно независимой.

Справедливо следующее утверждение.

Система векторов линейного пространства линейно независима тогда и только тогда, когда из равенства следует равенство нулю всех коэффициентов.

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

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

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

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

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

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

Например, доказано, что система векторов из

, ,...,

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

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

Пусть и -- два базиса в. Матрицей перехода от базиса к базису называется матрица, столбцами которой являются координаты векторов в базисе :

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

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

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

Определение 1. 2. Функция (1) называется целевой функцией (или линейной формой) задачи (1)-(4), а условия (2)-(4) - ограничениями данной задачи.

Определение 1. 3. Стандартной ( или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k=m и l=n.

Определение 1. 4. Основной ( или канонической) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1. 1) при выполнении условий (3) и (4), где k=0 и l=n.

Определение 1. 5. Совокупность чисел X=(x1, x2, ..., xN) , удовлетворяющих ограничениям задачи (2)-(4), называется допустимым решением задачи (или планом).

Определение 1. 6. План X=(x1*, x2*, ..., xN*), при котором целевая функция задачи принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции при плане X будем обозначать через F(X). Следовательно, X* - оптимальный план задачи, если для любого X выполняется неравенство F(X)<=F(X*) (соответственно F(X)>=F(X*))

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

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

1. В том случае, когда требуется найти минимум функции F=c1X1 + c2X2 + +. . . + cNXN , можно перейти к нахождению максимума функции F1=F=c1X1 + c2X2 +. . . + cNXN, поскольку функция F принимает минимальное значение в той же точке, в которой функция F1 принимает максимальное значение. 2. Ограничение-неравенство исходной задачи линейного программирования, имеющие вид "<=", можно преобразовать в ограничения-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида ">=" - в ограничение равенство вычитанием из его левой части дополнительной неотрицательной переменной. таким образом, ограничение неравенство

AI1X1+aI2X2+...+aInXN<=bI

Преобразуется в ограничение-равенство

AI1X1+aI2X2+...+aInXN+xN+1=bI

А ограничение-неравенство

AI1X1+aI2X2+...+aInXN>=bI

Преобразуется в ограничение-равенство

AI1X1+aI2X2+...+aInXN-xN+1=bI

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств.

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

3. Если переменная xk не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными uk и vk, приняв xk=uk-vk.

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

Перепишем эту задачу в векторной форме: найти максимум функции

F=c1X1 + c2X2 + +. . . + cNXN

При условиях

X1P1+x2P2+. . . +xNPN=P0,

XJ>=0 (j=1,n),

Где P1, . . . , PN и P0 - m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы уравнений задачи:

Определение 1. 7. План X=(x1, x2, . . . , xN) называется опорным планом основной задачи линейного программирования, если положительные коэффициенты (xJ>0) стоят при линейно-независимых векторах PJ.

Так как векторы PJ являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем m.

Определение 1. 8. Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он называется вырожденным.

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

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

Пусть требуется найти максимальное значение функции

F=c1X1 + c2X2 + +. . . + cNXN

При условиях

Здесь aIj, bI и cJ (i=1,m; j=1,n) - заданные постоянные числа (mI>0).

Векторная форма данной задачи имеет следующий вид: найти максимум функции

При условиях

X1P1+x2P2+. . . +xMPM+. . . +xNPN=P0 (6)

XJ>=0 (j=1,l; l<=n) (7)

Где

Так как

B1P1+b2P2+. . . +bMPM=P0

То по определению опорного плана X=( b1, b2, . . . , bM, 0, . . . , 0) является опорным планом данной задачи (последние n-m компонент вектора X равны нулю). Этот план определяется системой единичных векторов P1, P2, . . . , PM, которые образуют базис m-мерного пространства.

Найдем

Теорема 1. 1. (признак оптимальности опорного плана). Опорный план X=(x1*, x2*, ..., xM*,0,0,...,0) задачи (5)-(7) является оптимальным, если J>=0 для любого j (j=1, ..., n)

Теорема 1. 2. Если K<0 для некоторого j=k и среди чисел aIk (i=1, ...m) нет положительных (aIk <=0), то целевая функция (5) задачи (5)-(7) не ограничена на множестве ее планов.

Теорема 1. 3. Если опорный план X задачи (5)-(7) невырожден и K<0, но среди чисел aIk есть положительных (не все aIk <=0), то существует опорный план X1 такой, что F(X1)>F(X).

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

Теоремы (1-3) позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

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

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

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

В симплекс таблице первые от строк определяются исходными данным задачи, а показатели (от m+1)-й строки вычисляют. В этой строке i столбце вектора Р0 записывают значение целевой функции, котора она принимает при данном опорном плане, а в столбце вектора PJ значение J = ZJ - CJ. Значение zJ находится как скалярное произведение вектора PJ на вектор C6

Значение F0 равно скалярному произведению вектора P0 на вектор СБ:

После заполнения симплекс таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (то m+ 1)-ой строки таблицы. В результате может иметь место один из следующих трех случаев:

В первом случае на основании признака оптимальности исходный опрный план является оптимальным.

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

В качестве вектора, вводимого в базис, можно взять любой из акторов PJ, имеющий индекс j, для которого J< 0. Пусть, например, J<0 и решено ввести в базис вектор PK.

Для определения вектора, подлежащего исключению из базиса, [находят min (bI/aIk) для всех aIk> 0]. Пусть этот минимум достигается при i = r. Тогда из базиса исключают вектор РR, а число aRk называется разрешающим элементом.

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

После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты разложения векторов РJ, через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана--Гаусса. При этом можно показать, что положительные компоненты нового опорного плана и коэффициенты разложения векторов PI через векторы нового базиса вычисляются по формулам

Базис	СБ	P0	C1	...	CM	CM+1	...	CK	...	CN
P1	...	PM	PM+1	...	PK	...	PN
P1	C1	B1	1	...	0	A1m+1	...	A1k	...	A1n
...	...	...	...	...	...	...	...	...	...	...
PR	CR	BR	0	...	0	ARm+1	...	ARk	...	ARn
...	...	...	...	...	...	...	...	...	...	...
PM	CM	BM	0	...	1	AMm+1	...	AMk	...	AMn
0	...	0	M+1	...	K	...	N

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

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

Элементы векторов Р0 и РJ в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце СБ в строке вводимого вектора проставляют величину сК, где k - индекс вводимого вектора.

Остальные элементы столбцов вектора Р0 и РJ новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов находят три числа:

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

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

После заполнения новой симплекс-таблицы просматривают элементы (m+1)-й строки. Если все zJ- cJ > 0, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо получают оптимальный план задачи, либо устанавливают ее неразрешимость.

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

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции

F(x1, x2, ..., xN)

При условии, что переменные удовлетворяют соотношениям

Где f и gI - некоторые известные функции n переменных, а bI - заданные числа.

В результате решения задачи будет определена точка X*=(x1*, x2*, ..., xN*), координаты которой удовлетворяют соотношениям.

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

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

Если определена область допустимых решений, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f(x1, x2, ..., xN)=h. Указанная точка может находиться как на границе области допустимых решений, так и внутри нее.

Элементы аналитической геометрии на прямой плоскости и в трехмерном пространстве.

Элементы матричного анализа - Методы решения системы линейных уравнений

Похожие статьи