Лекция 7. Формальные методы

(МФПС, Методы формализованного представления сиcтем)

В данном лекции принята и кратко характеризуется классификация Ф.Е. Темникова, в которой выделяются следующие обобщенные группы (классы) методов (табл. 2.1):

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

статистические (включающее и теоретические разделы математики - теорию вероятностей, математическую статистику, и направления прикладной математики, использующие стохастические представления - теорию массового обслуживания, методы статистических испытаний (основанные на методе Монте-Карло), методы выдвижения и проверки статистических гипотез А. Вальда и другие методы статистического имитационного моделирования);

теоретико-множественные;

логические;

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

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

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

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

Таблица 2.1

Класс методов	Содержание методов	Применение методов
Аналитические	Аналитическими названы здесь методы, в которых ряд свойств многомерной, многосвязной системы (или какой-либо ее части) отображается о n-мерном пространстве одной единственной точкой, совершающей какое-то движение. Это отображение осуществляется либо с помощью функции f(S_x), либо посредством оператора (функционала) Ф[S_x]. Можно также две или более системы либо их части отобразить точками и рассматривать взаимодействие этих точек, каждая из которых совершает какое-то движение, имеет свое поведение. Поведение точек и их взаимодействие описываются аналитическими закономерностями. Основу понятийного (терминологического) аппарата составляют понятия классической математики и некоторых новых ее разделов (величина, функция, уравнение, система уравнений и т. п.). На базе аналитических представлений воз никли и развиваются математические теории различной сложности — от аппарата классического математического анализа (методов исследования экстремумов функций, вариационного исчисления и т. п.) до таких разделов современно» математики, как математическое программирование (линейное, нелинейное, динамическое и т. п.). теория игр (матричные игры с чистыми стратегия ми, дифференциальные игры).	Применяются в тех случаях, когда свойства системы можно отобразить с помощью детерминированных величин или зависимостей, т. е. когда знания о процессах и событиях в некотором интервале времени позволяют полностью определить поведение их вне этого интервала. Эти методы используются при решении задач движения и устойчивости, оптимального размещения, распре деления работ и ресурсов, выбора наилучшего пути, оптимальной стратегии поведения в конфликтных ситуациях и т. п. Математические теории, развивающиеся на базе аналитических представлений, явились основой ряда прикладных теорий (теории автоматического управления, теории оптимальных решений и др.): При практическом применении аналитических представлений для отображения сложных систем следует иметь в виду, что они требуют установления всех детерминированных взаимосвязей между учитываемы ми компонентами и целями системы в виде аналитических зависимостей. Для сложных многокомпонентных, многокритериальных систем получить требуемые аналитические зависимости очень трудно. Более того, если даже это и удастся, то практически невозможно доказать правомерность применения этих аналитических выражений т. е. адекватность модели рассматриваемой задаче.
Статистические	В тех случаях, когда не удается представить систему с помощью детерминированных категорий, можно применить отображение ее с помощью случайных (стохастических) событий, процессов, которые описываются соответствующими вероятностными {статистическими) характеристиками и статистическими закономерностями. Статистические отображения системы в общем случае (по аналогии с аналитически ми) можно представить как бы в виде «раз мытой» точки (размытой области) в n-мерном пространстве, в которую переводит систему (ее учитываемые свойства) оператор Ф[S_x]. «Размытую» точку следует понимать как некоторую область, характеризующую движение системы (ее поведение); при этом границы области заданы с некоторой вероятностью («размыты») и движение точки определяется некоторой случайной функцией, Закрепляя все параметры, кроме одного, можно получить срез по линии а—b, физический смысл которого — воздействие данного параметра на поведение системы, что можно описать статистическим распре делением по этому параметру. Аналогично можно получить двумерную, трехмерную и т. д. картины статистического распределения. На статистических отображениях базируются теории математической статистика, теория статистических испытаний или статистического имитационного моделирования (частным случаем которой является метод Монте-Карло), теория выдвижения и проверки статистических гипотез (частным случаем которой является байесовский подход к исследованию процессов передачи информации в процессах общения, обучения и других ситуациях, характерных для сложных развивающихся систем).	Статистические отображения позволили расширить области применения ряда дисциплин, возникших на базе аналитических представлений. Так возникли статистическая теория распознавания образов, стохастическое программирование, новые разделы теории игр и др. На базе статистических представлений возникли и развиваются та кие прикладные направления, как теория массового обслуживания, теория статистического анализа и др. Расширение возможностей отображения сложных систем и процессов по сравнению с аналитическими методами можно объяснить тем, что при применении статистических представлений процесс постановки за дачи как бы частично заменяется статистическими исследованиями, позволяющими, не выявляя все детерминированные связи между изучаемыми событиями или учитываемыми компонентами сложной системы, на основе выборочного исследования (исследования представительной выборки) получать статистические закономерности и распространять их на поведение системы в целом. Однако не всегда можно получить статистические закономерности, не всегда может быть определена представительная (репрезентативная) выборка, доказана правомерность применения статистических закономерностей. В ряде случаев для получения статистических закономерностей требуются недопустимо большие затраты времени, что также ограничивает возможности их приме нения.
Теоретико-множественные	Теоретико-множественные представления, предложенные Г. Кантором, базируются на понятиях: множество (содержательно эквивалентное понятиям «совокупность», «собрание», «ансамбль», «коллекция» и т. п.), элементы множества и отношения на множествах. Сложную систему можно отобразить в виде совокупности разнородных множеств и отношений между ними. Множества могут задаваться двумя способами: перечислением элементов (а₁, а₃,... ,a_n) и названием характеристического свойства (именем, отражающим это свойство) — например, множество А. В основе большинства теоретико-множественных преобразований лежит переход от одного способа задания множества к другому. В множестве могут быть выделены под множества. Из двух и более множеств или подмножеств можно, установив отношения между их элементами, сформировать новое множество, состоящее из элементов, качественно отличающихся от элементов исходных множеств (при таком преобразовании у элементов нового множества как бы появляется иной смысл по сравнению с исходными). Теоретико-множественные представления допускают введение любых отношений. При конкретизации применяемых отношений и правил их использования можно получить одну из алгебр логики, один из формальных языков математической лингвистики, создать язык моделирования сложных систем, который затем, получив соответствующее название, может развиваться как самостоятельное научное направление.	Благодаря тому, что при теоретико-множественных представлениях систем и процессов в них можно вводить любые отношения, эти представления: а) служат хорошим языком, с помощью которого облегчается взаимопонимание между представителями различных областей знаний; б) могут являться основой для возникновения новых научных направлений, для создания языков моделирования, языков автоматизации проектирования. Теоретико-множественные представления являются основой математической теории систем М. Месаровича. Однако свобода введения любых отношений приводит к тому, что в создаваемых языках моделирования трудно ввести правила, закономерности, используя которые формально, можно получить новые результаты, адекватные реальным моделируемым объектам и процессам (как это позволяют делать аналитические и статистические методы). Поэтому первоначально при приме нении теоретико-множественных представлении стремились использовать ограниченный набор отношении. В общем же случае в языке могут появляться ситуации парадоксов или антиномий, что приводит к необходимости ограничения разнообразия отношений в создаваемых языках
Логические	Логические представления переводят реальную систему и отношения в ней на язык одной из алгебр логики (двузначной, многозначной), основанных на применении алгебраических методов для выражения законов формальной логики. Наибольшее распространение получила бинарная алгебра логики Буля (булева алгебра). Алгебра логики оперирует понятиями: высказывание, предикат, логические операции (логические функции, кванторы). В ней доказываются теоремы, приобретающие затем силу логических законов, применяя которые, можно преобразовать систему из одного описания в другое с целью ее совершенствования, например, получить более простую структуру (схему), содержащую меньшее число состояний, элементов, но осуществляющую требуемые функции. Теоремы доказываются и используются в рамках формального логического базиса, который определяется совокупностью специальных правил. Логические методы представления систем относятся к детерминистским, хотя возможно и их расширение в сторону вероятностных оценок. На базе математической логики созданы и развиваются теории логического анализа и синтеза, теория автоматов. На основе логических представлений первоначально начинали развиваться некоторые разделы теории формальных языков. В силу ограниченности смысловыражающнх возможностей бинарной алгебры логики в последнее время имеются попытки со здания многозначных (тернарной к т. п.) алгебр логики с соответствующими логическими базисами и теоремами.	Применяются при исследовании новых структур систем разнообразной природы (технических объектов, текстов и др.), в которых характер взаимодействия между элементами еще не настолько ясен, чтобы было возможно их представление аналитическими методами, а статистические исследования либо затруднены, либо не привели к выявлению устойчивых закономерностей. В то же время следует иметь в виду, что с помощью логических алгоритмов можно описывать не любые отношения, а лишь те которые предусмотрены законами алгебры логики и подчиняются требованиям логического базиса. Логические представления нашли широкое практическое применение при исследовании и разработке автоматов разного рода, автоматических систем контроля, а так же при решении задач распознавания образов. Логические представления лежат в основе теории алгоритмов. На их базе развиваются прикладные разделы теории формальных языков. В то же время смысловыражающие возможности логических методов ограничены базисом и функциями алгебры логики и не всегда позволяют адекватно отобразить реальную проблемную ситуацию. Попытки же создания многозначных алгебр логики на практике пока не находят широкого применения из-за сложности создания логического базиса и доказательства формальных теорем законов многозначной алгебры логики.
Лингвистические, семиотические	Лингвистические представления базируются на понятиях тезауруса Т (множества смысловыражающих элементов языка с за данными смысловыми отношениями; тезаурус характеризует структуру языка), грамматики G (правил образования смысловыражающих элементов разных уровней тезауруса), семантики (смыслового содержания формируемых фраз, предложений и других смысловыражающих элементов) и прагматика (смысла для данной задачи, цели). Семиотические представления базируются же при решении задач распознавания об разов. Логические представления лежат в основе теории алгоритмов. На их базе развиваются прикладные разделы теории формальных языков. В то же время смысловыражающне возможности логических методов ограничены базисом и функциями алгебры логики и не всегда позволяют адекватно отобразить реальную проблемную ситуацию. Попытки же создания многозначных алгебр логики на практике пока не находят широкого применения из-за сложности создания логического базиса и доказательства формальных теорем-законов многозначной алгебры логики на понятиях: знак, знаковая система, знаковая ситуация. Семиотика возникла как наука о знаках в широком смысле. Однако наиболее широкое практическое применение нашло направление лингвистической семиотики, которое наряду с основными понятиями семиотики (знак, знаковая система, треугольник Фреге и т. п.) широко пользуется некоторыми понятиями математической лингвистики (тезаурус, грамматика и т. п.). С теоретической точки зрения границу между лингвистическими и семиотическими представлениями при разработке языков моделирования можно определить характером правил грамматики (если правила не охватываются классификацией правил вывода формальных грамматик Н. Хомского, то модель удобнее отнести к семиотической иприменять принципы ее анализа, предлагаемые семиотикой). Для практических приложении модели лингвистических и семиотических представлений можно рассматривать как один класс методов формализованного представления систем.	Лингвистические и семиотические представления возникли и развиваются в связи с потребностями анализа текстов и языков. Однако в последнее время эти представления начинают широко применяться для от отображения и анализа процессов в сложных системах в тех случаях, когда не удается применить сразу аналитические, статистические представления или методы формальной логики. В частности, лингвистические и семиотические представления являются удобным аппаратом (особенно о сочетании с графическими) для первого этапа постепенной формализации задач принятия решений в плохоформализуемых ситуациях, чем и был вызван возрастающий интерес к этим методам со стороны инженеров и разработчиков сложных систем. На их основе разрабатывают языки моделирования, автоматизации проектирования и т.д. Что касается недостатков методов, то при усложнении языка моделирования, при применении правил произвольных грамматик Н. Хомского или правил лингвистической семиотики трудно гарантировать правильность получаемых результатов, возни кают проблемы алгоритмической разреши мости, возможно появление парадоксов, что частично может быть устранено с помощью содержательного контроля и корректировки языка на каждом шаге его расширения в диалоговом режиме моделирования. При этом создатель языка не всегда может объяснить его возможности, происходит как бы «выращивание» языка, у которого появляются новые свойства.
Графические	К графическим представлениям здесь отнесены любые графики (графики Ганта, диаграммы, гистограммы и т. п.) и возникшие на основе графических отображений теории: теория графов, теория сетевого планирования и управления и т. п.), т. е. все то, что позволяет наглядно представить процессы, происходящие в системах, и об легчить таким образом их анализ для человека (лица, принимающего решения).	Графические представления являются удобным средством исследования структур и процессов в сложных системах и решения различного рода организационных вопросов в информационно-управляющих комплексах, вкоторых необходимо взаимодействие человека и технических устройств (в том числе ЭВМ). Широкое применение на практике получили теория сетевого планирования и управления.

