Контрольная работа по "Экономико-математическим методам и моделям в отрасли связи"

Министерство  связи  и массовых коммуникаций

Российской  Федерации

Государственное образовательное учреждение высшего 

профессионального образования

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

информатики

Межрегиональный центр переподготовки специалистов СибГУТИ

 

 

 

 

 

 

 

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

 

по дисциплине:

 

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

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

(Вариант 2)

 

 

 

 

 

 

 

 

 

 

 

       Выполнил: студент Богданов Е.А.

        Группа: ЭМ-07с

    

 

 

                            Проверил:  доц. Батый А.Р.

 

 

 

 

 

 

 

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

 

 

Задача 1

 

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

- на станции А – Q_А, номеров;

-  на станции Б – Q_Б, номеров;

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

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

- 1 - q₁ номеров;

- 2 - q₂ номеров;

- 3 - q₃ номеров;

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

 

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

 

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

Таблица 1.1 Свободные емкости телефонных станций

Возможности станций	номеров
QА	1000
QБ	1500
QВ	500

 

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

Спрос районов	номеров
q1	400
q2	800
q3	1200
q4	600

 

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

Станции	Районы
	q 1	q2	q3	q4
А	4	5	6	4
Б	3	2	1	4
В	6	7	5	2

 

 

 

 

Решение:

 

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

 

Получаем, что      , то есть модель закрытая, вводим условную станцию, возможность которой равна   .

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

 

Решим задачу распределительным методом. Построим исходный план способом  «северо-западного угла» (Таблица 1.4).

 

Таблица 1.4 -  Матрица для m-пунктов отправления (поставщиков) и n-пунктов назначения (потребителей).

Наименование  поставщиков	Наименование  потребителей				Возможности пунктов отправления
	q1	q2	q 3	q 4
QА	400	600	-	-	1000
QБ	-	200	1200	100	1500
QВ	-	-	-	500	500
Потребности пунктов назначения	400	800	1200	600	3000

 

 

Следует заметить, что при заполнении исходного  плана способом «северо-западного  угла» зачастую получается план, весьма далекий от оптимального.

 

         Функция цели задачи должна отражать искомый результат в соответствии с выбранным критерием оценки .

 

 

 

 

Наименование  поставщиков	Наименование  потребителей				Возможности пунктов отправления
	q1	q2	q 3	q 4
QА	4 400	5 600	6 -	4 -	1000
QБ	3 -	2 200	1 1200	4 100	1500
QВ	6 -	7 -	5 -	2 500	500
Потребности пунктов назначения	400	800	1200	600	3000

 

Рассчитаем  затраты:

Z = (400*4)+(600*5)+(200*2)+(1200*1)+(100*4)+(500*2)=7600

То есть при  данном исходном плане затраты составят 7600, согласно цели задачи сводим данное значение к min.

 

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

Характеристики  свободных мест определяются с помощью  контуров. Контуры строятся из горизонтальных и вертикальных отрезков прямых по правилу: одна вершина контура должна находиться в свободной клетке, для  которой считается характеристика, а все остальные вершины контура должны находиться в занятых местах. У вершины контура проставляются знаки: у вершины, находящейся в свободной клетке ставится всегда «+», а знаки других вершин чередуются «–», «+» и т.д.

Значение  характеристики свободной клетки находится как алгебраическая сумма оценок С_ij , стоящих у вершин контура. При этом оценки суммируются с учетом знаков, проставленных у вершин.

План считается  оптимальным, если характеристики всех свободных мест плана окажутся положительными.

 

Строим контур для свободных клеток Q_Бq₁,Q_Вq_1, Q_Аq₃,Q_Вq_3, ,Q_Аq₄:

 

Наименование  поставщиков	Наименование  потребителей				Возможности пунктов отправления
	q1	q2	q 3	q 4
QА	4 400	5 600	6	4	1000
QБ	3	2 200	1 1200	4 100	1500
QВ	6	7	5	2 500	500
Потребности пунктов назначения	400	800	1200	600	3000

 

 

Q_Бq₁=3-2+5-4=2

Q_Вq₁=6-2+4-2+5- 4 = 7

Q_Вq₃=7-2+4-2=7

Q_Аq₃=6-5+2-1 = 2

Q_Вq₃=5-2+4-1 = 6

Q_Аq₄=4-5+2-4 = -3

 

Так как ячейка Q_Аq₄ <0, следовательно, исходный план распределения требует улучшения.

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

 

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

 

Наименование поставщиков	Наименование  потребителей				Возможности пунктов отправления
	q1	q2	q 3	q 4
QА	4 400	-          5 600	6	+       4	1000
QБ	3	+ 2 200	1 1200	- 4 100	1500
QВ	6	7	5	2 500	500
Потребности пунктов назначения	400	800	1200	600	3000

 

В нашем случае,  среди поставок, стоящих у отрицательных  вершин контура, находится наименьшая по значению находится в клетке Q_Бq₁ со значением – 100.

