Введение
Глава 1. Задачи оптимального линейного упорядочения 32
1.1 Полиномиальные алгоритмы для специальных ориентированных графов 32
1.2 Гибридный алгоритм для произвольного ориентированного графа 49
1.3 Полиномиальный алгоритм для двухполюсного неориентированного графа 58
Глава 2. Размещение на линии с минимально допустимыми расстояниями 71
2.1 Постановки задач и их свойства 71
2.2 Фиксированный порядок расположения объектов . 79
2.3 Модели целочисленного линейного программирования 87
2.4 Анализ L-структуры многогранных множеств . 102
2.5 Алгоритмы решения 113
Глава 3. Размещение на сетях 127
3.1 Решение минимаксной задачи Вебера на дереве . 128
3.2 Решение задачи Вебера на дереве с критерием минимума суммарной стоимости связей 135
3.3 Алгоритмы решения задач Вебера на общих сетях . 142
3.4 Полиномиальные алгоритмы для задач с взаимно однозначным размещением 157
3.5 Динамическое программирование для квадратичной задачи о назначении на дереве 170
3.6 Свойства многогранника задачи о р-медиане . 174
Глава 4. Размещение на плоскости и дискретных множествах 180
4.1 Модели целочисленного программирования для задач на плоскости с запрещенными зонами 181
4.2 Размещение объекта с учетом запрещенных зон и прямоугольной метрикой 188
4.3 Размещение объекта с учетом запрещенной зоны и евклидовой метрикой 197
4.4 Построение оценок суммарной стоимости связей . 202
Глава 5. Решение прикладных задач 218
5.1 Построение моделей 218
5.2 Модель оптимального размещения модулей швейного производства . 227
5.3 Анализ оптимальности расположения нефтеперерабатывающего оборудования 234
Заключение 240
Список использованной литературы 242
Приложение 1 260
