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

1 / 16

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1 43
УДК 519.9 DOI: 10.18698/1812-3368-2017-1-43-58
АЛГОРИТМ ПОСТРОЕНИЯ НАСЛЕДСТВЕННО МИНИМАКСНОЙ СЕТИ
С ЗАДАННЫМ ВЕКТОРОМ СТЕПЕНЕЙ УЗЛОВ
П.С. Селин1
В.И. Цурков2
А.А. Гурченков2, 3
1 Университет Акита, Акита, Япония
2 Вычислительный центр им. А.А. Дородницына ФИЦ «Информатика и управление»
РАН, Москва, Российская Федерация
3 МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
Аннотация Ключевые слова
В отличие от классической транспортной задачи, где
известны пункты производства и потребления, и требует-
ся минимизировать стоимость перевозки, в настоящей
работе рассмотрен минимаксный критерий. В частности,
ищется матрица с минимальным наибольшим элементом
в классе неотрицательных матриц с заданными суммами
элементов строк и столбцов. В таком случае минимакс-
ный критерий можно интерпретировать следующим
образом. Допустим, что время перевозки из пункта про-
изводства в пункт потребления пропорционально объему
перевозки. Тогда минимакc — минимальное время, необ-
ходимое для перевозки всего объема. Это обычная ситуа-
ция, когда принимающий решения не знает тарифных
коэффициентов. В других ситуациях они не имеют смыс-
ла, как и нелинейные тарифные целевые функции. В этих
случаях минимаксная интерпретация приводит к эффек-
тивному решению. Для классов неоринтированных сетей
с заданным вектором степеней узлов (транспортных и
сетевых многогранников) с применением характеристи-
ческих функций получены аналитические формулы для
вычисления минимаксных значений, выраженных через
координаты вектора и неотрицательный параметр. Ми-
нимаксные значения определяют необходимые и доста-
точные условия, при которых усеченные многогранники
не пустые множества. Получен алгоритм построения
наследственно минимаксной сети в сетевых многогран-
никах
Оптимизация сетей, задачи тран-
спортного типа, минимакс, ми-
нимаксная сеть, наследственно
минимаксная сеть, равномерная
сеть, транспортные многогран-
ники, сетевые многогранники, за-
данные степени узлов, фиксиро-
ванные степени узлов
Поступила в редакцию 13.07.2016
©МГТУ им. Н.Э. Баумана, 2017
Работа выполнена при финансовой поддержке Российского фонда
фундаментальных исследований № 15-01-05552
Введение. В настоящей работе рассмотрены классы сетей (взвешенных графов),
веса дуг которых ограничены неотрицательным параметром с заданным векто-
ром степеней узлов и двудольных сетей, степени узлов которых задаются парой
векторов. В транспортных задачах эти классы называются усеченными сетевы-