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

• Автор: Демин, Александр Юрьевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 154 с. : ил

Содержание

Список сокращений

Введение.

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. Результаты решения задачи
Заключение
Литература


Преобразования задачи с целыо уменьшения ее размерности и эффективного применения комбинированного метода. Преобразование задачи для применения комбинированного метода. Современные системы поддержки принятия решения и автоматизированные системы управление построены на последних достижениях прикладных наук. Одной из таких наук является математическое программирование 1,,,,. С помощью математического программирования решаются разнообразные задачи, так или иначе являющиеся составными частями автоматизированных систем управления АСУ, систем автоматизированного проектирования САПР и систем поддержки принятия решения С1II1Р. Важным подклассом задач математического программирования являются линейные задачи целочисленного программирования ,,,,,,,,,. С помощью них формализуются многие реальные задачи оптимального планирования 6,7,8,,,,,,,, , и, в частности, такие типовые постановки задач этого класса, как основная производственная задача с дискретным характером производимой продукции, задача о ранце, задача о загрузке транспорта и многие другие. Необходимо отметить, что многие задачи нелинейного программирования могут быть сведены к линейным задачам. В настоящее время существует ряд оптимизационных методов, позволяющих решать задачи этого класса, такие как методы неявного перебора, метод правильных отсечений, метод ветвей и границ. Целью работы является разработка комбинированного метода для решения линейных задач целочисленного программирования обоснование, разработка алгоритмической и программной реализаций, исследование ею свойств, и решение с помощью него задачи по нахождению оптимальной топологии ЛВС. ЛВС. В работе применяются методы системного анализа, в том числе математического программирования, машинного эксперимента и объектноориентированного проектирования программ. ЛВС с использованием разработанного метода. РКК Энергия. С помощью разработанного программного обеспечения была решена задача по определению оптимальной топологии ЛВС этого предприятия. Кроме того, осуществлено внедрение разработанного программного обеспечения в учебный процесс МАИ в составе лабораторного комплекса по изучению методов решения задач линейного целочисленного программирования. Разработанное программное обеспечение зарегистрировано в Реестре программ для ЭВМ . Идеи и концепции, предложенные в диссертационной работе, докладывались и обсуждались на различных конференциях, в том числе международных, в частности, на 5, 6, 7, 8 и международных научнотехнических семинарах Современные технологии в задачах управления автоматики и обработки информации Россия, Алушта, , , , , , на восьмой международной научнотехнической конференции студентов и аспирантов Радиоэлектроника, электротехника и энергетика Москва, МЭИ, . Разработка комбинированного метода осуществлена в рамках плановой НИР ПН 5 2 кафедры 2 МАИ, выполненной на основе конкурса грантов Министерства образования в г. Результа ты работы отражены в публикациях. Диссертация состоит из 3 страниц машинописного текста, в том числе введения, 4 глав, заключения. Объем основной части диссертации составляет 0 страниц. Во введении обоснована актуальность темы диссертации, сформулирована цель, задачи и основные положения, выносимые па защиту, научная новизна и практическая значимость диссертационной работы. В первой главе производится постановка задачи, решению которой посвящена эта диссертация, а именно формулированию задачи по определению оптимальной топологии ЛВС, содержательная постановка которой взята с предприятия РКК Энергия, перед инженерами которой возникли потребности в решении некоторых оптимизационных задач, а именно нахождение оптимальной структуры для локальной вычислительной сети, ее формализации и анализу текущего состояния достижений математического программирования в направлении линейных целочисленных оптимизационных задач. Во второй главе диссертации производится обоснование комбинированного метода для решения задач линейного целочисленного программирования. В этой главе приведена математическая база комбинированного метода.