Прикладные классификации МФПС. Для удобства выбора методов решения реальных практических задач на базе математических направлений развиваются прикладные и предлагаются их классификации.Так существуют различные классификации экономико-математических методов, обобщение которых приведено в табл. 2.2. Эта классификация включает прикладные направления, базирующиеся, в основном, на использовании аналитических и статистических представлений. Однако некоторые из них (модели объемного и календарного планирования. потоковые модели) используют графические методы (сетевое моделирование), а иногда для предвари тельного описания задачи - теоретико-множественные представления.

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

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

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

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

Аналитические методы

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

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

В табл. 2.1 эта особенность аналитических представлений условно иллюстрируется символическим образом, преобразования сложной системы в точку, совершающую какое-то движение (или обладающую каким-то поведением), посредством -оператора (функции, функционала) Ф[S_х]. Как правило, поведение точек, их взаимодействие описываются строгими соотношениями, имеющими силу закона.

Основу понятийного (терминологического) аппарата этих представлений составляют понятия классической математики (величина, формула, функция, уравнение, система уравнений, логарифм, дифференциал, интеграл и т. д.).

Аналитические представления имеют многовековую историю развития [2.41, 2.45 и др.], и для них характерно не только стремление к строгости терминологии, но и к закреплению за некоторыми специальными величинами определенных букв (напр., удвоенное отношение площади круга к площади вписанного в него квадрата -пи равно3,14; основание натурального логарифма - е равно 2,7 и т.д.).

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

