Файловый архив студентов. Файловый архив студентов.
1267 вузов, 4648 предметов.
/ Регистрация
FAQ Обратная связь Вопросы и предложения
Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Калининградский государственный технический университет
Предмет:
[НЕСОРТИРОВАННОЕ]
Файл:

MоP

.pdf
Скачиваний:
375
Добавлен:
03.05.2015
Размер:
1.98 Mб
Скачать
☆

Тема7. Решениезадачтранспортноготипа

141

______________________________________________________________________________________________

7.1.69

 

 

 

 

Ai

Bj

1

2

3

4

45

155

114

57

190

1

6

2

1

6

2

164

4

5

3

0

7.1.71

 

 

 

 

 

Ai

Bj

1

2

3

4

 

28

98

29

102

69

 

1

4

2

1

6

 

2

69

0

4

5

3

 

7.1.73

 

 

 

 

 

Ai

Bj

1

2

3

4

 

34

71

185

199

94

 

1

4

2

6

1

 

2

126

4

6

2

0

 

7.1.75

 

 

 

 

 

Ai

Bj

1

2

3

4

5

169

136

138

194

87

15

1

0

6

1

1

1

2

143

1

7

2

5

4

7.1.77

 

 

 

 

 

Ai

Bj

1

2

3

4

5

149

16

104

189

8

89

1

1

3

5

1

3

2

107

4

2

0

3

4

7.1.79

 

 

 

 

 

Ai

Bj

1

2

3

4

 

183

89

161

59

157

 

1

0

2

4

7

 

2

10

1

7

6

1

 

7.1.81

 

 

 

 

 

Ai

Bj

1

2

3

4

5

23

7

65

196

187

121

1

1

3

7

4

1

2

51

5

4

3

6

6

7.1.83

 

 

 

 

 

Ai

Bj

1

2

3

 

 

128

56

102

111

 

 

1

6

7

3

 

 

2

97

3

7

5

 

 

3

138

0

0

2

 

 

4

59

7

1

2

 

 

7.1.70

 

 

 

 

 

Ai

Bj

1

2

3

 

 

31

146

17

36

 

 

1

2

5

0

 

 

2

82

5

0

7

 

 

3

127

7

5

6

 

 

7.1.72

 

 

 

 

 

Ai

Bj

1

2

3

4

 

98

55

124

173

158

 

1

0

5

2

3

 

2

23

2

5

6

2

 

7.1.74

 

 

 

 

 

Ai

Bj

1

2

3

4

 

183

113

149

8

65

 

1

2

6

2

4

 

2

49

0

4

3

1

 

3

180

4

7

2

2

 

7.1.76

 

 

 

 

 

Ai

Bj

1

2

3

 

 

163

6

51

125

 

 

1

4

7

2

 

 

2

29

1

2

1

 

 

3

12

6

1

5

 

 

7.1.78

 

 

 

 

 

Ai

Bj

1

2

3

4

5

25

175

173

70

175

31

1

6

4

3

4

0

2

143

7

1

2

3

0

7.1.80

 

 

 

 

 

Ai

Bj

1

2

3

4

 

141

74

112

186

118

 

1

3

2

6

7

 

2

80

0

5

0

7

 

3

170

3

7

6

0

 

7.1.82

 

 

 

 

 

Ai

Bj

1

2

3

4

 

119

157

120

166

191

 

1

7

4

6

3

 

2

90

6

4

3

0

 

3

141

1

1

6

4

 

7.1.84

 

 

 

 

 

Ai

Bj

1

2

 

 

 

139

96

183

 

 

 

1

2

5

 

 

 

2

39

7

6

 

 

 

3

95

6

5

 

 

 

4

33

5

7

 

 

 

5

165

1

3

 

 

 

142 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

7.1.85

 

 

 

Ai

Bj

1

2

3

198

19

119

43

1

1

7

4

2

36

2

4

5

3

198

5

7

1

7.1.87

 

 

 

 

 

Ai

Bj

1

2

 

 

 

146

35

171

 

 

 

1

6

6

 

 

 

2

83

3

4

 

 

 

3

89

5

7

 

 

 

4

35

3

3

 

 

 

7.1.89

 

 

 

 

 

Ai

Bj

