23414

Формалізація та моделювання

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2013-08-05

161 KB

2 чел.

МІНІСТЕРСТВО ОСВІТИ І НАУКИ,  МОЛОДІ ТА СПОРТУ УКРАЇНИ

ДЕРЖАВНИЙ УНІВЕРСИТЕТ

ІНФОРМАЦІЙНО-КОМУНІКАЦІЙНИХ ТЕХНОЛОГІЙ

ЗАТВЕРДЖУЮ

Завідуючий кафедрою

_______________ Костік Б.Я.

       (підпис, прізвище)

“ ____ “  _________2012  року

Лекція №  2

з навчальної дисципліни __моделювання компютерних мереж 

напряму підготовки _______інформаційні технології________

освітньо-кваліфікаційного рівня ____cпеціаліст_____________

спеціальності _____ компютерні системи та мережі_________

Тема     Формалізація та моделювання

                     (повна назва лекції)

Лекція розроблена стар. викладач каф. Інф. Срочинська Г.С.

(вчена ступінь та звання,  прізвище та ініціали автора)

Обговорено на засіданні кафедри (ПМК)

Протокол № __________

“ ____ “ _____________ 2012 року

Київ


Навчальні цілі: вивчення етапів інформаційного моделювання,  основ моделювання. Види моделей.

Виховні цілі: Формування у студентів інженерно-технічного кругозору, методами  імітаційного моделювання для побудови  комп’ютерних систем та мереж, вміння ставити та вирішувати складні інженерні задачі, проводити аналіз, аргументовано робити висновки.       

Час  90 хв.

ПЛАН ПРОВЕДЕННЯ ЛЕКЦІЇ ТА РОЗРАХУНОК ЧАСУ

Вступ                                                                                                    10  хвилин

Навчальні питання

1.  Формалізація. Етапи інформаційного моделювання                      30 хвилин

(найменування питання лекції)

 2. Основи моделювання. Види моделей.______________________40 хвилин

(найменування питання лекції)

Заключення                                                                                            10  хвилин

ЛІТЕРАТУРА:

(рекомендована для студентів)

1. В.Г. Кривуца, В.В. Барковський, Л.Н. Беркман. Математичне моделювання телекомунікаційних систем: Навч. посібник. –К.: Звязок, 2007.

НАВЧАЛЬНО-МАТЕРІАЛЬНЕ ЗАБЕЗПЕЧЕННЯ

(наочні посібники, схеми, таблиці, ТЗН та інше)

Діапроектор, дидактичні слайди


НАВЧАЛЬНІ МАТЕРІАЛИ

Вступ

Дисципліна «Моделювання комп’ютерних мереж»   забезпечує професійну підготовку студентів за фахом  «Компютерні системи та мережі».

        Метою вивчення дисципліни є формування у студентів системи знань, навичок і умінь по основних принципах побудови і проектуванні вивчення імітаційної моделі персонального комп’ютера; технологічних етапів випробування та експлуатації імітаційних моделей.

І. ТЕКСТ ЛЕКЦІЙ


1. Формализация и моделирование

Модель — это искусственно создаваемый объект, заменяющий некоторый объект реального мира (объект моделирования) и воспроизводящий ограниченное число его свойств. Понятие модели относится к фундаментальным общенаучным понятиям, а моделирование — это метод познания действительности, используемый различными науками.

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

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

Информационные модели используются при теоретических исследованиях объектов моделирования. В наше время основным инструментом информационного моделирования является компьютерная техника и информационные технологии.

Компьютерное моделирование включает в себя прогресс реализмом информационной модели на компьютере и исследование с помощью этой модели объекта моделирования проведение вычислительного эксперимента.

Формализация
К предметной области информатики относятся средства и методы компьютерного моделирования. Компьютерная модель может быть создана только на основе хорошо формализованной информационной модели. Что же такое формализация?

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

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

Но можно говорить и о другой стороне формализации применительно к компьютеру. Программа на определенном языке программирования есть формализованное представление процесса обработки данных. Это не противоречит приведенному выше определению формализованной информационной модели как совокупности знаков, поскольку машинная программа имеет знаковое представление. Компьютерная программа — это модель деятельности человека по обработке информации, сведенная к последовательности элементарных операций, которые умеет выполнять процессор ЭВМ. Поэтому программирование на ЭВМ есть формализация процесса обработки информации. А компьютер выступает в качестве формального исполнителя программы.

