Исследование и решение задач об упаковке множества на основе L-разбиения и лексикографической оптимизации

• Автор: Корбут, Мария Федоровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 129 с. : ил.

Оглавление
Введение
Глава 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-классов при решении