Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ДЗ1 Лапина.doc
Скачиваний:
8
Добавлен:
24.05.2015
Размер:
660.99 Кб
Скачать

Московский институт стали и сплавов

(ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ)

Домашнее задание № 1

По курсу: «Методы условной оптимизации»

Вариант № 15

Выполнила: ст. гр.МА-02-1

Лапина Е.И.

Проверил: Смирнов А.П.

Москва 2005

Условие задачи:

Владелец грузового автомобиля совершает рейсы по населенным пунктам и доставляет М видов продуктов. Единица i-го вида занимает в кузове объем c(i), (i=1,N). Полезный объем кузова равен Cs.

Спрос q(i) единиц на i-й продукт описывается равномерным законом распределения с плотностью:

| 1/b(i), 0<=q(i)<=b(i)

p(q(i)) = |

| 0, в остальных случаях , где b(i) задано.

Определить значения x(i)- числа погруженных единиц i-го продукта, при которых минимизируется математическое ожидание неудовлетворенного спроса за рейс. Решить задачу при следующих данных: М=4, c(1)=1, с(2)=5/3, с(3)=3, с(4)=10.3, Сs=15.75,

b(1)=20, b(2)=24, b(3)=25, b(4)=27.

Решение:

Формальная постановка задачи.

Задача о загрузке – это задача о рациональной загрузке грузового автомобиля, который имеет ограничения по объему (или грузоподъемности). Каждый помещенный на автомобиль продукт обладает определенным спросом. Задача состоит в определении загрузки автомобиля такими продуктами, которые минимизируют математическое ожидание неудовлетворенного спроса (или которые приносят наибольшую суммарную прибыль).

Пусть mi-количество предметов і-го наименования, подлежащих загрузке, ri-прибыль, которую приносит один загруженный предмет і-го наименования, ci-вес одного предмета і-го наименования. Задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать z=r1m1+r2m2+…+r4m4.

при условии, что

c1m1+с2m2+c3m3+с4m4 <= Сs,

m1,m2,m3,m4 >0 и целые.

Определяется следующим образом:

1. Этап j ставится в соответствии предмету і-го наименования.

Варианты решения на этапе j описываются количеством mi предметов

і-го наименования, подлежащих загрузке. Соответствующая прибыль

равна rimi. Значение mi заключено в пределах от 0 до [Cs/ci], где

[Cs/ci] – целая часть числа Cs/ci.

2. Состояние x(j) на этапе j выражает суммарный вес предметов,

решения о погрузке которых приняты на этапах j,j+1,...n. Это

определение отражает тот факт, что ограничения по весу является

единственным, которое связывает n этапов вместе.

3.ограничения: 0<=X(j)<=4

4.уравнение движения: X(j+1)= X(j)+U(j)*с(i)

5.Значение целевой функции на траектории:

6.формула Беллмана: F(j)=max(f(j)+F(j+1)).

Расчётные таблицы с указанием условно-оптимальных траекторий.

j=3

X(3)

U(3)

X(4)

f(3)

F(4)

f(3)+F(4)

УОТ

15.75

0

15.75

0

0

0

5.45

1

15.75

27

0

27

*

j=2

X(2)

U(2)

X(3)

f(2)

F(3)

f(2)+F(3)

УОТ

15.75

0

15.75

0

0

0

 

12.75

1

15.75

25

0

25

 

9.75

2

15.75

50

0

50

 

6.75

3

15.75

75

0

75

 

3.75

4

15.75

100

0

100

 

0.75

5

15.75

125

0

125

*

 

 

 

 

 

 

 

5.45

0

5.45

0

27

27

 

2.45

1

5.45

25

27

52

*

j=1

X(1)

U(1)

X(2)

f(1)

F(2)

f(1)+F(2)

УОТ

15.75

0

15.75

0

0

0

 

42.25/3

1

15.75

24

0

24

 

37.25/3

2

15.75

48

0

48

 

32.25/3

3

15.75

72

0

72

 

27.25/3

4

15.75

96

0

96

 

22.25/3

5

15.75

120

0

120

 

17.25/3

6

15.75

144

0

144

 

12.25/3

7

15.75

168

0

168

 

7.25/3

8

15.75

192

0

192

 

2.25/3

9

15.75

216

0

216

*

 

 

 

 

 

 

 

12.75

0

12.75

0

25

25

 

33.25/3

1

12.75

24

25

49

 

28.25/3

2

12.75

48

25

73

 

23.25/3

3

12.75

72

25

97

 

18.25/3

4

12.75

96

25

121

 

13.25/3

5

12.75

120

25

145

 

8.25/3

6

12.75

144

25

169

 

3.25/3

7

12.75

168

25

193

*

 

 

 

 

 

 

 

9.75

0

9.75

0

50

50

 

24.25/3

1

9.75

24

50

74

 

