Контрольная работа 1 страница. Межрегиональный центр переподготовки специалистов

Дисциплина

Межрегиональный центр переподготовки специалистов

«Экономико-математические методы и модели

в отрасли связи»

Вариант № 9

	Выполнил: слушатель гр. ФКТ-23   Проверил: преподаватель Батый Ада Рамазановна

ЗАДАЧА № 1

На территории города имеется три телефонных станции: А, Б и В. Незадействованные емкости станций составляют:

на станции А - Q_А=1600 номеров,

на станции Б - Q_Б=800 номеров,

на станции В - Q_В=400 номеров.

Потребности новых районов застройки города в телефонах составляют:

1 - q₁=800 номеров,

2 - q₂=900 номеров,

3 - q₃=400 номеров,

4 - q₄ = 700 номеров.

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

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

Таблица 1.1, Незадействованные ёмкости телефонных станций.

Возможности станций, номеров	Варианты
QА
QБ
QВ

Таблица 1.2, Спрос на установку телефонов.

Спрос районов, номеров	Варианты
Q1
Q2
Q3
Q4

Таблица 1.3, Среднее расстояние от станции до районов застройки, км.

Станции	РАЙОНЫ
А
Б
В

Решение:

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

Q_A+Q_Б+Qв= q₁+q2+q₃+q₄ =1600+800+400=800+900+400+700=2800

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

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

Для решения задачи используем способ «наименьшего элемента», т.к этот метод позволяет получить решение более близкое к оптимальному.

Станции	РАЙОНЫ	Возможности станций, номеров
А
Б
В
Спрос районов, номеров

Из всех расстояний от станции до районов застройки выбираем наименьшую. Такой минимальной ценой в нашем примере является элемент Б3, равный 1. С клетки Б3 следует начинать составление опорного плана. Спрос района 3 составляет 400 номеров, а станция Б может обеспечить 800 номеров. Следовательно, спрос района 3 может быть полностью удовлетворен за счет станции Б. При этом остаток свободных номеров станции Б составляет 400 ед.

Вследствие того, что спрос района 3 удовлетворен полностью, столбец 3 в исходной таблице можно вычеркнуть. Наименьшими элементами, в оставшейся части таблицы являются Б2 и В4, выберем В4 наименьший элемент равен 2. Спрос района 4 полностью удовлетворяется станцией В. Вследствие того, что свободная номерная емкость станции В полностью использована, строку В исходной таблицы можно вычеркнуть. Так как элементов равных 2 было два следующей заполняем клетку Б2, спрос 2 района будет удовлетворен не полностью, так как на станции Б осталось всего 400 свободных номеров, которые мы и проставляем в данную клетку, после чего строку Б можно вычеркнуть. У нас осталась незаполненными клетки А1, А2 и А4 которые можно заполнить единственным образом, за счет станции А в соответствии со спросом.

Полученное методом наименьшего элемента решение задачи показано в таблице 3 протяженность линий согласно этому решению составит:

800 * 4 + 500 * 5 + 300 * 4 + 400 * 2 + 400 * 1 + 400 * 2 = 8100 км.

Станции	РАЙОНЫ	Возможности станций, номеров
А
Б
В
Спрос районов, номеров

Составим таблицу модифицированного распределительного метода, принимая в качестве исходного решение по методу наименьшего элемента.

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

Станции	Дополнительный столбец	РАЙОНЫ	Возможности станций, номеров
Дополнительная строка
V1	V2	V3	V4
А	UА
Б	UБ
В	UВ
Спрос районов, номеров

Первый этап расчетов заключается в определении значений клеток, образующих дополнительную строку и дополнительный столбец. Во всех случаях верхняя клетка дополнительного столбца (строка А) получает значение 0. Этот 0 будет фигурировать в процессе всего решения.

Рассчитаем значения других дополнительных клеток. Если значения клеток, образующих дополнительный столбец, обозначить через U_А, U_Б, U_В, а значение клеток, образующих дополнительную строку – V₁, V₂, V₃ и V₄, то исходным положением для расчета их значений будет равенство U_i + V_j = - С_ij, где С_ij – среднее расстояние от станции до районов застройки и клетка на пересечении рассматриваемых строки и столбца. При этом определяются значения клеток тех столбцов и строк, пересечения которых образуют занятые места.

Начнем с первой клетки дополнительного столбца, значение которой принято равным 0. Для столбца, соответствующего району 1, имеем 0+V₁ = -4; отсюда V₁ = -4.

Для столбца 2: 0 + V₂ = -5; V₂ = -5.

Для столбца 4: 0 + V₄ = -4; V₄ = -4

Для столбца 3 в строке А такого равенства составить нельзя, так как клетки А3 является свободным местом.

Аналогично составим уравнения для строки Б: U_Б + V₂ = -2; так как V₂ = -5, получим: U_Б = -2 +5 = 3; 3 + V₃ = -1; V₃ = 2.

Для строки В: U_B + V₄ = -2. Но поскольку V₄ = -4, то U_B = 2.

Получены значения всех клеток, образующих дополнительные строку и столбец. Эти значения записываются на соответствующие места в таблице:

Станции	Дополнительный столбец	РАЙОНЫ	Возможности станций, номеров
Дополнительная строка
-4	-5	-4	-4
А
Б
В
Спрос районов, номеров

Найденные значения клеток позволяют провести исследование свободных мест. Его целью является выявление отрицательных свободных мест. Если U_i + V_j меньше соответствующего значения расстояния (в клетке на пересечении i-й строки и j-го столбца), взятого с обратным знаком, то свободное место (i, j) отрицательно и решение может быть улучшено.

Для свободных мест:
А3 0 - 4 > -6;
Б1 3 – 4 > -3;
В4 3 - 4 > -3;
В1 2 - 4 > -6;
В2 2 - 5 > -7;

В3 2 – 4 > -5.

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

ЗАДАЧА № 2

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

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

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

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

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

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

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

Решение:

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,135	1,08
		0,27	1,89	0,27
		0,27	1,62	0,54
	1,33	0,18	0,9	0,54
	0,67	0,09	0,36	0,36
	0,27	0,036	0,108	0,18
	0,09	0,012	0,024	0,072
	0,025	0,0034	0,0034	0,024
	0,0063	0,00085		0,0069
Итого	7,39		5,99	1,99

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

ЗАДАЧА № 3

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

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

Вариант	А	Б	В	Г	Д	Е
A		-
Б
В				-
Г					-
Д						-
Е							-

Решение:

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

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

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

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

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

	А	Б	В	Г	Д	Е
А	-						2	min в строке 1
Б		-					7	min в строке 2
В			-				6	min в строке 3
Г				-			2	min в строке 4
Д					-		14	min в строке 5
Е						-	7	min в строке 6

	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-

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

	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-
	­ min в столбце 1	­ min в столбце 2	­ min в столбце 3	­ min в столбце 4	­ min в столбце 5	­ min в столбце 6

	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-

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

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

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

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

	А	Б	В	Г	Д	Е
А	-			0(6)
Б		-				0(3)
В			-	0(5)
Г	0(2)			-
Д	0(0)		0(2)		-	0(0)
Е		0(1)			0(5)	¥

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

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

	А	Б	В	Д	Е
Б		-
В			-
Г	-
Д				-
Е					-

Матрица С_1,1

	А	Б	В	Д	Е
Б		-
В			-
Г	-
Д				-
Е					-

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

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

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

	А	Б	В	Г	Д	Е
А	-			∞
Б		-
В			-
Г				-
Д					-
Е						-

Матрица С_1,2

Дата добавления: 2015-04-24