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