Министерство  Российской Федерации  по связи и информатизации

Сибирский Государственный  Университет Телекоммуникаций и 

Информатики 

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

Дисциплина   

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

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

Контрольная работа 

Вариант № 9 
 
 
 
 
 
 

Проверил:  
 
 
 
 
 
 

2010

г. Новосибирск 
 

ЗАДАЧА 1.

     На  территории города имеется три телефонных станции А, Б и В. Незадействованные  емкости станций составляют на станции  А - Q_А=1600, Б - Q_Б=800, В - Q_В=400 номеров . Потребности новых районов застройки города в телефонах составляют: 1 - q₁=800, 2 - q₂=900, 3 - q₃=400, 4 - q₄ = 700 номеров .

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

Таблица 1.1

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

Решение:

Таблица 1.2

Исходная.

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

    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 которые можно заполнить единственным образом, за счет станции А в соответствии со спросом. Таблица 1.2 примет вид (таблица 1.3) . Полученное методом наименьшего элемента решение задачи показано в таблице 3 протяженность линий согласно этому решению составит:

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

Таблица 1.3

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

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

     Таблица 1.4

     Первый  этап расчетов заключается в определении  значений клеток, образующих дополнительную строку и дополнительный столбец. Во всех случаях верхняя клетка дополнительного  столбца (строка А) получает значение 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. 

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

     Таблица 1.5

     Найденные значения клеток позволяют провести исследование свободных мест. Его  целью является выявление отрицательных  свободных мест. Если 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 будет занято

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

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

     Решение: 

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

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

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

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

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

k=1,

k=2,

k=3,

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 

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

ЗАДАЧА 3. 

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

Таблица 3.1

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

Решение:  

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

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

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

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

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

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