Математические модели и алгоритмы дискретной оптимизации распределенных баз данных тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Румянцева, Инна Ивановна

• Румянцева, Инна Ивановна
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Румянцева, Инна Ивановна

СОДЕРЖАНИЕ

стр.

Введение

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.Практические рекомендации по оптимизации параметров структуры РБД специального назначения

Выводы

Заключение

Литература

Приложения

Приложение 1

Приложение 2

Приложение 3

Введение диссертации (часть автореферата) на тему «Математические модели и алгоритмы дискретной оптимизации распределенных баз данных»

Введение.

Ключевой проблемой современной теории управления является оптимизация. Решение этой проблемы требует разработки и практического применения методов оптимизации, основанных на использовании последних достижений в области новых информационных и компьютерных технологий. Среди прикладных задач оптимизации важное место занимают задачи дискретного программирования. Большинство задач этого типа (коммивояжера, классическая задача теории расписаний, задача о раскраске, об оптимальном покрытии, о максимальном разрезе, о ранце и ряд других) являются универсальными задачами целенаправленного перебора и относятся к числу NP-сложных. Для их решения до настоящего времени не найдены эффективные алгоритмы, трудоемкость которых полиномиально зависела бы от размерности задачи[1-8]. Поэтому остается актуальной задача дальнейшего совершенствования и модификации алгоритмов решения, разработки их современного программного обеспечения.

Среди общих методов дискретного программирования [9-13] можно выделить три основных: отсечения, ветвей и границ, динамического программирования.

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

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

Введение более одного дополнительного ограничения на каждом шаге итерации (как в методе отсечения) приводит к построению дерева возможных вариантов, оценке для каждой вершины границы решения, отбрасыванию бесперспективных вершин. Все перечисленные особенности легли в основу метода ветвей и границ, идея которого впервые была сформулирована в известном алгоритме А.Лэнд и А.Дойг для решения задачи ЦЛП [19]. Широкую популярность метод получил после его применения Д.Литтлом, К.Мурти, Д.Суини, С.Кэрэл к решению задачи коммивояжера [20].

Метод ветвей и границ [21] сравнительно легок в применении: он не требует для своей реализации большого объема машинной памяти; его вычислительная схема проста и хорошо обозрима; конечность вычислений, как правило, не нуждается в доказательстве. Однако, решение многих практических задач большой размерности с помощью алгоритмов данного метода проблематично, так как экспериментальные оценки трудоемкости этих алгоритмов имеют экспоненциальную зависимость от размеров решаемых задач.

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

линейного программирования, неопределенных множителей Лагранжа, градиентные методы и, прежде всего, метод динамического программирования.

Метод динамического программирования был разработан Р.Беллманом [22], связан с работами А.А.Маркова и А.Вальда. Он основан на принципе оптимальности, который используется также в методе последовательного анализа вариантов В.С.Михалевича [23] и локальных вариаций Н.Н.Моисеева [24]. К положительным сторонам этого метода следует отнести: возможность решения вариационных задач с ограничениями-неравенствами и конечномерных экстремальных задач с дискретной структурой, упрощение поиска оптимальных решений задач комбинаторного типа за счет резкого сокращения объемов вычислений. В то же время, метод обладает рядом недостатков, таких как: отсутствие универсального алгоритма, пригодного для решения различных типов задач (алгоритмы, используемые в рамках динамического программирования, объединены лишь общей идеей и в каждом конкретном случае должны формироваться применительно к условиям задачи), большие трудности при решениии многомерных задач.

Существенно повысить эффективность методов ветвей и границ и динамического программирования и преодолеть их недостатки позволяет теория двойственности [25-31].

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

Кроме того, двойственная задача может быть использована для проверки оптимальности допустимого целочисленного решения. Совпадение приближенного решения двойственной задачи с допустимым целочисленным решением основной задачи свидетельствует об оптимальности целочисленного решения.

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

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

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

Методы оптимизации эффективно применяются в самых различных областях человеческой деятельности, особенно, при проектировании больших технических систем, к которым можно отнести вычислительные сети[32-39], распределенные банки и базы данных[40-42].

Вопросам проектирования структур распределенных баз данных посвящено большое количество работ известных авторов: Кульба В.В., Ма-миконов А.Г., Цвиркун А.Д.,Ужастов И.А., Якубайтис Э.А. [43-47].

Распределенные банки и базы данных (РБнД и РБД) отличает функциональная и структурная сложность, а процесс их проектирования характеризуется большой длительностью, высокой трудоемкостью и значительными финансовыми затратами. Имеющийся в настоящее время аппарат

для разработки логических и физических структур РБД недостаточно формализован и базируется, в основном, на использовании опыта и интуиции разработчиков, что не позволяет оптимизировать процессы проектирования и функционирования РБД.

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

В настоящее время, несмотря на многообразие моделей и методов проектирования распределенных баз данных, отсутствует единый комплекс взаимосвязанных формализованных моделей и методов анализа и синтеза оптимальных по заданным критериям эффективности логических структур РБД, локальных БД и сетевых каталогов, позволяющих автоматизировать процесс проектирования РБД на всех основных этапах их разработки. Реализация формализованных моделей и методов, пакетов прикладных программ (ППП) и систем автоматизированного проектирования представлена в настоящее время ограниченным числом разработок БД [4854], отдельных процедур проектирования РБД [55-62].

В работах отечественных [55,63,64] и зарубежных авторов [57, 5861] исследуются вопросы проектирования отдельных компонентов логического уровня РБнД, разработка которых осуществляется независимо, что приводит к существенному снижению эксплуатационных характеристик РБД.

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

информации и процедур ее обработки; многообразием критериев эффективности; ограничениями СУРБД, СУБД, операционных систем и технических средств; недостаточной разработкой используемых формальных методов проектирования.

Практика разработки логических структур РБД базируется на использовании эвристических методов проектирования рациональных и формализованных методов проектирования оптимальных логических структур РБД [45, 46, 52, 53, 55, 59-61, 65].

Большинство разработанных в настоящее время моделей синтеза логических структур РБД основывается на исследовании задач размещения баз данных или информационных массивов и программ по узлам вычислительной сети заданной конфигурации [55, 59-62], которые решаются с использованием методов целочисленного линейного [59, 60], нелинейного [58, 61], квадратичного [62] и динамического [66] программирования. В качестве элементов размещения используются базы данных или информационные массивы, структуры которых, в отличие от моделей [43, 46, 65, 67, 68], не оптимизируются.

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

