Федеральное агентство связи 

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

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

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

По  дисциплине: экономико-математические методы и модели

                                      Выполнил: Лагутин М. Е.

                                      Группа: ЭДВ-04

                                      Вариант: 8

                                      Проверил: ___________________ 
 
 
 
 
 
 
 
 

Новосибирск, 2011 г

Задача 1.

На территории города имеется три телефонных станции  А, Б и В. Незадействованные емкости  станций составляют на станции А – 1000 номеров, Б – 400 номеров, В – 500 номеров. Потребности новых районов застройки города в телефонах составляют: 1 - 700, 2 - 600, 3 - 200, 4 - 400 номеров.

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

Выполнение.

Среднее расстояние от телефонных станций до новых районов приведено в  таблице:

Проверим  соотношения между суммарной  возможностью поставщиков и суммарным  спросом потребителей:

, или 1000+400+500 ? 700+600+200+400

1900=1900

Возможность равна требованиям поставщиков

Суммарную протяженность вновь построенных  линий определим как количество подключенных абонентов умноженное на расстояния от станций до районов. Данная протяженность должна быть минимальной.

Построим  матрицу

 Характеристикой в данном случае является расстояние. Остаток емкости приведен справочно.

В клетке А1 спрос удовлетворяется полностью. В клетке А2 также есть возможность полного удовлетворения спроса. Аналогично и в клетках А3 и А4. Станция А может удовлетворить запросы любого района.

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

Аналогично  со станцией В.

Используем  метод наименьшего элемента в  столбце.

В столбце 1 наименьшим элементом является Б, однако потребность еще не удовлетворена. Следующим будет элемент А. Таком образом для района 1:

400 абонентов  станции Б, 300 абонентов станции  А. Остаток станции А 700 абонентов.

Столбец 2. Поскольку станция Б исчерпала  номерную емкость на предыдущем шаге - абоненты будут подключены со станции А. Остаток станции А равен 100 номерам.

Столбец 3. Станция В полностью перекрывает  потребность района, являясь еще  и наиболее оптимальной (станция  Б исчерпана). Остаток станции  А равен 100 абонентам, станции Б 300 абонентам.

Столбец 4. Остаток будет подключен на остатки станций А и Б.

Итоговая  матрица:

Это и  будет исходным планом.

Суммарная протяженность линий в данном плане: 300*4+600*5+100*4 +400*3+200*1+300*2=6300км.

Применим  модифицированный распределительный  метод.

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

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

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

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

А3: 0-1>-6

Б2: 7-5>-2

Б3: 7-1>-1

Б4: 7-4>-4

В1: 6-4>-6

В2: 6-5>-7

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

Задача 2.

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

Выполнение.

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

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

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

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

     Определим значение нагрузки:

Вероятность того, что все линии свободны, определяется по формуле , где n это количество линий связи.

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

Теперь рассчитаем вероятность занятости k линий из n, применив формулу:

Рассчитаем:

k=1,

k=2,

k=3, =0,184

k=4,

k=5,

То есть, соответственно, 28%, снова 28%, 18,4%, 9,4%, 3,9%.

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

Вероятность отказа в обслуживании  3,6%. Вероятность DoS, как видно из структуры формулы, катастрофически падает при увеличении числа каналов.

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

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

Коэффициент занятости 

Определим теперь число свободных линий:

Среднее число  свободных линий 3,299, коэффициент  простоя   

Либо  можно определить логически, сумма  коэффициента простоя и коэффициента занятости должна быть равна 1, то есть 1-0,396=0,604.

Вывод:

     Вероятность отказа в обслуживании не более 3,6% и  довольно высокий (39% по современным  меркам довольно высокий показатель) коэффициент занятости линий  говорит о хорошем уровне обслуживания данной схемы. Однако, число линий  можно уменьшать с достаточно большим резервом с целью экономии средств на обслуживание и оптимизации производства.

Задача 3.

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

Решение.

Данная  задача относится к «задаче коммивояжера». Коммивояжеру необходимо пройти через все точки замкнутого графа и вернуться в исходную точку маршрута.

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

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

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

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

Обнуляем и вычитаем:

По столбцам:

Обнулим:

Сумма констант приведения 4+9+5+4+7+8+2=39

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

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