Размещено на http://www.allbest.ru/

Федеральное агентство связи

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

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

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

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

Выполнил: Шмидт И.А.

Группа: ФКТ - 21

Новосибирск 2012

Задача 1

На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров.

Таблица 1.1

Станций
Qa	3000
Qб	4000
Qв	2000

q1=1200, q2=2700; q3=3100; q4=2000.

Таблица 1.2

Станции	Районы
А	4
Б	3
В	6

Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.

Решение

Данная задача относится к типу транспортных задач линейного программирования. В качестве поставщиков выступают автоматические телефонные станции, а в качестве потребителей - абоненты микрорайонов города.

Суммарные незадействованные емкости станций:

Суммарный спрос потребителей:

Так как , задача закрытая.

Составим закрытую транспортную задачу в табличной форме

Наименование поставщиков	Наименование потребителей	Возможности пунктов отправления
	1	2	3	4
1	4 С11	5 С12	6 С13	4 C14	3000
2	3 С21	2 С22	1 С23	4 C24	4000
3	6 С31	7 С32	5 С33	2 C34	2000
Потребности пунктов назначения	1200	2700	3100	2000	9000

По правилу наименьшего элемента в столбце распределяем:

Наименование поставщиков	Наименование потребителей	Возможности пунктов отправления
	1	2	3	4
1	4 1200	5 1800	6	4	3000
2	3	2 900	1 3100	4	4000
3	6	7	5	2 2000	2000
Потребности пунктов назначения	1200	2700	3100	2000	9000

Используя метод потенциалов, найдем потенциалы поставщиков и потребителей.

Пусть u1 = 10,

V1 = U1 + C11 = 10 + 4 = 14;

V2 = U1 + C12 = 10 + 5 = 15;

U2 = V2 - C22 = 15 - 2 = 13;

V3 = U2 + C23 = 13 + 1 = 14;

V4 = U2 + C24 = 13 + 0 = 13;

U3 = V4 - c34 = 13 - 2 = 11.

Наименование поставщиков	Наименование потребителей	Возможности пунктов отправления	Ui
	1	2	3	4
1	4 1200	5 1800	6	4	3000	10
2	3	2 900	1 3100	4 0	4000	13
3	6	7	5	2 2000	2000	11
Потребности пунктов назначения	1200	2700	3100	2000	9000
Vj	14	15	14	13

Вычислим величины ?ij для свободных клеток:

?13 = V3 - C13 - U1 = 14 - 6 - 10 = -2;

?14 = V4 - C14 - U1 = 13 - 4 - 10 = -1;

?21 = V1 - C21 - U2 = 14 - 3 - 13 = -2;

?31 = V1 - C31 - U3 = 14 - 6 - 11 = -3;

?32 = V2 - C32 - U3 = 15 - 7 - 11 = -3;

?33 = V3 - C33 - U3 = 14 - 5 - 11 = -2.

Все ?ij < 0. Получен оптимальный план.

При этом:

S* = 1200*4 + 1800*5 + 900*2 + 3100*1 + 2000*2 = 22700.

Ответ: S* = 22700.

Задача 2

Необходимо оценить работу автоматической телефонной станции (АТС), которая имеет n линий связи. Моменты поступления вызовов на станцию являются случайными и независимыми друг от друга. Средняя плотность потока равна л вызовов в единицу времени. Продолжительность каждого разговора является величиной случайной и подчинена показательному закону распределения. Среднее время одного разговора равно tобс единиц времени.

Таблица 2.1 Исходные данные

Варианты	1
Количество линий, n	7
Плотность потока, л	3
Среднее время разговора, tобс	2

Автоматические телефонные станции относятся к типу систем обслуживания с потерями (с отказами). Абонент получает отказ в случае, если все линии заняты.

Для определения основных показателей работы АТС необходимо рассчитать значение поступающей нагрузки в Эрлангах Ш и вероятности, что из n-линий k будет занято.

Для расчета используются формулы

Далее следует определить вероятность отказа Ротказа , среднее число занятых и среднее число свободных линий, коэффициенты занятости и простоя линий и сделать вывод о качестве обслуживания абонентов и эффективности использования линий связи.

