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

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

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

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

Дисциплина

Экономико-математические методы и модели в отрасли связи

КОНТРОЛЬНАЯ РАБОТА

Выполнила : студентка

Романенко Алена Викторовна

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

Проверила: Батый Ада Рамазановна

2011

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

Вариант 7

Задача 1

На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров (таблица 1.2).

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

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

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

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

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

РЕШЕНИЕ:

Согласно условию задачи вводится условная станция номеров (условная дополнительная станция).

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

Задачу решаем распределительным методом. Для получения исходного плана используем метод «северо-западного» угла. При использовании этого способа установка телефонов по районам производится без учета расстояния от станций до районов. Заполнение клеток начинается с верхней левой ("северо-западной") клетки.

Если Q₁ >q₁ , то потребность первого пункта назначения полностью удовлетворяется за счет первой станции. Второй, в этом случае, заполняется клетка А-2. Если же спрос пункта 1 больше возможности пункта А, т.е. q₁ >Q₁ , то второй заполняется клетка Б-1. Если спрос пункта 1, при этом, окажется полностью удовлетворенным, то следующей заполняется клетка справа Б-2 и т.д. Заполненные клетки плана образуют ступенчатую фигуру, начинающуюся в верхнем левом углу и заканчивающуюся в нижнем правом углу.

Таблица – 4

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

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

Таблица 5 – Пример построения контура для свободной клетки А2

Таблица 6 - Пример построения контура для свободной клетки А3

Значение характеристики свободной клетки находиться как алгебраическая сумма

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

А2=5-2+3-4=2

А3=6-5+7-2+3-4=5

А4=4-2+5-1+3-4=5

Б4=4-2+5-1=6

В1=6-3+1-5= -1

В2=7-2+1-5=1

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

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

Улучшение обеспечивается за счет перераспределения поставок (емкости), стоящих у вершин контура, по которому была найдена сама характеристика свободной клетки. Пересчет поставок ведется следующим образом: среди поставок, стоящих у отрицательных вершин контура, находится наименьшая по значению и на эту величину в новом плане увеличиваются поставки, стоящие у вершин со знаком "+" и одновременно уменьшаются поставки у вершин со знаком "-".

В1=6-3+1-5= -1-отрицательная характеристика

Таблица 7 – План с отрицательной характеристикой.

Новый план В3=5-6+3-1=1

Таблица 8 – Новый улучшенный план.

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

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

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

А2=5-2+3-4=2

А3=6-1+3-4=4

А4=4-2+6-4=4

Б4=4-2+6-3=5

В3=5-6+3-1=1

В2=7-6+3-2=2

Таблица 9 – Контур для характеристики В2.

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

Значение общей протяженности абонентских линий на реализацию плана определяется как сумма произведений количества линий на расстояние от станции до района:

800*4+200*3+500*6+400*2+600*1+(600+200)*2=9800 км.

Распределение станций между районами

ЗАДАЧА 2.

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

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

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

РЕШЕНИЕ

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

λ – средняя плотность потока,

- среднее время разговора

При общей нагрузки λ=2 нагрузка, выраженная в Эрлангах, составит:

Ψ = 2*1 =2

Далее находим вероятность того, что все линии на станции свободны, по формуле:

Т.е. время, когда телефонная станция вообще не занята, составляет в процентах от общего рабочего времени:

Находим вероятность отказа, или вероятность одновременной занятости всех семи линий, по формуле:

Отсюда, из 100 вызовов поступающих в систему, 99 будут обслужены, а 1 – нет.

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

= 1

Тогда среднее число свободных линий составит:

6 – 1 = 5

В этих условиях коэффициент занятости линий составит:

1/6= 0,166

Каждая линия занята 16% своего рабочего времени.

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

1 – 0,16 = 0,83

Каждая линия будет свободна 83% своего рабочего времени.

Ответ:

· Вероятность отказа 0,01

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

· Среднее число свободных линий 5

· Коэффициент занятости 0,16

· Коэффициент простоя 0,83

Из полученных значений видно, что качество обслуживания абонентов АТС находится на достаточном уровне.

ЗАДАЧА 3.

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

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

Таблица 10 –Исходные данные.

РЕШЕНИЕ

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

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

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

Для приведения исходной матрицы сначала в каждой строке находим наименьший элемент, в таблице он выделен:

Далее вычитаем наименьший элемент строки из элементов своей строки, получаем:

Затем в приведенной по строкам матрице в каждом столбце находим наименьший элемент:

