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

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

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

Информатики

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

«Экономико-математические методы и модели в отрасли связи»

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

ЗАДАЧА 1

На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - Q_А=1600, Б - Q_Б=800, В - Q_В=400 номеров . Потребности новых районов застройки города в телефонах составляют: 1 - q₁=800, 2 - q₂=900, 3 - q₃=400, 4 - q₄ = 700 номеров . Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.

Таблица 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	1600
Б	3	2	1	4	800
В	6	7	5	2	400
Спрос районов, номеров	800	900	400	700	2800

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

Q_A+Q_Б+Qв= q₁+q2+q₃+q₄ =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 которые можно заполнить единственным образом, за счет станции А в соответствии со спросом. Таблица 1.2 примет вид (таблица 1.3) . Полученное методом наименьшего элемента решение задачи показано в таблице 3 протяженность линий согласно этому решению составит:

800 * 4 + 500 * 5 + 300 * 4 + 400 * 2 + 400 * 1 + 400*2 = 8100 км.

Таблица 1.3

Станции	РАЙОНЫ	Возможности станций, номеров
	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.4

Станции	Дополнительный столбец	РАЙОНЫ	Возможности станций, номеров
		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.5.

Таблица 1.5

Станции	Дополнительный столбец	РАЙОНЫ	Возможности станций, номеров
		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.

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

ЗАДАЧА 2

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

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

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

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

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

1. Определим значение поступающей нагрузки ? по формуле

 = 1·2=2

2. Найдем вероятность того, что все линии связи свободны по формуле:

,

где n количество линий связи, к=1,2,…,n

Вероятность того, что все линии связи будут свободны, составляет 13,5%

3. Рассчитаем вероятности занятости k-линий из n, по формуле

k=1,

k=2,

k=3, =0,18

k=4,

k=5,

k=6,

k=7,

k=8,

4. Найдем вероятность того, что все линии связи заняты, т.е. вероятность отказа, по формуле:

Вероятность отказа равна 8,5%.

5. Найдем среднее число занятых линий по формуле:

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

6. Коэффициент занятости линий

=

7. Найдем среднее число свободных линий по формуле:



Среднее число свободных линий равно 5,99

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

Коэффициент простоя можно было посчитать другим методом 1-0,25=0,75

k
0	1	0,135	1,08
1	2	0,27	1,89	0,27
2	2	0,27	1,62	0,54
3	1,33	0,18	0,9	0,54
4	0,67	0,09	0,36	0,36
5	0,27	0,036	0,108	0,18
6	0,09	0,012	0,024	0,072
7	0,025	0,0034	0,0034	0,024
8	0,0063	0,00085	0	0,0069
Итого	7,39	1	5,99	1,99

Вывод: качество обслуживания абонентов неплохое так как вероятность отказа составляет 8,5%, но эффективность использования линий низкая потому что очень высокий процент простоя линий связи 75%.

ЗАДАЧА 3

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

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

Вариант	А	Б	В	Г	Д	Е
A	9	?	21	12	2	15	23
Б	9	18	?	20	10	19	7
В	9	12	20	?	6	18	17
Г	9	2	10	8	?	21	16
Д	9	14	15	18	20	?	14
Е	9	24	7	18	16	14	?

Решение:

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

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

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

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

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

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

	А	Б	В	Г	Д	Е
А		19	10	0	13	21
Б	11		13	3	12	0
В	6	14		0	12	11
Г	0	8	6		19	14
Д	0	1	4	6		0
Е	17	0	11	9	7

Теперь ? по столбцам:

	А	Б	В	Г	Д	Е
А		19	10	0	13	21
Б	11		13	3	12	0
В	6	14		0	12	11
Г	0	8	6		19	14
Д	0	1	4	6		0
Е	17	0	11	9	7
	0	0	4	0	7	0
	min в столбце 1	min в столбце 2	min в столбце 3	min в столбце 4	min в столбце 5	min в столбце 6

	А	Б	В	Г	Д	Е
А		19	6	0	6	21
Б	11		9	3	5	0
В	6	14		0	5	11
Г	0	8	2		12	14
Д	0	1	0	6		0
Е	17	0	7	9	0

