Автоматизированные банковские системы

3. Найти x^t+1 минимизирующее значение P(x^t+1,R^t) при фиксированном R^t. В качестве начальной точки использовать x^t, а в качестве параметра окончания шага - константу e₂ (возможно и e₁).

4. Проверить, выполняется  ли условие 

                                     | P(x^t+1,R^t)-P(x^t,R^t-1) | £ e₃.

     если "да" - положить x^t+1=x^T и закончить процесс решения;

     если "нет" - перейти к следующему шагу.

5. Положить R^t+1=R^t+DR^t в соответствии с используемым правилом пересчета, после чего вернуться к шагу 2.

 

2.2.3 Методы  прямого поиска

 

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

 

Перед непосредственным применением методов прямого поиска необходимо провести ряд мероприятий по подготовке задачи к решению, а именно:

• Исключить ограничения в виде равенств.
• Определить начальную допустимую точку.

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

 

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

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

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

• Метод комплексов.
• Метод случайного поиска.

Алгоритм метода комплексов:

Заданы границы значений всех переменных x_i^L, x_i^U, i=1,2,..., N (размерность задачи), допустимая точка x⁰, параметр отображения a (рекомендуется a=1,3) и параметры окончания вычислений e и d.

1. Построение начального комплекса,  состоящего из P допустимых точек(рекомендуется  P=2N). Для каждой точки p = 1, 2,...,P-1

а) Случайным образом определить координаты x^p.

б) Если x^p - недопустимая точка, то найти центр тяжести x_цт уже найденных точек и положить x^p = x^p + (x_цт - x^p); повторять процедуру до тех пор, пока x^p не станет допустимой.

в) Если x^p - допустимая точка, повторять a) до тех пор, пока p=P.

г) Вычислить W(x^p) для p=0,1,...,P-1.

2. Отражение комплекса:

а) Выбрать точку x^R, для которой W(x^R) = max W(x^p) = W_max (решается задача минимизации);

б) Найти центр тяжести x_цт и новую точку x^m = x_цт + a (x_цт - x^R);

в) Если x^m - допустимая точка и W(x^m)³W_max, уменьшить в два раза расстояние между x^m и центром тяжести x^цт, продолжать поиск, пока W(x^m)<W_max.

г) Если x^m - допустимая точка и W(x^m)<W_max, то перейти к шагу 4;

д) Если x^m - недопустимая точка, то перейти к шагу 3.

3. Корректировка для  обеспечения допустимости:

а) Если x_i^m < x_i^L(нижняя граница допускаемой области), то положить x_i^m = x_i^L; если x_i^m > x_i^U(верхняя граница допускаемой области), то положить x_i^m = x_i^U.

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

 

4. Проверка условий  окончания вычислений:

а) Положить

б) Если

то вычисления прекратить; в противном случае перейти к шагу 2a.

 

2.2.4 Методы  случайного поиска

 

Наиболее простой процедурой случайного поиска является прямая выборочная процедура, заключающаяся в разыгрывании на ЭВМ последовательности точек с  координатами

                                 x_i = x_i^L +r_i (x_i^U - x_i^L), i=1,2,...,N

где

r_i - случайная величина, равномерно распределенная на интервале [0,1].

После проверки каждой точки на допустимость вычисляются значения целевой функции, которое сравнивается с наилучшим  значением, полученным к данному моменту. Если текущая точка дает лучшее значение, то она запоминается, в противном - отбрасывается. Процесс прекращается после заданного числа итераций N или по исчерпанию заданного машинного времени. Для получения 90% доверительного интервала величиной e_i(x_i^U-x_i^L), где 0<e<1, для переменной x_i совместный случайный поиск требует

испытаний. При N=5, e_i=0,01 число испытаний оценивается в 2,3×10¹⁰, что исключает возможность непосредственного использования метода.

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

Заданы границы значений всех переменных x_i^L, x_i^U, i=1,2,..., N (размерность задачи), начальные допустимая точка x⁰ и интервал поиска Dx⁰ = x_i^U - x_i^L, количество серий Q, количество точек в серии P и параметр окончания вычислений e. Для каждой из серий, начиная с q = 1, необходимо выполнить следующие действия:

 

1. Для i = 1,2,...,N вычислить 

x_i^p = x_i^q-1 +r_i Dx^q-1,

 

где

r_i - случайная величина, равномерно распределенная на интервале [-0,5,0,5].

