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

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

Введение.

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. Особенности реализации метода ветвей и границ с использованием специальных алгоритмов решения ЗЛП с двухсторонними ограничениями на оптимизационные переменные.

3.3.2. Программная реализация метода ветвей и границ.

3.4. Реализация метода правильных отсечений.

3.4.1. Особенности алгоритмической реализации метода правильных отсечений.

3.4.2. Описание процедуры расширения симплекс-таблицы при введении нового правильного отсечения по i -й производящей строке.

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,30,32,33,44]. С помощью математического программирования решаются разнообразные задачи, так или иначе являющиеся составными частями автоматизированных систем управления (АСУ), систем автоматизированного проектирования (САПР) и систем поддержки принятия решения (СППР).Важным подклассом задач математического программирования являются линейные задачи целочисленного программирования [12,14,15,28,34,36,46,53,61,62]. С помощью них формализуются многие реальные задачи оптимального планирования [6,7,8,13,19,24,29,31,35,52, 58,59] и, в частности, такие типовые постановки задач этого класса, как: основная производственная задача с дискретным характером производимой продукции, задача о ранце, задача о загрузке транспорта и многие другие.Необходимо отметить, что многие задачи нелинейного программирования могут быть сведены к линейным задачам.В настоящее время существует ряд оптимизационных методов, позволяющих решать задачи этого класса, такие как: методы неявного перебора, метод правильных отсечений, метод ветвей и границ. Каждый из этих методов имеет свои серьезные недостатки, ограничивающие их применение к решению высокоразмерных оптимизационных задач, что делает актуальной разработку более эффективного метода и соответствующего алгоритма решения линейных целочисленных оптимизационных задач: более надежного и обладающего меньшей вычислительной сложностью [11,39,40,45,50,55].Цель работы Целью работы является разработка комбинированного метода для решения линейных задач целочисленного программирования: обоснование, разработка алгоритмической и программной реализаций, исследование его свойств, и решение с помощью него задачи по нахождению оптимальной топологии ЛВС. Задачи исследования: • решить с помощью разработанного комбинированного метода задачу по нахождению оптимальной топологии ЛВС. • обосновать идеи и концепцию разработанного комбинированного метода решения линейных задач целочисленного программирования; • разработать алгоритмическую реализацию комбинированного метода и эффективную программную реализацию комбинированного метода; • исследовать свойства комбинированного метода и сравнить его с существующими методами, которые решают задачи этого же класса.Методика исследования В работе применяются методы системного анализа, в том числе математического программирования, машинного эксперимента и объектноориентированного проектирования программ.Результаты, выносимые на защиту: • результаты решения задачи по нахождению оптимальной топологии ЛВС при помощи комбинированного метода; • комбинированный метод для решения задач линейного целочисленного программирования; • результаты исследования свойств комбинированного метода и его результаты сравнения с существующими методами.Научная новизна • впервые предложена концепция комбинированного метода решения линейных задач целочисленного программирования, объединяющая методы линейного программирования, неявного перебора по векторной решетке и эвристические подходы для эффективного решения задач большой размерности.Использование эвристических подходов в комбинированном методе не влияет на возможность нахождения строго оптимального решения, а лишь обеспечивает более быстрый его поиск; • проведено всестороннее сравнение разработанного метода с различными известными универсальными методами решения линейных задач целочисленного программирования (в том числе и с использованием машинного эксперимента), показавшее его преимупцества; • поставлены и решены задачи оптимизации топологии ЛВС с использованием разработанного метода.Практическая значимость В результате выполнения диссертационной работы автором получены следующие результаты: • с использованием объектно-ориентированного подхода осуществлена программная реализация комбинированного метода, позволяющая подстраивать алгоритм метода под конкретную задачу с помощью использования разнообразных эвристик, и с помощью этой программной реализации получено решение задачи определения оптимальной топологии локальной вычислительной сети; • разработана эффективная библиотека современных оптимизационных методов для решения линейных задач целочисленного программирования; • результаты, полученные в работе, внедрены на предприятии РКК «Энергия». С помощью разработанного программного обеспечения была решена задача по определению оптимальной топологии ЛВС этого предприятия. Кроме того, осуществлено внедрение разработанного программного обеспечения в учебный процесс МАИ в составе лабораторного комплекса по изучению методов решения задач линейного целочисленного программирования.Разработанное программное обеспечение зарегистрировано в Реестре программ для ЭВМ [21\ Апробация работы Идеи и концепции, предложенные в диссертационной работе, докладывались и обсуждались на различных конференциях, в том числе международных, в частности, на 5, 6, 7, 8 и 11 международных научнотехнических семинарах «Современные технологии в задачах управления автоматики и обработки информации» (Россия, Алушта, 1996, 1997, 1998, 1999, 2002), на восьмой международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, МЭИ, 2002).Разработка комбинированного метода осуществлена в рамках плановой НИР ПН 235 (302-98-05) кафедры 302 МАИ, выполненной на основе конкурса грантов Министерства образования в 1998-1999 г.Результаты работы отражены в 11 публикациях.Структура объем диссертации Диссертация состоит из 153 страниц машинописного текста, в том числе введения, 4 глав, заключения. Объем основной части диссертации составляет О страниц.Основное содержание работы Во введении обоснована актуальность темы диссертации, сформулирована цель, задачи и основные положения, выносимые на защиту, научная новизна и практическая значимость диссертационной работы.В первой главе производится постановка задачи, решению которой посвящена эта диссертация, а именно формулированию задачи по определению оптимальной топологии ЛВС, содержательная постановка которой взята с предприятия РКК «Энергия», перед инженерами которой возникли потребности в решении некоторых оптимизационных задач, а именно: нахождение оптимальной структуры для локальной вычислительной сети, ее формализации и анализу текущего состояния достижений математического программирования в направлении линейных целочисленных оптимизационных задач.Во второй главе диссертации производится обоснование комбинированного метода для решения задач линейного целочисленного программирования. В этой главе приведена математическая база комбинированного метода. Кроме того, вторая глава содержит описание алгоритма комбинированного метода с детализацией различных вариантов его функционирования. Особенности всех прочих оптимизационных методов, используемых в комбинированном методе, и их модификации также приведены во второй главе.Третья глава посвящена анализу свойств комбинированного метода.Для этого производится разбор ряда тестовых задач, которые были решены классическими методам или вручную (несложные задачи малой размерности). Кроме этого, в третьей главе комбинированный метод сравнивается по своим свойствам с существующими методами, решающими задачи этого же класса. Для этого в рамках диссертационной работы были осуществлены их программные реализации. Некоторые классические методы [4,17,23,27,43] получили усовершенствование, благодаря которым улучшились их показатели эффективности. Идеи и суть осуществленных усовершенствований классических методов также приведены в третьей главе.Описание программной реализации комбинированного метода вошло в состав третьей главы, как неотъемлемая составляющая положительных качеств этого метода. Являясь сложным алгоритмически, комбинированный метод потребовал создания ряда вспомогательных утилит для своего тестирования, отладки и исследования, например, таких как генератор линейных задач целочисленного программирования, описание программной реализации которого также вошло в третью главу.Четвертая глава диссертации решению задачи определения оптимальной топологии ЛВС с комбинированного метода. Был сформулирован эвристический алгоритм поиска допустимого решения.Полученная задача была решена с помощью комбинированного метода с применением разработанного эвристического алгоритма и без него.

