Учебник системный анализ - Антонов

'1 ,

11

1;':

,11'

1"

I

!

Рассмотрим пример решения задачи нелинейноro программирова­ ния с ограничениями в виде неравенств. Пусть требуется минимизиро­

вать функцию

f(X) = ЗxI2 +4X1X2 +5х;

приограничеНИЯХХ1 ~O; Х2 ~O; Х1 +Х2 ~4.

Перепишем условие задачи следующим образом:

f(x) = 3XI2 +4X1X2 +5х;,

-Х1 ::;0; -Х2 ::;0; -X1 - X2 ::;-4.

Преобразуем ограничения, добавив в левую часть ослабляющие пере­

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

-XI +UI2 =0; -х2 +и;=0; -XI -X2 +U;=-4.

Далее запишем функцию Лагранжа

F(Х,и,Л) =3X~ +4X1X2 +5х; +ЛI(U~ -Х1)+Л2(U; -Х2)+Лз(U; -Х1 -Х2 +4).

Необходимые условия минимума для данной функции:

6Х1 +4х2 -лl -лз =0;

4Х1 +10Х2 -1..2 -Лз =0;

-Х1 ::;0;

-Х2 ::;0;

-Х1 -Х2 ::;-4;

Л1Х1 =0;

\ ",

Л2Х2 =О;

Лз(4-Х1 -Х2) =0;

Лl'Л2,Лз ~ о.

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

Лагранжадолжен быть отличен от нуля. Положим "'. = "'2 = О, тоща (по­

скольку решается задача минимизации) должно выполияться неравен­

ство "'з> О, откуда следует 4 - х. - Х2= О или 4 - х.= х2• Подставляем

данное выражение для параметраХ2 в два первых равенства и решаем их:

