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

Страницы работы

Содержание работы

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

Новосибирский государственный технический университет

Кафедра экономической информатики

Отчет

по лабораторной работе №4

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

Вариант №7

Факультет: Бизнеса

Группа:

Студенты:

Преподаватель:

Новосибирск

2004

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

Задача о ранце

 Требуется загрузить ранец объемом 95 предметами 4 типов. Известен объем каждого предмета vi и его ценность сi . Определить, какие предметы и в каком количестве нужно загрузить в ранец, чтобы суммарная ценность груза была максимальной.

V

V1

V2

V3

V4

C1

C2

C3

C4

95

11

9

7

15

520

470

350

640

Параметры состояния:

x0 = 95,

x1 = 95-11x1,

x2 = 95-11x1-9x2,

x3 = 95-11x1-9x2-7x3,

x4 = 95-11x1-9x2- 7x3-15x4.

Уравнения состояний:

x1 = x0-11x1,

x2 = x1-9x2,

x3 = x2-7x3,

x4 = x3-15x4,

Решение:

1. Решение в ПЭР, как задачи динамического программирования.

ИТОГОВОЕ РЕШЕНИЕ   для 132

Элем.     Чис.эл-в  Прибыл    Свободн.пр-во

1           0       0             95

2           9       4230          14

3           2       700           0

4           0       0             0

Сумм.прибыль = 4930

2. Анализируем процесс решения. Сравниваем результат решения задачи с полученным по методу Гомори и методом ветвей и границ.

По методу Гомори:

┌─────────────────────────────────────────────────────────────────┐

│                   ИТОГОВЫЙ РЕЗУЛЬТАТ ДЛЯ 12     Стр. : 1        │

╞═════════╤══════════╤═══════════╦═════════╤══════════╤═══════════╡

│Переменн.│          │Двойственн.║Переменн.│          │Двойственн.│

No. Имена│ РЕШЕНИЕ  │   оцен    ║No. Имена│ РЕШЕНИЕ  │   оцен    │

╞═════════╪══════════╪═══════════╬═════════╪══════════╪═══════════╡

│1   X1   │    0.0000│   12.8571 ║5   S1   │    0.0000│   47.1429 │

│2   X2   │    9.0000│    0.0000 ║6   S2   │    1.0000│    0.0000 │

│3   X3   │    2.0000│    0.0000 ║7   S3   │    8.0000│    0.0000 │

│4   X4   │    0.0000│  107.1429 ║8   S4   │    0.0000│    2.8571 │

╞═════════╧══════════╧═══════════╩═════════╧══════════╧═══════════╡

│            MAX   величина цел.ф-и = 4930  Итерац.= 4            │

└─────────────────────────────────────────────────────────────────┘

Методом ветвей и границ:

 ┌─────────────────────────────────────────────────────────────────┐

 │                   ИТОГОВЫЙ РЕЗУЛЬТАТ для 12     Стр. : 1        │

 ╞═════════╤══════════╤═══════════╦═════════╤══════════╤═══════════╡

 │Переменн.│          │Целев.ф-ия.║Переменн.│          │Целев.ф-ия.│

 │No. Имена│ Решение  │Коэффициент║No. Имена│ Решение  │Коэффициент│

 ╞═════════╪══════════╪═══════════╬═════════╪══════════╪═══════════╡

 │1   X1   │     0.000│   520.000 ║3   X3   │     2.000│   350.000 │

 │2   X2   │     9.000│   470.000 ║4   X4   │     0.000│   640.000 │

 ╞═════════╧══════════╧═══════════╩═════════╧══════════╧═══════════╡

 │      MAX   величина цел.ф-и =  4930  Всего итераций   = 7       │

 └─────────────────────────────────────────────────────────────────┘

Результаты решений разными методами совпадают. Максимальная величина целевой функции равна 4930, ранец загружают предметами второго и третьего  типа. Следовательно, все три метода одинаково хорошо подходят для решения задач подобной формулировки. Анализируя процесс решения, можно сделать вывод о том, что при решении задачи о ранце методом динамического программирования можно быстрее всего добиться желаемого результата, нежели при решении подобной задачи методом Гомори и методом ветвей и границ.

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

Похожие материалы

Информация о работе