Автор: Пользователь скрыл имя, 02 Июня 2013 в 06:22, контрольная работа
Математическая модель транспортной задачи: F = ∑∑cijxij, (1)
при условиях: ∑xij = ai, i = 1,2,…, m, (2) ∑xij = bj, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов ...
Проверим необходимое и достаточное условие разрешимости задачи.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Запасы | |
1 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
150 |
2 |
9[20] |
3[50] |
2 |
8[10] |
6 |
4[160] |
20 |
0 |
240 |
3 |
5 |
9 |
4 |
2[60] |
11 |
15 |
8 |
0 |
60 |
4 |
18 |
7 |
3 |
8 |
6 |
9[30] |
4[260] |
0 |
290 |
5 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
70 |
6 |
12 |
3 |
5 |
6[60] |
2[30] |
9 |
14 |
0[380] |
470 |
Потребности |
100 |
50 |
70 |
130 |
30 |
190 |
260 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=8 |
v2=2 |
v3=1 |
v4=7 |
v5=3 |
v6=3 |
v7=-2 |
v8=1 | |
u1=0 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
u2=1 |
9[20] |
3[50] |
2 |
8[10] |
6 |
4[160] |
20 |
0 |
u3=-5 |
5 |
9 |
4 |
2[60] |
11 |
15 |
8 |
0 |
u4=6 |
18 |
7 |
3 |
8 |
6 |
9[30] |
4[260] |
0 |
u5=-1 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
u6=-1 |
12 |
3 |
5 |
6[60] |
2[30] |
9 |
14 |
0[380] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (4;8): 0
Для этого в перспективную клетку (4;8) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Запасы | |
1 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
150 |
2 |
9[20] |
3[50] |
2 |
8[10][-] |
6 |
4[160][+] |
20 |
0 |
240 |
3 |
5 |
9 |
4 |
2[60] |
11 |
15 |
8 |
0 |
60 |
4 |
18 |
7 |
3 |
8 |
6 |
9[30][-] |
4[260] |
0[+] |
290 |
5 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
70 |
6 |
12 |
3 |
5 |
6[60][+] |
2[30] |
9 |
14 |
0[380][-] |
470 |
Потребности |
100 |
50 |
70 |
130 |
30 |
190 |
260 |
450 |
Цикл приведен в таблице (4,8; 4,6; 2,6; 2,4; 6,4; 6,8; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Запасы | |
1 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
150 |
2 |
9[20] |
3[50] |
2 |
8 |
6 |
4[170] |
20 |
0 |
240 |
3 |
5 |
9 |
4 |
2[60] |
11 |
15 |
8 |
0 |
60 |
4 |
18 |
7 |
3 |
8 |
6 |
9[20] |
4[260] |
0[10] |
290 |
5 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
70 |
6 |
12 |
3 |
5 |
6[70] |
2[30] |
9 |
14 |
0[370] |
470 |
Потребности |
100 |
50 |
70 |
130 |
30 |
190 |
260 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=8 |
v2=2 |
v3=1 |
v4=0 |
v5=-4 |
v6=3 |
v7=-2 |
v8=-6 | |
u1=0 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
u2=1 |
9[20] |
3[50] |
2 |
8 |
6 |
4[170] |
20 |
0 |
u3=2 |
5 |
9 |
4 |
2[60] |
11 |
15 |
8 |
0 |
u4=6 |
18 |
7 |
3 |
8 |
6 |
9[20] |
4[260] |
0[10] |
u5=6 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
u6=6 |
12 |
3 |
5 |
6[70] |
2[30] |
9 |
14 |
0[370] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;1): 5
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Запасы | |
1 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
150 |
2 |
9[20][-] |
3[50] |
2 |
8 |
6 |
4[170][+] |
20 |
0 |
240 |
3 |
5[+] |
9 |
4 |
2[60][-] |
11 |
15 |
8 |
0 |
60 |
4 |
18 |
7 |
3 |
8 |
6 |
9[20][-] |
4[260] |
0[10][+] |
290 |
5 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
70 |
6 |
12 |
3 |
5 |
6[70][+] |
2[30] |
9 |
14 |
0[370][-] |
470 |
Потребности |
100 |
50 |
70 |
130 |
30 |
190 |
260 |
450 |
Цикл приведен в таблице (3,1; 3,4; 6,4; 6,8; 4,8; 4,6; 2,6; 2,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Запасы | |
1 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
150 |
2 |
9 |
3[50] |
2 |
8 |
6 |
4[190] |
20 |
0 |
240 |
3 |
5[20] |
9 |
4 |
2[40] |
11 |
15 |
8 |
0 |
60 |
4 |
18 |
7 |
3 |
8 |
6 |
9[0] |
4[260] |
0[30] |
290 |
5 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
70 |
6 |
12 |
3 |
5 |
6[90] |
2[30] |
9 |
14 |
0[350] |
470 |
Потребности |
100 |
50 |
70 |
130 |
30 |
190 |
260 |
450 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=8 |
v2=7 |
v3=1 |
v4=5 |
v5=1 |
v6=8 |
v7=3 |
v8=-1 | |
u1=0 |
8[80] |
5 |
1[70] |
10 |
7 |
4 |
1 |
0 |
u2=-4 |
9 |
3[50] |
2 |
8 |
6 |
4[190] |
20 |
0 |
u3=-3 |
5[20] |
9 |
4 |
2[40] |
11 |
15 |
8 |
0 |
u4=1 |
18 |
7 |
3 |
8 |
6 |
9[0] |
4[260] |
0[30] |
u5=1 |
13 |
6 |
18 |
19 |
12 |
4 |
9 |
0[70] |
u6=1 |
12 |
3 |
5 |
6[90] |
2[30] |
9 |
14 |
0[350] |