6. Результаты работы внедрены на предприятии РКК «Энергия» при решении указанных в п. 4 задач, а также в учебный процесс кафедры «Автоматизированные системы обработки информации и управление» факультета №3 МАИ.

На основе полученных результатов можно сделать вывод об эффективности комбинированного метода, по сравнению с существующими методами, при решении задач, возникающих в современных системах

147 поддержки принятия решений, и о его применимости в создании разнообразных систем управления.

Заключение

1. Разработан, алгоритмически и программно реализован комбинированный метод решения задач целочисленного программирования, эффективно объединяющий возможности линейного программирования, неявного перебора по векторной решетке, а в определенных условиях и эвристические подходы для нахождения оптимального решения.

2. Осуществлены формализованная постановка задач определения оптимальной структуры ЛВС в виде линейных задач целочисленного программирования и их решение с использованием разработанного комбинированного метода.

3. Проведено сравнение комбинированного метода с рядом существующих универсальных методов решения задач рассматриваемого класса и получены следующие результаты:

• комбинированный метод обладает преимуществами по сравнению с существующими методами, в частности, отсутствует влияние погрешности вычислений на надежность и точность оптимизации, в отличие от метода ветвей и границ, метода правильных отсечений отсутствует неопределенность, связанная с размерностью используемых структур данных и этапностью решения задачи;

