Основы оптимизационных методов
КОНТРОЛЬНАЯ РАБОТА
Вариант-34
Задача 1. Решить транспортную задачу по критерию стоимости.
Матрица цен: Емкость АТС: Потребность районов:
Решение:
Данная транспортная задача имеет открытый тип, так как суммарный запас (предложение) емкостей АТС больше суммарных потребностей районов:
Чтобы привести задачу к закрытому типу, вводим фиктивного потребителя B6, потребность которого составляет 269-99=70, а стоимость перевозки равна 0.
Обозначим через - объем электроэнергии, переданной от поставщика (станции) потребителю (району) .
Тогда система ограничений примет вид:
Наша задача - составить такую схему распределения (из станции, в какой район и сколько единиц поставлять), чтобы все потребности были удовлетворены и общая стоимость всех распределений была минимальной (найти оптимальный план).
Тогда целевую функцию можно записать:
Условие неотрицательности объемов перевозок:
1) Найдем методом минимального элемента допустимый план перевозок:
Потребители Поставщики |
B1 |
B2 |
B3 |
B4 |
B5 |
B6* |
Запасы |
A1 |
7 - |
12 - |
2 38 |
14 - |
2 - |
0 - |
38 |
A2 |
19 - |
23 - |
8 4 |
13 7 |
13 11 |
0 16 |
38 |
A3 |
14 - |
8 - |
24 - |
8 47 |
23 - |
0 - |
47 |
A4 |
8 47 |
6 - |
8 - |
12 - |
9 - |
0 - |
47 |
A5 |
17 18 |
4 27 |
32 - |
13 - |
19 |
0 54 |
99 |
Потребности |
65 |
27 |
42 |
54 |
11 |
70 |
Загрузку начинаем с клетки, которой соответствует наименьший тариф : транспортный гамильтонов контур программирование
Такой клеткой является клетка (1,3), для которой.
Помещаем в клетку. Из дальнейшего рассмотрения исключаем первую строку (запасы на станции А1 закончились).
Снова ищем клетку с минимальным тарифом: это клетка (5, 2), для которой с=4. Помещаем в нее. Исключаем второй столбец. И т. д.
В результате полного распределения, получаем исходное опорное решение:
,
F(x) = 2*38 + 8*4 + 13*7 + 13*11 + 0*16 + 8*47 + 8*47 + 17*18 + 4*27 + 0*54 = 1508
2) Проверим план X0 на оптимальность методом потенциалов:
Поставщику ставим в соответствие потенциалы, а потребителю и определяем их.
Назначаем, и находим все остальные потенциалы из условия, что для занятых клеток должны выполняться условия:
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
U2 + v5 = 13; 6 + v5 = 13; v5 = 7
U2 + v6 = 0; 6 + v6 = 0; v6 = -6
U5 + v6 = 0; -6 + u5 = 0; u5 = 6
U5 + v1 = 17; 6 + v1 = 17; v1 = 11
U4 + v1 = 8; 11 + u4 = 8; u4 = -3
U5 + v2 = 4; 6 + v2 = 4; v2 = -2
V1=11 |
V2=-2 |
V3=2 |
V4=7 |
V5=7 |
V6=-6 | |
U1=0 |
7 |
12 |
2 38 |
14 |
2 |
0 |
U2=6 |
19 |
23 |
8[4 |
13 7 |
13 [11 |
0 16 |
U3=1 |
14 |
8 |
24 |
8 47 |
23 |
0 |
U4=-3 |
8 47 |
6 |
8 |
12 |
9 |
0 |
U5=6 |
17 18 |
4 27 |
32 |
13 |
19 |
0 54 |
Для всех свободных клеток находим оценки из соотношения
.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vI > cIj
- (1;1): 0 + 11 > 7; ?11 = 0 + 11 - 7 = 4 (1;5): 0 + 7 > 2; ?15 = 0 + 7 - 2 = 5
Max(4,5) = 5
Выбираем максимальную оценку свободной клетки (1;5): 2
Для этого в перспективную клетку (1;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
12 |
2 38 [-] |
14 |
2 [+] |
0 |
38 |
2 |
19 |
23 |
8 4[+] |
13 7 |
13 11[-] |
0 16 |
38 |
3 |
14 |
8 |
24 |
8 [47 |
23 |
0 |
47 |
4 |
8 47 |
6 |
8 |
12 |
9 |
0 |
47 |
5 |
17 18 |
4 27 |
32 |
13 |
19 |
0 54 |
99 |
Потребности |
65 |
27 |
42 |
54 |
11 |
70 |
Цикл приведен в таблице (1,5; 1,3; 2,3; 2,5; ).
Из хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 5) = 11. Прибавляем 11 к значениям, стоящих в плюсовых клетках и вычитаем 11 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
12 |
2 27 |
14 |
2 11 |
0 |
38 |
2 |
19 |
23 |
8 15 |
13 7 |
13 |
0 16 |
38 |
3 |
14 |
8 |
24 |
8 47 |
23 |
0 |
47 |
4 |
8 47 |
6 |
8 |
12 |
9 |
0 |
47 |
5 |
17 18 |
4 27 |
32 |
13 |
19 |
0 54 |
99 |
Потребности |
65 |
27 |
42 |
54 |
11 |
70 |
Проверим оптимальность опорного плана. Находим потенциалы и оценки:
V1=11 |
V2=-2 |
V3=2 |
V4=7 |
V5=2 |
V6=-6 | |
U1=0 |
7 |
12 |
2 27 |
14 |
2 11 |
0 |
U2=6 |
19 |
23 |
8 15 |
13 7 |
13 |
0 16 |
U3=1 |
14 |
8 |
24 |
8 47 |
23 |
0 |
U4=-3 |
8 47 |
6 |
8 |
12 |
9 |
0 |
U5=6 |
17[18] |
4[27] |
32 |
13 |
19 |
0[54] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vI > cIj
(1;1): 0 + 11 > 7; ?11 = 0 + 11 - 7 = 4
Выбираем максимальную оценку свободной клетки (1;1): 7
Для этого в перспективную клетку (1;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 + |
12 |
2 27 - |
14 |
2 11 |
0 |
38 |
2 |
19 |
23 |
8 15 + |
13 7 |
13 |
0 16 - |
38 |
3 |
14 |
8 |
24 |
8 47 |
23 |
0 |
47 |
4 |
8 47 |
6 |
8 |
12 |
9 |
0 |
47 |
5 |
17[18] - |
4[27] |
32 |
13 |
19 |
0[54] + |
99 |
Потребности |
65 |
27 |
42 |
54 |
11 |
70 |
Цикл приведен в таблице (1,1; 1,3; 2,3; 2,6; 5,6; 5,1; ).
В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 16 |
12 |
2 11 |
14 |
2 11 |
0 |
38 |
2 |
19 |
23 |
8 31 |
13 7 |
13 |
0 |
38 |
3 |
14 |
8 |
24 |
8 47 |
23 |
0 |
47 |
4 |
8 47 |
6 |
8 |
12 |
9 |
0 |
47 |
5 |
17 2 |
4 27 |
32 |
13 |
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
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,4})] = min(8+33 /2345; 13+26 /3452; 11+26 /4523; 19+20 /5234)=37 /64523;
В(3,{2,4,5,6})=min [s32+B(2,{4,5,6}); s34+B(4,{2,5,6}); s35+B(5,{2,4,6});s36+B(6,{2,4,5})] = min(7+40 /2645; 8+31 /4526; ?+27 /5264; 12+29 /6452)=39 /34526;
В(2,{3,4,5,6})=min [s23+B(3,{4,5,6}); s24+B(4,{3,5,6}); s25+B(5,{3,4,6});s26+B(6,{3,4,5})] = min(5+43/(3456 или 3645);12+43 /4536;19+39/5364; 9+41/(6345 или 6453))=48/(23456 или 23645);
Итак, все шаги метода динамического программирования выполнены: оптимальное значение критерия равно 37.
Оптимальный маршрут следующий:
1 ® 6 ® 5 ® 2 ® 3® 1.
Длина маршрута: 37+s31=37+15=52
Ответ: 1 > 6 > 5 > 2 > 3> 1, S=52
Похожие статьи
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Транспортная задача - Основы экономико-математического моделирования
На трех складах А 1, А 2 и А 3 хранится А 1=100, А 2=200, а 3=60+10 N единиц одного и того же груза, соответственно. Этот груз требуется доставить трем...
-
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из...
-
Задача №1 (Вариант 12) - Экономико-математические методы и модели в логистике
Условие задачи Производственная компания может закупить сырье для четырех своих заводов у трех поставщиков. Стоимость перевозки сырья в расчете на одну...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Метод наименьших квадратов - Основы научных исследований
Пусть проведен однофакторный эксперимент, в котором исследована зависимость У от Х . Установлено, что основные предпосылки регрессионного анализа...
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
СУЩНОСТЬ СТАТИСТИЧЕСКИХ МЕТОДОВ ПРОГНОЗИРОВАНИЯ Динамический или временной ряд представляет собой совокупность численных данных, характеризующих...
-
Многокритериальный оптимизация нейронный аппроксимация Общая схема рассматриваемого метода является итерационной и состоит из следующих основных этапов....
-
Методы изучения связи качественных признаков - Основы эконометрики
При наличии соотношения между вариацией качественных признаков говорят об их ассоциации, взаимосвязанности. Для оценки связи в этом случае используют ряд...
-
Собственно-корреляционные параметрические методы изучения связи - Основы эконометрики
Измерение тесноты и направления связи является важной задачей изучения и количественного измерения взаимосвязи социально-экономических явлений. Оценка...
-
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Методы непараметрической статистики - Основы теории систем и системного анализа
Использование классических распределений случайных величин обычно называют "параметрической статистикой" - мы делаем предположение о том, что...
-
Покупательский спрос математический программирование Математическое программирование -- область математики, разрабатывающая теорию и численные методы...
-
Введение, Графический метод решения задач линейного программирования - Методы оптимальных решений
Задача линейного программирования может быть решена графическим методом, достоинство которого в его простоте и наглядности, но существенным недостатком...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Метод Гомори последовательных отсечений - Математическое моделирование экономических процессов
При решении многих задач (планирование мелкосерийного производства, распределение кораблей по путям сообщения, выработка суждений типа "да-нет" и т. п.)...
-
Первая симплексная таблица - Методы оптимальных решений
Величины Свободные члены Х1 Х2 Х3 Х4 F 0 - 60 - 70 - 120 - 130 У1 16 1 4 1 1 У2 110 6 5 4 3 У3 100 4 6 10 13 Проверка на допустимость и оптимальность...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Введение - Метод представления знаний в интеллектуальных системах поддержки экспертных решений
Во многих областях человеческой деятельности - науке, технике, бизнесе - широко распространены проблемные ситуации, которые могут быть описаны исходными...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Используется адаптивная нейро-нечеткая система вывода ANFIS, функционально эквивалентная системе нечеткого вывода Сугено. Вывод осуществляется за два...
-
Задачи и методы качественного анализа - Основы аналитической химии
Обнаружение или, как иногда говорят, "открытие" отдельных элементов или ионов, входящих в состав веществ - это задачи качественного анализа. Качественный...
-
Бизнес документирование организационный ценность Рассмотрим деятельность предприятия с точки зрения цепочек создания ценности. Для этого необходимо...
-
Методы отбора выборок - Основы научных исследований
Известны три метода отборок выборок: случайный, систематический и комбинированный. В результате случайного отбора получается случайная выборка. Выборка...
-
1. В результате линейной комбинации две атомные орбитали (АО) формируют две молекулярные орбитали (МО) - связывающую, энергия которой ниже, чем энергия...
-
Причинность, регрессия, корреляция Исследование объективно существующих зависимостей и взаимосвязей между явлениями и процессами - важнейшая задача...
-
МЕТОДЫ ОТБОРА СПЕЦИАЛИСТОВ В ЭКСПЕРТНУЮ ГРУППУ - Основы прогнозирования
Проведение экспертизы начинается с создания специальной группы специалистов-организаторов опроса. Задачами группы являются выбор цели экспертизы,...
-
Легирование стали повышает ее антикоррозионные свойства. Например, совершенную стойкость к атмосферной коррозии показывают нержавеющие легированные...
-
В этом методе сравнивают степени окисления атомов в исходных веществах и в продуктах реакции, при этом руководствуемся правилом: число электронов,...
-
Указанные выше основные направления реформирования сферы ЖКХ позволяют перейти к раскрытию существа ряда первоочередных по значимости факторов,...
-
Парная регрессия на основе метода наименьших квадратов и метода группировок - Основы эконометрики
Парная регрессия Характеризует связь между двумя признаками: результативным и факторным. Аналитически связь между ними описывается уравнениями: Прямой...
-
Научный метод. Практические и теоретические аспекты - Основы естественно-научных знаний
Одним из основных методов естествознания является научный метод познания, включающий в себя определенный ряд этапов изучения объектов: наблюдение,...
-
Метод максимального правдоподобия - Основы научных исследований
Разработан Р. Фишером. Пусть Х 1 ,х 2 ...х N - выборка из генеральной совокупности случайной величины Х с функцией плотности вероятности Р(х, и),...
Основы оптимизационных методов