Наконец вычитаем наименьший элемент в столбце из элементов своего столбца - получается приведенная матрица:

Таблица 11 – Приведенная матрица.

Параллельно с расчетами в матрицах рисуется "дерево маршрута". Исходной вершиной дерева является вершина "все циклы", определяющая все множество возможных вариантов построения кольцевого маршрута по объезду (обходу) заданных пунктов. Для вершин дерева считаются "нижние границы". Нижняя граница вершины "все циклы" равна сумме наименьших элементов строк и столбцов, в результате вычитания которых получена приведенная матрица. Сумма констант приведения равна:

5+10+7+6+6+6+4+3=47

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

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

Например, характеристика для нуля в строке А и столбце В складывается из минимума по строке А, равного 0 (Р_А,Г =0), и минимума по столбцу В, равного 0 (Р_Б,В =1), без учета самого Р_АВ

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

Ноль с наибольшим значением характеристики находится в ячейке Е-Д, он указывает на связь между пунктами, которую следует оценить - включать ее в маршрут (Р_Е Р_Д ) или от нее следует отказаться .

От исходной вершины рисуется две ветви: одна к вершине Р_Е Р_Д , другая к вершине . Чтобы оценить, что выгоднее, нужно для обеих вершин рассчитать "нижние границы". "Нижняя граница" с обязательным исключением связи считается как сумма "нижней границы" исходной вершины, откуда выходит ветвь, идущая к вершине , и характеристики нуля, указавшего на эту связь.

Чтобы рассчитать "нижнюю границу" вершины с обязательным включением связи Р_Е Р_Д нужно прежде вычеркнуть Е строку и Д столбец и одновременно элемент, соответствующий обратной связи этих пунктов Р_Е Р_Д .

Теперь проанализируем оставшуюся матрицу. Это матрица приведенная, т.к. в каждой строке и каждом столбце ее содержит не менее одного нуля. Тогда сумму констант приведения для этой таблицы равна 0.

Сумма констант приведения и нижней границы вершины "все циклы" определяет значение "нижней границы" вершины Р_Е Р_Д .

Та вершина, которой соответствует наименьшая по величине "нижняя граница", определяет включить связь в маршрут или нет. Наименьшее значение нижней границы будет соответствовать вершине с обязательным включением в маршрут связи Р_Е Р_Д , поэтому ветвление дерева продолжается от вершины Р_Е Р_Д .

Очередная связь определяется аналогично - путем расчета характеристик для нулей последней матрицы. Итак, запишем приведенную матрицу, указывая рядом с каждым нулем его характеристики:

Ноль с наибольшим значением характеристики находится в ячейке строки Д и столбца Е. Продолжаем рисовать «дерево маршрута»:

Все пункты включены в кольцевой маршрут. Следовательно, мы получили маршрут следующего вида:

Е Д

В Б

А Г

Затраты времени по маршруту: 6+14+7+5+10+13+16=71 мин.

ЗАДАЧА 4 .

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

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

Используя имеющиеся запасы времени по некритическим работам, скорректируйте сетевой график с учётом ограничения по количеству рабочих.

Рисунок 1

РЕШЕНИЕ:

Для оптимизации, прежде всего, необходимо рассчитать основные параметры сетевого графика: возможные ранние сроки начала (t_ij ^PH ) и раннего окончания (t_ij ^PI ), допустимые поздние сроки начала (t_ij ^IH ) и позднего окончания (t_ij ^Io ) , частный (÷ij) и полный резерв времени (R_ij ) для выполнения каждой i,j - работы. Расчет параметров выполнить в таблице.

Перед началом расчета на основании сетевого графика (рис.1) заполняются колонки 1 и 2 таблицы.

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

Таблица 12- График выполнения работ.

Для каждой работы в сетевом графике ранние сроки начала и окончания определяются переходом от более ранних событий к более поздним. Расчет ранних сроков начала и окончания работ (колонки 3 и 4) ведется от исходного события к завершающему (сверху вниз).

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

t^ро _ij = 0 + t_ij

Определяем эти параметры для исходных работ 1-2, 1-3 и 1-4, раннее начало которых равно нулю, а ранее окончание соответственно:

t^ро _1-2 = 0+2=2

t^ро _1-3 = 0+5=5

t^ро _1-4 = 0+6=6

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

t^ро _ij = t^рн _ij + t_ij Например : t^ро _2-5 = t^рн _2-5 + t_2-5 = 2+4 = 6

Если данной работе предшествует только одна работа, то раннее начало данной работы равно раннему окончанию предшествующей работы.