• существует возможность включения в работу метода эффективных эвристик, которые могут позволить существенно снизить вычислительную сложность поиска оптимального решения;

• комбинированный метод превосходит существующие методы по затратам машинного времени на поиск оптимального решения, которые возрастают при увеличении размерности решаемой задачи.

4. Произведено обобщение существующего метода неявного перебора по векторной решетке, ориентированного на решение комбинаторных задач, для линейных задач целочисленного программирования общего вида. Это позволило эффективно использовать его в составе комбинированного метода, а также использовать его как самостоятельный метод поиска оптимального решения рассматриваемого класса задач.

5. Получено свидетельство о регистрации Роспатента на разработанное программное обеспечение [21].

1. Абрамов Л.М., Капустин В.Ф. Математическое программирование. Ленинград, ЛГУ, 1976 г., (183 стр.).

2. Аоки М. Введение в методы оптимизации. М.: Наука, 1979 г.

3. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982 г. (583 стр.).

4. Батищев Д.И. Поисковые методы оптимального проектирования. М.: Советское радио, 1975 г.

5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. -М.: Наука, 1965 г. (458 стр.).

6. Бункин В.А. Справочник по оптимизационным задачам в АСУ. М.: Машиностроение, 1984 г.

7. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. М.: «Изд-во Бином», 1998 г. (560 стр.)

8. Ю.Вагнер Г. Основы исследования операций. Том 2. М. Мир, 1973 г. (484 стр.).

9. Волконский В.А. Оптимальное планирование в условиях большой размерности (итеративные методы и принцип декомпозиции). М.: ЭММ т. 1 вып. 2, 1965 г.

10. Гасс С. Линейное программирование. -М.: Физматгиз, 1961 г. (304 стр.).

11. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969 г. (384 стр.).

12. Голыптейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Советское радио, 1966 г. (524 стр.).

13. Данциг Дж. Линейное программирование, его применения и обобщения. -М.: Прогресс, 1966 г. (600 стр.).

14. Дегтярев Ю.И. Исследование операций: Учебник для вузов по специальности АСУ. М.: Высшая школа, 1986 г. (320 стр.).

15. Дегтярев Ю.И. Методы оптимизации: Учебное пособие для вузов. М.: Советское радио, 1980 г. (272 стр.).

16. Дегтярев Ю.И. Системный анализ и исследование операций: Учебное пособие для вузов по специальности АСОИУ. М.: Высшая школа, 1996 г. (335 стр.).

17. Деннис Дж. Математическое программирование и электрические цепи. -М.: ИЛ, 1961 г.

18. Дёмин А.Ю. Генератор линейных задач целочисленного программирования. Труды международного НТС "Современные технологии в задачах управления автоматики и обработки информации". Алушта, М.: МАИ, 1998 г. (стр. 189—191).

19. Дёмин А.Ю. Свидетельство об официальной регистрации программы для ЭВМ «Программный комплекс для решения линейных задач целочисленного программирования комбинированным методом» №2002610824 от 27.05.2002 г. Роспатент, Москва, 2002 г.