1

2

3

4

5

106

165

7

19

93

191

1

5

0

2

0

6

2

11

6

3

7

4

4

7.1.91

 

 

 

 

 

Ai

Bj

1

2

3

4

 

25

16

35

54

164

 

1

2

3

5

4

 

2

161

4

2

2

4

 

7.1.93

 

 

 

 

 

Ai

Bj

1

2

3

4

 

145

33

140

157

117

 

1

2

3

7

2

 

2

75

1

5

7

1

 

7.1.95

 

 

 

 

 

Ai

Bj

1

2

3

4

 

111

124

53

136

136

 

1

0

6

7

6

 

2

113

0

3

7

1

 

3

77

5

2

6

2

 

7.1.97

 

 

 

 

 

Ai

Bj

1

2

3

4

 

89

42

60

97

167

 

1

7

2

5

7

 

2

56

3

2

0

1

 

3

153

4

2

7

2

 

7.1.99

 

 

 

 

 

Ai

Bj

1

2

 

 

 

158

103

77

 

 

 

1

2

6

 

 

 

2

135

1

3

 

 

 

3

27

2

7

 

 

 

4

43

2

3

 

 

 

5

97

1

5

 

 

 

7.1.86

 

 

 

 

 

Ai

Bj

1

2

 

 

 

146

188

18

 

 

 

1

7

1

 

 

 

2

114

2

6

 

 

 

3

19

5

1

 

 

 

4

163

3

2

 

 

 

5

32

2

5

 

 

 

7.1.88

 

 

 

 

 

Ai

Bj

1

2

 

 

 

176

33

113

 

 

 

1

2

6

 

 

 

2

146

1

6

 

 

 

3

94

3

4

 

 

 

4

38

5

1

 

 

 

7.1.90

 

 

 

 

 

Ai

Bj

1

2

3

 

 

89

143

163

166

 

 

1

4

5

3

 

 

2

9

1

3

3

 

 

3

181

6

5

7

 

 

4

156

7

4

6

 

 

7.1.92

 

 

 

 

 

Ai

Bj

1

2

3

4

 

41

131

119

98

170

 

1

6

3

1

3

 

2

122

3

1

6

6

 

7.1.94

 

 

 

 

 

Ai

Bj

1

2

3

4

 

145

95

57

132

29

 

1

3

0

2

1

 

2

103

6

2

4

4

 

3

91

7

2

4

7

 

7.1.96

 

 

 

 

 

Ai

Bj

1

2

3

 

 

41

157

165

45

 

 

1

4

2

6

 

 

2

145

0

4

7

 

 

3

133

6

1

2

 

 

7.1.98

 

 

 

 

 

Ai

Bj

1

2

3

4

5

46

20

104

45

62

169

1

1

4

4

3

7

2

21

0

3

3

1

7

7.1.100

 

 

 

 

 

Ai

Bj

1

2

3

4

5

116

25

86

13

76

137

1

5

3

5

0

3

2

104

3

1

0

1

5

Тема7. Решениезадачтранспортноготипа

143

______________________________________________________________________________________________

7.2. В следующих задачах о назначениях необходимо закрепить работы (Р.i) за исполнителями (И.j) таким образом чтобы общая эффективность выполнения работ была максимальной. В таблицах задана эффективность выполнения соответствующих работисполнителями(пересечениесоответствующихстрокистолбцовтаблицы).

7.2.01

 

 

 

7.2.02

 

 

 

7.2.03

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

3

4

7

7

 

Р.1

4

4

2

2

 

Р.1

0

4

1

3

Р.2

6

1

6

3

 

Р.2

1

6

7

5

 

Р.2

6

4

5

1

Р.3

5

6

4

1

 

Р.3

4

6

5

3

 

Р.3

2

3

5

2

Р.4

5

5

5

6

 

Р.4

3

1

1

4

 

Р.4

1

0

6

6

7.2.04

 

 

 

7.2.05

 

 

 

7.2.06

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

5

2

7

6

 

Р.1

0

2

7

7

 

Р.1

2

5

5

4

Р.2

6

6

4

7

 

Р.2

1

1

2

1

 

Р.2

4

7

7

0

Р.3

4

3

2

2

 

Р.3

3

6

