Отметка о зачислении и переводе с курса на курс

Пример работы алгоритма.

Составляем таблицу значений l_ij. Таблица будет заполнена ниже главной диагонали, т.к. матрица стоимости перевозок симметрична.

Первая сверху строка и первый слева столбец и клетки главной диагонали не заполняются, т.к. параметр l_ij вычисляется при i¹j¹0.

l_ij= d_i0 + d_0j - d_ij

l₂₁= d₂₀ + d₀₁ - d₂₁ =6+4-3=7

	P1	P2	P3	P4	P5	P6
P1	-	-	-	-	-	-
P2		-	-	-	-	-
P3			-	-	-	-
P4				-	-	-
P5					-	-
P6						-

Выбираем начальное тривиальное решение S.

Составляем таблицу для g _i и объёмности перевозок по контурам решения S.

	g i	Q{ Pi }
P0,P1,P0	g 1 =1	Q{P1}=C 1=4
P0,P2,P0	g 2 =1	Q{P2}=C 2=6
P0,P3,P0	g 3 =1	Q{P3}=C 3=3
P0,P4,P0	g 4 =1	Q{P4}=C 4=1
P0,P5,P0	g 5 =1	Q{P5}=C 5=8
P0,P6,P0	g 6 =1	Q{P6}=C 6=2

1). l₆₃= 12 =maximum

g₆ = g₃ =1 и Q{P₆}+ Q{P₃}=C ₆+ C ₃=2+3=5< C =10

Образуем класс {P_6,P₃} и выделяем l₆₃ кружком в таблице. Значения g _i не изменяются.

2). l₆₂= 10 > 0

Пробуем объединить классы {P_6,P₃} и {P₂}:

g₆ = g₂ =1 и Q{P₆}+ Q{P₃}+ Q{P₂}=C ₆+ C ₃+ C ₂=2+3+6=11 > C =10

Вычёркиваем l₆₂ в таблице. Значения g _i не изменяются.

3). l₅₃= 10 > 0

Пробуем объединить классы {P_6,P₃} и {P₅}:

g₅ = g₃ =1 и Q{P₅}+ Q{P₆}+ Q{P₃}=C ₅+ C ₆+ C ₃=8+2+3=13 > C =10

Вычёркиваем l₅₃ в таблице. Значения g _i не изменяются.

4). l₃₁= 9 > 0

Пробуем объединить классы {P_6,P₃} и {P₁}:

g₁ = g₃ =1 и Q{P₃}+ Q{P₆}+ Q{P₁}=C ₃+ C ₆+ C ₁=3+2+4=9 < C =10

Образуем класс {P_6,P₃,P₁}. Отмечаем клетку l₃₁ в таблице.

Находим новые значения g _i: g₆ = g₁ =1; g₃ =0

5). l₃₂= 9 > 0

g₃ =0, g₂ =1 Условие а) не выполняется. Поэтому вычеркиваем клетку l₃₂.

6). l₅₁= 7 > 0

g₅ = g₁ =1 и Q{P₅}+ Q{P₁}+ Q{P₆}+ Q{P₃}=C ₅+ C ₁+ C ₆+ C ₃=8+4+2+3=17 > C =10

Вычёркиваем l₅₁ в таблице. Значения g _i не изменяются.

7). l₂₁= 7 > 0

g₂ = g₁ =1 и Q{P₂}+ Q{P₁}+ Q{P₆}+ Q{P₃}=C ₂+ C ₁+ C ₆+ C ₃=6+4+2+3=15 > C =10

Вычёркиваем l₂₁ в таблице. Значения g _i не изменяются.

8). l₆₄ = 5 > 0

g₆ = g₄ =1 и Q{P₆}+ Q{P₃}+ Q{P₁}+ Q{P₄}=C ₆+ C ₃+ C ₁+ C ₄=2+3+4+1=10 = C =10

Образуем класс {P_4,P₆,P₃,P₁}. Отмечаем клетку l₆₄ в таблице.

Находим новые значения g _i: g₁ = g₄ =1; g₃ = g₆ =0

9). l₆₅ = 5 > 0

g₆ =0, g₅ =1 Условие а) не выполняется. Поэтому вычеркиваем клетку l₆₅.

10). l₆₁ = 4 > 0

Но {P₆} и {P₁} уже в одном классе! Поэтому вычеркиваем клетку l₆₁.

11). l₄₁ = 4 > 0

Но {P₄} и {P₁} тоже уже в одном классе! Поэтому вычеркиваем клетку l₄₁.

12). l₅₂= 3 > 0

Пробуем объединить классы {P₅} и {P₂}:

g₅ = g₂ =1 и Q{P₅}+ Q{P₂}=C ₅+ C ₂=8+6=14 > C =10. Условие не выполнено.

Вычеркиваем клетку l₅₂ в таблице.

13). l₅₄= 3 > 0

Пробуем объединить классы {P₄, P₆, P₃, P₁,} и {P₅}:

g₅ = g₄ =1. Очевидно, что S Q{P} будет > C =10. Условие не выполнено.

Вычеркиваем клетку l₅₄ в таблице.

14). l₄₂= 2 > 0

Пробуем объединить классы {P₄, P₆, P₃, P₁,} и {P₂}:

g₂ = g₄ =1. Очевидно, что S Q{P} будет > C =10. Условие не выполнено.

Вычеркиваем клетку l₄₂ в таблице.

15). l₄₃ = 2 > 0

Но {P₄} и {P₃} уже в одном классе! Поэтому вычеркиваем клетку l₄₁.

Все элементы l₄₃ мы рассмотрели. У нас получились такие маршруты, являющиеся решением задачи:

(Р₀,Р₄,Р₆,Р₃,Р₁,Р₀)= d₀₄ + d₄₆ + d₆₃ + d₃₁ + d₁₀ =2+2+1+3+4=12;

(Р₀,Р₂,Р₀)= d₀₂ + d₂₀ =6+6=12;

(Р₀,Р₅,Р₀)= d₀₅ + d₅₀ =4+4=8;

Общая стоимость перевозок: 12+12+8=32.

Полученная ранее стоимость перевозок без учёта метода Флетчера-Кларка была равна 44, что больше 32.

ВЫПОЛНЕНИЕ УЧЕБНОГО ПЛАНА

Наименование дисциплины	Выполнение контрольных и курсовых работ	Экзамены и зачеты	Примечания
Дата поступления	Фамилия рецензента	Отметка сдаче	Дата	Фамилия экзаменатора	Оценка

ЗАЧЕТНО-ЭКЗАМЕНАЦИОННЫЕ СЕССИИ

Дата вызова	Наименование документа	Дата вызова	Наименование документа	Примечания

За весь период обучения получено оценок________ из них: отлично_____

хорошо______

удовлетворительно______

Доступен к сдаче государственных экзаменов, приказ №__ от «___________»_____ 20 г.

ГОСУДАРСТВЕННЫЕ ЭКЗАМЕНЫ

№ п/п	Наименование дисциплины	Дата экзамена	Оценка

Дипломная работа с защитой в Государственной экзаменационной комиссии

Решением Государственной экзаменационной комиссии от «________»___ 20 г.

Присвоена квалификация:

/со специализацией/

ДЕКАН__________________

Дата добавления: 2015-01-03