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

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

Информатики

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

Дисциплина

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

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

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

Вариант № 9

Выполнил: слушатель гр. ФКТ-23

Проверил: преподаватель Батый Ада Рамазановна

2012

ЗАДАЧА № 1

На территории города имеется три телефонных станции: А, Б и В. Незадействованные емкости станций составляют:

на станции А - Q_А=1600 номеров,

на станции Б - Q_Б=800 номеров,

на станции В - Q_В=400 номеров.

Потребности новых районов застройки города в телефонах составляют:

1 - q₁=800 номеров,

2 - q₂=900 номеров,

3 - q₃=400 номеров,

4 - q₄ = 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

Решение:

Решение начнем с проверки соотношения между суммарной незадействованной емкостью телефонных станций и суммарным спросом на установку телефонов.

Q_A+Q_Б+Qв= q₁+q2+q₃+q₄ =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_В , а значение клеток, образующих дополнительную строку – 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			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

Найденные значения клеток позволяют провести исследование свободных мест. Его целью является выявление отрицательных свободных мест. Если U_i + V_j меньше соответствующего значения расстояния (в клетке на пересечении 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.

Неравенства показывают, что характеристики всех свободных мест положительные, значит план оптимальный.