Введение
Глава 1 Анализ разветвленности сети 37
1.1. Эффективный метод анализа разветвленное сети 3 7
1.1.1. Общее 37
1.1.2. Постановка задач и метод их решения 39
1.1.3. Методика проверки существования трёх независимых путей между любой парой узлов сети без использования компьютера 43
1.1.4. Пример 45
1.2. Задача об улучшении разветвленности сети. 48
Глава 2 Максимизация использования сети 49
2.1. Оптимальное использование сети для многопродуктового одноприоритетного потока
2.1.1. Постановка задачи и алгоритм решения 49
2.1.2. Эффективный алгоритм генерации столбцов в задаче оптимального использования сети 57
2.2. Алгоритмы нахождения кратчайших путей в оптимизационных задачах на сетях связи 63
2.2.1. Поля кратчайших путей 64
2.2.2. Модифицированный алгоритм Дейкстры для неориентированной сети 70
2.2.3. Модифицированный алгоритм Дейкстры для поля 72
2.2.4. Результаты вычислительного эксперимента 74
2.3. Задача эффективной эксплуатации сети связи 75
2.3.1. Постановка задачи 75
2. Алгоритм решения задачи 78
3. Пример решения задачи 82
Глава 3 Оптимизационные задачи развития сети 85
Задача развития сети с минимизацией капиталовложений при обеспечении заданных объемов потоков каждого продукта 85
1. Линейная частично-целочисленная задача с большим количеством непрерывных переменных 85
Задача развития сети при ограниченных капиталовложениях 89
1. Математическая постановка задачи 89
2. Алгоритм решения задачи развития сети при ограниченных капиталовложениях 91
3. Пример решения задачи развития сети при ограниченных капиталовложениях 94 Задача развития сети с целью максимизации прибыли в условиях получения кредита. Оптимизация объема кредита. 101
1. Математическая постановка задачи 101
2. Алгоритм решения задачи развития сети с выбором оптимального кредита 103
3. Пример решения задачи развития сети с выбором оптимального кредита 104
Глава 4 Многомерная задача о ранце специальной лестничной структуры с коэффициентами равными 0 или 1 в матрице ограничений 107
Постановка и алгоритм решения задачи 108
Пример решения задачи 116
Абсолютно унимодулярные матрицы, состоящие из 0 и 1 119
4.3.1. Абсолютная унимодулярность матриц ограничений многомерной задачи о ранце специальной лестничной структуры 119
4.3.2. Абсолютная унимодулярность выпуклых матриц 119
Заключение 129
Список литературы 130
