Математические модели и алгоритмы дискретной оптимизации распределенных баз данных

• Автор: Румянцева, Инна Ивановна
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Тула
• Количество страниц: 177 с.

СОДЕРЖАНИЕ

Введение
1.АНАЛИЗ ПРИМЕНЕНИЯ МЕТОДОВ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПРОЕКТИРОВАНИЯ РАСПРЕДЕЛЕННЫХ БАЗ ДАННЫХ
1.1 Этапы, задачи и методы проектирования РБД
1.2. Математические модели оптимизации параметров логической структуры РБД
1.2.1. Выбор и обоснование показателя эффективности функционирования РБД
1.2.2. Оптимизация распределения ИМ по узлам ВС по критерию суммарного среднего времени обработки запросов пользователей
1.2.3. Определение оптимального состава оперативного резерва информации в РБД
1.3. Математические модели оптимизации параметров физической структуры РБД
1.4. Особенности комбинаторных методов оптимизации и пути повышения их эффективности
Выводы
2.ПРИМЕНЕНИЕ ТЕОРИИ ДВОЙСТВЕННОСТИ В МЕТОДЕ ВЕТВЕЙ И ГРАНИЦ И ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
2.1. Предварительное сокращение размерности задачи на основе теории двойственности
2.2. Способы оценки границ решения при использовании теории двойственности
2.3. Определение порядка ветвления переменных и оценка границ решения задачи целочисленного программирования с булевыми переменными
2.4. Применение разрешающих множителей модифицированного симплекс-метода для повышения эффективности метода ветвей и границ
2.5. Применение теории двойственности в методе встречного решения функциональных уравнений динамического программирования
Выводы
3.ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА МЕТОДОВ ОПТИМИЗАЦИИ НА ОСНОВЕ РАЗРАБОТАННОГО ПАКЕТА ПРИКЛАДНЫХ ПРОГРАММ
3.1. Экспериментальная оценка эффективности методов и алгоритмов оптимизации
3.2.Практические рекомендации по оптимизации параметров структуры РБД специального назначения
Выводы
Заключение
Литература
Приложения
Приложение
Приложение
Приложение

Введение.
Ключевой проблемой современной теории управления является оптимизация. Решение этой проблемы требует разработки и практического применения методов оптимизации, основанных на использовании последних достижений в области новых информационных и компьютерных технологий. Среди прикладных задач оптимизации важное место занимают задачи дискретного программирования. Большинство задач этого типа (коммивояжера, классическая задача теории расписаний, задача о раскраске, об оптимальном покрытии, о максимальном разрезе, о ранце и ряд других) являются универсальными задачами целенаправленного перебора и относятся к числу NP-сложных. Для их решения до настоящего времени не найдены эффективные алгоритмы, трудоемкость которых полиномиально зависела бы от размерности задачи[1-8]. Поэтому остается актуальной задача дальнейшего совершенствования и модификации алгоритмов решения, разработки их современного программного обеспечения.
Среди общих методов дискретного программирования [9-13] можно выделить три основных: отсечения, ветвей и границ, динамического программирования.
Идейно наиболее простым является метод отсечения. Однако, он обладает существенными недостатками: нерегулярность вычислительной процедуры и плохая сходимость к целочисленному решению. Первым примером реализации метода отсечения служат известные алгоритмы Р.Гомори [14]. В работах Колоколова A.A. [15-18] развивается новый подход к анализу метода отсечения и задач целочисленного линейного программирования, в основе которого лежит идея исследования эффективности алгоритмов с помощью специальных разбиений допустимой области соответствующей непрерывной задачи. В терминах такого разбиения определяется "объем" отсекаемой части (дробного накрытия) и глубина отсе-

виртуальный КС посредством передачи по кратчайшему маршруту. Наличие
реальных каналов связи между узлами описывается матрицей соц |
12 = 7, С;), причем озц 1=1, если между С и /-2 узлами есть канал связи; 0 —в противном случае. Кроме того, =0 для 1
Тогда в ходе решения задачи требуется найти такие (р п! , которые минимизировали бы
р -? 5 _к- 1Л
(1.12)

при временных и системо-технических ограничениях , где:
Й - среднее время выполнения / -го запроса на выборку данных; в силу
того, что одна и та же задача (запрос, задание на корректировку) может выполняться по требованию различных пользователей, время ее решения будет зависеть от того, каким пользователем задача инициирована (сказанное в равной мере относится и к среднему времени выполнения заданий на корректировку данных);
- среднее время выполнения 5 -го задания на корректировку, инициированного г -м пользователем;
Для определения среднего времени выполнения запросов воспользуемся выражением

с- $ - X X Хп '/л-1,
1=1 П
-ЗУ ,, ,-зкс «РпДпЦ, + (1 ~ Фпд 1пП
(1.13)

где гп{1 - среднее время выполнения f -го запроса по и-му ИМ непосредственно на / -м узле ВС (узел, за которым г-й пользователь закреплен);
Са2 " среднее время выполнения указанного запроса при условии, что требуемый(-е) ИМ расположен(ы) на узле, отличном от /-го (£-9-й), причем пе-