t^рн _ij = t^ро _hi Например : t^рн _3-6 = t^ро _1-3 = 5

Если данной работе предшествуют несколько работ, то ее раннее начало равно максимальному значению из всех ранних окончаний предшествующих работ t^рн _ij = max { t^ро _hi }.

Например: t^рн _5-7 = max{t^ро _2-5 , t^ро _3-5 }= max{6, 12} = 12

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

Продолжительность критического пути: t_кр = t^ро _5-7 = 18 дней.

Затем последовательно определяем поздние параметры всех остальных работ (колонки 5 и 6). Поздние сроки начала и окончания работ определяем от завершающего события к исходному, то есть снизу вверх.

Позднее начало работы определяется как разность ее позднего окончания и продолжительности самой работы.

t^пн _ij = t^по _ij - t_ij Например : t^пн _5-7 = t^по _5-7 -t_5-7 = 18-6=12

Если у данной работы последующих работ одна, ее позднее окончание равно позднему началу последующей работы

t^по _ij = t^пн _jk . Например : t^по _4-6 = t^пн _6-7 =16

Если за данной работой следует не одна, а несколько работ, то ее позднее окончание будет равно минимальному значению из всех поздних начал последующих работ.

t^по _ij = min{t^пн _jk }

Например, t^по _1-3 = min{t^пн _3-5 , t^пн _3-6 } = min{5,13}= 5

После расчета ранних и поздних временных параметров работ определяем полный и частный резервы времени (колонки 7 и 8).

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

Полный резерв равен разности позднего и раннего начала или позднего и раннего окончания всех работы.

R_ij = t^пн _ij - t^рн _ij = t^по _ij - t^ро _ij .

Например : R_4-6 = t^по _4-6 - t^ро _4-6 = 16 – 8 = 8

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

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

r_ij = t^рн _jk - t^ро _ij Например : r_2-5 = t^рн _5-7 - t^ро _2-5 = 12 - 6= 6.

Затем находим работы, образующие критический путь , у них резервы времени равны нулю. В нашем примере это работы 1-3, 3-5 и 5-7.

Известно, что в распоряжении организации имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой. Учитывая это ограничение, определить сроки выполнения работ. На основании данных о продолжительностях работ, возможных сроков их раннего начала и окончания строим линейный календарный план выполнения работ по ранним началам некритических работ (таблица 13) указав, сколько исполнителей ежедневно занято на выполнении каждой конкретной работы. Суммируя количество рабочих на каждый день по всем работам и построив по этим данным график движения рабочих, видно, что в какие-то дни суммарное число работников оказалось больше заданного ограничения. Следовательно, сетевой график с точки зрения использования рабочих составлен неудовлетворительно и должен быть скорректирован с учетом имеющихся ограничений по количеству рабочих. Корректировка возможна за счет использования имеющихся у работ резервов времени - частного и полного. Продолжительность работ увеличиваем в пределах имеющихся резервов с одновременным уменьшением ежедневной потребности в исполнителях.

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

Работу 1-2 продолжительностью два дня оставляем без изменения.

Работу 1-3 (критическую) оставляем без изменения, так как резерв времени у этой работы равен нулю.

Начало работы 1-4 сдвигаем на два дня, при этом сокращая количество рабочих с 11 до 8 и увеличивая продолжительность работы с 6 до 7 дней.

Работу 2-5, имеющую трудоемкость 11 человеко-дня и запас времени 6 дней можно передвинуть на 7 дней вправо и сократить ее выполнение до трех дней, при этом количество рабочих увеличится с 11 до 14.

Работа 3-5 является критической и поэтому остается без изменения.

Работа 3-6 имеет продолжительность 3 дня. Растягиваем эту работу до 6 дней, уменьшая при этом количество рабочих с 11 до 6, но при этом делаем перерыв между четвертым и пятым днем продолжительностью 3 дня.

Начало работы 4-6 передвигаем на 6 дней, не изменяя сроки и количество рабочих, два дня и 3 человека соответственно.

Работа 5-7 – критическая, поэтому остается без изменения.

Работа 6-7 следует за работами 3-6 и 4-6, поэтому ее начало сдвигается на 6 дней, при этом увеличиваем ее продолжительность до 4 дней, а количество рабочих сокращаем до 10 человек.

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

После корректировки сетевого графика видно, что каждый день на всех работах будет занято 28 человек, в 13 и 14 день возможно сократить количество рабочих до 27 человек.

Таблица 13- Линейный календарный план выполнения работ.