3

7

 

Р.3

1

5

6

4

Р.4

3

2

1

0

 

Р.4

1

0

5

4

 

Р.4

6

1

2

4

7.2.07

 

 

 

7.2.08

 

 

 

7.2.09

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

5

3

1

0

 

Р.1

7

0

2

7

 

Р.1

3

0

0

3

Р.2

7

7

7

1

 

Р.2

4

1

3

7

 

Р.2

2

6

3

0

Р.3

0

5

3

2

 

Р.3

0

2

1

5

 

Р.3

2

3

5

1

Р.4

3

3

4

1

 

Р.4

6

7

2

0

 

Р.4

7

3

4

4

7.2.10

 

 

 

7.2.11

 

 

 

7.2.12

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

2

5

7

 

Р.1

6

0

0

1

 

Р.1

1

4

3

3

Р.2

3

0

5

2

 

Р.2

3

7

4

3

 

Р.2

1

5

1

5

Р.3

2

3

6

3

 

Р.3

6

3

7

3

 

Р.3

2

6

5

6

Р.4

4

3

3

7

 

Р.4

1

3

7

7

 

Р.4

2

5

0

7

7.2.13

 

 

 

7.2.14

 

 

 

7.2.15

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

7

4

3

4

 

Р.1

6

6

4

4

 

Р.1

6

3

0

1

Р.2

3

4

7

3

 

Р.2

6

7

0

0

 

Р.2

0

2

0

0

Р.3

2

4

7

6

 

Р.3

2

7

0

3

 

Р.3

2

3

7

4

Р.4

4

6

0

7

 

Р.4

2

6

7

1

 

Р.4

6

4

4

3

7.2.16

 

 

 

7.2.17

 

 

 

7.2.18

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

6

2

5

5

 

Р.1

3

2

5

7

 

Р.1

1

0

6

6

Р.2

1

0

0

0

 

Р.2

6

5

5

2

 

Р.2

2

1

2

4

Р.3

6

5

2

2

 

Р.3

7

0

0

4

 

Р.3

3

5

2

2

Р.4

4

3

0

4

 

Р.4

2

3

4

1

 

Р.4

5

2

3

3

7.2.19

 

 

 

7.2.20

 

 

 

7.2.21

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

1

3

7

2

 

Р.1

0

7

5

6

 

Р.1

2

1

3

5

Р.2

5

5

6

6

 

Р.2

6

3

6

3

 

Р.2

4

5

0

3

Р.3

6

0

5

6

 

Р.3

4

3

6

6

 

Р.3

3

0

1

4

Р.4

4

0

3

2

 

Р.4

2

1

2

0

 

Р.4

3

0

6

5

144 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

7.2.22

 

 

 

7.2.23

 

 

 

7.2.24

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

3

5

6

 

Р.1

3

3

7

5

 

Р.1

1

5

1

0

Р.2

2

7

4

5

 

Р.2

6

4

4

3

 

Р.2

3

1

7

3

Р.3

3

4

6

4

 

Р.3

3

6

4

6

 

Р.3

4

7

7

3

Р.4

6

2

1

2

 

Р.4

4

4

0

2

 

Р.4

6

4

5

6

7.2.25

 

 

 

7.2.26

 

 

 

7.2.27

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

3

0

1

 

Р.1

6

2

0

0

 

Р.1

2

7

0

6

Р.2

6

1

7

2

 

Р.2

7

7

6

2

 

Р.2

7

4

0

6

Р.3

3

6

2

5

 

Р.3

7

3

4

3

 

Р.3

5

3

3

5

Р.4

2

4

3

2

 

Р.4

4

3

3

3

 

Р.4

4

6

7

3

7.2.28

 

 

 

7.2.29

 

 

 

7.2.30

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

5

2

4

6

 

Р.1

3

2

4

3

 

Р.1

3

0

0

5

Р.2

1

3

0

7

 

Р.2

5

7

2

4

 

Р.2

0

6

3

1

Р.3

0

4

4

7

 

Р.3

7

2

1

5

 

Р.3

6

3

0

0

Р.4

2

7

2

3

 

Р.4

7

7

7

7

 

Р.4

1

3

6

0

7.2.31

 

 

 

7.2.32

 

 

 

