Введение
1 Задачи размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций 25
1.1 Задача размещения на сети с ограниченными пропускными способностями коммуникаций 25
1.1.1 Постановка задачи 25
1.1.2 Задача размещения на древовидной сети 28
1.1.3 Задача размещения на два-дереве 33
1.2 Задача размещения на сети с ограниченными мощностями и пропускными способностями коммуникаций . 38
1.2.1 Постановка задачи 38
1.2.2 Сравнение релаксаций 41
1.2.3 Вычисление релаксаций 46
1.2.4 Реализация метода ветвей и границ 47
2 Приближенные алгоритмы для репіения задач размещения с ограниченными объемами производства и поставок и обоснование условий их асимптотической точности 51
2.1 Постановки задач 51
2.2 Вспомогательные понятия и утверждения 54
2.3 Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и условия его асимптотической точности 57
2.4 Приближенный алгоритм для решения задачи размещения с ограниченными объемами производства и единичными объемами поставок и условия его аснптотпческоп точности 66
2.5 Замечания 76
3 Приближенный алгоритм для задачи размещения на максимум с ограниченными объемами производства и поставок 80
3.1 Постановка задачи 80
3.2 Субмодулярные функции и жадный алгоритм 82
3.3 Эквивалентная задача 84
3.4 Оценки качества алгоритма 86
Заключение 91
Список публикаций автора по теме диссертации 93
Благодарности 95
Список литературы 96