19.25/3

2

9.75

48

50

98

 

14.25/3

3

9.75

72

50

122

 

9.25/3

4

9.75

96

50

146

 

4.25/3

5

9.75

120

50

170

*

 

 

 

 

 

 

 

6.75

0

6.75

0

75

75

 

15.25/3

1

6.75

24

75

99

 

10.25/3

2

6.75

48

75

123

 

5.25/3

3

6.75

72

75

147

 

0.25/3

4

6.75

96

75

171

*

 

 

 

 

 

 

 

3.75

0

3.75

0

100

100

 

6.25/3

1

3.75

24

100

124

 

1.25/3

2

3.75

48

100

148

*

 

 

 

 

 

 

 

X(1)

U(1)

X(2)

f(1)

F(2)

f(1)+F(2)

УОТ

5.45

0

5.45

0

27

27

 

11.35/3

1

5.45

24

27

51

 

6.35/3

2

5.45

48

27

75

 

1.35/3

3

5.45

72

27

99

*

 

 

 

 

 

 

 

2.45

0

2.45

0

52

52

 

2.35/3

1

2.45

24

52

76

*

j=0

X(0)

U(0)

X(1)

f(0)

F(1)

f(0)+F(1)

УОТ

15.75

0

15.75

0

0

0

 

14.75

1

15.75

20

0

20

 

13.75

2

15.75

40

0

40

 

12.75

3

15.75

60

0

60

 

11.75

4

15.75

80

0

80

 

10.75

5

15.75

100

0

100

 

9.75

6

15.75

120

0

120

 

8.75

7

15.75

140

0

140

 

7.75

8

15.75

160

0

160

 

6.75

9

15.75

180

0

180

 

5.75

10

15.75

200

0

200

 

4.75

11

15.75

220

0

220

 

3.75

12

15.75

240

0

240

 

2.75

13

15.75

260

0

260

 

1.75

14

15.75

280

0

280

 

0.75

15

15.75

300

0

300

*

 

 

 

 

 

 

 

42.25/3

0

42.25/3

0

24

24

 

39.25/3

1

42.25/3

20

24

44

 

36.25/3

2

42.25/3

40

24

64

 

33.25/3

3

42.25/3

60

24

84

 

30.25/3

4

42.25/3

80

24

104

 

27.25/3

5

42.25/3

100

24

124

 

24.25/3

6

42.25/3

120

24

144

 

21.25/3

7

42.25/3

140

24

164

 

18.25/3

8

42.25/3

160

24

184

 

15.25/3

9

42.25/3

180

24

204

 

12.25/3

10

42.25/3

200

24

224

 

9.25/3

11

42.25/3

220

24

244

 

6.25/3

12

42.25/3

240

24

264

 

3.25/3

13

42.25/3

260

24

284

 

0.25/3

14

42.25/3

280

24

304

*

 

 

 

 

 

 

 

37.25/3

0

37.25/3

0

48

48

 

34.25/3

1

37.25/3

20

48

68

 

31.25/3

2

37.25/3

40

48

88

 

28.25/3

3

37.25/3

60

48

108

 

25.25/3

4

37.25/3

80

48

128

 

22.25/3

5

37.25/3

100

48

148

 

19.25/3

6

37.25/3

120

48

168

 

16.25/3

7

37.25/3

140

48

188

 

13.25/3

8

37.25/3

160

48

208

 

10.25/3

9

37.25/3

180

48

228

 

7.25/3

10

37.25/3

200

48

248

 

4.25/3

11

37.25/3

220

48

268

 

1.25/3

12

37.25/3

240

48

288

*

 

 

 

 

 

 

 

32.25/3

0

32.25/3

0

72

72

 

29.25/3

1

32.25/3

20

72

92

 

26.25/3

2

32.25/3

40

72

112

 

23.25/3

3

32.25/3

60

72

132

 

20.25/3

4

32.25/3

80

72

152

 

17.25/3

5

32.25/3

100

72

172

 

14.25/3

6

32.25/3

120

72

192

 

11.25/3

7

32.25/3

140

72

212

 

8.25/3

8

32.25/3

160

72

232

 

5.25/3

9

32.25/3

180

72

252

 

2.25/3

10

32.25/3

200

72

272

*

 

 

 

 

 

 

 

27.25/3

0

27.25/3

0

96

96

 

24.25/3

1

27.25/3

20

96

116

 

21.25/3

2

27.25/3

40

96

136

 

18.25/3

3

27.25/3

60

96

156

 

15.25/3

4

27.25/3

80

96

176

 

12.25/3

5

27.25/3

100

96

196

 

9.25/3

6

27.25/3

120

96

216

 

6.25/3

7

27.25/3

140

96

236

 

3.25/3

8

27.25/3

160

96

256

 

0.25/3

9

27.25/3

180

96

276