Сумма констант приведения ?(Г)=2+7+6+2+14+7+4+7=49.

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

Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 6 (c_А,Г=c_А,Д=6), и минимума по четвёртому столбцу Г, равного 0 (c_Г,В=0), без учета самого c_А,Г.

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

	А	Б	В	Г	Д	Е
А		19	6	0(6)	6	21
Б	11		9	3	5	0(3)
В	6	14		0(5)	5	11
Г	0(2)	8	2		12	14
Д	0(0)	1	0(2 )	6		0(0)
Е	17	0(1)	7	9	0(5)

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

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

А Б В Д Е Б 11 9 5 0 В 6 14 5 11 Г ? 8 2 12 14 Д 0 1 0 0 Е 17 0 7 0 Матрица С1,1	А Б В Д Е Б 11 9 5 0 В 1 9 0 6 Г ? 6 0 10 12 Д 0 1 0 0 Е 17 0 7 0 Матрица С1,1 после приведения

Сумма констант приведения матрицы С_1,1 здесь равна 7, поэтому ?(Г_{(А,Г)})= ?_{А,Г}=49+7=56. Сопоставим результат ?(Г_{(i,j)}) множеству Г_{(i,j)}, (в нашем случае Г_{(А,Г)}).

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

А Б В Г Д Е А 19 6 ? 6 21 Б 11 9 3 5 0 В 6 14 0 5 11 Г 0 8 2 12 14 Д 0 1 0 6 0 Е 17 0 7 9 0 Матрица С1,2	А Б В Г Д Е А 13 0 ? 0 15 Б 11 9 3 5 0 В 6 14 0 5 11 Г 0 8 2 12 14 Д 0 1 0 6 0 Е 17 0 7 9 0 Матрица С1,2 после приведения

Сумма констант последнего приведения равна 6, так что ?()=49+6=55. Теперь выберем между множествами Г_{(i,j)} и то, на котором минимальна функция j. В нашем случае из множеств, которому соответствует меньшее из чисел ?(Г_{(А,Г)})=56 и ?()=55 .Поэтому дальнейшей разработке подвергнется множество . Итак, выделена определенная дуга (А,Г) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл , если данная ветвь будет продолжена до конца и иметь минимальный вес. В матрице С_1,2,1 подсчитаем веса нулей (веса нулей указаны в скобках):

	А	Б	В	Г	Д	Е
А		13	0(0)	?	0(0)	15
Б	11		9	3	5	0(3)
В	6	14		0(8)	5	11
Г	0(2)	8	2		12	14
Д	0(0)	1	0(0)	6		0(0)
Е	17	0(1)	7	9	0(0)

Самым тяжёлым является нуль с номером (В,Г), так что теперь следует рассматривать множества и . Обратимся к первому из них. Необходимо заменить на числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем циклам, которые проходят через уже отобранные ранее ребра. Поскольку, вычеркнув строку В и столбец Г в матрице С_1,2, нужно также заменить на ? числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (В,Г) надо поставить символ ?. Получим матрицу С_1,2,1:

	А	Б	В	Д	Е
А		13	0	0	15
Б	11		9	5	0
Г	?	8	?	12	14
Д	0	1	0		0
Е	17	0	7	0

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

А Б В Г Д Е А 13 0 ? 0 15 Б 11 9 3 5 0 В 6 14 ? 5 11 Г 0 8 2 12 14 Д 0 1 0 6 0 Е 17 0 7 9 0 Матрица С1,2,2	А Б В Г Д Е А 13 0 ? 0 15 Б 11 9 0 5 0 В 1 9 ? 0 6 Г 0 8 2 12 14 Д 0 1 0 3 0 Е 17 0 7 6 0 Матрица С1,2,2 после приведения

Сумма констант приведения ?()=55+8=63. Следовательно дальнейшей разработке подлежит . «Взвешиваем» нули в матрице С_1,2,1:

	А	Б	В	Д	Е
А		13	0(0)	0(0)	15
Б	11		9	5	0(5)
Г	0(8)	8	?	12	14
Д	0(0)	1	0(0)		0(0)
Е	17	0(1)	7	0(0)

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

	Б	В	Д	Е
А	13	?	0	15
Б		9	5	0
Д	1	0		0
Е	0	7	0

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

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

