Другие предметы \ Исследование операций и методы оптимизации

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

V1=1

V2=2

V3=5

V4=6

V5=8

u1= 0

30

0

2

6

5

4

6

6

15

0

16

U2=4

5

6

29

0

9

9

5

0

7

0

15

U3=0

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

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

V1=5

V2=2

V3=5

V4=6

V5=7

u1= 0

30

0

2

6

5

4

6

6

15

0

16

U2=0

5

6

29

0

9

0

5

0

7

9

15

U3=0

16

0

24

0

14

0

6

14

26

0

14

U4=1

13

0

28

0

4

9

25

0

8

6

15

6

6

13

20

15

60=60

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

V1=30

V2=2

V3=5

V4=7

V5=9

u1= 0

30

6

2

6

5

4

6

0

15

0

16

U2=-2

5

0

29

0

9

0

5

6

7

9

15

U3=-1

16

0

24

0

14

0

6

14

26

0

14

U4=-1

13

0

28

0

4

9

25

0

8

6

15

6

6

13

20

15

60=60

Все пустые ячейки отвечают правилу Cij ≥ ui+vj , значит найден оптимальный вариант. Считаем Z.

Z=6*30+6*2+4*5+6*5+9*7+14*6+9*4+6*8=473

Венгерский метод

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

30

0

6

5

6

15

16

10

0

6

29

9

0

9

7

15

0

16

24

14

0

11

26

14

3

13

28

0

13

25

8

15

2

6

6

13

20

15

60=60

0

0

0

0

15

Q1 = {2; 3; 10; 15}

Меняем стоимости: от стоимости закрашенных свободных ячеек отнимаем 5, а к не закрашенным – прибавляем. Записываем невязки.

25

0

6

0

0

1

10

16

10

0

6

34

4

0

9

12

15

0

21

29

9

0

11

31

14

3

18

33

0

13

30

13

15

2

6

6

13

20

15

60=60

0

0

0

0

15

Q2 = {2; 3; 10; 15}

Находим элемент, который и в столбце, и в строке минимальный, обнуляем его стоимость и заполняем ячейку максимально возможным значением.Обнуляем стоимость и заполняем первую ячейку пятого столбца максимально возможным значением. Меняем стоимости: от стоимости закрашенных свободных ячеек отнимаем 5, а к не закрашенным – прибавляем. и записываем невязки.

Скачать файл