Математические методы и программные средства для исследования и решения задач, формализуемых системами линейных дизъюнктных неравенств

• Автор: Дорожкина, Наталия Николаевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Минск
• Количество страниц: 160 с. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. МОДЕЛИ ЗАДАЧ ПЛАНИРОВАНИЯ И

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

1.1. Модель задачи оперативного регулирования производственного процесса.

1.2. Модели задач теории расписаний и планирования.

1.3. Модель задачи распределительного типа.

1.4. Принадлежность задачи линейных дизъюнктных неравенств к классу ЫР

1.5. Возможные варианты сведения системы линейных дизъюнктных неравенств к системе простых неравенств
1.6. Выводы
ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МЕТОДЫ НА ОСНОВЕ СТРАТЕГИИ УСТРАНЕНИЯ НЕВЯЗОК ДЛЯ РЕШЕНИЯ ЗАДАЧ НА СИСТЕМАХ ПРОСТЫХ ЛИНЕЙНЫХ НЕРАВЕНСТВ
2.1. Стратегия устранения невязок и ее использование для создания математической платформы для решения задач планирования
и диспетчеризации.
2.1.1. Существо стратег ии устранения невязок
2.1.2. Доказательство финитности стратег ии устранения
невязок
2.1.3. Градиентный метод для повышения скорости сходимости стратегии устранения невязок
2.1.4. Анализ скорости сходимости градиентного метода
2.1.5. Вариант реализации стратегии устранения невязок без неравенств 0блока
2.2. Задача линейного программирования.
2.3. Выводы
ГЛАВА 3. МАТЕМАТИЧЕСКИЕ МЕТОДЫ НА ОСНОВЕ СТРАТЕГИИ УСТРАНЕНИЯ НЕВЯЗОК ДЛЯ РЕШЕНИЯ ЗАДАЧ НА СИСТЕМАХ ЛИНЕЙНЫХ ДИЗЪЮНКТНЫХ НЕРАВЕНСТВ
3.1. Стратегия устранения невязок для решения задач на системах линейных дизъюнктных неравенств в вещественных числах
3.2. остроение модели времени счета задач на линейных дизъюнктных неравенствах
3.3. Задача оптимизации на системах линейных дизъюнктных неравенств, с приближенный подход
3.4. Статистически оптимальный алгоритм для задач линейных дизъюнктных неравенств
3.5. Использование стратегии устранения невязок для систем линейных дизъюнктных неравенств для решения целочисленных и булевых задач
3.6. Выводы.
ГЛАВА 4. РАЗРАБОТКА КОМПЛЕКСА ПРОГРАММ ДЛЯ
АВТОМАТИЗАЦИИ ИССЛЕДОВАНИЯ И РЕШЕНИЯ ЗАДАЧ, ФОРМАЛИЗУЕМЫХ СИСТЕМАМИ ЛИНЕЙНЫХ ДИЗЪЮНКТНЫХ НЕРАВЕНСТВ
4.1. Объектноориентированные технологии в автоматизации
прикладных задач.
4.1.1. Иерархия классов.
4.1.2. Диаграмма классов
4.2. Синтаксис спецификаций в форме БэкусаНаура
4.3. Реализация.
4.4. Примеры моделей задач практической реализации
4.4.1. Технологический процесс изготовления изделий на заводе крупнопанельного домостроения 1.
4.4.2. Технологический процесс изготовления плат
4.4.3. Задача раскроя материала.
4.5. Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Алгоритм для решения задач оптимизации с линейным функционалом и линейными ограничениями на основе стратегии устранения невязок. Метод для решения задач с Офаничениями в форме линейных дизъюнктных неравенств в вещественных числах па основе стратегии устранения невязок. Метод для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных дизъюнктных неравенств. Градиентный метод для повышения скорости сходимости стратегии устранения невязок для задач с линейными простыми и дизъюнктными ограничениями. Практическая значимость полученных результатов. Разработаны математические методы для решения задач оптимизации, формализуемых системами линейных простых и дизъюнктных неравенств. Разработано программное средство для решения одною варианта задачи оптимального раскроя и упаковки материала, позволяющее повысить точность раскроя на 5 фигур в сравнении с эвристическими методами за практически приемлемое время. На заводе крупнопанельного домостроения 1 г. Минск. На экспериментальноопытном заводе Политехник г. Минск. Минск. Связь работы с крупными научными программами. Разработка теоретических основ исчисления спецификаций сложных систем. Раздел II. Гос. ГБЦ Т1. Разработка программноматематического обеспечения для быстрого логического вывода в системах принятия решений реального времени. Гос. ГБЦ Т. Апробация работы. Результаты работы докладывались на й научнотехнической конференции Белорусского государственного технологического университета Минск, г. XXXV, XXXVIII научнотехнических конференциях аспирантов и студентов БГУИР Минск, , гг. Шестой межвузовской научнотеоретической конференции Человек. Цивилизация. Культура Международный гуманитарноэкономический институт, Минск, г. Международной школесеминаре по геометрии и анализу памяти Н. В. Ефимова АбрауДюрсо. Результаты изложены в 8 научных статьях, в 2 тезисах докладов конференций, в отчете о НИР. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из наименований и восьми приложений. В первой главе рассмотрены некоторые модели прикладных задач, записанные с помощью линейных дизъюнктных неравенств. Данный класс задач достаточно широк. В настоящее время задачи с дизъюнктными ограничениями решаются путем сведения к типовым задачам математического программирования. Показано, что сведением дизъюнктной задачи к типовым задачам, может быть получена более сложная задача. Таким образом, обоснована необходимость поиска собственных методов решения дизъюнктных задач, учитывающих их специфику. Во второй главе рассмотрена стратегия устранения невя зок СУ I I, как основа для разработки метода решения задач с дизъюнктными ограничениями. Проведено экспериментальное сравнение разработанных методов с известными методами математического программирования. Третья глава посвящена разработке математических методов для решения задач с ограничениями в форме линейных дизъюнктных неравенств. Рассмотрена возможность использования метода для решения задач с дизъюнктными ограничениями для решения булевых задач. Построена модель времени счета дизъюнктных задач. Разработан статистически оптимальный алгоритм для решения задач большой размерности на базе рассмотренных вариантов сведения дизъюнктной задачи к задаче о минимальном взвешенном покрытии. В четвертой главе рассмотрена разработка прог раммной платформы для исследования и решения задач, формализуемых системами линейных дизъюнктных неравенств, на основе соединения концепции объектноориентированного программирования и языка математических спецификаций. Также рассмотрены модели задач практической реализации. В заключении обобщены итоги и результаты проведенных исследований. В приложениях приведены примеры реализации методов, результаты сравнения программной реализации СУП для задач с офаничениями в виде линейных простых и дизъюнктных неравенств с коммерческими программами i x. СУП и алгоритма Харрис для систем линейных простых неравенств, документы, подтверждающие внедрение результатов диссертационной работы.