ЗАДАЧА № 1
Сибирский Государственный Университет Телекоммуникаций и
Информатики
На территории города имеется три телефонных станции: А, Б и В. Незадействованные емкости станций составляют: на станции А - QА=1600 номеров, на станции Б - QБ=800 номеров, на станции В - QВ=400 номеров. Потребности новых районов застройки города в телефонах составляют: 1 - q1=800 номеров, 2 - q2=900 номеров, 3 - q3=400 номеров, 4 - q4 = 700 номеров. Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.
Исходные данные:
Таблица 1.1, Незадействованные ёмкости телефонных станций.
Таблица 1.2, Спрос на установку телефонов.
Таблица 1.3, Среднее расстояние от станции до районов застройки, км.
Решение:
Решение начнем с проверки соотношения между суммарной незадействованной емкостью телефонных станций и суммарным спросом на установку телефонов. QA+QБ+Qв= q1+q2+q3+q4 =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 которые можно заполнить единственным образом, за счет станции А в соответствии со спросом. Полученное методом наименьшего элемента решение задачи показано в таблице 3 протяженность линий согласно этому решению составит: 800 * 4 + 500 * 5 + 300 * 4 + 400 * 2 + 400 * 1 + 400 * 2 = 8100 км.
Составим таблицу модифицированного распределительного метода, принимая в качестве исходного решение по методу наименьшего элемента. Основное отличие модифицированного распределительного метода заключается в порядке исследования свободных мест таблицы с помощью дополнительных строки и столбца.
Первый этап расчетов заключается в определении значений клеток, образующих дополнительную строку и дополнительный столбец. Во всех случаях верхняя клетка дополнительного столбца (строка А) получает значение 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.
Получены значения всех клеток, образующих дополнительные строку и столбец. Эти значения записываются на соответствующие места в таблице:
Найденные значения клеток позволяют провести исследование свободных мест. Его целью является выявление отрицательных свободных мест. Если Ui + Vj меньше соответствующего значения расстояния (в клетке на пересечении i-й строки и j-го столбца), взятого с обратным знаком, то свободное место (i, j) отрицательно и решение может быть улучшено.
Для свободных мест: В3 2 – 4 > -5.
Неравенства показывают, что характеристики всех свободных мест положительные, значит план оптимальный.
|