2. Если x^p - недопустимая точка и p < P, то повторить шаг 1.

Если x^p - допустимая точка, то запомнить x^p и W(x^p) и

• если p < P, то повторить шаг 1.
• если p = P, то найти среди всех допустимых точек x^p точку с наименьшим значением W(x^p) и положить ее равной x^q.

 

3. Уменьшить интервал  поиска, полагая Dx_i^q = e_iDx_i^q-1.

4. Если q > Q, то закончить  вычисления. В противном случае  увеличить q = q + 1 и продолжить  вычисления, начиная с шага 1.

 

2.2.5 Методы  линеаризации

 

Идея методов заключается  в сведении задачи нелинейного программирования к задаче линейного программирования. С этой целью нелинейные функции  целевой функции W(x) и ограничений g(x), h(x) в разлагают ряд Тейлора  до членов первого порядка в окрестности  точки линеаризации x_t, что позволяет W(x), g(x), h(x)

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

 

 

к следующей задаче линейного  программирования:

Решая ее при помощи методов линейного программирования, находим новое приближение x^t+1. В случае нелинейных функций точка x^t+1 обычно недопустимая точка. Однако для сходимости к оптимуму достаточно, чтобы для последовательности точек {x^t}, полученных в результате решения последовательности подзадач линейного программирования, выполнялось следующее условие: значение целевой функции W и невязки по ограничениям в x^t+1 меньше их значений в точке x_t.

 

2.3 Пути решения  проблемы очередей в системе

 

В информационной системе, функционирующей в режиме реального времени, невозможно предсказать каков будет размер очереди входных данных в фиксированный момент времени, так как ее формирование носит стохастический характер [12]. В периоды пиковых нагрузок время реакции системы увеличивается. Мгновенные пиковые нагрузки, превышающие производительность системы, не являются постоянными, а возникают эпизодически. В этот момент некоторая часть входных данных стоит в очереди на обработку до тех пор, пока у системы не появится возможность их обработать. На рис. 11 изображен график изменения интенсивности потока входных данных, на котором показаны пиковые значения нагрузки системы. Информационную систему можно спроектировать таким образом, что ее пропускная способность будет представляться линией AB и она сможет обработать в моменты пиковых значений нагрузки все входные данные без задержек, но это было бы не экономично. Поэтому пропускная способность более удачной системы представлена на графике линией CD: в ней в моменты пиковых значений нагрузки обрабатываются не все входные данные, а только их часть, тогда как другая часть входных данных обрабатывается в то время, когда нагрузка на систему не превышается расчетную. Конечно, в этом случае время реакции системы увеличивается. Если же пропускная способность системы представляется линией EF, то система не в состоянии обработать некоторые из поступающих заявок.

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

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

P(n) – вероятность обращения  в банк [n] клиентов в заданный  интервал времени,  – среднее значение  [n] для заданного интервала времени.

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

Нельзя не сказать о том, что  существует зависимость между коэффициентом  использования оборудования и очередями  внутри системы: можно спроектировать удовлетворительно работающую систему  с коэффициентом использования 70%, но коэффициент, превышающий 90%, может привести к ухудшению качества обработки данных. Коэффициент использования оборудования равен отношению нагрузки на подсистему к максимально допустимой нагрузке или равен отношению времени занятости подсистемы к общему времени ее функционирования [9].

Рассмотрим очередь с одним  прибором обслуживания (см. рис. 12). Введем следующие обозначения:

t_s - время обслуживания сообщения.

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

t_q - время пребывания сообщения в системе.

w - число сообщений, ожидающих обслуживания в данный момент времени.

q - число сообщений в системе,  ожидающих обслуживания и обслуживаемых  в данный момент.

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

v - скорость обслуживания  сообщения.

 

 Так как рассматривается устойчивое состояние системы, то имеют место следующие равенства:

 

 

 

 

Благодаря устойчивости состояния  имеем:

 

 

 

Учитывая вышеизложенное получим:

Основная формула теории очередей с одним прибором обслуживания была получена Хинчиным и Поллакчеком и имеет вид:

 

 

 

Данная формула применяется  в случае экспоненциального распределения  времени поступления сообщений  и выбор сообщения для обслуживания не зависит от времени обслуживания [16]. Если выбор  сообщения для  обслуживания является зависимой величиной времени обслуживания, тогда используются уравнения, производные от уравнения Хинчина-Поллакчека: