Алгоритм построения наследственно минимаксной сети с заданным вектором степеней узлов

В отличие от классической транспортной задачи, где известны пункты производства и потребления, и требуется минимизировать стоимость перевозки, в настоящей работе рассмотрен минимаксный критерий. В частности, ищется матрица с минимальным наибольшим элементом в классе неотрицательных матриц с заданными суммами элементов строк и столбцов. В таком случае минимаксный критерий можно интерпретировать следующим образом. Допустим, что время перевозки из пункта производства в пункт потребления пропорционально объему перевозки. Тогда минимате - минимальное время, необходимое для перевозки всего объема. Это обычная ситуация, когда принимающий решения не знает тарифных коэффициентов. В других ситуациях они не имеют смысла, как и нелинейные тарифные целевые функции. В этих случаях минимаксная интерпретация приводит к эффективному решению. Для классов неоринтированных сетей с заданным вектором степеней узлов (транспортных и сетевых многогранников) с применением характеристических функций получены аналитические формулы для вычисления минимаксных значений, выраженных через координаты вектора и неотрицательный параметр. Минимаксные значения определяют необходимые и достаточные условия, при которых усеченные многогранники не пустые множества. Получен алгоритм построения наследственно минимаксной сети в сетевых многогранниках.

Литература

[1] Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ / под ред. И.В. Красикова. М.: Вильямс, 2005. 1296 с.

[2] Зыков А.А. Основы теории графов. М.: Вузовская книга, 2004. 664 с.

[3] Миронов А.А., Цурков В.И. Наследственно минимаксные матрицы в моделях транспортного типа // Известия РАН. Теория и системы управления. 1998. № 6. С. 104-121.

[4] Миронов А.А., Цурков В.И. Открытые транспортные модели с минимаксным критерием // ДАН. 2001. Т. 381. № 4. С. 448-451.

[5] Tsurkov V., Mironov A. Minimax under transportation constrains. Dordrecht-Boston-London: Kluwer Academic Publishers, 1999.

[6] Лукоянов Н.Ю. Минимаксные и вязкостные решения в задачах оптимизации наследственных систем // Труды института математики и механики УрО РАН. 2009. Т. 15. № 4. С. 183-194.

[7] Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. 382 с.

[8] Goldsmith A. Wireless communications. Cambridge University Press, 2005. 571 p.

[9] Lewis F.L. Wireless sensor networks // Smart Environments: Technologies, Protocols, and Applications. New York: John Wiley, 2004. 432 p.

[10] Тищенко С.А. Сепараторы в планарных графах как новый способ их характеризации // Фундамент. и прикл. матем. 2002. Т. 8. № 4. C. 1193-1214.

[11] Voloshin V.I. Introduction to graph and hypergraph theory. New York: Nova Science Publishers, 2009.

[12] Селин П.С., Цурков В.И. Метод характеристических функций для классов сетей с фиксированными степенями узлов // Известия РАН. Теория и системы управления. 2014. № 5. С. 28-37. DOI: 10.7868/S0002338814050126

[13] Ding J., Tana P., Lu Y.-Z. Optimizing the controllability index of directed networks with the fixed number of control nodes // Neurocomputing. 2016. Vol. 171. P. 1524-1532.

[14] Fontanari J.F., Rodrigues F.A. Influence of network topology on cooperative problemsolving systems // Theory in Biosciences. 2015. P. 1-10.

[15] Peng G.-S., Wu J. Optimal network topology for structural robustness based on natural connectivity // Physica A: Statistical Mechanics and its Applications. 2016. Vol. 443. P. 212-220. URL: http://dx.doi.org/10.1016/j.physa.2015.09.023

[16] Abello J., Queyroi F. Network decomposition into fixed points of degree peeling // Social Network Analysis and Mining. 2014. No. 4. P. 191.

[17] Horvat E.-A., Zweig K.A. A fixed degree sequence model for the one-mode projection of multiplex bipartite graphs // Social Network Analysis and Mining. 2013. Vol. 3. No. 4. P. 1209-1224.

[18] Dong G., Gao J., Du R., Tian L., Stanley H.E., Havlin S. Robustness of network of networks under targeted attack // Physical Review E. 2013. Vol. 87. No. 5. P. 052804-1-052804-11. DOI: 10.1103/PhysRevE.87.052804

[19] Richard M.G.A., Fanchon E. Reduction and fixed points of Boolean networks and linear network coding solvability // IEEE Transactions on Information Theory. 2016. Vol. 62. No. 5. P. 2504-2519.

[20] Назаров М.Н. О представлении графов в виде группоидов специального вида // Прикладная дискретная математика. 2015. № 1. C. 96-104.