А Б В Д Е А 13 0 0 15 Б 11 9 5 0 Г 8 ? 12 14 Д 0 1 0 0 Е 17 0 7 0 Матрица С1,2,1,2	А Б В Д Е А 13 0 0 15 Б 11 9 5 0 Г 0 ? 4 6 Д 0 1 0 0 Е 17 0 7 0 Матрица С1,2,1,2 после приведения

Сумма констант приведения ?()=55+8=63.

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

	Б	В	Д	Е
А	13	?	0(13)	15
Б		9	5	0(5)
Д	1	0(7)		0(0)
Е	0	7	0(0)

Самый тяжелый вес равный 13 имеет нуль в клетке с номером (А,Д), следовательно будем рассматривать множества и . Вычеркиваем строку А и столбец Д и заменяем число в клетке (Д,В) на знак ?. Получаем матрицу С_1,2,1,1,1:

Б В Е Б 9 0 Д 1 ? 0 Е 0 7 Матрица С1,2,1,1,1	Б В Е Б 2 0 Д 1 ? 0 Е 0 0 Матрица С1,2,1,1,1 после приведения

Сумма констант приведения ?()=55+7=62.

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

Б В Д Е А 13 ? ? 15 Б 9 5 0 Д 1 0 0 Е 0 7 0 Матрица С1,2,1,1,2	Б В Д Е А 0 ? ? 2 Б 9 5 0 Д 1 0 0 Е 0 7 0 Матрица С1,2,1,1,2 после приведения

Сумма констант приведения ?()=55+13=68.

Следовательно дальше разрабатываем матрицу . «Взвешиваем» нули в матрице С_1,2,1,1,1:

	Б	В	Е
Б		2	0(2)
Д	1	?	0(1)
Е	0(1)	0(2)

У нас получилось два одинаково тяжелых нуля, разработаем матрицы и . Вычеркиваем строку Б и столбец Е и заменяем число в клетке (Б,Е) на ?. Получаем матрицу С_1,2,1,1,1,1:

Б В Д 1 ? Е ? 0 Матрица С1,2,1,1,1,1	Б В Д 0 ? Е ? 0 Матрица С1,2,1,1,1,1 после приведения

Сумма констант приведения ? ()=62+2=68.

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

Б В Е Б 2 ? Д 1 ? 0 Е 0 0 Матрица С1,2,1,1,1,2	Б В Е Б 0 ? Д 1 ? 0 Е 0 0 Матрица С1,2,1,1,1,2 после приведения

Сумма констант приведения ?()=62+2. Получается что для дальнейшей разработки можно брать любое из множеств, если мы возьмем матрицу С_1,2,1,1,1,1 то можно отработать матрицу и следовательно мы получим кольцевой маршрут следующего вида:

(В,Г)(Г,А)(А,Д)(Д,Б)(Б,Е)(Е,В) или В>Г>А>Д>Б>Е>В.

ЗАДАЧА 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.

Таблица 4.2

Код работы	tij	rij	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
1-2	2	2	8	8
			2	2	2	2	2	2	2	2
1-3	5	0	20	20	20	20	20
			20	20	20	20	20
1-4	6	0	11	11	11	11	11	11
			6	6	6	6	6	6	6	6	6	6	6
2-5	4	6			11	11	11	11
								11	11	11	11
3-5	7	0						14	14	14	14	14	14	14
								9	9	9	9	9	9	9	9	9	9
3-6	3	0						11	11	11
												11	11	11
4-6	2	0							3	3
											2	2	2
5-7	6	0													18	18	18	18	18	18
															18	18	18	18	18	18
6-7	2	8									15	15
																		10	10	10
Число рабочих до корректировки	39	39	42	42	42	47	28	28	29	29	14	14	18	18	18	18	18	18
Число рабочих после корректировки	28	28	28	28	28	28	28	28	28	28	28	28	27	27	27	28	28	28

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

Расчет параметров в сетевом графике. Корректировка сетевого графика по параметру «время».

Сетевой график основан на использовании другой математической модели - графа. Говоря более привычным для инженера (но менее точным) языком, граф - это набор кружков (прямоугольников, треугольников и проч.), соединенных направленными или ненаправленными отрезками. В этом случае сами кружки (или другие используемые фигуры) по терминологии теории графов будут называться "вершинами", а соединяющие их ненаправленные отрезки - "ребрами", направленные (стрелки) - "дугами". Если все отрезки являются направленными, граф называется ориентированным, если ненаправленными - неориентированным.

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



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

