КАФЕДРА
Экономической кибернетики
имитационное моделирование на основании предварительноустановленных зависимостей.
г. ЖелтыеВоды 2004
Содержание
1. Постановка задачи _________________________________3
2. Метод решениязадачи _________________________________ 5
3. Программноерешение _________________________________ 8
4. Руководствопользователя_______________________________ 11
5. Листинг программы _________________________________12
Постановка задачи
В современном мире гарантиейэффективной работы любого предприятия служит рациональное использованиеденежных средств и трудового фактора. Так для расчета экономического эффектаработы кассового зала необходимо провести имитационное моделирование наосновании предварительно установленных зависимостей.
Допустим, что клиенты взал прибывают с интервалом, исчисляемым в минутах (см. рис. 1).
/>/>
/> />
Рис. 1 – «Приход клиентовв зал»
Приход клиентов в залописывается пуассоновским потоком с интенсивностью r, который определяется следующим образом:
/>/> (1.1)
где: r – интенсивность потока;
k – время между приходами клиентов.
Параметр k может принимать дискретные значенияот нуля до бесконечности. Причем k=0означает приход сразу двух клиентов.
Предположим, в залеимеется N касс. Математическое ожиданиеобслуживания клиентов в банке обозначим />. Обслуживание клиентов у касс происходит поэкспоненциальному закону распределения случайной величины /> (/> — время обслуживания клиентов) с плотностьюраспределения />:
/>/> (1.2)
Примечание:
Если в зале естьсвободные кассы, то клиент становится на обслуживание к ближайшей из них (т.е.к кассе с минимальным номером). Если все кассы заняты – клиент становится вочередь к той кассе, где очередь минимальна. Если очереди одинаковы, то клиентстановится в любую из них.
Для решения поставленнойзадачи необходимо разработать алгоритм имитационного моделирования работы кассовогозала за 24-часовый рабочий день. А также определить время простоя касс иколичество клиентов в очереди не обслуженных на момент закрытия банка.
1. Методрешения задачи
Имитационное моделирование на ЭВМпроцесса функционирования автоматизированной системы управления работойкассового зала позволяет получить численное решение поставленной задачи. Сутьрассматриваемого приближенного метода решения состоит в проведении рядаслучайных испытаний вероятностной модели исследуемой системы и получениисовокупности реализаций случайных процессов изменения состояния.
В результате многократнойреализации случайных процессов определяются оценки вероятности тех или иныхсобытий и средние значения случайных величин. Имитационное моделированиесвязано с необходимостью воспроизведения случайных событий и величин,распределенных по произвольному закону. Существует несколько способов генерациислучайных величин и формирования их распределений. Модель системы управления работойкассового зала включает в себя:
· Приход клиентов взал />;
· Времяобслуживания клиентов у касс />.
По условию поставленнойзадачи приход клиентов в зал описывается пуассоновским потоком с интенсивностьюr. Для лучшего понимания сутираспределения Пуассона необходимо знать основные определения:
Интенсивность потока –среднее число событий, которое появляется в единицу времени.
Поток –последовательность событий, которые наступают в случайные моменты времени.
Закон распределенияПуассона выражается формулой (1.1).
Будем моделировать интервал временимежду двумя последовательно зашедшими в банк клиентами методом Монте-Карло сдатчиком случайных чисел на интервале [0 — 1].
Совокупность /> независимых случайных событий,образующих полную группу, характеризуется вероятностями появления каждого изсобытий />, причем />. Для моделирования этойсовокупности случайных событий используется генератор случайных чисел,равномерно распределенных в интервале [0 — 1]. При делении отрезка [0 — 1] на n частей, численно равных />, возникновение события /> устанавливается путемопределения нахождения случайного числа Х в пределах интервала при проверкеусловия />, где /> изменяется от нуля до n. При /> имеем />; при /> имеем /> и так далее. При подстановке /> в формулу (1.1) получим:
/> />;
/> />;
/> /> и так далее.
Причем />(мин.) – максимальное количество ожиданияклиентов.
Так как опыт проводится многократно,то, очевидно, что частота попадания случайных чисел на каждый из отрезков,определяющихся их длиной, и соответствует полученным вероятностям
Моделирование времениобслуживания клиентов у касс происходит по экспоненциальному законураспределения, формула которого представлена выше (формула (1.2)).
Время обслуживанияклиентов />, как и любая инаяслучайная величина, описывается функцией распределения />, определяемая как вероятность /> случайного события, заключающегося в том,что время обслуживания клиентов />меньше некоторого заданного времени />:
/>
Эта вероятностьрассматривается как функция /> вовсем диапазоне возможных значений величины />. Функция распределения любой случайной величиныявляется неубывающей функцией времени />. Примерный вид функции /> дан на рисунке 3./> />
Рис. 3 – «Функцияраспределения экспоненциального закона»
Так как значения /> не могут быть отрицательными, то/>. При />/> величина /> стремится к единице. Таким образом, функцияраспределения времени обслуживания клиентов:
/> (1.3)
где /> - параметр распределения (среднее времяобслуживания клиентов у кассы).
Соответственно плотностьраспределения:
/> (1.4)
Для моделирования времениобслуживания клиента у кассы проинтегрируем функцию распределения />:
/>
/> (1.5)
От датчика случайныхчисел равномерно распределенных на интервале [0 — 1] получаем очередное числоХ, которое подставляем в формулу (1.5) и вычисляем />:
/>
/> (1.6)
Из соотношения (1.6)найдем /> соответствующее Х,которое будем принимать за случайное число, обозначающее время обслуживанияданной кассой.
2. ПРОГРАММНОЕРЕШЕНИЕ
Программа имитационногомоделирования работы кассового зала написана на языке C с помощью среды разработки Borland C++ 3.1.
/>Блок-схема имитационногомоделирования работы кассового зала/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Исходный текст программысостоит из одного файла Kas1.c который содержит реализацию такихфункций программы:
– float RND_DIG (void) — Функция возвращающая СЧ вдиапазоне [0, 1];
– void massive (void)- Функция выделяющая память под массив времени обслуживания у каждой из касс;
– float _tau(void) — Функция возвращающая время обслуживания у кассы;
– float time_to(void) — Функция определяет время входа следующего клиента. Промежутки междувходами распределены по закону Пуассона с параметром lambda;
– void inf (void) — Функция вывода информации пользователю.
РУКОВОДСТВОпользователя
1. Программаимитационного моделирования работы банка расположена по следующему адресу:
A:\Kas1.exe
2. На запроспрограммы:
«Введитеколичество касс в кассовом зале ж\\д вокзала:»
Вводим предполагаемое (данное)количество касс обслуживающих клиентов.
3. На запроспрограммы:
«Введите параметр распределенияПуассона для определения времени между входами пассажиров в зал:»
Вводим lambda – Параметрраспределения Пуассона
4. На запрос программы:
«Введите минимальнуюпродолжительность обслуживания у касс»
Вводим tau_min – минимальнуюпродолжительность обслуживания.
4. На запроспрограммы:
«Введите максимальную продолжительность обслуживания укасс»
Вводим tau_max – максимальную продолжительность обслуживания.
5. На запроспрограммы:
«Введите время моделирования работызала(в ч.):»
Вводим hours - время моделирования работы зала.
6. На запроспрограммы:
«Введите математическое ожиданиевремени обслуживания у касс:»
Вводим MO — математическое ожидание.
7. На запроспрограммы:
«Введите среднеквадратическоеотклонение времени обслуживания у касс:»
Вводим SKO — среднеквадратическоеотклонение.
8. После просмотра результатов,нажмите любую клавишу для завершения работы.
5. Листингпрограммы
/* Включаемие модули*/
#include // Функции потокового ввода — вывода
#include // Формирование экракна
#include // Математические функции
#include // Функции по работе с динам. памятью
//Прототипы функций
float RND_DIG( void ); //Ф-я генерирует случ. числа
void inf(void); // Ф-я сообщает о назн-ии программы
void massive( void ); // Ф-я выделяющая память под массив
float _tau( void); // Расчет времени обсл-я клиента у кассы
float time_to ( void ); // Расчет времени входа пассажира в зал
//Объявление переменных
float
tau_min, // Мин. время обсл-я у касс
tau_max, //Макс. время обсл-я у касс
*tau, // Тек. время обсл-я у касс
current_time, // Тек. время
minutes, // Общ. время работы в минутах
lambda, // Пар-р закона распр-я Пуассона
enter_time_, // Время входа очередного пассажира
MO, // Мат. ожид-е времени обсл-я
SKO, //Среднекв. откл-е времени обсл-я у касс
t_free, // Общ. время простоя касс
t_free_av, // Ср. время простоя
serve_av, // Ср. % обслуж-я пассажиров
refuse_av, // Ср. % отказов в обсл-ии
N0=7836, // 1-й множитель для расчета случ. числа
NI=4792, // 2-й множитель для расчета случ. числа
N, // Прозведение N0 и NI
ND; // Средние 4 цифры из числа N
int
m, // Кол-во касс
i, // Тек. номер кассы
enter, // Кол-во вошедших
hours, // Время работы зала в часах
serve, // Кол-во обслуж-х пассажиров
refuse, // Кол-во необслуж-х пассажиров
stand, // Кол-во стоящих в очереди на момент обслуживания
INDPAS; // Флаг обслуживания пассажиров
// Главная функция программы
void main(void)
{
inf(); // cообщение о назначении программы
textcolor( 14); //установка цвета и фона
textbackground( 1 );
clrscr(); //очистка экрана
/* Прием данных от пользователя */
printf("\n████████████████████████████████████████████████████████████████████████████████");
for(i=1;i
printf("█ █");
printf("████████████████████████████████████████████████████████████████████████████████");
gotoxy(10,7);
do
{
printf("\n█\tВведитеколичество касс в кассовом"
"зале ж\\д вокзала:");
scanf("%d", &m );
}
while((m=100) );
do
{
printf( "\n█\tВведитепараметр распределения Пуассона для"
"определения" );
printf( "\n█\t\tвременимежду входами пассажиров в зал:" );
scanf( "%f",&lambda );
}while(lambda
clrscr();
//Вывод рамки
printf("\n████████████████████████████████████████████████████████████████████████████████");
for(i=1;i
printf("█ █");
printf("████████████████████████████████████████████████████████████████████████████████");
gotoxy(5,3);
do
{
printf("\n█\n█\tВведите минимальную продолжительность обслуживания " );
printf("\n█\t\t\tу кассами:" );
scanf("%f", &tau_min );
}while(tau_min
do
{
printf( "\n█\tВведитемаксимальную продолжительность обслуживания " );
printf( "\n█\t\t\tу касс:" );
scanf("%f", &tau_max );
}while(tau_max
do
{
printf( "\n█\tВведитевремя моделирования работы зала(в ч.):" );
scanf( "%d",&hours );
}while(hours
do
{
printf("\n█\tВведитематематическое ожидание времени обслуживания");
printf( "\n█\t\tу касс:");
scanf("%f", &MO );
}while( MO
do
{
printf( "\n█\tВведитесреднеквадратическое отклонение времени ");
printf( "\n█\tобслуживанияу касс:");
scanf( "%f",&SKO );
}while(SKO
massive(); // создание и обнуление массива
minutes=floor( hours*60); // переведем время работы в минуты
enter=0; // никто не входил
serve=0; // никого не обслужили
refuse=0; // никому не отказали
t_free=0; // кассы еще не простаивали
current_time=0; // начало отсчета времени с нуля
enter_time_=time_to(); // когда зайдет следующий
/*Цикл моделирования работы зала
for(current_time=0; current_time
{
/*Коррект-ка времени обсл-я у каждой кассы */
if( current_time )
for(i=1; i
if( tau[i]) //Если касса занята, то уменьшимвремя обсл-я
tau[i]--; // в ней на 1 мин.
else // Если касса свободна, наращиваем общее время
t_free++; // простоя касс.
if(enter_time_
{
enter++; // Если входит пассажир, отмечаем это
enter_time_=time_to(); // Узнаем, когда зайдет следующий?
i=1; // Вошедший подходит к 1-й кассе
INDPAS=1; // Его еще не обслуживают
do
{
if(tau[i]
{ //обсл-е и узнаем, сколько ему стоять у кассы
tau[i]=_tau();
INDPAS=0; //Укажем, что пассажира обслуживают
}
i++; // Подходим к следующей кассе
}while((i
if(INDPAS==1 ) // Если клиент не обслужен,отмечаем это
refuse++;
if(INDPAS==0) // Если клиент обслужен,отмечаем это
serve++;
}
}
stand=0; //Пока в очереди никто не стоит
i=1; // Начинаем с первой кассы
do
{
if( tau[i]>0) // Если время обсл-я не равнонулю, значит
stand++; // у кассы кто-то стоит
i++; // Смотрим у следующей кассы
}while( i
serve-=stand; // Корректируем кол-во обслуженных
t_free_av=(float)t_free/m; // Вычислим ср. время простоя
serve_av=(float)serve/enter; // Вычислим ср. % обслуженных
refuse_av=(float)refuse/enter; // Вычислим ср. % необслуженных
textcolor(1); // Установка параметров текста
textbackground(2);
clrscr();
_setcursortype( _NOCURSOR );
/*Выводполученных результатов
//Выводрамки
printf("\n████████████████████████████████████████████████████████████████████████████████");
for(i=1;i
printf("█ █");
printf("████████████████████████████████████████████████████████████████████████████████");
gotoxy(3,3);
printf( "\n█\n█\t╔════════════════════════════════════════════════════════════╗");
printf(" \n█\t║%d железнодорожных касс работало на протяжении: %d часов.",m,hours );
gotoxy(70,6);
printf("║");
printf(" \n█\t║ В зал зашло %d посетителей.", enter );
gotoxy(70,7);
printf("║");
printf(" \n█\t║");
gotoxy(70,8);
printf("║");
printf(" \n█\t║\n█\t║Было обслужено %d человек(а).", serve);
gotoxy(70,9);
printf("║");
printf(" \n█\n█\t║Ушли необслуженными %d человек(а).", refuse);
gotoxy(70,10);
printf("║");
printf(" \n█\n█\t║В очереди осталось стоять %d человек(а). ", stand);
gotoxy(70,11);
printf("║");
printf(" \n█\n█\t║Средний процент обслуживания пассажиров %.2f%%", serve_av*100);
gotoxy(70,12);
printf("║");
printf(" \n█\n█\t║Средний процент отказов в обслуживании %.2f%%", refuse_av*100);
gotoxy(70,13);
printf("║");
printf(" \n█\n█\t║Всего кассы простаивали: %.0fч. %.0f мин. ",floor( t_free/60 ),
t_free-floor(t_free/60 )*60 );
gotoxy(70,14);
printf("║");
printf(" \n█\n█\t║Среднее время простоя 1 кассы: %.0fч. %.0f мин.",
floor( t_free_av/60 ),t_free_av-floor( t_free_av/60 )*60);
gotoxy(70,15);
printf("║");
gotoxy(70,16);
printf("║");
printf(" \n█\t╚════════════════════════════════════════════════════════════╝");
getch();
}
//Функциявозвращающая СЧ в диапазоне от 0 до 1
float RND_DIG (void)
{
float
x; //СЧв диапазоне от 0 до 1
N=(NI*N0);
ND=floor(N/100);
ND=(ND/10000-floor(ND/10000))*10000; // Отбросим первые 2 цифры
N0=NI;
NI=ND;
x=ND/9999;
return x;
}
//Ф-я выделяет память подмассив времени обсл-я у каждой из касс
void massive( void )
{
int i;
tau=(float*)malloc( (m+1)*sizeof(float) );
/* Обнуление элементов массива */
for(i=1; i
tau[i]=0;
}
// Ф-я возвр.время обсл-я у кассы
float _tau( void )
{
float
x, // Случайное число x
y, // Случайное число y
z, // Случайное число z
tau_; //Время обслуживания
//Проверка на четность
//---------------------
if( floor ( (float )i/2 )==ceil( ( float )i/2 ) )
{
x=RND_DIG(); // Запрос случ. числа от ДСЧ
y=RND_DIG(); // Запрос случ. числа от ДСЧ
if(x>=.0001) // Если х не слишком маленькое, считаем z
z=sqrt( -2*log( x ) )*sin(2*M_PI*y );
else
{
if(sin( 2*M_PI*y )
z=0; // Если обамножителя слишком малы, то z=0
else
z=(float)minutes/2; //Если 2-й множ-ль нормальный, то
} //вел-на z равна половине времени работы зала.
tau_=MO+z*SKO; // Вычислим нормально распределенное время обсл-я
if( tau_
tau_=1;
}
else
{
x=RND_DIG(); // Запрос случ. величины от ДСЧ
/*Вычислим равномерно распределенное время обсл-я */
//--------------------------------------------------
tau_=floor(tau_min+x*( tau_max-tau_min )+.5);
}
return floor(tau_+.5 ); //Выведем в место запроса
}
// Ф-яопределяет время входа след-го клиента. Промежутки
// междувходами распределены по закону Пуассона с пар-м lambda
// ============================================================
float time_to( void )
{
int
j; // Пар-р закона распр-я Пуассона
float
x, // Случ. вел-на
tau, // Время до входа
a, // Пар-р закона распр-я
n, // Половина общего времени работы
S; // Пар-р закона распр-я
n=floor( minutes/2+0.5 );
x=RND_DIG(); // Примем случ. число
tau=0;
j=0;
a=exp( (lambda * (-1))); // Расчет нач. знач-я пар-ра а
S=0;
do
{
if(S>=x && x
break;
tau++;
j++;
S+=a;
a*=lambda/j;
}
while( tau
return current_time+tau; //Возвратим время до входа след-го клиента
}