Автор работы: Пользователь скрыл имя, 03 Марта 2014 в 20:10, контрольная работа
Задача 1. Решить транспортную задачу по критерию стоимости.
Матрица цен: Емкость АТС: Потребность районов:
Задача 2. Найти гамильтонов контур минимальной длины методом динамического программирования
Матрица расстояний:
Проверим оптимальность опорного плана. Находим потенциалы и оценки
u1 + v1 = 7; 0 + v1 = 7; v1 = 7
u4 + v1 = 8; 7 + u4 = 8; u4 = 1
u5 + v1 = 17; 7 + u5 = 17; u5 = 10
u5 + v2 = 4; 10 + v2 = 4; v2 = -6
u5 + v6 = 0; 10 + v6 = 0; v6 = -10
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u2 + v3 = 8; 2 + u2 = 8; u2 = 6
u2 + v4 = 13; 6 + v4 = 13; v4 = 7
u3 + v4 = 8; 7 + u3 = 8; u3 = 1
u1 + v5 = 2; 0 + v5 = 2; v5 = 2
v1=7 |
v2=-6 |
v3=2 |
v4=7 |
v5=2 |
v6=-10 | |
u1=0 |
7 16 |
12 |
2 11 |
14 |
2 11 |
0 |
u2=6 |
19 |
23 |
8 31 |
13 7 |
13 |
0 |
u3=1 |
14 |
8 |
24 |
8 47 |
23 |
0 |
u4=1 |
8 47 |
6 |
8 |
12 |
9 |
0 |
u5=10 |
17 2 |
4 27 |
32 |
13 |
19 |
0 70 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(5;4): 10 + 7 > 13; ∆54 = 10 + 7 - 13 = 4
Выбираем максимальную оценку свободной клетки (5;4): 13
Для этого в перспективную клетку (5;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 16 + |
12 |
2 11 - |
14 |
2 11 |
0 |
7 16 |
2 |
19 |
23 |
8 31 + |
13 7 - |
13 |
0 |
19 |
3 |
14 |
8 |
24 |
8 47 |
23 |
0 |
14 |
4 |
8 47 |
6 |
8 |
12 |
9 |
0 |
8 47 |
5 |
17 2 - |
4 27 |
32 |
13 + |
19 |
0 70 |
17 2 |
Потребности |
65 |
27 |
42 |
54 |
11 |
70 |
Цикл приведен в таблице (5,4; 5,1; 1,1; 1,3; 2,3; 2,4; ).
В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 18 |
12 |
2 9 |
14 |
2 11 |
0 |
38 |
2 |
19 |
23 |
8 33 |
13 5 |
13 |
0 |
38 |
3 |
14 |
8 |
24 |
8 47 |
23 |
0 |
47 |
4 |
8 47 |
6 |
8 |
12 |
9 |
0 |
47 |
5 |
17 |
4 27 |
32 |
13 2 |
19 |
0 70 |
99 |
Потребности |
65 |
27 |
42 |
54 |
11 |
70 |
Проверим оптимальность опорного плана. Находим потенциалы и оценки:
u1 + v1 = 7; 0 + v1 = 7; v1 = 7
u4 + v1 = 8; 7 + u4 = 8; u4 = 1
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u2 + v3 = 8; 2 + u2 = 8; u2 = 6
u2 + v4 = 13; 6 + v4 = 13; v4 = 7
u3 + v4 = 8; 7 + u3 = 8; u3 = 1
u5 + v4 = 13; 7 + u5 = 13; u5 = 6
u5 + v2 = 4; 6 + v2 = 4; v2 = -2
u5 + v6 = 0; 6 + v6 = 0; v6 = -6
u1 + v5 = 2; 0 + v5 = 2; v5 = 2
v1=7 |
v2=-2 |
v3=2 |
v4=7 |
v5=2 |
v6=-6 | |
u1=0 |
7 18 |
12 |
2 9 |
14 |
2 11 |
0 |
u2=6 |
19 |
23 |
8 33 |
13 5 |
13 |
0 |
u3=1 |
14 |
8 |
24 |
8 47 |
23 |
0 |
u4=1 |
8 47 |
6 |
8 |
12 |
9 |
0 |
u5=6 |
17 |
4 27 |
32 |
13 2 |
19 |
0 70 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Запишем оптимальный план:
Минимальные затраты составят:
F(x) = 7*18 + 2*9 + 2*11 + 8*33 + 13*5 + 8*47 + 8*47 + 4*27 + 13*2 + 0*70 = 1381
Ответ: , F(x) = = 1381
Задача 2. Найти гамильтонов контур минимальной длины методом динамического программирования
Матрица расстояний:
Решение:
Задача нахождения гамильтонова контура минимальной длины состоит в следующем: требуется обойти все вершины ориентированного графа с учетом направления дуг, побывав в каждой вершине точно один раз и в конце пути вернуться в исходную вершину.
Пусть xi – произвольная вершина (i =1,2…6), а V – любое подмножество вершин, не содержащее вершины x1 и вершины xi. Через М(i, V) обозначим совокупность путей, каждый из которых начинается из xi, завершается в x1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V ) обозначим длину кратчайшего пути множества М(i, V ). Для решаемой задачи В(i, V) – функция Беллмана. Как очевидно, В(1, {2, 3, …, n}) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все вершины.
Если V – одноэлементное множество, V ={j}, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути µ = (i, j, 1). Поэтому
i ÎN, j Î {2, 3,…, n}, j ≠ i. (1)
Предположим, что значения функции В(i, V ) для всех i ÎN\{1} и всех возможных k-элементных (k < n – 1) множеств V уже вычислены. Тогда значение В(i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле
(2)
Уравнения (1)–(2) – рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они обеспечивают реализацию обратного метода Беллмана.
Сначала, пользуясь формулой (1), определяем значения В(i, {j}):
В(2, {3}) = s23 + s31 = 5 + 15 =20
В(2, {4}) = s24 + s41 = 12 + 4 =16
В(2, {5}) = s25 + s51 = 19 + 17 =36
В(2, {6}) = s26 + s61 = 9 + 16 =25
В(3, {2}) = s32 + s21 = 7 + 12 =19
В(3, {4}) = s34 + s41 = 8 + 4 =12
В(3, {5}) = s35 + s51 = ∞ + 17 =∞
В(3, {6}) = s36 + s61 = 12 + 16 =28
В(4, {2}) = s42 + s21 = 12 + 12 =24
В(4, {3}) = s43 + s31 = 11 + 15 =26
В(4, {5}) = s45 + s51 = 3 + 17 =20
В(4, {6}) = s46 + s61 = 11 + 16 =27
В(5, {2}) = s52 + s21 = 3 + 12 =15
В(5, {3}) = s53 + s31 = 12 + 15 =27
В(5, {4}) = s54 + s41 = 18 + 4 =22
В(5, {6}) = s56 + s61 = 16 + 16 =32
В(6, {2}) = s62 + s21 = 8 + 12 =20
В(6, {3}) = s63 + s31 = 13 + 15 =28
В(6, {4}) = s64 + s41 = 11 + 4 =15
В(6, {5}) = s65 + s51 = 19 + 17 =36
Далее по формуле (2) последовательно получаем :
В(4, {2, 3}) = min [s42 + B(2,{3}); s43 + B(3,{2})] = min(12 + 20; 11 + 19)=30 /432;
В(5, {2, 3}) = min [s52 + B(2,{3}); s53 + B(3,{2})] = min(3 + 20; 12 + 19)=23 /523;
В(6, {2, 3}) = min [s62 + B(2,{3}); s63 + B(3,{2})] = min(8 + 20; 13 + 19) =28 /623 ;
В(3, {2, 4}) = min [s32 + B(2,{4}); s34 + B(4,{2})] = min(7 + 16; 8 + 24)=23 /324;
В(5, {2, 4}) = min [s52 + B(2,{4}); s54 + B(4,{2})] = min(3 + 16; 18 + 24)=19 /524;
В(6, {2, 4}) = min [s62 + B(2,{4}); s64 + B(4,{2})] = min(8 + 16; 11 + 24)=24 /624;
В(3, {2, 5}) = min [s32 + B(2,{5}); s35 + B(5,{2})] = min(7 + 36; ∞ + 15)=43 /325;
В(4, {2, 5}) = min [s42 + B(2,{5}); s45 + B(5,{2})] = min(12 + 36; 3 + 15)=18 /452;
В(6, {2, 5}) = min [s62 + B(2,{5}); s65 + B(5,{2})] = min(3 + 36; 19 + 15)=34 /652;
В(3, {2, 6}) = min [s32 + B(2,{6}); s36 + B(6,{2})] = min(7 + 25; 12 + 20)=32 /(326 или 362);
В(4, {2, 6}) = min [s42 + B(2,{6}); s46 + B(6,{2})] = min(12 + 25; 11 + 20)=31 /462;
В(5, {2, 6}) = min [s52 + B(2,{6}); s56 + B(6,{2})] = min(3 + 25 ; 16 + 20)=28 /526;
В(2, {3, 4}) = min [s23 + B(3,{4}); s24 + B(4,{3})] = min(5 + 12; 12 + 26)=17 /234;
В(5, {3, 4}) = min [s53 + B(3,{4}); s54 + B(4,{3})] = min(12 + 12;18 + 26)=24 /534;
В(6, {3, 4}) = min [s63 + B(3,{4}); s64 + B(4,{3})] = min(13 +12; 11 + 26)=25 /634;
В(2, {3, 5}) = min [s23 + B(3,{5}); s25 + B(5,{3})] = min(5 + ∞; 19 + 27)=46 /253;
В(4, {3, 5}) = min [s43 + B(3,{5}); s45 + B(5,{3})] = min(11 + ∞; 3 + 27)=30 /453;
В(6, {3, 5}) = min [s63 + B(3,{5}); s65 + B(5,{3})] = min(13 + ∞; 19 + 27)=46 /653;
В(2, {3, 6}) = min [s23 + B(3,{6}); s26 + B(6,{3})] = min(5 + 28; 9 + 28)=33 /236;
В(4, {3, 6}) = min [s43 + B(3,{6}); s46 + B(6,{3})] = min(11 + 28; 11 + 28)=39 /(436 или 463);
В(5, {3, 6}) = min [s53 + B(3,{6}); s56 + B(6,{3})] = min(12 + 28; 16 + 28)=40 / 536;
В(2, {4, 5}) = min [s24 + B(4,{5}); s25 + B(5,{4})] = min(12 + 20; 19 + 22)=32 /245;
В(3, {4, 5}) = min [s34 + B(4,{5}); s35 + B(5,{4})] = min(8 + 20; ∞ + 22)=28 /345;
В(6, {4, 5}) = min [s64 + B(4,{5}); s65 + B(5,{4})] = min(11 + 20; 19 + 22)=31 /645;
В(2, {4, 6}) = min [s24 + B(4,{6}); s26 + B(6,{4})] = min(12 + 27; 9 + 15)=24 /264;
В(3, {4, 6}) = min [s34 + B(4,{6}); s36 + B(6,{4})] = min(8 + 27; 12 + 15)=27 /364;
В(5, {4, 6}) = min [s54 + B(4,{6}); s56 + B(6,{4})] = min(18 + 27; 16 + 15)=31 /564;
В(2, {5, 6}) = min [s25 + B(5,{6}); s26 + B(6,{5})] = min(19 + 32; 9 + 36)=45 /265;
В(3, {5, 6}) = min [s35 + B(5,{6}); s36 + B(6,{5})] = min(∞ + 32; 12 + 36)=48 /365;
В(4, {5, 6}) = min [s45 + B(5,{6}); s46 + B(6,{5})] = min(3+ 32; 11 + 36)=35 /456;
В конце после знака «/» указана последовательность, на которой при подсчете реализуется указанный минимум.
Выполняем по формуле (2) следующий шаг:
В(5, {2,3,4}) = min [s52 + B(2,{3,4}); s53 + B(3,{2,4}); s54 + B(4,{2,3})] =
= min(3+17 /234 ; 12+23 /324 ; 18+30 /432)=20 /5234;
В(6, {2,3,4}) = min [s62 + B(2,{3,4}); s63 + B(3,{2,4}); s64 + B(4,{2,3})] =
= min(8+17 /234 ; 13+23 /324; 11+30 /432 )=25 /6234;
В(4, {2,3,5}) = min [s42 + B(2,{3,5}); s43 + B(3,{2,5}); s45 + B(5,{2,3})] =
= min(12+46 /253; 11+43 /325; 3+23 /523)=26 /4523;
В(6, {2,3,5}) = min [s62 + B(2,{3,5}); s63 + B(3,{2,5}); s65 + B(5,{2,3})] =
= min(8+46 /253; 13+43 /325; 19+23 /523)=42 /6523;
В(4, {2,3,6}) = min [s42 + B(2,{3,6}); s43 + B(3,{2,6}); s46 + B(6,{2,3})] =
= min(12+33 /236; 11+32 /(326 или 362); 11+28 /623)=39 /4623;
В(5, {2,3,6}) = min [s52 + B(2,{3,6}); s53 + B(3,{2,6}); s56 + B(6,{2,3})] =
= min(3+33 /236; 12+32 /(326 или 362); 16+28 /623)=36 /5236;
В(3, {2,4,5}) = min [s32 + B(2,{4,5}); s34 + B(4,{2,5}); s35 + B(5,{2,4})] =
= min(7+32 /245; 8+18 /452; ∞+19 /524)=26 /3452;
В(6, {2,4,5}) = min [s62 + B(2,{4,5}); s64 + B(4,{2,5}); s65 + B(5,{2,4})] =
= min(8+32 /245; 11+18 /452; 19+19 /524)=29 /6452;
В(3, {2,4,6}) = min [s32 + B(2,{4,6}); s34 + B(4,{2,6}); s36 + B(6,{2,4})] =
= min(7+24 /264; 8+31 /462; 12+24 /624)=31 /3264;
В(5, {2,4,6}) = min [s52 + B(2,{4,6}); s54 + B(4,{2,6}); s56 + B(6,{2,4})] =
= min(3+24 /264; 18+31 /462; 16+24 /624)=27 /5264;
В(3, {2,5,6}) = min [s32 + B(2,{5,6}); s35 + B(5,{2,6}); s36 + B(6,{2,5})] =
= min(7+45 /265; ∞+28 /526; 12+34 /652)=46 /3652;
В(4, {2,5,6}) = min [s42 + B(2,{5,6}); s45 + B(5,{2,6}); s46 + B(6,{2,5})] =
= min(12+45 /265; 3+28 /526; 11+34 /652)=31 /4526;
В(2, {3,4,5}) = min [s23 + B(3,{4,5}); s24 + B(4,{3,5}); s25 + B(5,{3,4})] =
= min(5+28 /345; 12+30 /453; 19+24 /534)=33 /2345;
В(6, {3,4,5}) = min [s63 + B(3,{4,5}); s64 + B(4,{3,5}); s65 + B(5,{3,4})] =
= min(13+28 /345; 11+30 /453; 19+24 /534)=41 /(6345 или 6453);
В(2, {3,4,6}) = min [s23 + B(3,{4,6}); s24 + B(4,{3,6}); s26 + B(6,{3,4})] =
= min(5+27 /364; 12+39 /(436 или 463); 9+25 /634)=32 /2364;
В(5, {3,4,6}) = min [s53 + B(3,{4,6}); s54 + B(4,{3,6}); s56 + B(6,{3,4})] =
= min(12+27 /364; 18+39 /(436 или 463); 16+25 /634)=39 /5364;
В(2, {3,5,6}) = min [s23 + B(3,{5,6}); s25 + B(5,{3,6}); s26 + B(6,{3,5})] =
= min(5+48 /365; 19+40 / 536; 9+46 /653)=53 /2365;
В(4, {3,5,6}) = min [s43 + B(3,{5,6}); s45 + B(5,{3,6}); s46 + B(6,{3,5})] =
= min(11+48 /365; 3+40 / 536; 11+46 /653)=43 /4536;
В(2, {4,5,6}) = min [s24 + B(4,{5,6}); s25 + B(5,{4,6}); s26 + B(6,{4,5})] =
= min(12+35 /456; 19+31 /564; 9+31 /645)=40 /2645;
В(3, {4,5,6}) = min [s34 + B(4,{5,6}); s35 + B(5,{4,6}); s36 + B(6,{4,5})] =
= min(8+35 /456; ∞+31 /564; 12+31 /645)=43 /(3456 или 3645);
Выполняем по формуле (2) следующий шаг:
В(6,{2,3,4,5})=min [s62+B(2,{3,4,5}); s63+B(3,{2,4,5});
s64+B(4,{2,3,5});s65+B(5,{2,3,
Информация о работе Контрольная работа по дисциплине "Программирование"