Моделирование расписаний: участок дороги с односторонним движением

J(uk - аkрk)<J(uk)

В случае выполнения формулы и вхождения в область U примем

uk+1= uk - аkрk, ak+1= aak

Назовем (k + 1)-ю итерацию удачной, если справедливо хотя бы одно из неравенств и соответствующая точка u= uk аkрk принадлежит области U. Если (k + 1)-я итерация неудачная, то есть одновременно с условием не выполняется ни одно из неравенств и, то полагаем

Здесь -- фиксированное число, являющееся параметром метода. Условия означают, что если за один цикл из n итераций при переборе направлений всех координатных осей е1,…. ,еn с шагом аk реализовалась хотя бы одна удачная итерация, то длина шага ак не дробится и сохраняется на протяжении по крайней мере следующего цикла из n итераций. Если же среди последних n итераций не оказалось ни одной удачной, то шаг ак дробится. Описание метода покоординатного спуска закончено.

5.2 Оптимизация программного кода

Из условия задачи можно сделать вывод, что за эо с автомооиль проезжает ремонтируемый участок дороги от начала до конца. По окончании «зеленого» интервала светофор должен исходить из наихудшего предположения, заключающегося в том, что последний автомобиль въехал на участок как раз перед включением красного света, ведь у светофора нет автоматической системы видеонаблюдения за дорогой и он не может отследить момент въезда последней машины. Но на самом деле такое предположение является избыточным, ведь наверняка возникают ситуации, когда в последние, скажем, 10 с «зеленого» интервала автомобили на участок не въезжали. Значит, уже через 45 с на другом светофоре можно включать зеленый свет. Сделаем фантастическое предположение: светофоры оборудованы автоматической системой и могут динамически подстраивать длительности «красных» интервалов друг друга, фиксируя момент проезда последней машины и одновременно с переключением на красный свет посылая сообщение «коллеге», через сколько секунд ему включить зеленый. Соответственно, через некоторое время отправитель и сам получит сообщение от коллеги, через какое время ему включать зеленый. Если же такое сообщение по каким-то причинам получено не будет, зеленый свет включится по детерминированному расписанию. Интересно выяснить, как скажется такое дорогостоящее техническое новшество на основном показателе -- среднем времени ожидания.

Для сокращения дальнейшего сравнительного анализа назовем прежнюю модель первой, а рассматриваемую в данном случае -- второй. Для второй модели длительность «красного» интервала становится случайной величиной, поэтому между двумя светофорами должна существовать связь для передачи сообщений. Выпишем для второй модели фрагменты кода, которые претерпевают изменения по сравнению с первой моделью.

Листинг программы файл 2.h. Описание классов

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<cmath>

using namespace std;

#include "List.h"

#include "random.h"

FILE *que1;

FILE *que2;

int K=10;

FILE *sojourn;

int entered=0;

int completed=0;

float que1_ave=0;

float que2_ave=0;

float soj_ave=0;

long int total;

class Client

{

int id;

int time;

public:

friend class SignalLights;

Client(int i);

void Print();

};

Client::Client(int i)

{

id=i;

time=0;

}

void Client::Print()

{

printf("id=%d time=%d\n", id, time);

}

class SignalLights

{

const static int both=550;

const static int gap=20;

float input_rate;

int id;

int green_I;

int green_other;

ListNode<Client> *queue;

int to_red;

int to_green;

int to_forward;

int to_arrival;

int q_length;

int from_last;

SignalLights *other;

public:

SignalLights(float a, int b, int c, int d);

void Arrival();

void Forward();

void Red();

void Green();

void run();

void PutOther(SignalLights *p);

};

void SignalLights::PutOther(SignalLights *p)

{

other=p;

}

SignalLights::SignalLights(float a, int b, int c, int pr)

{

id=pr;

queue=NULL;

input_rate=a;

green_I=b;

green_other=c;

if (pr==1)

{

to_red=green_I;

to_green=-1;

}

else

{

to_green=both+green_other;

to_red=-1;

}

to_forward=-1;

q_length=0;

to_arrival=(int)(get_exp(input_rate)*K);

if (to_arrival==0) to_arrival=1;

from_last=-1;

}

void SignalLights::Arrival()

{

Client *ptr=NULL;

ListNode<Client> *ptr1=NULL;

to_arrival=(int)(get_exp(input_rate)*K);

if (to_arrival==0) to_arrival=1;

entered++;

ptr=new Client(entered);

if (q_length>0)

{

ptr1=new ListNode<Client>(ptr, NULL);

ListAdd<Client>(queue, ptr1);

q_length++;

}

else if (to_green>0)

{

ptr1=new ListNode<Client>(ptr, NULL);

queue=ptr1;

q_length=1;

}

else

{

completed++;

delete ptr;

soj_ave=soj_ave*(1-1.0/completed);

fprintf(sojourn, "1\n");

from_last=0;

}

return;

}