7.2.33

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

3

7

6

5

 

Р.1

7

6

5

6

 

Р.1

3

6

3

1

Р.2

6

3

0

6

 

Р.2

5

4

5

5

 

Р.2

3

6

2

3

Р.3

2

6

4

5

 

Р.3

3

5

5

6

 

Р.3

7

1

7

1

Р.4

5

1

6

2

 

Р.4

1

2

0

5

 

Р.4

0

0

7

3

7.2.34

 

 

 

7.2.35

 

 

 

7.2.36

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

7

0

4

6

 

Р.1

6

4

4

3

 

Р.1

0

7

7

5

Р.2

0

1

7

7

 

Р.2

3

1

6

3

 

Р.2

2

7

2

1

Р.3

2

3

6

4

 

Р.3

7

0

3

1

 

Р.3

5

2

3

5

Р.4

7

1

1

6

 

Р.4

0

2

4

6

 

Р.4

6

1

2

1

7.2.37

 

 

 

7.2.38

 

 

 

7.2.39

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

5

0

5

1

 

Р.1

6

1

4

0

 

Р.1

3

2

1

5

Р.2

7

6

3

6

 

Р.2

7

2

2

2

 

Р.2

0

7

1

1

Р.3

4

6

1

6

 

Р.3

6

2

0

6

 

Р.3

2

7

4

5

Р.4

0

4

7

6

 

Р.4

6

5

4

5

 

Р.4

7

1

4

2

7.2.40

 

 

 

7.2.41

 

 

 

7.2.42

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

1

1

7

0

 

Р.1

1

3

7

6

 

Р.1

3

1

2

6

Р.2

4

7

4

3

 

Р.2

7

4

3

1

 

Р.2

4

6

1

6

Р.3

7

7

3

1

 

Р.3

0

0

1

3

 

Р.3

6

1

6

1

Р.4

0

1

0

7

 

Р.4

1

5

1

6

 

Р.4

2

6

2

2

7.2.43

 

 

 

7.2.44

 

 

 

7.2.45

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

0

2

5

 

Р.1

2

1

5

7

 

Р.1

5

5

5

6

Р.2

7

2

4

0

 

Р.2

4

1

6

0

 

Р.2

0

7

4

6

Р.3

2

1

4

4

 

Р.3

4

4

2

4

 

Р.3

3

0

3

7

Р.4

5

7

5

3

 

Р.4

7

3

4

6

 

Р.4

2

7

1

5

Тема7. Решениезадачтранспортноготипа

145

______________________________________________________________________________________________

7.2.46

 

 

 

7.2.47

 

 

 

7.2.48

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

7

5

5

2

 

Р.1

3

2

6

4

 

Р.1

7

3

1

0

Р.2

0

2

6

7

 

Р.2

0

4

5

4

 

Р.2

5

7

4

7

Р.3

0

4

5

2

 

Р.3

1

5

0

5

 

Р.3

7

2

2

6

Р.4

0

1

3

4

 

Р.4

6

0

7

3

 

Р.4

6

1

6

1

7.2.49

 

 

 

7.2.50

 

 

 

7.2.51

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

4

2

6

2

 

Р.1

1

4

2

2

 

Р.1

0

0

1

4

Р.2

2

4

7

7

 

Р.2

4

6

3

6

 

Р.2

5

4

0

7

Р.3

6

2

6

5

 

Р.3

0

5

0

3

 

Р.3

4

1

6

3

Р.4

2

3

6

2

 

Р.4

3

5

3

5

 

Р.4

2

0

4

6

7.2.52

 

 

 

7.2.53

 

 

 

7.2.54

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

3

3

0

2

 

Р.1

0

5

6

4

 

Р.1

2

1

5

0

Р.2

6

4

0

0

 

Р.2

5

1

2

1

 

Р.2

4

6

3

6

Р.3

1

6

0

5

 

Р.3

4

4

5

3

 

Р.3

0

7

2

7

Р.4

2

2

6

2

 

Р.4

7

7

1

1

 

Р.4

6

7

7

3

7.2.55

 

 

 

7.2.56

 

 

 

7.2.57

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

7

1

2

3

 

Р.1

6

1

7

3

 

Р.1

2

0

