Понятие математической модели. Графическая, имитационная, математическая модели. Моделирование глобальных процессов. Графы и его виды

Автономная некоммерческая организация дополнительного образования «Сибирский институт непрерывного дополнительного образования» ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ Введение Понятие модели относится к фундаментальным общенаучным понятиям, а моделирование — это метод познания действительности, используемый различными науками. Практически во всех естественных и социальных науках построение и использование моделей является мощным орудием исследований. Реальные объекты и процессы бывают столь многогранны и сложны, что лучшим способом их изучения оказывается построение модели, отображающей лишь какую-то часть реальности и потому многократно более простой, чем эта реальность. Предметом исследования и разработки информатики является методология информационного моделирования, связанная с использованием компьютерной техники и технологий. В этом смысле говорят о компьютерном моделировании. Межпредметное значение информатики в значительной степени проявляется именно через внедрение компьютерного моделирования в различные научные и прикладные области: физику и технику, биологию и медицину, экономику, управление и многие другие. Компьютерное моделирование включает в себя процесс реализации информационной модели на компьютере и исследование с помощью этой модели объекта моделирования — проведение вычислительного эксперимента. С помощью компьютерного моделирования решаются многие научные и производственные задачи. Цель: Изучить понятие информационного моделирования и понять сущность процесса моделирования на примере глобальных процессов. План: 1. Понятие математической модели. 2. Графическая, имитационная, математическая модели. 3. Моделирование глобальных процессов. 4. Объектно-информационные модели. ЛЕКЦИЯ №1 «Понятие математической модели» План: 1. Понятие математического моделирования. 2. Причины возникновения математического моделирования. 3. Схема построения математического моделирования. 4. Понятие адекватности модели. Под математическим моделированием, в узком смысле слова, понимают описание в виде уравнений и неравенств реальных физических, химических, технологических, биологических, экономических и других процессов. Для того чтобы использовать математические методы для анализа и синтеза различных процессов, необходимо уметь описать эти процессы на языке математики, то есть описать в виде системы уравнений и неравенств. Как методология научных исследований математическое моделирование сочетает в себе опыт различных отраслей науки о природе и обществе, прикладной математики, информатики и системного программирования для решения фундаментальных проблем. Математическое моделирование объектов сложной природы – единый сквозной цикл разработок от фундаментального исследования проблемы до конкретных численных расчетов показателей эффективности объекта. Результатом разработок бывает система математических моделей, которые описывают качественно разнородные закономерности функционирования объекта и его эволюцию в целом как сложной системы в различных условиях. Вычислительные эксперименты с математическими моделями дают исходные данные для оценки показателей эффективности объекта. Поэтому математическое моделирование как методология организации научной экспертизы крупных проблем незаменимо при проработке народнохозяйственных решений (в первую очередь это относится к моделированию экономических систем). По своей сути математическое моделирование есть метод решения новых сложных проблем, поэтому исследования по математическому моделированию должны быть опережающими. Следует заранее разрабатывать новые методы, готовить кадры, умеющие со знанием дела применять эти методы для решения новых практических задач. Математическая модель может возникнуть тремя путями: 1. В результате прямого изучения реального процесса. Такие модели называются феноменологическими. 2. В результате процесса дедукции. Новая модель является частным случаем некоторой общей модели. Такие модели называются асимптотическими. 3. В результате процесса индукции. Новая модель является обобщением элементарных моделей. Такие модели называют моделями ансамблей. Процесс моделирования начинается с моделирования упрощенного процесса, который с одной стороны отражает основные качественные явления, с другой стороны допускает достаточно простое математическое описание. По мере углубления исследования строятся новые модели, более детально описывающие явление. Факторы, которые считаются второстепенными на данном этапе, отбрасываются. Однако, на следующих этапах исследования, по мере усложнения модели, они могут быть включены в рассмотрение. В зависимости от цели исследования один и тот же фактор может считаться основным или второстепенным. Математическая модель и реальный процесс не тождественны между собой. Как правило, математическая модель строится с некоторым упрощением и при некоторой идеализации. Она лишь приближенно отражает реальный объект исследования, и результаты исследования реального объекта математическими методами носят приближенный характер. Точность исследования зависит от степени адекватности модели и объекта и от точности применяемых методов вычислительной математики. Схема построения математических моделей следующая: 1. Выделение параметра или функции, подлежащей исследованию. 2. Выбор закона, которому подчиняется эта величина. 3. Выбор области, в которой требуется изучить данное явление. В практике математического моделирования исходным пунктом часто является некоторая эмпирическая ситуация, выдвигающая перед исследователем задачу, на которую требуется найти ответ. Прежде всего, необходимо установить, в чём именно заключается задача. Часто (но не всегда) параллельно с этой стадией постановки задачи идёт процесс выявления основных или существенных особенностей явления. В частности для физических явлений этот процесс схематизации или идеализации играет решающую роль, поскольку в реальном явлении участвует множество процессов и оно чрезвычайно сложно. Некоторые черты явления представляются важными многие другие - несущественными. Возьмем, к примеру, движение маятника, образованного тяжёлым грузом, подмешанным на конце нити. В этом случае существенным является регулярный характер колебаний маятника, а несущественным – то, что нить белая, а груз чёрный. После того как существенные факторы выявлены, следующий шаг состоит в переводе этих факторов на язык математических понятий и величин и постулировании соотношений между этими величинами. После построения модели её следует подвергнуть проверке. Адекватность модели до некоторой степени проверяется обычно в ходе постановки задачи. Уравнения или другие математические соотношения, сформулированные в модели, постоянно сопоставляются с исходной ситуацией. Существует несколько аспектов проверки адекватности. Во-первых, сама математическая основа модели (которая и составляет её существо) должна быть непротиворечивой и подчиняться всем обычным законам математической логики. Во-вторых, справедливость модели зависит от её способности адекватно описывать исходную ситуацию. Модель можно заставить отражать действительность, однако она не есть сама действительность. Ситуации моделируют для разных целей. Главная из них – необходимость предсказывать новые результаты или новые свойства явления. Эти предсказания могут быть связаны с распространением существующих результатов или иметь более принципиальный характер. Часто они относятся к условиям, которые, по всей вероятности, будут иметь место в некоторый момент в будущем. С другой стороны, предсказания могут относится к событиям, непосредственное экспериментальное исследование которых неосуществимо. Наиболее важный пример такого рода дают многочисленные прогнозы, которые делались на основе математических моделей в программе космических исследований. Однако для этой цели моделируются не все ситуации: в некоторых случаях достаточно уметь описывать математическими средствами работу системы для того, чтобы добиться более глубокого понимания явления (именно эту роль и играют многие выдающиеся физические теории, хотя на их основе делаются также и прогнозы). Обычно при таком математическом описании не учитывается элемент контроля, однако в моделях, построенных, например, для исследования работы сетей, таких как схемы движения поездов или самолётов, контроль часто является важным фактором. Математическая модель представляет собой упрощение реальной ситуации. Ощутимое упрощение наступает тогда, когда несущественные особенности ситуации отбрасываются и сложная исходная задача сводится к идеализированной задаче, поддающейся математическому анализу. Именно при таком подходе в классической прикладной механике возникли блоки без трения, невесомые нерастяжимые нити, невязкие жидкости, абсолютно твёрдые или чёрные тела и прочие подобные идеализированные модели. Эти понятия не существуют в реальной действительности, они являются абстракциями, составной частью идеализации, предпринятой автором модели. И, тем не менее, их часто можно с успехом считать хорошим приближением к реальным ситуациям. Описанный образ действий при построении математических моделей не является единственным, и этому совсем не стоит удивляться. В другом возможном подходе первым шагом является построение простой модели нескольких наиболее характерных особенностей явления. Это часто делается для того, чтобы почувствовать данную задачу, причём делается это ещё до того, как сама задача окончательно сформулирована. Затем эта модель обобщается, чтобы охватить другие факты, пока не будет найдено приемлемое или адекватное решение. Есть ещё подход, когда с самого начала вводится в рассмотрение одновременно большое число факторов. Он часто применяется в исследовании операций, и такие модели обычно изучают имитационными методами с использованием ЭВМ. Важнейшее решение, которое часто принимается в самом начале процесса моделирования, касается природы рассматриваемых математических переменных. По существу они делятся на два класса. В один из них входят известные характеристики, т.е. величины, поддающиеся (по крайней мере, теоретически) точному измерению и управлению. Такие переменные называются детерминированными переменными. В другой класс входят неизвестные характеристики, т.е. величины, которые никогда не могут быть точно измерены и имеют случайный характер – они называются стохастическими переменными. Модель, содержащая стохастические переменные, должна по определению описываться математическим аппаратом теории вероятностей и статистики. Детерминированные переменные часто, но не всегда требуют привлечения обычного математического анализа. Природа некоторых ситуаций бывает ясна не сразу, другие ситуации характеризуются переменными обоих типов. Для построения модели чрезвычайно важно, чтобы природа переменных была правильно представлена. ЛЕКЦИЯ №2 «Графическая, имитационная и математическая модели» План: 1. Графы и его виды. 2. Дерево – граф иерархической структуры. 3. Графическое моделирование результатов научной деятельности. 4. Имитационные модели и детерминированное моделирование. 5. Модели случайных процессов. 6. Алгоритм детерминированной имитационной модели. 7. Математические модели и этапы его моделиррования. 8. Классификация математических моделей. Разнообразие графических моделей достаточно велико. Рассмотрим некоторые из них. Наглядным средством отображения состава и структуры систем являются графы. Рассмотрим пример. Имеется словесное описание некоторой местности: “Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино”. По такому описанию довольно трудно представить себе эту местность. Гораздо легче та же информация воспринимается с помощью схемы (см. рисунок 1). Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема, отображающая элементный состав системы и структуру связей, называется графом. Рис.1. Пример графа Составными частями графа являются вершины и ребра. На рисунке вершины изображены кружками — это элементы системы, а ребра изображены линиями — это связи (отношения) между элементами. Глядя на этот граф, легко понять структуру дорожной системы в данной местности. Построенный граф позволяет, например, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино? Видно, что есть два возможных пути: 1) Р  К  Б  М и) Р  К  Д  Б  М. Можно ли отсюда сделать вывод, что 1-й путь короче 2-го? Нет, нельзя. Данный граф не содержит количественных характеристик. Это не карта, где соблюдается масштаб и есть возможность измерить расстояние. Граф, приведенный на следующем рисунке (см. Рис.2), содержит количественные характеристики. Числа около ребер обозначают длины дорог в километрах. Это пример взвешенного графа. Взвешенный граф может содержать количественные характеристики не только связей, но и вершин. Например, в вершинах может быть указано население каждого поселка. Согласно данным взвешенного графа, оказывается, что первый путь длиннее второго. Рис. 2. Пример взвешенного графа Подобные графы еще называют сетью. Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин. Для сетей также характерно наличие замкнутых путей, которые называются циклами. В данном случае имеется цикл: К  Д  Б  К. На рассмотренных схемах каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б (предполагаем, что действует двустороннее движение). Такие графы являются неориентированными, а их связи называют симметричными. Весьма распространенным типом систем являются системы с иерархической структурой. Иерархическая структура естественным образом возникает, когда объекты или некоторые их свойства находятся в отношении соподчинения (вложения, наследования). Как правило, иерархическую структуру имеют системы административного управления, между элементами которых установлены отношения подчиненности. Например: директор завода — начальники цехов — начальники участков — бригадиры — рабочие. Иерархическую структуру имеют также системы, между элементами которых существуют отношения вхождения одних в другие. Граф иерархической структуры называется деревом. Основным свойством дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель. Посмотрите на граф (см. рис.3), отражающий иерархическую административную структуру нашего государства: Российская Федерация делится на семь административных округов; округа делятся на регионы (области и национальные республики), в состав которых входят города и другие населенные пункты. Такой граф называется деревом. Рис. 3. Дерево административной структуры РФ У дерева существует одна главная вершина, которая называется корнем дерева. Эта вершина изображается вверху; от нее идут ветви дерева. От корня начинается отсчет уровней дерева. Вершины, непосредственно связанные с корнем, образуют первый уровень. От них идут связи к вершинам второго уровня и т.д. Каждая вершина дерева (кроме корня) имеет одну исходную вершину на предыдущем уровне и может иметь множество порожденных вершин на следующем уровне. Такой принцип связи называется “один ко многим”. Вершины, которые не имеют порожденных, называются листьями (на дереве административной структуры РФ - это вершины, обозначающие города). Общую цель научной графики можно сформулировать так: сделать невидимое и абстрактное “видимым”. Последнее слово заключено в кавычки, так как эта “видимость” часто весьма условна. Можно ли увидеть распределение температуры внутри неоднородно нагретого тела сложной формы без введения в него сотен микродатчиков, т.е., по существу, его разрушения? — Да, можно, если есть соответствующая математическая модель и, что очень важно, договоренность о восприятии определенных условностей на рисунке. Можно ли увидеть распределение металлических руд под землей без раскопок? Строение поверхности чужой планеты по результатам радиолокации? На эти и множество других вопросов ответ — да, можно, с помощью компьютерной графики и предшествующей ей математической обработки. Более того, можно “увидеть” и то, что, строго говоря, вообще плохо соответствует слову “видеть”. Так, возникшая на стыке химии и физики наука — квантовая химия — дает нам возможность “увидеть” строение молекулы. Эти изображения — верх абстракции и системы условностей, так как в атомном мире обычные наши понятия о частицах (ядрах, электронах и т.п.) принципиально неприменимы. Однако многоцветное “изображение” молекулы на экране компьютера для тех, кто понимает всю меру его условности, приносит большую пользу, чем тысячи чисел, являющихся результатами вычислений. Стандартным приемом обработки результатов вычислительного эксперимента является построение линий (поверхностей), называемых изолиниями(изоповерхностями), вдоль которых некоторая функция имеет постоянное значение. Это очень распространенный прием визуализации характеристик некоторого скалярного поля в приближении сплошной среды: изотермы — линии равной температуры, изобары — линии равного давления, изолинии функции тока жидкости или газа, по которым легко можно представить себе их потоки, изолинии численностей экологической популяции на местности, изолинии концентрации вредных примесей в окружающей среде и т.д. На рисунке (см. Рис.3) изображены изолинии функции тока неравномерно нагретой жидкости в прямоугольной области течения. По этой картине можно наглядно судить о направлении потоков течения и их интенсивности. Рис. 3. Изолинии течения Еще один интересный прием современной научной графики — условная раскраска. Она находит широчайшее применение в самых разных приложениях науки и представляет собой набор приемов по максимально удобной визуализации результатов компьютерного моделирования. В различных исследованиях температурных полей встает проблема наглядного представления результатов, например, температур на метеорологических картах. Для этого можно рисовать изотермы на фоне карты местности. Но можно добиться еще большей наглядности, учитывая, что большинству людей свойственно воспринимать красный цвет как “горячий”, синий — как “холодный”. Переход по спектру от красного к синему отражает промежуточные значения температур. То же самое можно делать при иллюстрации температурного поля и на поверхности обрабатываемой на станке детали, и на поверхности далекой планеты. При моделировании сложных органических молекул компьютер может выдавать результаты в виде многоцветной картины, на которой атомы водорода изображены одним цветом, углерода — другим и т.д., причем атом представлен шариком (кружочком), в пределах которого плотность цвета меняется в соответствии с распределением электронной плотности. При поиске полезных ископаемых методами аэрофотосъемки с самолетов или космических спутников компьютеры строят условные цветовые изображения распределений плотности под поверхностью Земли. Изображения в условных цветах и контрастах — мощнейший прием научной графики. Он позволяет понять строение не только плоских, но и объемных (трехмерных) объектов, дает в руки исследователя один из замечательных методов познания. Имитационная модель воспроизводит поведение сложной системы взаимодействующих элементов. Для имитационного моделирования характерно наличие следующих обстоятельств (одновременно всех или некоторых из них): · объект моделирования — сложная неоднородная система; · в моделируемой системе присутствуют факторы случайного поведения; · требуется получить описание процесса, развивающегося во времени; · принципиально невозможно получить результаты моделирования без использования компьютера. Состояние каждого элемента моделируемой системы описывается набором параметров, которые хранятся в памяти компьютера в виде таблиц. Взаимодействия элементов системы описываются алгоритмически. Моделирование осуществляется в пошаговом режиме. На каждом шаге моделирования изменяются значения параметров системы. Программа, реализующая имитационную модель, отражает изменение состояния системы, выдавая значения ее искомых параметров в виде таблиц по шагам времени или в последовательности происходящих в системе событий. Для визуализации результатов моделирования часто используется графическое представление, в т.ч. анимированное. Имитационная модель основана на подражании реальному процессу (имитации). Например, моделируя изменение (динамику) численности микроорганизмов в колонии, можно рассматривать много отдельных объектов и следить за судьбой каждого из них, ставя определенные условия для его выживания, размножения и т.д. Эти условия обычно задаются в вербальной форме. Например, по истечении некоторого промежутка времени микроорганизм делится на две части, а по прошествии другого (большего) временного отрезка — погибает. Выполнение описанных условий алгоритмически реализуется в модели. Такой компьютерный эксперимент фактически претендует на воспроизведение натурного эксперимента. На вопрос: “Зачем это нужно делать?” можно дать следующий ответ: имитационное моделирование позволяет выделить “в чистом виде” следствия гипотез, заложенных в представления о микрособытиях (т.е. на уровне элементов системы), избавив их от неизбежного в натурном эксперименте влияния других факторов, о которых мы можем даже не подозревать. Если такое моделирование включает и элементы математического описания процессов на микроуровне, и если исследователь при этом не ставит задачу поиска стратегии регулирования результатов (например, управления численностью колонии микроорганизмов), то отличие имитационной модели от математической (дескриптивной) оказывается достаточно условным. Примеры имитационных моделей (эволюция колонии микроорганизмов, движение молекул в газе) приводят к детерминированному описанию систем. В них отсутствуют элементы вероятности, случайности событий в моделируемых системах. Рассмотрим пример моделирования системы, обладающей этими качествами. Кому не случалось стоять в очереди и с нетерпением прикидывать, успеет ли он сделать покупку (или заплатить за квартиру, покататься на карусели и т.д.) за некоторое имеющееся в его распоряжении время? Или, пытаясь позвонить по телефону в справочную и натыкаясь несколько раз на короткие гудки, нервничать и оценивать — дозвонюсь или нет? Из таких “простых” проблем в начале XX века родилась новая отрасль математики — теория массового обслуживания, использующая аппарат теории вероятностей и математической статистики, дифференциальных уравнений и численных методов. Впоследствии выяснилось, что эта теория имеет многочисленные выходы в экономику, военное дело, организацию производства, биологию и экологию и т.д. Компьютерное моделирование при решении задач массового обслуживания, реализуемое в виде метода статистических испытаний (метода Монте-Карло), играет важную роль. Возможности аналитических методов решения реально возникающих задач массового обслуживания весьма ограничены, в то время как метод статистических испытаний универсален и относительно прост. Рассмотрим простейшую задачу этого класса. Имеется магазин с одним продавцом, в который случайным образом входят покупатели. Если продавец свободен, то он начинает обслуживать покупателя сразу, если зашло одновременно несколько покупателей — выстраивается очередь. Есть немало других аналогичных ситуаций: · ремонтная зона в автохозяйстве и автобусы, сошедшие с линии из-за поломки; · травмпункт и больные, пришедшие на прием по случаю травмы (т.е. без системы предварительной записи); · телефонная станция с одним входом (или одной телефонисткой) и абоненты, которых при занятом входе ставят в очередь (такая система иногда практикуется); · сервер локальной сети и персональные машины на рабочем месте, которые шлют сообщение серверу, способному воспринять разом и обработать не более одного сообщения. Процесс прихода покупателей в магазин — случайный процесс. Промежутки времени между приходами любой последовательной пары покупателей — независимые случайные события, распределенные по некоторому закону, который может быть установлен лишь путем многочисленных наблюдений (либо для моделирования взят некоторый его правдоподобный вариант). Второй случайный процесс в этой задаче, никак не связанный с первым, — длительность обслуживания каждого из покупателей. Целью моделирования систем такого вида является получение ответа на ряд вопросов. Относительно простой вопрос — какое в среднем время придется стоять в очереди при заданных законах распределения указанных выше случайных величин? Более сложный вопрос: каково распределение времен ожидания обслуживания в очереди? Не менее сложный вопрос: при каких соотношениях параметров входных распределений наступит кризис, при котором очередь до вновь вошедшего покупателя не дойдет никогда? Если задуматься над этой относительно простой задачей, возможные вопросы будут множиться. Способ моделирования выглядит в общих чертах так. Используемые математические формулы — законы распределения исходных случайных величин; используемые числовые константы — эмпирические параметры, входящие в эти формулы. Не решается никаких уравнений, которые использовались бы при аналитическом исследовании данной задачи. Вместо этого происходит имитация очереди, разыгрываемая с помощью компьютерных программ, генерирующих случайные числа с заданными законами распределения. Затем производится статистическая обработка совокупности полученных значений величин, определяемых заданными целями моделирования. Например, находится оптимальное количество продавцов для разных периодов времени работы магазина, которое обеспечит отсутствие очередей. Математический аппарат, который здесь используется, называется методами математической статистики. Рассмотрим имитационную модель эволюции популяции живых организмов, известную под названием “Жизнь”, которую легко реализовать на любом языке программирования. Для построения алгоритма игры рассмотрим квадратное поле из n + 1 столбцов и строк с обычной нумерацией от 0 до n. Крайние граничные столбцы и строки для удобства определим как “мертвую зону”, они играют лишь вспомогательную роль Для любой внутренней клетки поля с координатами (i, j) можно определить 8 соседей. Если клетка “живая”, ее закрашиваем, если клетка “мертвая”, она пустая. Зададим правила игры. Если клетка (i, j) “живая” и ее окружает более трех “живых” клеток, она погибает (от перенаселения). “Живая” клетка также погибает, если в ее окружении находится менее двух “живых” клеток (от одиночества). “Мертвая” клетка оживает, если вокруг нее появляются три “живые” клетки (см. Рис. 4). Рис. 4. Графическое представление игры «Жизнь» Для удобства введем двумерный массив A[0..n, 0..n], элементы которого принимают значение 0, если соответствующая клетка пустая, и 1, если клетка “живая”. Тогда алгоритм определения состояния клетки с координатой (i, j) можно определить следующим образом: S := А[I - 1, J - 1] + А[I – 1, J] + + А[I - 1, J + 1] + А[I + 1, J - 1] + А[I + 1, J] + А[I + 1, J + 1] + + А[I, J + 1] + А[I, J - 1]; If (А[I, J] = 1) And ((S > 3) Or (S <)) Then B[I, J] := 0; If (A[I, J] = 0) And (S = 3) Then B[I, J] := 1; Здесь массив B[0..n, 0..n] определяет координаты поля на следующем этапе. Для всех внутренних клеток от i = 1 до n – 1 и j = 1 до n – 1 справедливо сказанное выше. Отметим, что последующие поколения определяются аналогично, стоит лишь осуществить процедуру переприсваивания: For I := 1 To N - 1 Do For J := 1 To N - 1 Do A[I, J] := B[I, J]; На экране дисплея удобнее выводить состояние поля не в матричном, а в графическом виде. Осталось лишь определить процедуру задания начальной конфигурации игрового поля. При случайном определении начального состояния клеток подходит алгоритм: For I := 1 To K Do Begin K1 := Random(N - 1); K2 := Random(N - 1) + 1; A[K1, K2] := 1 End; Интереснее для пользователя самому задавать начальную конфигурацию, что легко осуществить. В результате экспериментов с этой моделью можно найти, например, устойчивые расселения живых организмов, которые никогда не погибают, оставаясь неизменными или изменяя свою конфигурацию с определенным периодом. Абсолютно неустойчивым (гибнущим во втором поколении) является расселение “крестом”. Математическая модель — приближенное описание объекта моделирования, выраженное с помощью математической символики. Математические модели появились вместе с математикой много веков назад. Огромный толчок развитию математического моделирования придало появление ЭВМ. Применение вычислительных машин позволило проанализировать и применить на практике многие математические модели, которые раньше не поддавались аналитическому исследованию. Реализованная на компьютере математическая модель называется компьютерной математической моделью, а проведение целенаправленных расчетов с помощью компьютерной модели называется вычислительным экспериментом. Рис. 5. Этапы компьютерного математического моделирования Этапы компьютерного математического моделирования изображены на рисунке (см. Рис. 5). Первый этап — определение целей моделирования. Эти цели могут быть различными: 1) модель нужна для того, чтобы понять, как устроен конкретный объект, какова его структура, основные свойства, законы развития и взаимодействия с окружающим миром (понимание); 2) модель нужна для того, чтобы научиться управлять объектом (или процессом) и определить наилучшие способы управления при заданных целях и критериях (управление); 3) модель нужна для того, чтобы прогнозировать прямые и косвенные последствия реализации заданных способов и форм воздействия на объект (прогнозирование). Поясним на примерах. Пусть объект исследования — взаимодействие потока жидкости или газа с телом, являющимся для этого потока препятствием. Опыт показывает, что сила сопротивления потоку со стороны тела растет с ростом скорости потока, но при некоторой достаточно высокой скорости эта сила скачком уменьшается с тем, чтобы с дальнейшим увеличением скорости снова возрасти. Что же вызвало уменьшение силы сопротивления? Математическое моделирование позволяет получить четкий ответ: в момент скачкообразного уменьшения сопротивления вихри, образующиеся в потоке жидкости или газа позади обтекаемого тела, начинают отрываться от него и уноситься потоком. Второй этап: определение входных и выходных параметров модели; разделение входных параметров по степени важности влияния их изменений на выходные. Такой процесс называется ранжированием, или разделением по рангам. Третий этап: построение математической модели. На этом этапе происходит переход от абстрактной формулировки модели к формулировке, имеющей конкретное математическое представление. Математическая модель — это уравнения, системы уравнений, системы неравенств, дифференциальные уравнения или системы таких уравнений и пр. Четвертый этап: выбор метода исследования математической модели. Чаще всего здесь используются численные методы, которые хорошо поддаются программированию. Как правило, для решения одной и той же задачи подходит несколько методов, различающихся точностью, устойчивостью и т.д. От верного выбора метода часто зависит успех всего процесса моделирования. Пятый этап: разработка алгоритма, составление и отладка программы для ЭВМ — трудно формализуемый процесс. Из языков программирования многие профессионалы для математического моделирования предпочитают FORTRAN: как в силу традиций, так и в силу непревзойденной эффективности компиляторов (для расчетных работ) и наличия написанных на нем огромных, тщательно отлаженных и оптимизированных библиотек стандартных программ математических методов. В ходу и такие языки, как PASCAL, BASIC, C, — в зависимости от характера задачи и склонностей программиста. Шестой этап: тестирование программы. Работа программы проверяется на тестовой задаче с заранее известным ответом. Это — лишь начало процедуры тестирования, которую трудно описать формально исчерпывающим образом. Обычно тестирование заканчивается тогда, когда пользователь по своим профессиональным признакам сочтет программу верной. Седьмой этап: собственно вычислительный эксперимент, в процессе которого выясняется, соответствует ли модель реальному объекту (процессу). Модель достаточно адекватна реальному процессу, если некоторые характеристики процесса, полученные на ЭВМ, совпадают с экспериментально полученными характеристиками с заданной степенью точности. В случае несоответствия модели реальному процессу возвращаемся к одному из предыдущих этапов. В основу классификации математических моделей можно положить различные принципы. Можно классифицировать модели по отраслям наук (математические модели в физике, биологии, социологии и т.д.). Можно классифицировать по применяемому математическому аппарату (модели, основанные на применении обыкновенных дифференциальных уравнений, дифференциальных уравнений в частных производных, стохастических методов, дискретных алгебраических преобразований и т.д.). Наконец, если исходить из общих задач моделирования в разных науках безотносительно к математическому аппарату, наиболее естественна такая классификация: · дескриптивные (описательные) модели; · оптимизационные модели; · многокритериальные модели; · игровые модели. Поясним это на примерах. Дескриптивные (описательные) модели. Например, моделирование движения кометы, вторгшейся в Солнечную систему, производится с целью предсказания траектории ее полета, расстояния, на котором она пройдет от Земли, и т.д. В этом случае цели моделирования носят описательный характер, поскольку нет никаких возможностей повлиять на движение кометы, что-то в нем изменить. Оптимизационные модели используются для описания процессов, на которые можно воздействовать, пытаясь добиться достижения заданной цели. В этом случае в модель входит один или несколько параметров, доступных влиянию. Например, меняя тепловой режим в зернохранилище, можно задаться целью подобрать такой режим, чтобы достичь максимальной сохранности зерна, т.е. оптимизировать процесс хранения. Многокритериальные модели. Нередко приходится оптимизировать процесс по нескольким параметрам одновременно, причем цели могут быть весьма противоречивыми. Например, зная цены на продукты и потребность человека в пище, нужно организовать питание больших групп людей (в армии, детском летнем лагере и др.) физиологически правильно и, одновременно с этим, как можно дешевле. Ясно, что эти цели совсем не совпадают, т.е. при моделировании будет использоваться несколько критериев, между которыми нужно искать баланс. Игровые модели могут иметь отношение не только к компьютерным играм, но и к весьма серьезным вещам. Например, полководец перед сражением при наличии неполной информации о противостоящей армии должен разработать план: в каком порядке вводить в бой те или иные части и т.д., учитывая и возможную реакцию противника. Есть специальный раздел современной математики — теория игр, — изучающий методы принятия решений в условиях неполной информации. ЛЕКЦИЯ №3 «Моделирование процессов оптимального планирования» План: 1. Постановка задачи оптимального планирования. 2. Пример математической модели оптимального планирования. 3. Пример решения задачи оптимального планирования на примере линейного программирования. Планирование — важнейший этап экономической и управленческой деятельности. Объектом планирования может быть деятельность подразделения или всего предприятия, отрасли промышленности или сельского хозяйства, региона, наконец, государства. Постановка задачи планирования в общем случае выглядит следующим образом: · имеются некоторые плановые показатели: X, Y, …; · имеются некоторые ресурсы: R1, R2, …, за счет которых эти плановые показатели могут быть достигнуты; · имеется определенная стратегическая цель, зависящая от значений плановых показателей, на которую следует ориентировать планирование. Задача оптимального планирования заключается в определении значений плановых показателей с учетом ограниченности ресурсов при условии достижения стратегической цели. Приведем примеры. Пусть объектом планирования является детский сад. Ограничимся лишь двумя плановыми показателями: числом детей и числом воспитателей. Основными ресурсами деятельности детского сада являются размер финансирования и размер помещения. А каковы стратегические цели? Естественно, одной из них является сохранение и укрепление здоровья детей. Количественной мерой этой цели является минимизация заболеваемости воспитанников детского сада. Другой пример: планирование экономической деятельности государства. Безусловно, это слишком сложная задача для детального анализа. Плановых показателей очень много: это производство различных видов промышленной и сельскохозяйственной продукции, подготовка специалистов, выработка электроэнергии, размер зарплаты работников бюджетной сферы и многое другое. К ресурсам относятся: количество работоспособного населения, бюджет государства, природные ресурсы, энергетика, возможности транспортных систем и пр. Разумеется, каждый из этих видов ресурсов ограничен. Кроме того, важнейшим ресурсом является время, отведенное на выполнение плана. Вопрос о стратегических целях в этом случае очень сложен. У государства их много, но в разные периоды истории приоритеты могут меняться. Например, в военное время главной целью является максимальная обороноспособность, военная мощь страны. В мирное время в современном цивилизованном государстве приоритетной целью должно быть достижение максимального уровня жизни населения. Решение задач оптимального планирования чаще всего является сложным и недоступным при использовании лишь человеческого опыта (эмпирических методов). Для решения таких задач строится математическая модель, устанавливающая связь между параметрами задачи. Следовательно, оптимальное планирование осуществляется путем применения математического моделирования. Как правило, такие модели для реальных ситуаций не поддаются аналитическому решению, поэтому используются численные методы решения, реализуемые на компьютере. Рассмотрим простой пример, с помощью которого можно получить представление об одном из классов задач оптимального планирования. Школьный кондитерский цех готовит пирожки и пирожные. В силу ограниченности емкости склада за день можно приготовить в совокупности не более 700 изделий. Рабочий день в кондитерском цехе длится 8 часов. Поскольку производство пирожных более трудоемко, то, если выпускать только их, за день можно произвести не более 250, пирожков же можно произвести 1000 (если при этом не выпускать пирожных). Стоимость пирожного вдвое выше, чем пирожка. Требуется составить дневной план производства, обеспечивающий кондитерскому цеху наибольшую выручку. Сформулируем эту задачу математически. Плановыми показателями являются: x — дневной план выпуска пирожков; y — дневной план выпуска пирожных. Ресурсы производства — это: · длительность рабочего дня — 8 часов; · вместимость складского помещения — 700 мест. Получим соотношения, следующие из условий ограниченности времени работы цеха и вместимости склада, т.е. суммарного числа изделий. Из постановки задачи следует, что на изготовление одного пирожного затрачивается в 4 раза больше времени, чем на 1 пирожок. Если обозначить время изготовления пирожка t мин., то время изготовления пирожного равно 4t мин. Стало быть, суммарное время на изготовление x пирожков и yпирожных равно tx + 4ty = (x + 4y)t. Но это время не может быть больше длительности рабочего дня. Отсюда следует неравенство (x + 4y)t  8 ? 60, или (x + 4y)t  480. Поскольку за рабочий день может быть изготовлено 1000 пирожков, то на один тратится 480/1000 = 0,48 мин. Подставляя это значение в неравенство, получим: (x + 4y) ? 0,48  480. Отсюда x + 4y 1000. Ограничение на общее число изделий дает очевидное неравенство x + y  700. К двум полученным неравенствам следует добавить условия положительности значений величин x и y (не может быть отрицательного числа пирожков и пирожных). В итоге мы получили систему неравенств: x + 4y  1000, x + y  700, x  0, y  0                     ()                 Формализуем стратегическую цель: получение максимальной выручки. Выручка — это стоимость всей проданной продукции. Пусть цена одного пирожка r рублей. По условию задачи, цена пирожного в два раза больше, т.е. 2r рублей. Отсюда стоимость всей произведенной за день продукции равна rx + 2ry = r(x + 2y). Целью производства является получение максимальной выручки. Будем рассматривать записанное выражение как функцию от x, y: F(x, y) = r(x + 2y). Поскольку r — константа, то максимальное значение F(x, y) будет достигнуто при максимальной величине выражения x + 2y. Поэтому в качестве функции, максимум которой соответствует стратегической цели, можно принять  f(x, y) = x + 2y () Следовательно, получение оптимального плана свелось к следующей математической задаче: найти значения плановых показателей x и y, удовлетворяющих системе неравенств () и придающих максимальное значение целевой функции (). Приведенный выше пример относится к классу задач линейного программирования. В теории оптимального планирования существует несколько классов задач, из которых линейное программирование — самый простой вариант. Изучение математических методов решения таких задач выходит за рамки целей школьного образования. Вместе с тем было бы не логично ограничиться лишь теоретической постановкой задач оптимального планирования. Современные информационные технологии позволяют решать некоторые задачи оптимального планирования (и, в частности, линейного программирования) без проникновения в существо применяемых математических методов. В частности, такие средства имеются в табличном процессоре Excel, и на их основе можно продемонстрировать ученикам приемы решения конкретных задач. Средство, о котором идет речь, называется Поиск решения. Соответствующая команда находится в меню Сервис. Опишем кратко, как воспользоваться указанным средством для решения поставленной выше задачи. Вначале подготовим таблицу к решению задачи оптимального планирования (см. Рис.1). Рис. 1. Пример оформления таблицы для решения задачи оптимального планирования Ячейки B5 и C5 зарезервированы, соответственно, для значений x (план по изготовлению пирожков) и y (план по изготовлению пирожных). Левые части неравенств в столбце В, правые — в столбце D; знаки “<=” и т.д. в столбце С программой реально не используются. Целевая функция занесена в ячейку В15. Вызовем программу оптимизации и сообщим ей, где расположены данные. Для этого выполним команду Сервис -> Поиск решения. На экране откроется соответствующая форма. Будем действовать по следующему алгоритму: 1. Введем координату ячейки с целевой функцией. В нашем случае это В15. (Заметим, что если перед этим установить курсор на ячейку В15, то ввод произойдет автоматически.) 2. Поставим отметку “Равной максимальному значению”, т.е. сообщим программе, что нас интересует нахождение максимума целевой функции. 3. В поле “Изменяя ячейки” введем В5:С5, т.е. сообщим, какое место отведено под значения переменных — плановых показателей. 4. В поле “Ограничения” надо ввести информацию о неравенствах-ограничениях, которые имеют вид: B10<=D10; B11<=D11; B12>=D12; B13>=D13. Ограничения вводятся следующим образом: · щелкнуть по кнопке “Добавить”; · в появившемся диалоговом окне “Добавление ограничения” вводим ссылку на ячейку В10, выбираем из меню знак неравенства “<=” и вводим ссылку на ячейку D10; снова щелкаем по кнопке “Добавить”, аналогично вводим второе ограничение B11<=D11 и т.д. 5. Закрываем диалоговое окно “Добавление ограничения”. Перед нами — подготовленная форма “Поиск решения”. 6. Щелкаем по кнопке “Выполнить” — в ячейках В5 и С5 появляется оптимальное решение (числа 600 и 100), а также число 800 в ячейке В15 — максимальное значение целевой функции. Таким образом, с помощью компьютерных средств легко и просто спрогнозировать любой вычислительный процесс. ЛЕКЦИЯ №4 «Объектно-информационные модели» План: 1. Понятие объекта, его свойства и значения. 2. Иерархия классов. 3. Методические рекомендации к изучению объектного подхода информационного моделирования. Объектный подход к информационному моделированию берет свое начало в парадигме объектно-ориентированного программирования (ООП), возникшей в 1970-х годах. Главным понятием здесь является “объект”. Объект — часть окружающей нас действительности. Понятие объекта является очень широким и объединяет в себе как реальные, осязаемые предметы (например: кресло, автомобиль, мост), так и образы, созданные мышлением человека (например: стихотворение, музыкальное произведение, математическая теорема). Информационная модель объекта должна отражать некоторый набор его свойств. Свойства объекта — это совокупность признаков, которые отличают его от других объектов. В следующей таблице (см. таблицу 1) даны примеры объектов и их свойств. Таблица 1. Примеры объектов и их свойств У каждого конкретного объекта свойства имеют определенные значения. В нашем примере добавим значения свойств объектов (см. таблицу 2). Эти значения могут быть количественными величинами (10 лет, 5 Гб), но могут быть и именами других объектов. Например, “Иван Иванович Иванов” и “Математика” сами могут рассматриваться как объекты. Таблица 2. Пример объектов, их свойств и значений Состояние объекта характеризуется перечнем всех возможных его свойств и текущими значениями каждого из этих свойств. Изменение состояния объекта отражается в его информационной модели изменением значений его свойств. Как правило, объекты не остаются неизменными. Например, растет стаж работы учителя И.И. Иванова; на жестком диске изменяется объем занятой памяти; документ может быть перенесен на другой диск, в другую папку и пр. Все эти процессы в информационной модели отражаются изменениями значений свойств. В объектно-информационной модели отражаются не только свойства, но также и поведение объекта. Поведение объекта — действия, которые могут выполняться над объектом или которые может выполнять сам объект. Теперь опишем поведение объектов из нашего примера. Объекты, обладающие одинаковыми свойствами и поведением, образуют класс объектов. Каждый объект является экземпляром какого-либо класса. Все преподаватели обладают одним и тем же набором свойств (имя, стаж работы, читаемый курс) и поэтому образуют класс объектов. Присвоим этому классу имя “Преподаватель”. Каждый конкретный преподаватель — экземпляр этого класса (или объект). Следовательно, “Мой преподаватель” — экземпляр класса “Преподаватель”. Аналогично можно ввести класс “Жесткий диск”, объединив в нем все жесткие диски. Тогда “Мой жесткий диск” — экземпляр класса “Жесткий диск”. Если принять во внимание, что класс “Документ” описывает свойства и поведение всех документов, то “Важный документ” — экземпляр класса “Документ”. Таким образом, экземпляр класса (объект) — это конкретный предмет или образ, а класс определяет множество объектов с одинаковыми свойствами и поведением. Класс может порождать произвольное число объектов, однако любой объект относится к строго фиксированному классу. Объектно-информационные модели имеют иерархическую структуру (дерево). Иерархичность проявляется в том, что некоторый класс сам может быть подмножеством другого, более широкого класса. Вот пример иерархической классификации из биологии: вид “Насекомые” включает в себя два отряда: “Крылатые” и “Бескрылые”; в свою очередь, “Крылатые” насекомые делятся на подотряды: “Мотыльки”, “Бабочки”, “Мухи” и т.д. В такой иерархической структуре между классами определяется отношение наследования. Рис. 1.Фрагмент классификации насекомых Наследование — это такое отношение между классами, когда один класс повторяет свойства и поведение другого класса. Такой способ классификации, в частности, хорошо согласуется с механизмом биологического наследования в мире насекомых. Классы верхних уровней являются более общими по отношению к нижним. При спуске по дереву каждый следующий класс является более специфичным и в то же время наследует все свойства своих предшественников. Класс, свойства и поведение которого наследуются, называется суперклассом (или базовым классом). Производный от суперкласса класс называется подклассом. В нашем примере “Насекомые” — суперкласс для подклассов “Крылатые”, “Бескрылые”, “Мотыльки”, “Бабочки”, “Мухи”, а “Крылатые” — суперкласс для подклассов “Мотыльки”, “Бабочки”, “Мухи”. В подклассе дополняются свойства и уточняется поведение суперкласса. При определении класса “Мухи” нет необходимости вводить свойство “Наличие крыльев”, так как это свойство наследуется из суперкласса “Крылатые”. Еще один пример. Рассмотрим систему классов, отражающих сведения о различных видах транспорта. Свойства и поведение, присущие каждому классу, отражены в таблице ниже. Здесь звездочками отмечены наследуемые свойства и действия. Таблица 3. Пример классов, их свойств и значений Все самые общие свойства располагаются в суперклассе “Транспорт”. Эти свойства наследуются классами “Автомобиль”, “Грузовик”, “Корабль”, “Авианосец” и “Самолет”. Кроме того, свойства “Марка” и “Пробег” наследуются классом “Грузовик” от базового класса “Автомобиль”, а свойства “Нахождение” и “Водоизмещение” наследуются классом “Авианосец” от базового класса “Корабль”. Столбец Поведение (действия) позволяет проследить наследование действий. А теперь определим экземпляры классов (объекты) и значения их свойств. Таким образом, определены три экземпляра класса “Автомобиль”. Для определения экземпляров (объектов) других классов необходимо аналогичным образом задать значения свойств. Подводя итог, сделаем вывод о том, что такое объектно-информационная модель (ОИМ). ОИМ включает в себя описание иерархической системы классов, между которыми действуют отношения наследования. Для каждого класса определяется совокупность присущих ему свойств и действий (поведения), указывается, какие свойства и действия являются наследуемыми, а какие — специфическими. Для каждого объекта, входящего в ОИМ, указывается класс, элементом которого он является, а также конкретные значения свойств. Изучение объектного подхода к информационному моделированию имеет две дидактические задачи: во-первых, оно развивает системное мышление учащихся, во-вторых, имеет непосредственное отношение к современной методике программирования — объектно-ориентированному программированию. Развитие системного мышления должно происходить путем анализа знакомых и понятных для учеников систем. Например: семья, школа, городской транспорт, учебные дисциплины и пр. Основной навык, который при этом формируется, заключается в умении выделить в этих системах отдельные объекты, перечислить некоторое множество их свойств и действий (поведения). Необходимо обратить внимание учеников на тот факт, что, как любая форма модели, объектно-информационная модель включает в себя лишь часть свойств объекта и его действий, существенных с позиции целей моделирования. Поэтому для построения объектно-информационной модели в первую очередь нужно договориться о целях моделирования. Следующим важным моментом объектного моделирования является классификация объектов. Основное свойство определяемых классов — их иерархическая подчиненность. А связи между классами различных уровней иерархии реализуются через наследование свойств и поведения. Освоение программирования на объектно-ориентированных языках (С++, Delphi и др.) в школе может происходить на уровне профильного обучения в старших классах. Его отличие от традиционного процедурного программирования заключается в способе мышления, сводящемся к умению выстраивать объектно-информационные модели (иерархии классов).