Решение задач транспортного типа методами северо-западного угла, минимального элемента, двойного предпочтения, потенциалов и венгерским методом

Страницы работы

Содержание работы

Методы решения задач транспортного типа

Задание

30

2

5

6

15

16

5

29

9

5

7

15

16

24

14

6

26

14

13

28

4

25

8

15

6

6

13

20

15

60=60

Решить методами северо-западного угла, минимального элемента, двойного предпочтения, потенциалов и венгерским методом.

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

Начиная  с левого верхнего угла, берем максимально возможное значение элемента  и двигаемся по диагонали, заполняя ячейки.

30

6

2

6

5

4

6

0

15

0

16

5

0

29

0

9

9

5

6

7

0

15

16

0

24

0

14

0

6

14

26

0

14

13

0

28

0

4

0

25

0

8

15

15

6

6

13

20

15

60=60

В верхнюю левую ячейку ставим максимально возможное значение элемента – 6. Обнуляем оставшиеся элементы столбца, т. к. их заполнить уже нельзя. Во вторую ячейку первой строки ставим максимально возможное значение – 6 и обнуляем оставшиеся элементы столбца . В следующую ячейку строки ставим максимально возможное значение – 4 и обнуляем оставшиеся элементы строки. В третью ячейку второй строки ставим – 9 и обнуляем оставшиеся элементы столбца. В четвертую ячейку втрой строки ставим – 6 и обнуляем оставшиеся элементы строки. В четвертую ячейку третьей строки ставим – 14 и обнуляем оставшиеся элементы строки. В пятую ячейку четвертой строки ставим максимальное значение =15  Считаем Z.

Z = 6*30+6*2+4*5+9*9+6*5+14*6+15*8=527

Метод минимального элемента

Выбираем в строках минимальные элементы и ставим в них максимально возможные значения. В ячейки отмеченные «*» ставим максимально возможные значения, отдавая предпочтение минимальным стоимостям. Обнуляем ячейки в заполненных строках и столбцах. Оставшиеся ячейки заполняем максимально возможными значения, отдавая предпочтение минимальным стоимостям и обнуляем оставшиеся ячейки.

30

0

2*

6

5

0

6

0

15

10

16

5*

6

29

0

9

0

5*

9

7

0

15

16

0

24

0

14

0

6*

11

26

3

14

13

0

28

0

4*

13

25

0

8

2

15

6

6

13

20

15

60=60

 Считаем Z.

Z=6*2+10*15+6*5+9*5+11*6+3*26+13*4+2*8=449

Метод двойного предпочтения

Выбираем в строках и столбцах минимальные элементы и отмечаем их «*». В ячейки отмеченные двумя «*» ставим максимально возможные значения. В ячейки с одной «*» ставим максимально возможные значения, отдавая предпочтение минимальным стоимостям или обнуляем их, если строка или столбец уже заполнены.

Обнуляем заполненные строки и столбцы.

Оставшиеся ячейки заполняем максимально возможными значения, отдавая предпочтение минимальным стоимостям и обнуляем оставшиеся ячейки.

30

0

2**

6

5

0

6

0

15

10

16

5**

6

29

0

9

0

5**

9

7*

0

15

16

0

24

0

14

0

6*

11

26

3

14

13

0

28

0

4**

13

25

0

8

2

15

6

6

13

20

15

60=60

Считаем Z.

Z=6*2+10*15+6*5+9*5+11*6+3*26+13*4+2*8=449

Метод потенциалов

Расставляем значения элементов по методу северо-западного угла. Находим потенциалы для каждого столбца и строки по правилу: Cij=ui+vj.

V1=30

V2=2

V3=5

V4=1

V5=8

u1= 0

30

6

2

6

5

4

6

0

15

0

16

U2=4

5

0

29

0

9

9

5

6

7

0

15

U3=5

16

0

24

0

14

0

6

14

26

0

14

U4=0

13

0

28

0

4

0

25

0

8

15

15

6

6

13

20

15

60=60

U1=0, т. к. первая строка наиболее заполнена. Рассматриваем незаполненные ячейки и отмечаем их, если Cij < ui+vj.

V1=30

V2=2

V3=5

V4=1

V5=8

u1= 0

30

6

2

6

5

4

6

0

15

0

16

U2=4

5

0

29

0

9

9

5

6

7

0

15

U3=5

16

0

24

0

14

0

6

14

26

0

14

U4=0

13

0

28

0

4

0

25

0

8

15

15

6

6

13

20

15

60=60

Рассматриваем незаполненные ячейки и отмечаем их в соответствии с правилом:

Cij ≥ ui+vj.

Переносим 6 элементов в соответствии с направлением стрелок, для оптимизации заполнения таблицы. И рассчитываем новые потенциалы. Рассматриваем незаполненные ячейки и отмечаем их, если Cij < ui+vj.

Похожие материалы

Информация о работе