Таким образом, величина, вводимая в клетку поставки Q_Аq₄ в новом плане берется равный минимум из поставок, стоящих у отрицательных вершин контура, построенного для этой клетки, то есть 100. На эту величину в новом плане увеличатся поставки, стоящие у положительных вершин и одновременно уменьшаем поставки, стоящие у отрицательных вершин данного контура на эту величину.

Все другие в данном контуре  в новый план переносим без изменений.

 

Составляем новый откорректированный план:

 

 

Наименование  поставщиков	Наименование потребителей				Возможности пунктов отправления
	q1	q2	q 3	q 4
QА	4 400	5 500	6	4 100	1000
QБ	3	2 300	1 1200	4	1500
QВ	6	7	5	2 500	500
Потребности пунктов назначения	400	800	1200	600	3000

 

Рассчитаем  затраты после улучшения плана:

Z= (400*4)+(500*5)+(300*2)+(1200*1)+(100*4)+(500*2)=7300

Так же строим контур для свободных клеток:

Q_Бq₁=3-2+5-4=2

Q_Вq₁=6-2+4-4=4

Q_Вq₂=7-2+4-5=4

Q_Аq₃=6-5+2-1=2

Q_Вq₃=5-2+4-1=6

Q_Бq₄=4-4+5-2=3

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2

 

Задание:

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

 

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

Количество линий, n – 8;

плотность потока (вызовов), l - 4;

среднее время разговора, t_обс - 1

 

Решение:

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

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

Формулы, которые служат для расчета вероятностей р, k =0,1, ...,n, в установившемся режиме, называются формулами Эрланга :

 

                                                   Ψ = λ* t_{обс               ,}                                  (1)

 

Где, Ψ –  входящая нагрузка в Эрлангах;

λ  - плотность  потока, количество вызовов в единицу  времени;

t_обс – среднее время одного разговора.

 

Ψ =  4 · 1= 4 Эрл.

Получим значение поступающей нагрузки равной 4 Эрл.

Далее найдем вероятность того, что k- линий из n будут заняты по формулам 2,3.

                                                  P_k = ,                      (2) 

                                                                      (3) 

P₀ – вероятность того, что в системе нет ни одного требования.

 

 

Данные сведем в таблицу:

                                                                                      

K (линии)	Ψk (поступающая нагрузка)	K!	Ψk/k!
1	4	1	4
2	16	2	8
3	64	6	10,667
4	256	24	10,667
5	1024	120	8,533
6	4096	720	5,689
7	16384	5040	3,251
8	65536	40320	1,625
Итого	-	-	52,432

 

 

P₀ = 1 / 52,432 = 0,019072

 

1. Вероятность отказа равна:

 

P_отк = (Ψⁿ / n!) ∙ P₀

 

Получим:  P_отк= (4⁸ / 8!) ∙ 0,019072 = 0,031

 

2. Среднее  число занятых линий равно:

                                                       _n

n_{зан ср}  =   ∑ [Ψ^k / (k-1)!]*P₀

                                                        ^k=1

Получим:  n_{зан ср} = 0,019072*(4¹ / 0!+ 4² / 1!+4³ / 2!+ 4⁴ / 3!+ 4⁵ / 4!+ 4⁶ /5!+ 4⁷ /6!+ 4⁸ /7!) = 3,9523

 

3. Среднее число свободных линий равно:

 

n_{своб ср} = n_общ. - n_{зан ср}

 

Получим:   n_{своб ср} = 8 – 3,9523 = 4,0477

 

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

К_занят = n_{зан ср} / n

    Получим:  К_занят = 3.9523/ 8 = 0.494

 

 

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

К_прост = n_{своб ср} / n

 

Получим: К_своб = 4.0477/ 8 = 0.5059

 

  Вывод: Оценивая работу данной автоматической станции (АТС), было выявлено, что вероятность отказа в предоставлении вызова равна 0.031 при коэффициенте занятости линии 0.494, то есть около 3% позвонивших получат отказ в ответе, а загрузка линий составляет всего 49,4%, таким образом, среднее число занятых и свободных линий равно. Данные показатели неплохие для работы АТС, тем не менее коэффициент простоя больше 50%, а следовательно в это время возникают неоправданные затраты на обслуживание данной АТС.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3

 

Задание:

С учетом установленного контрольного срока рассчитать:

- количество маршрутов;

- распределить пункты обслуживания между маршрутами;

- определить последовательность обхода пунктов обслуживания.

 

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

В таблице 3.1 приводится матрица суммарных затрат времени на проход между i и j пунктами и обслуживание j-пункта.

Значение контрольного срока К_s = 75 мин.

 

        Таблица 3.1 – Матрица затрат времени, минут

 

	А	Б	В	Г	Д	Е	Ж	З	И	К	Л	М	Н