Этапы информационного моделирования

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

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

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

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

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


Основы моделирования. Виды моделей.

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

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

Информация — это абстракция.
Модель
— это тот объект, та система, которая позволяет облечь эту информацию в конкретное, например компьютерное, представление, содержание.
Моделирование — тот процесс, метод, который позволяет осуществлять перенос информации от реальной системы к модели и наоборот.

Модели по их назначению бывают познавательными, прагматическими и инструментальными.

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

По уровню моделирования модели бывают эмпирическими, теоретическими и смешанными.

  •  Эмпирическая — на основе эмпирических фактов, зависимостей;
  •  Теоретическая — на основе математических описаний;
  •  Смешанная или полуэмпирическая — использующая эмпирические зависимости и математические описания.

Проблема моделирования состоит из трех задач:

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


Моделирование
 

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

Моделирование 

- процесс построения, изучения и применения моделей.

Т.е. можно сказать, что

моделировaние 

- это изучение объектa путем построения и исследования его модели, осуществляемое с определенной целью и состоит в зaмене экспериментa с оригинaлом экспериментом нa модели.

Приведем наиболее важные типы моделей (моделирования) с краткими определениями, примерами.

Модель называется статической, если среди параметров, участвующих в описании модели, нет временного параметра. Статическая модель в каждый момент времени дает лишь «фотографию» системы, ее срез.

Модель динамическая, если среди параметров модели есть временной параметр, т. е. она отображает систему (процессы в системе) во времени.

Модель дискретная, если она описывает поведение системы только в дискретные моменты времени.

Модель непрерывная, если она описывает поведение системы для всех моментов времени из некоторого промежутка.

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

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

Модель теоретико-множественная, если представима с помощью некоторых множеств и отношений принадлежности им и между ними.

Модель логическая, если она представима предикатами, логическими функциями.

Модель игровая, если она описывает, реализует некоторую игровую ситуацию Между участниками игры (лицами, коалициями).

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

Модель языковая, лингвистическая, если она представлена некоторым лингвистическим объектом, формализованной языковой системой или структурой. Иногда такие модели называют вербальными, синтаксическими и т. п.

Модель визуальная, если она позволяет визуализировать отношения и связи моделируемой системы, особенно в динамике.

Модель натурная, если она есть материальная копия объекта моделирования.

Модель геометрическая, графическая, если она представима геометрическими образами и объектами.

Тип модели зависит от информационной сущности моделируемой системы, от связей и отношений ее подсистем и элементов, а не от ее физической природы.

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

Основные свойства любой модели:

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

Этапы моделирования

Прежде чем браться за какую-либо работу, нужно четко представить себе отправной и конечный пункт деятельности, а также примерные ее этапы. То же самое можно сказать и о моделировании. Отправной пункт здесь — прототип. Им может быть существующий или проектируемый объект или процесс. Конечный этап моделирования — принятие решения на основании знаний об объекте.

Цепочка выглядит следующим образом:

Прототип (объект, процесс) Моделирование Принятие решения 

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

Этап 1. Постановка задачи.

Под задачей понимается некая проблема, которую надо решить. На этапе постановки задачи необходимо:

  1.  описать задачу,
  2.  определить цели моделирования,
  3.  проанализировать объект или процесс.

Описание задачи.
Задача формулируется на обычном языке, и описание должно быть понятным. Главное здесь — определить объект моделирования и понять, что должен представлять собой результат.

