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