Содержание
Задача 1 4
Задача 2 9
Задача 3 13
Задача 4 19
Задача 1
На территории города имеется три телефонные станции А, Б, и В. Незадействованные ёмкости станций составляют на станции А-1200, Б-500, В-1100 номеров. Потребности новых районов застройки города в телефонах составляют: 1-800, 2-700, 3-400, 4-900 номеров.
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения ёмкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условия будет такое распределение ёмкости, при котором общая протяжённость абонентских линий будет минимальной.
Таблица 1.1 Среднее расстояние от станции до районов застройки, км.
Станции
РАЙОНЫ
1
2
3
4
А
4
5
6
4
Б
3
2
1
4
В
6
7
5
2
Решение:
Таблица 1.2 Исходная.
Станции
РАЙОНЫ
Возможности станций, номеров
1
2
3
4
А
4
5
6
4
1200
Б
3
2
1
4
500
В
6
7
5
2
1100
Спрос районов, номеров
800
700
400
900
2800
Решение начнем с проверки соотношения между суммарной незадействованной емкостью телефонных станций и суммарным спросом на установку телефонов.
QA+QБ+Qв=q1+q2+q3+q4=1600+800+400=800+900+400+700=2800
Задачи, в которых соблюдается равенство суммарной возможности пунктов отправления суммарному спросу пунктов назначения, называются транспортными задачами закрытого типа.
Задача заключается в нахождении такого распределения емкости, при котором общая протяженность абонентских линий была бы минимальной, т.е
Для решения задачи используем способ «наименьшего элемента», т.к этот метод позволяет получить решение более близкое к оптимальному.
Из всех расстояний от станции до районов застройки выбираем наименьшую. Такой минимальной ценой в нашем примере является элемент Б3, равный 1. С клетки Б3 следует начинать составление опорного плана. Спрос района 3 составляет 400 номеров, а станция Б может обеспечить 500 номеров. Следовательно, спрос района 3 может быть полностью удовлетворен за счет станции Б. При этом остаток свободных номеров станции Б составляет 100 ед. Вследствие того, что спрос района 3 удовлетворен полностью, столбец 3 в исходной таблице можно вычеркнуть.
Наименьшими элементами, в оставшейся части таблицы являются Б2 и В4, выберем В4 наименьший элемент равен 2. Спрос района 4 полностью удовлетворяется станцией В. При этом остаток свободных номеров станции В составляет 200 ед. Вследствие того, что спрос района 4 удовлетворен полностью, столбец 4 в исходной таблице можно вычеркнуть.
Так как элементов равных 2 было два следующей заполняем клетку Б2, спрос 2 района будет удовлетворен не полностью, так как на станции Б осталось всего 100 свободн