Симметрии многогранника системы независимости и их применение для решения задачи об упаковке множества

Симметрии многогранника системы независимости и их применение для решения задачи об упаковке множества

Автор: Червяков, Олег Владимирович

Шифр специальности: 05.13.16

Научная степень: Кандидатская

Год защиты: 2000

Место защиты: Омск

Количество страниц: 126 с. ил.

Артикул: 285727

Автор: Червяков, Олег Владимирович

Стоимость: 250 руб.

Симметрии многогранника системы независимости и их применение для решения задачи об упаковке множества  Симметрии многогранника системы независимости и их применение для решения задачи об упаковке множества 

1.1. Основные понятия
1.2. Линейные симметрии и автоморфизмы.
1.3. Аффинные симметрии и Яотображения
1.4. Критерий существования Яотображения
1.5. Симметрии с единичным сдвигом.
1.6. Аффинные симметрии специальных систем независимости
Глава 2. Понижение размерности задачи
на системе независимости
2.1. Постановки задач
2.2. Задача об упаковке множества
2.3. Полиэдральная схема понижения размерности.
2.4. Комбинаторная схема.
2.5. Процедура ветвления и задача об упаковке .
Глава 3. Приближенные алгоритмы
решения задачи об упаковке
3.1. Приближенная схема понижения размерности.
3.2. Приближенный алгоритм решения задачи об упаковке .
3.3. Приближенный алгоритм для некоторых
специальных систем независимости
3.4. Задача о наибольшем независимом множестве
вершин и алгоритм ПР
3.5. Вычислительный эксперимент.
Заключение
Список литературы


Эксперименты проводились на задаче об упаковке множества первая и вторая серии экспериментов и задаче о наибольшем независимом множестве вершин третья и четвертая серии. В общей сложности было решено 5 задач об упаковке множества и 6 задач о наибольшем независимом множестве вершин графа. Из полученных результатов вытекает, что предложенные в работе приближенные алгоритмы имеют хорошую экспериментальную оценку точности как на случайных, так и на специально сгенерированных задачах и в среднем лучше известного жадного алгоритма, алгоритмов Хватала и Кларксона 1. Эксперименты показали, что использование в метоле ветвей и границ процедуры понижения размерности, основанной на симметриях многогранника, дает значительное ускорение процесса решения задач. Результаты работы докладывались на Втором Сибирском конгрессе по прикладной и индустриальной математике Новосибирск, , Хой Всероссийской конференции Математическое программирование и приложения Екатеринбург, , Международной конференции Проблемы оптимизации и экономические приложения Омск, . Международной Сибирской конференции по исследованию операций Новосибирск. Х1ой Всероссийской конференции Математическое программирование и приложения Екатеринбург, , а также на семинарах кафедры математического моделирования Омского государственного университета. Института информационных технологий и прикладной математики СО РАН и Института математики им. С.Л. Соболева СО РАН. Основные результаты диссертации опубликованы в работах . Автор выражает искреннюю признательность научному руководителю Р. Ю.Симанчву за постоянное внимание и всестороннюю поддержку при выполнении данной работы.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.264, запросов: 244