Решение

Значение поступающей нагрузки:

ш = лТзагр = 3*2 = 6 Эрланг.

Р0 = = 0,00333.

Вычислим вероятности состояний:

Р1 =

Р2 = 0,06

Р3 = 0,12

Р4 = 0,18

Р5 = = 0,216

Р6 = 0,216

Р7 = 0,185

Ротк = Р7 = 0,185.

Значит, 18,5% из числа поступивших заявок не принимаются к обслуживанию.

Вероятность обслуживания поступающих заявок.

В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:

pотк + pобс = 1

Относительная пропускная способность:

Q = pобс.

pобс = 1 - pотк = 1 - 0,185 = 0,815.

Следовательно, 81,5% из числа поступивших заявок будут обслужены. При этом приемлемый уровень обслуживания должен быть выше 90%.

Среднее число занятых линий связи

nз = ш * pобс = 6*0,815 = 4,89 линии.

Среднее число простаивающих каналов.

nпр = n - nз = 7 - 4,89 = 2,11 каналов.

Коэффициент занятости каналов обслуживанием.

K3 = n3/n = 4,89 / 7 = 0,7

Следовательно, система на 70% занята обслуживанием.

Коэффициент простоя линий

Таким образом, уровень обслуживания ниже приемлемого.

Задача 3

В таблице 3.1 приведены затраты времени почтальона (в минутах) на проход между пунктами доставки на участке. Используя метод "ветвей и границ", найти маршрут почтальона, при котором затраты времени на его проход будут минимальными.

Таблица 3.1 Исходные данные

Вариант	А	Б	В	Г	Д	Е
A	-	7	5	15	10	6
Б	8	-	7	20	6	12
В	4	6	-	19	10	4
Г	16	20	20	-	8	14
Д	10	8	9	7	-	12
Е	7	12	4	15	10	-

экономический математический метод анализ

Решение

Задачу решаем методом теории графов, известным как метод "ветвей и границ". Матрица считается приведенной, если в каждой строке и каждом столбце содержит не менее одного нуля. Для приведения исходной матрицы сначала в каждой строке находится наименьший элемент и вычитается из элементов своей строки, затем в приведенной по строкам матрице в каждом столбце находится наименьший элемент и вычитается из элементов своего столбца - получается приведенная матрица. Обозначим за Г множество всех обходов почтальона (т. е. всех простых ориентированных остовных циклов).

Поскольку граф - полный, это множество заведомо не пусто.