2

4

Р.2

0

2

1

6

 

Р.2

2

7

4

0

 

Р.2

5

5

1

5

Р.3

4

0

3

3

 

Р.3

0

7

3

2

 

Р.3

5

1

0

3

Р.4

5

6

0

5

 

Р.4

3

6

5

0

 

Р.4

0

2

4

6

7.2.58

 

 

 

7.2.59

 

 

 

7.2.60

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

2

7

2

 

Р.1

6

2

2

3

 

Р.1

7

0

4

4

Р.2

6

1

7

7

 

Р.2

1

3

3

5

 

Р.2

3

2

5

6

Р.3

3

3

0

3

 

Р.3

3

4

6

5

 

Р.3

0

1

3

6

Р.4

0

3

5

5

 

Р.4

0

6

1

2

 

Р.4

6

7

4

3

7.2.61

 

 

 

7.2.62

 

 

 

7.2.63

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

4

0

7

6

 

Р.1

2

0

3

1

 

Р.1

4

1

6

6

Р.2

3

4

1

3

 

Р.2

0

6

7

0

 

Р.2

6

5

5

5

Р.3

3

6

2

2

 

Р.3

0

5

6

5

 

Р.3

1

2

6

6

Р.4

0

5

7

2

 

Р.4

5

1

7

4

 

Р.4

2

6

0

3

7.2.64

 

 

 

7.2.65

 

 

 

7.2.66

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

3

2

0

 

Р.1

3

4

2

0

 

Р.1

5

0

5

4

Р.2

1

6

4

2

 

Р.2

2

3

5

3

 

Р.2

6

5

4

4

Р.3

5

3

1

0

 

Р.3

3

1

4

4

 

Р.3

3

6

6

6

Р.4

3

1

7

5

 

Р.4

4

7

6

7

 

Р.4

1

6

5

7

7.2.67

 

 

 

7.2.68

 

 

 

7.2.69

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

3

7

0

3

 

Р.1

0

5

7

2

 

Р.1

5

4

2

4

Р.2

2

6

5

2

 

Р.2

6

3

3

7

 

Р.2

1

7

3

5

Р.3

5

6

7

5

 

Р.3

6

3

5

1

 

Р.3

6

7

3

2

Р.4

3

4

1

5

 

Р.4

4

1

6

5

 

Р.4

5

7

1

1

146 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

7.2.70

 

 

 

7.2.71

 

 

 

7.2.72

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

4

4

6

4

 

Р.1

1

6

7

6

 

Р.1

4

4

6

5

Р.2

2

0

6

4

 

Р.2

6

0

0

5

 

Р.2

6

5

2

1

Р.3

0

3

6

3

 

Р.3

6

2

4

6

 

Р.3

6

6

1

3

Р.4

2

6

7

6

 

Р.4

2

5

6

2

 

Р.4

1

7

3

5

7.2.73

 

 

 

7.2.74

 

 

 

7.2.75

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

1

2

1

2

 

Р.1

2

2

1

0

 

Р.1

0

2

7

4

Р.2

3

6

4

2

 

Р.2

2

7

2

4

 

Р.2

5

4

5

1

Р.3

3

2

3

6

 

Р.3

6

4

2

5

 

Р.3

6

3

1

1

Р.4

7

2

3

7

 

Р.4

4

2

1

5

 

Р.4

6

6

3

1

7.2.76

 

 

 

7.2.77

 

 

 

7.2.78

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

3

1

6

0

 

Р.1

5

2

1

3

 

Р.1

6

0

2

1

Р.2

5

1

6

0

 

Р.2

7

3

6

6

 

Р.2

5

2

2

3

Р.3

6

2

2

6

 

Р.3

3

2

2

3

 

Р.3

3

5

1

4

Р.4

7

3

4

3

 

Р.4

4

6

0

1

 

Р.4

2

7

7

7

7.2.79

 

 

 

7.2.80

 

 

 

7.2.81

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

4

1

2

2

 

Р.1

1

3

0

6

 

Р.1

6

5

0

0

Р.2

5

6

4

1

 

Р.2

4

5

5

7

 

Р.2

2

0

5

2

Р.3

5

0

7

6

 

Р.3

1

3

4

0

 

Р.3

