Контрольная работа 2 страница

	А	Б	В	Г	Д	Е
А	-			∞
Б		-
В			-
Г				-
Д					-
Е						-

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

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

В матрице С_1,2,1 подсчитаем веса нулей (веса нулей указаны в скобках):

	А	Б	В	Г	Д	Е
А	-		0(0)	-	0(0)
Б		-				0(3)
В			-	0(8)
Г	0(2)			-
Д	0(0)		0(0)		-	0(0)
Е		0(1)			0(0)	-

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

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

	А	Б	В	Д	Е
А	-
Б		-
Г	-		-
Д				-
Е					-

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

	А	Б	В	Г	Д	Е
А	-			-
Б		-
В			-	-
Г				-
Д					-
Е						-

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

	А	Б	В	Г	Д	Е
А	-			-
Б		-
В			-	-
Г				-
Д					-
Е						-

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

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

	А	Б	В	Д	Е
А	-		0(0)	0(0)
Б		-			0(5)
Г	0(8)		-
Д	0(0)		0(0)	-	0(0)
Е		0(1)		0(0)	-

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

Вычеркиваем строку Г и столбец А, ставим ∞ в клетке (А,Г) и получаем матрицу С_1,2,1,1

	Б	В	Д	Е
А		-
Б	-
Д			-
Е				-

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

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

	А	Б	В	Д	Е
А	-
Б		-
Г	¥		-
Д				-
Е					-

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

	А	Б	В	Д	Е
А	-
Б		-
Г	-		-
Д				-
Е					-

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

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

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

	Б	В	Д	Е
А		-	0(13)
Б	-			0(5)
Д		0(7)	-	0(0)
Е			0(0)	-

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

Получаем матрицу С_1,2,1,1,1:

	Б	В	Е
Б	-
Д		-
Е			-

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

	Б	В	Е
Б	-
Д		-
Е			-

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

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

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

	Б	В	Д	Е
А		-	-
Б	-
Д			-
Е				-

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

	Б	В	Д	Е
А		-	-
Б	-
Д			-
Е				-

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

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

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

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

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

	Б	В
Д		-
Е	-

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

	Б	В
Д		-
Е	-

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

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

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

	Б	В	Е
Б	-		-
Д		-
Е			-

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

	Б	В	Е
Б	-		-
Д		-
Е			-

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

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

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

ЗАДАЧА № 4

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

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

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

Рисунок 4.1.

Решение:

Шифр работы i-j	Продолжи-тельность работы
1-2
1-3
1-4
2-5
3-5
3-6
4-6
5-7
6-7

Дата добавления: 2015-04-24