20. Дёмин А.Ю., Хахулин Г.Ф. Комбинированный метод решения линейных задач целочисленного программирования. Труды международного НТС «Современные технологии в задачах управления и обработки информации». Алушта, М.: МАИ, 1997 г. (стр. 139—140).

21. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982 г.

22. Евтушенко Ю.Г., Мазурик В.П. Программное обеспечение систем оптимизации. М.: Знание, 1989 г. (48 стр.).

23. Канторович Л.В. Математическое программирование. М.: Наука, 1966 г. (135 стр.).

24. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование в экономике. М.: 1972 г. (232 стр.).

25. Карманов В.Г. Математическое программирование. М.: Наука, 1986 г.

26. Карманов В.Г. Математическое программирование. М.: Физматгиз, 1975 г. (272 стр.).

27. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969 г. (368 стр.).

28. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975 г.

29. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование. М.: МИР, 1977 г. (432 стр.).

30. Кун X., Таккер А., Линейные неравенства и смежные вопросы. М.: ИЛ, 1959 г. (472 стр.).

31. ЛедлиР. Программирование и использование вычислительных машин. -М.: Мир, 1966 г. (644 стр.).

32. Литл Дж., Мурта К., Суини Д., Керел К. Алгоритм для решения задачи о коммивояжере. Экономика и математические методы, т. 1, №1, 1965 г. (стр. 94—107).

33. Лэдсон Л. Оптимизация больших систем. М.: Наука, 1975 г. (432 стр.).

34. Ляшенко И.Н., Карагородова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. К.: Вигца школа, 1972 г. (372 стр.).

35. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. М.: Бином Универсал, К.: Юниор, 1997 г. (496 стр.).

36. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. -М.: Наука, 1978 г. (352 стр.).

37. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. -Новосибирск: Наука, 1977 г. (320 стр.).

38. Пападимитру X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и Сложность. -М.: Мир, 1985 г. (512 стр.).

39. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные задачи. М.: 1973 г. (304 стр.).

40. Страуструп Б. Язык программирования С++, 3-е издание. М.: «Невский диалект» - «Изд-во Бином», 1999 г. (991 стр.).

41. ТахаХ. Введение в исследование операций т.1. М.: МИР, 1985 г. (479 стр.).

42. Теренс Ч. Системное программирование на С++ для UNIX. К.: Издательская группа BHV, 1997 г. (592 стр.).

43. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида. ДАН СССР, 189, №5, 1969 г. (стр. 552—554).

44. Федоров А., РогаткинД. Borland Pascal в среде Windows. Киев: «Диалектика», 1993 г. (656 стр.).

45. Фомин Г.П. Методы и модели линейного программирования коммерческой деятельности / Учебное пособие для вузов. М.: Финансы и статистика, 2000 г. (127 стр.).

46. Хахулин Г.Ф. Постановки и методы решения задач дискретного программирования. М.: МАИ, 1992 г. (59 стр.).

47. Хачатуров В.Р., Веселовский В.Е., ЗлотовА.В. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. РАН. ВЦ.— М.: Наука, 2000 г. (354 стр.).

48. Хедли Дж. Нелинейное и динамическое программирование. М.: Мир, 1967 г. (507 стр.).

49. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975 г.

50. ХоваридР. Динамическое программирование и марковские процессы. -М.: Советское радио, 1964 г.

51. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974 г. (520 стр.).бО.ЭрроуК., ГурвицЛ., УдзаваХ. Исследования по линейному и нелинейному программированию. М.: ИЛ, 1962 г. (335 стр.).

52. ЮдинД.Б., Голыптейн Е.Г. Линейное программирование. М.: Наука, 1967 г. (776 стр.).

53. Юдин Д.Б., Голыптейн Е.Г. Линейное программирование (теория, методы и приложения). М.: Наука, 1969 г. (424 стр.).

54. Khakhulin G.F. The new approach to solution of integer linear optimization tasks. Proceedings of the fourth MAI/BUAA international symposium on automatic control. Moscow, Russia, August, 1997 r.