А	-	32	24	36	20	18	20	21	34	24	34	22	26
Б	27	-	25	35	24	19	25	22	24	34	30	25	18
В	19	28	-	15	21	25	23	27	15	17	31	13	35
Г	31	38	15	-	23	19	25	27	29	19	23	21	17
Д	16	24	20	25	-	29	30	15	23	18	20	16	17
Е	13	19	25	17	29	-	14	18	21	23	27	23	18
Ж	15	23	24	25	31	18	-	15	15	25	19	15	21
З	16	19	27	27	15	19	15	-	31	33	37	30	13
И	28	27	15	29	23	21	18	31	-	25	15	19	21
К	18	33	17	17	19	23	25	33	25	-	17	17	25
Л	29	30	30	23	21	27	19	35	15	17	-	15	23
М	17	24	10	21	17	23	15	34	19	15	15	-	19
Н	21	18	35	15	17	19	20	13	21	25	20	19	-

 

 

Решение:

Для решения  данной задачи используем алгоритм «задачи  развозки». Ценность этого метода заключается  в том, что он позволяет определить необходимое количество маршрутов, их тип (радиальный или кольцевой), распределить пункты между маршрутами, построить маршруты с учетом заданного контрольного времени на обслуживание маршрутов.

Решение задачи начнем с  преобразования матрицы исходных данных. Заголовок в преобразованную  матрицу переписывается без изменения, а элементы основной части преобразованной  матрицы (С_ij) рассчитываются по формуле (3.1): 

                                                                                      (3.1)

 

По результатам  расчетов получаем преобразованную  матрицу (таблица 3.2.).

 

          Таблица 3.2 – Преобразованная матрица

 

i\j	1	2	3	4	5	6	7	8	9	10	11	12	13
1	-	32	24	36	20	18	20	21	34	24	34	22	26
2	27	-	26	28	23	26	22	26	37	17	31	24	35
3	19	23	-	40	18	12	16	13	38	26	22	28	10
4	31	25	40	-	28	30	26	25	36	36	42	32	40
5	16	24	20	27	-	5	6	22	27	22	30	22	25
6	13	26	12	32	4	-	19	16	26	14	20	12	21
7	15	24	15	26	4	15	-	21	34	14	30	22	20
8	16	29	13	25	21	15	21	-	19	7	13	8	29
9	28	33	37	35	25	25	30	18	-	27	47	31	33
10	18	17	25	37	19	13	13	6	27	-	35	23	19
11	29	31	23	42	28	20	30	15	48	36	-	36	32
12	17	25	31	32	20	12	22	4	32	26	36	-	24
13	21	35	10	42	24	20	21	29	34	20	35	24	-

 

 

Далее в  основной части преобразованной матрицы выбираем максимальный элемент .

Поскольку общие  затраты времени на обслуживание маршрута не должны превышать установленного контрольного срока (K_s=75 мин.), то все получаемые варианты маршрутов проверяются на соответствие контрольному сроку.

Если  , то включение в маршрут прохода (или проезда) считается допустимым. В этом случае строка k и столбец l в преобразованной матрице вычеркиваются, и одновременно вычеркивается элемент обратной связи этих пунктов C_lk, так как движение из пункта k в пункт l в кольцевом маршруте исключает движение из пункта l в пункт k.

Далее, снова  из числа невычеркнутых выбирается максимальный элемент и т.д.  Если включение прохода (или проезда) между пунктами k и l приводит к образованию маршрута, время обхода по которому больше заданного контрольного срока, вариант маршрута 1-k-l-1 считается недопустимым, а поэтому элемент, соответствующий этой связи в преобразованной матрице зачеркивается. После этого среди невычеркнутых элементов преобразованной матрицы снова ищется максимальный.

Расчеты продолжаются до тех пор, пока все элементы матрицы не будут вычеркнуты.

Элемент 1:

Т_обсл= 34+15+28 = 77мин

Сравним полученный результат с контрольным временем – 75 мин. Очевидно, что полученный результат  превышает контрольное время, следовательно, маршрут недопустим. В таком случае, вычеркиваем элемент, который привел к недопустимости маршрута .

Найдем следующие  максимальные элементы по порядку:

 

Элемент 2:

Т_обсл= 34+15+29 = 78мин

Маршрут недопустим, вычеркиваем элемент

 

Элемент 3:

Т_обсл= 26+15+31 = 72 мин <К_s

Маршрут допустим, в преобразованной матрице вычеркивается строка 13, столбец 4 и элемент обратной связи

 

Элемент 4:

Т_обсл = 26+31+15 = 72мин< К_s

Маршрут допустим, в преобразованной матрице вычеркивается строка 11, столбец 4 и элемент обратной связи

 

Расчеты продолжаем до тех пор, пока все элементы матрицы  не будут вычеркнуты. После проверки всех маршрутов, оптимальные для внедрения (допустимые) только те, время обслуживания которых не превышает контрольное время в 75 мин, то есть:

 

1. АН-НГ-ГА;

2. АМ-МЛ-ЛК-КА;

3. АВ-ВИ-ИМ-МА;

4. АЗ-ЗБ-БЕ-ЕА;

5. АД-ДЖ-ЖА.