void SignalLights::Forward()

{

int p;

ListNode<Client> *ptr;

if (to_red==-1) { to_forward=-1; return; }

completed++;

q_length--;

p=queue->Data()->time;

fprintf(sojourn, "%.1f\n", ((float)p)/K);

soj_ave=soj_ave*(1-1.0/completed)+((float)p)/completed;

from_last=0;

if (q_length>0)

{

ptr=queue;

to_forward=gap;

queue=queue->Next();

delete ptr;

}

else

{

to_forward=-1;

delete queue;

queue=NULL;

}

return;

}

void SignalLights::Red()

{

to_red=-1;

to_green=2*both+green_other;

to_forward=-1;

other->to_green=both-from_last;

from_last=-1;

}

void SignalLights::Green()

{

to_green=-1;

to_red=green_I;

if (q_length>0) Forward();

}

void SignalLights::run()

{

int zu;

ListNode<Client> *pur=NULL;

if ((from_last!=-1)&&(from_last<both)) from_last++;

if (to_forward>0) to_forward--;

if (to_forward==0) Forward();

if (to_red>0) to_red--;

if (to_red==0) Red();

if (to_green>0) to_green--;

if (to_green==0) Green();

if (to_arrival>0) to_arrival--;

if (to_arrival==0) Arrival();

if (q_length>0)

{

zu=0;

pur=queue;

while(pur!=NULL)

{

(pur->Data()->time)++;

pur=pur->Next();

zu++;

}

}

if ((id==1)&&(total%20==0)&&(total/20>0))

{

fprintf(que1, "%d\n", q_length);

que1_ave=que1_ave*(1-1.0/(total/20))+((float)q_length)/(total/20);

}

if ((id==2)&&(total%20==0)&&(total/20>0))

{

fprintf(que2, "%d\n", q_length);

que2_ave=que2_ave*(1-1.0/(total/20))+((float)q_length)/(total/20);

}

}

Листинг программы функция main() (вариант №2)

#include "stdafx.h"

#include "iostream"

#define N 432000 //общее время моделирования - 8 часов

#include "2.h"

int main()

{

int i;

SignalLights *s1, *s2;

que1=fopen("que1", "wt");

que2=fopen("que2", "wt");

sojourn=fopen("sojourn", "wt");

srand((unsigned)time(0));

s1=new SignalLights(0.083, 600, 600, 1);

s2=new SignalLights(0.111, 600, 600, 2);

s1->PutOther(s2);

s2->PutOther(s1);

for(total=0L;total<N;total++)

{ s1->run();

s2->run();

} //удаление объектов

delete s1; delete s2; //закрытие файлов сбора статистики

fclose(sojourn);

fclose(que1); fclose(que2);// вывод на печать результатов имитационного эксперимента

setlocale(LC_ALL, "Russian");

cout << "Всего поступлений " << entered << endl;

cout << "Проехало по участку " << completed << endl;

cout << "Средняя длина очереди к первому светофору " << que1_ave << endl;

cout << "Средняя длина очереди ко второму светофору " << que2_ave << endl;

cout << "Среднее время пребывания в очереди " << soj_ave/K << endl;

_gettch();

}

6. Анализ результатов работы программы

Рис. 3. Скриншот работы программы (первая модель)

Приведем результаты расчетов методом покоординатного спуска для первой модели. Значения функции (среднего времени ожидания) округлены до одного знака после запятой. Значение шага не будем принимать меньшим одной секунды. В качестве начального приближения примем значения «зеленых» интервалов равными одной минуте, то есть (g1,g2) = (60,60).

Т(60, 60) = 81,7; а =10.

Результаты первой итерации:

T(50; 60) = 78,8; T(70; 60) = 86,5; T(60; 70) = 79,8; T(60; 50) = 108,1.

Итерация удачна, так как T(50; 60) < T(60; 60). Значение шага сохраняется. Результаты второй итерации:

T(40; 60) = 80,2; T(50; 70) = 78,3; T(50; 50) = 88,6.

Итерация удачна. Значение шага сохраняется. Результаты третьей итерации:

T(40; 70) = 83,9; T(50; 80) = 79,4.

Итерация неудачна. Полагаем значение шага равным 5:

