Матмодели

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

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

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

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

В качестве показателей эффективности СМО используются:

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

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

- вероятность отказа обслуживания заявки ();

- среднее число занятых каналов (k);

- среднее число заявок в очереди ();

- среднее время пребывания заявки в очереди ();

- среднее число заявок, обслуживаемых в единицу времени;

- среднее время ожидания обслуживания;

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

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

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

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

Теория моделирования - это теория замещения одних объектов (оригиналов) другими объектами (моделями).

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

Модели делятся на физические и математические.

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

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

Компоненты - это такие составные части модели или системы, которые при соответствующем объединении образуют систему. Иногда компонентами системы считают ее элементы или подсистемы.

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

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

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

Экзогенные переменные - это независимые переменные (входные воздействия, воздействия внешней среды и внутренние параметры).

Эндогенные переменные - это выходные (зависимые) переменные или характеристики системы или переменные состояния.

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

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

Детерминированные соотношения - это соотношения, которые однозначно описываются входными и внешними параметрами системы.

Стохастические соотношения учитывают влияние случайных факторов.

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

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

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

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

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

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

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

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

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

Имитационная модель воспроизводит процесс функционирования системы во времени. Сущность метода имитационного моделирования состоит в реализации на ЭВМ процесса функционирования системы и получении по исходным данным сведений о ее состоянии в определенные моменты времени.

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

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

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

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

Источник – внешнее устройство, генерирующее заявки и посылающее их в систему.

Накопитель – устройство для хранения заявок в системе в течение некоторого времени.

Канал – устройство непосредственного обслуживания заявки.

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

- ожидание обслуживания;

- собственно обслуживание.

Этот процесс можно представить в виде некоторого прибора обслуживания Пi, показанного на рисунке 1, который состоит из накопителя заявок Нi и канала обслуживания заявок Кi. В накопитель поступает поток заявок wi, в канал – поток обслуживания ui. С выхода снимают поток обслуженных заявок yi.

,

где – время пребывания заявки в накопителе.

Минимальное число заявок, находящихся в системе – минимальное число заявок в системе в данный момент времени, после первой обслуженной заявки: