«Экономико-математические методы и модели в отрасли связи» Вариант № 9

ЗАДАЧА № 1
На территории города имеется три телефонных станции: А, Б и В. Незадействованные емкости станций составляют:
на станции А - QА=1600 номеров,
на станцииБ - QБ=800 номеров,
на станцииВ - QВ=400 номеров.
Потребности новых районов застройки города в телефонах составляют:
1 - q1=800 номеров,
2 - q2=900 номеров,
3 - q3=400 номеров,
4 - q4 = 700 номеров.
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое рас ...

ЗАДАЧА № 1
На территории города имеется три телефонных станции: А, Б и В. Незадействованные емкости станций составляют:
на станции А - QА=1600 номеров,
на станцииБ - QБ=800 номеров,
на станцииВ - QВ=400 номеров.
Потребности новых районов застройки города в телефонах составляют:
1 - q1=800 номеров,
2 - q2=900 номеров,
3 - q3=400 номеров,
4 - q4 = 700 номеров.
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.

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

Таблица 1.1, Незадействованные ёмкости телефонных станций.
Возможности станций, номеров Варианты
9
QА 1600
QБ 800
QВ 400

Таблица 1.2, Спрос на установку телефонов.
Спрос районов, номеров Варианты
9
Q1 800
Q2 900
Q3 400
Q4 700
Таблица 1.3, Среднее расстояние от станции до районов застройки, км.
Станции РАЙОНЫ
1 2 3 4
А 4 5 6 4
Б 3 2 1 4
В 6 7 5 2
ЗАДАЧА № 2

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



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

Исходные данные:
Варианты 9
Количество линий, n 8
Плотность потока, λ 1
Среднее время разговора,tобс 2
ЗАДАЧА № 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 -

ЗАДАЧА № 4
На сетевом графике (рис.4.1) цифры у стрелок показывают в числителе - продолжительность работы в днях, в знаменателе - количество ежедневно занятых работников на её выполнение.
В распоряжении организации, выполняющей этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.
Используя имеющиеся запасы времени по некритическим работам, скорректируйте сетевой график с учётом ограничения по количеству рабочих.

ЗАДАЧА № 1
На территории города имеется три телефонных станции: А, Б и В. Незадействованные емкости станций составляют:
на станции А - QА=1600 номеров,
на станцииБ - QБ=800 номеров,
на станцииВ - QВ=400 номеров.
Потребности новых районов застройки города в телефонах составляют:
1 - q1=800 номеров,
2 - q2=900 номеров,
3 - q3=400 номеров,
4 - q4 = 700 номеров.
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое рас пределение емкости, при котором общая протяженность абонентских линий будет минимальной.

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

Таблица 1.1, Незадействованные ёмкости телефонных станций.
Возможности станций, номеров Варианты
9
QА 1600
QБ 800
QВ 400

Таблица 1.2, Спрос на установку телефонов.
Спрос районов, номеров Варианты
9
Q1 800
Q2 900
Q3 400
Q4 700
Таблица 1.3, Среднее расстояние от станции до районов застройки, км.
Станции РАЙОНЫ
1 2 3 4
А 4 5 6 4
Б 3 2 1 4
В 6 7 5 2
ЗАДАЧА № 2

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



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

Исходные данные:
Варианты 9
Количество линий, n 8
Плотность потока, λ 1
Среднее время разговора,tобс 2
ЗАДАЧА № 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 -

ЗАДАЧА № 4
На сетевом графике (рис.4.1) цифры у стрелок показывают в числителе - продолжительность работы в днях, в знаменателе - количество ежедневно занятых работников на её выполнение.
В распоряжении организации, выполняющей этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.
Используя имеющиеся запасы времени по некритическим работам, скорректируйте сетевой график с учётом ограничения по количеству рабочих.