*

 

 

 

 

 

 

 

22.25/3

0

22.25/3

0

120

120

 

19.25/3

1

22.25/3

20

120

140

 

16.25/3

2

22.25/3

40

120

160

 

13.25/3

3

22.25/3

60

120

180

 

10.25/3

4

22.25/3

80

120

200

 

7.25/3

5

22.25/3

100

120

220

 

4.25/3

6

22.25/3

120

120

240

 

1.25/3

7

22.25/3

140

120

260

*

 

 

 

 

 

 

 

17.25/3

0

17.25/3

0

144

144

 

14.25/3

1

17.25/3

20

144

164

 

11.25/3

2

17.25/3

40

144

184

 

8.25/3

3

17.25/3

60

144

204

 

5.25/3

4

17.25/3

80

144

224

 

2.25/3

5

17.25/3

100

144

244

*

 

 

 

 

 

 

 

12.25/3

0

12.25/3

0

168

168

 

9.25/3

1

12.25/3

20

168

188

 

6.25/3

2

12.25/3

40

168

208

 

3.25/3

3

12.25/3

60

168

228

 

0.25/3

4

12.25/3

80

168

248

*

 

 

 

 

 

 

 

7.25/3

0

7.25/3

0

192

192

 

4.25/3

1

7.25/3

20

192

212

 

1.25/3

2

7.25/3

40

192

232

*

 

 

 

 

 

 

 

12.75

0

12.75

0

25

25

 

11.75

1

12.75

20

25

45

 

10.75

2

12.75

40

25

65

 

9.75

3

12.75

60

25

85

 

8.75

4

12.75

80

25

105

 

7.75

5

12.75

100

25

125

 

6.75

6

12.75

120

25

145

 

5.75

7

12.75

140

25

165

 

4.75

8

12.75

160

25

185

 

3.75

9

12.75

180

25

205

 

2.75

10

12.75

200

25

225

 

1.75

11

12.75

220

25

245

 

0.75

12

12.75

240

25

265

*

 

 

 

 

 

 

 

33.25/3

0

33.25/3

0

49

49

 

30.25/3

1

33.25/3

20

49

69

 

27.25/3

2

33.25/3

40

49

89

 

24.25/3

3

33.25/3

60

49

109

 

21.25/3

4

33.25/3

80

49

129

 

18.25/3

5

33.25/3

100

49

149

 

15.25/3

6

33.25/3

120

49

169

 

12.25/3

7

33.25/3

140

49

189

 

9.25/3

8

33.25/3

160

49

209

 

6.25/3

9

33.25/3

180

49

229

 

3.25/3

10

33.25/3

200

49

249

 

0.25/3

11

33.25/3

220

49

269

*

 

 

 

 

 

 

 

28.25/3

0

28.25/3

0

73

73

 

25.25/3

1

28.25/3

20

73

93

 

22.25/3

2

28.25/3

40

73

113

 

19.25/3

3

28.25/3

60

73

133

 

16.25/3

4

28.25/3

80

73

153

 

13.25/3

5

28.25/3

100

73

173

 

10.25/3

6

28.25/3

120

73

193

 

7.25/3

7

28.25/3

140

73

213

 

4.25/3

8

28.25/3

160

73

233

 

1.25/3

9

28.25/3

180

73

253

*

 

 

 

 

 

 

 

23.25/3

0

23.25/3

0

97

97

 

20.25/3

1

23.25/3

20

97

117

 

17.25/3

2

23.25/3

40

97

137

 

14.25/3

3

23.25/3

60

97

157

 

11.25/3

4

23.25/3

80

97

177

 

8.25/3

5

23.25/3

100

97

197

 

5.25/3

6

23.25/3

120

97

217

 

2.25/3

7

23.25/3

140

97

237

*

 

 

 

 

 

 

 

18.25/3

0

18.25/3

0

121

121

 

15.25/3

1

18.25/3

20

121

141

 

12.25/3

2

18.25/3

40

121

161

 

9.25/3

3

18.25/3

60

121

181

 

6.25/3

4

18.25/3

80

121

201

 

3.25/3

5

18.25/3

100

121

221

 

0.25/3

6

18.25/3

120

121

241

*

 

 

 

 

 

 

 

13.25/3

0

13.25/3

0

145

145

 

10.25/3

1

13.25/3

20

145

165

 

7.25/3

2

13.25/3

40

145

185

 

4.25/3

3

13.25/3

60

145

205

 

1.25/3

4

13.25/3

80

145

225

*

 

 

 

 

 

 

 

8.25/3

0

8.25/3

0

169

169

 

5.25/3

1

8.25/3

20

169

189

 

2.25/3

2

8.25/3

40

169

209

*

 

 

 

 

 

 

 

3.25/3

0

3.25/3

0

193

193

 

0.25/3

1

3.25/3

20

193

213