1

2

2

0

Р.4

0

0

6

0

 

Р.4

6

1

2

4

 

Р.4

7

7

3

0

7.2.82

 

 

 

7.2.83

 

 

 

7.2.84

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

7

2

2

4

 

Р.1

3

4

2

2

 

Р.1

5

2

0

5

Р.2

0

1

4

1

 

Р.2

4

2

3

3

 

Р.2

4

5

5

1

Р.3

5

5

6

1

 

Р.3

1

2

1

3

 

Р.3

0

6

6

4

Р.4

5

6

4

3

 

Р.4

6

0

5

4

 

Р.4

5

7

3

6

7.2.85

 

 

 

7.2.86

 

 

 

7.2.87

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

0

2

2

0

 

Р.1

6

7

3

2

 

Р.1

4

4

6

3

Р.2

0

0

2

0

 

Р.2

7

2

3

7

 

Р.2

7

4

2

1

Р.3

4

1

3

6

 

Р.3

1

7

5

1

 

Р.3

2

7

0

4

Р.4

1

7

6

4

 

Р.4

5

5

3

0

 

Р.4

1

5

0

6

7.2.88

 

 

 

7.2.89

 

 

 

7.2.90

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

4

1

0

 

Р.1

4

2

1

6

 

Р.1

7

5

3

4

Р.2

0

4

2

5

 

Р.2

2

2

5

3

 

Р.2

1

5

7

6

Р.3

5

0

5

0

 

Р.3

5

1

1

1

 

Р.3

3

5

6

2

Р.4

2

6

0

6

 

Р.4

6

6

6

4

 

Р.4

4

1

4

4

7.2.91

 

 

 

7.2.92

 

 

 

7.2.93

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

2

2

1

0

 

Р.1

0

7

5

2

 

Р.1

1

3

7

4

Р.2

0

6

1

6

 

Р.2

0

0

4

5

 

Р.2

6

5

1

1

Р.3

5

7

3

3

 

Р.3

6

3

0

0

 

Р.3

1

3

2

4

Р.4

5

0

3

1

 

Р.4

1

7

7

6

 

Р.4

1

6

5

4

Тема7. Решениезадачтранспортноготипа

147

______________________________________________________________________________________________

7.2.94

 

 

 

7.2.95

 

 

 

7.2.96

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

4

3

3

0

 

Р.1

2

1

5

2

 

Р.1

5

3

7

4

Р.2

0

3

3

0

 

Р.2

4

1

2

4

 

Р.2

5

5

3

4

Р.3

2

7

2

7

 

Р.3

4

0

5

3

 

Р.3

2

2

4

3

Р.4

3

2

0

0

 

Р.4

5

6

2

7

 

Р.4

4

4

7

4

7.2.97

 

 

 

7.2.98

 

 

 

7.2.99

 

 

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

 

 

И.1

И.2

И.3

И.4

Р.1

1

3

5

2

 

Р.1

3

6

6

3

 

Р.1

1

5

6

0

Р.2

6

3

5

3

 

Р.2

1

7

4

4

 

Р.2

7

3

1

3

Р.3

4

6

3

5

 

Р.3

5

0

2

3

 

Р.3

7

5

4

1

Р.4

7

7

5

5

 

Р.4

4

2

0

3

 

Р.4

2

0

7

1

7.2.100

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

И.1

И.2

И.3

И.4

 

 

 

 

 

 

 

 

 

 

 

 

Р.1

7

0

2

1

 

 

 

 

 

 

 

 

 

 

 

 

Р.2

0

4

6

6

 

 

 

 

 

 

 

 

 

 

 

 

Р.3

3

4

7

4

 

 

 

 

 

 

 

 

 

 

 

 

Р.4

1

5

3

1

 

 

 

 

 

 

 

 

 

 

 

 

148 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Тема 8. Применение метода динамического программирования для решения экономических задач

8.1. Общие сведения. Постановка задачи

Решение многих экономических задач может быть разбито на конечное число этапов. Такие задачи могут быть решены методом динамического программирования.

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

Суть этого принципа поясним на следующем примере. Пусть исходный материал поступает на раскрой в виде листов прямоугольной формы заданного размера. Требуется раскроить данный исходный материал на заготовки прямоугольной формы так, чтобы получить их максимальное количество.

