Математическая постановка задачи
Введение
Статистическим моделированием
называется численный метод решения
математических задач при помощи
моделирования структур процессов
и других объектов исследования с
использованием случайных величин
и случайных
Этот вид моделирования применяется в тех случаях, когда аналитические методы не применимы или требуется уточнить их точность. Основная идея статистического моделирования заключается в использовании специализированных процедур, которые генерируют случайные величины, используемые при расчётах в математической модели и дающие случайные результаты.
Использование случайных
величин и результатов
Система массового обслуживания – это, прежде всего, система, где люди работают с людьми, притом в больших количествах. Поэтому проводить анализ таких систем крайне сложно и трудозатратно т.к. вести учёт обслуживания больших масс людей очень проблематично, а порой и невозможно. Статистическое моделирование позволяет смоделировать работу системы массового обслуживания, в каких угодно масштабах и временных рамках, предоставляя удобную для анализа модель работы системы. Использование случайных чисел в расчётах позволяет получать каждый раз новую модель. Анализ нескольких моделей одной системы предоставляет широкие возможности по улучшению системы.
Основной проблемой
Но зато один раз написанная программа может моделировать огромное количество различных по параметрам моделей за очень короткое время и зачастую наглядней и удобней для анализа, чем было бы на бумаге.
Целью данной курсовой работы является построение простейшей статистической модели системы массового обслуживания и написание универсальной программы по её реализации. Для достижения этой цели в работе решены следующие задачи:
- изучен алгоритм построения простейшей модели системы массового обслуживания;
- изучены основные характеристики простейшей модели системы массового обслуживания
- выбран язык программирования, позволяющий реализовать указанную модель;
1.Математическая постановка задачи
Смоделировать работу системы массового обслуживания, поступление требований в которой подчинено пуассоновскому закону распределения со средним λ=5 клиент/час. Время обслуживания заявки равно 0.4 с вероятностью 0.5 и 0.6 с вероятностью 0.5. Моделирование закончить с поступлением 5 заявки. При моделировании использовать следующие случайные числа
0.345500
0.487110
0.811154
0.891254
0.429090
0.230243
0.595449
0.542293
0.420822
0.697501
2. Решение задачи
Теория массового обслуживания (теория очередей) — раздел теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из неё, длительности ожидания и длины очередей. В теории массового обслуживания используются методы теории вероятностей и математической статистики.
Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин.[
Первые задачи ТМО (Теории Массового Обслуживания) были рассмотрены сотрудником Копенгагенской телефонной компании, ученым Агнером Эрлангом, в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.
Имеется телефонный узел (обслуживающий прибор), на котором телефонистки время от времени соединяют отдельные номера телефонов друг с другом. Системы массового обслуживания (СМО) могут быть двух видов: с ожиданием и без ожидания (то есть с потерями). В первом случае вызов (требование, заявка), пришедший на станцию в момент, когда занята нужная линия, остается ждать момента соединения. Во втором случае он «покидает систему» и не требует забот СМО.
В СМО подразумевается, что есть типовые пути (каналы обслуживания), через которые в процессе обработки проходят заявки. Принято говорить, что заявки обслуживаются каналами. Каналы могут быть разными по назначению, характеристикам, они могут сочетаться в разных комбинациях; заявки могут находиться в очередях и ожидать обслуживания. Часть заявок может быть обслужена каналами, а части могут отказать в этом. Важно, что заявки, с точки зрения системы, абстрактны: это то, что желает обслужиться, то есть пройти определенный путь в системе. Каналы являются также абстракцией: это то, что обслуживает заявки.
Заявки могут приходить
Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.
К примеру, пусть сказано: «заявки в среднем приходят в количестве 5 штук в час». Это означает, что времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 1, но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 — но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.
| |
Рис. 1. Случайный процесс прихода заявок в СМО |
Результат (например, пропускная способность системы), конечно, тоже будет случайной величиной на отдельных промежутках времени. Но измеренная на большом промежутке времени, эта величина будет уже, в среднем, соответствовать точному решению. То есть для характеристики СМО интересуются ответами в статистическом смысле.
Итак, систему испытывают случайными входными сигналами, подчиненными заданному статистическому закону, а в качестве результата принимают статистические показатели, усредненные по времени рассмотрения или по количеству опытов.
Во-вторых, все модели СМО собираются типовым образом из небольшого набора элементов (канал, источник заявок, очередь, заявка, дисциплина обслуживания, стек, кольцо и так далее), что позволяет имитировать эти задачи типовым образом. Для этого модель системы собирают из конструктора таких элементов. Неважно, какая конкретно система изучается, важно, что схема системы собирается из одних и тех же элементов. Разумеется, структура схемы будет всегда различной.
Перечислим некоторые основные понятия СМО.
Каналы — то, что обслуживает; бывают горячие (начинают обслуживать заявку в момент ее поступления в канал) и холодные (каналу для начала обслуживания требуется время на подготовку).Источники заявок — порождают заявки в случайные моменты времени, согласно заданному пользователем статистическому закону. Заявки, они же клиенты, входят в систему (порождаются источниками заявок), проходят через ее элементы (обслуживаются), покидают ее обслуженными или неудовлетворенными. Бывают нетерпеливые заявки — такие, которым надоело ожидать или находиться в системе и которые покидают по собственной воле СМО. Заявки образуют потоки — поток заявок на входе системы, поток обслуженных заявок, поток отказанных заявок. Поток характеризуется количеством заявок определенного сорта, наблюдаемым в некотором месте СМО за единицу времени (час, сутки, месяц), то есть поток есть величина статистическая.
Очереди характеризуются правилами стояния в
очереди (дисциплиной обслуживания), количеством
мест в очереди (сколько клиентов максимум
может находиться в очереди), структурой
очереди (связь между местами в очереди).
Бывают ограниченные и неограни
Дадим яркий пример, показывающий, как правильный выбор той или иной дисциплины обслуживания позволяет получить ощутимую экономию по времени.
Пусть имеется два магазина. В магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь реализована дисциплина обслуживания FIFO (см. рис. 2.).
| |
Рис. 2. Организация очереди по дисциплине FIFO |
Время
обслуживания tобслуж. на рис.
Заявки могут поступать в систему обслуживания в соответствии с определенным графиком (один пациент на прием к стоматологу каждые пятнадцать минут, один автомобиль на конвейере каждые двадцать минут), или они появляются случайный
образом. Появления клиентов считаются случайными, если они независимы друг от друга и точно не предсказуемы. Часто в задачах массового обслуживания число появлений в единицу времени может быть оценено с помощью распределения вероятностей, известного, как пуассоновское распределение. При заданном темпе поступления (например, два клиента в час, или четыре грузовика в минуту), дискретное распределение Пуассона описывается следующей формулой:
для х = 0, 1, … ,
где р(х) — вероятность поступления х заявок в единицу времени;
х —число заявок в единицу времени;
λ — среднее число заявок в единицу времени (темп поступления заявок);
е = 2,7183 (основание натурального логарифма).
Соответствующие значения вероятностей р(х) нетрудно определить с помощью таблицы пуассоновского распределения. Например, если средний темп поступления заявок равен двум клиентам в час, то вероятность не поступления в систему в течение часа ни одной заявки равна 0,13; вероятность появления одной заявки -0,27; двух — также около 0,27; три заявки могут появиться с вероятностью 0,18; четыре — с вероятностью около 0,9 и т.д. Вероятность того, что за час в систему поступят 9 и более заявок близка нулю.
На практике вероятности появления заявок не всегда подчиняются пуассоновскому распределению. Поэтому, сначала следует провести предварительное исследование, будет ли пуассоновское распределение давать хорошую аппроксимацию для данного процесса.
Судить о результатах работы СМО можно по показателям. Наиболее популярные из них:
- пропускная способность системы;
- среднее количество заявок, стоящих в очереди;
- среднее время ожидания заявки в очереди;
- среднее время обслуживания заявки;
- среднее время нахождения заявки в системе.
Процесс моделирования начинаем с того, что генерируем время поступления первого клиента (заявки).
R=0.345500
T1=Т0+P1=0-(1/5)*ln(0.345500)=
I событие.
Ттек=0.21- время поступления первой заявки.
Сгенерируем время поступления второй заявки
R=0.487110
Т2=Ттек+Р2=0.21-(1/5)*ln(0.
Так как в начальный момент времени система простаивала, то определим время простоя:
Tпростоя=Tтек-T0=0.21
Сгенерируем время обслуживания первой заявки
R=0.811154
R>0.5 => q=q2=0.6
Определим время окончания обслуживания первой заявки
Tок.1 = Tтек + q=0.21+0.6=0.81
II событие
Ттек=0.35- время поступления второй заявки.
Сгенерируем время поступления третей заявки:
R= 0.891254
T3 = Tтек. + P3 = 0.35 –(1/5) *ln(0.891254) = 0.37
Так как система работает, ставим заявку в очередь и увеличиваем длину очереди:
Q = 0 + 1 = 1 ( при
III событие.
Tтек = 0.37 – время поступления третей заявки.
Сгенерируем время поступления четвертой заявки:
R= 0.429090
T4 = Tтек. + P4 = 0.38 – (1/5)* ln 0.429090=0.54
Так как система работает, ставим заявку в очередь и увеличиваем длину очереди:
Q = 1 + 1 = 2 (при
IV событие
Ттек=0.54 – время поступления четвёртой заявки.
Сгенерируем время поступления пятой заявки:
R=0.230243
T5 = Tтек. + P5 = 0.54 – (1/5)* ln 0.230243=0.83
Так как система работает, ставим заявку в очередь и увеличиваем длину очереди:
Q = 2 + 1 = 3 (при
V событие
Tтек = 0.81 – время окончания обслуживания второй заявки.
Так как очередь не пустая, то берем на обслуживание следующую в очереди заявку , генерируем время её обслуживания и вычисляем время окончания обслуживания:
R = 0.595449
R>0.5 q = q2 = 0.6
Tок.2 = Tтек. + q = 0.81 + 0.6 = 1.41
Изменяем длину очереди:
Q = 3 – 1 = 2 (при
Определим время ожидания обслуживания:
W = 0+ ( 0.81-0.35 ) = 0.46
VI событие
Ттек=0.83 – время поступления пятой заявки.
Сгенерируем время поступления шестой заявки:
R= 0.542293
T6 = Tтек. + P6 = 0.84 – (1/5)* ln 0.542293=0.96
Так как система работает, ставим заявку в очередь и увеличиваем длину очереди:
Q = 2 + 1 = 3 (при
Примем период моделирования Т=0.9 и определим основные параметры системы.
Определить коэффициент
Kпрост. = Tпрост. / T * 100% = 0.21/0.9 * 100 = 23.3%
Определим среднее время ожидания обслуживания:
W = 0.46 + ( 0.9 – 0.37 ) = 0.98
Ŵ = W / n = 0.99 / 5 =0.196
Определим среднюю длину очереди:
Q = 0 0 <= T < 0.35 A = 0
Q = 1 0.35 <= T < 0.38 A = 0 + 1 * (0.38 – 0.35) = 0.03
Q = 2 0.37 <= T < 0.54 A = 0.03 + 2 * (0.54 – 0.38) = 0.35
Q = 3 0.54 <= T < 0.81 A = 0.35 + 3 * (0.81 – 0.54) = 1.16
Q = 2 0.81 <= T < 0.84 A = 1.16 + 2 * (0.84 – 0.81) = 1.22
Q = 3 0.84 <= T < 0.9 A = 1.23 + 3 * (0.9 – 0.84) = 1.4
Q = A / T = 1.41 / 0.9 = 1.56
3.Интерпретация
Первые задачи теории систем
массового обслуживания (ТСМО) были
рассмотрены сотрудником
Примерами СМО (см. табл. 1) могут служить:
Пример 1. Телефонная связь времен Эрланга представляла из себя телефонную станцию, связанную с большим числом абонентов. Телефонистки станции по мере поступления вызовов соединяли телефонные номера между собой.
Задача: Какое количество телефонисток (при условии их полной занятости) должно работать на станции для того, чтобы потери требований были минимальными.
Пример 2. Система скорой помощи некоего городского района представляет собой пункт (который принимает требования на выполнение), некоторое количество автомашин скорой помощи и несколько врачебных бригад.
Задача:
Определить количество врачей, вспомогательного
персонала, автомашин, для того чтобы
время ожидания вызова было для больных
оптимальным при условии
Пример 3. Важной задачей является организация морских и речных перевозок грузов. При этом особое значение имеют оптимальное использование судов и портовых сооружений.
Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сократить простои судов при погрузочно-разгрузочных работах.
Пример 4. Система обработки информации содержит мультиплексный канал и несколько ЭВМ. Сигналы от датчиков поступают на мультиплексный канал, где буферизуются и предварительно обрабатываются. Затем поступают в ту ЭВМ, где очередь минимальна.
Задача: Обеспечить ускорение обработки сигналов при заданной суммарной длине очереди.
Таблица 1 | ||||||||||||||||||||||
|
||||||||||||||||||||||
4. Перечень идентификаторов
5. Описание алгоритма
6. Блок-схема алгоритма
7. Проверка счёта по программе
При сравнении данных, полученных
при решении задачи линейного
программирования, приведённых в
разделе 2 «Решение задачи», с результатами,
полученными в ходе работы программы,
можно сделать вывод, что программа,
реализующая моделирование СМО,
работает верно.
Заключение
В ходе данного курсового проектирования была написана программа по построению модели простейшей системы массового обслуживания. Программный продукт был реализован в среде программирования Delphi 7.0 и протестирована на платформе Windows 7 Начальная 32-разрядная, Процессор Intel(R) Atom(TM) CPU N570 1.66 GHz (4 CPus) ОЗУ 2 Гб
Написанная программа позволяет построить модель простейшей системы массового обслуживания и провести анализ данной модели на такие параметры, как: среднее время ожидания обслуживания, средняя длина очереди, коэффициент простоя. Программа позволяет отражать процесс решения в виде временной диаграммы, что значительно облегчает проверку хода решения и повышает наглядность. Ввод данных в программу осуществляется через поля, специально запрограммированные на отказ от неверного ввода данных и сообщающие об этом в специальном поле. Все эти программные решения и расчёты были реализованы с помощью объектно-ориентированного языка Delphi (на диалекте Object Pascal в среде разработки Delphi 7.0). Данный язык программирования предоставляет множество достаточно мощных и в тоже время простых для понимания компонентов, позволяющих создать интуитивно-понятный и настраиваемый пользовательский интерфейс, что позволяет сосредоточиться на программной логике кода и написании сложных алгоритмов для решения практически любых задач.
Рассмотрим Delphi подробнее.
Язык программирования Паскаль
(Pascal) был создан Н. Виртом в 1968 году
специально для обучения студентов.
Язык Паскаль представлял собой
квинтэссенцию технологий программирования
середины 60-х — эпохи создания
структурного программирования. Язык
был популярен в
Объектно-ориентированные
средства языка Паскаль прошли большой
путь от простейших объектных расширений
в TurboPascal 5.5 до современной объектной
модели Delphi, не уступающей по своим
потенциальным возможностям ни одному
объектно-ориентированному языку. Объектная
модель Delphi поддерживает все средства
которые могут понадобиться при
объектно-ориентированном
Но основным преимуществом Delphi является его среда программирования с визуальным конструктором программ. Эта среда (вместе с объектной библиотекой VCL) позволяет эффективно программировать под MS Windows, не отвлекаясь на выяснение всех деталей Win API, а работать над логикой программы.
Среди этих достоинств Delphi:
- простой и мощный язык программирования Pascal;
- удобная и полная объектная модель;
- достаточно удобная среда разработки;
- обширная объектная библиотека VCL;
- мощные средства разработки приложений баз данных.
Достоинствами разработанной программы можно считать:
- понятный пользовательский интерфейс;
- Контроль ввода данных.
- возможность пользователя самому выбирать период моделирования для расчётов программы на основе анализа схемы;
К недостаткам программы можно отнести:
- Для построения новой модели приходится перезапускать программу;
Список используемой литературы
Приложение 1. Листинг программы
unit Kurs;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls, Buttons, Grids, ComCtrls, Menus;
type
TForm1 = class(TForm)
pnl1: TPanel;
lbl1: TLabel;
pnl2: TPanel;
lbl2: TLabel;
edt11: TEdit;
lbl3: TLabel;
edt12: TEdit;
edt13: TEdit;
edt14: TEdit;
lbl4: TLabel;
lbl5: TLabel;
lbl6: TLabel;
mmo1: TMemo;
btn1: TButton;
Image1: TImage;
BitBtn1: TBitBtn;
Memo1: TMemo;
Panel1: TPanel;
ScrollBar1: TScrollBar;
strngrd1: TStringGrid;
edt1: TEdit;
ud1: TUpDown;
Panel2: TPanel;
Edit1: TEdit;
BitBtn3: TBitBtn;
Label1: TLabel;
LabeledEdit1: TLabeledEdit;
Edit2: TEdit;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Edit3: TEdit;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
BitBtn4: TBitBtn;
MainMenu1: TMainMenu;
N1: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
Label8: TLabel;
Label9: TLabel;
Label10: TLabel;
Label11: TLabel;
procedure btn1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure ScrollBar1Change(Sender: TObject);
procedure ud1Click(Sender: TObject; Button: TUDBtnType);
procedure BitBtn3Click(Sender: TObject);
procedure strngrd1KeyPress(Sender: TObject; var Key: Char);
procedure edt11KeyPress(Sender: TObject; var Key: Char);
procedure edt1KeyPress(Sender: TObject; var Key: Char);
procedure edt12KeyPress(Sender: TObject; var Key: Char);
procedure edt13KeyPress(Sender: TObject; var Key: Char);
procedure edt14KeyPress(Sender: TObject; var Key: Char);
procedure Edit1KeyPress(Sender: TObject; var Key: Char);
procedure BitBtn4Click(Sender: TObject);
procedure N4Click(Sender: TObject);
procedure N3Click(Sender: TObject);
//procedure N21Click(Sender: TObject);
// procedure prov(Sender: TObject);
private
{ Private declarations }
public
procedure prov;
{ Public declarations }
end;
var
Form1: TForm1;
buf,li,lin:integer;
tprost:double;
znach:array of double; // ìàññèâ ÿíà÷åíèé íà ëèíèè
och,pom:array of Integer; // ìàññèâ î÷åðåäè è ïîìåòîê
zap:array of boolean;
implementation
//uses Unit2;
{$R *.dfm}
procedure TForm1.prov;
var i:integer;
begin
if panel2.Visible=false then
begin
mmo1.Clear;
li:=0;
lin:=0;
for i:=0 to strngrd1.Rowcount-1 do if (strngrd1.Cells[0,i]<>'')and
(strtofloat(strngrd1.Cells[0,
memo1.lines.Add(inttostr(li));
if li<>strngrd1.RowCount then begin
mmo1.Lines.Add('Ñëó÷àéíûå ÷
mmo1.Lines.add('
end;
if (edt11.text='') or (strtofloat(edt11.text)=0)or(
mmo1.Lines.Add('Íå ââåäåíî
end else lin:=lin+1;;
if (edt12.text='') or (strtofloat(edt12.text)=0)or (strtofloat(edt12.Text)>=1)
mmo1.Lines.Add('Íå ââåäåíî
//mmo1.Lines.Add('.');
end else lin:=lin+1;
if (edt13.text='') or (strtofloat(edt13.text)=0) or (strtofloat(edt13.Text)>=1) then begin
mmo1.Lines.Add('Íå ââåäåíî
//mmo1.Lines.Add('');
end else lin:=lin+1;
if (edt13.text='') or (strtofloat(edt13.text)=0) then begin
memo1.Lines.Add('Íå ââåäåí
end else lin:=lin+1;
if (li=strngrd1.RowCount) and (lin=4) then btn1.Enabled:=true else btn1.Enabled:=false;
end;
end;
procedure TForm1.btn1Click(Sender: TObject);
var
r: array of Double; // ìàññèâ ðàíäîìíûõ ÷èñåë
q,i,q1,q2,pprost,tok,ttek,
shag,s1,s2,l,prost,qo,a,z,j,f,
begin
setlength(r,strngrd1.RowCount+
setlength(znach,strngrd1.
setlength(och,strngrd1.
setlength(pom,strngrd1.
for j:=0 to strngrd1.RowCount-1 do r[j+1]:=StrToFloat(strngrd1.
l:=StrToInt(edt11.Text); //çàíåñåíèå ëÿìáäû
q1:=StrToFloat(edt12.Text);
q2:=StrToFloat(edt13.Text);
i:=StrToFloat(edt14.Text);
shag:=1;
s1:=1; //ñ÷¸ò÷èê äëÿ ðàíäîìíûõ ÷èñåë
tpost:=0;
s2:=0;
ttek:=0;
tok:=0;
prost:=0;
q:=0;
qo:=0;
znach[0]:=0;
strngrd1.Options:=[
edt11.ReadOnly:=true;
edt12.ReadOnly:=true;
edt13.ReadOnly:=true;
edt14.ReadOnly:=true;
//ïåðâàÿ èòåðàöèÿ
znach[1]:=ttek+(-(1/l)*ln(r[
mmo1.Lines.Add(floattostr(
znach[1]:=(round(znach[1]*100)
mmo1.Lines.Add(floattostr(

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