Транспортная задача

Автор работы: Пользователь скрыл имя, 31 Мая 2012 в 15:03, задача

Краткое описание

метод северо-зарадного угла

Вложенные файлы: 1 файл

Вариант 10 расчетка4.docx

— 31.39 Кб (Скачать файл)

Вариант 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*3+70*2=375+180+30+275+120+140=1120

Найдём потенциалы 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

 

 

Вычислим разности для  свободных клеток:

1313-(u1+v3)=3-(0+7)=-4

1414-(u1+v4)=4-(0+6)=-2

2121-(u2+v1)=3-(-2+5)=0

2424-(u2+v4)=5-(-2+6)=1

3131-(u3+v1)=1-(-4+5)=0

3232-(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

 

 

Вычислим разности для  свободных клеток:

1212-(u1+v2)=4-(0+(-0))=4

1414-(u1+v4)=4-(0+2)=2

2121-(u2+v1)=3-(2+5)=-4

2424-(u2+v4)=5-(2+2)=1

3131-(u3+v1)=1-(-0+5)=-4

3232-(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

 

 

Вычислим разности для  свободных клеток:

1212-(u1+v2)=4-(0+4)=0

1414-(u1+v4)=4-(0+2)=2

2323-(u2+v3)=5-(-2+3)=4

2424-(u2+v4)=5-(-2+2)=5

3131-(u3+v1)=1-(-0+5)=-4

3232-(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

 

 

Вычислим разности для  свободных клеток:

1212-(u1+v2)=4-(0+4)=0

1414-(u1+v4)=4-(0+6)=-2

2323-(u2+v3)=5-(-2+3)=4

2424-(u2+v4)=5-(-2+6)=1

3232-(u3+v2)=6-(-4+4)=6

3333-(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

 

Информация о работе Транспортная задача