Цели моделирования. 

  1.  Познание окружающего мира.
    Зачем человек создает модели? Чтобы ответить на этот вопрос, надо заглянуть в далекое прошлое. Несколько миллионов лет назад, на заре человечества, первобытные люди изучали окружающую природу, чтобы научиться противостоять природным стихиям, пользоваться природными благами, просто выживать. Накопленные знания передавались из поколения в поколение устно, позже письменно, наконец с помощью предметных моделей. Так родилась, к примеру, модель земного шара — глобус, — позволяющая получить наглядное представление о форме нашей планеты, ее вращении вокруг собственной оси и расположении материков. Такие модели позволяют понять, как устроен конкретный объект, узнать его основные свойства, установить законы его развития и взаимодействия с окружающим миром моделей.
  2.  Создание объектов с заданными свойствами (задача типа «Как сделать, чтобы...»).
    Накопив достаточно знаний, человек задал себе вопрос: «Нельзя ли создать объект с заданными свойствами и возможностями, чтобы противодействовать стихиям или ставить себе на службу природные явления?» Человек стал строить модели еще не существующих объектов. Так родились идеи создания ветряных мельниц, различных механизмов, даже обыкновенного зонтика. Многие из этих моделей стали в настоящее время реальностью. Это объекты, созданные руками человека.
  3.  Определение последствий воздействия на объект и принятие правильного решения (задача типа «Что будет, если...»: что будет, если увеличить плату за проезд в транспорте, или что произойдет, если закопать ядерные отходы в такой-то местности?)
    Например, для спасения Петербурга от постоянных наводнений, приносящих огромный ущерб, решено было возвести дамбу. При ее проектировании было построено множество моделей, в том числе и натурных, именно для того, чтобы предсказать последствия вмешательства в природу.
  4.  Эффективность управления объектом (или процессом).
    Поскольку критерии управления бывают весьма противоречивыми, то эффективным оно окажется только при условии, если будут «и волки сыты, и овцы целы». Например, нужно наладить питание в школьной столовой. С одной стороны, оно должно отвечать возрастным требованиям (калорийное, содержащее витамины и минеральные соли), с другой — нравиться большинству ребят и к тому же быть «по карману» родителям, а с третьей — технология приготовления должна соответствовать возможностям школьных столовых. Как совместить несовместимое? Построение модели поможет найти приемлемое решение.

Анализ объекта.
На этом этапе четко выделяют моделируемый объект, его основные свойства, его элементы и связи между ними. Простой пример подчиненных связей объектов — разбор предложения. Сначала выделяются главные члены (подлежащее, сказуемое), затем второстепенные члены, относящиеся к главным, затем слова, относящиеся к второстепенным, и т. д.

Этап 2. Разработка модели.

Информационная модель.
На этом этапе выясняются свойства, состояния, действия и другие характеристики элементарных объектов в любой форме: устно, в виде схем, таблиц. Формируется представление об элементарных объектах, составляющих исходный объект, т. е. информационная модель. Модели должны отражать наиболее существенные признаки, свойства, состояния и отношения объектов предметного мира. Именно они дают полную информацию об объекте.

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

Например, в школе учащиеся знакомятся с информационной моделью кровообращения. Предлагаемой в учебнике анатомии информации достаточно для школьника, но мало для тех, кто проводит операции на сосудах в больницах.
Информационные модели играют очень важную роль в жизни человека.
Знания, получаемые вами в школе, имеют вид информационной модели, цель которой — изучение предметов и явлений.
Уроки истории дают возможность построить модель развития общества, а знание этой модели позволяет строить собственную жизнь, либо повторяя ошибки предков, либо учитывая их.
На уроках географии вам сообщают информацию о географических объектах: горах, реках, странах и др. Это тоже информационные модели. Многое, о чем рассказывается на занятиях по географии, вы никогда не увидите в реальности.
На уроках химии информация о свойствах разных веществ и законах их взаимодействия подкрепляется опытами, которые есть не что иное, как реальные модели химических процессов.
Информационная модель никогда не характеризует объект полностью. Для одного и того же объекта можно построить различные информационные модели.

Другой пример различных информационных моделей для одного и того же объекта

Выбор наиболее существенной информации при создании информационной модели и сложность этой модели обусловлены целью моделирования.

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

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

Компьютерная модель

— это модель, реализованная средствами программной среды.

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

Основные функции компьютера при моделировании систем:

  •  исполнение роли вспомогательного средства для решения задач, решаемых и обычными вычислительными средствами, алгоритмами, технологиями;
  •  исполнение роли средства постановки и решения новых задач, не решаемых традиционными средствами, алгоритмами, технологиями;
  •  исполнение роли средства конструирования компьютерных обучающих и моделирующих сред типа: «обучаемый — компьютер — обучающий», «обучающий — компьютер — обучаемый», «обучающий — компьютер — группа обучаемых», «группа обучаемых — компьютер — обучающий», «компьютер — обучаемый — компьютер»;
  •  исполнение роли средства моделирования для получения новых знаний;
  •  «обучение» новых моделей (самообучение моделей).

