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

14 / 16

П.С. Селин, В.И. Цурков, А.А. Гурченков
56 ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
Цурков Владимир Иванович — д-р физ.-мат. наук, заведующий отделом Вычисли-
тельного центра им. А.А. Дородницына ФИЦ «Информатика и управление» РАН
(Российская Федерация, Москва, 119333, ул. Вавилова, д. 40).
Гурченков Анатолий Андреевич — д-р физ.-мат. наук, ведущий научный сотрудник
Вычислительного центра им. А.А. Дородницына ФИЦ «Информатика и управление»
РАН (Российская Федерация, Москва, 119333, ул. Вавилова, д. 40), профессор кафедры
«Высшая математика» МГТУ им. Н.Э. Баумана (Российская Федерация, Москва, 105005,
2-я Бауманская ул., д. 5).
Просьба ссылаться на эту статью следующим образом:
Селин П.С., Цурков В.И., Гурченков А.А. Алгоритм построения наследственно мини-
максной сети с заданным вектором степеней узлов // Вестник МГТУ им. Н.Э. Баумана.
Сер. Естественные науки. 2017. № 1. C. 43–58. DOI: 10.18698/1812-3368-2017-1-43-58
AN ALGORITHM FOR CONSTRUCTING A HEREDITARILY MINIMAX
NETWORK WITH PREDEFINED VECTOR OF NODE DEGREES
P.S. Selin1
V.I. Tsurkov 2
A.A. Gurchenkov 2, 3
1 Akita University, Akita, Japan
2 Dorodnitsyn Computing Centre Federal Research Centre Cumputer Science and Centrol,
Russian Academy of Sciences, Moscow, Russian Federation
3 Bauman Moscow State Technical University, Moscow, Russian Federation
Abstract Keywords
In contrast to the classical transportation problem, where
supply and demand points are known, and it is required to
minimize the transportation cost, we consider a minimax
criterion. In particular, a matrix with the minimal largest
element is sought in the class of nonnegative matrices with
given sums of row and column elements. In this case, the
concept of the minimax criterion can be interpreted as
follows. Suppose that the shipment time from a supply
point to a demand point is proportional to the amount to
be shipped. Then, the minimax is the minimal time
required to transport the total amount. It is a common
situation that the decision maker does not know the tariff
coefficients. In other situations, they do not have any
meaning, and neither do nonlinear tariff objective
functions. In such cases, the minimax interpretation leads
to an effective solution. For the classes of undirected
networks with predefined vector of node degrees (transport
and network polyhedrons) by using a characteristic
functions the analytical formulas of calculating the
minimax values expressed in terms of the vector
coordinates and a nonnegative parameter are obtained.
Network optimization, transport
type problems, minimax, minimax
network, hereditarily minimax net-
work, uniform network, transpor-
tation polyhedrons, network poly-
hedrons, predefined node degrees,
fixed node degrees