Министерство Российской Федерации по связи и информатизации
Сибирский Государственный Университет Телекоммуникаций и
Информатики
Межрегиональный центр переподготовки специалистов
Дисциплина
«Экономико-математические методы и модели
в отрасли связи»
Контрольная работа
Вариант № 9
Выполнил:
слушатель гр. ФКТ-23 Проверил:
преподаватель Батый Ада Рамазановна
2012
ЗАДАЧА № 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 |
Решение:
Решение начнем с проверки соотношения между суммарной незадействованной емкостью телефонных станций и суммарным спросом на установку телефонов.
QA+QБ+Qв= q1+q2+q3+q4 =1600+800+400=800+900+400+700=2800
Задачи, в которых соблюдается равенство суммарной возможности пунктов отправления суммарному спросу пунктов назначения, называются транспортными задачами закрытого типа.
Задача заключается в нахождении такого распределения емкости, при котором общая протяженность абонентских линий была бы минимальной, т.е
Для решения задачи используем способ «наименьшего элемента», т.к этот метод позволяет получить решение более близкое к оптимальному.
Станции |
РАЙОНЫ |
Возможности станций, номеров | ||||
1 |
2 |
3 |
4 |
| ||
А |
4 |
5 |
6 |
4 |
1600 | |
Б |
3 |
2 |
1 |
4 |
800 | |
В |
6 |
7 |
5 |
2 |
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 которые можно заполнить единственным образом, за счет станции А в соответствии со спросом.
Полученное методом наименьшего элемента решение задачи показано в таблице 3 протяженность линий согласно этому решению составит:
800 * 4 + 500 * 5 + 300 * 4 + 400 * 2 + 400 * 1 + 400 * 2 = 8100 км.
Станции |
РАЙОНЫ |
Возможности станций, номеров | |||||||||||
1 |
2 |
3 |
4 | ||||||||||
А |
|
4 |
|
5 |
|
6 |
|
4 |
1600 | ||||
800 |
|
500 |
|
|
|
300 |
| ||||||
Б |
|
3 |
|
2 |
|
1 |
|
4 |
800 | ||||
|
|
400 |
|
400 |
|
|
| ||||||
В |
|
6 |
|
7 |
|
5 |
|
2 |
400 | ||||
|
|
|
|
|
|
400 |
| ||||||
Спрос районов, номеров |
800 |
900 |
400 |
700 |
2800 |
Составим таблицу модифицированного распределительного метода, принимая в качестве исходного решение по методу наименьшего элемента.
Основное отличие модифицированного распределительного метода заключается в порядке исследования свободных мест таблицы с помощью дополнительных строки и столбца.
Станции |
Дополнительный столбец |
РАЙОНЫ |
Возможности станций, номеров | |||||||||||||
1 |
2 |
3 |
4 |
| ||||||||||||
Дополнительная строка | ||||||||||||||||
V1 |
V2 |
V3 |
V4 |
| ||||||||||||
А |
UА |
|
4 |
|
5 |
|
6 |
|
4 |
1600 | ||||||
800 |
|
500 |
|
|
|
300 |
| |||||||||
Б |
UБ |
|
3 |
|
2 |
|
1 |
|
4 |
800 | ||||||
|
|
400 |
|
400 |
|
|
| |||||||||
В |
UВ |
|
6 |
|
7 |
|
5 |
|
2 |
400 | ||||||
|
|
|
|
|
|
400 |
| |||||||||
Спрос районов, номеров |
800 |
900 |
400 |
700 |
2800 |
Первый этап расчетов заключается в определении значений клеток, образующих дополнительную строку и дополнительный столбец. Во всех случаях верхняя клетка дополнительного столбца (строка А) получает значение 0. Этот 0 будет фигурировать в процессе всего решения.
Рассчитаем значения других дополнительных клеток. Если значения клеток, образующих дополнительный столбец, обозначить через UА , UБ , UВ , а значение клеток, образующих дополнительную строку – V1 , V2 , V3 и V4 , то исходным положением для расчета их значений будет равенство Ui + Vj = - Сij , где Сij – среднее расстояние от станции до районов застройки и клетка на пересечении рассматриваемых строки и столбца. При этом определяются значения клеток тех столбцов и строк, пересечения которых образуют занятые места.
Начнем с первой клетки дополнительного столбца, значение которой принято равным 0. Для столбца, соответствующего району 1, имеем 0+V1 = -4; отсюда V1 = -4.
Для столбца 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.
Получены значения всех клеток, образующих дополнительные строку и столбец. Эти значения записываются на соответствующие места в таблице:
Станции |
Дополнительный столбец |
РАЙОНЫ |
Возможности станций, номеров | |||||||||||
1 |
2 |
3 |
4 | |||||||||||
Дополнительная строка | ||||||||||||||
-4 |
-5 |
-4 |
-4 | |||||||||||
А |
0 |
|
4 |
|
5 |
|
6 |
|
4 |
1600 | ||||
800 |
|
500 |
|
|
|
300 |
| |||||||
Б |
3 |
|
3 |
|
2 |
|
1 |
|
4 |
800 | ||||
|
|
400 |
|
400 |
|
|
| |||||||
В |
2 |
|
6 |
|
7 |
|
5 |
|
2 |
400 | ||||
|
|
|
|
|
|
400 |
| |||||||
Спрос районов, номеров |
800 |
900 |
400 |
700 |
2800 |
Найденные значения клеток позволяют провести исследование свободных мест. Его целью является выявление отрицательных свободных мест. Если 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.
Неравенства показывают, что характеристики всех свободных мест положительные, значит план оптимальный.