В связи с вышеизложенным, научной задачей, решаемой в диссертационной работе, является теоретическое обоснование и разработка способов повышения эффективности методов оптимизации параметров структур РБД на основе теории двойственности.

Целью работы является разработка моделей, алгоритмов и пакета прикладных программ (ППП) оптимизации параметров логической и физической структур РБД.

Поставленная цель достигается решением ряда взаимосвязанных задач:

- разработка моделей оптимизации параметров логической структуры РБД;

- разработка моделей оптимизации параметров физической структуры РБД;

- совершенствование алгоритмов и методов решения задач оптимизации и оценка их эффективности.

Содержание этих решений изложено в трех главах настоящей работы.

В первой главе рассматриваются этапы и задачи проектирования РБД, проводится анализ и уточнение системы математических моделей оптимизации параметров логической и физической структур РБД, включающей: модель оптимизации распределения информационных массивов по узлам вычислительной сети по критерию суммарного среднего времени обработки запросов пользователей, модель оптимизации состава оперативного резерва информации в РБД по критерию суммарного среднего времени обработки запросов пользователей, модель оптимизации размещения экземпляров логических записей по страницам информационных массивов(ИМ) по критерию затраченной памяти при синтезе страниц массивов, модель оптимизации распределения логических массивов по типам памяти по критерию суммарного среднего времени доступа к ИМ. Показа-

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

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

В третьей главе обосновываются критерии оценки эффективности разработанных методов и алгоритмов оптимизации параметров структур РБД. Проводится сравнительная оценка эффективности разработанных и существующих методов и алгоритмов оптимизации. Приводится описание пакета прикладных программ, реализующего предлагаемые методы и алгоритмы.

В заключении формулируются результаты работы в целом.

Основными научными результатами, выносимыми на защиту, являются следующие:

1. Система математических моделей оптимизации параметров логической и физической структур РБД.

2. Способы определения границы решения и порядка ветвления переменных в методе ветвей и границ на основе теории двойственности.

3. Способы определения границы решения и порядка ветвления переменных в методе ветвей и границ на основе А - оценок и разрешающих множителей МС-М.

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

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

Апробация работы. Материалы диссертации докладывались, обсуждались и одобрены на VII Международной конференции "Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел", г. Воронеж (1995г.), III Российской международной конференции "Современные проблемы теории чисел и её приложения", г. Тула (1996г.), НТК ТВАИУ (1995г., 1997г.), НТК ВАА им. М.И.Калинина (1996г.).

Публикации. Материалы диссертации опубликованы в НТС ТВАИУ (1994-1996г.г.), НТС ВАА им. М.И. Калинина (1996г.)| ;

Реализация. Результаты исследований реализованы в НИР "Лукошко - АН", ОКР "Бинт - Т", внедрены в учебном процессе Тульского АИИ.

1 .АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПРОЕКТИРОВАНИЯ РАСПРЕДЕЛЕННЫХ БАЗ ДАННЫХ

1.1. Этапы, задачи и методы проектирования распределенных баз данных

Процесс проектирования распределенных баз данных включает анализ предметных областей пользователей, синтез оптимальных логических структур РБД, логических и физических структур локальных БД и сетевых каталогов, выполняемых на этапах технико-экономического обоснования проекта, разработки технического задания и технорабочего проектирования РБД [50]. Сложившаяся в настоящее время этапность разработки РБД в основном определяется многоуровневым представлением данных, связанным с содержательным различием выполняемых на каждом этапе работ, сложностью, длительностью и трудоемкостью процесса проектирования, необходимостью решения большого количества технических и организационных вопросов. Задачи, решаемые на каждом этапе проектирования РБД при использовании формализованных моделей и методов анализа и синтеза оптимальных логических и физических структур РБД, и их взаимосвязь с основными этапами создания автоматизированных систем управления приведены в таблице 1.1.

Таблица 1.1

Основные этапы Основные этапы про- Основные этапы автоматизи-

проектирования ектирования РБД рованного проектирования

АСУ РБД

Технико- Проектирование 1 .Предпроектный анализ ин-

экономическое внешних моделей формации предметных облас-

обоснование пользователей тей

Разработка 2.Проектирование внешних

технического моделей пользователей

задания 3.Проектирование ОВМ 4.Анализ ОВМ 5.Проектирование канонической структуры РБД

Разработка технического проекта Проектирование логической структуры 6.Синтез оптимальной логической структуры РБД 7.Проектирование логических структур локальных БД 8.Проектирование структуры сетевого каталога

Проектирование фи- 9.Синтез оптимальных физи-

зической структуры ческих структур локальных БД или выбор средств СУБД, обеспечивающих оптимальную физическую структуру 9.1.Оптимальный синтез ИМ. 9.2.Оптимальное распределение ИМ по типам ЗУ.

На этапе технико-экономического обоснования создания АСУ проводится комплекс научно-исследовательских и организационных работ, направленных на определение экономической целесообразности создания РБД и его функциональных возможностей. Предпроектный этап начинается с проведения

обследования предметной области и информационных требований пользователей; определяется состав и характеристики используемой информации, требования, предъявляемые к организации информационной базы, а также разрабатывается каноническая структура БД. Завершается данный этап разработкой технического задания (ТЗ), содержащего: описание характеристик системы управления; назначение РБД; основные требования к РБД; технико-экономические показатели функционирования РБД; состав, содержание и организацию работ по созданию РБД; порядок приемки и сдачи РБД.

Этап технического проектирования АСУ. Технический проект РБД, разрабатывается на основе ТЗ. На данном этапе заказчиком создается специализированное подразделение, предназначенное для решения задач администрирования банков данных. Кроме того, заказчиком создаются необходимые классификаторы информации с учетом требований обработки данных в условиях РБД, приобретается СУБД, тип которой определяется в ТЗ. Этап технического проектирования завершается разработкой технического проекта РБД, который содержит согласованный с заказчиком план мероприятий по подготовке к вводу РБД в эксплуатацию; описание комплекса технических средств, программного и информационного обеспечения, организационную структуру и технологию обработки данных в условиях РБД; систему регламентных запросов и организации БД; чертежи форм документов (видеограмм); перечень входных данных и выходных сообщений; описание контрольного примера для тестирования программных средств РБД.

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

реструктуризации.

Одним из основных этапов проектирования РБД является анализ предметных областей пользователей. Предметная область пользователей - это совокупность объектов управления, информация о которых моделируется с помощью БД и используется для решения различных функциональных задач. Основной целью данного этапа является изучение и анализ предметных областей пользователей, определение целесообразности проектирования РБД, обеспечение формализованного описания и структуризации предметных областей пользователей. Процесс анализа включает четыре взаимосвязанных этапа [47]: предпроектный анализ информационных множеств пользователей; анализ предметных областей и построение внешних, концептуальных, инфологиче-ских моделей данных пользователей; построение обобщенной внешней глобальной концептуальной модели РБД; нормализация обобщенной внешней модели (ОВМ) и построение канонической структуры РБД.

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

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

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

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

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

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

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

