Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
rgr_1.docx
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
241 Кб
Скачать
☆

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

1. Из всей таблицы стоимости выбирают наименьшую (минимальный элемент в строке), клетку помечают * и расставляют максимальное количество груза и обнуляют эту стоимость.

2. Затем находят элементы с минимальной стоимостью и в строке, и в столбце, помечают их. Выбирают наиболее подходящий из них, расставляют максимальное количество груза и обнуляют его стоимость. Из каждой стоимости элемента в строке и в столбце, в которых находится данный элемент, вычитают его стоимость, а к остальным элементам её прибавляют. Определяют вектор невязок Q.

3. Выполняют до тех пор, пока не расставят все грузы.

Таблица 1.5.1

 

22

 

24

 

7

 

25

 

23

 

29

24

14

 

10

 

 

 

 

1

 

21

 

30

 

10

 *

7

 

19

14

0

14

 

 

 

 

 

 

 

 

 

2

 

26

*

3

 

18

30

 

27

19

11

8

 

 

 

 

 

 

22

 *

10

 

9

 

29

 

26

 

23

27

27

 

 

 

 

 

 

 

 

 

 

18

 

16

13

 

17

18

 

19

16

16

 

 

 

 

 

 

6 

 

 

 

22

19

10

14

17

18

100

0

19

0

14

17

18

Таблица 1.5.2

 

32

 

14

 

0

 

35

 

33

 

39

24

14

 

10

 

 

 

 

0

 

11

 

40

 

20

 

17

 

29

14

0

14

 

 

 

 

 

 

 

 

 

0

 

16

*

13

 

28

40

 

37

19

11

8

 

 

 

 

 

 *

12

 

0

 

0

 

19

 

16

 

13

27

8

 

 

 19

 

 

 

 

 

 

 

28

 *

6

0

 

27

28

 

29

16

16

 

 

 

 

 

 

6 

 

 

 

22

19

10

14

17

18

100

0

0

0

14

17

18

Таблица 1.5.3

 

22

 

26

 

0

 

47

 

45

 

51

24

14

 

10

 

 

 

 

0

 

23

 

52

 

32

 

29

 

41

14

0

14

 

 

 

 

 

 

 

 

 

0

 

29

0

 

40

52

 

49

19

11

8

 

 

 

 

 

 *

0

 

0

 

0

 

7

 

4

 

1

27

8

 

 

 19

 

 

 

 

 

 

 

16

 

18

0

 

39

40

 

41

16

16

 

 

 

 

 

 

 

 

 

22

19

10

14

17

18

100

0

0

0

14

17

18

Таблица 1.5.4

 

23

 

24

 

0

 

48

 

46

 

50

24

14

 

10

 

 

 

 

0

 

24

 

53

 

33

 

30

 

40

14

0

14

 

 

 

 

 

 

 

 

 

0

 

30

0

 

41

53

 

48

19

11

8

 

 

 

 

 

 

0

 *

19

 

0

 

6

 *

3

 

0

27

0

 

 

 

 

 

 

 

 

8

 

 

17

 

19

0

 

40

41

 

40

16

16

 

 

 

 

 

 

 

 

 

22

19

10

14

17

18

100

0

0

0

14

17

18

Таблица 1.5.5

42

 

8

 

0

 

67

 

65

 

69

24

14

 

10

 

 

 

 

0

 

5

 

72

 

52

 

49

 

59

14

0

14

 

 

 

 

 

 

 

 

 

0

 

11

0

 

60

72

 

67

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

25

 

21

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

36

 

0

0

 

21

22

 

21

16

16

 

 

 

 

 

 

 

 

 

22

19

10

14

17

18

100

0

0

0

14

17

18

Таблица 1.5.6

63

 

29

 

0

 

88

 

84

 

48

24

14

 

10

 

 

 

 

0

 *

26

 

93

 

73

 

70

 

38

14

0

14

 

 

 

 

 

 

 

 

 

0

 

32

0

 

81

93

 

46

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

46

 

42

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

15

 

0

0

 

0

*

1

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

17

0

Таблица 1.5.7

99

* 

3

 

0

 

114

 

110

 

74

24

14

 

10

 

 

 

 

0

 

0

 

67

 

47

 

44

* 

12

14

0

14

 

 

 

 

 

 

 

 

 

0

 

6

0

 

107

119

 

72

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

72

 

68

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

41

 

0

0

 

0

*

27

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

17

0

Таблица 1.5.8

126

* 

30

 

0

 

141

 

83

 

101

24

14

 

10

 

 

 

 

0

 

0

 

94

 

74

* 

17

39

14

0

14

 

 

 

 

 

 

 

 

 