T(55; 70) = 78,9; T(45; 70) = 79,8; T(50; 75) = 78,7; T(50; 65) = 78,4.

Итерация неудачна. Полагаем значение параметра равным 2:

T(52; 70) = 78,5; T(48; 70) = 78,4; T(50; 72) = 78,5; T(50; 68) = 78,2.

Формально итерация удачна, хотя вычисления уже можно прекращать -- с практической точки зрения точность на уровне десятых долей секунды нам в этой задаче не нужна. Сделаем еще одну итерацию:

T(52; 68) = 78,4; T(48, 68) = 78,2; T(50; 66) = 78,2.

Итак, делаем вывод: для достижения оптимального решения необходимо задать длину «зеленого» интервала для первого светофора 50 с, для второго светофора -- от 65 до 70 с. При этом среднее время ожидания автомобиля в очереди равно около 78 с.

Добавим, что при оптимальных значениях «зеленых» интервалов, средняя длина очереди к первому светофору равна около 7, ко второму -- около 8. Это логично, так как интенсивность входного потока ко второму светофору выше.

Рис. 4. Скриншот работы программы (вторая модель)

Проведем аналогичные расчеты для второй модели. На основе имеющихся данных мы можем выбрать для начала расчетов лучшее начальное приближение -- точку (50; 70):

T(50; 70) = 68,2.

Результаты первой итерации, а = 5:



Рис. 5. Зависимости среднего времени ожидания от длины «зеленого» интервала второго светофора

T(55; 70) = 68,3; T(45; 70) = 69,3; T(50; 75) = 68,6; T(50; 65) = 68.

Итерация удачна, так как T(50; 65) < T(50; 70). Значение шага сохраняется. Результаты второй итерации:

T(55; 65) = 68,5; T(45; 65) = 68,7; T(50; 60) = 68,3.

Итерация неудачна, а = 2:

T(52; 65) = 68,1; T(48; 65) = 68; T(50; 67) = 68; T(50; 63) = 68,1.

Дальнейшие вычисления излишни. Вывод об оптимальных значениях «зеленых» интервалов такой же, как и для первой модели. А вот среднее время ожидания сократилось за счет динамической подстройки «красных» интервалов на 10 с. Средняя длина очереди тоже уменьшилась: 6 -- для первого светофора и 7,5 -- для второго. На рис. 5 приведены графики зависимости среднего времени ожидания от длины «зеленого» интервала для второго светофора при длине «зеленого» интервала первого светофора, равной 50. Область определения зависимостей рассчитана с помощью выражения при g1 = 50 и представляет собой интервал [46; 139]. Нетрудно заметить идентичность этих двух кривых.

Средняя длительность «красного» интервала в обоих направлениях уменьшается во второй модели с 55 до 46-47 с при g1 = 50, g2 = 66.

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

7. Заключение

В результате выполнения курсовой работы были достигнуты следующие результаты:

· изучены метод имитационного моделирования экономических объектов;

· получены навыки проведения численных экспериментов на имитационных моделях экономических систем;

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

Список использованной литературы

1. Труб И. И. «Объектно-ориентированное моделирование на С++»: Учебный курс.-СПб.:Питер, 2006.-411с.:ил.

2. Варфоломеев В.И. «Алгоритмическое моделирование элементов экономических систем». - М.: Финансы и статистика, 2008г.

3. Клейнрок Л. «Теория массового обслуживания.»-М.: Машиностроение, 2007.-432 с.

4. Прицкер А. «Введение в имитационное моделирование»-М.: Мир, 2010.-644с.

5. Емельянов А.А.,Власова Е.А., «Имитационное моделирование экономических процессов» - М. Финансы и статистика, 2007.

6. Дубров А.М., Лагоша Б.А., Хрусталев Е.Ю. Моделирование рискованных ситуаций в экономике и бизнесе. -М.: Финансы и статистика, 2008. -224 с.

7. Князевская Н.В., Князевский В.С. Принятие рискованных решений в экономике и бизнесе. -М.: Контур, 2008. -160 с.

8. Шикин Е.В. Математические методы и модели в управлении. -М.: Финансы и статистика, 2005. -430 с.

9. Федосеева В.В. «Экономико-математические методы и прикладные модели», под ред., Москва «Юнити» 2009 г.

7. Гинзбург А.И. Экономический анализ: Предмет и методы. Моделирование ситуаций. Оценка управленческих решений: учебное пособие. -СПб.: Питер, 2008. -622 с.

8. Грабовый П.Г. Риски в современном бизнесе. -М.: Финансы и статистика, 2010. -200 с.

Размещено на Allbest.ru