Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Корбут, Мария Федоровна
05.13.18
Кандидатская
2013
Омск
129 с. : ил.
Стоимость:
499 руб.
Оглавление
Введение
Глава 1. Математические модели и методы для задач об упаковке множества
1.1. Постановки задач и приложения
1.2. Задача о наибольшем независимом множестве
1.3. Полиномиально разрешимые случаи
1.4. Метод регулярных разбиений
1.5. Алгоритм перебора Г-классов
Глава 2. Исследование задач об упаковке множества с системами ограничений блочной структуры
2.1. Проектирование одной системы радиосвязи
2.2. Анализ Г-накрытий задач со связующими столбцами
2.3. Оценки мощности Г-накрытий для некоторых семейств задач
2.4. Подклассы КР-трудных задач
Глава 3. Разработка и анализ алгоритмов
3.1. Исследование процесса перебора Г-классов
3.2. Алгоритмы перебора Г-классов и лексикографической оптимизации для задач об упаковке множества
3.3. Алгоритмы решения задач блочной структуры
3.4. О приближенном решении задач
Глава 4. Результаты вычислительного эксперимента
4.1. Описание разработанного комплекса программ
4.2. О среднем числе итераций метода перебора Г-классов
4.3. Исследование алгоритмов для задач об упаковке множества .
4.4. Решение задач об упаковке множества блочной структуры . .
Заключение
Список литературы
Введение
Актуальность темы. Исследование различных задач оптимизации, разработка и анализ методов их решения осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного программирования (ЦП) [9.20,29.74.81,90.92]. Особый интерес к задачам ЦП вызван тем. что во многих случаях необходимо находить оптимальные решения, удовлетворяющие условию целочисленпости. Указанные задачи имеют большое леоретическое и практическое значение.
Модели и методы целочисленного программирования [8,21.25,27.37-39,69.78,85,91,93] применяются для анализа и решения задач дискретной оптимизации [4, 39, 64. 67. 73, 85], например, оптимального размещения [-5-7.11.32.33.52.53,77], о покрытии [26.84]. максимальной выполнимости логической формулы [2, 3, 43, 44], о рюкзаке [49, 56, 129, 133], задач проектирования с логическими ограничениями [14. 54, 63]. оптимизации па графах [79.80], поэтому данной проблематике посвящено значительное число публикаций.
Задачи об упаковке множества занимают важное место в дискретной оптимизации и имеют широкий круг приложений в экономике, планировании, управлении, теории информации и других областях [24.68,96-98.121.131,140.142]. Для указанных задач изучается их структура и сложность, выделяются полиномиально разрешимые случаи и семейства трудных задач, устанавливаются новые свойства многогранников, разрабатываются и исследуются алгоритмы точного и приближенного решения |66, 96, 100, 106, 107. 111. 114. 116, 124, 132, 138].
3) если получено х' G Z71, то обновить рекорд гес = f(x'), положить р = п 4- 1, х" = х перейти на шаг 3.
4) иначе перейти на шаг 2.
Шаг 4- Допустимое целочисленное решение, соответствующее рекорду, является оптимальным решением задачи (1.15). Если таких решений нет, то задача неразрешима.
Алгоритм LCE является конечным, число его итераций ограничено сверху мощностью L-структуры задачи.
Одним из подходов к построению оценок числа итераций алгоритмов перебора L-классов заключается в исследовании мощности L-накрытия задач. Для оценивания величины АД/L применялось погружение в различные множества с последующей оценкой числа целочисленных точек в них, например, параллелепипеды, симплексы, слои и другие [41]. Для задачи об упаковке множества была получен следующий результат.
Теорема 1.8. ([41]) Для задачи (1.12) имеет место неравенство
идь «С {т — 1)(1 4- п)т.
В работах [3,16,19,30,34,43—45, 52,109,110] проводились исследования алгоритма перебора L-классов, строились различные его модификации, учитывающие специфику задач, применялись гибридные схемы, в частности лексикографический перебор L-классов комбинировался с регулярными отсечениями, выполнялись экспериментальные исследования. В [62] был предложен вариант распаралеливания алгоритма LCE. Для задач выполнимости и максимальной выполнимости, одномерной задачи о рюкзаке удалось построить комбинаторные варианты алгоритма, в которых поиск представителя очередного L-класса осуществлялся аналитически без использования симплексных таблиц [44,57].
В последнее время особое внимание уделяется построению оценок в среднем числа итераций для алгоритма перебора L-классов при решении
Название работы | Автор | Дата защиты |
---|---|---|
Некоторые классы обратных задач для математических моделей тепломассопереноса | Сафонов, Егор Иванович | 2015 |
Моделирование, анализ и синтез управляемых комбинированных динамических систем | Комарова, Мария Сергеевна | 2012 |
Разработка вейвлет-методов для выявления предвестниковых эффектов землетрясений | Родионов, Евгений Анатольевич | 2018 |