Автор работы: Пользователь скрыл имя, 31 Мая 2012 в 15:03, задача
метод северо-зарадного угла
Вариант 10
В1 |
В2 |
В3 |
В4 |
Запасы | |
А1 |
5 |
4 |
3 |
4 |
120 |
А2 |
3 |
2 |
5 |
5 |
70 |
А3 |
1 |
6 |
3 |
2 |
110 |
потребности |
75 |
60 |
95 |
70 |
Задача закрытая (сбалансированная)
В1 |
В2 |
В3 |
В4 |
Запасы | |
А1 |
Х 5 |
Х 4 |
Х 3 |
Х 4 |
120 |
А2 |
Х 3 |
Х 2 |
Х 5 |
Х 5 |
70 |
А3 |
Х 1 |
Х 6 |
Х 3 |
Х 2 |
110 |
потребности |
75 |
60 |
95 |
70 |
Найдём первоначальный план
перевозок методом северо-
В1 |
В2 |
В3 |
В4 |
Запасы | |
А1 |
75 5 |
45 4 |
Х 3 |
Х 4 |
120 |
А2 |
Х 3 |
15 2 |
55 5 |
Х 5 |
70 |
А3 |
Х 1 |
Х 6 |
40 3 |
70 2 |
110 |
потребности |
75 |
60 |
95 |
70 |
F(x0)=75*5+45*4+15*2+55*5+40*
Найдём потенциалы ui+vj=cij. ui=0
u1+v1=5
u1+v2=4
u2+v2=2
u2+v3=5
u3+v3=3
u3+v4=6
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
75 5 |
45 4 |
Х 3 |
Х 4 |
0 |
А2 |
Х 3 |
15 2 |
55 5 |
Х 5 |
-2 |
А3 |
Х 1 |
Х 6 |
40 3 |
70 2 |
-4 |
V |
5 |
4 |
7 |
6 |
Вычислим разности для свободных клеток:
∆13=с13-(u1+v3)=3-(0+7)=-4
∆14=с14-(u1+v4)=4-(0+6)=-2
∆21=с21-(u2+v1)=3-(-2+5)=0
∆24=с24-(u2+v4)=5-(-2+6)=1
∆31=с31-(u3+v1)=1-(-4+5)=0
∆32=с32-(u3+v2)=6-(-4+4)=6
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
75 5 |
45 4 |
-4 Х 3 |
-2 Х 4 |
0 |
А2 |
0 Х 3 |
15 2 |
55 5 |
1 Х 5 |
-2 |
А3 |
0 Х 1 |
6 Х 6 |
40 3 |
70 2 |
-4 |
V |
5 |
4 |
7 |
6 |
Опорная клетка (1;3) [+45] далее (1;2) [-45], (2;2) [+45], (2;3) [-45]
В1 |
В2 |
В3 |
В4 |
Запасы | |
А1 |
75 5 |
Х 4 |
45 3 |
Х 4 |
120 |
А2 |
Х 3 |
60 2 |
10 5 |
Х 5 |
70 |
А3 |
Х 1 |
Х 6 |
40 3 |
70 2 |
110 |
потребности |
75 |
60 |
95 |
70 |
Найдём потенциалы ui+vj=cij. ui=0
u1+v1=5
u1+v3=0 3
u2+v2=2
u2+v3=5
u3+v3=3
u3+v4=2
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
75 5 |
Х 4 |
45 3 |
Х 4 |
0 |
А2 |
Х 3 |
60 2 |
10 5 |
Х 5 |
-2 |
А3 |
Х 1 |
Х 6 |
40 3 |
70 2 |
-0 |
V |
5 |
-0 |
3 |
2 |
Вычислим разности для свободных клеток:
∆12=с12-(u1+v2)=4-(0+(-0))=4
∆14=с14-(u1+v4)=4-(0+2)=2
∆21=с21-(u2+v1)=3-(2+5)=-4
∆24=с24-(u2+v4)=5-(2+2)=1
∆31=с31-(u3+v1)=1-(-0+5)=-4
∆32=с32-(u3+v2)=6-(-0+(-0))=46
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
75 5 |
4 Х 4 |
45 3 |
2 Х 4 |
0 |
А2 |
-4 Х 3 |
60 2 |
10 5 |
1 Х 5 |
-2 |
А3 |
-4 Х 1 |
6 Х 6 |
40 3 |
70 2 |
-0 |
V |
5 |
-0 |
3 |
2 |
Опорная клетка (2;1) [+10] далее (2;3) [-10], (1;3) [+10], (1;1) [-10]
В1 |
В2 |
В3 |
В4 |
Запасы | |
А1 |
60 5 |
Х 4 |
55 3 |
Х 4 |
120 |
А2 |
10 3 |
60 2 |
Х 5 |
Х 5 |
70 |
А3 |
Х 1 |
Х 6 |
40 3 |
70 2 |
110 |
потребности |
75 |
60 |
95 |
70 |
Найдём потенциалы ui+vj=cij. ui=0
u1+v1=5
u1+v3=3
u2+v1=3
u2+v2=2
u3+v3=3
u3+v4=2
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
60 5 |
Х 4 |
55 3 |
Х 4 |
0 |
А2 |
10 3 |
60 2 |
Х 5 |
Х 5 |
-2 |
А3 |
Х 1 |
Х 6 |
40 3 |
70 2 |
-0 |
V |
5 |
4 |
3 |
2 |
Вычислим разности для свободных клеток:
∆12=с12-(u1+v2)=4-(0+4)=0
∆14=с14-(u1+v4)=4-(0+2)=2
∆23=с23-(u2+v3)=5-(-2+3)=4
∆24=с24-(u2+v4)=5-(-2+2)=5
∆31=с31-(u3+v1)=1-(-0+5)=-4
∆32=с32-(u3+v2)=6-(-0+4)=2
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
60 5 |
0 Х 4 |
55 3 |
2 Х 4 |
0 |
А2 |
10 3 |
60 2 |
4 Х 5 |
5 Х 5 |
-2 |
А3 |
-4 Х 1 |
2 Х 6 |
40 3 |
70 2 |
-0 |
V |
5 |
4 |
3 |
2 |
Опорная клетка (3;1) [+40] далее (3;3) [-40], (1;3) [+40], (1;1) [-40]
В1 |
В2 |
В3 |
В4 |
Запасы | |
А1 |
25 5 |
Х 4 |
95 3 |
Х 4 |
120 |
А2 |
10 3 |
60 2 |
Х 5 |
Х 5 |
70 |
А3 |
40 1 |
Х 6 |
Х 3 |
70 2 |
110 |
потребности |
75 |
60 |
95 |
70 |
Найдём потенциалы ui+vj=cij. ui=0
u1+v1=5
u1+v3=3
u2+v1=3
u2+v2=2
u3+v1=1
u3+v4=2
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
25 5 |
Х 4 |
95 3 |
Х 4 |
0 |
А2 |
10 3 |
60 2 |
Х 5 |
Х 5 |
-2 |
А3 |
40 1 |
Х 6 |
Х 3 |
70 2 |
-4 |
V |
5 |
4 |
3 |
6 |
Вычислим разности для свободных клеток:
∆12=с12-(u1+v2)=4-(0+4)=0
∆14=с14-(u1+v4)=4-(0+6)=-2
∆23=с23-(u2+v3)=5-(-2+3)=4
∆24=с24-(u2+v4)=5-(-2+6)=1
∆32=с32-(u3+v2)=6-(-4+4)=6
∆33=с33-(u3+v3)=3-(-4+3)=4
В1 |
В2 |
В3 |
В4 |
U | |
А1 |
25 5 |
0 Х 4 |
95 3 |
-2 Х 4 |
0 |
А2 |
10 3 |
60 2 |
4 Х 5 |
1 Х 5 |
-2 |
А3 |
40 1 |
6 Х 6 |
4 Х 3 |
70 2 |
-4 |
V |
5 |
4 |
3 |
6 |