В графике могут использоваться пунктирные стрелки - это так называемые "зависимости" (фиктивные работы), не требующие ни времени, ни ресурсов. Они указывают на то, что "событие", на которое направлена пунктирная стрелка, может происходить только после свершения события, из которого исходит эта стрелка.

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

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

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

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

Очередность расчета параметров сети принимается следующая : сначала определяются ранние сроки начала и окончания работ t^рн_ij и t^ро_ij , начиная от исходного события и кончая завершающим. На основе вычисленных ранних сроков устанавливается критический путь, затем определяются поздние сроки начала и окончания t^пн_ij и t^по_ij , после чего для всех некритических путей и работ вычисляются резервы времени.

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

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

t^ро_ij = 0 + t_ij Например : t^ро_1-2 = 0 + t_1-2 = 0 + 4 = 4

Раннее окончание работ равно раннему ее началу плюс продолжительность самой работы.

t^ро_ij = t^рн_ij + t_ij Например : t^ро_3-6 = t^рн _3-6 + t_3-6 = 10+7=17

Если данной работе предшествует только одна работа, то раннее начало данной работы равно раннему окончанию предшествующей работы.

t^рн_ij = t^ро_hi

Например : t^рн_3-6 = t^ро_1-3 = 10

Если данной работе предшествуют несколько работ, то ее раннее начало равно максимальному значению из всех ранних окончаний предшествующих работ .

t^рн_ij = max { t^ро_hi }.

Например : t^рн _4-6 = max{t^ро_2-4, t^ро_1-4 }= max{3,6} = 6

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

t^пн_ij = t^по_ij - t_ij

Например : t^пн_5-8 = t^по_5-8 -t_5-8 = 30-11=19

Если у данной работы последующих работ одна, ее позднее окончание равно позднему началу последующей работы

t^по_ij = t^пн_jk.

Например : t^по_3-5 = t^пн _5-8 =19

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

Разница между продолжительностью критического пути t_кр и продолжительностью любого другого пути t_L называется полным резервом времени пути L и обозначается R_L.

R_L = t_кр - t_L

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

Работы в сетевом графике, не лежащие на критическом пути, располагают полным и частным резервами.

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

Полный резерв равен разности позднего и раннего начала или позднего и раннего окончания всех работы.

R_ij = t^пн_ij - t^рн_ij = t^по_ij - t^ро_ij.

Например : R_4-6 = t^по_4-6 - t^ро_4-6 = 17-14=3

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

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

r_ij = t^рн_jk - t^ро_ij

Например : r_1-4 = t^рн_4-6 - t^ро_1-4 = 6 -3=3.

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

- за счет резервов времени некритических работ и соответствующего перераспределения ресурсов;

- за счет привлечения дополнительных ресурсов;

- за счет изменения организационно-технологической последовательности и взаимосвязи работ.

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

Принятие решений методами имитационного моделирования (привести пример).

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

Многообразие ситуаций неопределённости делает возможным применение любого из описанных методов в качестве инструмента анализа рисков, однако, по мнению автора, наиболее перспективными для практического использования являются методы сценарного анализа и имитационного моделирования, которые могут быть дополнены или интегрированы в другие методики. В частности, для количественной оценки риска инвестиционного проекта предлагается использовать следующие алгоритмы: Алгоритм имитационного моделирования (инструмент «РИСК-АНАЛИЗ»):

1.Определяются ключевые факторы ИП. Для этого предлагается применять анализ чувствительности по всем факторам (цена реализации, рекламный бюджет, объём продаж, себестоимость продукции и т. д.). В качестве ключевых выбираются те факторы, изменения которых приводят к наибольшим отклонениям чистой текущей стоимости (NPV).

Таблица 1. Выбор ключевых факторов ИП на основе анализа чувствительности

Факторы	Дисперсия NPV
	F1	F2	F3	……	Fn
-20%	npv11	npv21	npv31	……	npvn1
-10%	npv12	npv22	npv32	……	npvn2
0	npv13	npv23	npv33	……	npvn3
10%	npv14	npv24	npv34	……	npvn4
20%	npv15	npv25	npv35	……	npvn5
	Var (npv1)	Var (npv2)	Var (npv3 )		Var (npvn)

