Содержание к диссертации
Введение
Глава I. Основные концепции построения диалоговых процедур разработки и реализации оптимизационных задач 12
1.1. Проблемы автоматизации в городском хозяйстве. Состав и функции АСУ "Город". Постановка задачи исследования 12
1.2. Анализ и классификация экономико-математических моделей и методов их реализации на ЭВМ 27
1.3. Требования к структуре и функциональным характеристикам системы разработки и реализации оптимизационных задач в АСУ 44
Глава 2. Построение информационной модели и языковых средств реализации диалоговых процессов решения оптимизационных задач 60
2.1. Общие принципы построения диалога при реализации оптимизационных задач 60
2.2. Представление и реализация информационных моделей диалогового процесса разработки и реализации оптимизационных задач 65
2.3. Язык описания сценариев диалоговых процессов 78
Глава 3 . Методы реализации на ЭВМ экономико-математических моделей оптимизационных задач 95
3.1. Организация библиотеки экономико-математических методов системы со структурной адаптацией 95
3.2. Эвристический метод решения одного класса оптимизационных задач, приводящихся к моделям целочисленного линейного программирования 109
3.3. Оценка эффективности и экспериментальное исследование алгоритма решения задач, приводящихся к моделям ЦЛП 122
Глава 4. Методы реализации диалоговой системы разработки и решения оптинизационных задач в АСУ 131
4.1. Программная организация диалоговой системы разработки и реализации задач 131
4.2. Диалоговый процесс разработки и реализации комплекса оптимизационных задач планирования 140
4.3. Схема реализации оптимизационных задач в АСУ на основе диалоговой системы 150
4.4. Оценки влияния внедрения оптимизационных задач на научно-технический уровень и экономическую эффективность АСУ 161
Заключение 173
Литература 175
- Проблемы автоматизации в городском хозяйстве. Состав и функции АСУ "Город". Постановка задачи исследования
- Общие принципы построения диалога при реализации оптимизационных задач
- Организация библиотеки экономико-математических методов системы со структурной адаптацией
- Программная организация диалоговой системы разработки и реализации задач
Введение к работе
В материалах ХХУІ съезда КПСС и последующих решениях Коммунистической партии и Правительства подчеркивается необходимость всемерного ускорения научно-технического прогресса, вывода всех отраслей народного хозяйства на передовые рубежи науки и техники. Поистине революционные возможности предоставляет для этого использование средств вычислительной техники и экономико-математических методов в рамках автоматизированных систем управления во всех сферах деятельности народного хозяйства, включая такую область,как городское хозяйство.
Управление городским хозяйством и городом в целом реализуется в рамках интегрированной, многоотраслевой, иерархической системы управления - АСУ "Город", представляющей собой комплекс взаимоувязанных систем управления, включающий общегородские, районные, межотраслевые, отраслевые АСУ, АСУ предприятиями и объединенитли, АСУ технологическими процессами и производством. Эффективность функционирования такой комплексной системы управления во многом определяется согласованностью и оптимальностью процессов планирования и управления, направленных на повышение эффективности функционирования народного хозяйства, рациональное использование материальных, трудовых и финансовых ресурсов.
Важнейшим направлением повышения эффективности АСУ является разработка и внедрение комплексов оптимизационных задач, предназначенных для получения оптимальных (или рациональных) планов и управляющих воздействий.
Вопросы разработки методов оптимизации и внедрения их в различные АСУ нашли отражение в фундаментальных работах В.М. Глушкова, Н.Н. Моисеева, B.C. Михалевича, Г.С. Поспелова ДБ. Сергиенко, Д.Б. Юдина ж ряда других специалистов.
Полученные теоретические и практические результаты позволили выявить те проблемы, с которыми встречаются разработчики АСУ при проектировании и внедрении оптимизационных задач. Среди них следует отметить: сложность построения экономико-математических моделей, адекватных процессам планирования и управления, трудности в реализации оптимизационных алгоритмов на ЭВМ (объемно-временные, точностные и надежностные характеристики), а также необходимость учета "человеческих факторов" при внедрении оптимизационных методов в практику работы планирующих и управляющих органов.
Указанные проблемы определяют необходимость дополнительных исследований в части повышения адекватности построения экономико-математических моделей, методов реализации оптимизационных алгоритмов, разработки и реализации комплексов опттжзационных задач в АСУ на основе специализированных инструментальных средств, функционирующих в режиме диалога человек - ЭВМ.
Все вышеперечисленные факторы определяют актуальность и научно-практическую ценность исследований по разработке и внедрению диалоговых процедур реализации опттжзационных задач в АСУ.
Выполнение диссертационной работы проводі/їлось в рамках комплексной целевой програти ГКНТ СССР 0.80.23 "Создать и ввести в действие комплекс взаимоувязанных автоматизированных систем управления хозяйством г.Москвы - комплекс АСУ "Москва" и комплексной программы работ Минприбора СССР от 01.07.80 "Совершенствование планирования и управления отраслью на основе АСУ-Прибор".
Цель работы состоит в исследовании и разработке методов, алгоритмов и программных средств реализации оптш.шзационных задач АСУ в режиме диалога человек - ЭВМ и внедрения их в составе АСУ различного уровня и назначения.
Содержание работы составляют четыре главы.
В первой главе рассматриваются концепции построения диалоговых процедур разработки и реализации оптимизационных задач в АСУ. Определяются основные проблемы автоматизации в городском хозяйстве, состав и функции АСУ "Город". Проводится анализ используемых оптимизационных задач в АСУ городского хозяйства и соответствующих им экономико-математических моделей и методов реализации, на основании которого обосновывается необходимость разработки специализированных инструментальных языковых и программных средств, функционирующих в режиме диалога человек - ЭВМ. Рассматриваются основные функциональные процедуры разработки и реализации оптимизационных задач. Определяются основные общесистемные и функциональные требования к рассматриваемой диалоговой системе. Проводится формализация диалогового процесса при решении задач, определяется информационная структура системы. Рассматривается состав комплекса программных и языковых средств, реализующих информационную структуру. Приводится перечень рабочих, сервисных, контролирующих и эволюционных функций системы. Обосновывается обобщенная структура диалогового процесса разработки и реализации оптимизационных задач в АСУ.
Вторая глава посвящена вопросам построения информационной модели и языковых средств реализации диалоговых процедур разработки оптимизационных задач. Проводится обзор разработанных диалоговых систем и на его основе формулируются требования к диалоговым средствам системы. Производится построение информационной модели диалогового процесса, рассматриваемого в виде процедуры, реализующей обмен сообщениями между пользовате лем и системой. Проводится формализация информационной модели в виде графа диалогового процесса (ГДП). Определяются основные свойства ГДП и формируются процедуры анализа и композиции информационных моделей. Вводится язык описания сценариев диалога. Рассматриваются основные типы вершин ГДП. Для каждого типа вершин определяется вид элементарного оператора и его синтаксическая конструкция. Приводится представление операторов языка описания сценариев в виде бланков входного языка, заполняемых пользователем. Рассматриваются основные алгоритмы обработки операторов языка и формирования сценария. Приводится структура каталога сценариев диалога и алгоритмы функционирования диалоговой программы, представляющей собой набор параметрических процедур. Определяется набор команд языка, обеспечивающих реализацию сервисных функций системы.
В третьей главе рассматриваются методы реализации на ЭВМ оптимизационных задач. Приводятся принципы организации и алгоритмы функционирования библиотеки методов реализации экономико-математических моделей со структурной адаптацией, обеспечивающей автоматический выбор наилучшего с точки зрения заданных критериев алгоритма. Рассматривается задача выбора состава алгоритмического обеспечения комплексов оптимизационных задач в АСУ, которая формализуется в виде многокритериальной задачи целочисленного линейного программирования. Для решения данной задачи производится построение алгоритма и итерационной диалоговой процедуры. Предлагается приближенный метод решения оптимизационных задач, приводящихся к моделям целочисленного линейного программирования большой размерности. Проводится оценка эффективности предложенного алгоритма и его экспериментальное исследование. Предлагается метод получения абсолютной оценки точностной эффективности приближенных алгоритмов по верхней границе значения оптимума целевого функционала.
Четвертая глава посвящена вопросам реализации диалоговой системы разработки и решения оптимизационных задач в АСУ. Определяются состав, структура, программная организация и алгоритмические основы функционирования системы. Приводится пример реализации средствами системы диалогового процесса разработки и решения комплекса оптимизационных задал планирования. Рассматривается схема реализации оптимизационных задач в системе, обеспечивающая последовательно этапы формирования модели, выбора метода решения, генерации основных проектных решений и непосредственно реализации оптимизационных задач в АСУ. Проводится анализ влияния внедрения системы на научно-технический уровень АСУ. Рассматриваются факторы, определяющие экономическую эффективность использования системы на общегородском, межотраслевом, отраслевом уровнях АСУ городского хозяйства, а также в АСУ предприятий.
Диссертация состоит из 131 страницы основного текста, содержит 34 рисунка, 10 таблиц, библиографию из 109 названий и 7 приложений (общий объем диссертации - 243 стр.).
Разработанные инструментальные средства реализации оптимизационных задач в АСУ ориентированы на широкий круг пользователей и обеспечивают в диалоговом режиме функции разработки экономико-математических моделей для различных объектов управления, выбор метода реализации модели на ЭВМ, проведение экспериментальных исследований модели и метода, получение основных проектных решений по программно-математическому и информационному обеспечению, и реализацию комплексов оптимизационных задач в АСУ. Разработанные языковые и программные средства могут быть использованы в качестве средств исследования, проектирования и реализации оптимизационных задач в АСУ различного уровня и назначения.
Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: 2-й Всесоюзной конференции "Управление большим городом" (г.Москва, 1983 г.); "Всесоюзном семинаре "Проблемы создания и развития автоматизированных систем, научных исследований коллективного пользования в городском хозяйстве" (г.Москва, 1983 г.); Всесоюзной научно-технической конференции "Программное обеспечение АСУ" (г.Калинин, 1983 г.); Научно-техническом семинаре "Опыт разработки и внедрения АСУ в ПО и предприятиях отрасли на базе использования современных методов проектирования" (г.Харьков, 1983 г.); Московской городской конференции "Информатика, вычислительная техника, автоматизация в науке и технике, в народном хозяйстве" (г.Москва, 1983 год); Всесоюзном семинаре "Применение методов экономико-математического моделирования, комплексного анализа и прогнозирования, экономического и социального развития города в автоматизированных системах планирования" (г.Москва, 1984 г.); 3-м совещании молодых ученых и специалистов по "Проблемам кибернетики, вычислительной техники и автоматизации" (г.Москва, 1984 г.); научно-техническом семинаре "Применение экономико-математических методов в управлении городом" (г.Москва, 1984 год).
Результаты диссертационной работы использованы при разработке второй очереди комплекса АСУ "Москва, разрабатываемого в соответствии с целевой комплексной программой ГКНТ СССР 0.80.23 (ГлавСистем НПО АСУ "Москва, ИВЦ "Мосжилуправление", ВЦІШ "Здравоохранение") при разработке систем организационного управления и АСУ организаций Минприбора (ВНИИоргтехника, Харьковский завод "Оргтехника", Московский завод "Сакко и Ванцетти"), а также в ряде других организаций. Суммарный эко номический эффект от внедрения диссертации составляет более 80,0 тыс.рублей.
По теме диссертации опубликовано 12 печатных работ.
Проблемы автоматизации в городском хозяйстве. Состав и функции АСУ "Город". Постановка задачи исследования
Основной задачей экономической политики партии и правительства на современном этапе является, как указано в; решениях ХХУІ съезда КПСС, рост благосостояния советского народа,дальнейшее повышение эффективности производства и качества работы во всех звеньях народного хозяйства. Важнейшие условия решения этой задачи - совершенствование форм и методов руководства экономикой и в первую очередь планирования и управления.
Немаловажное значение в формировании экономики социалистического общества имеют города. В настоящее время в городах проживает 62% населения страны [б J . Здесь сосредоточена большая часть основных фондов народного хозяйства. В процессе интенсификации и концентрации производства роль городов возрастает, усложняется их хозяйственная структура.
Под городом как объектом управления принято понимать сложную социально-экономическую систему, представляющую собой территориальный комплекс, состоящий из тесно взаимодействующих элементов. Народное хозяйство города - это комплекс предприятий, организаций и учреждений градообразующих и градообслужи-вающих отраслей, строения, сооружения, сети и коммуникации города, городская территория и окружающая среда, обеспечивающие функционирование, сохранение и развитие города как социально-экономической системы и удовлетворяющие потребности социально-экономической системы более широкой, чем город (регион, республика, страна в целом). Все выше сказанное в наибольшей степени относится к столице СССР-г.Москве. Для управления таким сложным, многоотраслевым, динамичным хозяйством как город, должна быть создана эффективная система управления, важное место в которой отводится АСУ "Город" (для г.Москва - комплекс АСУ "Москва" [з] ), призванному обеспечить условия для комплексного социального и экономического планирования и управления развитием города. Совершенствование организационной системы городского планирования и управления осуществляется по четырем основным направлениям (компонентам города); градообразующая основа (отрасли промышленности), население и трудовые ресурсы, градообслуживающий комплекс (отрасли городского хозяйства), окружающая среда (экология). Таким образом, с позиций системного подхода город является большой открытой социально-экономической системой и должен рассматриваться как сложный, состоящий из множества взаимосвязанных элементов, объект управления, социально-экономическое развитие которого регулируется организационно-распорядительными и экономико-математическими метода - 14 ми управления. Рациональное (оптимальное - при заданном критерии и ограничениях) решение задач экономического и социального развития города в условиях располагаемых ресурсов, обуславливает необходиглость координации, руководства и регулировашш производственно-хозяйственной деятельности, т.е. осуществления комплексного социально-экономического планирования и управления городом как относительно обособленным объектом с использованием определенной технологии, методов и средств, объединенных в единую систему управления. Создание такой системы управления предполагает широкое использование экономико-математических методов, средств вычислительной техники и связи.
При комплексном рассмотрении организационных проблем создания общегородской системы планирования и управления необходимо учитывать внешние ограничения (ресурсные и временные),которые будут накладываться на все подсистемы города. Это потребует определенной согласованности и пропорций в развитии подсистем, поэтому решение общегородской проблемы планирования и управления необходимо рассматривать по двум главным взаимосвязанным направлениям: общее совершенствование городского социально-экономического планирования и автоматизации процессов планирования и управления.
По характеру общественного разделения труда и участия в создании совокупного общественного продукта и национального дохода, в хозяйственной сфере большого города выделяют три группы отраслей: материального производства (производственные); производство услуг (непроизводственные), смешанные, т.е. выполняющие как производственные, так и непроизводственные функции. Причем каждая отрасль должна рассматриваться как составная часть соответствующей народнохозяйственной отрасли» Так, в Москве представлены практически все отрасли материального производства, относящиеся к той или иной отрасли промышленности в соответствии с народнохозяйственной номенклатурой отраслей. Непроизводственные отрасли Москвы складываются из городских сфер нематериального производства (жилищно-коммунальное обслуживание, здравоохранение, физическая культура, социальное обеспечение, просвещение, культура и искусство, наука и научное обслуживание, кредитование и госстрах, партийные и общественные организации, планирование и управление). К смешанным отраслям относятся городские предприятия: транспорта (обслуживающего население города), связи, торговли, общественного питания и др. Как правило, такие отрасли имеют двойное подчинение.
Большая часть предприятий, учреждений и организаций непроизводственной сферы объединяется понятием городское хозяйство социалистического города, в которое входят также предприятия, выполняющие как производственные, так и непроизводственные функции градообслушшающего комплекса. Отрасли городского хозяйства Москвы тесно взаимосвязаны в процессе функционирования со всеми предприятиями, учреждениями и организациями градообразующей основы.
Большие масштабы и сложность многоотраслевого хозяйства Москвы, необходимость повышения эффективности общественного производства выдвигают требование взаимной увязки перспектив развития каждой отдельной отрасли с перспективами развития городского хозяйства. Поэтому совершенствование планирования развития Москвы требует всестороннего учета общественно-политических, социальных, экономических, экологических, градостроительных и других факторов. В связи с этим одной из главных задач совершенствования организационной системы планирования социально-экономического развития Москвы является определение основных направлений и показателей плана, которые были бы приме - 16 ниш на всех стадиях социально-экономического планирования. Это, в свою очередь, потребует решения большого количества оптимизационных, плановых и учетных задач, а следовательно, и привлечения больших вычислительных мощностей ЭВМ для проведения расчетов.
Общие принципы построения диалога при реализации оптимизационных задач
Как было рассмотрено в 1.3. одним из основных требований, предъявляемых к системе решения оптимизационных задач, является требование реализации ее как диалоговой системы. В основе всякого диалога лежат средства коммуникации между пользователем и системой, возможности которых во многом определяют оперативность, гибкость и универсальность диалогового режима. Эффективность функционирования диалоговой системы определяется группой факторов, основными из которых являются: 1. Концепция построения диалоговых процессов, т.е. требование, чтобы структура диалогового процесса и его возможности в наибольшей степени соответствовали требованиям проблемной области, методологии моделирования и решения задач. 2. Принципы построения и возможности языковых средств диалога, т.е. средств, с помощью которых пользователь может создавать и реализовывать сценарии диалога с ЭВМ. 3. Методы реализации диалоговых программ. Для определения общих принципов построения рассматриваемой диалоговой системы предварительно проведем обзор и анализ прин пдпов построения диалоговых систем (ДС).
Входные языки диалоговых систем могут быть разделены на три вида: директивный, близкий к естественному, типа алгоритмического. директивный входной язык предусматривает использование предварительно разработанного сценария диалога, учитывающего все возможные ответы пользователя на заранее предписанную последовательность вопросов системы. Ответом пользователя обычно является один из предложенных альтернативных вариантов ведения диалога. Эти системы называются системами с жесткой логикой [ 77, 79, 82, 83 J . Ответы пользователя задаются либо на специальном языке (возможно, включающем конструкции естественного языка), либо на языке "кнопок" (в частности световых).
Диалоговые системы с директивным входным языком имеют наиболее широкое распространение.
В системе ИНЭО-2 [іОЗ, 105 J программы пишутся пользователем на языке описания сценария диалога. Этот язык представляет средства описания операций ввода и вывода информации на дисплей, обработки символьной информации, выполнения обращений к программам, а также для условных и безусловных передач управления.
Систему ЙНЭС-2 можно рассматривать как систему с директивным входным языком, включающим конструкции естественного языка.
К этому же классу можно отнести диалоговую интерпретирующую систему автоматизации моделирования - ДИСАМ [_91, 94J , которая позволяет реализовать на ЭВМ модели объектов, составленных по модульному принципу.
В ряду диалоговых систем с директивным входным языком, включающим конструкции естественного языка следует отметить систему СПОК [931 - систему программирования и поддержания обслуживающих и обучающих курсов, которая является пакетом прикладных программ специального назначения и представляет собой диалоговую систему реального времени, реализующую для обслуживания пользователей режим разделения времени. функциональные возможности системы СПОК использованы в ряде других диалоговых систем, например, в системе ПРОЛОГ-ЕС [9 ЗІ.
Система ДШРОзЮР [94] , предназначена для обеспечения диалогового программирования на Фортране под управлением ЭВМ. Система ДИПЮОР ориентирована на совместное программирование громоздких формульных вычислений, процедур принятия решений в инженерном проектировании и т.д. Эта система является обучающе-решающей системой для программирования алгоритмов реализации определенных задач на языке Фортран. Главной частью такой системы является общий человеко-машинный мета-алгоритм (MA), т.е. алгоритм для построения частных алгоритмов решения определенного класса задач. Мета-алгоритм по своей структуре представляет собой граф, вершинами которого служат либо номера вопросов и команд, выдаваемых пользователю, либо номера программ автоматизации действий по конструированию алгоритмов решения задач данного класса.
В диалоговой системе ПИОНЕР [ 105 ] реализован командно-ориентированный язык общения (язык директив). Все допустимые в текущий момент директивы или команды система сама выдает на экран дисплея в форме текстовых строк.
К системам с входным языком типа алгоритмического можно отнести ДИСУС [ 94J - диалоговую систему управления структурами многомодульных комплексов. Следует оговориться, что использование алгоритмического языка как входного находит сегодня все меньше применения, т.к. это доступно лишь пользователям, владеющим основами программирования.
Теоретические исследования систем с входным языком близким к естественному, ведутся в двух направлениях. Первое из них связано с построением всеобъемлющей лингвистической модели языка и с реализацией этой модели на ЭВМ. Второе направление - исходит от формальных или психологических моделей порождения естественного языка.
Система ДИЛОС [94І - диалоговая информационно-логическая система, предназначена для использования в качестве интеллектуального посредника между конечным пользователем и традиционными средствами вычислительной системы при решении прикладных задач.
Система ДИЛОС представляет собой универсальную диалоговую систему, базирующуюся на использовании входного естественного языка и базы знаний. Важнейшей ее особенностью является наличие базы знаний, воплощенной в виде содержимого "модельной базы данных" (МВД) и "главной базы данных" (ГБД).
К диалоговым системам с входным языком, близким к естественному, можно отнести систему ДИСПУТ [90, 91 ] - диалоговую информационно-справочную систему, предназначенную для использования при планировании и управлении в транспортных системах.
Анализ диалоговых систем, имеющих различные входные языки, показывает, что их можно разделить на два типа: системы с фиксированным сценарием диалога; самообучающиеся системы.
Сценарий для систем первого типа предварительно описывается в виде схемы решения задачи и реализуется с помощью мета-алгоритма (МА) описания диалоговых процессов (ОДП) или другого аналогичного инструмента. В рамках этого сценария пользователь обладает большой свободой в формулировке запросов, в задании промежуточных и окончательных целей.
Самообучающиеся - это те системы, в которых на основании заранее разработанного диалога проводится порождение новых процедур по типу старых. Генерация этих процедур производится с последующим подключением в состав обеспечивающих программ системы и базы знаний.
Кроме рассмотренных выше диалоговых систем общего назначения необходимо рассмотреть проблемно-ориентированные диалоговые системы. ШШ "Вариантные расчеты годовой производственной программы на линейных оптимизационных моделях в режиме диалога" (ШШ "С0ЛМЇЇ ЕС") [90, 105] предназначен для формирования матриц экономико-математических моделей (ЭММ) оптимального планирования и ведения вариантных расчетов в режиме диалога. Пакет реализует модели, математически-приводимые к задаче линейного программирования, что позволяет, с одной стороны, определить вариант плана, отвечающий требованиям выбранного критерия оптимизации при заданных ограничениях, а, с другой стороны, производить вариантные расчеты при различных изменениях исходных данных. ШШ "СОЛМИ ЕС" представляет собой пакет, в банк моделей которого заложены описания ЭММ определения годовой производственной программы промышленного предприятия. Построение пользователем і конкретной модели сводится к модификации ЭММ, заложенных в банк моделей, в соответствии с постановкой задачи и наличием информации.
Организация библиотеки экономико-математических методов системы со структурной адаптацией
В соответствии с обобщенной алгоритмической структурой диалогового процесса проектирования одним из основных этапов ДП после построения и параметризации модели является этап выбора эффективного метода реализации модели на ЭВМ, который во многих случаях может рассматриваться как процедура многокритериального выбора. Необходимость решения данной проблемы определяется следующими факторами:
I. Как было показано в 1.2 модели оптимизационных задач приводятся к достаточно широкому классу экономико-математических методов - линейное программирование, методы теории расписаний, целочисленное линейное программирование, нелинейное прог-раммирование, расчетные алгоритмы. Это определяет необходшлость в процессе параметризации модели приведения ее к одному из классов экономико-математических методов.
2. Анализ методов одного и того же класса показывает, что их можно условно разделить на две грушш: группа методов, характеристики которых инвариантны (либо линейнозависимы) от параметров модели (число переменных, размерность, структура входных данных, точность решения и т.д.) и характеристик ЭВМ (объем памяти, быстродействие), и группа методов, характеристики эффективности которых нелинейны относительно параметров модели и характеристик ЭВМ (см. 1.2).
3. Учет эргатических факторов функционирования диалоговой системы (как человеко-машинной системы) определяет требования ко времени формирования реакции системы в процессе ДП, что накладывает временные ограничения на характеристики функционирования алгоритмов.
Эти требования определяют принципы построения и алгоритмы функционирования библиотеки ЭММ системы.
Библиотека ЭММ системы содержит набор алгоритмов (и реализующих их программ) и архив и обладает структурной адаптацией, т.е. обеспечивает автоматическое варьирование структуры программного обеспечения для реализации наилучшего для решаемой задачи алгоритма. Структурная адаптация осуществляется на основе анализа архива, содержащего сведения о характеристиках эффективности функционирования алгоритмов относительно реализуемых моделей.
Множество ситуаций С библиотеки строится с помощью системы признаков, позволяющей определить состояние оптимизируемого объекта. Такими признаками являются характеристики оптимизационной задачи (специфические для каждого класса), которые определяют ситуацию среды (С С ), и харакреристики очередного рабочего шага, определяющие ситуацию алгоритма (GA). Ситуация С С представляет собой объединение ситуации среды и алгоритма и ог - 99 -раничений диалоговой системы (СД), т.е. С ССи САиСЗ) (3.5) Ситуация среды СС строится с помощью следующей системы признаков: наличие у задачи нескольких целевых функций; наличие ограничений типа равенств (неравенств); наличие линейных (нелинейных) ограничений; непрерывность функций fi, с = , 2.f,.., /Ч- Яч- L ; линейность функций ft ; нелинейность функций fi (выпуклость, вогнутость); принадлежность функций fl к классу С fit) , где ьс область определения fith l, ; наличие начального приближения -X ; наличие эргатических ограничений. Ситуация СС является исходной информацией и в ходе решения задачи ее значение не изменяется. Ситуация алгоритма СА характеризует очередной рабочий шаг выбора метода с помощью следующей системы признаков: близость текущей точки к экстремуму целевой функции; близость текущей точки к границе области допустимых значений; близость к расчетному значению. Список характеристик СА может быть увеличен. Значение субвектора СА в некоторой точке -А вычисляется с помощью функций диагностики ситуации га : X - с . При этом используется численная характеристика среды, в которой происходит оптимизация, определяемая как частота неулучшения (X) показателя качества в некотором кубе пространства R с центром в точке X:
Для успешного решения широкого класса оптимизационных задач набор алгоритмов А должен быть достаточно велик и разнообразен. Но тогда трудно априорно указать правило выбора основании которого осуществлялся бы выбор (переключение) алгоритмов с целью обеспечить эффективное отыскание решения. Поэтому производится корректировка правил выбора введением в библиотеку некоторого набора оценочных критериев / ( ct х ).
Каждый из описанных выше оценочных критериев представляет собой функцию, определенную на конечном множестве пар ( с, о.). Поэтому для каждого оценочного критерия строится матрица оценочных коэффициентов Р, обеспечивающая построение функции выбора г& . Элемент pCCL матрицы Р представляет собой "вес" алгоритма а. в ситуации с - характеристику эффективности. Чем больше "вес" алгоритма в данной ситуации, тем эффективней он работает, поэтому функция выбора ставит в соответствие каждой ситуациисєС некоторый алгоритм а. А , наилучшим образом работающий (по введенным оценкам) в данной ситуации: f$(c)=OL, где О- - номер алгоритма такой, что /)са pea. , VOL Ф а . Функция выбора корректируется после решения каждой задачи. Таким образом, в процессе функционирования вырабатываются наилучшие средние показатели эффективности для автоматического выбора алгоритмов.
Программная организация диалоговой системы разработки и реализации задач
В соответствии со структурой системы, рассмотренной в гл.1, программные средства системы состоят из двух частей 64,66J : средства диалога и средства библиотеки реализации задач со структурной адаптацией, функционирующих под общим управлением. Средства диалога функционируют в следующих режимах: - создание сценария ДП и запись его в каталог; - работа с ДП (разработка и решение задач в диалоговом режиме); - обслуживание каталога сценариев (ввод, коррекция, исключение, просмотр); - сервисные функции.
Структура функций средств диалога представлена на рис. 26, а схема программной реализации на рис.27. Программно-диалоговая система [98,1021 представляет собой совокупность за грузочных модулей, работа которых реализуется динамическим вызовом их из исполнительной библиотеки. В состав библиотеки входят: 1) Программа загрузки и настройки ДС. Она обеспечивает настройку пользовательских программ для работы с системой,выбор терминальных устройств и загрузку в основную память управляющей (основной) программы. 2) Управляющая программа (находится в основной памяти в процессе сеанса диалога). В ее состав входят следующие модули: - модуль загрузки в память программ, обеспечивающих все режимы функционирования ДС; - модуль, осуществляющий обмен информацией между пользователем и экраном терминала; - модуль синтаксического анализа команд диалогового языка, с помощью которых ведется диалог; 3) Программа инициализации сценария ДП. В ее состав вхо дят следующие модули: - модуль инициализации каталога, производящий инициализацию записей оглавления каталога, дорожек на носителях памяти прямого доступа для записей содержимого каталога и формирование служебной записи состояния каталога; - модуль семантического и синтаксического анализа сценария ДП, введенного пользователем, для последующей записи его в каталог сценариев ДП. Этим же модулем обеспечивается формирование записей ДП в соответствии с его логической структурой; - модуль записи сценариев ДП в каталог. Одновременно производится формирование записи оглавления каталога, соответствующей введеиному сценарию ДП, и модификация служебной информации каталога; 4) Программа диалога с пользователем, загружаемая в про цессе выполнения данного режима работы с ДП и удаляемая из памяти по окончании работы в этом режиме. Диалог реализуется пошаговой обработкой вершин вызванного сценария ДП (со всеми коррекциями и командами пользователя). При этом производится накопление данных (значений переменных) в служебный файл системы, вычисление по этим данным значений арифметических и логико-арифметических выражений (в альтернативных вершинах), выполнение пользовательских прикладных программ. Результаты выполнения программ пользователя можно посмотреть на экране после их завершения. Весь ход ДП заносится в последовательный файл-копию. Работа с копией ДП осуществляется в тех случаях, когда необходимо продолжить прерванный на время ДП или пересмотреть результаты работы на более ранних шагах ДП. 5) Программа обработки каталога ДП, состоящая из следующих модулей: - модуль обработки команд пользователя; - модуль операций обработки каталога. Данный модуль обеспечивает выполнение следующих операций: - чтение оглавления (просмотр номеров и названий ДП, записанных в каталог); - чтение вершин ДП в физической последовательности (по возрастанию номеров вершин), т.е. в последовательности их записи в каталог в процессе инициализаций; - чтение вершины ДП в логической последовательности, т.е. в той последовательности, в какой вершины имеют ссылки одна на другую; - чтение любой вершины указанного ДП; - корректировка описания вершины ДП; - удаление описаний вершин ДП; - удаление сценариев ДП; - фактическая реорганизация (сжатие) каталога; - дозапись сценария ДП. 6) Программа синтаксического и семантического анализа операторов языка описания ДЕІ. Данная программа состоит из следующих модулей: - модуль синтаксического анализа структуры ДП. Данный модуль обеспечивает контроль правильности информационной модели ДЦ, представленной в виде графа ДП, на соответствие правилам, введенным в 2.2; - модуль оценки характеристик ДП. Данный модуль производит подсчет некоторых характеристик информационной модели (графа) ДП (число вершин, число путей, длина путей и т.д.), а также реализует алгоритм определения изоморфности вводимого графа ДП по сравнению с ранее введенными в каталог описаниями ДП. 7) Библиотека экономико-математических моделей оптимиза ционных задач. Данная библиотека состоит из двух частей [бсЦ [100] : - описание и математическая формулировка модели; - системный архив характеристик моделей, в котором хранятся параметры ЭММ, не формируемые пользователем в процессе диалога. Библиотека оформлена средствами операционной системы ЭВМ и представляет совокупность разделов, каждый из которых соответствует одной ЭММ. 8) Библиотека исполнительных программ. В данную библио теку пользователем заносятся исполнительные программы, ис пользуемые для обработки информации и принятия решений в про цессе ДП. Библиотека также организована средствами операцион ной системы ЭВМ.