Этап 3. Компьютерный эксперимент.

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

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

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

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

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

С развитием вычислительной техники появился новый уникальный метод исследования — компьютерный эксперимент. Компьютерный эксперимент включает некоторую последовательность работы с моделью, совокупность целенаправленных действий пользователя над компьютерной моделью.

Этап 4. Анализ результатов моделирования.

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

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


Разновидности задач моделирования и подходов к их
                                                решению

Задачи моделирования делятся на две категории: прямые и обратные.

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

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

Остановимся на обратных задачах. Если число допустимых вариантов решения невелико, то можно вычислить критерий эффектности для каждого из них, сравнить между собой полученные значения и непосредственно указать один или несколько оптимальных вариантов. Такой способ нахождения оптимального решения называется "простым перебором". Однако. Когда число допустимых вариантов решения велико, то поиск оптимального решения простым перебором затруднителен, а зачастую практически невозможен. В этих случаях применяются методы "направленного" перебора, обладающие той особенностью, что оптимальное решение находится рядом последовательных попыток или приближений, из которых каждое последующие приближает нас к искомому оптимальному.

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

Их можно разделить на:

принятие решений в условиях определенности - исходные данные - детерминированные; принятие решений в условиях неопределенности - исходные данные - случайные величины.

Классификация задач оптимизации

Исходные данные

Переменные

Зависимости

Задача

Детерминированные

Непрерывные

Линейные

Линейного программирования

Целочисленные

Линейные

Целочисленного программирования

Непрерывные, целочисленные

Нелинейные

Нелинейного программирования

Случайные

Непрерывные

Линейные

Стохастическое программирование

А по критерию эффективности:

одноцелевое принятие решений (один критерий эффективности);

многоцелевое принятие решений (несколько критериев эффективности).

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

В общем виде обратная детерминированная задача будет выглядеть следующим образом.

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

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

Очень часто реальные задачи содержит помимо выше перечисленных факторов, еще одну группу - неизвестные факторы. Тогда обратную задачу можно сформулировать следующим образом. 

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

Это уже другая, не чисто математическая задача (недаром в ее формулировке сделана оговорка "по возможности"). Наличие неопределенных факторов переводит эту задачу в новое качество: она превращается в задачу о выборе решений в условиях неопределенности.

Приведем примеры.

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

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

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

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

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

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

Прежде всего нужно выбрать показатель эффективности F. Разумеется, желательно, чтобы время ожидания врача было минимальным. Но время величина случайная и если применить "оптимизацию в среднем", то надо выбрать тот алгоритм, при котором время ожидания минимально.

Но дело в том, что время ожидания врача отдельными больными не суммируется: слишком долгое ожидание одного из них не компенсируется почти мгновенным обслуживанием другого. Чтобы избежать таких неприятностей, можно дополнить показатель эффективности добавочными требованиями, чтобы фактическое время ожидания врача было не больше какого предельного значения f0. Поскольку время ожидания величина случайная, нельзя просто потребовать, чтобы выполнялось условие F≤ f0, но можно потребовать, чтобы это условие выполнялось с большой вероятностью, настолько большой, чтобы событие F≤ f0 было практически достоверным. Пусть k=0,995 и потребуем, чтобы вероятность P(F≤ f0 ) ≥ k.

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

Особенно осторожными надо быть с "оптимизацией в среднем", когда речь идет об единичной операции.

Кроме рассмотренных выше, бывают задачи, когда неизвестные факторы не могут быть изучены и описаны статистическими методами. Это бывает в двух случаях:

  •  распределение вероятностей для параметров в принципе существует, но к моменту принятия решения не может быть получено;
  •  распределение вероятностей для параметров вообще не существует.

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

Заключення

Методы математического программирования.

Выше уже упоминалось о самых простых - детерминированных и одноцелевых задачах, исследованием которых занимается математическое программирование. Слово программирование в данном случае означает "планирование".