0

 

33

0

 

134

92

 

99

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

99

 

41

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 *

14

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

17

0

Таблица 1.5.9

143

* 

47

 

0

 

158

 

66

 

118

24

14

 

10

 

 

 

 

0

 

0

 

77

 

57

0

*

22

14

0

14

 

 

 

 

 

 

 

 

 

0

 

50

0

 

151

75

 

116

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

116

* 

24

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 *

31

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

17

0

Таблица 1.5.10

96

0

 

0

 

111

 *

19

 

71

24

14

 

10

 

 

 

 

0

 

0

 

124

 

101

0

*

69

14

0

14

 

 

 

 

 

 

 

 

 

0

 *

3

0

 

198

122

 

163

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

163

0

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

78

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

17

0

Таблица 1.5.11

77

0

 

0

 

92

 

0

 *

52

24

0

 

10

 

14

 

 

 

0

 

0

 

143

 

120

0

188

14

0

14

 

 

 

 

 

 

 

 

 

0

 *

21

0

 

217

103

 

182

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

182

0

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

97

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

3

0

Таблица 1.5.12

98

0

 

0

 

113

 

0

 *

73

24

0

 

10

 

14

 

 

 

0

 

0

 

164

 

141

0

109

14

0

14

 

 

 

 

 

 

 

 

 

0

 

0

0

 

196

*

82

 

161

19

11

8

 

 

 

 

 

 

0

 

0

 

0

 

209

0

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

118

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

3

0

Таблица 1.5.13

180

0

 

0

 

195

 

0

 

165

24

0

 

10

 

14

 

 

 

0

 

0

 

256

 

233

0

201

14

0

14

 

 

 

 

 

 

 

 

 

0

 

0

0

 

114

0

 *

79

19

8

8

 

 

 

3

 

 

 

0

 

0

 

0

 

301

0

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

210

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

0

0

Таблица 1.5.14

259

0

 

0

 

274

 

0

 

86

24

0

 

10

 

14

 

 

 

0

 

0

 

335

 

312

0

122

14

0

14

 

 

 

 

 

 

 

 

 

0

 

0

0

 *

35

0

 

0

19

8

8

 

 

 

3

 

 

 

0

 

0

 

0

 

380

0

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

289

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

8

0

0

Таблица 1.5.15

294

0

 

0

 

239

 

0

 

121

24

0

 

10

 

14

 

 

 

0

 

0

 

370

 

284

0

157

14

0

14

 

 

 

 

 

 

 

 

 

0

 

0

0

 

0

0

 

0

19

0

8

 

 

8

 

3

 

 

 

0

 

0

 

0

 

345

0

 

0

27

0

 

 

 19

 

 

 

 

 

8

 

 

324

 

0

0

 

0

0

 

0

16

0

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

0

0

0

0

0

0

Переходим к оптимизации опорного плана.

Таблица 1.5.16

22

24

 

7

 

25

 

23

 

29

24

 

10

 

14

 

 

 

1

 

21

 

30

 

10

7

19

14

14

 

 

 

 

 

 

 

 

 

2

 

26

3

 

18

30

 

27

19

8

 

 

8

 

3

 

 

 

22

 

10

 

9

 

29

26

 

23

27

 

 

 19

 

 

 

 

 

8

 

 

18

 

16

13

 

7

18

 

19

16

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

W=14+16+190+70+8*18+42+14*23+90+8*23+190=1262

Таблица 1.5.17

22

24

 

7

 

25

 

23

 

29

24

 

10

8

 

6

 

 

 

1

 

21

 

30

 

10

7

19

14

6

 

 

 

 

 

8

 

 

 

 

2

 

26

3

 

18

30

 

27

19

16

 

 

 

3

 

 

 

22

 

10

 

9

 

29

26

 

23

27

 

 

 19

 

 

 

 

 

8

 

 

18

 

16

13

 

7

18

 

19

16

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

W=6+38+190+70+8*25+42+6*23+8*7+90+8*23+190=1258

Таблица 1.5.17

22

24

 

7

 

25

 

23

 

29

24

 

10

8

 

6

 

 

 

1

 

21

 

30

 

10

7

19

14

3

 

 

 

 

 

11

 

 

 

 

2

 

26

3

 

18

30

 

27

19

19

 

 

 

 

 

 

22

 

10

 

9

 

29

26

 

23

27

 

 

 19

 

 

 

 

 

8

 

 

18

 

16

13

 

7

18

 

19

16

 

 

 

 

 

 

6

 

 

10

 

22

19

10

14

17

18

100

W=3+38+190+70+8*25+42+6*23+11*7+8*23+190=1192

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]