Комбинированный метод решения линейных задач целочисленного программирования и его применение для оптимизации топологии локальных вычислительных сетей

Содержание
Список сокращений
Введение.
1. Задача определения оптимальной топологии ЛВС и подходы к
се решению
1.1. Постановка задачи
1.1.1. ЛВС с применением концентраторов разных типов и непосредственным подключением пользователей к центральному концентратору.
1.1.2. ЛВС с однотипными концентраторами и опосредованным подключением пользователей к центральному концентратору.
1.2. Методы решения задач целочисленного программирования
и подходы к решению поставленной задачи
1.2.1. Существующие методы решения линейных задач целочисленного программирования
1.2.2. Предпосылки создания нового метода для решения линейных целочисленных задач.
1.2.3. Выводы.
2. Разработка комбинированного метода для решения задачи
определения оптимальной топологии ЛВС.
2.1. Необходимость комбинированного метода
2.2. Теоретическое обоснование комбинированного метода решения математической модели линейного целочисленного программирования
2.2.1. Формализованная запись исходной задачи.
2.2.2. Метод неявного перебора по векторной решетке и возможности его применения в комбинированном методе
2.2.3. Преобразования исходной задачи для применения комбинированного метода.
2.2.4. Совместное использование линейного программирования и неявного перебора но векторной решетке для нахождения допустимого субоптимального решения.
2.2.5. Совместное использование линейного программирования и метода неявного перебора по векторной решетке для окончательного поиска оптимального решения
2.3. Алгоритм комбинированного метода.
2.3.1. Комментарии к выполнению п. 3.1 алгоритма
2.3.2. Комментарии к выполнению п. 3.2.1 алгоритма
2.4. Использование эвристических алгоритмов для улучшения свойств комбинированного метода
2.5. Свойства комбинированного метода
3. Сравнительный анализ
3.1. Прог раммная реализация комбинированного метода.
3.1.1. Язык программирования.
3.1.2. Используемый компилятор.
3.1.3. Схема межмодульных связей.
3.1.4. Укрупненная схема алгоритма программы.
3.1.5. Подключение модулей, реализующих эвристические алгоритмы
3.2. Решение комбинированным методом задач малой размерности.
3.3. Реализация метода ветвей и границ.
3.3.1. Особенности реализации метода ветвей и границ с использованием специальных азгоритмов решения ЗЛГ1 с двухсторонними ограничениями на оптимизационные переменные.
3.3.2. Программная реализация метода ветвей и границ
3.4. Реализация метода правильных отсечений.
3.4.1. Особенности алгоритмической реализации метода
правильных отсечений.
3.4.2. Описание процедуры расширения симплекстаблицы при введении нового правильного отсечения ПО 1Й производящей строке.
3.4.3. Описание процедуры сжатия
3.4.4. Оценка накапливаемой при осуществлении ПГЖ погрешности и использование ес для определения идентификации целочисленных базисных компонент
3.4.5. Программная реализация метода правильных отсечений.
3.5. Сравнение альтернативных методов поиска оптимального решения математической модели линейного программирования
3.5.1. Критерии сравнения.
3.5.2. Генератор линейных задач целочисленного программирования
3.5.3. Результаты сравнения.
4. Решение задачи определения оптимальной топологии ЛВС
комбинированным методом.
4.1. ЛВС с применением концентраторов разных типов и непосредственным подключением пользователей к центральному концентратору
4.1.1. Преобразования задачи с целыо уменьшения ее размерности и эффективного применения комбинированного метода.
4.1.2. Эвристический алгоритм формирования допустимого решения задачи
4.1.3. Результаты решения задачи
4.2. ЛВС с однотипными концентраторами и опосредованным
подключением пользователей к центральному концентратору.
4.2.1. Преобразование задачи для применения комбинированного метода.
4.2.2. Результаты решения задачи
Заключение
Литература