Введение в математическое моделирование

Дисциплина: Математические методы в решении профессиональных задач Лекция № 3 Введение в математическое моделирование Тема 1 Основы теории принятия решений 3. Литература: 1. Беляков, С. А., Борисов, В. И., Шумов, В. В. Введение в погранометрику. – М.: Пограничная академия ФСБ России, 2012. 2. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. - М.: Дрофа, 2004. 3. Кучков А.Ф., Лукашевич Н.Ф., Попов Г.П., Шумов В.В. Математическое моделирование служебно-боевых действий пограничных войск: Учебник. - М.: ФПС России, 1996. 4. Учебные вопросы и расчет времени Содержание Время, мин Вступительная часть 5 Учебные вопросы (основная часть) 80 1. Классификация математических моделей 30 2. Основы применения математических моделей 50 Заключительная часть 5 Текст лекции № 1. Классификация математических моделей Моделирование – процесс, посредством которого исследова­тель стремится понять определенные аспекты реальной жизни. Модель не является точной копией реальности, а представляет со­бой упрощенный ее вариант, согласованный с задачами исследова­теля. Один и тот же объект в зависимости от целей исследования может иметь разные модели. Например, моделью человека может являться кукла, мешок с песком (100 кг) при испытании парашюта, ватный макет с большим числом датчиков при испытании противоударных средств в автомобиле, манекен при моделировании одежды и т.д.. С моделями мы часто встречаемся в обычной жизни, возможно, не подозревая, что это модели. В дальнейшем под моделированием мы будем понимать тео­ретические модели реальности, а не процесс изготовления моде­лей каких-либо предметов, например самолетов. Процесс моделирования – это скорее искусство, чем наука. Тем не менее, он предполагает некоторые вполне определенные этапы. Моделирование – это прежде всего умение выделить главное. Модели должны быть по возможности простыми, однако они должны включать все самые важные части исследуе­мой системы (оригинала), самые важные функции и самые важ­ные связи, внутрисистемные и внешние. Но таких элементов, выбранных для последующего детального исследования, долж­но быть ограниченное, небольшое количество, иначе будет трудно вести анализ. Для того чтобы найти главные части и связи системы, следует сосредоточить внимание на трех важных моментах: 1. Определить главную цель системы, ответив на вопросы о том, зачем существует система и какие главные функции она выполняет. 2. Понять работу системы и определить главные части (под­системы), участвующие в выполнении главной функции. 3. Установить важные связи между этими частями. При этом связи и части системы будут действительно важными, если после их исключения из нее система «рассыпается». И наоборот, если мы исключили какую-то часть или связь и ничего не изменилось, то это не главная часть или, соответственно, не важная связь. Математической моделью называется математическое описание какого-либо процесса. Под математическим моделированием понимают способ исследования различных процессов, действий, операций путем изучения явлений, описываемых математическими зависимостями. Следует отметить, что рецептов построения хорошей модели не существует. Известный американский ученый Р. Шэннон ука­зывал, что «любой набор правил для разработки моделей, в луч­шем случае имеет ограниченную полезность и может служить лишь предположительно в качестве каркаса будущей модели или отправного пункта в ее построении». Кроме того, следует иметь в виду, что модель, успешно применяемая в одних случаях, в других может оказаться бесполезной. «Культура моделирования требует, чтобы для каждой модели был указан перечень условий, при которых данная модель верна. От модели не требуется истинность. Модель должна быть адекватной, работо­способной, т.е. давать удовлетворительные ответы на поставленные вопросы». Если модель не дает ответ на поставленный вопрос, то она уточняется или заменяется новой. В экономической теории часто используется линейная модель спроса и предложения. Несмотря на свою предельную простоту (в реальности кривые спроса и предложения вряд ли бывают прямыми линиями), она дает ответы на многие экономические вопросы: установление рыночного равновесия, определение равновесной цены, изменение спроса, изменений предложения и т.д. Когда же модель спроса и предложения не дает ответы на поставленные вопросы, она уточняется или заменяется новой. В этом случае, возможно, обращаются к более сложному для исследования варианту модели, где кривые спроса и предложения представляются нелинейными функциями. Научиться моделированию, ограничившись только формальным усвоением каких-то правил, конечно, невозможно. Но все же есть со­веты, к которым стоит прислушаться. Например, к советам академика Ю.И. Неймарка. Они достаточно общие и не могут служить непосредственным указанием к действию, но дают разумные подсказки, что и как следует делать: 1. Чем проще модель, тем меньше возможность ошибочных выводов. 2. Модель должна быть простой, но не проще, чем это воз­можно. 3. Пренебрегать можно чем угодно, нужно только знать, как это повлияет на решение. 4. Модель должна быть грубой: малые поправки не должны кардинально менять ее поведение. 5. Модель и расчет не должны быть точнее исходных данных. Основные принципы построения математической модели 1. Необходимо соизмерять точность и подробность модели, во-первых, с точностью тех исходных данных, которыми располагает исследователь, и, во-вторых, с теми результатами, которые требуется получить. 2. Математическая модель должна отражать существенные черты исследуемого явления и при этом не должна его сильно упрощать. 3. Математическая модель не может быть полностью адекватна реальному явлению, поэтому для его исследования лучше использовать несколько моделей, для построения которых применены разные матема­тические методы. Если при этом получаются сходные результаты, то исследование заканчивается. Если результаты сильно различаются, то следует пересмотреть постановку задачи. 4. Любая сложная система всегда подвергается малым внешним и внут­ренним воздействиям, следовательно, математическая модель должна быть устойчивой, т.е. сохранять свои свойства и структуру при этих воздействиях. Классификация математических моделей По числу критериев эффективности математические модели делятся на однокритериальные и многокритериальные (рис. 1). Многокритериальные математические модели содержат два и более критерия. По учету неизвестных факторов математические модели делятся на детерминированные, стохастические и модели с элементами неопределенности. В стохастических моделях неизвестные факторы – это случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т. п.). Среди стохастических можно выделить: • модели стохастического программирования, в которых либо в целе­вую функцию, либо в ограничения входят случайные величины; • модели теории случайных процессов, предназначенные для изучения процессов, состояние которых в каждый момент времени является слу­чайной величиной; • модели теории массового обслуживания, в которой изучаются много­канальные системы, занятые обслуживанием требований. Также к стохас­тическим моделям можно отнести модели теории полезности, поиска и принятия решении. Для моделирования ситуаций, зависящих от факторов, для которых не­возможно собрать статистические данные, либо значения которых не опреде­лены, используются модели с элементами неопределенности. В моделях теории игр задача представляется в виде игры, в которой участвуют несколько игроков, преследующих разные цели, например организацию предприятия в условиях конкуренции. В имитационных моделях реальный процесс разворачивается в ма­шинном времени, и прослеживаются результаты случайных воздействий на него, например организация производственного процесса. В детерминированных моделях неизвестные факторы не учитываются. Несмотря на кажущуюся простоту этих моделей, к ним сводятся многие практические задачи, в том числе большинство социально-экономических задач. По виду целевой функции и ограничений детерминированные модели де­лятся на линейные, нелинейные, динамические и графические. В линейных моделях целевая функция и ограничения линейны по управляющим переменным. Построение и расчет линейных моделей яв­ляются наиболее развитым разделом математического моделирования, поэтому часто к ним стараются свести и другие задачи либо на этапе по­становки, либо в процессе решения. Для линейных моделей любого вида и достаточно большой размерности известны стандартные методы решения. Рис. 1 Нелинейные модели – это модели, в которых либо целевая функция, либо какое-нибудь из ограничений (либо все ограничения) не линейны по управляющим переменным. Для нелинейных моделей нет единого метода расчета. В зависимости от вида нелинейности, свойств функции и ограничений можно предложить различные способы решения. Однако может случиться и так, что для поставленной нелинейной задачи вообще не существует метода В этом случае задачу следует упростить, либо сведя ее к из­вестным линейным моделям, либо просто линеаризовав модель. В динамических моделях в отличие от статических линейных и нели­нейных моделей учитывается фактор времени. Критерий оптимальности в динамических моделях может быть самого общего вида (и даже вообще не быть функцией), однако для него должны выполняться определенные свойства. Расчет динамических моделей сложен, и для каждой конкретной задачи необходимо разрабатывать специальный алгоритм решения, Графические модели используются тогда, когда задачу удобно представить в виде графической структуры. Основные этапы построения модели 1. Определение цели, т.е. чего хотят добиться, решая поставленную задачу. 2. Определение параметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет. 3. Формирование управляющих переменных, изменяя значение которых можно приближаться к поставленной цели. Значения управляющих переменных являются решениями задачи. 4. Определение области допустимых решений, т.е. тех ограничений, которым должны удовлетворять управляющие переменные. 5. Выявление неизвестных факторов, т.е. величин, которые могут изменяться случайным или неопределенным образом. 6. Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.е. формирование целевой функции, называемой также критерием эффективности или критерием оптимальности задачи. Линейные модели Линейные модели имеют широкое применение при решении экономических задач, возникающих в производстве, управлении финансами, торговле, транспортной отрасли и т.д. Построение линейных моделей является наиболее развитым разделом математического моделирования.  Широкое применение линейных моделей любого вида и достаточно большой размерности подкрепляется высокоэффективными компьютерными алгоритмами. К моделям линейной оптимизации относятся задачи на максимум или минимум линейной целевой функции многих переменных при ограничениях на них в форме линейных равенств и неравенств. С любой экономико-математической задачей, для которой можно построить линейную модель, либо свести к построению линейной модели, связана двойственная задача. Прямая и двойственная задача тесно взаимосвязаны, так как оптимальное решение одной задачи можно получить непосредственно, зная оптимальное решение другой задачи. Совместное изучение прямой задачи и двойственной к ней дает, как правило, значительно больше информации. 2. Основы применения математических моделей 2.1. Математические модели линейного программирования 2.1.1. Одноиндексные задачи линейного программирования Одноиндексные задачи линейного программирования относятся к наиболее простым задачам этого типа. Такие задачи называются одноиндекскноми, т.к. неизвестные xi, включаемые в математическую модель, в обозначениях имеют одинарный индекс. Задача 1. Руководство фирмы предполагает производить продукцию двух моделей А1 и А2. Для каждого изделия модели А1 требуется 0,3 м3 древесины, 0,2 часа работы станков и затратить 1,6 денежных единиц, а для изделия модели А2 - 0,4 м3 древесины, 0,5 часа работы станков и 1 ден. ед. Фирма может получить от своих поставщиков до 170 м3 древесины в неделю и использовать оборудование в течение 160 часов. На финансирование проекта предполагается выделять 800 ден. ед. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А1 приносит 2 ден. ед. прибыли, а каждое изделие модели А2 - 4 ден. ед. прибыли? Построение математической модели Так как нужно определить объемы производства каждого вида моделей продукции, переменными в модели являются: х1 - количество выпущенных за неделю изделий модели А1, х2 - количество выпущенных за неделю изделий модели А2. Математическая модель задачи записывается: Целевая функция: max W = 2 х1 + 4 х2 (1) Ограничения: 0,3 х1 + 0,4 х2 £ 170 (2) 0,2 х1 + 0,5 х2 £ 160 (3) 1,6 х1 + х2 £ 800 (4) х1 ³ 0, х2 ³ 0 (5) Составление математической модели и решение задачи рассмотрим на занятиях по теме 2. 2.1.2. Двухиндексные задачи линейного программирования Задача 2 (транспортная задача). Однородный груз сосредоточен у двух поставщиков в объемах a1, a2. Данный груз необходимо доставить трем потребителям в объемах b1, b2, b3. Известны стоимости перевозки единиц груза Cij от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными. Исходные данные приведены в таблице ai bj 20 30 40 Cij 40 3 5 7 50 4 6 10 Переменными (неизвестными) транспортной задачи являются xij, – объемы перевозок от i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок: Математическая модель рассматриваемой задачи записывается следующим образом: найти переменные задачи, обеспечивающие минимум целевой функции (1) и удовлетворяющие системе ограничений (2) и условиям неотрицательности (3). В данной задаче неизвестные содержат два индекса i и j, поэтому такой тип задачи относится к двухиндекскным задачам линейного программирования. 2.2. ММ нелинейного программирования Задача 3. Предприятие может выпускать два вида продукции (j = 1, 2). На ее изготовление расходуется три вида ресурсов (i = 1, 2, 3). С учетом брака расход ресурсов на единицу производимой продукции j-го вида определяется выражением , а прибыль в зависимости от объемов производства равна , где xj – искомый объем производства продукции j-го вида; aij – норма расхода i-го ресурса на производство единицы продукции j-го вида; kij – коэффициент изменения расхода соответствующего ресурса с учетом выпуска бракованных изделий; pj – прибыль от реализации единицы продукции j-го вида; lj – коэффициент изменения прибыли, влияющий на объем производства продукции j-го вида. Требуется найти такие объемы производства продукции, при которых прибыль была бы максимальной. Численные исходные данные приведены в таблице: Ресурс Нормы расхода ресурсов aij на продукцию вида j Запас ресурса Коэффициент изменения норм расхода ресурсов kij на продукцию вида j 1 2 1 2 1 15 18 1350 0,1 0,05 2 12 16 1400 0,2 0,2 3 17 14 1580 0,1 0,15 Прибыль за ед. продукции 100 120       Коэффициент изменения прибыли – 0,08 – 0,1    Математическая модель Целевая функция, которую необходимо максимизировать равна Максимум целевой функции находится при ограничениях 2.3. ММ динамического программирования Динамическое программирование – это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса. Пусть планируется деятельность группы предприятий на N лет. Здесь шагом является один год. В начале 1-го года на развитие предприятий выделяются средства, которые должны быть как-то распределены между этими предприятиями. В процессе их функционирования выделенные средства частично расходуются. Каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале года имеющиеся средства могут перераспределяться между предприятиями: каждому из них выделяется какая-то доля средств. Ставится вопрос: как в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий за N лет был максимальным? Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделение каких-то средств каждому из предприятий в начале года. УВ на каждом шаге должно выбираться с учетом всех его последствий в будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать "c заглядыванием в будущее", иначе возможны серьезные ошибки. Действительно, предположим, что в рассмотренной группе предприятий одни заняты выпуском предметов потребления, а другие производят для этого машины. Причем целью является получение за N лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя их узких интересов данного шага (года), мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема продукции. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы. 2.4. Задача массового обслуживания Большой класс систем, которые сложно изучить аналитическими способами, но которые хорошо изучаются методами статистического моделирования, сводится к системам массового обслуживания (СМО). Примерами СМО могут служить: автобусный маршрут и перевозка пассажиров; производственный конвейер по обработке деталей; влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО; ствол и рожок автомата, которые «обслуживают» патроны; электрические заряды, перемещающиеся в некотором устройстве и т. д. Пример. Автозаправочная станция (АЗС). Постановка задачи. На рис. приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час. На АЗС две одинаковые колонки, статистическая производительность каждой из которых известна. Первая колонка в среднем обслуживает 1 машину в час, вторая в среднем — 3 машины в час. Владелец АЗС заасфальтировал для машин место, где они могут ожидать обслуживания. Если колонки заняты, то на этом месте могут ожидать обслуживания другие машины, но не более двух одновременно. Очередь будем считать общей. Как только одна из колонок освободится, то первая машина из очереди может занять ее место на колонке (при этом вторая машина продвигается на первое место в очереди). Если появляется третья машина, а все места (их два) в очереди заняты, то ей отказывают в обслуживании, так как стоять на дороге запрещено (см. дорожные знаки около АЗС). Такая машина уезжает прочь из системы навсегда и как потенциальный клиент является потерянной для владельца АЗС. 2.5. ММ теории игр Во многих задачах часто возникают ситуации, когда две или более сторон разрешают одну и ту же проблему, но преследуют различные цели, их интересы противоположны. Подобные ситуации называются конфликтными. Примерами таких ситуаций служат отношения между продавцом и покупателем, адвокатом и прокурором, кредитором и дебитором, истцом и ответчиком, снарядом и броней, авиацией и средствами ПВО, пограничным нарядом и НГГ и т.д. Математические методы анализа конфликтных ситуаций объединяются под названием теории игр, сама конфликтная ситуация носит название игры, а стороны, участвующие в конфликте, называются игроками. Исход игры называется выигрышем (или проигрышем) игроков. Если в игре участвуют только два игрока, то игра называется парной. Рассмотрим следующую модель. Игрок А желает принять решение, на результат которого влияет другой игрок В, цели которого противоположны А. Игрок В анализирует все возможные варианты А и принимает такое решение, которое приводит к наименьшему выигрышу А (соответственно максимальному своему выигрышу). Пример. Игрок А прячет в одной из рук монету. Игрок В пытается угадать руку с монетой. Если В не угадывает, то А получает от В 1 р. Если В угадывает руку с монетой и эта рука правая, то он получает от А 1 р. Если В находит монету в левой руке, то он получает от А 2 р. Определить оптимальные стратегии поведения для каждого игрока и средний выигрыш для А. Пусть стратегии игроков: А1 – спрятать в правой; В1 – искать в правой; А2 – спрятать в левой; В2 – искать в левой. Игровая матрица для данной ситуации относительно игрока А имеет вид:   B1 B2 A1 -1 1 A2 1 -2 Эта матрица называется платежной или матрицей игры.  2.6. Сетевая модель Сетевой моделью (другие названия: сетевой график, сеть) называется экономико-компьютерная модель, отражающая комплекс работ (операций) и событий, связанных с реализацией   некоторого проекта (научно-исследовательского, производственного и др.), в их логической  и технологической последовательности и связи.  Анализ сетевой  модели, представленной в графической или табличной (матричной) форме, позволяет:  • во-первых, более четко выявить взаимосвязи этапов реализации проекта; • во-вторых, определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ. Основные понятия сетевой модели: • событие, • работа, • путь. На рисунке графически представлена сетевая модель, состоящая из 11 событий и 16 работ, продолжительность выполнения которых указана над работами. Вопросы и задания для проверки 1. Что называется моделью, моделированием? 2. Приведите классификацию математических моделей. 3. Приведите примеры решения задач с помощью моделей линейного программирования. 4. Какие задачи могут быть решены с помощью модели массового обслуживания? 5. Приведите основные принципы построения математических моделей.