Минимакс в транспортных моделях

• Автор: Миронов, Анатолий Анатольевич
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 241 с.

7/-' з$-
РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР
На правах рукописи
МИРОНОВ АНАТОЛИЙ АНАТОЛЬЕВИЧ МИНИМАКС В ТРАНСПОРТНЫХ МОДЕЛЯХ
Специальность:
05ЛЗЛ8 — Теоретические основы математического моделирования, численные методы, комплексы программ
Диссертация на соискание ученой степени доктора физико-математических наук
Москва-1998 г.
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Глава 1. МОДЕЛИ ТРАНСПОРТНОГО ТИПА
С МИНИМАКСНЫМ КРИТЕРИЕМ
§ 1. Транспортные модели
1.1. Равномерные матрицы и матричные множества
1.2. Примеры транспортных моделей с критериями
минимаксных типов
1.3. Усеченные транспортные многогранники
§ 2. Транспортные матрицы с ограничением для элементов
2.1. Разбиения пар векторов
2.2. Условия существования матриц с заданным ограничением
2.3. Критерий существования транспортной матрицы в форме несократимой системы неравенств
2.4. Алгоритмы построения транспортных матриц
§ 3. Характеристические уравнения для усеченных транспортных
многогранников
3.1. Общие свойства транспортных матриц
3.2. Примеры применений характеристических уравнений
Глава 2. критерии минимаксного типа
§ 1. Условия единственности решения задачи минимизации
наибольшего элемента транспортной матрицы
1.1. Минимаксные значения и минимаксные матрицы
1.2. Условия единственности минимаксной матрицы
транспортного многогранника
1.3. Алгоритм вычисления минимаксного значения
§ 2. Наследственные свойства транспортных матриц
2.1. Наследственно минимаксные матрицы

2.2. Единственность наследственно минимаксной матрицы
транспортного многогранника
2.3. Минимизация равномерными минимаксными матрицами
2.4. Свойства равномерных матриц
2.5. Минимизация равномерными матрицами
§ 3. Наследственно минимаксные матрицы в транспортных задачах
с критериями минимаксных типов
3.1. Наибольшие элементы подматриц транспортной матрицы
и равномерность
3.2. Минимизация наследственно минимаксными матрицами
Глава 3. ЦЕЛОЧИСЛЕННЫЕ ТРАНСПОРТНЫЕ МАТРИЦЫ
§ 1. Целочисленные матрицы с общим ограничением
для элементов
1.1. Вспомогательные построения
1.2. Редукционный критерий существования транспортных матриц
1.3. Редукционные алгоритмы построения транспортных
матриц
§ 2. Матрицы, состоящие из нулей и единиц
2.1. Критерий существования и характеристические уравнения
2.2. Редукционные алгоритмы
Глава 4. ЭКСТРЕМАЛЬНЫЕ МАТРИЦЫ И ФУНДАМЕНТАЛЬНЫЕ
ТРАНСПОРТНЫЕ МНОГОГРАННИКИ
§ 1. Экстремальные пары векторов и экстремальные матрицы
1.1. Экстремальные пары векторов
1.2. Экстремальные матрицы
1.3. Множества экстремальных матриц (и пар векторов)
одного порядка
1.4. Совершенные пары векторов и совершенные матрицы
§ 2. Алгебраические свойства экстремальных пар векторов
и экстремальных матриц
2.1. Операции над парами векторов и матрицами
2.2. Изоморфные дистрибутивные решетки фундаментальных систем пар векторов и матриц
§ 3. Метрические свойства экстремальных пар векторов
и экстремальных матриц

Приведем условия, являющиеся следствием теоремы Гейла, при которых М(А, В; (с )) 0 [11, 19, 83]: если векторы А=(ар
1 < i < п, 1 < } < т, состоит из неотрицательных элементов, то усечен-
ный транспортный многогранник М(А, В; (с..)) 0 тогда и только тогда, когда

min (Ь. 2 с..) > X а- (1.2°)
у— I ге/ г'е
для любого подмножества индексов I С {1,
В частности, если в (1.20) положить с.. = с, 1 < i < п, 1 < j < m, то
получим необходимые и достаточные условия для М(А, В; с) 0. В этом случае количество проверяемых неравенств уменьшится, причем, для координат первого вектора А удобно предположить их упорядоченность по невозрастанию. Так как
2 сг= с,л

при с = с, 1 < i < п, < j < т, где 1/1 — количество индексов множества /, то справедливо утверждение: если векторы А £ А" и В £ R™
удовлетворяют условию замкнутости (1.1) и с > 0, то транспортный многогранник М(А, В; с) 0 тогда и только тогда, когда

min (А, с&) > 2. (1.21)
7=1 г
для любого к £ Z, 1 < к < п, где А = (2,
Для векторов А = (а{,
кнутости не предполагается) и значений с, к, где с > 0 и к Е Z, 1 < к < л, рассмотрим функцию [53—55, 57]

б/А, В; с) = 2 bj - 2 iPj - ск) - Д- (1.22)
/—1