Контрольная работа по Экономико-математическим методам и модели в отрасли связи (стр. 1 из 5)
Министерство Российской Федерации по связи и информатизации
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов
Дисциплина
Экономико-математические методы и модели в отрасли связи
КОНТРОЛЬНАЯ РАБОТА
Выполнила: студентка
Романенко Алена Викторовна
Группа: ЭДВ-91
Проверила: Батый Ада Рамазановна
2011
Контрольная работа
Вариант 7
Задача 1
На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров (таблица 1.2).
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.
Исходные данные:
Таблица 1 - Незадействованные ёмкости телефонных станций.
| Возможности станций, номеров | |
| QА | 800 |
| QБ | 1200 |
| QВ | 1100 |
Таблица 2 - Спрос на установку телефонов
| Спрос районов, номеров | |
| q1 | 1500 |
| q2 | 400 |
| q3 | 600 |
| q4 | 800 |
Таблица 3 - Среднее расстояние от станции до районов застройки, км (для всех вариантов)
| Станции | Районы | |||
| 1 | 2 | 3 | 4 | |
| А | 4 | 5 | 6 | 4 |
| Б | 3 | 2 | 1 | 4 |
| В | 6 | 7 | 5 | 2 |
РЕШЕНИЕ:
Согласно условию задачи
вводится условная станция 
номеров (условная дополнительная станция).Задача заключается в нахождении таких неотрицательных значений. неизвестных, при которых суммарные затраты на установку телефонов и станций в районы потребления были бы минимальными, т. е.
.Задачу решаем распределительным методом. Для получения исходного плана используем метод «северо-западного» угла. При использовании этого способа установка телефонов по районам производится без учета расстояния от станций до районов. Заполнение клеток начинается с верхней левой ("северо-западной") клетки.
Если Q1>q1, то потребность первого пункта назначения полностью удовлетворяется за счет первой станции. Второй, в этом случае, заполняется клетка А-2. Если же спрос пункта 1 больше возможности пункта А, т.е. q1>Q1 , то второй заполняется клетка Б-1. Если спрос пункта 1, при этом, окажется полностью удовлетворенным, то следующей заполняется клетка справа Б-2 и т.д. Заполненные клетки плана образуют ступенчатую фигуру, начинающуюся в верхнем левом углу и заканчивающуюся в нижнем правом углу.
| Наименование поставщиков | Наименование потребителей, районы | Возможности пунктов отправления,Q | |||
| 1 | 2 | 3 | 4 | ||
| А, 1 | 800 | 800 | |||
| Б, 2 | 700 | 400 | 100 | 1200 | |
| В, 3 | 500 | 600 | 1100 | ||
| Условная станция, 4 | 200 | 200 | |||
| Спрос на установку qj | 1500 | 400 | 600 | 800 | 3300 |
Таблица – 4
Суммы чисел расположенных в клетках каждой строки, равны возможностям существующих станций, а суммы чисел каждого столбца – потребностям районов. Следовательно, составленный план является доступным.
Характеристики свободных мест определяются с помощью контуров. Контуры строятся из горизонтальных и вертикальных отрезков прямых по правилу: одна вершина контура должна находиться в свободной клетке, для которой считается характеристика, а все остальные вершины контура должны находиться в занятых местах. У вершины контура проставляются знаки: у вершины, находящейся в свободной клетке ставится всегда "+", а знаки других вершин чередуются "-", "+" и т.д.
| Наименование поставщиков | Наименование потребителей, районы | Возможности пунктов отправления,Q | |||
| 1 | 2 | 3 | 4 | ||
| А, 1 |   800 , -,4 |  5,+ | 6, | 4 | 800 |
| Б, 2 |  700, +, 3 | 400, -,2 | 100,1 | 4 | 1200 |
| В, 3 | 6 | 7 | 500,5 | 600, 2 | 1100 |
| Условная станция, 4 | 200 | 200 | |||
| Спрос на установку qj | 1500 | 400 | 600 | 800 | 3300 |
Таблица 5 – Пример построения контура для свободной клетки А2
| Наименование поставщиков | Наименование потребителей, районы | Возможности пунктов отправления,Q | |||
| 1 | 2 | 3 | 4 | ||
| А, 1 |   800 , -,4 | 5 |  6, + | 4 | 800 |
| Б, 2 |  700, +, 3 |  400, -,2 | 100,1 | 4 | 1200 |
| В, 3 | 6, |  +,7 | 500,-,5 | 600, 2 | 1100 |
| Условная станция, 4 | 200 | 200 | |||
| Спрос на установку qj | 1500 | 400 | 600 | 800 | 3300 |
Таблица 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-отрицательная характеристика
| Наименование поставщиков | Наименование потребителей, районы | Возможности пунктов отправления,Q | |||
| 1 | 2 | 3 | 4 | ||
| А, 1 | 800 , -,4 | 5 | 6, + | 4 | 800 |
| Б, 2 |   700, 3,- | 400, -,2 |  100,1,+ | 4 | 1200 |
| В, 3 |  6, + | +,7 | 500,-,5 | 600, 2 | 1100 |
| Условная станция, 4 | 200 | 200 | |||
| Спрос на установку qj | 1500 | 400 | 600 | 800 | 3300 |
Таблица 7 – План с отрицательной характеристикой.
Новый план В3=5-6+3-1=1
| Наименование поставщиков | Наименование потребителей, районы | Возможности пунктов отправления,Q | |||
| 1 | 2 | 3 | 4 | ||
| А, 1 | 800 , -,4 | 5 | 6, + | 4 | 800 |
| Б, 2 |   200, 3,-,+ | 400, -,2 |  600,1,+,- | 4 | 1200 |
| В, 3 |  6, +,500- | +,7 | 0,-,5+ | 600, 2 | 1100 |
| Условная станция, 4 | 200 | 200 | |||
| Спрос на установку qj | 1500 | 400 | 600 | 800 | 3300 |
Таблица 8 – Новый улучшенный план.