Российский государственный университет им. И. Канта Математический

моделирования и информационных систем
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Александр Васильевич Колесников
доктор технический наук, профессор
Калининград,

(1916 г.).


2) Работы по теории массового обслуживания Эрланга,

концепцией индустриального общества и с разработкой английскими военно-воздушными силами систем

гг. работы по исследованию операций в военной области в Англии,

социолог и политолог Д. Белл выдвинул концепцию постиндустриального общества. Он

возник системный анализ (А.А. Богданов, Л. Берталанфи, Н.Винер, Н.Н. Моисеев,

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

ИСО неразрывно связана с разработкой математических методов и моделей.

Совокупность

1939 г. «родилось» линейное программирование. Была напечатана брошюра Леонида Витальевича

Л.В. Канторович, академик АН СССР, математик, экономист, лауреат Нобелевской премии по экономике в 1975 г.

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу, названную «проблема выбора», а метод решения получил название «венгерского метода».

Л.В. Канторовича после второй мировой войны были переоткрыты на западе.

Тьяллинг Чарльз Купманс, доктор наук, профессор, американский экономист и математик, лауреат Нобелевской премии по экономике в 1975 г.

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

динамическое программирование впервые был использован в 1940-х годах Ричардом Эрнстом Беллманом (американский

Первые задачи теории массового обслуживания были рассмотрены сотрудником Копенгагенской телефонной компании, ученым Аргеном Эрлангом, в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.

Ричард Беллман
Американский математик, один из ведущих специалистов в области математики и вычислительной техники, профессор

Монте-Карло  — общее название группы численных методов, основанных на получении большого

Станислав Мартин Улам, польско-американский математик, автор метода Монте-Карло, основной разработчик водородной бомбы

Идея метода развита С. Уламом. Он предложил поставить «эксперимент» большое число раз и, таким образом, подсчитав число удачных исходов, оценить их вероятность. Он же предложил использовать компьютеры для расчётов методом Монте-Карло.

Годом рождения метода - 1949 г., когда вышла статья Метрополиса и Улама «Метод Монте-Карло». Название метода происходит от названия города в княжестве Монако, широко известного своими казино с рулеткой - самым известным генератором случайных чисел. В 1950-х годах метод использовался для расчётов при разработке водородной бомбы.

важные модели, разработанные с применением методов исследования операций:


Задачи учета,

методов исследования операций:

военные проблемы,
работа государственных органов,
городские системы,

количественных методов для обоснования решений во всех областях целенаправленной человеческой

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

является основным методологическим принципом исследования операций, который состоит в том,

одинаковыми причалами и одним прибывшим с промысла судном, которому нужно

Понятие задачи в исследовании операций

в распоряжении ЛПР имеются практически неограниченные ресурсы, то первое, что

Анализ ситуаций

"не прерывать обработку ни одного из двух судов, а поставить

Анализ ситуаций

задачи исследования операций

1. План снабжения предприятий. Есть предприятия, потребляющих известное

точки зрения формирования (постановки) целей и их реализации (достижения) наиболее

Основные понятия исследования операций

элементов решения могут фигурировать числа, векторы, функции.

Например, если составляется

Основные понятия исследования операций

элементами решения. Пределы зафиксированы с самого начала и нарушены быть

Основные понятия исследования операций

при минимальных расходах на перевозки. Показатель эффективности R — суммарные

Две задачи исследования операций Целевые функции

выборе одной из имеющихся альтернатив.
Элементы процесса принятия решений:
Задача (проблема), подлежащая

Признание необходимости решения

Восприятие и признание проблемы
Интерпретация и формулирование проблемы
Определение критериев

Этап 2. Выработка решения

Разработка альтернатив
Оценка альтернатив
Выбор альтернативы

Этап 3. Выполнение решения

Организация выполнения решения
Анализ и контроль выполнения решения
Обратная связь и корректировка

Постановка и формулировка задачи
Анализ задачи
Метод «бритва Оккама» Диаграмма сродства
Древовидная диаграмма

Диаграмма

Формулировка ограничений, критериев и выявление альтернатив

Сбор данных

Интерпретация данных

Поиск решения

Контрольные листки

Диаграммы Парето Гистограммы

Анализ силового поля
Модифицированный метод Дельфи
Обмен мнениями
Коллажи и фантазии
Матричная диаграмма

Анализ эффективности решений и окончательный выбор

Презентация результатов

Реализация решения

Мониторинг и оценка результатов

Логическая диаграмма
Стрелочная диаграмма

часто используют метафору потока, чтобы описать ощущение легкости при выполнении

Психология принятия решений

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

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

Ап Дейкстергюйс из университета Амстердама поставил опыт. Испытуемые были разделены на три группы. У задачи был правильный ответ – критерии выбора были известны и одна из квартир была лучше других.

Психология принятия решений

который показывает успешность в зависимости от уровня мотивации на задачах

Притча о наказании наградой: “Каждый день одного пожилого человека оскорбляла ватага десятилетних мальчишек, которые проходили мимо его дома по дороге в школу. Однажды он вышел к ним и сказал: “Завтра за каждое ругательство в мой адрес я дам вам доллар!”. Мальчишки пришли назавтра и он выполнил свое обещание. Расплатившись, он сказал: “Приходите завтра еще, я буду давать вам по 25 центов”. Завтра повторилась та же история. На следующий день он пообещал им по центу. “По центу?” – возмутились мальчишки. “Мы не будем заниматься этим за цент!” Больше они никогда не приходили. Лишняя мотивация мешает.  

Психология принятия решений

семеркой:
где t - постановка задачи (например, выбрать одну наилучшую в

метод оптимизации моделей, в которых целевые функции и ограничения строго

Пример. Пусть есть компания, которая производит краску для внутренних и наружных работ из двух видов сырья: M1 и M2. Компания ограничила ежедневное производство краски для внутренних работ до 2 т, так как нет спроса и приняла решение: производство краски для внутренних работ не должно превышать производство краски для наружных работ более чем на одну тонну. Требуется найти оптимальное соотношение между видами выпускаемой продукции для максимизации ежедневного дохода.

любая задача ИСО, включает три основных элемента.
Переменные, которые следует определить.
Целевая

Шаг 1. Определение переменных.
В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели:

-ежедневный объем производства краски для наружных работ, т;

-ежедневный объем производства краски для внутренних работ, т;

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

В соответствии с целями компании получаем задачу:

Линейное программирование
Геометрический смысл задачи линейного программирования

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

Из таблицы имеем:

Линейное программирование
Геометрический смысл задачи линейного программирования

и 6 тоннами, получим следующие ограничения:
Есть еще два ограничения по

Второе ограничение: максимальный ежедневный обюъем производства краски для внутренних работ не должен превышать 2 т :

Еще одно ограничение: переменные и должны быть неотрицательными (условие неотрицательности переменных):

Линейное программирование
Геометрический смысл задачи линейного программирования

ограничениям модели называется допустимым. Например, решение

Линейное программирование
Геометрический смысл задачи линейного программирования

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

Графический способ решения задач линейного программирования

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

допустимых решений
Шаг 1. Проведем оси: на оси абсцисс будем указывать

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

Шаг 3. Отобразим графически остальные ограничения. Для этого заменим неравенства равенствами, получим уравнения прямых и построим по этим уравнениям прямые.

Шаг 4. Рассматриваем как графически интерпретируются неравенства. Каждое из них делит плоскость ( ) на две полуплоскости, которые располагаются по обе стороны от прямой. Точки, расположенные по одну сторону от прямой – удовлетворяют неравенству, а по другую сторону – нет.

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

линейного программирования
Случай максимизации целевой функции
Поиск оптимального допустимого решения

допустимого решения
Шаг 1. Определение направления возрастания целевой функции. Для этого

допустимого решения
Оптимальное решение соответствует точке С. Эта точка – место

Решением этой системы будет . При этом значение целевой функции равно

Полученное решение означает, что для компании оптимальным выбором будет ежедневное производство 23 т краски для наружных работ и 1,5 т – для внутренних работ с ежедневным доходом в 21000 руб.

производит 800 кг добавки – смеси кукурузной и соевой муки.

состоит только из кукурузной муки, определим следующие переменные:
- количество кукурузной

- количество соевой муки, используемой в дневном производстве добавки, кг.;

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

в пищевой добавке. Общее количество белка в смеси, состоящей из

Аналогично строится ограничение для клетчатки:

Далее нужно переменные из правых частей неравенств перенести в левые части.

этом параметры модели: коэффициенты целевой функции и неравенств ограничений предполагаются

функции задачи ЛП с двумя переменными:

означает, что текущий уровень ресурса М1может быть уменьшен не более

функции, соответствующего интервалу осуществимости, деленное на значение интервала осуществимости

что оптимальное решение всегда находится в угловой точке ОДР .

Применение СМ требует преобразования зада ЛП к стандартной форме.

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

Преобразование неравенств в равенства

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

обе части это равенства на -1 , получим равенство с

программирования

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

Имеем:

угловых точек.

На рисунке видны только четыре точки: А, В,С и D. Есть и точки E и F. Но это недопустимые угловые точки. Они не рассматриваются при поиск оптимума.

Стандартная форма задач линейного программирования
Пример

Комбинаторное число сочетаний из n по m .

переменные – переменные в количестве n – m , которые

Базисные переменные – переменные в количестве m , которые доставляют системе уравнений единственное решение

Базисное решение – совокупность базисных переменных.

Допустимое базисное решение – неотрицательное базисное решение.

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

систем уравнений порядка 10 х 10.

Задачи ЛП размерности 10 х 20 считаются небольшими. Реальные задачи имеют сотни и тысячи переменных. Симплекс-метод частично снимает эту проблему, т.к. рассматривает не все базисные решения (угловые точки ОДР), а только часть допустимых базисных решений.

D → C идут вдоль границ ОДР. Причина: симплекс-метод не

точке ОДР
Исключаемая переменная -

задачу ЛП в стандартной форме:
Представим целевую функцию в виде:

Йордан)
Ведущий столбец
Ведущая строка
Ведущий столбец ассоциируется с вводимой переменной.
Ведущая строка ассоциируется

Текущая z- строка

из двух этапов:
Вычисление элементов новой ведущей строки:
Новая ведущая строка

Определим по таблице уравнение целевой функции

Ведущий столбец

Ведущая строка

Новая ведущая строка

Новая z- строка

строка

ведущей строки:

Новая ведущая - строка =

Расчеты для одного шага вычислений нового базисного решения методом Гаусса-Жордано

«Базис» и «решения» получить новое решение, соответствующее точке С .
Определение

коэффициентов, соответствующих небазисным переменным

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

быть полезна при интерпретации результатов решения задачи. Эти сведения также

С вычислительной точки зрения вырожденность может привести к зацикливанию. С теоретической точки зрения вероятность зацикливания в задачах ЛП, решаемых симплекс-методом очень мала.

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

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

Математически можно найти все точки отрезка ВС как взвешенное среднее.

явление возникает, когда в задаче ЛП имеет место не ограниченная

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

возникает, если ограничения задачи ЛП несовместимы, т.е. не могут выполняться

Псевдооптимальное решение

задача - это задача, формулируемая с помощью определенных правил непосредственно

Максимизировать или минимизировать целевую функцию

При ограничениях:

В состав n переменных входят и дополнительные переменные.
Стандартная форма задач ЛП приводит к стандартной таблице симплекс-метода.

формируются путем симметричных структурных преобразований прямой задачи по следующим правилам.

Каждому

двойственную задачу

ограничениях
Минимизировать
Пример прямой и двойственной задачи
(избыточное условие)

ЛП будет прямая задача.
Поэтому симплекс-метод симметричен относительно прямой и двойственной

задачи значения (конечные) их целевых функций удовлетворяют неравенству
Иными словами –

алгоритмы

(X) = 0.
По склону горы идет дорога, требуется найти на

Толстая линия – это дорога. Точка М, в которой дорога касается одной линий уровня, - это и есть наивысшая точка дороги. Если – точка плотности, и – её координаты, то задаче можно придать следующую форму. Пусть f (Х) — высота точки Х над уровнем моря, а уравнение g ( X) = 0 описывает дорогу. Тогда наивысшая точка дороги - решение задачи.

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

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

Метод множителей Лагранжа
Простой пример

“исправить” рельеф местности так, чтобы отклонение от дороги не давало

Теперь, поскольку рельеф L (X) делает площадку в окрестности точки оптимума горизонтальной, эта точка удовлетворяет равенствам




а так как точка лежит на дороге, то – и ограничению g ( X) = 0.

Метод множителей Лагранжа
Простой пример

Разрез горы по АВ

- весовые коэффициенты.

Метод штрафных функций

до тех пор, пока не получат приемлемое решение.
Координаты последующей точки

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

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

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

Метод штрафных функций

задаваемой этой функцией, а его модуль равен частной производной этой

Понятие градиента

оператор набла

1. Находим частные производные функции F :

2. Вычисляем частные производные в точке A (2, 1 ,1):

3. Вычисляем градиент функции F в точке А (2, 1, 1) :

Понятие градиента

вычислений.
Находят по всем переменным частные производные от целевой функции и

Метод штрафных функций

уровня для целевой функции. Этими линиями служат окружности в центром

Метод штрафных функций

задачи и линии уровня для целевой функции. Этими линиями служат

12 итераций, видим, что они с точностью до 0,1 совпадают.

Пример

Метод штрафных функций

Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ

Ричард Беллман
Американский математик, один из ведущих специалистов в области математики и вычислительной техники, профессор

задачи путем ее декомпозиции на n этапов, каждый из которых

Рекуррентная природа вычислений в динамическом программировании

Вычисления в ДП рекуррентные в том смысле, что оптимальное решение одной подзадачи – исходные данные для следующей. Решение последней задачи – оптимальное решение исходной задачи.

и позволяющий заменить решение одной большой задачи решением серии меньших

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

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

городами (городами 1 и 7) Сеть дорог на рисунке –

1

2

3

4

5

6

7

7

8

5

12

8

9

10

13

9

6

Начало пути

Конец пути

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

ее на этапы. Вертикальные пунктирные линии на рисунке выделяют три

Декомпозиция исходной задачи на части

постепенно накапливаемых расстояний ко всем вершинам этапа с последующим использованием

Переходим к этапу 2 вычисления кратчайших (накопленных) расстояний к вершинам 5 и 6. Рассматриваем вершину 5 первой. Есть 3 маршрута для достижения вершины 5: (2,5), (3,5) и (4,5). Эта информация вместе с кратчайшими расстояниями к узлам 2, 3 и 4 определяет кратчайшее (накопленное) расстояние к вершине 5 следующим образом:

вершины 4 в вершину 5 – 12 км;

Последний шаг – третий этап. Конечную вершину 7 можно достичь из вершин 5 и 6. Используя итоговые результаты этапа 2 и расстояния от вершин 5 и6 к вершине 7, получим

Этап 3. Итоговые результаты:
Кратчайший путь к вершине 7 равен 21 км (из вершины 5);

Кратчайшее расстояние между вершинами 1 и 7 равно 21 км.

Из итоговых результатов 3 этапа следует, что вершина 7 связывается

1

2

3

4

5

6

7

8

5

12

8

9

7

13

2

3

4

5

6

7

9

6

0

7

8

5

7

8

5

12

17

12

17

21

Этап 1

Этап 2

Этап 3

1 ← 4

4 ← 5

5 ← 7

Динамическое программирование

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

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

до третьего раскрывает суть алгоритма прямой прогонки. Известен и алгоритм

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

где для . Последовательность вычислений .

Алгоритм обратной прогонки

связан с узлами 5 и

1

2

3

4

5

6

7

8

5

12

8

9

7

13

2

3

4

5

6

7

9

6

Этап 3

Алгоритм обратной прогонки

не рассматривается. Используя значения

1

2

3

4

5

6

7

8

5

12

8

9

7

13

2

3

4

5

6

7

9

6

Этап 2

Оптимальное решение 2 этапа означает: «Если Вы находитесь в вершине 2 или 4, кратчайший путь к вершине 7 проходит через узел 5, а если в вершине 3 – через вершину 6.

Алгоритм обратной прогонки

(1,3) и (1,4). Используя значения

Оптимальное решение на первом этапе показывает, что кратчайший путь проходит через вершину1. Далее из оптимального решения на этапе 2 следует, что из города 4 нужно двигаться в город 5. Из оптимального решения на этапе 3 следует, что вершина 5 связана с вершиной 7. Следовательно, полным маршрутом с кратчайшей длиной, является 1→4 →5 →7 и его длина – 21 км.

Алгоритм обратной прогонки

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

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

Экстремальная точка функции определяет либо ее максимальное, либо минимальное значение. С математической точки зрения точка
является точкой максимума функции , если неравенство
выполняется для всех , таких, что
достаточно малы при всех других j . Другими словами, точка является точкой максимума, если значения функции в окрестности точки не превышают
. Аналогично точка является точкой минимума функции , если для определенного выше вектора h имеет место неравенство

оптимизации
Методы имитирующие интеллект роя

полиномиальной аппроксимации

Нелдера-Мида
Метод случайного поиска
Метод сопряженных градиентов
Метод Флетчера-Ривса
Метод Ньютона
Метод переменной метрики
Метод Девидсона-Флетчера-Пауэла

эволюционные алгоритмы
Генетические алгоритмы для многокритериальной оптимизации

роя частиц  (англ.  Particle swarm optimization).
3. Пчелиный алгоритм (англ.  Bees algorithm).
4.

случаях овражных функций, так, к примеру, в случае функции Розенброка.

испытаниям естественных процессов наследования, происходящих в мире живых организмов, а

Джон Генри Холланд,
американский ученый, отец генетических алгоритмов

эволюция происходит на хромосомах, а не на живых существах. Holland

Классические генетические алгоритмы

Решение оптимизационной задачи классическим генетическим алгоритмом
Простейшая система управления

. Пространство поиска будет содержать конечное множество точек,

Первые десять генов каждого индивидуума соответствуют параметру , а остальные десять - параметру . Длина индивидуума, таким образом, равна 20.

Популяция, хромосомы, гены, генотип, фенотип

Он состоит из следующих шагов: 1) инициализации, т.е. выбора начальной

Блок-схема классического генетического алгоритма

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



Оценка приспособленности индивидуумов

Описание блок-схемы классического ГА

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

При этом обозначает значение функции оценки индивидуума , а - вероятность выбора индивидуума .

Описание блок-схемы классического ГА

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

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

Описание блок-схемы классического ГА

селекции, используется для создания новой популяции потомков. В классическом ГА

Описание блок-схемы классического ГА

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

Описание блок-схемы классического ГА

изменяется на противоположное (0 → 1 или 1 → 0).

Описание блок-схемы классического ГА

большим числом единиц. Предположим, что индивидуум состоит из 12 генов,

Пример работы классического ГА

единиц в индивидууме. Обозначим функцию оценки через

Пример работы классического ГА

текущей популяции (N = 8) имеем сектора колеса рулетки, выраженные

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

Пример работы классического ГА

оператора селекции, не мутируют, а подлежат скрещиванию. Это означает, что

Пример работы классического ГА

Пример работы классического ГА

- стохастические. Попытка их математического описания с помощью детерминистических моделей

связанную с большим числом абонентов. Телефонистки станции по мере поступления

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

величина «Время обслуживания заявки прибором»
Понятие СМО

называют потоком требований.

Поток требований, поступающих в обслуживающую систему, называют входящим

Определения, термины

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

По характеру организации:
с

Классификация СМО

на входе СМО, производительностью одного канала, числом каналов и эффективностью

Основная задача теории массового обслуживания

обслуживания (СМО) задается следующими свойствами. СМО имеет канал. В СМО приходят заявки.

которых следующие:
- коэффициент загрузки  ρ;
- средняя длина очереди  L ;
-

Пуассоновский поток событий

Цель анализа СМО

этого требования состоит в том, чтобы «скорость поступления работы» в

Расчет коэффициента загрузки СМО

поступающих в СМО в единицу времени, равно среднему числу заявок,

Расчет коэффициента загрузки СМО

значение той части единицы времени, в течение которой канал занят;
б)

Далее рассматриваем только стационарные значения  характеристик.
Средняя длина очереди L (среднее число заявок в очереди) в одноканальной экспоненциальной СМО рассчитывается по формуле:
       

График зависимости L(ρ) приведен на рисунке. Среднее число M заявок в СМО равно сумме среднего числа L заявок в очереди и среднего числа r заявок в канале:

где r - среднее число заявок в канале.

Средняя длина очереди

ожидания обслуживания через среднюю длину очереди:

                                                         

Аналогично вычисляется среднее время

Применение формулы Литтла