Более предпочтительной является методология нормализации, разработанная специально для иерархических и сетевых моделей данных. При этом под нормализацией понимается процесс упорядочения информации по уровням иерархии, выявление и устранение дублируемых информационных элементов и избыточных взаимосвязей (транзитивных зависимостей), группирование простых информационных элементов в семантически связанные группы, выделение в группах ключевых элементов и зависимых атрибутов. Методология нор-

мализации иерархических и сетевых моделей данных связана с исследованиями общих свойств бинарных и реляционных моделей, а также моделей, основанных на функциональных зависимостях.

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

Синтез логической структуры РБД рассматривается как процесс поиска оптимального варианта отображения канонической структуры РБД в логическую, которая обеспечивает оптимальное значение заданного критерия эффективности функционирования РБнД и удовлетворяет основным требованиям и ограничениям, накладываемым на логическую структуру на этапе разработки технического задания [50]. Для отображения канонической структуры в логическую используется метод объединения групп канонической структуры РБД в типы логических записей с одновременным распределением их по узлам вычислительной сети.

Основными критериями синтеза оптимальных логических структур РБД являются минимум общего времени выполнения множества запросов и корректировок пользователей, минимум суммарной стоимости хранения информации и реализации процедур обработки данных, минимум максимального времени (стоимости) реализации множества запросов и заданий на корректировку, инициируемых различными классами пользователей.

В качестве основных ограничений используются ограничения на временные и стоимостные характеристики процесса реализации запросов и корректировок; на объем доступной внешней памяти в узлах ВС; на пропускную спо-

собность каналов связи; на надежность доступа к заданному узлу ВС и др.

Решение задач синтеза оптимальных логических структур РБД позволяет определить состав типов логических записей; структуру и типы отношений между ними; размещение типов записей по узлам ВС; характеристики типов записей; использование типов записей при реализации процедур обработки.

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

Синтез физической структуры локальной БД рассматривается как процесс поиска оптимального варианта отображения логической структуры в структуру хранения, которая обеспечивает экстремум заданного критерия эффективности функционирования РБнД на физическом уровне [50].

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

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

время доступа к отдельным массивам БД, на объем и количество страниц памяти, на допустимый нижний уровень достоверности информации и др.

Синтез физической структуры локальной БД обеспечивает оптимальное распределение массивов по типам памяти и экземпляров логических записей по страницам памяти, выбор оптимальных методов организации записей и связей в пределах каждого массива или страницы памяти.

1.2. Математические модели оптимизации параметров логической

структуры РБД

1.2.1. Выбор и обоснование показателя эффективности функционирования РБД

В качестве основных критериев оптимизации параметров распределенных баз данных АСУ целесообразно рассматривать временные и надежностные характеристики их функционирования.

Пусть = = 1>Л)) " множество групповых информационных элементов;

3 = |зр |, |р= 1,Р0| - множество детерминированных запросов пользователей;

^ ={£$.}, |5=1,5'0| - множество заданий пользователей на корректировку и обновление информации в РБД;

£/ = }, = 1 - множество пользователей;

