Разработка метода иерархии формальных грамматик и его применение в планировании ремонтов энергооборудования

• Автор: Штильман, Борис Михайлович
• Шифр специальности: 05.14.02, 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 184 c. : ил

СОДЕРЖАНИЕ ВВЕДЕНИЕ

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

1.1. Актуальность проблемы оптимального планирования ремонтов

1.2. Методы решения экстремальных задач методы оптимального планирования .

1.3. Оценки эффективности применяемых методов

1.4. Связь с проблематикой искусственного интеллекта. Алгоритм ПИОНЕР .

2. ЯЗЫК ТРАЕКТОРИЙ

2.1. Обзор метода.

2.2. Постановка задачи

2.3. Формальные грамматики . АЗ

2.4. Язык траекторий .

3. ЯЗЫК ЗОН
3.1. Траекторные сети и зоны
3.2. Свойства переводов
4. ЯЗЫК ПЕРЕВОДОВ
4.1. Семантика зоны.
4.2. Язык переводов
4.3. Язык управления
5. ПЛАНИРОВАНИЕ РЕМОНТОВ ЭНЕРГООБОРУДОВАНИЯ В ЭКСПЛУАТАЦИИ ЭНЕРГОСИСТЕМ
5.1. Плановопредупредительные ремонты
5.2. Заявка на ремонт. Ограничения
5.3. Критерии, методы и результаты планирования ремонтов.
6. ПРИМЕНЕНИЕ МЕТОДА В ЗАДАЧЕ МЕСЯЧНОГО ПЛАНИРОВАНИЯ РЕМОНТОВ. ПРОГРАММА ПИОНЕР
6.1. Опробование метода в шахматной игре. Программа ПИОНЕР. Аналогия моделей .
6.2. Месячное планирование ремонтов. Структура программы ПИОНЕР2
6.3. Реализация языка переводов в задаче месячного планирования
6.4. Результаты и перспективы применения метода
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Общих математических методов нахождения экстремумов функций любого вида при наличии произвольных ограничений не существует. Однако, для случаев, когда функционал и ограничения обладают определенными свойствами, разработаны ряд специальных методов, которые относятся к классу методов математического программирования. Если V/, о(-ь линейные функции, причем «{. Для ее решения разработаны различные методы, в частности, симплекс - метод, метод потенциалов. Если л/, о<-? Я ним относятся градиентные методы [I] , методы наискорейшего спуска, метод Билла и др. Учет ограничений в форме неравенств для линейной и нелинейной задач может быть выполнен с помощью приближенного метода - метода штрафных функций. Если условия операции описываются обыкновенными дифференциальными уравнениями, а Х«Х (О зависит от времени, то для поиска оптимального решения применяется метод Л. С. Понтряги-на Г]. Сюда же входят различные игровые задачи. Дискретные экстремальные задачи являются предметом исследования в настоящей работе. Для решения таких задач применяются методы регуляризации, комбинаторные и приближенные методы [] . Если получено нецелочисленное решение, то специальным образом добавляется новое ограничение задачи и снова проводится оптимизация и т. Итеративный процесс заканчивается при получении дискретного решения. Другой приближенный метод получения дискретного решения по непрерывному состоит в аппроксимации последнего дискретными планами. При этом используются различные комбинаторные методы. Именно такой подход применяется е разработанных ранее программах планирования ремонтов энергооборудования (см. Комбинаторные методы - это методы направленного перебора допустимых (по ограничениям) вариантов решений. Наиболее известными среди них являются динамическое программирование (] и метод ветвей и границ [] . B.C. Михалевичем разработан метод последовательного анализа вариантов (ПАВ), обобщающий эти методы. Рассмотрим вкратце подход Михалевича (следуя [,,]). Пусть надо найти экстремум функции W (V), заданной на множестве вариантов V . Опытом может служить вычислительная процедура, удовлетворение неравенства, суждение эксперта и т. Вводится оператор сужения S(^), который на каждом шаге сужает область возможных решений в зависимости от результата VL проведенного опыта яг («? Процедура решения заключается в последовательном проведении опытов и соответствующем сужении множества вариантов; в результате приходим к искомому оптимальному варианту. Ф (х ) достигает максимума. Рассмотрим начальный подвектор X'-(Xi? Х1},)Хе из заданного множества их значений. При этом X'- (*ен,. Х„) продолжение вектора х. Отметим, что если Х^б{0,1]- , то увеличение числа ? X' означает спуск по двоичному дереву. X' два начальных подвектора векторов X, и Х2 . Функционал Ф называется монотонно-рекурсивным, если из того, что Х/'гХ/ (продолжения совпадают) и Ф(х,')<Ф(х2) следует, что на полных векторах Ф(х,)< Ф(х2) . Обобщенный принцип оптимальности состоит в следующем. Пусть Ф - монотонно рекурсивный функционал и X' , Х2 - начальные подвектора векторов X, , Х2 (вектора X' , Х2 называют также частичными решениями). Если теперь Ф(хО $ Ф(х2), а множество всех продолжений X,' , входит в аналогичное множество для Х2 , то на X, максимум функционала Ф не достигается. Этот принцип позволяет отсеивать неперспективные частичные решения: если на нельзя достигнуть максимума, то х можно отбросить. В частности, такая ситуация имеет место в динамическом программировании (где монотонно-рекурсивный функционал является аддитивным функционалом). Здесь для любого частного решения его продолжение должно быть оптимальным. Поэтому из двух частичных решений X,' и Х'г "сходящихся в одной точке" (х,е=Ха), будет отброшено частичное решение с меньшим значением функционала. В случае метода ветвей и границ два частичных решения сравниваются "в целом" с точки зрения их возможных продолжений,и отбрасывается заведомо худший вариант. Разнообразные схемы перебора, объединяемые общим названием "метод ветвей и границ", являются частным случаем ПАВ. Основные этапы построения и отсева вариантов, конкретизируются следующим образом.