Fuertes, universalmente fuertes y débiles vectores propios de intervalo en álgebra max-plus
Autores: Gavalec, Martin; Plavka, Ján; Ponce, Daniela
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Fuertes, universalmente fuertes y débiles vectores propios de intervalo en álgebra max-plus
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problemas de optimización
Programación
Gestión de proyectos
álgebra max-plus
Eigenvectores de intervalo
Ejemplos numéricos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
Los problemas de optimización, como la programación de horarios o la gestión de proyectos, en los que la función objetivo depende de las operaciones y , pueden formularse y resolverse de manera natural en álgebra max-plus. Un sistema de eventos discretos, por ejemplo, activaciones de procesadores en computación paralela, o activaciones de otras máquinas cooperantes, se describe mediante un sistema de ecuaciones lineales max-plus. En particular, si el sistema se encuentra en un estado estacionario, como una red informática sincronizada en el procesamiento de datos, entonces el vector de estado es un autovector del sistema. En realidad, las entradas de las matrices y los vectores se consideran como intervalos. En este documento se estudian las propiedades y algoritmos de reconocimiento para varios tipos de autovectores de intervalo. Para una matriz de intervalo y un vector de intervalo dados, se define un conjunto de generadores. Luego, se estudian y describen los autovectores fuertes y fuertemente universales como combinaciones lineales max-plus de generadores. Además, se sugiere un algoritmo de reconocimiento polinómico y se demuestra su corrección. Resultados similares se presentan para los autovectores débiles. Los resultados se ilustran con ejemplos numéricos. Los resultados tienen un carácter general y pueden aplicarse en todo álgebra max-plus y en cada instancia del problema de autovalor de intervalo.
Descripción
Los problemas de optimización, como la programación de horarios o la gestión de proyectos, en los que la función objetivo depende de las operaciones y , pueden formularse y resolverse de manera natural en álgebra max-plus. Un sistema de eventos discretos, por ejemplo, activaciones de procesadores en computación paralela, o activaciones de otras máquinas cooperantes, se describe mediante un sistema de ecuaciones lineales max-plus. En particular, si el sistema se encuentra en un estado estacionario, como una red informática sincronizada en el procesamiento de datos, entonces el vector de estado es un autovector del sistema. En realidad, las entradas de las matrices y los vectores se consideran como intervalos. En este documento se estudian las propiedades y algoritmos de reconocimiento para varios tipos de autovectores de intervalo. Para una matriz de intervalo y un vector de intervalo dados, se define un conjunto de generadores. Luego, se estudian y describen los autovectores fuertes y fuertemente universales como combinaciones lineales max-plus de generadores. Además, se sugiere un algoritmo de reconocimiento polinómico y se demuestra su corrección. Resultados similares se presentan para los autovectores débiles. Los resultados se ilustran con ejemplos numéricos. Los resultados tienen un carácter general y pueden aplicarse en todo álgebra max-plus y en cada instancia del problema de autovalor de intervalo.