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

 

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

Информатики 

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

Дисциплина   

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

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

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

Вариант № 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