Загрузка...

Пример разработки функциональной модели. САиИО.


 Описание предметной области Информационная система «Таксопарк» предназначена для упрощения регулированием системы и  для автоматизации её функций. Таксопарк «Миг» является современным автотранспортным предприятием, которое оказывает услуги по перевозке людей на легковых автомобилях. Для состоятельных клиентов предусмотренная дополнительная услуга – VIP карта, которая позволяет накапливать скидку и оплачивать поездки со своего счета. Если поездка осуществляется одним клиентом Читать далее

Введение. Цели и задачи. Историческая справка. Значение системного анализа.


На современном этапе развития общества происходит постоянное усложнение и развитие техники, технологического производства, увеличение масштабов и темпов производства, планирование и управление. Возникающие при этом задачи требуют новых современных методов решения. Они имеют большую размерность и могут быть решены в реальных условиях только с применением ЭВМ. Изучением этих методов и задач занимаются:

Основные понятия ИО


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

Основные этапы системного анализа


-Постановка задачи: сначала формулируется заказчиком и записывается словесно. Эта постановка не является окончательной. Операционная группа проводит обследование и в результате постановка задачи корректируется.

Задачи исследования операций в условиях определенности, неопределенности и риска


Любые операционные системы обязательно содержат: 1. Лицо, которое стремится к достижению определенной цели 2. Должно существовать некоторое множество достиг. цели. 3. Существовать некоторая обстановка во время которой проводятся операции 4. Известны исходы решения 5. Существуют правила выбора решения

Многокритериальные задачи. Примеры многокритериальных задачи


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

Метод свёртывания критериев. Метод уступок.


Рассмотрим мат. Модель линейной многокритериальной задачи. В методе свёртывания критериев задаются некоторые числа так называемые веса учитывающие степень важности некоторого критерия и затем строится обобщённый критерий и затем строим обобщённый критерий Z и решаем задачу в которой для этого критерия Z будем искать max при (1) и (2).

Двойственные задачи. Теоремы двойственности. Анализ устойчивости оптимального плана производства.


1.Задача оптимального плана производства и двойственная к ней – задача нахождения оптимальных оценок ресурсов. Запишем мат. Модель задачи оптимального плана производства. З.1)

Задачи исследования операций с целочисленными переменными. Общая характеристика задач.


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

Схема метода ветвей и границ


Для решения ЗЛЦП существует 3 группы методов: 1) Методы отсечения или отсекающих плоскостей 2) Комбинаторные методы 3) Эвристические методы

Метод Ленд и Дойг


Рассмотрим математическую модель ЗЛЦП с неделимостями. Для функции (1) (найти max) при условии

Принятие решений в иерархически организованных системах


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

Метод декомпозиции Данцига- Вульфа


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

Задача Комивояжора и ее решение методом ветвей и границ


Коммивояжер (К) должен обойти N городов и вернуться в исходный город. Пронумеруем эти города 1,2….N. Известна матрица расстояний L=(lij)NN так как К из города i переходит в другой город j, то lij не существует. Если из города i нельзя переход в j то расстояние lij=?. В общем случае lij? lji. Будем предполагать что К находится Читать далее

Элементы теории графов. Задача о максимальном потоке.


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

Теорема Форда — Фалкерсона


Для любой сети G=(J, U) с одним источником S и одним стоком t величина максимального потока из S в t равна пропускной способности минимального разреза, отделяющего S от t. Дугу, входящею в некоторую цепь в сети, будем наз. прямой, если ее направление совпадает с направлением обхода вершин, и обратной – в противном случае. Дуга (i, Читать далее

Нахождение величины максимального потока в сети методом Форда — Фалкерсона


Рассмотрим сеть G=(J, U) с одним источником S и одним стоком t и для всех дуг сети (i, j) заданы их пропускные способности Cij. Найти величину максимального потока в сети, который можно направить из источника в сток и минимальный разрез в сети. Метод Форда – Фалкерсона называют еще и методом пометок. Рассмотрим его по шагам.

Задача о кротчайшем пути


Пусть из города S в город T необходимо доставить некоторый груз за кротчайшее время. Города S и T связаны между собой сетью дорог, проходящих через перевалочные пункты. Изобразим город S и T и перевалочные пункты в виде вершин некоторого графа. И каждую пару вершин i и j связываем дугой, если между ними существует прямая связь, Читать далее

Правильная нумерация вершин сети


Рассмотрим сеть G=(J,U) с одним источником S и одним стоком T. В сети n вершин. В вершину S не входит ни одна дуга, а из вершины T не выходит ни одна дуга. Пронумеровать в такой сети вершины правильно необходимо, чтобы в сети не было контуров. Рангом вершины i назовем max число дуг в пути, которое Читать далее

Метод Форда


Рассмотрим ориентированную сеть G=(I,U) без контуров, с одним источником s и стоком t. Числа на дугах lij означают их длину. найдем следующим образом: источнику т.е. вершине 1 присваиваем метку Е1=0, число 0 означает, что это кратчайший путь до источника. Вершине 2 присваиваем метку Е2=Е1+l12 . Далее последовательно будем присваивать метки вершинам 3,4,…,n по правилу: Еj=min(Ei+lij), Читать далее

Задача о минимальном связывающем дереве.Алгоритм Краскала.


Рассмотрим задачу: имеется n городов A1, … ,An, которые необходимо связать между собой сетью шоссейных или железных дорог. Для каждой пары городов AiAj известна стоимость Cij соответствующей магистрали (Сij можно рассматривать как расстояние между городами Ai и Aj). Задача состоит в том, чтобы построить самую дешевую из сетей дорог, которые связывает все эти города. Вместо Читать далее

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


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

Сетевой график и правило построения.


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

Сетевые графики


1. Пусть имеется следующий фрагмент сетевого графика и известно, что работы U2 и U3 можно начинать до полного окончания работы U1 , т. е. для начала выполнения работ U2 и U3 необх. лишь частичное выполнение работы U1 , а для начала выполнения работы U4 необходимо полное выполнение работы U1 . В этом случае работу U1 Читать далее

Сроки начала и окончания работ. Резерв времени работ


Т.к. для событий сетевого графика можно найти их ранее и позднее сроки свершения, то очевидно, что начало и окончание работ тоже могут изменятся в определенных пределах. Действительно для каждой i,j можно найти ее решение TijРН и ее позднее TijПН начало. И ее ранее и позднее окончание (TijРО TijПО). Очевидно, что ранее начало ij равно раннему Читать далее

Основные понятия теории массового обслуживания


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

Классификация систем массового обслуживания


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

Входящий поток требований и его характеристики


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

Марковские случайные процессы


Марковским процессом называется такой случайный процесс, который обладает следующим свойством: для каждого момента времени t0 вероятность любого состояния в будущем (t > t0) зависит только от его состояния в настоящем (t = t0) и не зависит от того, когда и каким образом система пришла в это состояние. Другими словами, в Марковском случайном процессе будущее его Читать далее