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