Решение задач по математике онлайн
//mailru,yandex,google,vkontakte,odnoklassniki,instagram,wargaming,facebook,twitter,liveid,steam,soundcloud,lastfm, // echo( ‘
Калькулятор онлайн.
Решение систем линейных алгебраических уравнений (СЛАУ)
Метод Гаусса, матричный метод, метод Крамера, исследование на совместность (теорема Кронекера-Капелли), определение количества решений, нахождение нормальной фундаментальной системы решений.
С помощью данной математической программы вы можете решить и исследовать систему линейных алгебраических уравнений (СЛАУ).
Программа не только даёт ответ задачи, но и приводит подробное решение с пояснениями шагов решения.
Данная программа может быть полезна учащимся старших классов общеобразовательных школ при подготовке к контрольным работам и экзаменам, при проверке знаний перед ЕГЭ, родителям для контроля решения многих задач по математике и алгебре. А может быть вам слишком накладно нанимать репетитора или покупать новые учебники? Или вы просто хотите как можно быстрее сделать домашнее задание по математике или алгебре? В этом случае вы также можете воспользоваться нашими программами с подробным решением.
Таким образом вы можете проводить своё собственное обучение и/или обучение своих младших братьев или сестёр, при этом уровень образования в области решаемых задач повышается.
Ввод дробного числа в виде десятичной дроби.
При вводе десятичной дроби, целую часть от дробной части можно отделять точкой или запятой :
Ввод: -2.34
Результат: \( -2<,>34 \)
Ввод: -1,15
Результат: \( -1<,>15 \)
Ввод дробного числа в виде обыкновенной дроби.
В качестве числителя, знаменателя и целой части дроби может выступать только целое число.
Знаменатель не может быть отрицательным.
При вводе числовой дроби числитель отделяется от знаменателя знаком деления: /
Ввод: -2/3
Результат: $$ -\frac<2> <3>$$
Целая часть отделяется от дроби знаком амперсанд: &
Ввод: 5&8/3
Результат: $$ 5\frac<8> <3>$$
Помните, что на ноль делить нельзя!
RND CFracNum Fill RND int Fill Start MathJax
Сюда ввести строку с GET параметрами :
Немного теории.
Системы линейных алгебраических уравнений
Основные определения
Система \(m\) линейных алгебраических уравнений с \(n\) неизвестными (сокращенно СЛАУ) представляет собой систему вида
\( \left\< \begin
Уравнения системы называют алгебраическими потому, что левая часть каждого из них есть многочлен от \(n\) переменных \( x_1 , \ldots x_n \), а линейными потому, что эти многочлены имеют первую степень.
Числа \(a_
СЛАУ называют однородной, если \( b_1 = b_2 = \ldots = b_m = 0 \). Иначе её называют неоднородной.
Решением СЛАУ, да и вообще всякой системы уравнений, называют такой набор значений неизвестных \( x_1^\circ, \ldots , x_n^\circ \), при подстановке которых каждое уравнение системы превращается в тождество. Любое конкретное решение СЛАУ также называют её частным решением.
Решить СЛАУ — значит решить две задачи:
— выяснить, имеет ли СЛАУ решения;
— найти все решения, если они существуют.
СЛАУ называют совместной, если она имеет какие-либо решения. В противном случае её называют несовместной. Однородная СЛАУ всегда совместна, поскольку нулевой набор значений её неизвестных всегда является решением.
Если СЛАУ (1) имеет решение, и притом единственное, то её называют определенной, а если решение неединственное — то неопределенной. При \(m=n\), т.е. когда количество уравнений совпадает с количеством неизвестных, СЛАУ называют квадратной.
Формы записи СЛАУ
Кроме координатной формы (1) записи СЛАУ часто используют и другие её представления.
Рассматривая коэффициенты \(a_
\( \begin
или, обозначая столбцы соответственно \( a_1 , \ldots , a_n , b \),
\( x_1 a_1 + x_2 a_2 + \ldots + x_n a_n = b \tag <2>\)
Таким образом, решение СЛАУ (1) можно трактовать как представление столбца \(b\) в виде линейной комбинации столбцов \( a_1, \ldots, a_n \). Соотношение (2) называют векторной записью СЛАУ.
Поскольку \(A \;,\; X\) и \(B\) являются матрицами, то запись СЛАУ (1) в виде \(AX=B\) называют матричной. Если \(B=0\), то СЛАУ является однородной и в матричной записи имеет вид \(AX=0\).
Приведенные рассуждения показывают, что задачи :
а) решения СЛАУ (1)
б) представления столбца в виде линейной комбинации данных столбцов
в) решения матричных уравнений вида \(AX=B\)
являются просто различной формой записи одной и той же задачи.
Критерий совместности СЛАУ
«Триединство» форм записи СЛАУ позволяет легко получить критерий совместности СЛАУ. Напомним, что содержательный смысл это понятие имеет для неоднородных СЛАУ (однородные СЛАУ всегда совместны).
Матрицу
\( A = \begin
называют матрицей (коэффициентов) СЛАУ (1), а матрицу
\( (A|B) = \left( \begin
расширенной матрицей СЛАУ (1). Расширенная матрица полностью характеризует СЛАУ. Это означает, что по этой матрице однозначно (если сохранить обозначения для неизвестных) восстанавливается сама СЛАУ.
Теорема Кронекера-Капелли. Для совместности СЛАУ \(AX=B\) необходимо и достаточно, чтобы ранг её матрицы \(A\) был равен рангу её расширенной матрицы \( (A|B) \).
Формулы Крамера
Теорема. СЛАУ с квадратной невырожденной матрицей имеет решение, и притом единственное, которое определяется по формулам Крамера :
$$ x_i = \frac<\Delta_i> <|A|>\;,\quad i=\overline <1,n>\tag <3>$$
где \(\Delta_i\) — определитель матрицы, получающейся из матрицы \(A\) заменой \(i\)-го столбца на столбец свободных членов.
Следствие. Однородная СЛАУ с квадратной невырожденной матрицей имеет единственное решение — нулевое.
Если матрица СЛАУ не является квадратной невырожденной, то формулы Крамера не работают и приходится использовать другие методы нахождения решений.
Однородные системы
Теорема. Если столбцы \( X^<(1)>, X^<(2)>, \ldots , X^ <(s)>\) — решения однородной СЛАУ \(AX=0\), то любая их линейная комбинация также является решением этой системы.
Следствие. Если однородная СЛАУ имеет ненулевое решение, то она имеет бесконечно много решений.
Естественно попытаться найти такие решения \( X^<(1)>, \ldots , X^ <(s)>\) системы \(AX=0\), чтобы любое другое решение этой системы представлялось в виде их линейной комбинации и притом единственным образом. Оказывается, что это всегда возможно и приводит к следующему определению.
Определение. Любой набор из \(k=n-r\) линейно независимых столбцов, являющихся решениями однородной СЛАУ \(AX=0\), где \(n\) — количество неизвестных в системе, а \(r\) — ранг её матрицы \(A\), называют фундаментальной системой решений этой однородной СЛАУ.
При исследовании и решении однородных систем линейных алгебраических уравнений будем использовать следующую терминологию. Если в матрице \(A\) однородной СЛАУ \(AX=0\) фиксировать базисный минор, то ему соответствуют базисные столбцы и, следовательно, набор неизвестных, отвечающих этим столбцам. Указанные неизвестные называют базисными, или зависимыми, а остальные неизвестные — свободными, или независимыми.
Теорема. Пусть дана однородная СЛАУ \(AX=0\) с \(n\) неизвестными и \( \text
Если в фундаментальной системе решений все значения независимых неизвестных равны нулю, кроме одного, которое равно единице, то такую систему решений называют фундаментальной нормальной системой решений.
Следствие. С помощью нормальной фундаментальной системы решений однородной СЛАУ множество всех решений можно описать формулой :
$$ X = c_1X^ <(1)>+ \ldots + c_kX^ <(k)>$$
где постоянные \( c_i \;, \quad i=\overline <1,k>\), принимают произвольные значения.
Следствие. Для существования ненулевого решения у однородной квадратной СЛАУ необходимо и достаточно, чтобы её матрица была вырождена.
Неоднородные системы
Рассмотрим произвольную СЛАУ \(AX=B\). Заменив столбец \(B\) свободных членов нулевым, получим однородную СЛАУ \(AX=0\), соответствующую неоднородной СЛАУ \(AX=B\). Справедливо следующее утверждение о структуре произвольного решения неоднородной СЛАУ.
Теорема. Пусть столбец \(X^\circ\) — некоторое решение СЛАУ \(AX=B\). Произвольный столбец \(X\) является решением этой СЛАУ тогда и только тогда, когда он имеет представление \(X = X^\circ + Y \), где \(Y\) — решение соответствующей однородной СЛАУ \(AY=0\).
Следствие. Пусть \(X’\) и \(X»\) — решения неоднородной системы \(AX=B\). Тогда их разность \( Y = X’ — X» \) является решением соответствующей однородной системы \(AY=0\).
Эта теорема сводит проблему решения СЛАУ к случаю однородной системы: чтобы описать все решения неоднородной СЛАУ, достаточно энать одно её решение (частное решение) и все решения соответствующей однородной СЛАУ.
Чтобы решить неоднородную систему, надо, во-первых, убедиться, что она совместна (например, по теореме Кронекера-Капелли), а во-вторых, найти частное решение \(X^\circ\) этой системы, чтобы свести её к однородной системе.
Теорема о структуре общего решения СЛАУ. Пусть \(X^\circ\) — частное решение СЛАУ \(AX=B\) и известна фундаментальная система решений \( X^<(1)>, \ldots , X^ <(k)>\) соответствующей однородной системы \(AX=0\). Тогда любое решение СЛАУ \(AX=B\) можно представить в виде $$ X = X^\circ + c_1 X^ <(1)>+ c_2 X^ <(2)>+ \ldots + c_k X^ <(k)>$$
где \( c_i \in \mathbb
Эту формулу называют общим решением СЛАУ.
Решение систем линейных уравнений
Эта страничка поможет решить Системы Линейных Алгебраических Уравнений (СЛАУ) методом Гаусса, матричным методом или методом Крамера, исследовать их на совместность (теорема Кронекера-Капелли), определить количество решений, найти общее, частное и базисные решения.
Введите коэффициенты при неизвестных в поля. Если Ваше уравнение имеет меньшее количество неизвестных, то оставьте пустыми поля при переменных, не входящих в ваше уравнение. Можно использовать дроби ( 13/31 ).
Алгоритм нахождения неотрицательного решения системы линейных уравнений Текст научной статьи по специальности « Математика»
Аннотация научной статьи по математике, автор научной работы — Севостьянов Егор Николаевич, Лепчинский Михаил Германович
В статье рассматривается новый алгоритм для отыскания точного решения задачи линейного программирования. Метод основан на сведении задачи линейного программирования к задаче решения системы линейных уравнений неполного ранга в неотрицательных числах, которая решается через последовательные приближения в специально построенных подпространствах. Доказана сходимость метода за конечное число шагов. Приводятся результаты тестирования алгоритма на данных задачи Кли Минти и на группе случайных тестов.
Похожие темы научных работ по математике , автор научной работы — Севостьянов Егор Николаевич, Лепчинский Михаил Германович
Algorithm for finding of a non-negative solution for linear system of equations
The new algorithm for finding of the exact solution for the linear programming problem is constructed. The method is based on the converting of the linear programming problem to the problem of solving in nonnegative numbers for a system of linear equations with an incomplete rank. This problem is solved by successive approximations in specially constructed subspaces. The convergence of the algorithm for a finite number of the steps is proved. The algorithm has been tested on the data of the Klee Minty problem and on a set of random tests.
Текст научной работы на тему «Алгоритм нахождения неотрицательного решения системы линейных уравнений»
Челябинский физико-математический журнал. 2016. Т. 1, вып. 2. С. 68-77.
АЛГОРИТМ НАХОЖДЕНИЯ НЕОТРИЦАТЕЛЬНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
Е. Н. Севостьянов1′», М. Г. Лепчинский2’6
1ЗАО «Диджитал Айрон Пайп», Челябинск, Россия 2 Челябинский государственный университет, Челябинск, Россия «y384@mail.ru; ъшу1Н@сзи.ти
В статье рассматривается новый алгоритм для отыскания точного решения задачи линейного программирования. Метод основан на сведении задачи линейного программирования к задаче решения системы линейных уравнений неполного ранга в неотрицательных числах, которая решается через последовательные приближения в специально построенных подпространствах. Доказана сходимость метода за конечное число шагов. Приводятся результаты тестирования алгоритма на данных задачи Кли — Минти и на группе случайных тестов.
Ключевые слова: алгоритм линейного программирования, неотрицательное ‘решение системы линейных уравнений, линейное неравенство.
Первоначально исследования в области численных методов линейного программирования (ЛП) концентрировались в основном на симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а после опубликования статьи [1] внимание многих исследователей переключилось на методы внутренних точек.
В связи с тем, что не найден сильно полиномиальный алгоритм для задачи ЛП [2, с. 194-205], интерес вызывает изучение иных подходов к построению алгоритмов ЛП. Данная работа посвящена описанию и изучению алгоритма линейного программирования, отличного от алгоритмов метода внутренних точек и симплекс-метода. Отличительной особенностью алгоритма является то, что задача линейного программирования в стандартной форме с помощью комбинирования прямой и двойственной задачи сводится к задаче нахождения неотрицательного решения системы линейных уравнений, которая, в свою очередь, решается через последовательные приближения по направлениям вдоль гиперплоскостей, ограничивающих неотрицательную область пространства Кп. Доказана сходимость алгоритма к точному решению не более чем за 2пи шагов. Предложенный алгоритм можно считать обобщением и развитием идей, высказанных в работе [3].
1. Обозначения и начальный вид решаемой задачи
Договоримся обозначать множество матриц размером т на и над полем К как 1т’п. Единичную матрицу будем обозначать как Е. Под вектором (точкой) условимся понимать вектор-строку, чертой над вектором будем делать различие в обозначении между вектором и скаляром. Векторы из нулей и одной единицы на позиции г будем обозначать как е^. Линейную оболочку множества X будем обозначать как
Задача линейного программирования в стандартной форме имеет следующий
Покажем, как задачу (1) свести к задаче более простого вида:
Ax* = b*, где A G Rm’n и m 0.
По сути, в (2) надо решить систему линейных уравнений неполного ранга в неотрицательных числах.
Ш!аг 1. Комбинация прямой и двойственной задачи. Рассмотрим задачу
Ax* 0>, ограниченный гиперплоскостями Е = £(<ё1. ёп>\<ё>). В дальнейшем нас будут интересовать линейные подпространства данных гиперплоскостей, порождённые векторами из <е>, которые мы будем называть граничными К-плоскостями. Для каждой граничной К-плоскости введём квадратную диагональную матрицу Zi С Кга’га, составленную из единичных и нулевых векторов-строк, причём на главной диагонали матрицы Zi будет стоять единица, если данная единичная вектор-строка принадлежит граничной К-плоскости, и ноль в противном случае. Следовательно, ранг матрицы Zi совпадает с размерностью граничной К-плоскости и равен К. Будем обозначать граничную К-плоскость, порождённую матрицей Zi, как подразумевая, что
граничная К-плоскость является линейной оболочкой строк матрицы Множество решений системы линейных уравнений Аж* = Ь* обозначим как П.
Алгоритм решения системы линейных уравнений неполного ранга Ах1 = Ъ: в неотрицательных числах будет представлять из себя движение точки внутри конуса К к неотрицательному решению системы. Для этого будем последовательно уменьшать расстояние между множеством решений системы линейных уравнений П и рассматриваемой на данном этапе точкой х1-1, не выходя за пределы неотрицательной области К. Нам потребуется известная формула [5, с. 92] ортогональной проекции точки Х0 на множество решений системы линейных уравнений
Хр = Х0 — А'(АА’)-1АХ0 + А*(АА*)-1Ъ*. (5)
Подойдя к какой-либо граничной К-плоскости положительной области К,
будем изменять направление движения вдоль в сторону уменьшения рассто-
яния между и П. Ниже покажем, что для сходимости алгоритма достаточ-
но брать в качестве направления движения наиближайшую к х1-1 точку рассматриваемой граничной К-плоскости расстояние от которой до П минимально на L(Zi). При достижении минимума расстояния от какой-нибудь граничной К-плоскости до П будем искать новое приближение к решению, уходя от данной граничной К-плоскости.
Соответственно, квадрат расстояния от точки Х Е до множества решений
системы линейных уравнений Ахt = Ъ будет определяться формулой
р2^гх*, П) = р2^гх*, Zгxt — At(AAt)-1AZгxt + А1(АА1)-Щ =
= (At(AAt)-1AZгХt — А:(АА:)-1Ъ:)2. (6)
Очевидно, что квадратичная форма (6) является неотрицательной полуопределённой, а значит, выпуклой. Таким образом, для любых двух точек Х,у Е Кга и скаляра а Е [0,1] выполняется неравенство Йенсена
р2(ах + (1 — а)у, П) г. Если мы покажем, что р(х1-1, П) > р(Хк-1, П), то мы покажем, что в ходе работы алгоритма происходит постепенное приближение к П. Если для итерации ] Е <г, г + 1. к - 1>точка Хз = х1-1, то мы совершили движение в сторону уменьшения расстояния, а значит, р(х1-1, П) > р(Хд-1, П). Следовательно, нам надо показать, что существует ] Е <г, г + 1. к - 1>, для которого х1-1 = Хз.
В лемме 2 покажем, что для индекса ] Е <г, г + 1. к - 1>, при котором Х^-1 = х1-1, вектор у — х1-1 не ортогонален пространству £^+1). Отсюда следует, что если мы обозначим проекцию точки уд на множество 2(Zj+1) как к, то мы получим невырожденный прямоугольный треугольник Ау1Нх1-1, а значит, р(Х1-1, П) = р(в, П). Так как р(Х^1, П) = шт^е^—) р(в, П), то ^ 2^^). Отсюда следует, что существует ] Е <г,г + 1. к - 1>, такое, что х1-1 = Хз, а значит, х1-1 = Хк-1.
Покажем теперь, что алгоритм закончит работу за конечное число итераций. Действительно, для любого г Е Л выполняется соотношение р(х1-1, П) = шт^ея^- 1) р(в, П). Но так как мы постепенно уменьшаем расстояние до П, то за конечное число шагов мы найдём минимум на всех К-плоскостях, а значит, доберёмся и до положительного решения за конечное число шагов. □
Лемма 1. Пусть на итерации г матрица Zi = Е. Если неотрицательное решение существует, то 2^+) не ортогональна вектору к = уд — х1-1.
Доказательство. Предположим, что к ортогонален 2^+). Через П проведём гиперплоскость Ф, ортогональную вектору к . Через 2(Zi+1) проведём гиперплоскость Ф, ортогональную вектору к . В силу построений Ф П Ф = 0. Рассмотрим конус неотрицательной области К = <Х | Х = а1(в1 + . + апеп, где а >0>. В дальнейшем покажем, что Ф и К лежат по разные стороны от гиперплоскости Ф (причём К и Ф могут иметь общие точки). Отсюда будет следовать, что П ПК = 0. Тем самым мы покажем, что если существует неотрицательное решение, принадлежащее конусу К, то 2(Zi+1) не ортогональна вектору к . Геометрические построения при доказательстве леммы 1 можно отследить по рисунку на с. 73.
Рассмотрим множество Г’ тех индексов, для координат которых мы обнуляли строки матрицы Zi+1 на шаге (д) алгоритма. Исключим из Г’ все индексы, единичные векторы которых лежат в Ф, и обозначим данное множество как Г. Фиксируем какой-нибудь индекс Г Е Г. Пусть V = Ф П Аёгк, где А Е К. Заметим, что V существует, так как иначе ёгк Е Ф, а мы исключили этот случай.
Произведём перенос точки х1-1 в точку 0 Е Ф. Точка уд Е Ф тогда перейдёт в новую точку и Е Ф, которая является проекцией точки 0 на Ф. Так как Ф || Ф, то для любой точки д из Ф её проекция на Ф будет вычисляться как д +(у1 -Х1-1). Покажем, что знак Гд-й координаты точки уд и знак Гд-й координаты точки и совпадают. Если это не так, то существует точка в Е \у%,и] С Ф, у которой Г-я координата равна нулю. Пусть й — это проекция в на 2(Zi+1). Точка с1 принадлежит области (х1-1, 0) в силу того, что 0 Е 2^+) С Ф и х1-1 Е 2^+) С Ф. Заметим, что Гк-я координата вектора ( в — с1) нулевая, а Гд-я координата вектора (у1 — х1-1) отрицательная, но этого не может быть, так как Ф || Ф. Следовательно, знак Гд-й координаты точки и совпадает со знаком Г-й координаты точки уд и отрицателен.
Покажем, что и Гд-я координата точки V = Ф П АГгк также отрицательна. В силу того, что Ф П Ф = 0, точка V = 0. Пусть Гд-я координата точки V положительна, тогда среди внутренних точек отрезка [й,г>] существует точка I с нулевой Гк-й координатой. Рассмотрим треугольники Д0иР, Д0м/ и ДО/ V. Угол 0м/ прямой, следовательно, угол О/ V тупой. Так как Гд-я координата точки / нулевая, то (О — / , егк) = 0. В силу этого угол Ш / прямой. Отсюда следует, что сумма углов треугольника 0/Р больше 180°. Пришли к противоречию.
Так как Г/г-я координата точки у отрицательна, то луч АгГк, где А ^ 0, лежит на противоположной П стороне относительно гиперплоскости Ф (возможны общие точки Ф и Аегк, где А ^ 0). Данное утверждение справедливо для всех лучей, образованных единичными векторами с индексами из Г. Обозначим выпуклый конус, порождённый единичными векторами с индексами из Г’, как Ф. Очевидно, что К С <х | X = Г + д, / Е £(^+1), д Е Ф>. Отсюда следует, что К Р| П =
существует неотрицательное решение, принадлежащее конусу К, то £(^+1) не ортогонально вектору к .
Графическое построение леммы 1
Лемма 2. Пусть на итерации i матрица Z = E. Тогда если неотрицательное решение существует, то для итерации j ^ i, на которой Xj = Xi-1, граничная К-плоскость £(Zj+1) не ортогональна вектору h = y — Xi-1.
Доказательство. Доказательство проведём по индукции. Базой индукции послужит случай j = i, доказанный в лемме 1. Пусть верно для j = k — 1. Покажем для j = k. Отметим, что точки y и y не совпадают по построению, точка y Е П.
Обозначим проекцию точки y на L(Zj) как yL. Из формулы (5) следует, что такая проекция строится обнулением тех координат, которые обнулены в матрице Zj. Из предположения индукции следует, что p(Xi-1, П) > П) как отношение
длины катета и гипотенузы. Следовательно, Xi-1 = y¡L. Заметим, что отрезок [y, yL] лежит в L(Zj), а для функции (6) на линейном пространстве выполняются следующие неравенства p(Xi-1, П) > p(yj, П).
Далее покажем, что на К-плоскости L(Zj+1) лежит точка, расстояние от которой до П меньше, чем p(Xi-1, П). Отсюда сразу же будет следовать, что граничная К-плоскость £(Zj+1) не ортогональна вектору h = y — Xi-1.
Пусть множество в — это множество тех индексов единичных векторов e¿, которые входят в строки матрицы Zj, но отсутствуют среди строк матрицы Zj+1. Заметим, что координаты с индексами из в точки y неположительны по условиям работы алгоритма. Векторное подпространство L(Zj) С L(Zi+1), проекция вектора y на £(Zi+1) строится обнулением соответствующих координат, а координаты с индексами из в проекции y на L(Zi+1) неотрицательны в силу построений леммы 1, следовательно, координаты с индексами из в точки yL неотрицательны.
Так как Zj = Zj+1, то мощность в больше нуля. Проведём процедуру, уменьшающую мощность в так, чтобы построить точку из £(Zj+1), в которой значение
функции (6) меньше, чем в точке х1-1. Для этого введём следующие обозначения: щ = уз, и1 = у^ = ^.
После переобозначений получим следующие необходимые для проведения процедуры уменьшения мощности в условия: отрезок [у^и^ С 2(^), расстояние р(х1-1, П) > р(у1, П), расстояние р(х1-1, П) > р(и1, П), координаты с индексами из в точки ;и1 неположительны, а координаты с индексами из в точки и1 неотрицательны.
Процедура, уменьшающая мощность в: найдём точку у2 отрезка [У1,и1>, которая первой при движении от точки у1 в сторону точки и1 обнуляет хотя бы одну координату, соответствующую индексам из в. Удалим из множества в индексы, которые обнулились в точке у1. Обозначим матрицу ^^ как матрицу, совпадающую с матрицей Zj+1. Добавим ^^ единичные векторы-строки, индексы которых присутствуют в в. Далее обозначим проекцию точки у на 2^2) как и2.
Покажем, что у нас выполнены все условия, чтобы повторить процедуру для отрезка [у2,и2] С 2(Z,2). Действительно, так как выполняется неравенство Йенсе-на, то р(х1-1, П) > р(у2, П). Отсюда следует, что на 2^2) есть точка минимума функции (6), не совпадающая с х1-1, следовательно, р(х1-1, П) > р(и2, П), а значит, х1-1 = и2. Координаты с индексами из в точки у2 неположительны по построению. Векторное подпространство 2(Z2) С 2^+), проекция вектора у на 2^+) строится обнулением соответствующих координат, а координаты с индексами из в проекции у1 на 2(Zi+1) неотрицательны в силу построений леммы 1, следовательно, координаты с индексами из в точки и2 неотрицательны.
Пусть на повторе процедуры под номером в мы пришли к ситуации, когда мощность в равна нулю. Очевидно, что в конечна, так как конечна мощность в и на каждом повторе процедуры гарантированно происходит уменьшение мощности в. Заметим, что на повторе в матрица = Zj+1, следовательно, У3+1 Е [у8,й8] С 2(Zj+1). По построению р(х1-1 , П) > р(у3+1, П), поэтому граничная К-плоскость 2^з+1) не ортогональна вектору к = у1 — х1-1. □
5. Численные эксперименты
Целью численных экспериментов ставились поиск задач, на которых алгоритм показал бы время работы, наиболее близкое к полученной оценке, и проверка алгоритма на устойчивость. Для этих целей алгоритм был проверен на задаче Кли — Минти [6], на данных которой симплекс-метод Данцига совершает обход по всем вершинам симплекса за 2п шагов, а также и на группе случайных тестов.
Реализация алгоритма была осуществлена без потери точности в классе рациональных чисел библиотеки ОМР [7]. Для проверки численной устойчивости в тестах отслеживались два параметра — в и 7, где в — это минимальное количество бит, необходимых для кодирования любой переменной матрицы входных данных Аг(ААг)-1А, а 7 — это максимальное количество бит, которое потребовалось для кодирования любой промежуточной координаты вектора х1, вектора уд или коэффициента а из шага (б) алгоритма.
Результаты практической проверки для задачи Кли — Минти сведены в табл. 1. Первая строка п таблицы содержит размерность задачи Кли — Минти, во второй строке Б приводится экспериментальное число шагов предложенного алгоритма для данной размерности. Данные третьей и четвёртой строк соответствуют экспериментальным данным по параметрам в и 7, а пятая строка является отношением в, которое позволяет определить соотношение количества бит, необходимых для кодирования промежуточных и входных данных.
Проверка на данных задачи Кли — Минти
n 9 10 11 12 13 14 15 16 17 18 19 20
S 54 63 72 82 92 103 114 126 138 151 164 178
в 120 134 158 170 200 220 236 262 276 303 330 348
Y 224 270 302 346 390 436 468 522 563 604 655 697
Y в 1.86 2.01 1.91 2.03 1.95 1.98 1.98 1.99 2.03 1.99 1.98 2.00
Для инициализации случайных тестов квадратная матрица размерами п на п, отвечающая системе линейных неравенств, и вектор целевой функции заполнялись случайными знаковыми 32-битными целыми. Сгенерированная таблица симплекс-методом Данцига проверялась на наличие решения и в случае существования оптимума отдавалась на проверку предложенному в работе алгоритму. Для каждого рассматриваемого размера проводилось по тысяче случайных тестов. Результаты тестов сведены в табл. 2. Первая строка п таблицы содержит размерность случайной задачи. Во второй строке Б приводится максимальное экспериментальное число шагов алгоритма для данной размерности, которое было обнаружено при тестировании. Данные третьей и четвёртой строк соответствуют экспериментальным данным по параметрам в и 7, которые отвечают максимальному обнаруженному значению дроби 7/в для данной размерности, значение которой занесено в пятую строку.
Проверка на случайных тестах
n 7 8 9 10 11 12 13 14 15
S 45 50 54 63 61 72 77 82 89
в 768 912 1028 1136 1256 1368 1504 1624 1736
Y 2822 3227 3837 4027 4527 4418 4630 5424 5879
Y в 3.67 3.53 3.73 3.54 3.60 3.22 3.07 3.34 3.38
Низкое значение дроби 7/в и отсутствие роста её значения при увеличении размерности задачи на случайных экспериментальных данных свидетельствуют о хорошей численной устойчивости предлагаемого алгоритма.
Из табл. 1 видно, что на данных задачи Кли — Минти предложенный алгоритм показывает преимущество по количеству шагов над алгоритмом симплекс-метода Данцига. Из данных табл. 2 видно, что набору случайных тестов не удалось найти задачу, которая по числу итераций приближалась бы к значению 2nn. Однако результаты данных тестов нельзя интерпретировать в пользу полиномиальности предлагаемого алгоритма, так как и симплекс-метод Данцига, являющийся полиномиальным в среднем алгоритмом [2, с. 142-147], тоже не показал на этих тестах «плохих» результатов. Поэтому вопрос о наличии примеров, подтверждающих экс-поненциальность предложенного алгоритма, остаётся открытым.
1. Дикин, И. И. Итеративное решение задач линейного и квадратичного программирования / И. И. Дикин // Докл. АН СССР. — 1967. — Т. 174, № 4. — С. 745-747.
2. Schrijver, A. Theory of Linear and Integer Programming / A. Schrijver. — Wiley-Interscience series in discrete mathematics. — Chichester : John Wiley & Sons, 1986. — xi+471 p.
3. Моллаверди, Н. Методы решения задач линейной оптимизации большой размерности : дис. канд. физ.-мат. наук / Н. Моллаверди. — М. , 2005. — 96 с.
4. Karmarkar, N. A new polynomial-time algorithm for linear programming / N. Karmarkar // Combinatorica. — 1984. — № 4. — Р. 373-395.
5. Розенфельд, Б. А. Многомерные пространства / Б. А. Розенфельд. — М. : Наука, 1966. — 648 с.
6. Klee, V. How good is the Simplex algorithm? / V. Klee, G. J. Minty // Inequalities: III, ed. O. Shisha. — New York : Academic Press, 1972. — P. 158-175.
7. Nikolaevskaya, E. Programming with Multiple Precision / E. Nikolaevskaya, A. Khimich, T. Chistyakova. — Studies in Computational Intelligence. — Vol. 397. — Richmond, USA : Springer, 2012. — 234 p.
Поступила в ‘редакцию 08.04-2016 После переработки 21.05.2016
Сведения об авторах
Севостьянов Егор Николаевич, ведущий инженер-программист (руководитель группы математического моделирования), ЗАО «Диджитал Айрон Пайп», Челябинск, Россия; e-mail: y384@mail.ru.
Лепчинский Михаил Германович, кандидат физико-математических наук, доцент кафедры вычислительной математики, Челябинский государственный университет, Челябинск, Россия; e-mail: myth@csu.ru.
Chelyabinsk Physical and Mathematical Journal. 2016. Vol. 1, iss. 2. P. 68-77.
ALGORITHM FOR FINDING OF A NON-NEGATIVE SOLUTION FOR LINEAR SYSTEM OF EQUATIONS
E.N. Sevostyanov1″, M.G. Leptchinski26
1ZAO «Digital Iron Pipe», Chelyabinsk, Russia 2 Chelyabinsk State University, Chelyabinsk, Russia ay384@mail.ru; bmyth@csu.ru
The new algorithm for finding of the exact solution for the linear programming problem is constructed. The method is based on the converting of the linear programming problem to the problem of solving in nonnegative numbers for a system of linear equations with an incomplete rank. This problem is solved by successive approximations in specially constructed subspaces. The convergence of the algorithm for a finite number of the steps is proved. The algorithm has been tested on the data of the Klee — Minty problem and on a set of random tests.
Keywords: algorithm of linear programming, non-negative solution of linear system of equations, linear inequality.
1. Dikin I.I. Iterativnoe reshenie zadach lineynogo i kvadratichnogo programmirovaniya [Iterative solving of linear and quadratic programming problems]. Doklady Akademii Nauk SSSR [USSR Academy of Science Reports], 1967, vol. 174, no. 4, pp. 745-747. (In Russ.).
2. Schrijver A. Theory of Linear and Integer Programming. Wiley-Interscience series in discrete mathematics. Chichester, John Wiley & Sons, 1986. xi+471 p.
3. Mollaverdi N. Metody resheniya zadach lineynoy optimizatsii bol’shoy razmernosti [Methods for solving of linear optimization problems with large dimension. Thesis]. Moscow, 2005. 96 p. (In Russ.).
4. Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984, no. 4, pp. 373-395.
5. Rozenfel’d B.A. Mnogomernye prostranstva [Multidimensional spaces]. Moscow, Nauka Publ., 1966. 648 p. (In Russ.).
6. Klee V, Minty G.J. How good is the Simplex algorithm? Inequalities: III. New York, Academic Press, 1972. Pp. 158-175.
7. Nikolaevskaya E., Khimich A., Chistyakova T. Programming with Multiple Precision. Studies in Computational Intelligence, vol. 397. Richmond, USA, Springer, 2012. 234 p.
Accepted article received 08.04.2016 Corrections received 21.05.2016
http://matrixcalc.org/slu.html
http://cyberleninka.ru/article/n/algoritm-nahozhdeniya-neotritsatelnogo-resheniya-sistemy-lineynyh-uravneniy