12 / 16
П.С. Селин, В.И. Цурков, А.А. Гурченков
54
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
Алгоритм 2.
Построение наследственно минимаксной сети без петель.
Пусть
A
— произвольный вектор из множества
.
n
Наследственно мини-
максная сеть строится следующим образом.
Шаг 1.
Применяют теорему 10 для вычисления минимакса
>
( , ) ( )
( ) =
= .
max ( 1)
i
i
i t
i r
kq
t r T
a a
c
c
t r
A
A
Числа
,
kq
c
,
k
q
задают веса дуг искомой сети (элементы симметричной матри-
цы)
( ),
X
A
равные
( )
c
A
и равные 0 (теорема 9).
Шаг 2.
Применяя лемму 6, вычисляют пару векторов
( ,
)
A A
и вектор
.
A
Для пары векторов
( ,
)
A A
применяют алгоритм 1, чтобы построить наслед-
ственно минимаксную двудольную сеть, в результате будут найдены веса дуг
ij
x
искомой сети
( ),
X
A
где
1
,
i k
< .
q j n
Далее для вектора
A
применяют шаги 1 и 2 алгоритма 2 и т. д.
Очевидно, что построенная с помощью алгоритма 2 матрица
( )
X
A
— рав-
номерная. Следующим шагом может быть распространение результатов иссле-
дования на целочисленные сети, а также многоиндексные, нелинейные и беско-
нечномерные обобщения [3, 4], а также широкий класс теоретических и при-
кладных задач [13–20].
Заключение.
Классические транспортные задачи и методы их решения ши-
роко известны. Рассмотрены транспортные модели с минимаксным критерием.
Во многих случаях тарифные коэффициенты неизвестны принимающему реше-
ния, а иногда и не имеют смысла. В этих случаях минимаксная модель приводит
к эффективному решению. В частности, часто ищется матрица с минимальным
наибольшим элементом в классе неотрицательных матриц с заданными сумма-
ми элементов строк и столбцов. Минимаксный критерий показывает, что время
перевозки продукции минимально при условии, что время перевозки пропор-
ционально объему продукции. Для классов сетей с заданным вектором степеней
узлов с использованием характеристических функций были получены формулы
для вычисления минимаксных значений, определяющих необходимые и доста-
точные условия, при которых усеченные сетевые и транспортные многогранни-
ки не пустые множества. Для рассматриваемых классов сетей также получен
алгоритм построения наследственно минимаксной сети. Основное отличие от
результатов, полученных ранее, заключается в том, что расчет минимакса мож-
но упростить, исключив неравенства из систем линейных соотношений.
ЛИТЕРАТУРА
1.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.
Алгоритмы: построение и анализ / под
ред. И.В. Красикова. М.: Вильямс, 2005. 1296 с.
2.
Зыков А.А.
Основы теории графов. М.: Вузовская книга, 2004. 664 с.