Министерство образования Российской Федерации

Уфимский Государственный Авиационный Технический Университет

 

 

 

 

 

 

 

Кафедра ТК

 

 

 

 

Лабораторная работа №2 на тему:

Динамическое программирование

по предмету: ”Теория принятия решений”

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                    Выполнил:

студент группы Т28-421

Гонтовой Е.С.

Принял: Насыров Р.В.

 

 

 

 

 

 

 

 

 

 

 

Уфа 2006

Задача  6.

 

«Жилище для человечества» – прекрасная благотворительная организация, которая строит дома для бедствующих семей силами добровольцев. Такая семья может выбрать себе дом из трех типоразмеров: 1000, 1100 и 1200 квадратных футов. Дом каждого типоразмера требует выполнения определенного объема работ силами добровольцев. Филиал организации в городе Файтвилл получил пять заявок на предстоящие шесть месяцев. Комитет по надзору дает оценку каждой заявке в численном виде, принимая во внимание различные факторы. Более высокая оценка означает более острую потребность в жилье. В течение предстоящих шести месяцев филиал организации в этом городе может привлечь к работе максимум 23 добровольца. Следующая таблица содержит оценку каждой заявки и необходимое число добровольцев для ее выполнения. Какие заявки следует утвердить комитету?

 

Заявка

Размер дома (футов кв.)

Оценка

Необходимое число добровольцев

1

     2

3

4

5

1200

1000

1100

1000

1200

78

64

68

62

85

7

4

6

5

8

 

Решение задачи.

Данная задача является задачей о загрузке.

 

Постановка задачи:

1) i – тый  этап это   i – тая заявка. Всего этапов 5, по числу заявок;

2) Вариантами решения или альтернативами будет количество i –х заявок; обозначение

 может принимать значения {0,1}.

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

В данной задаче   «весом» будет являться количество человек, необходимое для  i – той заявки.

Роль прибыли выполняет оценка заявки - .

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

 

Решаем методом обратной прогонки:

Этап 5.

0

1

8

0

85

85

1

9

0

85

85

1

10

0

85

85

1

11

0

85

85

1

0

1

12

0

85

85

1

13

0

85

85

1

14

0

85

85

1

15

0

85

85

1

16

0

85

85

1

17

0

85

85

1

18

0

85

85

1

19

0

85

85

1

20

0

85

85

1

21

0

85

85

1

22

0

85

85

1

23

0

85

85

1

 

 

Этап 4.

0

1

5

0

62

62

1

6

0

62

62

1

7

0

62

62

1

8

85

62

85

0

9

85

62

85

0

10

85

62

85

0

11

85

62

85

0

12

85

62

85

0

13

85

147

147

1

14

85

147

147

1

15

85

147

147

1

16

85

147

147

1

17

85

147

147

1

18

85

147

147

1

19

85

147

147

1

20

85

147

147

1

21

85

147

147

1

22

85

147

147

1

23

85

147

147

1

 


Этап 3.

0

1

6

62

68

68

1

7

62

68

68

1

0

1

8

85

68

85

0

9

85

68

85

0

10

85

68

85

0

11

85

130

130

1

12

85

130

130

1

13

147

130

147

0

14

147

153

153

1

15

147

153

153

1

16

147

153

153

1

17

147

153

153

1

18

147

153

153

1

19

147

215

215

1

20

147

215

215

1

21

147

215

215

1

22

147

215

215

1

23

147

215

215

1

 

 

 

 

 

 

 


 

Этап 2.

0

1

4

0

64

64

1

5

0

64

64

1

6

68

64

68

0

7

68

64

68

0

8

85

64

85

0

9

85

64

85

0

10

85

132

132

1

11

130

132

132

1

12

130

149

149

1

13

147

149

149

1

14

153

149

153

0

15

153

194

194

1

16

153

194

194

1

17

153

211

211

1

18

153

217

217

1

19

215

217

217

1

20

215

217

217

1

21

215

217

217

1

22

215

217

217

1

23

215

279

279

1

 

 

 

 

 

 

 

 

 

 

Этап 1.

0

1

7

68

78

78

1

8

85

78

85

0

9

85

78

85

0

10

132

78

132

0

11

132

142

142

1

12

149

142

149

0

13

149

146

149

0

14

153

146

153

0

15

194

163

194

0

16

194

163

194

0

17

211

210

211

0

18

217

210

217

0

19

217

227

227

0

20

217

227

227

1

21

217

231

231

1

22

217

272

272

1

23

279

272

279

0

 

 

 

 

Рекламные ссылки