2. Определяются максимальное и минимальное значения ключевых факторов, и задаётся характер распределения вероятностей. В общем случае рекомендуется использовать нормальное распределение. 3. На основе выбранного распределения проводится имитация ключевых факторов, с учётом полученных значений рассчитываются значения NPV.

4. На основе полученных в результате имитации данных рассчитываются критерии, количественно характеризующие риск ИП (мат. ожидание NPV, дисперсия, среднеквадратическое отклонение и др.). Для проведения сценарного анализа разработана методика, позволяющая учитывать всевозможные сценарии развития, а не три варианта (оптимистичный, пессимистичный, реалистичный), как это предлагается в литературе. Предлагается следующий алгоритм сценарного анализа:

1.Используяанализ чувствительности, определяются ключевые факторы ИП (см. выше).

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

3.Методомэкспертных оценок определяются вероятности каждого сценария.

4.По каждому сценарию с учетом его вероятности рассчитывается NPV проекта, в результате чего получается массив значений NPV (табл. 2.)

Таблица 2. Массив значений NPV

Сценарий Вероятность NPV
1 Р1 npv1
2 Р2 npv2
3 Р3 npv3
4 Р4 npv4
5 Р5 npv5
… … …
n Pn npvn

5. На основе данных массива рассчитываются критерии риска ИП

Практические примеры расчёта

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

Таблица 3 Исходные условия эксперимента

	Минимум	Вероятное	Максимум
NPV(тыс.руб.)	9634	14790	43163
Вероятность	0,05	0,9	0,05

На основе исходных данных проводим имитацию. Для проведения имитации рекомендуется использовать функцию «Генерация случайных чисел».

Для осуществления имитации рекомендуется использовать нормальное распределение, так как практика риск анализа показала, что именно оно встречается в подавляющем большинстве случаев. Количество имитаций может быть сколь угодно большим и определяется требуемой точностью анализа. В данном случае ограничимся 500 имитациями.

Таблица 4 Имитация

№ п. п.	NPV(тыс. руб.)
1	15940,14853
2	15951,41663
3	15947,78512
4	15953,94136
5	15951,61013
6	15950,67133
7	15949,48875
8	15955,30642
9	15954,1289
10	15953,20001

И т. д. 500 имитаций

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

