[ Алгоритмы и программные средства решения
вычислительных задач тропической математики
Губанов Сергей Александрович, гр. 522
Санкт-Петербургский государственный университет
Математико-механический факультет
Кафедра статистического моделирования
Научный руководитель: д.ф.-м.н., доцент Кривулин Н.К.
Рецензент: к.ф.-м.н., доцент Христинич В.Б.
Санкт-Петербург 2012г.
1/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Введение Введение Введение Идемпотентная алгебра занимается изучением полуколец с 1 идемпотентным сложением.
Это быстро развивающийся раздел прикладной математики, находящий широкое применение.
Изучению идемпотентной алгебры посвящены работы Н.Н.
Воробьева, И.В. Романовского, В.П. Маслова, а также других российских и зарубежных учёных.
Многие задачи оптимизации сводятся в терминах идемпотентной алгебры к решению линейных уравнений.
Целый ряд алгоритмов решения таких задач, после их перевода на язык идемпотентной алгебры, оказываются аналогами вычислительных процедур линейной алгебры.
Возникает потребность иметь программные средства для решения задач идемпотентной алгебры.
2/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Введение Дипломная работа содержит:
Основные определения идемпотентой алгебры, на которые опираются представленные алгоритмы, Описание алгоритмов решения линейных уравнений 1–го и 2–го рода в идемпотентной алгебре, Формализацию и решение различных уравнений и неравенств 1–го и 2–го рода в алгебре Rmax,+, Представление результатов в общем виде, удобном для их реализации в виде вычислительных процедур, Разработанную на основе полученных результатов библиотеку классов.
3/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Основные определения Основные определения Идемпотентное полуполе Пусть X, 0, 1,, – идемпотентное полуполе, то есть коммутативное полукольцо с нулем 0 и единицей 1, сложение идемпотентно, другими словами X =.
каждый ненулевой элемент имеет обратный по умножению.
Определено отношение частичного порядка, так что В дальнейшем будем рассматривать полуполе где R — множество вещественных чисел.
4/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Общие сведения Идемпотентная алгебра матриц Операции сложения, умножения матриц и операция умножения на скаляр X определяются как обычно:
псевдообратную матрицу = ( ) X с элементами 5/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Линейные уравнения первого рода Определение уравнения относительно вектора X называется уравнение Теорема 1 (Кривулин, 2006) Уравнение = имеет решение тогда и только тогда, При этом = ( ) является максимальным решением.
Если столбцы матрицы образуют минимальную систему векторов, порождающую, то других решений нет.
6/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Линейные уравнения первого рода Общее решение уравнения Пусть – набор индексов столбцов, образующий минимальную порождающую систему векторов.
Пусть – множество всех таких наборов индексов.
Множество = только когда уравнение имеет решение.
Теорема 2 (Кривулин, 2006) Если уравнение = разрешимо,то его общим решением является семейство решений 7/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Алгоритм решения уравнения Будем считать, что уравнение = является приведённым (в нет нулевых элементов).
Алгоритм решения уравнения = :
матрицы, то уравнение имеет решение 8/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Уравнения второго рода Основные определения Неоднородное уравнение второго рода:
Нормальная форма матрицы :
где — неразложимая или нулевая квадратная матрица порядка, — произвольная матрица размера Матрица разложима, если одинаковыми перестановками строк и столбцов ей можно придать нормальную форму.
9/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Вспомогательные величины Определим следующие вспомогательные матрицы матрицу, столбцы которой удовлетворяют условию 10/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Решение уравнений 2–го рода и смешанных систем Теорема 3 (Кривулин, 2006) Пусть общее решение однородного уравнения с неразложимой матрицей. Тогда справедливы утверждения:
Алгоритм решение системы 11/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Сведение некоторых задач к ранее решённым При помощи рассмотренных выше алгоритмов можно решать следующие уравнения и неравенства идемпотентной алгебры:
Аналогично можно решать составленные из них системы.
Оказалось, что решение всех рассматриваемых уравнений, неравенств и их систем можно представить в виде 12/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Сведение некоторых задач к ранее решённым На основе метода, предложенного Бутковичем, осуществляется сведение к базовым задачам.
13/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Сведение некоторых задач к ранее решённым Для неоднородного уравнения второго рода = Для неоднородного неравенства второго рода 14/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Сведение некоторых задач к ранее решённым 15/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Разработанны программные средства для решения линейных уравнений, неравенств и их систем над Rmax,+.
Для написания программы используется среда Microsoft Visual Studio 2008. При этом используются только библиотеки, изначально содержащихся в C++.
Это позволяет обеспечить переносимость исходного кода в любую операционную среду.
Выбран общий вид решения для базовых задач.
В программе реализованы класс матриц, позволяющий производить вычисления над полуполем Rmax,+.
Класс задач, проверяющий корректность условия задачи, и подготавливающий данные для класса решений.
Класс решений, реализующий описанные алгоритмы и формирующий общий вид решения.
16/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики Заключение Рассмотрены алгоритмы решения линейных однородных уравнений первого и второго рода.
Предложен способ сведения уравнений, неравенств и их систем к однородным уравнениям первого и второго рода.
Предложен общий вид решения линейных уравнений, неравенств и их систем.
Выполнена программная реализация решений линейных уравнений, неравенств и их систем.
Обеспечена возможность работы программы в любой операционной системе, без значительных изменений.
17/17 Губанов Сергей Александрович, гр. 522 Вычислительные задачи тропической математики
«