Предположим, что на некотором этапе решения задачи получены два ва-

рианта раскроя:

 

 

 

 

 

 

 

 

 

 

Вариант 1

 

 

Вариант 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

. . .

 

 

. .

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

К1

 

К

 

К2

 

К

 

 

 

 

 

 

 

 

 

а

 

 

 

 

а

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пусть по первому варианту раскроена определенная часть листа размера а и получено К1 заготовок. По второму варианту раскроена та же часть листа и получено К2 заготовок. Предположим, что К1 < К2. Так как по первому и второму варианту остаток листа одинакового размера, то при оптимальном раскрое (любым методом, например, методом полного перебора) этой части листа получается одно и то же количество заготовок равное К. Тогда общее количество заготовок, полученное по первому и второму вариантам, можно оценить следующим соотношением: К1 + К < К2 + К.

Тема8. Применениеметодадинамическогопрограммированиядлярешенияэкономическихзадач

149

______________________________________________________________________________________________

Таким образом, так как задача с целевой функцией на максимум, второй вариант, возможно, будет оптимальным решением раскроя всего листа, а первый вариант можно в дальнейшем не рассматривать. Это позволяет сократить количество рассматриваемых вариантов решений.

Методом динамическою программирования могут быть решены, например, следующие задачи.

Задача 1. Пусть в распоряжении предприятия имеется некоторый объем денежных средств V. Предприятие имеет n подразделений. При выделении некоторого объёма денежных средств одному из подразделений, предприятие в целом получает некоторую прибыль. Зависимость прибыли от выделенной суммы, как правило, не является функциональной. Поэтому она задается в виде таблицы.

Ставится задача распределить указанный объем денежных средств между n подразделениями таким образом, чтобы предприятие в целом получило максимальную прибыль.

Задача 2. Потребность региона (района, города) в некотором продукте может быть удовлетворена путем строительства или реконструкции цехов (заводов, предприятий). Для реконструкции цеха по выпуску определенного количества продукции необходимы некоторые капитальные вложения. Зависимость объёма выпускаемой продукции от капитальных вложений не является функциональной и задаётся в виде таблицы.

Ставится задача провести реконструкцию или строительство цехов таким образом, чтобы потребность в продукте была удовлетворена, а затраты на реконструкцию или строительство были минимальными.

8.2. Задача оптимального распределения денежных средств между подразделениями

Решение данной задачи можно разбить на ряд этапов. Например, на первом этапе рассматривают выделение денежных средств первому подразделению. На втором этапе – распределение денежных средств между двумя подраз-

150 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

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

На некотором к-ом этапе рассматривают распределение денежных средств между к-ым подразделением и первыми к-1 подразделениями. Лучшие варианты распределения между к-1 подразделениями выбираются из результатов выполнения предыдущего (к-1)-го этапа.

Рассматриваются такие варианты распределения, которые имеют одинаковую сумму распределяемых денежных средств. И среди таких вариантов выбирается вариант с наибольшей прибылью (или с наименьшими затратами для задачи 2). Остальные варианты, согласно принципа оптимальности Беллмана, на последующих этапах не рассматриваются.

Таким образом, рассматриваются все n этапов. На последнем этапе выбирается оптимальное решение (или решения).

Алгоритм решения задачи 1 1. На первом этапе рассматриваются все варианты выделения денежных

средств первому подразделению.

2. На втором этапе производится распределение денежных средств между первыми двумя подразделениями. Для этих целей строится таблица, столбцами которой являются объёмы выделенных денежных средств первому подразделению, а строками – второму подразделению.

Вклетку на пересечении строки и столбца записываются две величины: сумма выделяемых объемов денежные средств первому и второму подразделению и сумма получаемой при этом прибыли.

Втаблице заполняются только те клетки, в которых общая сумма выде-

ленных средств не превышает величину V. После заполнения таблицы всё множество клеток разбивается на подмножества с одинаковыми объемами выделенных средств. В каждом подмножестве помечаются звездочкой (*) те клетки, которые имеют наибольшую общую прибыль.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
Помощь Обратная связь Вопросы и предложения Пользовательское соглашение Политика конфиденциальности