*

 

 

 

 

 

 

 

9.75

0

9.75

0

50

50

 

8.75

1

9.75

20

50

70

 

7.75

2

9.75

40

50

90

 

6.75

3

9.75

60

50

110

 

5.75

4

9.75

80

50

130

 

4.75

5

9.75

100

50

150

 

3.75

6

9.75

120

50

170

 

2.75

7

9.75

140

50

190

 

1.75

8

9.75

160

50

210

 

0.75

9

9.75

180

50

230

*

 

 

 

 

 

 

 

24.25/3

0

24.25/3

0

74

74

 

21.25/3

1

24.25/3

20

74

94

 

18.25/3

2

24.25/3

40

74

114

 

15.25/3

3

24.25/3

60

74

134

 

12.25/3

4

24.25/3

80

74

154

 

9.25/3

5

24.25/3

100

74

174

 

6.25/3

6

24.25/3

120

74

194

 

3.25/3

7

24.25/3

140

74

214

 

0.25/3

8

24.25/3

160

74

234

*

 

 

 

 

 

 

 

19.25/3

0

19.25/3

0

98

98

 

16.25/3

1

19.25/3

20

98

118

 

13.25/3

2

19.25/3

40

98

138

 

10.25/3

3

19.25/3

60

98

158

 

7.25/3

4

19.25/3

80

98

178

 

4.25/3

5

19.25/3

100

98

198

 

1.25/3

6

19.25/3

120

98

218

*

 

 

 

 

 

 

 

14.25/3

0

14.25/3

0

122

122

 

11.25/3

1

14.25/3

20

122

142

 

8.25/3

2

14.25/3

40

122

162

 

5.25/3

3

14.25/3

60

122

182

 

2.25/3

4

14.25/3

80

122

202

*

 

 

 

 

 

 

 

9.25/3

0

9.25/3

0

146

146

 

6.25/3

1

9.25/3

20

146

166

 

3.25/3

2

9.25/3

40

146

186

 

0.25/3

3

9.25/3

60

146

206

*

 

 

 

 

 

 

 

4.25/3

0

4.25/3

0

170

170

 

1.25/3

1

4.25/3

20

170

190

*

 

 

 

 

 

 

 

6.75

0

6.75

0

75

75

 

5.75

1

6.75

20

75

95

 

4.75

2

6.75

40

75

115

 

3.75

3

6.75

60

75

135

 

2.75

4

6.75

80

75

155

 

1.75

5

6.75

100

75

175

 

0.75

6

6.75

120

75

195

*

 

 

 

 

 

 

 

15.25/3

0

15.25/3

0

99

99

 

12.25/3

1

15.25/3

20

99

119

 

9.25/3

2

15.25/3

40

99

139

 

6.25/3

3

15.25/3

60

99

159

 

3.25/3

4

15.25/3

80

99

179

 

0.25/3

5

15.25/3

100

99

199

*

 

 

 

 

 

 

 

10.25/3

0

10.25/3

0

123

123

 

7.25/3

1

10.25/3

20

123

143

 

4.25/3

2

10.25/3

40

123

163

 

1.25/3

3

10.25/3

60

123

183

*

 

 

 

 

 

 

 

5.25/3

0

5.25/3

0

147

147

 

2.25/3

1

5.25/3

20

147

167

*

 

 

 

 

 

 

 

3.75

0

3.75

0

100

100

 

2.75

1

3.75

20

100

120

 

1.75

2

3.75

40

100

140

 

0.75

3

3.75

60

100

160

*

 

 

 

 

 

 

 

6.25/3

0

6.25/3

0

124

124

 

3.25/3

1

6.25/3

20

124

144

 

0.25/3

2

6.25/3

40

124

164

*

 

 

 

 

 

 

 

5.45

0

5.45

0

27

27

 

4.45

1

5.45

20

27

47

 

3.45

2

5.45

40

27

67

 

2.45

3

5.45

60

27

87

 

1.45

4

5.45

80

27

107

 

0.45

5

5.45

100

27

127

*

 

 

 

 

 

 

 

2.45

0

2.45

0

52

52

 

1.45

1

2.45

20

52

72

 

0.45

2

2.45

40

52

92

*

 

 

 

 

 

 

 

2.35/3

0

2.35/3

0

76

76

*

 

 

 

 

 

 

 

11.35/3

0

11.35/3

0

51

51

 

8.35/3

1

11.35/3

20

51

71

 

5.35/3

2

11.35/3

40

51

91

 

2.35/3

3

11.35/3

60

51

111

*

 

 

 

 

 

 

 

6.35/3

0

6.35/3

0

75

75

 

3.35/3

1

6.35/3

20

75

95

 

0.35/3

2

6.35/3

40

75

115

*

 

 

 

 

 

 

 

1.35/3

0

1.35/3

0

99

99

*

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