£)={дг}, (г=1,г0| - множество узлов ВС.

Введем характеристики вышеназванных множеств, которые будут использоваться в дальнейших постановках задач (см. табл. 1.2).

Таблица 1.2

Наименование, обозначение физический смысл

Матрица времен получения информации, содержащейся в группах 1^11 тк1 - максимально допустимое время получения информации г -й группы по запросу к -го пользователя

Матрица использования групп информационных элементов при выполнении запросов био- ¿у^-=1,если р-й запрос использует в процессе выполнения / -й групповой информационный элемент, О-в противном случае

Матрица частот использования запросов пользователями на задан-

ном интервале времени

¿;рк - частота использования р -го запроса к-м пользователем

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

при выполнении запросов

п

'р

у1р - среднее количество анализируемых

экземпляров / -й группы при выполнении р -го запроса

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

выполнения запросов ур1

ур1 - среднее количество групповых информационных элементов, выбираемых в результате выполнения р -го запроса

Матрица использования групп информационных элементов при выполнении заданий на корректиров-

ку

со

5/

1, если 5-е задание на корректировку изменяет или удаляет г -й групповой

информационный элемент О-в противном случае

Матрица частот использования за-дагий на корректировку пользователями на заданном интервале

- частота использования 5 -го задания на корректировку к -м пользователем

времени

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

экземпляров групп

У

«

уь - среднее значение количества корректируемых экземпляров г -й группы при выполнении 5 -й корректировки

Матрица использования запросов

пользователями РБД

(Ркр

(р\р=\, если к-и пользователь использует

р-й запрос, О-в противном случае

Матрица использования заданий на (р1ц-1, если к-и пользователь использует

корректировку ^ -е задание на корректировку,

пользователями РБД <Рк* О-в противном случае

Основными временными характеристиками функционирования РБД являются время реализации заданного множества запросов Г3 и время реализации заданного множества заданий на корректировку Гк, которые в сумме дают общее время выполнения «рабочей нагрузки» РБнД, т. е.

р=1 5=1

где Тр —время реализации р -го запроса пользователя, а Г/ —время реализации Б-аТ задания на корректировку. Время реализации р-го запроса пользователя складывается из следующих составляющих:

Г3 =?рз +/сб р р р р р

где ^ - время работы программ прикладного и сеансового уровней протоколов, обеспечивающих декомпозицию запроса на подзадачи и управление их реализацией [73]; Г® - время реализаци р-то запроса в локальной БД;

^ - время работы программ представительного и прикладного уровней протоколов, связанных с выполнением процедур сборки массивов промежуточных данных и формирования окончательного результата; - время инициирования

и передачи запроса (подзадачи) в локальную БД (узел ВС).

Время работы программ прикладного и сеансового уровней протоколов определяется как

где - время формирования одной подзадачи; кур - количество формируемых

подзадач, определяемое числом различных локальных БД (узлов ВС), к которым необходимо обратиться для поиска требуемых типов записей.

Реализация запроса в локальных БД включает процедуры поиска и считывания информации, формирования массивов промежуточных данных и передачи их в запрашивающий узел ВС, т.е. р 1 р р>

где 1ср- время, затрачиваемое на поиск и считывание информации, необходимой для реализации р-то запроса, из локальной БД в оперативную память; ¡р- время работы программ транспортной сети, обеспечивающих выбор маршрута, установление виртуального соединения и передачу информации по каналу связи.

Время формирования выходных сообщений, представляемых пользователю, определяется в виде

*ср6=^кУр (1.2)

где t^n - время работы программ представительного и прикладного уровней протокола, обеспечивающих выполнение операций сборки результатов двух подзадач в процессе формирования выходного сообщения; кур - количество процедур сборки, определяемое количеством порожденных подзадач. Время поиска требуемых типов записей определяется как

+ (1.3)

где /^ост- время поиска требуемых записей (блоков) в локальной БД; ¿,ож - время ожидания доступа и считывания информации из БД; /,обм - время обмена между

с

внешним запоминающим устройством (ВЗУ) и оперативной памятью; кр - количество считываемых блоков при выполнении р-го запроса. Обозначим

где г^0 —время ожидания доступа к БД и поиска требуемых записей (блоков).

время при выполнении канальной программы ввода-вывода: г1"1304, т. е.

, проц _ -дост .обм

11 — 1I 1

Время поиска информации в локальной БД определяется характеристиками физических методов организации данных на ВЗУ и параметрами этих устройств.

Время обмена данными между локальной БД (ВЗУ) и оперативной памятью определяется характеристиками процедур считывания (записи) информации и объемом считываемой информации: ¿°бм = теУБ, где те - время считывания (записи) единицы информации из локальной БД; ¥ъ - объем считываемой информации.

Полное время обслуживания заявки (¿"Р0") состоит из суммы независимых случайных величин: времени поиска дорожки (¿1дос) и длительности передачи информации (г^06), которые имеют равномерные распределения в интер-^ валах (0,г0) и (0,г0) соответственно, где ¿0 - время полного оборота диска и г0 - максимальная длительность передачи информации с ВЗУ в оперативную память. Распределение случайной величины г"13011 определяется как свертка

двух указанных равномерных распределений. При сделанных допущениях среднее время ожидания доступа и считывания информации с ВЗУ по адресу А определяется следующим образом [74]:

Время поиска /]дост и время обмена ?°бм определяют общее процессорное

отсюда

ож

где V - скорость перемещения головок накопителя на магнитном диске (НМД); А - адреса дорожек, являющиеся действительными числами, равномерно распределенными в интервале (0,1); р = < 1.

Объем памяти, занимаемый одним экземпляром Г -го типа записи, обозначаемый через у( 1) , определяется следующим образом:

где V" —объем полезной информации; Ц —длина одного указателя (адресной

ссылки); к? —количество указателей в типе записи; с—константа.

В связи с отсутствием на этапе логического синтеза информации о количестве указателей в типе записи, вводится в рассмотрение коэффициент %, учитывающий наличие служебной информации в записи. Объем памяти, занимаемый одним экземпляром, записывается в виде У^ = ^Р-/1, где определяет количество служебной информации на 1 байт полезной.

Объем полезной информации в одном экземпляре г -го типа записи определяется объемом входящих в него информационных групп, т. е. У" = £ >

где g = | - вектор длин информационных групп; - терминальный элемент, входящий в состав данной группы.

Объем информации, анализируемой подзадачей р-го запроса в г-м узле ВС за заданный период функционирования системы, определяется как

= 11 I (1.5)

к к, щг а] ек,

Объем информации, выбираемой подзадачей р-то запроса в соответствии с детерминированными условиями ее выполнения за этот же период, рассчитывается по формуле

выб

(1.6)

к И, едг еЛ,

Количество считываемых блоков при выполнении подзадачи р -го запро-

т/ДОСТ 7 б рг

са в г-м узле определяется как к -

-рг у •

Время выполнения б-го задания на корректировку складывается из следующих составляющих: Т* = ¿рз + + + где /5рз - время декомпозиции б-го задания на корректировку на подзадачи; ^ - время выполнения б-го задания на корректировку в локальной БД; ^ - время инициирования и передачи корректировки (подзадачи) в узел ВС (запрос блокировок локальной БД); t° - время формирования и передачи сообщения о результатах выполненной корректировки (снятие блокировок). Время декомпозиции рассчитывается по формуле

(1.7)

где ^ - время формирования одной подзадачи; kf - количество формируемых подзадач, определяемое общим числом узлов ВС, на которых размещаются копии требуемых записей.

Процесс выполнения задания на корректировку в локальных БД состоит из множества процедур поиска, корректировки и обновления данных, т. е.

с (1.8)

где - время поиска и корректировки хранимых данных; - время передачи корректирующей информации по каналам связи.

Время формирования и передачи сообщений о результатах выполненной корректировки зависит от числа порожденных ею подзадач и представляется в виде

(1.9)

где ^ - время формирования и передачи одного сообщения о выполненной корректировке (снятие блокировки локальной БД).

Составляющие времени выполнения э-го задания на корректировку запишутся в виде

,зп _ .до , ,обм 1 б . 1зг 1 + Ч

.П __ ,МК . ^ т/ЗП

х'У2 ~ Пг2 п ЛТ '

Сг\П

Объем передаваемой и записываемой информации V™ рассчитывается аналогично (1.5) и определяется как

к ¿[ок,

С учетом обозначений = '/7° и = ^^ Щ выражения

^ 42

для времени записи и времени передачи информации запишутся в виде

(1.10)

л

I +

к щг

V ¿[еИ, У

к едг

( \ гмк + У гп

V е/7, У

(1.11)

В приведенных зависимостях (1.1)—(1.11) используются такие величины, как время обмена данными между ВЗУ и ОП, время оборота диска ВЗУ, длина записи, размер служебной части записи, скорость перемещения головок НМД и т.д..

В данной работе предлагается рассматривать оптимизируемые характеристики логических структур РБД с меньшей степенью детализации. В качестве минимальной единицы информации предлагается рассматривать информационный массив, причем основным параметром управления [77] выступает факт наличия либо отсутствия данного ИМ на каком-либо узле ВС (распределение ИМ по узлам).

Максимизацию вероятности сохранности информационных массивов в заданном интервале времени, а следовательно минимизацию суммарных эксплуатационных затрат и максимизацию коэффициента готовности системы РБД обеспечивает круг задач оперативного резервирования, который включает [75] расчет оптимального числа копий и (или) предысторий.

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

Особенности обновления и использования массивов постоянных и текущих данных позволяют выделить следующие стратегии их резервирования[76]:

1. Используется некоторое число копий информационных массивов. Если основной массив разрушился, то используется первая его копия, если и она разрушилась, то - следующая и т.д.

2. Используются особенности организации обновления массивов текущих данных, которые заключаются в том, что в качестве копий текущего массива служат его предыстории (предыдущие массивы и массивы изменений). Если текущий массив разрушился, то он восстанавливается программой обновления из предыдущего массива и массива изменений. Если и этот массив разрушился, то его можно восстановить из предыдущей предыстории и т. д.

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

Полученные выражения для расчета основных вероятностных и временных характеристик стратегий резервирования программных модулей и информационных массивов сведены в таблицу 1.3.

Таблица 1.3

№

стратегий

I

р1 =1 Vй

Е1 =kr + 0p~H\-q

,к+1

II

PU=plpk+2-qk+2 ix

Е

„ 0

q-p

к+1 _

£ + 1

(ifc + 2)

1 -\qp

к +1

1-

£+2

III

_ у+2

X

X

v ' q-p

-\\У+1

y + 1-

1- UP

Здесь Р^ (7=1,11,111) - вероятность успешного решения текущей задачи при использовании стратегий j; - среднее время доступа к ЭВМ; q = 1 - р -вероятность разрушения массива при его обновлении; 0 - время обновления; т - время получения копии массива; к - число копий и (или) предысторий массива, х - число копий ну- число предысторий при стратегии III, причем

х + у = к.

Каждый ИМ характеризуется определенным временем выборки данных из него и временем выполнения его корректировки по требованию определен-

ной задачи (в дальнейшем - запроса пользователя). Указанное время зависит от производительности ЭВМ узла сети, а также от пропускной способности каналов связи. Иными словами, каждый ИМ характеризуется временем выборки (корректировки) по определенному запросу пользователя при размещении данного ИМ на определенном узле ВС.

Время выборки (корректировки) непосредственно на узле предлагается считать известной величиной, которая может быть определена экспериментальным путем на локальной ЭВМ в ходе подготовки исходных данных для решения оптимизационной задачи. Кроме того, предлагаемая методика организации резерва данных (оперативный резерв) и характеристики производительности современных и перспективных ЭВМ в узлах ВС позволяют пренебречь временем предоставления копии (см. табл. 1.3) в случае отказа основного ИМ.

Перечень величин, которые будут использоваться в дальнейших постановках задач, представлен в таблице 1.4.

Таблица 1.4

Величина Физический смысл

матрица распределения ИМ по узлам сети ||<^|| <рП1 = 1, если п-й ИМ располагается в 1-м узле сети; О-в противном случае

матрица закрепления пользователей за узлами ВС <уг) у/^1 = 1, если г-й пользователь закреплен за 1-м узлом; О-в противном случае

матрица генерации пользователями запросов на выборку данных у^ = 1, если г-й пользователь может выполнять 1-й запрос на выборку данных; О-в противном случае

матрица генерации пользователями зад на корректировку здний Угя К 1 ^ у^ = 1, если г-и пользователь может инициировать з-е задание на корректировку; О-в противном случае

матрица обращени] запросов к ИМ й = 1, если ^му запросу на выборку требуются данные из п-го ИМ; О-в противном случае

матрица использов ИМ заданиями на корректировку ания = 1, если э-е задание на корректировку может использовать п-й ИМ; О-в противном случае

матрица смежности акк о)1х12 = 1 ,если между Ц и 12 узлами есть канал связи; 0 -в противном случае

матрица вероятностей получения данных из им РпЛ рпд -вероятность получения данных из п-го ИМ, расположенного на 1-м узле ВС, по ^му запросу

матрица объема резерва ИМ ||*й|| каждый п-й ИМ имеет кп-1 копий

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

1.2.2. Оптимизация распределения ИМ по узлам ВС по критерию суммарного среднего времени обработки запросов пользователей

Постановка задачи. Рассмотрим распределенную вычислительную сеть произвольной структуры (рис. 1.1), состоящую из Ь ЭВМ, каждая из которых имеет определенное количество пунктов обработки информации (пользователей), под которыми понимаются микро-ЭВМ, дисплеи и т.п.

Закрепление пользователей за узлами сети описывается матрицей (г = 1,13; 1=1, С), где Л - общее количество пользователей в сети, причем у/^ =1, если г-й пользователь закреплен за Ь-м узлом; О-в противном случае.

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

корректировку. Соответствующие отношения определяются величинами у 3гГ и

Л

укГ5 (г = 1,Ъ 8=1, 5), где:

УгГ

ук =

/ гэ

1, если г-й пользователь может инициировать 1-й запрос на выборку данных;

О —в противном случае;

1, если г-й пользователь может инициировать Б-е задание на корректировку;

О —в противном случае;

Б и Э —общее количество в сети запросов на выборку и заданий на корректировку соответственно.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Румянцева, Инна Ивановна

126 Выводы

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

2. Результаты экспериментальной оценки способов определения границ решения с использованием теории двойственности показали, что наиболее эффективным является однократное решение двойственной задачи итерационными методами, который позволяет уточнять оценки переменных и определить порядок их ветвления. Среднее время решения с применением данного способа в 7-42 раза относительно первого, в 3-13 раза относительно второго и в 1.1-2.2 раза относительно третьего способа меньше. С ростом числа ограничений и переменных задачи это преимущество возрастает.

3. Применение разрешающих множителей модифицированного симплекс-метода сокращает время решения задачи в 3.02-8.05 раза относительно алгоритма с определением верхних границ при ветвлении базисных переменных с помощью А-оценок и в 2.44-3.42 раза относительно алгоритма с определением границ симплекс-методом.

4. Упорядочивание ограничений по жесткости и включение дополнительного отсева бесперспективных вариантов по условиям метода ветвей и границ с использованием двойственной задачи в способе встречного решения дает выигрыш по времени в 2.3-14.8 раза за счет уменьшения числа решений функциональных уравнений динамического программирования (числа итераций).

5. Экспериментальная проверка уточненной системы математических моделей, разработанных алгоритмов оптимизации параметров логической и физической структур РБД подтвердила их эффективность и целесообразность включения в состав специального математического и программного обеспечения.

128

ЗАКЛЮЧЕНИЕ

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

Предлагается рассматривать процесс функционирования системы распределенной обработки данных как взаимодействие запросов пользователей с информационными массивами. Под запросами пользователей понимаются собственно запросы на выборку данных из ИМ и задания на их корректировку. Информационный массив в рамках данной работы рассматривается как минимальная единица информации и характеризуется: временем выборки (корректировки), зависящем от расположения ИМ на конкретном узле сети, в конкретном типе памяти и вида запроса; вероятностью успешной выборки (корректировки); объемными характеристиками.

В качестве параметров оптимизации РБД используются, как правило, временные, стоимостные и надежностные характеристики их функционирования. При этом для РБД специального назначения целесообразным является решение задач оптимизации по временным параметрам (оперативность) при ограничениях на надежностные, стоимостные и технические характеристики, либо по критерию надежности (устойчивость) при ограничениях на временные, технические и стоимостные характеристики.

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

Для сокращения размерности общей задачи предложена ее декомпозиция на ряд взаимосвязанных задач. А именно, для параметров логической структуры РБД:

- оптимизация распределения ИМ по узлам ВС по критерию минимума суммарного среднего времени обработки запросов пользователей;

- оптимизация состава оперативного резерва информации в РБД по критерию минимума суммарного среднего времени обработки запросов пользователей; для параметров физической структуры РБД:

- оптимизация размещения экземпляров логических записей по страницам ИМ по критерию минимума затраченной памяти при синтезе страниц массивов;

- оптимизация распределения логических массивов по типам памяти по критерию минимума суммарного среднего времени доступа к информационным массивам.

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

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

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

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

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

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

Экспериментальная проверка разработанного комплекса математических моделей, методов и алгоритмов оптимизации параметров логической и физической структур РБД подтвердила их работоспособность, эффективность и целесообразность включения в состав специального математического и программного обеспечения АСУ различного назначения.

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

Список литературы диссертационного исследования кандидат технических наук Румянцева, Инна Ивановна, 1999 год

ЛИТЕРАТУРА

1. Алексеев О.Г. Алгоритм решения задачи о покрытии // Изв. АН СССР. Техн. кибернетика. - 1980. - № 5. - С. 12-16.

2. Алексеев О.Г., Григорьев В.Ф. Некоторые алгоритмы решения задачи о покрытии и их экспериментальная проверка на ЭВМ // ЖВМиМФ. -1984. - Т. 24, № 10. - С. 1565-1570.

3. Быков В.Н., Сергиенко И.В. Метод решения обобщенной задачи о ранце с использованием параллельных вычислений // Докл. АН УССР. Сер. А. - 1980. - № 10. - С. 810-812.

4. Ковалев М.М., Котов В.М. Анализ градиентного метода решения задачи коммивояжера // ЖВМиМФ. -1981. - № 4. - С. 1035-1038.

5. Кравец В.Л., Сергиенко И.В. Декомпозиционный метод решения одного класса комбинаторных оптимизационных задач // Кибернетика. -1983.- № 6. - С. 77-79, 84.

6. Михалевич B.C., Волкович В.Л., Волошин А.Ф., Поздняков Ю.М. Алгоритмы последовательного анализа и отсеивания вариантов в задачах дискретной оптимизации // Кибернетика. - 1980. - № 3. - С. 76-85.

7. Сергиенко И.В., Каспшицкая М.Ф. Об устойчивости алгоритмов метода вектора спада на одном классе комбинаторных оптимизационных задач // Докл. АН УССР. Сер. А. -1983. - № 10. - С. 64-66.

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

9. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука. Гл. ред. физ.-мат. лит., 1987. - 248 с.

10. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. - М.: Наука, 1981. - 208 с.

11. Корбут A.A., Финкелынтейн Ю.Ю. Приближенные методы дискретного программирования // Изв. АН СССР. Сер. Техн. кибернетика. -1983.-№ 1. - С. 165-176.

12. Михалевич B.C., Сергиенко ИВ., Шор Н.З. Исследования методов решения оптимизационных задач и их приложения // Кибернетика. -1981.-№4.- С. 89-113.

13. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. - Киев : Наук, думка, 1988. - 472 с.

14. Gomory R.E. Outline of an algorithm for integer solution to linear programs // Bull. Amer. Math. Soc. - 1958. - V.64, № 5. - P. 275-278.

15. Колоколов А.А. Верхние оценки числа отсекающих плоскостей для циклического алгоритма Гомори // Методы моделирования и обработки информации. - Новосибирск : Наука , 1976. - С. 106-116.

16. Колоколов А.А. Регулярные отсечения при решении задач целочисленной оптимизации // Управляемые системы. - Новосибирск : Наука, 1981. -21. - С. 18-25.

17. Колоколов А.А. Нижняя оценка числа итераций для одного класса алгоритмов отсечения // Управляемые системы. - Новосибирск : Наука, 1983.-23.-С. 64-69.

18. Колоколов А.А. Алгоритмы отсечения и некоторые разбиения множеств // Дискретная оптимизация и численные методы решения прикладных задач. - Новосибирск : ВЦ СО АН СССР, 1986. - С. 50-67.

19. Land А.Н., Doig A.G. An automatic method of solving descrete programming problems // Econometrica. - 1960. - V.28, № 3. - P. 497-520.

20. Little J.D., Murty K.G., Sweeney D.W., Karel C. An algorithm for the treveling salesman problem // Oper. Res. - 1963. - V.ll, № 6. - P. 972-989.

21. Корбут А.А., Сигал И.Х., Финкелыптейн Ю.Ю. Метод ветвей и границ: Обзор теории, алгоритмов, программ и приложений.- Math. Ор-erathionsforsch. und Statist., Ser. Optimiz., 1977. - 8, № 2. - С. 253-280.

22. Bellman R. Dynamic programming. - Princeton: Priceton University Press, 1957.

23. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. 1Д1 // Кибернетика. - 1965. - № 1.- С. 45-55. - № 2.- С. 85-89.

24. Моисеев H.H. Методы динамического программирования в теории оптимальных управлений. 1,11 // Журн. вычисл. математики и мат. физики. - 1964. - ТА, № 3. - С. 485-494. - 1965. - Т.5, № 1. - С. 44-56.

25. Алексеев О.Г., Алексеев А.О., Анисимов В.Г., Анисимов Е.Г. Применение двойственности для повышения эффективности метода ветвей и границ при решении задачи о ранце // ЖВМиМФ. - 1985. - Т. 25, № 11. -С. 1666-1673.

26. Алексеев О.Г., Алексеев А.О., Кисилев В.Д. Применение двойственности для определения порядка ветвления переменных и границ при решении задачи о ранце // ЖВМиМФ. - 1990. - Т.ЗО, № 4. - С. 630-632.

27. Алексеев О.Г., Киселев В.Д. Двойственные задачи при использовании метода ветвей и границ // Электронное моделирование . - 1990. - Т. 12, №4. - С. 34-37.

28. Алексеев О.Г., Алексеев А.О., Кисилев В.Д., Мировицкий Г.П. Применение двойственности для повышения эффективности метода встречного решения функциональных уравнений динамического программирования // Кибернетика. - 1990. - № 1. - С. 114-116.

29. Голынтейн Е.Г. Теория двойственности в математическом программировании и ее приложения. - М.: Наука, 1971.

30. Лебедев С.С., Шейнман O.K. Двойственность в целочисленном программировании II Экономика и мат. методы. - 1981. - Т. 17, вып. 3. -С. 593-608.

31. Киселев В.Д., Румянцева И.И. Двойственность в дискретном программировании // Сборник тезисов докладов X НТК ТВАИУ. - Тула. -1995. С. 111.

32. Киселев В.Д., Румянцева И.И. Применение двойственности в задачах дискретного программирования // Материалы международной конференции Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел. - Воронеж: 1995.

33. Румянцева И.И., Карелин Д.В., Лычиц Н.С., Огнев Е.В. Определение порядка ветвления переменных и оценки границ решения задачи ЦЛП с булевыми переменными // Научно-технический сборник №13. - Тула: ТВАИУ. - 1996. - С. 247-251.

34. Киселев В.Д., Румянцева И.И. Применение теории двойственности в методе встречного решения функциональных уравнений динамического программирования // Материалы российской международной конференции Современные проблемы теории чисел и ее приложения. - Тула. - 1996.

35. Привалов А.Н., Румянцева И.И. Метод решения задачи выбора количества рабочих мест в локальной вычислительной сети // Научно-технический сборник № 11. - Тула: ТВАИУ. - 1994. - С. 105.

36. Привалов А.Н., Румянцева И.И. Оптимизация распределения нагрузки между серверами в локальной вычислительной сети // Научно-технический сборник № 11. - Тула: ТВАИУ. - 1994. - С. 107.

37. Привалов А.Н., Румянцева И.И. Метод решения задачи обоснования структурной организации интерсетей // Научно-технический сборник №11. - Тула: ТВАИУ. - 1994. - С. 110.

38. Привалов А.Н., Румянцева И.И. Метод решения задачи распределения нагрузки между рабочими станциями ЛВС // Научно-технический сборник№11. -Тула: ТВАИУ. - 1994. -С. 113.

39. Привалов А.Н., Румянцева И.И. Модель оптимизации распределения информационной нагрузки вычислительной сети // Сборник тезисов докладов X НТК ТВАИУ. - Тула. - 1995. - С. 128.

40. Привалов А.Н., Румянцева И.И. Адаптивная система оптимизации военно-технических задач управления // Сборник тезисов докладов X НТК ТВАИУ. - Тула. - 1995. - С. 129.

41. Павлов A.A., Румянцева И.И. Определение оптимального состава резерва информационного обеспечения вычислительной сети специаль-

ного назначения // Сборник тезисов докладов XXXIV НТК ВАА им. Калинина. - 1996. - С. 113-114.

42. Киселев В.Д., Румянцева И.И. Пути повышения устойчивости ИВП в локальных вычислительных сетях // Сборник тезисов докладов XI межвузовской НТК. - Тула. - 1997. - С. 116.

43. Киселев В.Д., Павлов A.A., Румянцева И.И. Оптимизация параметров РБД АСУ с учетом резервирования // Сборник тезисов докладов X НТК ТВАИУ. - Тула. - 1995. - С. 108.

44. Киселев В.Д., Павлов A.A., Румянцева И.И. О подходе к синтезу оптимальных структур РБД АСУ//Сборник тезисов докладов X НТК ТВАИУ - Тула. - 1995. - С. 32-33.

45. Павлов A.A., Румянцева И.И. Оптимизация логической структуры информационного обеспечения системы распределенной обработки данных // Научно-технический сборник № 4. - Санкт-Петербург: ВАА им. Калинина. - С. 80-82.

46. Кульба В.В., Косяченко С.А., Ужастов И.А. Система автоматизированного проектирования распределенных баз данных для АСУ // Вопросы разработки и ведения баз данных средствами СУБД ИНЕС.-М.: ВНИИСИ, 1985.

47. Мамиконов А.Г., Цвиркун А.Д., Кульба В.В. Автоматизация проектирования АСУ. - М.: Энергоиздат, 1981.

48. Мамиконов А.Г., Кульба В.В., Косяченко С.А., Ужастов И.А. Анализ предметных областей пользователей и построение канонической структуры распределенных баз данных. Препринт. - М.: Ин-т проблем управления, 1985.

49. Ужастов И.А., Петрова В.Е. Синтез оптимальных логических структур распределенных баз данных // Методы оптимизации сложных сис-тем.-М.: Наука, 1987.

50. Мамиконов А.Г., Кульба В.В., Косяченко С.А., Ужастов И.А. Оптимизация структур распределенных баз данных в АСУ. - М.: Наука. Гл. ред. физ.-мат. лит., 1990.

51. Якубайтис Э.А. Информационно-вычислительные сети. - М.: Финансы и статистика, 1984. - 232 с.

52. Хаббард Дж. Автоматизация проектирования баз данных. - М.: Мир, 1984.

53. Davenport R.A. Data analysis for data base design // Australian Computer J. -1978.-V.10,№4.-P. 122-137.

54. Davenport R.A. Logical data base design - from entity model to DBMS structure // Australian Computer J. - 1979. - V.ll, № 3. - P. 82-97.

55. Ашимов A.A., Мамиконов А.Г., Кульба B.B. и др. Формализованные модели и методы анализа и синтеза структур баз данных // XIII Всесо-юз. семинар-совещание "Управление большими системами".-Алма-Ата: Каз. политехи, ин-т, 1983. - С. 134-135.

56. Мамиконов А.Г., Кульба В.В., Косяченко С.А. и др. Автоматизация этапов анализа и синтеза структур баз данных при разработке АБД // Банки данных. Тез. докл. II Всесоюз. конф., Секция 3. - Киев: Ин-т кибернетики АН УССР, 1983. - С. 15-17.

57. Мамиконов А.Г., Ашимов A.A., Кульба В.В. и др. Анализ информационных потоков и построение канонической структуры баз данных (Методические материалы и методика).-Алма-Ата: КазНИИНТИ, 1984.

58. Мамиконов А.Г., Ашимов A.A., Кульба В.В. и др. Формализованные модели и методы анализа и синтеза оптимальных структур баз данных // II Всесоюз. совещ. "Автоматизация проектирования и конструирования". Тез. докл., 4.1. - М.: Ин-т проблем управления, 1983. - С. 65-66.

59. Шаймарданов Р.Б. Моделирование и автоматизация проектирования структур баз данных. - М.: Радио и связь, 1984.

60. Сумароков JI.H. Архитектура сети МСНТИ // Международная конференция "Базы данных в сетях ЭВМ". - М.: МЦНТИ, 1984. - С. 3-7.

61. Bray О Н. Distributed data base design considerations // IEEE Trends and Applications. Computer Networks Symposium.-Gaithersburg, 1976. - P. 121-127.

62. Akoka J. Design of optimal distributed data base systems // International Symposium on Distributed Data Bases. - Paris: North-Holland Publ. Co., INRIA, 1980.-P. 229-246.

63. Levin K.D., Morgan H.L. Optimizing distributed data base - a framework for recearch // AFIPS Conf. Proc. - Montvale N.J., 1975. - V.44. -P. 473-478.

64. Machmud S.A., Riordon G.L. Optimal allocation of resources in distributed information network // ACM Trans. Data Base System. - 1976. - V.l, № 1. -P. 66-78.

65. Fisher M.L., Hochbaum D.S. Data base location in computer networks // J. ACM. - 1980. - V.27, № 4. - P. 718-737.

66. Chu W.W. Task allocation in distributed data processing // Computer.-1980. -V. 13, № 11. - P. 57-69.

67. Глушков B.M., Стогний A.A., Базилевич И.А. Средства работы со структурированными данными в сетях ЭВМ (обзор) // Управляющие системы и машины, 1980. - № 6. - С. 63-69.

68. Калиниченко JI.A., Костромина О.Е., Хитрова О.Н. Концепции построения систем управления распределенными базами данных // Прикладная информатика. Вып. 1(6). - М.: Финансы и статистика, 1984. - С. 6-47.

69. Ужастов И.А. Автоматизация этапов анализа и синтеза структур распределенных баз данных // Всесоюз. конф. по автоматизации проектирования систем управления. Тез. докл. (Ереван, октябрь 1984). - Москва, 1984. -С. 33-35.

70. Levin K.D., Morgan H.L. A dynamic optimization model for distributed data base // Operations Recearch. - 1978. - V. 26, № 5. - P. 824-835.

71. Кульба В.В., Косяченко С.А., Ужастов И.А. Задачи проектирования распределенных баз данных // Создание интегрированной ОАСУ-ХИМ. - М.: НИИТЭХИМ, 1985. - С. 90-100.

72. Ужастов И.А. Формализованные модели и методы анализа и синтеза структур РБД // II Всесоюз. семинар по методам синтеза типовых модульных систем обработки данных (Звенигород, 1985). - М.: Ин-т проблем управления, 1985. - С. 70-71.

73. Крамаренко , Голыцук И.А. Мультипроцессорная схема управления данными в СУБД с послойной архитектурой // Управляющие системы и машины. - 1983. - № 4. - С. 97-103.

74. Липаев В.В. Распределение ресурсов в вычислительных системах. - М.: Статистика, 1979.

75. Кульба В.В., Сомов С.К., Шелков А.Б. Резервирование данных в сетях ЭВМ. - Изд-во Казанского университета, 1987. - 175 с.

76. Кульба В.В., Мамиконов А.Г., Пелихов В.П., Шелков А.Б. Методы повышения достоверности и сохранности информации в АСУ: Обзор. -Автоматика и телемеханика. - 1985. - № 2. - С. 5-33.

77. Мельник Э.М. Теоретические основы построения автоматизированных систем управления. Основы системотехники. - Тула: ТВАИУ, 1988. -85 с.

78. Мельник Э.М. Методы оптимального планирования и основы моделирования боевых действий. Применение теории массового обслуживания для моделирования боевых действий и технических средств (учебное пособие). - Тула: ТВАИУ, 1985. - 47 с.

79. Киселев В.Д. Теоретические основы оптимизации информационно-вычислительного процесса в перспективных АСУ РВ и А Сухопутных войск. - Дис. доктор, тех. наук. - Тула: 1994. - 266 с.

80. Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы: Пер. с англ. - М.: Мир, 1990. - 506 с.

81. Пономарева К.В., Кузьмин С.А. Информационное обеспечение АСУ. - М.: Высшая школа. -1991.

82. Kolesar P.J. A branch - and - bound algorithm for the knapsack problem // Manag. Sei. - 1967. - V. 13, № 9. - P. 723-735.

83. Алексеев О.Г. Применение способа встречного решения для повышения эффективности метода динамического программирования // Изв. АН СССР. Техн. кибернетика. - 1968. - № 3. - С. 106-113.

84. Волкович В.Л., Войналович В.М., Кудин В.И. Релаксационная схема двойственного строчного симплекс-метода // Автоматика. - 1988. - № 1.

С. 39-46.

85. Данильченко И.А., Макаренков Ю.М., Пшеннова Э.Ф. Метод предварительного сокращения размерности задач линейного программирования с неотрицательной матрицей условий // Кибернетика. - 1980. - № 3. -С.103-107.

86. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. - М.: Наука. - 1982. - 296 с.

87. Алексеев О.Г., Киселев В.Д. Применение разрешающих множителей модифицированного симплекс-метода в задачах целочисленного линейного программирования // ЖВМиМФ. - 1990. - Т. 30, № 11. - С.

88. Алексеев О.Г., Алексеев А.О., Кисилев В.Д. Использование оценок переменных для определения границ решения в задачах дискретного линейного программирования // Электронное моделирование. - 1991. -Т.13, № 4. - С. 29-34.

89. Киселев В.Д., Алексеев О.Г. Упорядочение ограничений в методе встречного решения функциональных уравнений динамического программирования // Экономика и математические методы. -1995

90. Алексеев О.Г., Алексеев А.О., Кисилев В.Д., Мировицкий Г.П. Применение двойственности для повышения эффективности метода встречного решения функциональных уравнений динамического программирования // Кибернетика. - 1990. - № 1. - С. 114-116.

91. Киселев В.Д. Модификация алгоритма встречного решения в задачах динамического программирования // Научно-технический сборник № 3. - Тула: ТВАИУ, 1986. - С. 39-43.

92. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир. -1981.-323 с.

93. Киселев В.Д., Бабаев А.А., Олейник В.А. Методика экспериментальной оценки эффективности алгоритмов оптимизации военно-технических решений // Тематический сборник № 16, часть II-JI.: ВАА им. Калинина, 1988.

94. Вероятностные методы в вычислительной технике. Под ред. Лебедева А.Н. и Чернявского Е.А.. - М.: Высшая школа. - 1986. - 312 с.