Задача № 2

Необходимо оценить работу автоматической телефонной станции (АТС), которая имеет n=8 линий связи. Моменты поступления вызовов на станцию являются случайными и независимыми друг от друга. Средняя плотность потока равна λ=1 вызову в единицу времени. Продолжительность каждого разговора является величиной случайной и подчинена показательному закону распределения. Среднее время одного разговора равно t_обс = 2 единицы времени.

Автоматические телефонные станции относятся к типу систем обслуживания с потерями (с отказами). Абонент получает отказ в случае, если все линии заняты.

Для определения основных показателей работы АТС необходимо рассчитать значение поступающей нагрузки в Эрлангах Ψ и вероятности, что из n-линий k будет занято

Для расчета используются формулы:

Далее следует определить вероятность отказа Р_отказа , среднее число занятых и среднее число свободных линий, коэффициенты занятости и простоя линий и сделать вывод о качестве обслуживания абонентов и эффективности использования линий связи.

Исходные данные:

Варианты	9
Количество линий, n	8
Плотность потока, λ	1
Среднее время разговора,tобс	2

Решение:

1. Определим значение поступающей нагрузки Ψ по формуле

= 1·2=2

2. Найдем вероятность того, что все линии связи свободны по формуле:

,

где n количество линий связи, к=1,2,…,n

Вероятность того, что все линии связи будут свободны, составляет 13,5%

3. Рассчитаем вероятности занятости k-линий из n, по формуле

k=1,

k=2,

k=3, =0,18

k=4,

k=5,

k=6,

k=7,

k=8,

4. Найдем вероятность того, что все линии связи заняты, т.е. вероятность отказа, по формуле:

Вероятность отказа равна 8,5%.

5. Найдем среднее число занятых линий по формуле:

Среднее число занятых линий равняется 1,99.

6. Коэффициент занятости линий =

7. Найдем среднее число свободных линий по формуле:

Среднее число свободных линий равно 5,99

8.Коэффициент простоя линий

Коэффициент простоя можно было посчитать другим методом 1-0,25=0,75

K
0	1	0,135	1,08
1	2	0,27	1,89	0,27
2	2	0,27	1,62	0,54
3	1,33	0,18	0,9	0,54
4	0,67	0,09	0,36	0,36
5	0,27	0,036	0,108	0,18
6	0,09	0,012	0,024	0,072
7	0,025	0,0034	0,0034	0,024
8	0,0063	0,00085	0	0,0069
Итого	7,39	1	5,99	1,99

Вывод: качество обслуживания абонентов приемлимое, потому как вероятность отказа составляет 8,5%, но эффективность использования линий низкая, потому что очень высокий процент простоя линий связи 75%.

Задача № 3

В таблице приведены затраты времени почтальона (в минутах) на проход между пунктами доставки на участке. Используя метод "ветвей и границ", найти маршрут почтальона, при котором затраты времени на его проходбудут минимальными.

Исходные данные.

Вариант			А		Б		В		Г		Д		Е
A	9	-		21		12		2		15		23
Б	9	18				20		10		19		7
В	9	12		20		-		6		18		17
Г	9	2		10		8		-		21		16
Д	9	14		15		18		20		-		14
Е	9	24		7		18		16		14		-

Решение:

Задачу решаем методом теории графов, известным как метод "ветвей и границ".

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