Имитационное моделирование продемонстрировало следующие результаты: 1. Среднее значение NPV составляет 15950,79тыс. руб. 2. Минимальное значение NPV составляет 15940,15 тыс. руб. 3. Максимальное значение NPV составляет 15962,98 тыс. руб. 4. Коэффициент вариации NPV равен 12% 5. Число случаев NPV < 0 - нет. 6. Вероятность того, что NPV будет меньше нуля равна нулю. 7. Вероятность того, что NPV будет больше максимума также равна нулю. 8. Вероятность того, что NPV будет находится в интервале [M(E) + s; max] равна 16%. 9. Вероятность того, что NPV будет находиться в интервале [M(E) - s;[M(E)] равна 34%.

Оценим риск данного инвестиционного проекта.

Для расчёта цены риска в данном случае используем показатель среднеквадратического отклонения - s, и мат.ожидания - М (NPV). В соответствии с правилом «трёх сигм»,значение случайной величины, в данном случае - NPV, с вероятностью близкой 1находится в интервале [М-3s; М+3s]. В экономическом контексте это правило можно истолковать следующим образом: -вероятность получить NPV проекта в интервале[15950,79-3,58 ; 15950,79 +3,58] равна 68%; -вероятность получить NPV проекта в интервале [15950,79-7,16 ; 15950,79 +7,16] равна 94%; -вероятность получить NPV проекта в интервале [15950,79-10,74; 15950,79 +10,74] близка к единице, т.е. вероятность того, что значение NPVпроекта будет ниже 15 940,05 тыс. руб. (15950,79-10,74) стремится к нулю.

Таким образом, суммарная величина возможных потерь характеризующих данный инвестиционный проект, составляет 10,74 тыс. руб. (что позволяет говорить о высокой степени надёжности проекта).

Иначе говоря, цена риска данного ИП составляет 10,74 тыс. рублей условных потерь, т.е.принятие данного инвестиционного проекта влечёт за собой возможность потерь в размере не более 10,74 тыс. руб

Задача 5

программирование моделирование вероятность

Сколько единиц резервного оборудования R=2 и R=3 нужно иметь, чтобы потери от простоя оборудования были бы минимальными?

Обслуживаемых единиц оборудования n=6, интенсивность обслуживания , среднее время обслуживания 2 мин.

, ,

Электромехаников по обслуживанию r=1ед.

Решение:

Наличие резервного оборудование как и увеличение числа обслуживаемых каналов способствует снижению коэффициента простоя оборудования. В то же время образование резервного парка оборудование требует значительных затрат на его приобретение и содержание. С увеличением единиц резервного оборудования сокращается математическое ожидание числа неработающего оборудования, а вместе с ним сокращаются издержки от простоя оборудования. Задача сводится к отысканию такого соотношения между числом обслуживаемых каналов и количеством резервного оборудования, при котором общая величина издержек предприятия Э(r,R) будет наименьшей. Целевая функция, как упоминалось, имеет вид:

где

r-численность обслуживающего технического персонала;

k-коэффициент сменности обслуживающего персонала;

z-заработная плата с начислением одного электромеханика в единицу времени (в рублях);

- потери предприятия, связанные с неисправностью единицы оборудования в единицу времени (в рублях);

M=f(r,R)-математическое ожидание числа отказавшего оборудования, которое не может быть заменено резервным, т.е. когда запас резервного оборудования полностью исчерпан;

- приведённые затраты на единицу резервного оборудования, отнесённые к единице времени;

i- число типов оборудования;

R- количество резервного оборудования.

Для решения определяется Р_k - вероятность нахождения в обслуживающей системе К - требований и Р₀ - вероятность отсутствия требований в системе.

Среднее время обслуживания 2 мин, следовательно, интенсивность выходящего потока

=ч/треб

Коэффициент загрузки системы

 Обозначим через P_o вероятность того, что в данный момент на обслуживание не поступает ни одного требования и через P_k - вероятность нахождения в системе в данный момент k - требований из n - возможных (k=1,2,3,:,n).

Вероятности различных состояний системы определяют следующие соотношения:

Для определения P_о выразим все P_k(k=1,2,3,:,n) чрез P_о и учтём, что сумма вероятностей всех возможных состояний системы равна единице.

Откуда и определяем P_о , а затем по уравнениям все P_k. Зная P_k (k=1,2,3,:,n) можно вычислить основные числовые характеристики системы.

Математическое ожидание числа отказавших единиц оборудования, которое не

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



Пользуясь данной формулой, рассчитаем значение М для r=1, n=6, и R=2,3. Все расчеты сведем в таблицу.

k	Pk		Pk	Pk*k	R2 = (k-2)Pk	R3 = (k-3)Pk
0	P?	1	0,0282	0	-	-
1	6?0,4?P?	2,4	0,0677	0,0677	0	-
2	6?5?(0,4)??P?	4,8	0,1354	0,2707	0	-
3	6?5?4?(0,4)??P?	7,68	0,2166	0,6497	0,2166	0
4	6?5?4?3?(0,4)4?P?	9,216	0,2599	1,0396	0,5198	0,2599
5	6?5?4?3?2?(0,4)5?P?	7,3728	0,2079	1,0696	0,6237	0,4158
6	6?5?4?3?2?1?(0,4)6?P?	2,9491	0,0832	0,4989	0,3327	0,2495
	ИТОГО	35,4179	1	3,5962	1,6928	0,9252

Раcсчитаем затраты для R=2:

Э_произ= 1+(1,6928*30)+(34*2)=1+50,784+68=119,784 ден.ед.

Раcсчитаем затраты для R=3:

Э_произ= 1+(0,9252*30)+(34*3)=1+27,756+102=130,756

Для минимальных потерь необходимо, при наличии всего одного механика, иметь R=2 резервного оборудования.

Литература

1. Барсук В.А., Губин Н.М., Батый А.Р. Экономико-математические методы в планировании и управлении в отрасли связи. - М.: Радио и связь, 1984. Глава 11, § 11.3, стр. 213.

2. Губин Н.М., Добронравов А.С., Дорохов Б.С. Экономико-математические методы в планировании и управлении в отрасли связи. -М.: Радио и связь, 1993.

3. Курс лекций по предмету Экономико - математические методы и модели в отрасли связи СибГУТИ

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