К математическому программированию относится:

  1.  Линейное программирование: состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные;
  2.  Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями;
  3.  Особым случаем в задачах линейного и нелинейного программирования является случай, когда на оптимальные решения накладывается условие целочисленности. Такие задачи относятся к целочисленному программированию;
  4.  Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом;
  5.  Теория графов: с помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д.
  6.  Стохастическое линейное программирование
    Бывает много практических ситуаций, когда коэффициенты
    ci целевой функции, коэффициенты aij в матрице коэффициентов, коэффициенты ограничений bi - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования.
  7.  Геометрическое программирование
    Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.
  8.  Задачами теории массового обслуживания является анализ и исследование явлений, возникающих в системах обслуживания. Одна из основных задач теории заключается в определении таких характеристик системы, которые обеспечивают заданное качество функционирования, например, минимум времени ожидания, минимум средней длины очереди.
  9.  Теория игр пытается математически объяснить явления возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой.

        

II. МЕТОДИЧНІ ВКАЗІВКИ

           Дисципліна “ Моделювання комп’ютерних мереж”- це теоретичні основи принципів вивчення основних понять імітаційного моделювання, ознайомлення з поняттями системи та моделі, співвідношенням між моделлю та системою, класифікацією  моделей,  видами  моделей, технологію моделювання; побудовою  імітаційної моделі персонального комп’ютера; технологічних етапів випробування та експлуатації імітаційних моделей.

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

Самостійна робота студента по підготовці до поточних занять, модульного контролю в межах відведеного часу планується особисто кожним студентом.

III. ВИКОРИСТАНА ЛІТЕРАТУРА

1. В.Г. Кривуца, В.В. Барковський, Л.Н. Беркман. Математичне моделювання телекомунікаційних систем: Навч. посібник. –К.: Звязок, 2007.

Розробник лекції   старший викладач кафедри інфокомунікацій

___                          Срочинська Г.С.

(підпис, прізвище)

“ ____ “  _____________  2012  року


 

А также другие работы, которые могут Вас заинтересовать

55137. Порівняння стилів програмування 114 KB
  Стиль Олмана llmn Названий за іменем Еріка Олмана хакера з Берклі який написав у такому стилі багато утиліт для BSD. Стиль GNU Використовується у вихідних кодах проекту по розробці вільного програмного забезпечення GNU.
55138. Основні напрями регулювання ринку праці, зайнятості та умов праці. Законодавчо-нормативна база в галузі працевлаштування випускників вищих навчальних закладів 82 KB
  Сутність основних понять розмір середньої заробітньої плати; розмір допомоги по безробіттю; який вітсоток людей працює в малому бізнесі на Україні і яка ця статистика за кордоном; які галузі мають місце в малому бізнесі і яка максимальна можлива чисельність на нах працівникі...
55140. Технологія роботи з операційною системою Windows 216.5 KB
  Мета: Формування умінь та навичок по завантаженню ОС Windows користування мишею керування вікнами. Постановка загальної проблеми: Як запускати користуватися мишею керувати вікнами в операційній системі Windows І. Короткі теоретичні відомості Windows.
55141. Культура фахового спілкування 41.5 KB
  Яку роль виконує наголос у слові Як правильно наголошувати іменники на ання читання завдання Як правильно наголошувати слово ненависть і похідні: ненавидіти ненависник ненависництво ненависницький Як наголошуються префіксальні іменники задум припис розвідка...
55142. Экономический рост: сущность, типы, факторы 20.13 KB
  Под экономическим ростом понимаются долговременные изменения реального объема национального производства, связанные с развитием производительных сил в долгосрочном временном интервале.
55143. Теория экономического роста и экономического цикла 40.5 KB
  Несмотря на стремление к достижению экономического равновесия, экономика любой страны подвержена спадам и подъемам, т. е. испытывает циклические колебания. Теория экономических циклов как теория «больших волн» в экономике была разработана в 30-е годы XX века.
55144. Характер экономического цикла. Виды экономических циклов 21.31 KB
  Экономические циклы — циклические изменения экономической конъюнктуры, регулярные колебания уровня деловой активности от экономического подъема (бума) до спада (экономической депрессии).
55145. Антициклическое регулирование экономики 21.39 KB
  В экономической литературе существуют разные подходы к этому вопросу. Борьба с разными перепадами экономической конъюнктуры – это самая трудная из проблем, которые приходится сегодня решать правительствам.