Обозначим за Г множество всех обходов почтальона (т. е. всех простых ориентированных остовных циклов). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число φ(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов дуг графа и является оценкой снизу для стоимости минимального тура коммивояжёра. Приведённую матрицу весов данного графа следует запомнить, обозначим ее через С₁.

Подсчитаем φ(Г). Для этого выполним приведение матрицы весов.

Сначала – по строкам:

	А	Б	В	Г	Д	Е
А	-	21	12	2	15	23	2	¬ min в строке 1
Б	18	-	20	10	19	7	7	¬ min в строке 2
В	12	20	-	6	18	17	6	¬ min в строке 3
Г	2	10	8	-	21	16	2	¬ min в строке 4
Д	14	15	18	20	-	14	14	¬ min в строке 5
Е	24	7	18	16	14	-	7	¬ min в строке 6

	А	Б	В	Г	Д	Е
А	-	19	10	0	13	21
Б	11	-	13	3	12	0
В	6	14	-	0	12	11
Г	0	8	6	-	19	14
Д	0	1	4	6	-	0
Е	17	0	11	9	7	-

Теперь − по столбцам:

	А	Б	В	Г	Д	Е
А	-	19	10	0	13	21
Б	11	-	13	3	12	0
В	6	14	-	0	12	11
Г	0	8	6	-	19	14
Д	0	1	4	6	-	0
Е	17	0	11	9	7	-
	0	0	4	0	7	0
	­ minв столбце 1	­ minв столбце 2	­ minв столбце 3	­ minв столбце 4	­ minв столбце 5	­ minв столбце 6

	А	Б	В	Г	Д	Е
А	-	19	6	0	6	21
Б	11	-	9	3	5	0
В	6	14	-	0	5	11
Г	0	8	2	-	12	14
Д	0	1	0	6	-	0
Е	17	0	7	9	0	-

Сумма констант приведения φ(Г)=2+7+6+2+14+7+4+7=49.

Обозначим полученную матрицу через С₁ и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на ¥ приводит к изменению лишь двух слагаемых суммы констант приведения φ(Г) – по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца.

Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 6 (c_А,Г=c_А,Д=6), и минимума по четвёртому столбцу Г, равного 0 (c_Г,В=0), без учета самого c_А,Г.

Итак, запишем приведённую матрицу еще раз, указывая рядом с каждым нулем его вес:

	А	Б	В	Г	Д	Е
А	-	19	6	0(6)	6	21
Б	11	-	9	3	5	0(3)
В	6	14	-	0(5)	5	11
Г	0(2)	8	2	-	12	14
Д	0(0)	1	0(2 )	6	-	0(0)
Е	17	0(1)	7	9	0(5)	¥

Самым тяжелым оказывается нуль в клетке (А,Г).

Разобьём множество Г на две части: множество (все циклы, проходящие через дугу (А,Г)) и (все циклы, не проходящие через дугу (А,Г)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С_1,1, полученная вычёркиванием соответствующих строки (строку А) и столбца (столбец Г). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ∞ ; числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). В данном случае из города Г мы уже не можем проехать в город А, поэтому в клетке (А,Г) ставим знак ∞.

А Б В Д Е Б 11 - 9 5 0 В 6 14 - 5 11 Г - 8 2 12 14 Д 0 1 0 - 0 Е 17 0 7 0 - Матрица С1,1 А Б В Д Е Б 11 - 9 5 0 В 1 9 - 0 6 Г - 6 0 10 12 Д 0 1 0 - 0 Е 17 0 7 0 - Матрица С1,1 после приведения

Сумма констант приведения матрицы С_1,1 здесь равна 7, поэтому φ(Г_{(А,Г)})= φ_{А,Г}=49+7=56. Сопоставим результат φ(Г_{(i,j)}) множеству Г_{(i,j)}, (в нашем случае Г_{(А,Г)}).

Множеству (в нашем случае), в свою очередь, соответствует другая матрица – С_1,2, полученная заменой на ∞ элемент с_А,Г в матрице С₁:

А Б В Г Д Е А - 19 6 ∞ 6 21 Б 11 - 9 3 5 0 В 6 14 - 0 5 11 Г 0 8 2 - 12 14 Д 0 1 0 6 - 0 Е 17 0 7 9 0 - Матрица С1,2

	А	Б	В	Г	Д	Е
А	-	13	0	∞	0	15
Б	11	-	9	3	5	0
В	6	14	-	0	5	11
Г	0	8	2	-	12	14
Д	0	1	0	6	-	0
Е	17	0	7	9	0	-

Матрица С_1,2 после приведения

Сумма констант последнего приведения равна 6, так что φ()=49+6=55. Теперь выберем между множествами Г_{(i,j)} и то, на котором минимальна функция j. В нашем случае из множеств, которому соответствует меньшее из чиселφ(Г_{(А,Г)})=56 и φ()=55 .Поэтому дальнейшей разработке подвергнется множество . Итак, выделена определенная дуга (А,Г) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл , если данная ветвь будет продолжена до конца и иметь минимальный вес.

В матрице С_1,2,1 подсчитаем веса нулей (веса нулей указаны в скобках):

	А	Б	В	Г	Д	Е
А	-	13	0(0)	-	0(0)	15
Б	11	-	9	3	5	0(3)
В	6	14	-	0(8)	5	11
Г	0(2)	8	2	-	12	14
Д	0(0)	1	0(0)	6	-	0(0)
Е	17	0(1)	7	9	0(0)	-

Самым тяжёлым является нуль с номером (В,Г), так что теперь следует рассматривать множества и. Обратимся к первому из них. Необходимо заменить на¥ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем циклам, которые проходят через уже отобранные ранее ребра.

Поскольку, вычеркнув строку В и столбец Г в матрице С_1,2, нужно также заменить на ∞ числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (В,Г) надо поставить символ ∞. Получим матрицу С_1,2,1:

	А	Б	В	Д	Е
А	-	13	0	0	15
Б	11	-	9	5	0
Г	-	8	-	12	14
Д	0	1	0	-	0
Е	17	0	7	0	-

Сумма констант остается неизменной, так как матрица не требовала приведения φ()=55

А Б В Г Д Е А - 13 0 - 0 15 Б 11 - 9 3 5 0 В 6 14 - - 5 11 Г 0 8 2 - 12 14 Д 0 1 0 6 - 0 Е 17 0 7 9 0 - Матрица С1,2,2

А Б В Г Д Е А - 13 0 - 0 15 Б 11 - 9 0 5 0 В 1 9 - - 0 6 Г 0 8 2 - 12 14 Д 0 1 0 3 - 0 Е 17 0 7 6 0 - Матрица С1,2,2 после приведения

Сумма констант приведения φ()=55+8=63. Следовательно дальнейшей разработке подлежит. «Взвешиваем» нули в матрице С_1,2,1:

	А	Б	В	Д	Е
А	-	13	0(0)	0(0)	15
Б	11	-	9	5	0(5)
Г	0(8)	8	-	12	14
Д	0(0)	1	0(0)	-	0(0)
Е	17	0(1)	7	0(0)	-

Самым тяжелым является нуль с номером (Г,А), теперь рассмотрим множества и.

Вычеркиваем строку Г и столбец А , ставим ∞ в клетке (А,Г) и получаем матрицу С_1,2,1,1

	Б	В	Д	Е
А	13	-	0	15
Б	-	9	5	0
Д	1	0	-	0
Е	0	7	0	-

Матрица не требует приведения и сумма констант приведения останется без изменений φ()=55.

Рассмотрим матрицу С_1,2,1,2:

А Б В Д Е А - 13 0 0 15 Б 11 - 9 5 0 Г ¥ 8 - 12 14 Д 0 1 0 - 0 Е 17 0 7 0 - Матрица С1,2,1,2

А Б В Д Е А - 13 0 0 15 Б 11 - 9 5 0 Г - 0 - 4 6 Д 0 1 0 - 0 Е 17 0 7 0 - Матрица С1,2,1,2 после приведения

Сумма констант приведения φ()=55+8=63.

Произведем оценку нулей в матрице С_1,2,1,1

	Б	В	Д	Е
А	13	-	0(13)	15
Б	-	9	5	0(5)
Д	1	0(7)	-	0(0)
Е	0	7	0(0)	-

Самый тяжелый вес равный 13 имеет нуль в клетке с номером (А,Д), следовательно будем рассматривать множества и. Вычеркиваем строку А и столбец Д и заменяем число в клетке (Д,В) на знак ∞.

Получаем матрицу С_1,2,1,1,1:

Б В Е Б - 9 0 Д 1 - 0 Е 0 7 - Матрица С1,2,1,1,1

	Б	В	Е
Б	-	2	0
Д	1	-	0
Е	0	0	-

Матрица С_1,2,1,1,1после приведения

Сумма констант приведения φ()=55+7=62.

Для множества матрица С_1,2,1,1,2 приобретает вид:

Б В Д Е А 13 - - 15 Б - 9 5 0 Д 1 0 - 0 Е 0 7 0 - Матрица С1,2,1,1,2

Б В Д Е А 0 - - 2 Б - 9 5 0 Д 1 0 - 0 Е 0 7 0 - Матрица С1,2,1,1,2 после приведения

Сумма констант приведения φ()=55+13=68.

Следовательно дальше разрабатываем матрицу . «Взвешиваем» нули в матрице С_1,2,1,1,1:

	Б	В	Е
Б	-	2	0(2)
Д	1	-	0(1)
Е	0(1)	0(2)	-

У нас получилось два одинаково тяжелых нуля, разработаем матрицы и. Вычеркиваем строку Б и столбец Е и заменяем число в клетке (Б,Е) на ∞. Получаем матрицу С_1,2,1,1,1,1:

Б В Д 1 - Е - 0 Матрица С1,2,1,1,1,1

	Б	В
Д	0	-
Е	-	0

Матрица С_1,2,1,1,1,1после приведения

Сумма констант приведения φ ()=62+2=68.

Рассмотрим матрицу С_1,2,1,1,1,2:

Б В Е Б - 2 - Д 1 - 0 Е 0 0 - Матрица С1,2,1,1,1,2

Б В Е Б - 0 - Д 1 - 0 Е 0 0 - Матрица С1,2,1,1,1,2после приведения

Сумма констант приведения φ()=62+2. Получается что для дальнейшей разработки можно брать любое из множеств, если мы возьмем матрицу С_1,2,1,1,1,1 то можно отработать матрицу и следовательно мы получим кольцевой маршрут следующего вида:

(В,Г)(Г,А)(А,Д)(Д,Б)(Б,Е)(Е,В) или В→Г→А→Д→Б→Е→В.