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

  • Людмила Андреевна Пилипчук Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Республика Беларусь

Аннотация

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

Биография автора

Людмила Андреевна Пилипчук, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Республика Беларусь

кандидат физико-математических наук; доцент кафедры компьютерных технологий и систем факультета прикладной математики и информатики

Литература

  1. Bianco L., Confessore G., Gentili M. Combinatorial aspects of the sensor location problem. ann. oper. Res. Vol. 144, issue 1. 2006. P. 201–234. DOI: 10.1007/s10479-006-0016-9.
  2. Pilipchuk L. A. [Sparse underdetermined systems of linear algebraic equations]. Мinsk, 2012 (in Russ.).
  3. Pilipchuk L. A., Vishnevetskaya T. S., Pesheva Y. H. Sensor location problem for a multigraph. Math. Balk. New Ser. Vol. 27. Fasc. 1–2. 2013. P. 65–75.
  4. Pilipchuk L. A., Pilipchuk A. S., Ramanouski Y. V. Optimal location of sensors on a multigraph with zero split ratios of some arc flows. AIP Conf. Proc. 2014. Vol. 1631. P. 350 –353. DOI: 10.1063/1.4902497.
  5. Pilipchuk A. S. The location of the minimum number of monitored nodes in the generalized graph for estimating traffic its unobservable part. Vestnik BGU. Ser. 1, Fiz. Mat. Inform. 2015. No. 1. P. 108–111 (in Russ.).
  6. Pilipchuk L. A., Pilipchuk A. S. Sparse linear systems: theory of decomposition, methods, technology, applications and implementation in Wolfram Mathematica. AIP Conf. Proc. 2015. Vol. 1690, issue 1. DOI: 10.1063/1.4936744.
  7. Pilipchuk L. A., German O. V., Pilipchuk A. S. The general solutions of sparse systems with rectangular matrices in the problem of sensors optimal location in the nodes of a generalized graph. Vestnik BGU. Ser. 1, Fiz. Mat. Inform. 2015. No. 2. P. 91– 96.
Опубликован
2018-01-24
Ключевые слова: мультиграф, разреженная система, ранг, декомпозиция, опора, единственное решение
Как цитировать
Пилипчук, Л. А. (2018). Методы декомпозиции разреженных cистем линейных алгебраических уравнений для оценки трафика обобщенного мультиграфа. Журнал Белорусского государственного университета. Математика. Информатика, 2, 37-43. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/747
Выпуск
№ 2 (2017): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).