Сопоставим ему число ц(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов дуг графа и является оценкой снизу для стоимости минимального тура коммивояжёра. Приведённую матрицу весов данного графа следует запомнить, обозначим ее через С1.

Подсчитаем ц(Г). Для этого выполним приведение матрицы весов.

Сначала - по строкам:

	А	Б	В	Г	Д	Е
А	-	7	5	15	10	6	5	min в строке 1
Б	8	-	7	20	6	12	6	min в строке 2
В	4	6	-	19	10	4	4	min в строке 3
Г	16	20	20	-	8	14	8	min в строке 4
Д	10	8	9	7	-	12	7	min в строке 5
Е	7	12	4	15	10	-	4	min в строке 6

	А	Б	В	Г	Д	Е
А	-	2	0	10	5	1
Б	2	-	1	14	0	6
В	0	2	-	15	6	0
Г	8	12	12	-	0	6
Д	3	1	2	0	-	5
Е	3	8	0	11	6	-

Далее ? по столбцам:

	А	Б	В	Г	Д	Е
А	-	2	0	10	5	1
Б	2	-	1	14	0	6
В	0	2	-	15	6	0
Г	8	12	12	-	0	6
Д	3	1	2	0	-	5
Е	3	8	0	11	6	-
	0	1	0	0	0	0
	min в столбце 1	min в столбце 2	min в столбце 3	min в столбце 4	min в столбце 5	min в столбце 6

	А	Б	В	Г	Д	Е
А	-	1	0	10	5	1
Б	2	-	1	14	0	6
В	0	1	-	15	6	0
Г	8	11	12	-	0	6
Д	3	0	2	0	-	5
Е	3	7	0	11	6	-

Сумма констант приведения

ц(Г) = 5 + 6 + 4 + 8 + 7 + 4 + 1= 35.

Обозначим полученную матрицу через С1 и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на приводит к изменению лишь двух слагаемых суммы констант приведения ц(Г) - по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца.

Например, вес нуля в первой строке и третьем столбце складывается из минимума по первой строке, равного 1 (cА,Б = cА,Е = 1), и минимума по третьему столбцу В, равного 0 (cВ,Е = 0), без учета самого cА,В.

Итак, запишем приведённую матрицу еще раз, указывая рядом с каждым нулем его вес:

	А	Б	В	Г	Д	Е
А	-	1	0 (1)	10	5	1
Б	2	-	1	14	0 (1)	6
В	0 (2)	1	-	15	6	0 (1)
Г	8	11	12	-	0 (6)	6
Д	3	0 (1)	2	0 (10)	-	5
Е	3	7	0 (3)	11	6	-

Самым тяжелым оказывается нуль в клетке (Д,Г).

Разобьём множество Г на две части: множество (все циклы, проходящие через дугу (Д,Г)) и (все циклы, не проходящие через дугу (Д,Г)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С1,1, полученная вычёркиванием соответствующих строки (строку Д) и столбца (столбец Г). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ? ; числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). В данном случае из пункта Г мы уже не можем проехать в пункт Д, поэтому в клетке (Г,Д) ставим знак ?.

Матрица С1,1

	А	Б	В	Д	Е
А	?	1	0	5	1
Б	2	?	1	0	6
В	0	1	?	6	0
Г	8	11	12	?	6
Е	3	7	0	6	?

Матрица С1,1 после приведения

	А	Б	В	Д	Е
А	?	0	0	5	1
Б	2	?	1	0	6
В	0	0	?	6	0
Г	2	4	6	?	0
Е	3	6	0	6	?

Сумма констант приведения матрицы С1,1 здесь равна 7, поэтому

ц(Г{(Д,Г)}) = ц{Д,Г} = 35 + 7 = 42.

Сопоставим результат ц(Г{(i,j)}) множеству Г{(i,j)}, (в нашем случае Г{(Д,Г)}).

Множеству (в нашем случае ), в свою очередь, соответствует другая матрица - С1,2, полученная заменой на ? элемент сД,Г в матрице С1:

Матрица С1,2

	А	Б	В	Г	Д	Е
А	?	1	0	10	5	1
Б	2	?	1	14	0	6
В	0	1	?	15	6	0
Г	8	11	12	?	0	6
Д	3	0	2	?	?	5
Е	3	7	0	11	6	?

Матрица С1,2 после приведения

	А	Б	В	Г	Д	Е
А	?	1	0	0	5	1
Б	2	?	1	4	0	6
В	0	1	?	5	6	0
Г	8	11	12	?	0	6
Д	3	0	2	?	?	5
Е	3	7	0	1	6	?

Сумма констант последнего приведения равна 10, так что ц() = 35 + 10 = 45. Теперь выберем между множествами Г{(i,j)} и то, на котором минимальна функция j. В нашем случае из множеств, которому соответствует меньшее из чисел ц(Г{(Д,Г)}) = 42 и ц() = 45. Поэтому дальнейшей разработке подвергнется множество Г{(Д,Г)}. В матрице С1,1 подсчитаем веса нулей (веса нулей указаны в скобках):

	А	Б	В	Д	Е
А	?	0 (0)	0 (0)	5	1
Б	2	?	1	0 (6)	6
В	0 (2)	0 (0)	?	6	0 (0)
Г	2	4	6	?	0 (2)
Е	3	6	0 (3)	6	?

Самым тяжёлым является нуль с номером (Б, Д), так что теперь следует рассматривать множества и . Обратимся к первому из них. Необходимо заменить на числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем циклам, которые проходят через уже отобранные ранее ребра. Получим матрицу С1,1,1:

	А	Б	В	Е
А	?	0	0	1
В	0	0	?	0
Г	2	4	6	0
Е	3	6	0	?

Сумма констант остается неизменной, так как матрица не требовала приведения ц() = 42.

Матрица С1,1,2

	А	Б	В	Д	Е
А	?	0	0	5	1
Б	2	?	1	?	6
В	0	0	?	6	0
Г	2	4	6	?	0
Е	3	6	0	6	?

Матрица С1,1,2 после приведения

	А	Б	В	Д	Е
А	?	0	0	0	1
Б	1	?	0	?	5
В	0	0	?	1	0
Г	2	4	6	?	0
Е	3	6	0	1	?

Сумма констант приведения ц() = 42 + 6 = 48. Следовательно дальнейшей разработке подлежит . «Взвешиваем» нули в матрице С1,1,1:

	А	Б	В	Е
А	?	0 (0)	0 (0)	1
В	0 (2)	0 (0)	?	0 (0)
Г	2	4	6	0 (2)
Е	3	6	0 (3)	?

Самым тяжелым является нуль с номером (Е, В), теперь рассмотрим множества и .Вычеркиваем строку Е и столбец В, и получаем матрицу С1,1,1,1:

	А	Б	Е
А	?	0	1
В	0	0	0
Г	2	4	0

Матрица не требует приведения и сумма констант приведения останется без изменений ц() = 42.

Рассмотрим матрицу С1,1,1,2:

Матрица С1,1 ,1,2

	А	Б	В	Е
А	?	0	0	1
В	0	0	?	0
Г	2	4	6	0
Е	3	6	?	?

Матрица С1,1,1,2 после приведения

	А	Б	В	Е
А	?	0	0	1
В	0	0	?	0
Г	2	4	6	0
Е	0	3	?	?

Сумма констант приведения

ц() = 42 + 3 = 45.

Произведем оценку нулей в матрице С1,1,1,1:

	А	Б	Е
А	?	0 (1)	1
В	0 (2)	0 (0)	0 (0)
Г	2	4	0 (2)

У нас получилось два одинаково тяжелых нуля, разработаем матрицы и .

Вычеркиваем строку В и столбец А. Получаем матрицу С1,1,1,1,1:

	Б	Е
А	0	1
Г	4	0

Матрица не требует приведения и сумма констант приведения останется без изменений

ц() = 42.

Для множества матрица С1,1,1,1,2 приобретает вид:

Матрица С1,1,1,1,2

	А	Б	Е
А	?	0	1
В	?	0	0
Г	2	4	0

Матрица С1,1,1,1,2 после приведения

	А	Б	Е
А	?	0	1
В	?	0	0
Г	0	4	0

Сумма констант приведения

ц() = 42 + 2 = 44.

Произведем оценку нулей в матрице С1,1,1,1,1:

	Б	Е
А	0 (5)	1
Г	4	0 (5)

Следовательно, кольцевой маршрут имеет вид: (Д,Г) (Г,Е), (Е,В), (В,А), (А,Б), (Б,Д) или или Д > Г > Е > В >А > Б > Д.

Затраты времени на проход маршрута = 42.

Задача 4

На сетевом графике (рис.4.1) цифры у стрелок показывают в числителе - продолжительность работы в днях, в знаменателе - количество ежедневно занятых работников на её выполнение.

В распоряжении организации, выполняющей этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.

Используя имеющиеся запасы времени по некритическим работам, скорректируйте сетевой график с учётом ограничения по количеству рабочих.

Рисунок 4.1

Решение

Таблица 4.1

Шифр работы i-j	Продолжительность работы
1-2	2	0	2	6	8	6	0
1-3	5	0	5	0	5	5	0
1-4	6	0	6	8	14	8	0
2-5	4	2	6	8	12	6	6
3-5	7	5	12	5	12	0	0
3-6	3	5	8	13	16	8	0
4-6	2	6	8	14	16	8	0
5-7	6	12	18	12	18	0	0
6-7	2	8	10	16	18	8	8

Запись работ в графе 1 производится в определенном порядке. Сначала записываются все работы, выходящие из исходного первого события, затем -- выходящие из второго события, потом -- из третьего и т. д. В графе 2 против каждой работы проставляется ее продолжительность. После этого приступают к определению ранних сроков начала и окончания работ. Графы 3 и 4 рекомендуется заполнять одновременно сверху вниз. Сначала в графе 3 проставляется раннее начало работ, выходящих из первого события. Оно равно нулю. По формуле t=t+t подсчитываются ранние окончания этих работ и проставляются в графу 4 против соответствующей работы.

Затем последовательно определяют ранние параметры для всех других работ. При этом соблюдаются правила: раннее начало работы, имеющей только одну предшествующую работу, равно раннему окончанию предшествующей работы, а раннее начало работы, у которой предшествующих работ две или несколько, равно максимальному значению из ранних окончаний предшествующих работ.

Для того чтобы проставить, например, раннее начало работы 3--5, находим в графе 1 среди работ, записанных выше данной, работу, шифр которой заканчивался бы на 3, т. е. предшествующую. В нашем случае это будет работа 1--3. В графе 4 находим значение ее раннего окончания, равное 5, и переписываем в графу 3 против работ 3-- и 3--6.

Рассмотрим другую работу, например 5--7. Среди работ, записанных выше данной, две работы оканчиваются на цифру 5 -- работы 2--5 и 3--5. Раннее окончание этих работ соответственно равно 6 и 12 дней. Следовательно, в качестве раннего начала работы 5--7 принимаем наибольшее значение 12 и проставляем его в графу 3 против работы 5--7. Одновременно проставляем и раннее окончание работы 5--7, которое находим как сумму ее раннего начала и продолжительности 12+6=18. Таким образом, определяются по таблице ранние сроки начала и окончания всех работ сетевого графика. Раннее окончание работы 5--7, равное 18 дням, будет одновременно и поздним окончанием работ, входящих в конечное событие, поэтому против работ 5--7 и 6--7 в графе 6 проставляем 18.

Дальше заполнение граф 6 и 5 таблицы ведется в обратном порядке, т. е. снизу вверх. В графу 5 записывается позднее начало работ 5 -- 7 и 6 -- 7 , которое рассчитывается как разность между значениями позднего окончания и продолжительностью работы по формуле t = t -- t; t =t-t =18-2 =16, t = 18-6 = 12. Затем в графе 1 среди работ, записанных выше работы 6--7, отыскиваются работы, заканчивающиеся на шифр 6. Таких работ две: 3--6 и 4--6. Против, них в графу 6 записываем их позднее окончание, равное 16, и аналогично рассчитываем для них позднее начало. Если у работы имеются не одна, а несколько последующих работ, то в качестве ее позднего окончания следует принять наименьшее значение из поздних начал последующих работ.

Например, у работ 3--5 и 3--6 поздние начала соответственно равны 5 и 13. Эти работы являются последующими для работы 1--3. Для работы 1--3 в качестве позднего окончания следует взять наименьшее значение из поздних начал последующих работ -- 5.

Полным резервом времени работы R называется время, на которое можно задержать начало данной работы по сравнению с наиболее ранним возможным временем ее начала или на которое можно увеличить продолжительность работы без изменения общего срока окончания всех работ. Полный резерв времени равен разности позднего и раннего начала или позднего и раннего окончания работы

R = t--t = t--t

Общий или полный резерв времени работы R определяется как разность между данными графами 6 и 4 или 5 и 3.

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

r= t--t

Частный резерв времени работы, равный разности раннего начала последующей работы и раннего окончания данной работы, определяется следующим образом: среди последующих работ находим любую работу, у которой шифр начинается с той цифры, на которую заканчивается шифр данной работы. Например, при определении частного резерва работы 3--6 среди последующих работ, начинающихся с цифры 6, имеется одна. Это работа 6--7 . Для нее раннее начало равно 8, а раннее окончание работы 3--6--8. Следовательно, частный резерв времени работы 3--6 равен 8--8=0.

Размещено на Allbest.ru

...