Эти теоретические направления стали основой многих прикладных, в т. ч. теории автоматического управления, теории оптимальных решений и т. д.

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

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

В то же время в состав этого класса методов входит относительно новое направление математики математическое программирование, которое содержит средства постановки задачи и расширяет возможности доказательства адекватности моделей.

Идея этого направления была предложена инженером, а впоследствии за работы в этой области лауреатом государственной и нобелевской премий Л.В.Канторовичем для решения экономических задач (в частности, - задачи раскроя фанеры).

Для поясненияэтих особенностей рассмотрим упрощенный пример.

Предположим, что в трех цехах (Ц1, Ц2, ЦЗ) изготавливается два вида изделий И1 и И2. Известна загрузка каждого цеха a_i (оцениваемая в данном случае в про центах) при изготовлении каждого из изделий и прибыль (или цена, объем реализуемой продукции в рублях) c_i от реализации изделий. Требуется определить, сколько изделий каждого вида следует производить при возможно более полной загрузке цехов, чтобы получить за рассматриваемый плановый период максимальную при быль или максимальный объем реализуемой продукции. Такую ситуацию удобно отобразить таблицей 2.3

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

и ряд ограничений (в данном случае диктуемых возможностями цехов, т. е. их пре дельной 100%-ной загрузкой).

В данном случае ограничения однородны и их можно записать короче:

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

Анализ хода постановки и решения задачи позволяет выявить основные особенности математического программирования:

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

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

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

изучение методов решения задач математического программирования позволяет получить представление о пошаговом приближении к решению, т. е. о пошаговом алгоритме получения результата моделирования;

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

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

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

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

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

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

Дата добавления: 2015-04-15; просмотров: 3003;