6ХI +4(4-х1)-лз =0; {4Х1 +10(4-хl)-лз =0.

342

6х! +16-4Х1 -Лз =0; {4Х1 +40-10хt -лз =0.

Приводя подобные члены, получим

2ХI+16-Лз=0;

{ -6Х1 +40-1..з =0.

Перенесем множитель Лагранжа в правую часть:

2ХI+16=лз;'

{ -6Х1 +40 = Лз·

Решая данную систему, получим

Нетрудно проверить, что эти решения являются условиями мини­

мума и функция имеет минимальное значение, равное 44 в точке с ко-

ординатами (3, 1).

1:

1,

I

11

I

I

·1

1'!

Рассмотрим некоторые Понятия теории массового обслуживания более подробно. Одно из исходных- понятие ВХОдящего потокатребо­

ваний, которыйпредставляетсобой совокупностьтребований, поступа­

ющих в систему и НУЖДающихся в обслуживании. В начальный момент

времени в системе может находиться некоторое число требований.

Следующее требование поступает через случайное время, которое

имеет определенный закон распределения. Случайны также длитель­

ности между моментами поступления последовательных требований.

Промежуткимеждупоступлениямитребованийвомногих прикладных

задачах можно считать взаимно независимыми. Однако существуют

примеры, когда это предположение не Выполняется. Скажем, при дви­

жении Потока транспорта через перекресток интервалы между прохож­

дением очередных машин будут завИСимыми событиями.

В системумассовогообслуживания требованиямогутпоступать из

конечной или бесконечной совокупности, которая может СОСтоять из

различных категорий требований. Требования каждой из категорий

могут поступать с различным распределением, по одиночке или в со­

ставе группы, и занимать место в очереди в устаНОвившемся порядке.

Распределение Входящего потока требований может зависеть от рас­

пределения Выходящего потока. Например, в больницу пациенты при­

нимаются только при наличии освободившихся мест.

КаждойизСМО свойственнаопределеннаяорганизация. По соста­ вуСМОразделяютнаодноканальныеимНогоканальные. Многоканаль­

ные системы могут СОстоять из каналов одинаковой и разной произво­

дительности (пропускной способности). СМО классифицируются по

времени пребывания требования в системе до начала обслуживания.

Выделяют каналы с неограниченным временем ожидания, каналы с

отказами и каналы смешанного типа. В системах снеограниченным

временем ожидания очередная заявка, застав все обслуживающие ка­

налы занятыми, становится в очередь и ДОжидается до тех пор, пока

один из обслуживающих каналов не освободится. В системах с отка­

зами всякое вновь поступившее требование, застав все приборы заня­

тыми, покидает систему. В системах смешанного типа поступившее

требование, застав все приборы занятыми, станОВится в очередь. Но в ней оно может находиться ограниченное время, после истечения кото­

рого, не ДОждавшись обслуживания, требование покидает систему.

Всистемахсожиданиемиспользуютсяследующиедисциплиныобслу­

живания:

• первым пришел - первым обслужился (данная дисциплина нахо­

дит наиболее широкое применение и обозначается как FIFO - исполь­

зуется аббревиатура английского названия first input - first output);

, :

I

•дисциплина обслуживания по приоритетам;

•случайный выбор обслуживания.

При обслуживании по приоритетам в случае поступления в систе­

му требования с более высоким приоритетом обслуживание остальных требований может прерываться либо оно может быть завершено. В редких случаях встречается дисциплина обслуживания «последним пришел - первым обслужился».

СМО классифицируют по порядку занятия свободных каналов вновь поступившими требованиями, а именно:

• каналы подключаются в строгом порядке, определяемом приори­

тетом использования;

• каналы обслуживают поступившие требования в порядке освобож­

В заключение параграфа еще раз подчеркнем, что общеи ОСОбе~­ ностью всех задач теории массового обслуживания являет:я случаи­ ный характер исследуемых явлений. Количество требо~ании на обслу­

живание временные интервалы между их поступлениями, длительность

обслужи~ания- величиныслучайные.Основнымизадачами,решаемы­

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

в очереди, минимизация длины очереди и Т.П.

11.2. Характеристика входящего потока требований

Процесс поступления в СМО потока требований я~ляется случай­

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

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

ни.Числоn реализацийсобытияЕ, происходящихвтечениеинтервала

времени 't, является случайной величиной, которую будем обозначать

через N('t). Вероятность того, что N('t) = n, будем обозначать Pi't).

Сделаем следующие предположения.

1. Pn('t) зависит только от величины 't и не зависит от момента на­ чала отсчета (условие стационарности потока).

2. N('t) не зависит от числа реализаций события Е, пр~исшедших в

любые предшествующие 't интервалы времени, т.е. случаиная величи­

наN('t)He зависит от предыстории процесса (условие отсутствия послед­

ствий).

:':1',

I

I

I,!

3. Вероятность того, что событие Е произойдет более одного аза в интервале времени dt - бесконечно малая величина по сравненJю с

1

Посколькубылоотмечено, чтоP\(dt) = Adt, следо:вагельно Р =1- Adt Произведем аналОГИЧные Вычисления для участка't пр~и~вольноЙ

длительности. Рассмотриминтервал [о, 't+d't] и определимвероятность

1)n событийреализовалисьв интервале [о, 't] и ни одного события

винтервале времени ['t, 't+d't];

2)n - 1 событие реализовано в интервале [о, 't] и одно событие в

интервале времени ['t, 't+d't].

Вероятнобстьтого, чтов интервале времени ['t, 't+d't] не произойдет

ни одного со ытия, посчитана и равна

Ро=l- Adt.

Рn('t +d't) =Рn('t)(1- Лd't)+ Рn-1('t)Лd't.

Раскроем скобки:

348

Произведем элементарные преобразования:

Зададим начальные условия, состоящие в том, что априори посту­ лируется отсутствие требований в начальный момент времени Ро(О) = 1, Рn(О) = о, n = 1, 2, .... с учетом начальныхусловий из последнего уравне­

ния получаем Po('t) = е-Лt• Далее, подставляя выражение (11.2) в (11.1),

получаем зависимость для вычисления вероятности нахождения в сис­

теме одного требования, и, продолжая процесс вычисления по индук­

ции, приходим К следующим соотношениям:

Рn('t) = -'--"'----

n!

Полученные выражения представляют собой распределение Пуас-,

сона. Отметим, что величина Л.'t - среднее число событий Е в интер­

вале 't. Непосредственной подстановкой выражений полученной систе­

мы выводим следующую зависимость:

л't

Рn+1('t) = --n+1 Рn('t).

Процесс многократного появления однородных событий через слу­ чайные интервалы времени при выполнении условий стационарности, ординарности и отсутствия последействия называется процессом Пу­

ассона.

Распределеиие иитервалов между двумя событиями. Опреде­ лим закон распределения между двумя последовательными события­

ми.

Время поступления требований в систему подчиняется пуассонов­

скому закону распределения (процесс поступления требований - пуас­ соновский процесс), где е - случайная величина, определяющая длину

интервала между двумя соседними требованиями; f (е) - плотность

,11:

!i

распр~де~ения случайной величины е; F(e) - функция распределения

случаинои величины е Fce) =pce~E».

Вер,?ятность того, что на рассматриваемом интервале времени не

произоидет ни одного события, равна

Р(Э)= (А.е)0 е-А6 =е-А6

О! .

ТогдаПЛотность распределения случайной величиные при пуассо­

новском процессе поступления требований будет иметь вид

f(Э) = л.е-А6 .

Моменты распределения определяются следующим образом:

М(Э)=.! D(Э)=_1

1..' 1..2,

где л. - интенсивность потока требований.

Величина 1/л. представляет собой среднее значение длины интер­

вала между двумя последовательными событиями, а величина Л. - ин­ тенсивность потока требований или среднее число их за единицу вре­

мени.

Длительиость иитервала между (n, n + т) событиями. Рас­

смотрим процесс Пуассона с интенсивностьюЛ. иопределим законрас­ пределения длительности интервала между n и n + т событиями. Дли­

тельность этого интервала представляет собой сумму т подынтерва­

лов, имеющих одно и то же распределение/се) = л.е-М• Распределение суммы одинаково распределенных подынтервалов определяется как

свертка и имеет вид

f т(Э) = л.(А.е)m-I е-Ав

(m-l)!

- это распределение Эрланга. Его математическое ожидание и диспер­

сия выражаются Соответственно следующим образом:

Время Обслуживаиия. Время обслуживания - это характеристи­

ка обслуживающего канала, которая определяет его пропускную спо­

собность. Предполагается, что время обслуживания - случайная ве­

личина tобол, которая полностью характеризуется законом распределе­

ния. В случае экспоненциального законараспределениявремени обслу-

350

tобел

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

подчиняется экспоненциальному закону распределения.

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

начена.

Показатели эффективности зависят от трех факторов: 1) характе­ ристик качества и надежности системы; 2) экономических показателей; 3) условий, в которых эксплуатируется система (комплекс внешних и внутренних факторов, параметры потока требований и пр.).

Эффективность систем обслуживания можно характеризовать боль­ шим числом всевозможных количественных показателеЙ. Наиболее

широкое применение находят следующие:

• вероятность потери требования в СМО; применительно к систе­ мам обслуживания эта величина равна вероятности того, что все об­

служивающие каналы заняты;

• вероятность того, что занятыми являются k каналов обслужива­

ния (Pk); РО - вероятность того, что все каналы свободны;

m-I

• среднее число занятых каналов Nз = LkPk ; этот показатель ха­

k=1

рактеризует степень загрузки системы;

• среднее число каналов, свободных от обслуживания,

m-I

N o = L(m-k)Рk ;

k=O

N

• коэффициент простоя каналов Кп = ~ ;

т

• коэффициент загрузки каналов Кз = -Nз .

т

Для систем с ожиданием используются дополнительные характе­

ристики:

•среднее время ожидания требований (ждут сами требования);

•вероятность того, что время пребывания в очереди не превысит какой-либо определенной величины;

•средняя длина очереди;

•среднее число заявок в сфере обслуживания;

•вероятность того, что число требований в очереди, ожидающих

начала обслуживания, больше некоторой заданной величины;

1,

I

I , '

,

1, 1

I

'1,1

1

li 1

'1'I

1\

11

1111'

111,11

1,11

1;

"

1,

,1

"

li,

1

,1

• стоимостные показатели: стоимость обслуживания каждого тре­

бования в системе; стоимость потерь в единицу времени, связанных с

ожиданием заявки в очереди; стоимость потерь, связанных с уходом

требования из системы; стоимость единицы времени простоя.

11.3. Система массового обслуживания с ожиданием

Система массового обслуживаиия с ожиданием - это такая си­

стема, которая имеет возможность ставить заявки в очер~дь, где эти

заявки ожидают обслуживания. Системы массового обслуживания с ожиданием бывают разомкнутые и замкнутые. Разомкнутая система массового обслуживания - это система с неограниченным источником

потока требований. Примерами разомкнутой системы массового обслу­

живания могут служить пассажиры, покупающие билеты в кассе, поку­ патели в магазине и т.п. Замкнутая система массового обслуживания

- система, в которой поток требований ограничен. Примерами замкну­

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

конечно и чаще всего постоянно.

Разомкиутая система с одиим каиалом обслуживаиия. Рас­ смотрим следующую систему. Имеется один канал обслуживания. Время обслуживания распределено по экспоненциальному закону с па­

раметром fl (fl- интенсивность обслуживания). Интенсивность входя­ щего потока л.. Требования обслуживаются в порядке поступления в

систему. Входящий поток требований пуассоновский. Процесс обслу­

живания не зависит от предыстории системы, зависит только от теку­

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

рактеризуется матрицей переходных вероятностей. Описанный процесс

представлен на рис. 11.2.

Введем обозначения: Е. - состояние, при котором в системе нахо­ дится n требований; p.(t) - безусловная вероятность этого состояния в

момент времени t.

По условию ординарности за время dt не может поступить больше одного требования. Вероятность поступления требования за отрезок

времени длительностью dt равна A.dt.

352

1

Рис. 11.2. Схема одноканальной разомкнутой СМО с ожиданиеМ

Рассмотрим процесс функционирования такой системы. За отрезок

времени длительностью dt возможны следующие переходы:

Ео ~Eo; Ео ~El; Е1 ~Eo; Е1 ~El; Е1 ~E2; Е2 ~El;

Покажем, как вычисляются вероятности переходов. Пусть A.dt- ве­

роятность поступления нового требования (в интервале dt), f.1dt - веро­

ятность окончания процесса обслуживания одного требования (в интер­

вале dt).

Рассмотрим переход Е. ~ Е•. Событие Е. при условии, что преды­

дущее событие было также Е., может реализоваться двумя способами: 1) за время dt в систему поступило одно тре~ование и одно требо:

вание системой обслужилось; вероятность такои реализации событии

равна A.dt . f.1dt;

2) в интервале времени dt ни одно требование не поступило и ни одно

требование не обслужилось. Вероятность такой реализации соответ­

ственно равна (1 - A.dt)(1 - f.1dt).

Данные события несовместны и поэтому можно записать

Р(Е. ~ Е.) =Лdt· J.1dt +(1- Лdt)(I- J.1dt) =1- Лdt - J.1dt.

В данном выражении мы пренебрегаем членом второго порядка мало­

сти (dt)2.

По аналогии вычисляем вероятности для всех возможных переходов:

Р(Ео ~ Ео) = l-Лdt;

P(Et ~ Et +1 ) = Лdt;

P(Et +1 ~ Et ) = J.1dt;

P(Et ~ Et ) = 1- Лdt - J.1dt.

353

2З-4ЗSS

'1

,I

11'

11,1: '.

l'

i 111,' 1

1 Ili, .

,

'11 11 '

il

" . ··.·.1

1

,'1.1

1

1,

'1

1,.

~~;;::::М с выражением(11.5) те же преобразования, что ис (11.3) и

Устаиовившийся режим. Если при t ~ 00 для любого решения урав­

нений (11.4), (11.6) существуетпредел liтP;(t)=P; (; = О, 1,2, ...), то в данной

смо имеет место установившийся режим. Такая система называется статистически устойчивой.

Величины Р; называются стационарным решением системы урав­ нений. Для стационарного решения производные от вероятностей Pit), i = О, 1,2, ... равны нулю, следовательно,

Отметим, что в любой момент времени система может находить­ ся только в одном из состояний, следовательно, события несовместны:

IЛ=l

;=0

Обозначим ~= Ч';втеориимассовогообслуживанияданныйпоказатель

J..L

называется коэффициентом использования (загрузки) смо. Если

'р > 1, установившегося режима не существует. Если 'Р < 1, установив­

шийся режим существует и возможно вычисление соответствующих ве­

роятностей. Преобразуем выражение (11.10). Сгруппируем вероятнос­ ти в левой части, а единицу перенесем в правую часть

11

,'i i'

I

11

-(л.+ mJ.l)Pj + л.Рj_1 + 111J.lPj +1 = о, при j ~ n.

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

1. Вероятность того, что в системе находится k требований, при­

чем число требований меньше или равно числу обслуживающих кана­

лов,

откуда следует

1

4. Вероятность того, что все каналы заняты обслуживанием и s тре­ бований находится в очереди

",m+>

Рmн =-,-, РО , s >0.

т.т

5. Вероятность того, что время пребывания в очереди больше не­

которой заданной величины t

P('t > t) =1te-I1(m-IJ/)1 , где 1t =L Pk •

k=m

6. Среднее время ожидания

359

",

l'

1',

['

I!