Диссертация (1150576), страница 14
Текст из файла (страница 14)
4, no. 8. — P. 222–227.9792. Ramani, T. Scheduling of industrialized construction project using graphicalevaluation and review technique (GERT) / T. Ramani, R. Kannan // SecondInternational Conference on Advances in Industrial Engineering Applications.— 2014. — P. 35–39.93. Романовский, И. В. Алгоритмы решения экстремальных задач / И. В. Романовский. — Москва: Наука, 1977. — 352 с.94. Демьянов, В. Ф. К теории нелинейных минимаксных задач / В. Ф. Демьянов, В.
Н. Малоземов // Успехи математических наук. — 1971. — Т. 26,№ 3 (159). — С. 53–104.95. Демьянов, В. Ф. Введение в минимакс / В. Ф. Демьянов, В. Н. Малоземов.— Москва: Наука, 1972. — 368 с.96. Даугавет, В. А. Квадратичная скорость сходимости одного метода линеаризации для решения дискретных минимаксных задач / В. А. Даугавет,В. Н.
Малоземов // Журнал вычислительной математики и математи-ческой физики. — 1981. — Т. 21, № 4. — С. 835–843.97. Моделирование систем и процессов: учебник. Серия 58. Бакалавр. Академический курс (1-е изд.) / В. Н. Волкова, В. Н. Козлов, А. Н. Фирсов и др.— Москва: Издательствово Юрайт, 2015. — Т. 58 Бакалавр. Академический курс (1-е изд.). — 450 с.98. Маркова, Е. М. Решение задачи сетевого планирвоания методами тропической алгебры / Е. М. Маркова, Д. А.
Николаев // Сборник тезисов докладов научной конференции студентов и аспирантов Липецкого государственного технического университета. — 2016. — С. 384–387.99. Нормы радиационной безопасности (НРБ-99/2009) / СанПин. —№2.6.1.2523-09, Москва, 2009. Минздрав России.100. Основные санитарные правила обеспечения радиационной безопасности(ОСПОРБ-99/2010) / СанПин. — № 2.6.1.2612-10, Москва, 2010. МинздравРоссии.98101.
Krivulin, N. A new algebraic solution to multidimensional minimax locationproblems with Chebyshev distance / N. Krivulin // WSEAS Transactions onMathematics. — 2012. — Vol. 11, no. 7. — P. 605–614.102. Krivulin, N. Direct solutions to tropical optimization problems with nonlinearobjective functions and boundary constraints / N.
Krivulin, K. Zimmermann //Mathematical Methods and Optimization Techniques in Engineering: Proc.1st Intern. Conf. on Optimization Techniques in Engineering (OTENG ’13),Antalya, Turkey. — WSEAS Press, 2013. — P. 86–91.103. Krivulin, N. Algebraic solution of tropical optimization problems via matrixsparsification with application to scheduling / N.
Krivulin // Journal of Logicaland Algebraic Methods in Programming. — 2017. — Vol. 89. — P. 150–170.99Список рисунков1.1Схема подсчета слагаемых . . . . . . . . . . . . . . . . . . . .311.2Пример множества решений задачи без ограничений. . . . . . . .341.3Пример множества решений задачи с ограничениями (множествапересекаются).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.44.135Пример множества решений задачи с ограничениями (множестване пересекаются). . . . . . . . . . . . . . . . . . . . . . . . . . . . .37Узлы неравенства81. . . . . . . . . . . . . . . . . . . . . . . . . .
.100Приложение АПрограммная реализация задачи с псевдоквадратичной целевой функциейДля расчетов в главах 1 и 2 использовалось программное обеспечение, написанное на языке , листинг которого приводится в настоящемприложении,атакжеразмещенврепозиториипоадресуhttps://github.com/SovanSB/Idempotent/. Эта программа позволяет проводить вычисления и решать рассмотренные выше задачи оптимизации вразличных идемпотентных полуполях.Структура программного обеспеченияВ программе реализованы следующие функции:– Функция мультипликативно сопряженного транспонирования — ;– Функция сложения матриц в идемпотентном полуполе — ;– Функция перемножения матриц в идемпотентном полуполе — ;– Оператор «звезда Клини» — ;– Функция вычисления следа матрицы в идемпотентном полуполе — ;– Функция вычисления тропического аналога определителя — ;– Функция вычисления тропического спектрального радиуса матрицы —;101– Функция, решающая задачу с псевдоквадратичной целевой функцией безограничений (1.7), — ;– Функция вычисления необходимых компонент — ;– Функция, решающая задачу с псевдоквадратичной целевой функцией сограничениями (1.11), — ;– Функции для работы в полуполе Rmax ,+ ;– Функция нахождения минимума в расширенной задаче чебышевской аппроксимации (3.3), — ;– Функция разрежения матрицы в расширенной задаче чебышевской аппроксимации (3.3), — ;– Функция получения модифицированной разреженной матрицы задачи, — ;– Функция для упорядочивания элементов в столбцах по возрастанию, — ;– Функция поиска наилучшей строки из списка, — ;– Функция для отбрасывания избыточных границ, — ;– Процедура поиска множества решений расширенной задачи чебышевскойаппроксимации (3.3), — .Функция мультипликативно сопряженного транспонирования принимает на вход обязательный параметр — вектор, а также необязательные:функцию обращение числа и тропический нуль .
Здесь и далее, еслине указывать необязательные параметры, по умолчанию используется полуполеRmax ,+ .Функция сложения матриц в идемпотентном полуполе принимаетна вход обязательный параметр — набор векторов/матриц, а также необязательные: функцию тропического сложения и параметр учета пропущенныхзначений .. За основу для этой функции была взята встроенная функция102. Используется в случае, если сложение матриц не задано явно другойфункцией.Функция перемножения матриц в идемпотентном полуполе принимает на вход обязательные параметры — две матрицы подходящего размера,необязательные: функцию тропического сложения и функцию тропического умножения .Оператор «звезда Клини» принимает на вход обязательный параметр —квадратную матрицу, необязательные: функцию тропического сложения ,функцию тропического умножения , тропический нуль , тропическуюединицу , функцию сложения матриц .Функция вычисления следа матрицы в идемпотентном полуполе принимает на вход обязательный параметр — квадратную матрицу, необязательный— функцию тропического сложения .Функция вычисления тропического аналога определителя принимает навход обязательный параметр — квадратную матрицу, необязательные: функциютропического сложения и функцию тропического умножения .Функция вычисления спектрального радиуса матрицы в идемпотентном полуполе принимает на вход обязательный параметр — квадратную матрицу, необязательные: функцию тропического сложения , функцию тропического умножения и функцию тропического возведения в степень .Функция , решающая задачу без ограничений, принимает на входобязательные параметры: матрицу , векторы , , скаляр , необязательные: функцию тропического сложения , функцию тропического умножения, тропический нуль , тропическую единицу , функцию сложения матриц , функцию тропического возведения в степень , функциювзятия обратного по умножению .Функция для вычисления необходимых компонент принимаетна вход обязательные параметры: матрицы и , необязательные: функциютропического сложения , функцию тропического умножения , тропический нуль , тропическую единицу , функцию сложения матриц.
На выходе выдается список, содержащий — массив матриц ,−1 , = 0 . . . − 1, — массив матриц , = 0 . . . , а также исходныематрицы.103Функция , решающая задачу с ограничениями, принимает на входобязательные параметры: матрицу , векторы , , скаляр , матрицу ,необязательные: функцию тропического сложения , функцию тропическогоумножения , тропический нуль , тропическую единицу , функцию сложения матриц , функцию тропического возведения в степень ,функцию взятия обратного по умножению .Эти функции использовались для проведения расчетов в настоящей работе.Несмотря на то, что все примеры приводились в полуполе Rmax,+ , приведенныевыше функции могут корректно работать и в иных полуполях при заданиисоответствующих этим полуполям необязательных параметров.Листинг А.1: Исходные коды использованных функций123456# Функция для мультипликативно сопряженного транспонирования матриц.conjInv <- function (x , inv = maxplusinv , zero = - Inf ) {res <- matrix ( zero , nrow ( x ) , ncol ( x ) )res [ x != zero ] = inv ( x [ x != zero ])t ( res )}789101112131415161718192021# Функция перемножения матриц.multiply <- function (A , B , plus = max , mult = add ) {if ( ncol (A ) != nrow ( B ) )stop (" Incompatible matrices !")rows <- nrow ( A )cols <- ncol ( B )res <- matrix (0.
, nrow = rows , ncol = cols )for ( i in 1: rows ) {for ( j in 1: cols ) {res [i , j ] <- plus ( mult ( A [i ,] , B [ , j ]) )}}res}2223242526# Функция сложения матриц. Используется, если сложение матриц не задано явно.parplus <- function (... , plus = max , na . rm = FALSE ){elts <- list (...)104if ( length ( elts ) == 0 L )stop (" no arguments ")mmm <- elts [[1 L ]]attr ( mmm , " dim ") <- NULLhas . na <- FALSEfor ( each in elts [ -1 L ]) {attr ( each , " dim ") <- NULLl1 <- length ( each )l2 <- length ( mmm )if ( l2 < l1 ) {if ( l2 && l1 %% l2 )warning (" an argument will be fractionally recycled ")mmm <- rep ( mmm , length . out = l1 )}else if ( l1 && l1 < l2 ) {if ( l2 %% l1 )warning (" an argument will be fractionally recycled ")each <- rep ( each , length .
out = l2 )}nas <- cbind ( is . na ( mmm ) , is . na ( each ) )if ( has . na || ( has . na <- any ( nas ) ) ) {mmm [ nas [ , 1 L ]] <- each [ nas [ , 1 L ]]each [ nas [ , 2L ]] <- mmm [ nas [ , 2 L ]]}len <- length ( mmm )for ( i in 1: len ) {mmm [ i ] <- plus ( mmm [i ] , each [ i ])}if ( has . na && ! na . rm )mmm [ nas [ , 1 L ] | nas [ , 2 L ]] <- NA}mostattributes ( mmm ) <- attributes ( elts [[1 L ]])mmm27282930313233343536373839404142434445464748495051525354555657585960}616263646566# Оператор Звезда<< Клини > >.ast <- function (A , plus = max , mult = add , zero = -Inf ,identity = 0 , pplus = NULL ) {d <- ncol ( A )if ( d != nrow ( A ) )105stop (" Non - square matrix is given !")id <- matrix ( zero , d , d , byrow = TRUE )if ( d > 1)diag ( id ) <- identityelse id <- identityres <- idtemp <- Aif ( is .
null ( pplus ) )pplus <- function (...) parplus (... , plus = plus )res <- pplus ( res , temp )if ( d > 2) {for ( i in 1:( d -2) ) {temp <- multiply ( temp , A , plus , mult )res <- pplus ( res , temp )}}res676869707172737475767778798081828384}858687888990919293949596# Функция вычисления следа матрицы.tr <- function (A , plus = max ) {d <- ncol ( A )if ( d != nrow ( A ) )stop (" Non - square matrix is given !")if ( d > 1)temp <- plus ( diag ( A ) )elsetemp <- A [1 ,1]temp}979899100101102103104105106# Функция вычисления тропического аналога определителя.Tr <- function (A , plus = max , mult = add ) {d <- ncol ( A )if ( d != nrow ( A ) )warning (" Non - square matrix is given !")temp <- Ares <- tr (A , plus )for ( i in 2: d ) {temp <- multiply ( temp , A , plus , mult )106res <- plus ( res , tr ( temp ) )107}res108109110}111112113114115116117118119120121122123124# Функция вычисления спектрального радиуса матрицы.spectr <- function (A , plus = max , mult = add , deg = div ) {d <- ncol ( A )if ( d != nrow ( A ) )warning (" Non - square matrix is given !")temp <- Ares <- tr ( A )for ( i in 1:( d -1) ) {temp <- multiply ( temp , A , plus , mult )res <- plus ( res , deg ( tr ( temp , plus ) , 1/( i +1) ) )}res}125126127128129130131132133134135136137138139140141142143144145146# Функция, решающая задачу без ограничений.unconstr <- function (A , p , q , r , plus = max , mult = add ,zero = -Inf , identity = 0 , pplus = NULL ,deg = div , inv = maxplusinv ) {lambda <- spectr (A , plus , mult , deg )if ( lambda == zero )stop (" Incorrect matrix : eigenvalue equals zero !")myu <- plus ( lambda , r )qm <- conjInv (q , inv = inv , zero = zero )d <- nrow ( A )temp <- matrix ( zero , d , d , byrow = TRUE )diag ( temp ) <- identityfor ( i in 1: d ) {myu <- plus ( myu , deg ( multiply ( multiply ( qm , temp , plus , mult ) ,p , plus , mult ) , 1/( i + 1) ) )temp <- multiply ( temp , A , plus , mult )}myuminus <- inv ( myu )matr <- ast ( mult ( myuminus , A ) , plus , mult , zero , identity , pplus )left <- mult ( myuminus , p )right <- mult ( myu , conjInv ( multiply ( qm , matr , plus , mult ) ,107inv = inv , zero = zero ) )list ( myu = myu , matr = matr , left = left , right = right , A = A ,p = p, q = q, r = r)147148149150}151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183# Функция, вычисляющая S_ { km }sCreate <- function (A , B , plus = max , mult = add , zero = -Inf ,identity = 0 , pplus = NULL ) {n <- nrow ( A )# Массивы, используемые для вычисления M_ { km }.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