Для столбца 2: 0 + V2 = -5; V2 = -5. Для столбца 4: 0 + V4 = -4; V4 = -4Для столбца 3 в строке А такого равенства составить нельзя, так как клетки А3 является свободным местом.Аналогично составим уравнения для строки Б: UБ + V2 = -2; так как V2 = -5, получим: UБ = -2 +5 = 3; 3 + V3 = -1; V3 = 2.Для строки В: UB + V4 = -2. Но поскольку V4 = -4, то UB = 2.Получены значения всех клеток, образующих дополнительные строку и столбец. Эти значения записываются на соответствующие места в таблице:СтанцииДополнительный столбецРАЙОНЫВозможности станций, номеров1234Дополнительная строка-4-5-4-4А045641600800500300Б33214800400400В26752400400Спрос районов, номеров8009004007002800Найденные значения клеток позволяют провести исследование свободных мест. Его целью является выявление отрицательных свободных мест. Если Ui + Vj меньше соответствующего значения расстояния (в клетке на пересечении 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 будет занятоДля расчета используются формулы:Далее следует определить вероятность отказа Ротказа , среднее число занятых и среднее число свободных линий, коэффициенты занятости и простоя линий и сделать вывод о качестве обслуживания абонентов и эффективности использования линий связи.Исходные данные:Варианты9Количество линий, n8Плотность потока, λ1Среднее время разговора,tобс2Решение:1. Определим значение поступающей нагрузки Ψ по формуле = 1·2=22. Найдем вероятность того, что все линии связи свободны по формуле: , где nколичество линий связи, к=1,2,…,nВероятность того, что все линии связи будут свободны, составляет 13,5%3. Рассчитаем вероятности занятости k-линий из n, по формуле k=1, k=2, k=3, =0,18k=4, k=5, k=6, k=7, k=8, 4. Найдем вероятность того, что все линии связи заняты, т.е. вероятность отказа, по формуле:Вероятность отказа равна 8,5%.5. Найдем среднее число занятых линий по формуле:Среднее число занятых линий равняется 1,99.6. Коэффициент занятости линий =7. Найдем среднее число свободных линий по формуле:Среднее число свободных линий равно 5,998.Коэффициент простоя линий Коэффициент простоя можно было посчитать другим методом 1-0,25=0,75K010,1351,08120,271,890,27220,271,620,5431,330,180,90,5440,670,090,360,3650,270,0360,1080,1860,090,0120,0240,07270,0250,00340,00340,02480,00630,0008500,0069Итого7,3915,991,99Вывод: качество обслуживания абонентов приемлимое, потому как вероятность отказа составляет 8,5%, ноэффективность использования линий низкая, потому что очень высокий процент простоя линий связи 75%.ЗАДАЧА № 3В таблице приведены затраты времени почтальона (в минутах) на проход между пунктами доставки на участке. Используя метод "ветвей и границ", найти маршрут почтальона, при котором затраты времени на его проходбудут минимальными.Исходные данные. ВариантАБВГДЕA9-211221523Б9182010197В91220-61817Г92108-2116Д914151820-14Е9247181614-Решение: Задачу решаем методом теории графов, известным как метод "ветвей и границ".Матрица считается приведенной, если в каждой строке и каждом столбце содержит не менее одного нуля. Для приведения исходной матрицы сначала в каждой строке находится наименьший элемент и вычитается из элементов своей строки, затем в приведенной по строкам матрице в каждом столбце находится наименьший элемент и вычитается из элементов своего столбца – получается приведенная матрица.Обозначим за Г множество всех обходов почтальона (т. е. всех простых ориентированных остовных циклов). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число φ(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов дуг графа и является оценкой снизу для стоимости минимального тура коммивояжёра. Приведённую матрицу весов данного графа следует запомнить, обозначим ее через С1.Подсчитаем φ(Г). Для этого выполним приведение матрицы весов.Сначала – по строкам:АБВГДЕ А-2112215232min в строке 1Б18-20101977min в строке 2В1220-618176min в строке 3Г2108-21162min в строке 4Д14151820-1414min в строке 5Е247181614-7min в строке 6АБВГДЕА-191001321Б11-133120В614-01211Г086-1914Д0146-0Е1701197-Теперь − по столбцам:АБВГДЕА-191001321Б11-133120В614-01211Г086-1914Д0146-0Е1701197-004070min в столбце 1min в столбце 2min в столбце 3min в столбце 4min в столбце 5min в столбце 6АБВГДЕА-1960621Б11-9350В614-0511Г082-1214Д0106-0Е170790-Сумма констант приведения φ(Г)=2+7+6+2+14+7+4+7=49.Обозначим полученную матрицу через С1 и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на приводит к изменению лишь двух слагаемых суммы констант приведения φ(Г) – по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца. Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 6 (cА,Г=cА,Д=6), и минимума по четвёртому столбцу Г, равного 0 (cГ,В=0), без учета самого cА,Г.Итак, запишем приведённую матрицу еще раз, указывая рядом с каждым нулем его вес:АБВГДЕА-1960(6)621Б11-9350(3)В614-0(5)511Г0(2)82-1214Д0(0)10(2 )6-0(0)Е170(1)790(5)Самым тяжелым оказывается нуль в клетке (А,Г).Разобьём множество Г на две части: множество (все циклы, проходящие через дугу (А,Г)) и (все циклы, не проходящие через дугу (А,Г)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С1,1, полученная вычёркиванием соответствующих строки (строку А) и столбца (столбец Г). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ∞ ; числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n).