5.Экономико-математические методы и прикладные модели

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

Система массового обслуживания (СМО) это объект, характе-

ризующийся наличием следующих элементов: 1) источник заявок или требований на обслуживание; 2) очередь; 3) обслуживающий ап-

парат (ОА).

Источник, обычно, не считается элементом СМО. Предполага-

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

СМО содержит очередь и обслуживающий аппарат.

Для описания сокращенных обозначений для однофазных СМО используется трехбуквенное обозначение вида A/B/m, где A и B описывают соответственно интервалы времени между поступле-

ниями последовательных заявок и распределение времени их обслу-

живания; m - число каналов обслуживания. A и B принимают сле-

дующие значения:

M - экспоненциальное (показательное) распределение;

Er - распределение Эрланга порядка r;

D - детерминированное;

G - распределение общего вида.

Иногда указывают емкость очереди K и емкость источника заявок M. В этом случае используется пятибуквенное обозначение

A/B/m/K/M. При отсутствии одного из двух последних индексов его значение предполагается сколь угодно большим.

СМО удобно описывать на основе диаграммы состояний, кото-

рая носит название «процесс гибели и размножения» (рис. 5.1).

134

			k	k
0	1	2		k
1	2	3	k	k+1

Рис. 5.1. Процесс гибели и размножения.

Состояние Ek обозначается овалом, в котором записывается число k. Переходы между состояниями обозначаются стрелками, на которых представлены интенсивности переходов.

Здесь k – интенсивность потока заявок, поступающих в сис-

тему, находящуюся в состоянии с номером k (количество заявок, по-

ступающих за единицу времени); k – интенсивность обслуживания в системе, находящейся в состоянии с номером k (количество заявок,

которые обслуживаются в среднем за единицу времени).

Решение этой системы в общем виде невозможно. Модель да-

же простой системы является чрезвычайно сложной и трудно анали-

зируемой. Если рассматривать СМО более сложного вида, то вычис-

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

вившемся режиме при t→∞: dp(k;t)/dt→0, p(k;t)→p(k)=const.

Выпишем некоторые формулы для систем массового обслужи-

вания.

Вероятности состояний связаны между собой формулами

	k	i 1
	p(k ) p(0)		, k 1... .
	i 1	i

Неизвестную константу p(0) найдем из условий нормировки:

p(0)			1				.
			k
				i	1
	1
			k 1i 1		i

135

Для системы M/M/1 (диаграмма состояний представлена на

рис. 5. 2) справедливы следующие формулы:

i

const и

i

const

i .

Тогда, обозначая отношение

1, получаем:

p(0) 1 , p(k )

(1 ) k , k

1...

0

1

2

n

Рис.5.2. Диаграмма интенсивностей переходов системы M/M/1.

Здесь параметр имеет смысл коэффициента использования.

Ниже будет видно, почему не рекомендуется устремлять его к еди-

нице, т.е. не следует загружать оборудование и людей на все 100%.

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

(производстве, банковской сфере, сфере обслуживания и т.д.).

Среднее число заявок в системе равно				N					, среднее время
						1
пребывания заявки в системе: T	N	1						1	.
		(1		)

Как видно, если коэффициент использования стремится к еди-

нице, среднее число заявок в системе и среднее время пребывания заявок в системе стремится к бесконечности.

Иначе говоря, если Вы набрали заказов, стремясь полностью загрузить свои мощности, то, с очень высокой вероятностью, сорвете сроки выполнения заказов.

136

Для системы M/M/m диаграмма состояний представлена на рис. 5.3.

0

1

2

m-1

(m-1) m

Рис. 5.4. Диаграмма интенсивностей переходов системы M/M/m.

Имеем следующие формулы:

		(m )k
p(0)					, k m
p(k )			k!
			k
p(0)				mm , k m
		m!
Здесь			1.
	m

Среднее число заявок в системе всегда можно найти как

N i p(i) .

i1

5.2.Линейное, целочисленное и нелинейное программирование

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

	n
экстремум функции Ц	ai xi	extr при наличии следующих ог-
i	1
раничений:
n
bij xi c j , j 1...k; xi		0 i .
i 1

Рассмотрим пример такой задачи.

137

Имеется 150 л жидкости А и 150 л жидкости Б. Для получения одной бутыли смеси 1 нужно взять 2 л жидкости А и 1 л жидкости Б,

а для получения одной бутыли смеси 2 нужно взять соответственно 1

л жидкости А и 4 – жидкости Б.Смесь 1 продаѐтся по цене 2 ден.

единицы, а смесь 2 – 3 ден. единицы за одну бутыль. Сколько нужно приготовить бутылей каждой смеси, чтобы общая их стоимость бы-

ла наибольшей, при условии, что число бутылей со смесью 2 не ме-

нее числа бутылей со смесью 1?

Введѐм следующие обозначения: х1 - количество бутылей пер-

вой смеси; х 2 - количество бутылей второй смеси. Стоимость буты-

лей первой смеси составляет 2х1 ден. единиц, а второй смеси - 3х 2

ден. единиц, т. е. необходимо максимизировать целевую функцию

(общую стоимость):

f( X ) =2х1 + 3х2→ max.

Помимо указанной функции мы имеем ряд ограничений.

1-е ограничение: можно потратить не более 150 л жидкости А:

2x1 x2 150

2-е ограничение: можно потратить не более 150 л жидкости В:

x1 4x2 150

3-е ограничение: число бутылей со смесью 2 не менее числа бутылей со смесью 1:

x1 x2 0

4-е ограничение: количество бутылей не может быть отрица-

тельным:

x1 0, x2 0

Таким образом, получаем следующую задачу: f( X ) =2х1 + 3х2→ max при условиях

138

2x1 x2 150 x1 4x2 150

х1 х2 0 x1 0, x2 0

К аналогичным задачам приводятся транспортные задачи. Они имеют, как правило, следующую формулировку.

Имеется n поставщиков и m потребителей. Каждый поставщик имеет запасы некоторого товара в объеме ai, i=1…n, а каждому потребителю необходимо получить этого товара в объеме bj, j=1…m.

Затраты на доставку одной единицы товара от поставщика № i к потребителю № j равны cij. Разработать план доставки товаров, минимизирующий издержки.

Математическая формулировка этой задачи следующая:

		n m
Ц			xij cij min ;
	i	1 j	1
m
	xij		ai
j	1
n
	xij		b j
i	1
xij		0	i, j

Если общие запасы у поставщиков меньше, чем суммарные по-

требности, то второе равенство заменяется на неравенство ( bj). Если запасы превосходят потребности, то первое равенство заменяется на неравенство ( ai).

Задачи такого типа решаются при помощи дисциплины, называемой «линейное программирование».

139